負債證明

一名託管機構須向每位客戶支付一筆餘額。本程式證明，所有餘額之和不超過託管機構已公布的儲備數字，而無須公布任何一筆餘額或總額。每位客戶只需數行 Python 代碼，無須任何特殊工具，即可核實自己的餘額已被計入。

Example programs 載有四個範例頁面共用的設置。

1. 它證明甚麼

託管機構建構一棵 Merkle 總和樹（Merkle sum tree）。葉節點代表一個賬戶：客戶 id 與餘額的哈希值，旁附該餘額。內部節點是其兩個子節點及其總和的哈希值，旁附兩個總和相加之數。因此，根節點帶有其下所有餘額的總和。

這棵樹是在程式內部，由私有的賬戶清單建構而成。該次調用證明：

1. 收據中公布的根，是以託管機構所提供賬戶建構的總和樹的根；
2. 樹中每個總和，均是其下兩個總和的真實之和，且沒有溢出；
3. 根處的總額不超過部署時固定的儲備數字。

第 2 點是未附證明而公布的總和樹無法提供的。針對單純總和樹的已知攻擊，是託管機構把父節點的總和寫成小於其子節點之和的數值，而客戶單憑一條路徑無從察覺。在此，各總和由程式計算，而任何其他算術結果均不存在對應的證明。

證明並不涵蓋完整性：哪些賬戶納入其中，由託管機構決定。這個缺口由客戶來彌補。每位客戶核實，帶有其 id 及餘額的葉節點確實位於已公布的根之下（第 7 節）。被遺漏的賬戶，會由其持有人發現。

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 全程為大端序，而 SHA256 系統調用以十六個大端序字作為其 64 字節區塊。因此本程式將 id 讀作四個大端序字，並將根以大端序字公布：輸出 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. 主機端

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 一行是託管機構自己的視角，從不公布。

id 必須唯一且不可猜測。 如果兩位餘額相同的客戶獲分配同一個葉節點，託管機構便可以只為兩人計入一筆負債。只有客戶本人才能認出屬於自己的 id，可防止此事；而無法猜測的 id，則可阻止客戶在看見相鄰節點的哈希後，試猜鄰近賬戶的餘額。演示使用某個哈希的前 16 字節。實際部署會由客戶的賬戶及每個快照專用的 nonce 推導出 id，並向客戶展示。

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，十二個賬戶，以及腳本所打印的五個根字。見證共 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 所述、適用於任何超出預算的工作的模式。本範例並無採用。

自鏈 18 起，一次壓縮耗用 64 gas，而一個普通週期為 1。錢包會打印一次運行的確切 gas 及其所聲明的上限：

gas: 12489 (declaring 16384, tier 14)

每一行耗用 1 gas，而一次壓縮另加 63：7,764 行加 75 × 63 即 12,489。超過三分之一的 gas 用於哈希。（錢包比 rand-guest run 多計兩行，這是鏈 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,

客戶根據自己的 id 及餘額重新計算根，並將其前 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)

程式 id 把儲備數字及快照標籤與代碼綁定。新的快照即是新的部署，費用約為十分之一個 RAND，而其 id 就是新主張的公開聲明。

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。交易中沒有任何內容陳述餘額或總額。

這是一個第 14 層級的調用,因此調用證明是最耗時的部分:123 秒,其後花 7 秒處理支出授權,112 秒處理捆綁包,合共五分鐘,峰值記憶體為 6.6 GB。證明大小為 1,911,152 位元組。其中 SHA-256 表約佔 0.4 MB。

10. 自行核實

1. 聲明。 以程式 id 調用 rand_getProgramPublic,會返回儲備數字及標籤。託管方是否確實持有該筆儲備,不在本證明的範圍內:這須由鏈上結餘、核數師函件證明;至於跨鏈橋接資產,則可由該鏈本身的 rand_getTokenSupply 證明。
2. 程式碼。 在相同的 circuits commit 上重新建構 my-guests/solvency,並將 hc 與該程式的 code_hash 比對。
3. 收據。 狀態為 1,槽位 7 不是 3735928559,且 program 等於該 id。輸出 2 至 6 是每位客戶用以核對的根。
4. 你自己的葉節點,見第 7 節。

任何人均可使用示範帳戶重複這次調用,或修改某個結餘,觀察根如何改變。

本證明不能給你的保證

• 儲備本身。 本證明針對的是負債與某個數字之間的關係。該數字須另有證據支持。
• 沒有客戶參與的完整性。 若託管方遺漏了某個帳戶,只有該帳戶所屬的客戶才能發現。核對的客戶愈多,可供遺漏的空間愈小。
• 與儲備相吻合的時間點。 託管方可以在快照的那一小時內借入資金。在未經公佈的時間頻密進行快照,可收窄這種空間。
• 隱藏的相鄰節點。 客戶的路徑會顯示相鄰節點的總和(第 7 節)。
• 單次調用超過 32 個帳戶。 見預算。