Ein Nachweis der Verbindlichkeiten

Ein Verwahrer schuldet jedem Kunden ein Guthaben. Dieses Programm beweist, dass die Guthaben zusammen nicht mehr ergeben als eine vom Verwahrer veröffentlichte Reservezahl, ohne ein einzelnes Guthaben oder die Summe zu veröffentlichen. Jeder Kunde kann mit wenigen Zeilen Python und ohne Spezialwerkzeug prüfen, dass sein eigenes Guthaben mitgezählt wurde.

Beispielprogramme enthält das Setup, das alle vier Beispielseiten gemeinsam haben.

1. Was bewiesen wird

Der Verwahrer baut einen Merkle-Summenbaum. Ein Blatt ist ein Konto: ein Hash aus der ID des Kunden und seinem Guthaben, mit dem Guthaben daneben. Ein Knoten ist ein Hash aus seinen beiden Kindern und deren Summen, mit der Summe der beiden daneben. Die Wurzel trägt damit die Summe aller Guthaben unter ihr.

Der Baum wird innerhalb des Programms aus der privaten Kontenliste gebaut. Der Aufruf beweist:

1. Die in der Quittung veröffentlichte Wurzel ist die Wurzel eines Summenbaums über die vom Verwahrer gelieferten Konten;
2. jede Summe darin ist die tatsächliche Summe der beiden darunterliegenden, ohne Überlauf;
3. die Summe an der Wurzel ist höchstens so groß wie die beim Deploy festgelegte Reservezahl.

Punkt 2 kann ein Summenbaum, der ohne Beweis veröffentlicht wird, nicht leisten. Der bekannte Angriff auf einen bloßen Summenbaum besteht darin, dass ein Verwahrer die Summe eines Elternknotens kleiner angibt als die Summe seiner Kinder; kein Kunde kann das anhand eines einzelnen Pfads erkennen. Hier werden die Summen vom Programm berechnet, und ein Beweis für eine andere Arithmetik existiert nicht.

Nicht abgedeckt ist die Vollständigkeit: Der Verwahrer wählt, welche Konten aufgenommen werden. Diese Lücke schließen die Kunden. Jeder prüft, dass ein Blatt mit seiner ID und seinem Guthaben unter der veröffentlichten Wurzel liegt (Abschnitt 7). Ein ausgelassenes Konto findet sein Inhaber.

2. Die Schnittstelle

Die Reservezahl steht aus zwei Gründen im öffentlichen Segment und nicht in den Ausgaben. Es ist kein Platz: Status, Anzahl und eine 160-Bit-Wurzel füllen die Slots. Außerdem formuliert sie die Behauptung, bevor der Beweis existiert: Das Deployen des Programms veröffentlicht „Reserven von R, Snapshot S“, und der Aufruf beweist dann entweder, dass die Guthaben unter R passen, oder liefert Status 2.

Die Hashes, genau:

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

Der Baum hat immer 32 Blätter. Die Konten füllen ihn von links, leere Blätter füllen den Rest. Die führende 0 und 1 verhindern, dass ein Blatt je als Knoten gelesen wird.

Byte-Reihenfolge. SHA-256 ist durchgehend Big-Endian, und der SHA256-Syscall nimmt seinen 64-Byte-Block als sechzehn Big-Endian-Wörter. Deshalb liest dieses Programm eine ID als vier Big-Endian-Wörter und veröffentlicht die Wurzel als Big-Endian-Wörter: Ausgabe 2 in Hex entspricht den ersten acht Hexziffern der Wurzel. Das ist die umgekehrte Konvention wie beim Keccak-Programm, weil die beiden Hashes auf entgegengesetzten Byte-Reihenfolgen definiert sind.

3. Der Guest

my-guests/solvency/src/main.rs, vollständig:

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

Das Padding ist von Hand geschrieben. guest_sdk::sha256 nimmt eine beliebige Bytefolge und kopiert sie Byte für Byte. Jede Nachricht besteht hier aus ganzen Wörtern bekannter Länge, also füllt das Programm den 16-Wörter-Block direkt: die Nachrichtenwörter, dann 0x80000000, Nullen und die Bitlänge im letzten Wort. Ein Blatt ist eine Kompression. Die 84 Bytes eines Knotens laufen in einen zweiten Block über, ein Knoten sind also zwei.

Guthaben sind u64, und Summen werden geprüft. Ein Guthaben kann nicht negativ sein, weil der Typ keine negativen Werte hat; das beseitigt die andere klassische Möglichkeit, eine Summe zu verkleinern. checked_add macht aus einem Überlauf Status 4 statt einer umgelaufenen Summe.

Ein Ergebnis der Zahlungsunfähigkeit ist trotzdem ein Ergebnis. Status 2 ist ein gewöhnlicher Halt mit veröffentlichter Wurzel. Ein Verwahrer kann für Guthaben, die die Reservezahl übersteigen, keine Quittung mit Status 1 erhalten, und eine Quittung mit Status 2 ist genau der Beweis dafür.

4. Die Host-Seite

solvency.py verwendet nur die Standardbibliothek von 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

Die beiden Hashes darin sind die gesamte Spezifikation, die ein Kunde braucht:

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]

Die Demo hat zwölf Konten in demo-accounts.csv, je eine Zeile id,balance, mit Guthaben in Einheiten von 10⁻⁸ (die Genauigkeit, die ein gebridgter Token wie zUSD verwendet). Sie summieren sich auf 100.215,185678. Der Verwahrer behauptet Reserven von 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 ist 10.100.000.000.000. Die Zeile liabilities ist die eigene Sicht des Verwahrers. Sie wird nie veröffentlicht.

IDs müssen eindeutig und nicht erratbar sein. Würde man zwei Kunden mit demselben Guthaben dasselbe Blatt geben, könnte der Verwahrer für beide nur eine Verbindlichkeit zählen. Eine ID, die nur ihr Kunde als seine erkennen kann, verhindert das, und eine nicht erratbare ID hindert einen Kunden, der den Hash eines Nachbarn sieht, daran, Vermutungen über das Guthaben des Nachbarn zu testen. Die Demo verwendet die ersten 16 Bytes eines Hashs. Ein echtes Deployment würde die ID aus dem Konto des Kunden und einem Nonce je Snapshot ableiten und sie dem Kunden anzeigen.

5. Bauen und ausführen

$ 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, zwölf Konten und die fünf Wurzelwörter, die das Skript ausgegeben hat. Der Witness hat 73 Wörter: die Anzahl und sechs je Konto.

Mit auf 100 Einheiten gesenkter Reservezahl (--public 100 0 1) liefern dieselben Konten out[0] = 2. Eine Anzahl von 33 liefert out[0] = 3. Zwei Konten, deren Guthaben zusammen über 2⁶⁴ liegen, liefern out[0] = 4.

6. Das Budget

Die Zahl der Kompressionen ergibt sich aus n Blättern, einem leeren Blatt (einmal berechnet und kopiert) und zwei für jeden der 31 Knoten. Ein Aufruf darf höchstens 128 Kompressionen verwenden, und Tier 14 ist das höchste Tier, das ein Aufruf nutzen darf; 32 Konten sind also in diesem Entwurf nahe an dem, was ein Aufruf beweisen kann. Ein Baum mit 64 Blättern braucht 190 Kompressionen und passt nicht.

Das ist eine Demonstrationsgröße. Darüber hinaus muss man den Baum auf mehrere Aufrufe aufteilen und in einen abschließenden Aufruf eine Verpflichtung auf Wurzel und Summe jedes Teilbaums mitführen, das Muster, das Write a program für jede Aufgabe über dem Budget beschreibt. Dieses Beispiel tut das nicht.

Seit Chain 18 kostet eine Kompression 64 Gas, gegenüber 1 für einen gewöhnlichen Zyklus. Die Wallet gibt das genaue Gas eines Laufs und das Limit aus, das sie deklariert:

gas: 12489 (declaring 16384, tier 14)

Jede Zeile kostet 1 Gas, und eine Kompression kostet 63 mehr: 7.764 Zeilen plus 75 × 63 ergibt 12.489. Mehr als ein Drittel des Gas entfällt auf das Hashing. (Die Wallet zählt zwei Zeilen mehr als rand-guest run, wegen der Transaktionsbindung, die Chain 18 dem öffentlichen Segment eines Aufrufs hinzufügt.)

7. Die Prüfung durch einen Kunden

Der Verwahrer gibt jedem Kunden seinen Pfad: den Geschwister-Hash und die Geschwistersumme auf jeder der fünf Ebenen.

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

Der Kunde berechnet die Wurzel aus seiner eigenen ID und seinem Guthaben neu und vergleicht deren erste 20 Bytes mit den Ausgaben 2 bis 6 der Quittung:

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

Ein Pfad für ein um eine Einheit höheres Guthaben als das im Baum erreicht die Wurzel nicht:

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

Die gesamte Prüfung besteht darin, die oben genannten Funktionen leaf und parent fünfmal anzuwenden. Ein Kunde, der das Skript des Verwahrers nicht ausführen möchte, kann sie selbst schreiben.

Ein Pfad zeigt dem Kunden die Summen seiner Geschwister. Der erste Schritt des obigen Pfads offenbart, dass das benachbarte Blatt 6.600.000.000 Einheiten hält, und jeder höhere Schritt offenbart eine Teilbaumsumme. Das ist bei einem einfachen Summenbaum unvermeidlich. Das Mischen der Blätter bei jedem Snapshot begrenzt, was ein Kunde im Lauf der Zeit lernen kann, und die Summen ganz zu verbergen erfordert Verpflichtungen anstelle von Klartextzahlen, was dieses Beispiel nicht tut.

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)

Die Programm-ID bindet die Reservezahl und die Snapshot-Bezeichnung zusammen mit dem Code. Ein neuer Snapshot ist ein neues Deploy, für etwa ein Zehntel RAND, und seine ID ist die öffentliche Erklärung der neuen Behauptung.

9. Aufruf

$ 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, zwölf Konten und die Wurzel 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 in Hex. Nichts in der Transaktion nennt ein Guthaben oder die Summe.

Dies ist ein Aufruf der Stufe 14, daher ist der Beweis des Aufrufs der langsame Teil: 123 s, danach 7 s für die Ausgabeautorisierung und 112 s für das Bundle, insgesamt fünf Minuten, bei einem Spitzenverbrauch von 6,6 GB. Der Beweis umfasst 1.911.152 Bytes. Auf die SHA-256-Tabelle entfallen davon etwa 0,4 MB.

10. Selbst nachprüfen

1. Die Behauptung. rand_getProgramPublic liefert für die Programm-ID die Reservezahl und das Label. Ob der Verwahrer diese Reserve tatsächlich hält, liegt außerhalb dieses Beweises: Es wird durch einen On-Chain-Saldo, das Schreiben eines Prüfers oder, bei einem überbrückten Asset, durch das rand_getTokenSupply der Chain selbst belegt.
2. Der Code. Bauen Sie my-guests/solvency mit demselben Circuits-Commit neu und vergleichen Sie hc mit dem code_hash des Programms.
3. Die Quittung. Status 1, Slot 7 ungleich 3735928559, und program entspricht der ID. Die Ausgaben 2 bis 6 bilden die Wurzel, gegen die jeder Kunde prüft.
4. Ihr eigenes Blatt, wie in Abschnitt 7.

Jeder kann den Aufruf mit den Demo-Konten wiederholen oder einen Saldo ändern und beobachten, wie sich die Wurzel verschiebt.

Was der Beweis Ihnen nicht liefert

• Die Reserven selbst. Der Beweis betrifft Verbindlichkeiten gegenüber einer Zahl. Die Zahl braucht eigene Belege.
• Vollständigkeit ohne die Kunden. Ein Konto, das der Verwahrer ausgelassen hat, findet nur der Kunde, dem es gehört. Je mehr Kunden prüfen, desto geringer der Spielraum.
• Ein Zeitpunkt, der mit dem der Reserven übereinstimmt. Ein Verwahrer kann sich für die Stunde des Snapshots Mittel leihen. Häufige Snapshots zu unangekündigten Zeitpunkten verringern das.
• Verborgene Nachbarn. Der Pfad eines Kunden zeigt die Summen der Nachbarknoten (Abschnitt 7).
• Mehr als 32 Konten in einem Aufruf. Siehe das Budget.