Una proof of liabilities

Un custode deve a ogni cliente un saldo. Questo programma dimostra che la somma dei saldi non supera una cifra di riserva pubblicata dal custode, senza pubblicare né un singolo saldo né il totale. Ogni cliente può verificare, con poche righe di Python e senza strumenti speciali, che il proprio saldo sia stato conteggiato.

Programmi di esempio contiene la configurazione comune a tutte e quattro le pagine di esempio.

1. Che cosa dimostra

Il custode costruisce un albero di Merkle con somme. Una foglia è un conto: un hash dell’id del cliente e del saldo, con il saldo accanto. Un nodo è un hash dei suoi due figli e delle loro somme, con le due somme sommate accanto. La radice porta quindi il totale di tutti i saldi che si trovano sotto di essa.

L’albero è costruito dentro il programma, a partire dall’elenco privato dei conti. La chiamata dimostra che:

1. la radice pubblicata nella ricevuta è la radice di un albero di somme sui conti forniti dal custode;
2. ogni somma al suo interno è la vera somma delle due sottostanti, senza overflow;
3. il totale alla radice è al massimo pari alla cifra di riserva fissata al deploy.

Il punto 2 è ciò che un albero di somme pubblicato senza prova non può offrire. L’attacco noto contro un albero di somme privo di prova è quello di un custode che scrive la somma di un genitore come un valore inferiore a quella dei suoi figli, cosa che nessun cliente può rilevare da un singolo percorso. Qui le somme sono calcolate dal programma, e una prova di un’aritmetica diversa non esiste.

Ciò che la prova non copre è la completezza: il custode sceglie quali conti inserire. Questa lacuna è colmata dai clienti. Ciascuno verifica che una foglia con il proprio id e il proprio saldo si trovi sotto la radice pubblicata (sezione 7). Un conto escluso viene scoperto dal suo titolare.

2. L’interfaccia

La cifra di riserva sta nel segmento pubblico e non negli output per due ragioni. Non c’è spazio: lo stato, il conteggio e una radice a 160 bit riempiono gli slot. E dichiara l’affermazione prima che esista la prova: il deploy del programma pubblica «riserve pari a R, snapshot S», e la chiamata poi o dimostra che i saldi stanno sotto R oppure restituisce lo stato 2.

Gli hash, esattamente:

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

L’albero ha sempre 32 foglie. I conti lo riempiono da sinistra e le foglie vuote occupano il resto. Gli 0 e 1 iniziali impediscono che una foglia venga mai letta come un nodo.

Ordine dei byte. SHA-256 è big-endian ovunque, e la syscall SHA256 riceve il suo blocco di 64 byte come sedici parole big-endian. Per questo il programma legge un id come quattro parole big-endian e pubblica la radice come parole big-endian: l’output 2 stampato in esadecimale corrisponde alle prime otto cifre esadecimali della radice. È la convenzione opposta a quella del programma Keccak, perché i due hash sono definiti su ordini di byte opposti.

3. Il guest

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

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

Il padding è scritto a mano. guest_sdk::sha256 accetta qualsiasi sequenza di byte e la copia un byte alla volta. Qui ogni messaggio è fatto di parole intere di lunghezza nota, quindi il programma riempie direttamente il blocco di 16 parole: le parole del messaggio, poi 0x80000000, zeri, e la lunghezza in bit nell’ultima parola. Una foglia è una compressione. Gli 84 byte di un nodo sconfinano in un secondo blocco, quindi un nodo ne richiede due.

I saldi sono u64 e le somme sono verificate. Un saldo non può essere negativo perché il tipo non ha valori negativi, il che elimina l’altro classico modo di ridurre un totale. checked_add trasforma un overflow nello stato 4 invece di una somma con wrap-around.

Un risultato di insolvenza è comunque un risultato. Lo stato 2 è un normale halt con la radice pubblicata. Un custode non può ottenere una ricevuta con stato 1 per saldi che superano la cifra di riserva, e una ricevuta con stato 2 è la prova esatta di questo.

4. Il lato host

solvency.py usa solo la libreria standard di 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

I due hash al suo interno sono l’intera specifica di cui un cliente ha bisogno:

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]

La demo ha dodici conti in demo-accounts.csv, un id,balance per riga, con saldi in unità di 10⁻⁸ (la precisione usata da un token bridged come zUSD). Totalizzano 100.215,185678. Il custode dichiara riserve pari a 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 fa 10.100.000.000.000. La riga liabilities è la vista del custode stesso. Non viene mai pubblicata.

Gli id devono essere unici e non indovinabili. Se a due clienti con lo stesso saldo fosse assegnata la stessa foglia, il custode potrebbe contare una sola passività per entrambi. Un id che solo il suo cliente può riconoscere come proprio lo impedisce, e un id che non si può indovinare impedisce a un cliente che vede l’hash di un nodo adiacente di provare a indovinare il saldo del vicino. La demo usa i primi 16 byte di un hash. Un deploy reale ricaverebbe l’id dal conto del cliente e da un nonce per snapshot, e lo mostrerebbe al cliente.

5. Compilare ed eseguire

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

Stato 1, dodici conti, e le cinque parole della radice stampate dallo script. Il witness è di 73 parole: il conteggio e sei per conto.

Con la cifra di riserva abbassata a 100 unità (--public 100 0 1) gli stessi conti danno out[0] = 2. Un conteggio di 33 dà out[0] = 3. Due conti i cui saldi sommati superano 2⁶⁴ danno out[0] = 4.

6. Il budget

Il numero di compressioni è dato da n foglie, una foglia vuota (calcolata una volta e copiata) e due per ciascuno dei 31 nodi. Una chiamata può usare al massimo 128 compressioni, e il tier 14 è il tier più alto che una chiamata può usare, quindi 32 conti sono vicini a ciò che una singola chiamata può dimostrare in questo progetto. Un albero da 64 foglie richiede 190 compressioni e non ci sta.

È una dimensione dimostrativa. Andare oltre significa dividere l’albero su più chiamate e portare in una chiamata finale un impegno alla radice e alla somma di ciascun sottoalbero, il pattern che Scrivere un programma descrive per qualsiasi lavoro oltre il budget. Questo esempio non lo fa.

Dalla chain 18 una compressione costa 64 gas, contro 1 per un normale ciclo. Il wallet stampa il gas esatto di un’esecuzione e il limite che dichiara:

gas: 12489 (declaring 16384, tier 14)

Ogni riga costa 1 gas e una compressione ne costa 63 in più: 7.764 righe più 75 × 63 fa 12.489. Più di un terzo del gas è hashing. (Il wallet conta due righe in più rispetto a rand-guest run, per il binding della transazione che la chain 18 aggiunge al segmento pubblico di una chiamata.)

7. La verifica di un cliente

Il custode consegna a ogni cliente il suo percorso: l’hash e la somma del nodo fratello a ciascuno dei cinque livelli.

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

Il cliente ricalcola la radice a partire dal proprio id e dal proprio saldo e ne confronta i primi 20 byte con gli output da 2 a 6 della ricevuta:

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

Un percorso per un saldo superiore di una unità a quello presente nell’albero non raggiunge la radice:

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

L’intera verifica consiste nelle funzioni leaf e parent viste sopra, applicate cinque volte. Un cliente che non vuole eseguire lo script del custode può scriverla da sé.

Un percorso mostra al cliente le somme dei suoi nodi fratelli. Il primo passo del percorso qui sopra rivela che la foglia vicina contiene 6.600.000.000 unità, e ogni passo successivo rivela il totale di un sottoalbero. È inevitabile in un semplice albero di somme. Rimescolare le foglie a ogni snapshot limita ciò che un cliente può apprendere nel tempo, mentre nascondere del tutto le somme richiede impegni al posto dei numeri in chiaro, cosa che questo esempio non fa.

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)

L’id del programma vincola insieme al codice la cifra di riserva e l’etichetta di snapshot. Un nuovo snapshot è un nuovo deploy, a circa un decimo di RAND, e il suo id è la dichiarazione pubblica della nuova affermazione.

9. Chiamata

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

Stato 1, dodici conti, e la radice 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 in esadecimale. Nulla nella transazione dichiara un saldo o il totale.

Si tratta di una chiamata di livello 14, quindi la prova della chiamata è la parte lenta: 123 s, poi 7 s per l’autorizzazione di spesa e 112 s per il bundle, cinque minuti in tutto, con un picco di 6,6 GB. La prova è di 1.911.152 byte. La tabella SHA-256 ne occupa circa 0,4 MB.

10. Verificare in autonomia

1. L’affermazione. rand_getProgramPublic sull’id del programma restituisce il valore delle riserve e l’etichetta. Che il custode detenga davvero quelle riserve esula da questa prova: lo dimostrano un saldo on-chain, la lettera di un revisore o, per un asset bridged, il rand_getTokenSupply della catena stessa.
2. Il codice. Ricompilare my-guests/solvency allo stesso commit dei circuiti e confrontare hc con il code_hash del programma.
3. La ricevuta. Stato 1, slot 7 diverso da 3735928559, e program uguale all’id. Gli output da 2 a 6 sono la radice rispetto alla quale ogni cliente effettua la verifica.
4. La propria foglia, come nella sezione 7.

Chiunque può ripetere la chiamata con gli account dimostrativi, oppure modificare un saldo e osservare come si sposta la radice.

Che cosa la prova non garantisce

• Le riserve in sé. La prova riguarda le passività rispetto a un numero. Il numero richiede una propria evidenza.
• La completezza senza i clienti. Un account che il custode ha omesso viene scoperto solo dal cliente a cui appartiene. Più clienti verificano, minore è lo spazio di manovra.
• Un momento nel tempo che coincida con quello delle riserve. Un custode può prendere in prestito fondi per l’ora dello snapshot. Snapshot frequenti, in momenti non annunciati, riducono questo rischio.
• I vicini nascosti. Il percorso di un cliente mostra le somme dei nodi adiacenti (sezione 7).
• Più di 32 account in una sola chiamata. Vedi il budget.