Una prueba de pasivos

Un custodio debe a cada cliente un saldo. Este programa demuestra que los saldos suman no más que una cifra de reservas que el custodio ha publicado, sin publicar ningún saldo ni el total. Cada cliente puede comprobar, con unas pocas líneas de Python y sin herramientas especiales, que su propio saldo fue contabilizado.

Programas de ejemplo contiene la configuración que comparten las cuatro páginas de ejemplo.

1. Qué demuestra

El custodio construye un árbol de sumas de Merkle. Una hoja es una cuenta: un hash del id del cliente y de su saldo, con el saldo al lado. Un nodo es un hash de sus dos hijos y de sus sumas, con las dos sumas añadidas al lado. La raíz lleva, por tanto, el total de todos los saldos que están bajo ella.

El árbol se construye dentro del programa, a partir de la lista privada de cuentas. La llamada demuestra que:

1. la raíz publicada en el recibo es la raíz de un árbol de sumas sobre las cuentas que el custodio suministró;
2. cada suma del árbol es la suma verdadera de las dos que tiene debajo, sin desbordamiento;
3. el total en la raíz es como máximo la cifra de reservas fijada en el despliegue.

El punto 2 es lo que un árbol de sumas publicado sin una prueba no puede ofrecer. El ataque conocido contra un árbol de sumas sin más es un custodio que escribe la suma de un padre como algo menor que la de sus hijos, lo que ningún cliente puede detectar a partir de un solo camino. Aquí las sumas las calcula el programa, y no existe una prueba de ninguna otra aritmética.

Lo que la prueba no cubre es la exhaustividad: el custodio elige qué cuentas entran. Esa brecha la cierran los clientes. Cada uno comprueba que una hoja con su id y su saldo está bajo la raíz publicada (sección 7). Una cuenta omitida la descubre su titular.

2. La interfaz

La cifra de reservas está en el segmento público y no en las salidas por dos razones. No hay espacio: el estado, la cuenta y una raíz de 160 bits llenan las ranuras. Y enuncia la afirmación antes de que exista la prueba: desplegar el programa publica «reservas de R, instantánea S», y la llamada luego demuestra que los saldos caben bajo R o devuelve el estado 2.

Los hashes, exactamente:

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

El árbol siempre tiene 32 hojas. Las cuentas lo llenan desde la izquierda y las hojas vacías llenan el resto. El 0 y el 1 iniciales impiden que una hoja se lea alguna vez como un nodo.

Orden de bytes. SHA-256 es big-endian en todo momento, y la llamada al sistema SHA256 toma su bloque de 64 bytes como dieciséis palabras big-endian. Por eso este programa lee un id como cuatro palabras big-endian y publica la raíz como palabras big-endian: la salida 2 impresa en hexadecimal son los primeros ocho dígitos hexadecimales de la raíz. Es la convención opuesta a la de el programa Keccak, porque los dos hashes están definidos sobre órdenes de bytes opuestos.

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

El relleno se escribe a mano. guest_sdk::sha256 toma cualquier cadena de bytes y la copia byte a byte. Todos los mensajes aquí son palabras enteras de longitud conocida, así que el programa llena el bloque de 16 palabras directamente: las palabras del mensaje, luego 0x80000000, ceros y la longitud en bits en la última palabra. Una hoja es una compresión. Los 84 bytes de un nodo pasan a un segundo bloque, de modo que un nodo son dos.

Los saldos son u64 y las sumas están comprobadas. Un saldo no puede ser negativo porque el tipo no tiene valores negativos, lo que elimina la otra forma clásica de reducir un total. checked_add convierte un desbordamiento en el estado 4 en lugar de una suma que da la vuelta.

Un resultado insolvente sigue siendo un resultado. El estado 2 es una detención ordinaria con la raíz publicada. Un custodio no puede obtener un recibo de estado 1 para saldos que superan la cifra de reservas, y un recibo de estado 2 es una prueba de exactamente eso.

4. El lado del host

solvency.py usa solo la biblioteca estándar de 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

Los dos hashes que contiene son toda la especificación que un cliente necesita:

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 demostración tiene doce cuentas en demo-accounts.csv, un id,balance por línea, con saldos en unidades de 10⁻⁸ (la precisión que usa un token puenteado como zUSD). Suman 100,215.185678. El custodio 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 es 10,100,000,000,000. La línea liabilities es la visión propia del custodio. Nunca se publica.

Los ids deben ser únicos e inadivinables. Si a dos clientes con el mismo saldo se les diera la misma hoja, el custodio podría contar un solo pasivo para ambos. Un id que solo su cliente puede reconocer como suyo lo impide, y un id que no puede adivinarse impide que un cliente que ve el hash de un vecino pruebe conjeturas sobre el saldo del contiguo. La demostración usa los primeros 16 bytes de un hash. Un despliegue real derivaría el id de la cuenta del cliente y de un nonce por instantánea, y se lo mostraría al cliente.

5. Compilar y ejecutar

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

Estado 1, doce cuentas y las cinco palabras de la raíz que imprimió el script. El testigo es de 73 palabras: la cuenta y seis por cuenta.

Con la cifra de reservas reducida a 100 unidades (--public 100 0 1), las mismas cuentas dan out[0] = 2. Una cuenta de 33 da out[0] = 3. Dos cuentas cuyos saldos suman más de 2⁶⁴ dan out[0] = 4.

6. El presupuesto

La cuenta de compresiones es n hojas, una hoja vacía (calculada una vez y copiada) y dos por cada uno de los 31 nodos. Una llamada puede usar como máximo 128 compresiones, y el nivel 14 es el más alto que una llamada puede usar, así que 32 cuentas es cercano a lo que una llamada puede demostrar con este diseño. Un árbol de 64 hojas necesita 190 compresiones y no cabe.

Es un tamaño de demostración. Ir más allá significa dividir el árbol en varias llamadas y llevar un compromiso con la raíz y la suma de cada subárbol a una llamada final, el patrón que Escribir un programa describe para cualquier trabajo que exceda el presupuesto. Este ejemplo no lo hace.

Desde la chain 18, una compresión cuesta 64 de gas, frente a 1 de un ciclo ordinario. La wallet imprime el gas exacto de una ejecución y el límite que declara:

gas: 12489 (declaring 16384, tier 14)

Cada fila cuesta 1 de gas y una compresión cuesta 63 más: 7,764 filas más 75 × 63 son 12,489. Más de un tercio del gas se va en el hashing. (La wallet cuenta dos filas más que rand-guest run, por el vínculo de transacción que la chain 18 añade al segmento público de una llamada.)

7. La comprobación de un cliente

El custodio entrega a cada cliente su camino: el hash hermano y la suma hermana en cada uno de los cinco niveles.

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

El cliente recalcula la raíz a partir de su propio id y saldo y compara sus primeros 20 bytes con las salidas 2 a 6 del recibo:

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

Un camino para un saldo una unidad mayor que el del árbol no llega a la raíz:

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

Toda la comprobación son las funciones leaf y parent de arriba aplicadas cinco veces. Un cliente que no quiera ejecutar el script del custodio puede escribirla él mismo.

Un camino muestra al cliente las sumas de sus hermanos. El primer paso del camino anterior revela que la hoja vecina contiene 6,600,000,000 unidades, y cada paso superior revela el total de un subárbol. Eso es inherente a un árbol de sumas simple. Barajar las hojas en cada instantánea limita lo que un cliente puede aprender con el tiempo, y ocultar las sumas por completo requiere compromisos en lugar de números en claro, algo que este ejemplo no hace.

8. Desplegar

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

El id del programa vincula la cifra de reservas y la etiqueta de instantánea con el código. Una nueva instantánea es un nuevo despliegue, por alrededor de una décima de RAND, y su id es el enunciado público de la nueva afirmación.

9. Llamar

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

Estado 1, doce cuentas y la raíz 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 en hexadecimal. Nada en la transacción declara un saldo ni el total.

Se trata de una llamada de nivel 14, por lo que la prueba de la llamada es la parte lenta: 123 s, luego 7 s para la autorización de gasto y 112 s para el paquete, cinco minutos en total, con un pico de 6,6 GB. La prueba ocupa 1 911 152 bytes. La tabla de SHA-256 representa unos 0,4 MB de ese total.

10. Compruébelo usted mismo

1. La afirmación. rand_getProgramPublic sobre el id del programa devuelve la cifra de reservas y la etiqueta. Que el custodio mantenga realmente esa reserva queda fuera de esta prueba: se demuestra con un saldo on-chain, con la carta de un auditor o, en el caso de un activo puenteado, con el propio rand_getTokenSupply de la cadena.
2. El código. Reconstruya my-guests/solvency en el mismo commit de circuits y compare hc con el code_hash del programa.
3. El recibo. Estado 1, la ranura 7 distinta de 3735928559, y program igual al id. Las salidas 2 a 6 son la raíz contra la que comprueba cada cliente.
4. Su propia hoja, como en la sección 7.

Cualquiera puede repetir la llamada con las cuentas de demostración, o cambiar un saldo y ver cómo se mueve la raíz.

Lo que la prueba no le da

• Las reservas en sí. La prueba es de pasivos frente a una cifra. Esa cifra necesita su propia evidencia.
• Exhaustividad sin los clientes. Una cuenta que el custodio omitió solo la encuentra el cliente al que pertenece. Cuantos más clientes comprueban, menos margen queda.
• Un momento en el tiempo que coincida con el de las reservas. Un custodio puede tomar fondos prestados durante la hora de la instantánea. Las instantáneas frecuentes, en momentos no anunciados, reducen ese margen.
• Vecinos ocultos. La ruta de un cliente muestra las sumas de los nodos hermanos (sección 7).
• Más de 32 cuentas en una sola llamada. Véase el presupuesto.