A proof of liabilities

A custodian owes each customer a balance. This program proves that the balances add up to no more than a reserve figure the custodian has published, without publishing a single balance or the total. Each customer can check, with a few lines of Python and no special tooling, that their own balance was counted.

Example programs has the setup all four example pages share.

1. What it proves

The custodian builds a Merkle sum tree. A leaf is one account: a hash of the customer’s id and balance, with the balance beside it. A node is a hash of its two children and their sums, with the two sums added beside it. The root therefore carries the total of every balance under it.

The tree is built inside the program, from the private list of accounts. The call proves:

1. the root published in the receipt is the root of a sum tree over the accounts the custodian supplied;
2. every sum in it is the true sum of the two below it, with no overflow;
3. the total at the root is at most the reserve figure fixed at deploy.

Point 2 is what a sum tree published without a proof cannot give. The known attack on a bare sum tree is a custodian who writes a parent’s sum as something smaller than its children’s, which no customer can detect from a single path. Here the sums are computed by the program, and a proof of any other arithmetic does not exist.

What the proof does not cover is completeness: the custodian chooses which accounts go in. That gap is closed by the customers. Each one checks that a leaf with their id and their balance is under the published root (section 7). An account left out is found by its owner.

2. The interface

The reserve figure is in the public segment and not in the outputs for two reasons. There is no room: the status, the count and a 160-bit root fill the slots. And it states the claim before the proof exists: deploying the program publishes “reserves of R, snapshot S”, and the call then either proves the balances fit under R or returns status 2.

The hashes, exactly:

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

The tree always has 32 leaves. Accounts fill it from the left and empty leaves fill the rest. The leading 0 and 1 keep a leaf from ever being read as a node.

Byte order. SHA-256 is big-endian throughout, and the SHA256 syscall takes its 64-byte block as sixteen big-endian words. So this program reads an id as four big-endian words and publishes the root as big-endian words: output 2 printed in hex is the first eight hex digits of the root. This is the opposite convention from the Keccak program, because the two hashes are defined on opposite byte orders.

3. The guest

my-guests/solvency/src/main.rs, complete:

#![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();
}

The padding is written by hand. guest_sdk::sha256 takes any byte string and copies it a byte at a time. Every message here is whole words of a known length, so the program fills the 16-word block directly: the message words, then 0x80000000, zeros, and the bit length in the last word. A leaf is one compression. A node’s 84 bytes spill into a second block, so a node is two.

Balances are u64 and sums are checked. A balance cannot be negative because the type has no negative values, which removes the other classic way to shrink a total. checked_add turns an overflow into status 4 instead of a wrapped sum.

An insolvent result is still a result. Status 2 is an ordinary halt with the root published. A custodian cannot get a status 1 receipt for balances that exceed the reserve figure, and a status 2 receipt is a proof of exactly that.

4. The host side

solvency.py uses only Python’s standard library:

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

The two hashes in it are the whole specification a customer needs:

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]

The demo has twelve accounts in demo-accounts.csv, one id,balance per line, with balances in units of 10⁻⁸ (the precision a bridged token such as zUSD uses). They total 100,215.185678. The custodian claims reserves of 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 is 10,100,000,000,000. The liabilities line is the custodian’s own view. It is never published.

Ids must be unique and unguessable. If two customers with the same balance were given the same leaf, the custodian could count one liability for both. An id that only its customer can recognise as theirs prevents that, and an id that cannot be guessed stops a customer who sees a sibling’s hash from testing guesses of the neighbour’s balance. The demo uses the first 16 bytes of a hash. A real deployment would derive the id from the customer’s account and a per-snapshot nonce and show it to the customer.

5. Build and run

$ 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)

Status 1, twelve accounts, and the five root words the script printed. The witness is 73 words: the count and six per account.

With the reserve figure lowered to 100 units (--public 100 0 1) the same accounts give out[0] = 2. A count of 33 gives out[0] = 3. Two accounts whose balances add up past 2⁶⁴ give out[0] = 4.

6. The budget

The count of compressions is n leaves, one empty leaf (computed once and copied), and two for each of the 31 nodes. A call may use at most 128 compressions, and tier 14 is the highest tier a call may use, so 32 accounts is close to what one call can prove in this design. A 64-leaf tree needs 190 compressions and does not fit.

That is a demonstration size. Going past it means splitting the tree across several calls and carrying a commitment to each subtree’s root and sum into a final call, the pattern Write a program describes for any job over the budget. This example does not do that.

Since chain 18 a compression costs 64 gas, against 1 for an ordinary cycle. The wallet prints the exact gas of a run and the limit it declares:

gas: 12489 (declaring 16384, tier 14)

Every row costs 1 gas and a compression costs 63 more: 7,764 rows plus 75 × 63 is 12,489. More than a third of the gas is hashing. (The wallet counts two more rows than rand-guest run, for the transaction binding chain 18 adds to a call’s public segment.)

7. A customer’s check

The custodian gives each customer their path: the sibling hash and sibling sum at each of the five levels.

$ 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,

The customer recomputes the root from their own id and balance and compares its first 20 bytes with the receipt’s outputs 2 to 6:

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

A path for a balance one unit higher than the one in the tree does not reach the root:

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

The whole check is the leaf and parent functions above applied five times. A customer who does not want to run the custodian’s script can write it themselves.

A path shows the customer their siblings’ sums. The first step of the path above reveals that the neighbouring leaf holds 6,600,000,000 units, and each higher step reveals a subtree total. That is inherent in a plain sum tree. Shuffling the leaves each snapshot limits what a customer can learn over time, and hiding the sums entirely needs commitments in place of plain numbers, which this example does not do.

8. Deploy

$ 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)

The program id binds the reserve figure and the snapshot label with the code. A new snapshot is a new deploy, at about a tenth of a RAND, and its id is the public statement of the new claim.

9. Call

$ 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`

Status 1, twelve accounts, and the root 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 in hex. Nothing in the transaction states a balance or the total.

This is a tier-14 call, so the call proof is the slow part: 123 s, then 7 s for the spend authorisation and 112 s for the bundle, five minutes in all, with a peak of 6.6 GB. The proof is 1,911,152 bytes. The SHA-256 table accounts for about 0.4 MB of that.

10. Check it yourself

1. The claim. rand_getProgramPublic on the program id returns the reserve figure and the label. Whether the custodian really holds that reserve is outside this proof: it is shown by an on-chain balance, an auditor’s letter, or for a bridged asset by the chain’s own rand_getTokenSupply.
2. The code. Rebuild my-guests/solvency at the same circuits commit and compare hc with the program’s code_hash.
3. The receipt. Status 1, slot 7 not 3735928559, and program equal to the id. Outputs 2 to 6 are the root every customer checks against.
4. Your own leaf, as in section 7.

Anyone can repeat the call with the demo accounts, or change a balance and watch the root move.

What the proof does not give you

• The reserves themselves. The proof is of liabilities against a number. The number needs its own evidence.
• Completeness without the customers. An account the custodian left out is only found by the customer it belongs to. The more customers check, the less room there is.
• A moment in time that matches the reserves’. A custodian can borrow funds for the hour of the snapshot. Frequent snapshots at unannounced times narrow that.
• Hidden neighbours. A customer’s path shows sibling sums (section 7).
• More than 32 accounts in one call. See the budget.