اثبات بدهی‌ها

یک متولی (custodian) به هر مشتری یک مانده بدهکار است. این برنامه ثابت می‌کند که مجموع مانده‌ها از رقم ذخیره‌ای که متولی منتشر کرده بیشتر نیست، بی‌آنکه حتی یک مانده یا مجموع کل را منتشر کند. هر مشتری می‌تواند با چند خط Python و بدون هیچ ابزار ویژه‌ای بررسی کند که مانده‌اش شمرده شده است.

Example programs تنظیمات مشترکی را دارد که هر چهار صفحهٔ نمونه از آن استفاده می‌کنند.

1. چه چیزی را اثبات می‌کند

متولی یک درخت مرکل مجموعی (Merkle sum tree) می‌سازد. هر برگ یک حساب است: هشِ شناسه و مانده‌ی مشتری، و مانده در کنار آن. هر گره هشِ دو فرزندش و مجموع آن‌هاست، و مجموع این دو در کنارش آمده است. بنابراین ریشه حامل مجموع تمام مانده‌های زیر خود است.

درخت درون برنامه و از فهرست خصوصی حساب‌ها ساخته می‌شود. فراخوانی این موارد را اثبات می‌کند:

1. ریشه‌ای که در رسید منتشر شده، ریشهٔ یک درخت مجموعی بر روی حساب‌هایی است که متولی ارائه کرده است؛
2. هر مجموع در آن، مجموع درستِ دو مقدار زیرین خود است، بدون سرریز؛
3. مجموع در ریشه حداکثر برابر رقم ذخیره‌ای است که هنگام استقرار (deploy) تثبیت شده است.

مورد ۲ چیزی است که یک درخت مجموعی منتشرشده بدون اثبات نمی‌تواند تضمین کند. حملهٔ شناخته‌شده بر یک درخت مجموعیِ ساده، متولی‌ای است که مجموع یک والد را کمتر از مجموع فرزندانش می‌نویسد، و هیچ مشتری‌ای نمی‌تواند این را از روی یک مسیر واحد تشخیص دهد. در اینجا مجموع‌ها را خود برنامه محاسبه می‌کند و اثباتی برای هر محاسبهٔ دیگر وجود ندارد.

آنچه اثبات پوشش نمی‌دهد کامل بودن (completeness) است: متولی انتخاب می‌کند کدام حساب‌ها وارد شوند. این شکاف را مشتریان می‌بندند. هر مشتری بررسی می‌کند که برگی با شناسه و مانده‌ی او زیر ریشهٔ منتشرشده وجود دارد (بخش ۷). حسابی که حذف شده باشد، توسط صاحبش پیدا می‌شود.

2. رابط

رقم ذخیره به دو دلیل در بخش عمومی است و نه در خروجی‌ها. جایی برای آن نیست: وضعیت، تعداد و یک ریشهٔ 160 بیتی همهٔ شکاف‌ها را پر می‌کنند. و ادعا را پیش از وجود اثبات اعلام می‌کند: استقرار برنامه، «ذخایر R، اسنپ‌شات S» را منتشر می‌کند و فراخوانی بعدی یا اثبات می‌کند که مانده‌ها زیر R جا می‌گیرند یا وضعیت 2 را برمی‌گرداند.

هش‌ها، دقیقاً:

leaf  = SHA-256( be32(0) ‖ id (16 bytes) ‖ be64(balance) )                                  28 bytes
node  = SHA-256( be32(1) ‖ left hash ‖ be64(left sum) ‖ right hash ‖ be64(right sum) )      84 bytes
empty = leaf with id 0 and balance 0

درخت همیشه 32 برگ دارد. حساب‌ها از چپ آن را پر می‌کنند و برگ‌های خالی بقیه را. 0 و 1 ابتدایی مانع می‌شوند که یک برگ هرگز به عنوان گره خوانده شود.

ترتیب بایت. SHA-256 در همه جا big-endian است و syscall مربوط به SHA256 بلوک 64 بایتی خود را به صورت شانزده کلمهٔ big-endian می‌گیرد. بنابراین این برنامه شناسه را به صورت چهار کلمهٔ big-endian می‌خواند و ریشه را به صورت کلمه‌های big-endian منتشر می‌کند: خروجی 2 به صورت هگز چاپ شود، هشت رقم هگز اول ریشه است. این قرارداد برعکس برنامهٔ Keccak است، زیرا دو هش بر ترتیب‌های بایتیِ مخالف تعریف شده‌اند.

3. گست (guest)

my-guests/solvency/src/main.rs، کامل:

#![no_std]
#![no_main]

use guest_sdk::{halt, read_input, read_public, sha256_compress, write_output};

/// The tree always has 32 leaves. Accounts fill it from the left; the rest are empty leaves.
const LEAVES: usize = 32;

const SOLVENT: u32 = 1;
const INSOLVENT: u32 = 2;
const TOO_MANY: u32 = 3;
const OVERFLOW: u32 = 4;

const LEAF_TAG: u32 = 0;
const NODE_TAG: u32 = 1;

/// SHA-256's initial state (FIPS 180-4 §5.3.3).
const IV: [u32; 8] = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
];

#[derive(Clone, Copy)]
struct Node {
    hash: [u32; 8],
    sum: u64,
}

/// SHA-256 of the 28 bytes `be32(0) ‖ id (16 bytes) ‖ be64(balance)`. The message, its `0x80`
/// terminator and its bit length fit one 64-byte block, so a leaf is one compression.
fn leaf(id: &[u32; 4], balance: u64) -> Node {
    let mut buf = [0u32; 24];
    buf[0] = LEAF_TAG;
    buf[1..5].copy_from_slice(id);
    buf[5] = (balance >> 32) as u32;
    buf[6] = balance as u32;
    buf[7] = 0x8000_0000;
    buf[15] = 28 * 8;
    buf[16..].copy_from_slice(&IV);
    sha256_compress(&mut buf);
    let mut hash = [0u32; 8];
    hash.copy_from_slice(&buf[16..]);
    Node { hash, sum: balance }
}

/// SHA-256 of the 84 bytes `be32(1) ‖ left hash ‖ be64(left sum) ‖ right hash ‖ be64(right sum)`:
/// two compressions. `None` when the two sums do not fit a u64.
fn parent(l: &Node, r: &Node) -> Option<Node> {
    let sum = l.sum.checked_add(r.sum)?;
    let mut buf = [0u32; 24];
    buf[16..].copy_from_slice(&IV);
    // Block 1: words 0..16 of the message.
    buf[0] = NODE_TAG;
    buf[1..9].copy_from_slice(&l.hash);
    buf[9] = (l.sum >> 32) as u32;
    buf[10] = l.sum as u32;
    buf[11..16].copy_from_slice(&r.hash[..5]);
    sha256_compress(&mut buf);
    // Block 2: the last five words, the terminator, zeros, the bit length.
    buf[..3].copy_from_slice(&r.hash[5..]);
    buf[3] = (r.sum >> 32) as u32;
    buf[4] = r.sum as u32;
    buf[5] = 0x8000_0000;
    buf[6..15].fill(0);
    buf[15] = 84 * 8;
    sha256_compress(&mut buf);
    let mut hash = [0u32; 8];
    hash.copy_from_slice(&buf[16..]);
    Some(Node { hash, sum })
}

/// Public segment, fixed at deploy: [reserves low word, reserves high word, snapshot label].
/// Private input: [n, then n accounts of (id: 4 words, balance low, balance high)].
/// Outputs: [status, n, root (first 5 words), 0].
#[no_mangle]
pub extern "C" fn main() -> ! {
    let reserves = read_public(0) as u64 | (read_public(1) as u64) << 32;

    let n = read_input(0) as usize;
    if n > LEAVES {
        write_output(0, TOO_MANY);
        halt();
    }

    let empty = leaf(&[0; 4], 0);
    let mut row = [empty; LEAVES];
    for (i, slot) in row.iter_mut().enumerate().take(n) {
        let at = 1 + 6 * i as u32;
        let id = [read_input(at), read_input(at + 1), read_input(at + 2), read_input(at + 3)];
        let balance = read_input(at + 4) as u64 | (read_input(at + 5) as u64) << 32;
        *slot = leaf(&id, balance);
    }

    // Fold the row in place, a level at a time, until one node is left.
    let mut width = LEAVES;
    while width > 1 {
        width /= 2;
        for i in 0..width {
            match parent(&row[2 * i], &row[2 * i + 1]) {
                Some(p) => row[i] = p,
                None => {
                    write_output(0, OVERFLOW);
                    halt();
                }
            }
        }
    }
    let root = row[0];

    write_output(0, if root.sum <= reserves { SOLVENT } else { INSOLVENT });
    write_output(1, n as u32);
    for k in 0..5 {
        write_output(2 + k as u32, root.hash[k]);
    }
    halt();
}

پدینگ را دستی می‌نویسیم. guest_sdk::sha256 هر رشتهٔ بایتی را می‌گیرد و آن را بایت به بایت کپی می‌کند. هر پیام در اینجا از کلمه‌های کامل با طولی معلوم تشکیل شده است، پس برنامه بلوک 16 کلمه‌ای را مستقیم پر می‌کند: کلمه‌های پیام، سپس 0x80000000، صفرها، و طول بیتی در آخرین کلمه. یک برگ یک فشرده‌سازی است. 84 بایتِ یک گره به بلوک دوم سرریز می‌کند، پس یک گره دو فشرده‌سازی است.

مانده‌ها u64 هستند و مجموع‌ها بررسی می‌شوند. مانده نمی‌تواند منفی باشد، چون این نوع مقدار منفی ندارد، و این راه کلاسیک دیگرِ کوچک کردن مجموع را حذف می‌کند. checked_add سرریز را به جای مجموعِ دور زده، به وضعیت 4 تبدیل می‌کند.

نتیجهٔ ورشکستگی هم یک نتیجه است. وضعیت 2 یک توقف عادی همراه با ریشهٔ منتشرشده است. متولی نمی‌تواند برای مانده‌هایی که از رقم ذخیره بیشترند رسید با وضعیت 1 بگیرد، و رسید با وضعیت 2 دقیقاً اثباتی بر همین است.

4. سمت میزبان (host)

solvency.py فقط از کتابخانهٔ استاندارد Python استفاده می‌کند:

solvency.py setup   <accounts.csv> <reserves> <snapshot label>   writes public.txt, prints the root
solvency.py witness <accounts.csv>                 prints the private words
solvency.py path    <accounts.csv> <row>           prints that account's inclusion proof (JSON)
solvency.py verify  <proof.json> <root prefix hex> checks a proof against a receipt's root

دو هشِ موجود در آن، تمام مشخصاتی است که یک مشتری لازم دارد:

def leaf(ident: bytes, balance: int):
    return hashlib.sha256(struct.pack(">I", 0) + ident + struct.pack(">Q", balance)).digest(), balance

def parent(l, r):
    h = hashlib.sha256(struct.pack(">I", 1) + l[0] + struct.pack(">Q", l[1]) + r[0] + struct.pack(">Q", r[1]))
    return h.digest(), l[1] + r[1]

نمونه دوازده حساب در demo-accounts.csv دارد، در هر خط یک id,balance، با مانده‌ها به واحد 10⁻⁸ (دقتی که توکنِ پل‌شده‌ای مانند zUSD به کار می‌برد). مجموع آن‌ها 100,215.185678 است. متولی ذخایر 101,000 را ادعا می‌کند:

$ python3 solvency.py setup demo-accounts.csv 10100000000000 20260930
root 46b78564d60f75bdc9552d8ad1c4aadf411354054be3ffb80337b8549471a82c
root prefix 46b78564d60f75bdc9552d8ad1c4aadf41135405
root words 1186432356 3591337405 3377802634 3519326943 1091785733
liabilities 10021518567800
wrote public.txt
$ cat public.txt
2531887104 2351 20260930

2351 × 2³² + 2531887104 برابر 10,100,000,000,000 است. خط liabilities دید خود متولی است و هرگز منتشر نمی‌شود.

شناسه‌ها باید یکتا و غیرقابل حدس باشند. اگر به دو مشتری با مانده‌ی یکسان یک برگ یکسان داده شود، متولی می‌تواند یک بدهی را برای هر دو بشمارد. شناسه‌ای که فقط مشتری‌اش آن را از آنِ خود بشناسد مانع این کار می‌شود، و شناسه‌ای که نتوان حدس زد مانع می‌شود مشتری‌ای که هشِ همسایه را می‌بیند، برای مانده‌ی همسایه حدس بیازماید. نمونه از 16 بایت اول یک هش استفاده می‌کند. یک استقرار واقعی شناسه را از حساب مشتری و یک nonce مخصوص هر اسنپ‌شات استخراج می‌کند و به مشتری نشان می‌دهد.

5. ساخت و اجرا

$ rand-guest build my-guests/solvency --max-words 65535
994 words against a cap of 65535 (fits); 0 ecall(s) with a non-static a7
OK
wrote my-guests/solvency/image.bin and its .sha256 (994 words, hc 5559791a05bd9269bf7fc4e893c05e8b21defe5ef966d831b49ea463fb4552d3, program id 697412b5db65647164c21b27e4b4feb0b5f0b9fce2381157cd0786bfecf1769f)
$ cd my-guests/solvency
$ python3 solvency.py witness demo-accounts.csv > witness.txt
$ rand-guest run image.bin --public $(cat public.txt) --input $(cat witness.txt) --tier 14
out[0] = 1
out[1] = 12
out[2] = 1186432356
out[3] = 3591337405
out[4] = 3377802634
out[5] = 3519326943
out[6] = 1091785733
out[7] = 0
cycles 7492
tier 14
tier 14: fits (cycles 7762 of 16383, Poseidon2 permutations 270 of 2048)

وضعیت 1، دوازده حساب، و پنج کلمهٔ ریشه که اسکریپت چاپ کرد. witness شامل 73 کلمه است: تعداد، و شش کلمه برای هر حساب.

با کاهش رقم ذخیره به 100 واحد (--public 100 0 1) همان حساب‌ها out[0] = 2 می‌دهند. تعداد 33 مقدار out[0] = 3 می‌دهد. دو حساب که مانده‌هایشان از 2⁶⁴ بگذرد out[0] = 4 می‌دهند.

6. بودجه

تعداد فشرده‌سازی‌ها برابر است با n برگ، یک برگ خالی (یک بار محاسبه و کپی می‌شود)، و دو برای هر یک از 31 گره. یک فراخوانی حداکثر 128 فشرده‌سازی می‌تواند به کار برد و رده 14 بالاترین ردهٔ مجاز برای یک فراخوانی است، پس 32 حساب نزدیک به حدی است که یک فراخوانی در این طراحی می‌تواند اثبات کند. درخت 64 برگی به 190 فشرده‌سازی نیاز دارد و جا نمی‌گیرد.

این اندازهٔ نمایشی است. فراتر رفتن از آن یعنی تقسیم درخت میان چند فراخوانی و حمل یک تعهد به ریشه و مجموع هر زیردرخت به یک فراخوانی نهایی، الگویی که Write a program برای هر کاری فراتر از بودجه شرح می‌دهد. این نمونه چنین کاری نمی‌کند.

از chain 18 هر فشرده‌سازی 64 گاز هزینه دارد، در برابر 1 برای یک چرخهٔ عادی. کیف پول گاز دقیق یک اجرا و سقفی را که اعلام می‌کند چاپ می‌کند:

gas: 12489 (declaring 16384, tier 14)

هر ردیف 1 گاز هزینه دارد و هر فشرده‌سازی 63 گاز بیشتر: 7,764 ردیف به‌علاوهٔ 75 × 63 برابر 12,489 است. بیش از یک‌سوم گاز صرف هش کردن می‌شود. (کیف پول دو ردیف بیشتر از rand-guest run می‌شمارد، به دلیل مقید کردن تراکنش که chain 18 به بخش عمومی یک فراخوانی اضافه می‌کند.)

7. بررسی یک مشتری

متولی مسیر هر مشتری را به او می‌دهد: هش و مجموع همسایه در هر یک از پنج سطح.

$ python3 solvency.py path demo-accounts.csv 6 > proof6.json
$ head -12 proof6.json
{
 "id": "f8f4e4a0c855aad0d0f9ae5bab108333",
 "balance": 1820025000000,
 "path": [
  {
   "hash": "e39eaaabec5cca1fe4c76ce656692be631a39e807876f93bdd7baf8b057d6997",
   "sum": 6600000000,
   "sibling_is_left": false
  },
  {
   "hash": "4732f069886c966e6429ee9063f73429bf153eb2575cf2a28f00f27b7d0d89c6",
   "sum": 31500000000,

مشتری ریشه را از شناسه و مانده‌ی خودش دوباره محاسبه می‌کند و 20 بایت اول آن را با خروجی‌های 2 تا 6 رسید مقایسه می‌کند:

$ python3 solvency.py verify proof6.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix 46b78564d60f75bdc9552d8ad1c4aadf41135405 MATCH

مسیری برای مانده‌ای که یک واحد بیشتر از مانده‌ی موجود در درخت است به ریشه نمی‌رسد:

$ python3 solvency.py verify tampered.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix e9a1b4cbe49e412214b97afe73348fa7c555fa7a DOES NOT MATCH

کل بررسی همان توابع leaf و parent بالاست که پنج بار اعمال می‌شوند. مشتری‌ای که نمی‌خواهد اسکریپت متولی را اجرا کند می‌تواند خودش آن را بنویسد.

یک مسیر مجموع همسایه‌ها را به مشتری نشان می‌دهد. گام اول مسیر بالا فاش می‌کند که برگ مجاور 6,600,000,000 واحد دارد، و هر گام بالاتر مجموع یک زیردرخت را فاش می‌کند. این در یک درخت مجموعی ساده ذاتی است. بر زدن برگ‌ها در هر اسنپ‌شات آنچه مشتری در طول زمان می‌تواند بفهمد را محدود می‌کند، و پنهان کردن کامل مجموع‌ها به تعهدها به جای اعداد ساده نیاز دارد، که این نمونه انجام نمی‌دهد.

8. استقرار

$ rand fee deploy 994 --public-words 3
0.1007 RAND
$ rand program deploy image.bin --public public.txt
program id: fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0 (994 words, hc 1a7959556992bd05e8c47fbf8b5ec0935efede2131d866f963a49eb4d35245fb, public input 3 words, digest 70d5ae8935d646f7a0dd426c30aaf68e9bc382534d8a6ced90e363e129403608)
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 6.8s: tier 10, 1368908 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 116.7s: tier 14, 1500710 bytes
submitted deploy 39e8f35e0bdc7bc105ce942dc492b52f7a5efbb682ab6ebecc17cb310a161ada
  0 RAND out, 59.8545 RAND change, fee 0.1007 RAND, anchored at height 97831, proved in 116.7s (bundle) + 6.8s (auth)

شناسهٔ برنامه، رقم ذخیره و برچسب اسنپ‌شات را با کد مقید می‌کند. یک اسنپ‌شات جدید یک استقرار جدید است، با هزینه‌ای حدود یک‌دهم RAND، و شناسهٔ آن بیانیهٔ عمومی ادعای جدید است.

9. فراخوانی

$ rand call fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0 \
    $(sed 's/[0-9][0-9]*/--input &/g' witness.txt)

proving the call locally (73 inputs stay private, over the program's 3-word public input)…
gas: 12489 (declaring 16384, tier 14)
fee 0.007487437 RAND (incl. two price steps of headroom)
proved in 122.9s: tier 14, 1911152 bytes, outputs [1, 12, 1186432356, 3591337405, 3377802634, 3519326943, 1091785733, 0]
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 6.8s: tier 10, 1375371 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 111.9s: tier 14, 1500198 bytes
submitted call 5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17
  0 RAND out, 59.709221126 RAND change, fee 0.007487437 RAND, anchored at height 98336, proved in 111.9s (bundle) + 6.8s (auth)
{
  "h_in": "b151f38fbbefd08c9f36e65da89f016ba7fc0ccdb52bddda6544e3d86372d331",
  "h_pub": "70d5ae8935d646f7a0dd426c30aaf68e9bc382534d8a6ced90e363e129403608",
  "height": 98574,
  "index": 0,
  "outputs": [
    1,
    12,
    1186432356,
    3591337405,
    3377802634,
    3519326943,
    1091785733,
    0
  ],
  "program": "fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0",
  "tier": 14,
  "tx": "5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17"
}
input transcript published; open it with `rand open-call 5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17`

وضعیت 1، دوازده حساب، و ریشهٔ 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 به صورت هگز. هیچ چیز در تراکنش مانده‌ای یا مجموع را اعلام نمی‌کند.

این یک فراخوانی در سطح ۱۴ است، بنابراین اثبات فراخوانی بخش کند کار است: ۱۲۳ ثانیه، سپس ۷ ثانیه برای تأیید خرج‌کردن و ۱۱۲ ثانیه برای بسته، در مجموع پنج دقیقه، با اوج مصرف ۶٫۶ گیگابایت. اندازهٔ اثبات ۱٬۹۱۱٬۱۵۲ بایت است. جدول SHA-256 حدود ۰٫۴ مگابایت از این مقدار را به خود اختصاص می‌دهد.

10. خودتان بررسی کنید

1. ادعا. rand_getProgramPublic روی شناسهٔ برنامه، رقم ذخایر و برچسب را برمی‌گرداند. اینکه متولی واقعاً این ذخایر را در اختیار دارد یا نه، خارج از این اثبات است: این را موجودی روی زنجیره، نامهٔ حسابرس، یا برای دارایی پل‌شده خود rand_getTokenSupply زنجیره نشان می‌دهد.
2. کد. my-guests/solvency را با همان کامیت circuits بازسازی کنید و hc را با code_hash برنامه مقایسه کنید.
3. رسید. وضعیت 1، شکاف ۷ برابر با 3735928559 نباشد، و program برابر با شناسه باشد. خروجی‌های ۲ تا ۶ همان ریشه‌ای هستند که هر مشتری با آن مطابقت می‌دهد.
4. برگ خودتان، مانند بخش ۷.

هر کسی می‌تواند فراخوانی را با حساب‌های نمایشی تکرار کند، یا موجودی یک حساب را تغییر دهد و جابه‌جایی ریشه را ببیند.

آنچه اثبات به شما نمی‌دهد

• خود ذخایر. اثبات دربارهٔ بدهی‌ها در برابر یک عدد است. آن عدد به شواهد جداگانه نیاز دارد.
• کامل بودن بدون مشتریان. حسابی که متولی کنار گذاشته باشد فقط توسط مشتریِ صاحب آن پیدا می‌شود. هرچه مشتریان بیشتری بررسی کنند، جای کمتری برای پنهان‌کاری می‌ماند.
• یک لحظهٔ زمانی که با لحظهٔ ذخایر هم‌خوان باشد. متولی می‌تواند برای ساعتِ تصویر لحظه‌ای وجوه قرض بگیرد. تصاویر لحظه‌ای مکرر در زمان‌های اعلام‌نشده این را محدود می‌کند.
• همسایه‌های پنهان. مسیر یک مشتری مجموع گره‌های هم‌سطح را نشان می‌دهد (بخش ۷).
• بیش از ۳۲ حساب در یک فراخوانی. بودجه را ببینید.