Uma prova de passivos

Um custodiante deve a cada cliente um saldo. Este programa prova que a soma dos saldos não excede um valor de reservas que o custodiante publicou, sem publicar nenhum saldo nem o total. Cada cliente pode verificar, com poucas linhas de Python e sem nenhuma ferramenta especial, que o seu próprio saldo foi contabilizado.

Programas de exemplo traz a configuração que as quatro páginas de exemplo compartilham.

1. O que ele prova

O custodiante constrói uma árvore de somas de Merkle. Uma folha é uma conta: um hash do id do cliente e do saldo, com o saldo ao lado. Um nó é um hash dos seus dois filhos e das somas deles, com as duas somas adicionadas ao lado. A raiz carrega, portanto, o total de todos os saldos que estão abaixo dela.

A árvore é construída dentro do programa, a partir da lista privada de contas. A chamada prova que:

1. a raiz publicada no recibo é a raiz de uma árvore de somas sobre as contas fornecidas pelo custodiante;
2. toda soma nela é a soma verdadeira dos dois valores abaixo dela, sem overflow;
3. o total na raiz é, no máximo, o valor de reservas fixado no deploy.

O ponto 2 é o que uma árvore de somas publicada sem prova não pode oferecer. O ataque conhecido contra uma árvore de somas simples é o de um custodiante que escreve a soma de um pai como um valor menor do que a soma dos seus filhos, o que nenhum cliente consegue detectar a partir de um único caminho. Aqui as somas são calculadas pelo programa, e não existe prova de nenhuma outra aritmética.

O que a prova não cobre é a completude: o custodiante escolhe quais contas entram. Essa lacuna é fechada pelos clientes. Cada um verifica que uma folha com o seu id e o seu saldo está sob a raiz publicada (seção 7). Uma conta deixada de fora é descoberta pelo seu titular.

2. A interface

O valor de reservas está no segmento público e não nas saídas, por dois motivos. Não há espaço: o status, a contagem e uma raiz de 160 bits ocupam os slots. E ele declara a afirmação antes de a prova existir: fazer o deploy do programa publica “reservas de R, instantâneo S”, e a chamada então ou prova que os saldos cabem em R ou devolve o status 2.

Os hashes, exatamente:

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

A árvore sempre tem 32 folhas. As contas a preenchem a partir da esquerda e folhas vazias preenchem o resto. Os 0 e 1 iniciais impedem que uma folha seja lida como um nó.

Ordem dos bytes. O SHA-256 é big-endian do começo ao fim, e o syscall SHA256 recebe o seu bloco de 64 bytes como dezesseis palavras big-endian. Por isso este programa lê um id como quatro palavras big-endian e publica a raiz como palavras big-endian: a saída 2 impressa em hexadecimal são os primeiros oito dígitos hexadecimais da raiz. Essa é a convenção oposta à de o programa Keccak, porque os dois hashes são definidos sobre ordens de bytes opostas.

3. O 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();
}

O preenchimento é escrito à mão. guest_sdk::sha256 aceita qualquer sequência de bytes e a copia byte a byte. Toda mensagem aqui é composta de palavras inteiras de comprimento conhecido, então o programa preenche diretamente o bloco de 16 palavras: as palavras da mensagem, depois 0x80000000, zeros e o comprimento em bits na última palavra. Uma folha é uma compressão. Os 84 bytes de um nó transbordam para um segundo bloco, então um nó são duas.

Os saldos são u64 e as somas são verificadas. Um saldo não pode ser negativo porque o tipo não tem valores negativos, o que elimina a outra forma clássica de reduzir um total. checked_add transforma um overflow no status 4 em vez de uma soma que dá a volta.

Um resultado insolvente continua sendo um resultado. O status 2 é uma parada comum, com a raiz publicada. Um custodiante não consegue obter um recibo de status 1 para saldos que excedem o valor de reservas, e um recibo de status 2 é a prova justamente disso.

4. O lado do host

solvency.py usa apenas a biblioteca padrão do 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

Os dois hashes que ele contém são toda a especificação de que um cliente precisa:

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]

A demonstração tem doze contas em demo-accounts.csv, um id,balance por linha, com saldos em unidades de 10⁻⁸ (a precisão que um token com bridge como o zUSD usa). Elas somam 100.215,185678. O custodiante declara reservas de 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. A linha liabilities é a visão do próprio custodiante. Ela nunca é publicada.

Os ids devem ser únicos e imprevisíveis. Se a dois clientes com o mesmo saldo fosse dada a mesma folha, o custodiante poderia contar um único passivo para ambos. Um id que só o seu cliente reconhece como seu impede isso, e um id que não pode ser adivinhado impede que um cliente que vê o hash de um vizinho teste palpites sobre o saldo do vizinho. A demonstração usa os primeiros 16 bytes de um hash. Uma implantação real derivaria o id a partir da conta do cliente e de um nonce por instantâneo, e o mostraria ao cliente.

5. Compilar e executar

$ 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, doze contas e as cinco palavras da raiz que o script imprimiu. A testemunha tem 73 palavras: a contagem e seis por conta.

Com o valor de reservas reduzido a 100 unidades (--public 100 0 1), as mesmas contas dão out[0] = 2. Uma contagem de 33 dá out[0] = 3. Duas contas cujos saldos somam mais de 2⁶⁴ dão out[0] = 4.

6. O orçamento

A contagem de compressões é n folhas, uma folha vazia (calculada uma vez e copiada) e duas para cada um dos 31 nós. Uma chamada pode usar no máximo 128 compressões, e o nível 14 é o mais alto que uma chamada pode usar, portanto 32 contas é próximo do que uma chamada consegue provar neste projeto. Uma árvore de 64 folhas precisa de 190 compressões e não cabe.

Esse é um tamanho de demonstração. Ir além significa dividir a árvore em várias chamadas e levar um compromisso com a raiz e a soma de cada subárvore para uma chamada final, o padrão que Escrever um programa descreve para qualquer trabalho acima do orçamento. Este exemplo não faz isso.

Desde a chain 18, uma compressão custa 64 de gas, contra 1 para um ciclo comum. A carteira imprime o gas exato de uma execução e o limite que ela declara:

gas: 12489 (declaring 16384, tier 14)

Cada linha custa 1 de gas e uma compressão custa 63 a mais: 7.764 linhas mais 75 × 63 dá 12.489. Mais de um terço do gas é hashing. (A carteira conta duas linhas a mais que rand-guest run, pelo vínculo da transação que a chain 18 acrescenta ao segmento público de uma chamada.)

7. A verificação de um cliente

O custodiante dá a cada cliente o seu caminho: o hash irmão e a soma irmã em cada um dos cinco níveis.

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

O cliente recalcula a raiz a partir do seu próprio id e saldo e compara os primeiros 20 bytes dela com as saídas 2 a 6 do recibo:

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

Um caminho para um saldo uma unidade maior do que o da árvore não chega à raiz:

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

A verificação inteira são as funções leaf e parent acima aplicadas cinco vezes. Um cliente que não queira executar o script do custodiante pode escrevê-la ele mesmo.

Um caminho mostra ao cliente as somas dos seus irmãos. O primeiro passo do caminho acima revela que a folha vizinha contém 6.600.000.000 unidades, e cada passo mais alto revela o total de uma subárvore. Isso é inerente a uma árvore de somas simples. Embaralhar as folhas a cada instantâneo limita o que um cliente pode aprender ao longo do tempo, e ocultar as somas por completo exige compromissos no lugar de números simples, o que este exemplo não faz.

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)

O id do programa vincula o valor de reservas e o rótulo do instantâneo ao código. Um novo instantâneo é um novo deploy, por cerca de um décimo de RAND, e o seu id é a declaração pública da nova afirmação.

9. Chamada

$ 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, doze contas e a raiz 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 em hexadecimal. Nada na transação declara um saldo ou o total.

Esta é uma chamada de nível 14, portanto a prova da chamada é a parte lenta: 123 s, depois 7 s para a autorização de gasto e 112 s para o pacote, cinco minutos ao todo, com um pico de 6,6 GB. A prova tem 1.911.152 bytes. A tabela SHA-256 responde por cerca de 0,4 MB desse total.

10. Verifique você mesmo

1. A afirmação. rand_getProgramPublic sobre o id do programa devolve o valor da reserva e o rótulo. Se a custodiante realmente detém essa reserva está fora desta prova: isso se demonstra por um saldo on-chain, por uma carta de auditor ou, no caso de um ativo com bridge, pelo próprio rand_getTokenSupply da cadeia.
2. O código. Recompile my-guests/solvency no mesmo commit dos circuitos e compare hc com o code_hash do programa.
3. O recibo. Status 1, slot 7 diferente de 3735928559, e program igual ao id. As saídas 2 a 6 são a raiz contra a qual cada cliente verifica.
4. Sua própria folha, como na seção 7.

Qualquer pessoa pode repetir a chamada com as contas de demonstração, ou alterar um saldo e ver a raiz mudar.

O que a prova não oferece

• As reservas em si. A prova é de passivos contra um número. O número precisa de evidência própria.
• Completude sem os clientes. Uma conta que a custodiante deixou de fora só é descoberta pelo cliente a quem ela pertence. Quanto mais clientes verificam, menor a margem.
• Um momento no tempo que coincida com o das reservas. Uma custodiante pode tomar fundos emprestados durante a hora do snapshot. Snapshots frequentes, em horários não anunciados, reduzem esse risco.
• Vizinhos ocultos. O caminho de um cliente mostra as somas dos nós irmãos (seção 7).
• Mais de 32 contas em uma única chamada. Veja o orçamento.