Dowód zobowiązań

Depozytariusz jest winien każdemu klientowi saldo. Ten program dowodzi, że salda w sumie nie przekraczają opublikowanej przez depozytariusza kwoty rezerw, bez ujawniania ani jednego salda, ani sumy. Każdy klient może sprawdzić, za pomocą kilku linii w Pythonie i bez specjalnych narzędzi, że jego saldo zostało uwzględnione.

Programy przykładowe zawierają konfigurację wspólną dla wszystkich czterech stron z przykładami.

1. Co jest dowodzone

Depozytariusz buduje drzewo sum Merkle’a. Liść to jedno konto: skrót z identyfikatora klienta i salda, a obok niego samo saldo. Węzeł to skrót z dwóch jego potomków i ich sum, a obok niego suma obu sum. Korzeń zawiera więc łączną kwotę wszystkich sald pod nim.

Drzewo jest budowane wewnątrz programu, z prywatnej listy kont. Wywołanie dowodzi, że:

1. korzeń opublikowany w potwierdzeniu jest korzeniem drzewa sum nad kontami dostarczonymi przez depozytariusza;
2. każda suma w drzewie jest prawdziwą sumą dwóch sum poniżej, bez przepełnienia;
3. suma w korzeniu nie przekracza kwoty rezerw ustalonej przy wdrożeniu.

Punkt 2 to coś, czego drzewo sum opublikowane bez dowodu nie zapewnia. Znany atak na samo drzewo sum polega na tym, że depozytariusz zapisuje sumę rodzica jako wartość mniejszą niż suma jego potomków, czego żaden klient nie wykryje na podstawie pojedynczej ścieżki. Tutaj sumy oblicza program, a dowód innej arytmetyki nie istnieje.

Dowód nie obejmuje kompletności: to depozytariusz wybiera, które konta trafią do drzewa. Tę lukę zamykają klienci. Każdy z nich sprawdza, że liść z jego identyfikatorem i saldem znajduje się pod opublikowanym korzeniem (sekcja 7). Pominięte konto wykryje jego właściciel.

2. Interfejs

Kwota rezerw znajduje się w segmencie publicznym, a nie w wyjściach, z dwóch powodów. Brakuje na nią miejsca: status, liczba kont i 160-bitowy korzeń wypełniają sloty. Poza tym ustala ona twierdzenie, zanim powstanie dowód: wdrożenie programu publikuje „rezerwy w wysokości R, migawka S”, a wywołanie albo dowodzi, że salda mieszczą się poniżej R, albo zwraca status 2.

Skróty, dokładnie:

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

Drzewo ma zawsze 32 liście. Konta wypełniają je od lewej, a puste liście wypełniają resztę. Wiodące 0 i 1 zapobiegają odczytaniu liścia jako węzła.

Kolejność bajtów. SHA-256 jest wszędzie big-endian, a syscall SHA256 przyjmuje 64-bajtowy blok jako szesnaście słów big-endian. Dlatego ten program odczytuje identyfikator jako cztery słowa big-endian i publikuje korzeń jako słowa big-endian: wyjście 2 wypisane szesnastkowo to pierwszych osiem cyfr szesnastkowych korzenia. To konwencja odwrotna niż w programie Keccak, ponieważ te dwa skróty są zdefiniowane na przeciwnych kolejnościach bajtów.

3. Gość

my-guests/solvency/src/main.rs, w całości:

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

Dopełnienie jest zapisane ręcznie. guest_sdk::sha256 przyjmuje dowolny ciąg bajtów i kopiuje go bajt po bajcie. Każdy komunikat tutaj składa się z całych słów o znanej długości, więc program wypełnia 16-słowowy blok bezpośrednio: słowa komunikatu, potem 0x80000000, zera i długość w bitach w ostatnim słowie. Liść to jedna kompresja. 84 bajty węzła przelewają się na drugi blok, więc węzeł to dwie kompresje.

Salda są typu u64, a sumy są sprawdzane. Saldo nie może być ujemne, ponieważ ten typ nie ma wartości ujemnych, co eliminuje drugi klasyczny sposób pomniejszenia sumy. checked_add zamienia przepełnienie w status 4 zamiast zawiniętej sumy.

Wynik niwypłacalności jest nadal wynikiem. Status 2 to zwykłe zakończenie z opublikowanym korzeniem. Depozytariusz nie może uzyskać potwierdzenia ze statusem 1 dla sald przekraczających kwotę rezerw, a potwierdzenie ze statusem 2 jest dowodem dokładnie tego.

4. Strona hosta

solvency.py korzysta wyłącznie z biblioteki standardowej Pythona:

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

Dwa zawarte w nim skróty to cała specyfikacja, której potrzebuje klient:

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]

Demo ma dwanaście kont w demo-accounts.csv, po jednym id,balance w wierszu, z saldami w jednostkach 10⁻⁸ (precyzja używana przez token ppomostowy, taki jak zUSD). W sumie to 100 215,185678. Depozytariusz deklaruje rezerwy w wysokości 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 to 10 100 000 000 000. Wiersz liabilities to widok samego depozytariusza. Nigdy nie jest publikowany.

Identyfikatory muszą być unikalne i niemożliwe do odgadnięcia. Gdyby dwóm klientom o tym samym saldzie przypisano ten sam liść, depozytariusz mógłby policzyć jedno zobowiązanie za oba. Identyfikator, który tylko jego klient rozpozna jako własny, temu zapobiega, a identyfikator, którego nie da się odgadnąć, powstrzymuje klienta, który widzi skrót sąsiada, przed sprawdzaniem domysłów co do salda sąsiedniego konta. Demo używa pierwszych 16 bajtów skrótu. Rzeczywiste wdrożenie wyprowadzałoby identyfikator z konta klienta i nonce’a dla danej migawki i pokazywało go klientowi.

5. Budowanie i uruchomienie

$ 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, dwanaście kont i pięć słów korzenia wypisanych przez skrypt. Świadectwo ma 73 słowa: liczbę kont i sześć na konto.

Po obniżeniu kwoty rezerw do 100 jednostek (--public 100 0 1) te same konta dają out[0] = 2. Liczba kont równa 33 daje out[0] = 3. Dwa konta, których salda w sumie przekraczają 2⁶⁴, dają out[0] = 4.

6. Budżet

Liczba kompresji to n liści, jeden pusty liść (obliczany raz i kopiowany) oraz dwie dla każdego z 31 węzłów. Wywołanie może użyć najwyżej 128 kompresji, a poziom 14 jest najwyższym poziomem dostępnym dla wywołania, więc 32 konta to w tym projekcie niemal tyle, ile może udowodnić jedno wywołanie. Drzewo o 64 liściach wymaga 190 kompresji i się nie mieści.

To rozmiar demonstracyjny. Wyjście poza niego oznacza podział drzewa na kilka wywołań i przeniesienie zobowiązania do korzenia i sumy każdego poddrzewa do wywołania końcowego, według wzorca, który Napisz program opisuje dla każdego zadania przekraczającego budżet. Ten przykład tego nie robi.

Od chain 18 kompresja kosztuje 64 gas, wobec 1 dla zwykłego cyklu. Portfel wypisuje dokładny gas uruchomienia i zadeklarowany limit:

gas: 12489 (declaring 16384, tier 14)

Każdy wiersz kosztuje 1 gas, a kompresja dodatkowo 63: 7 764 wiersze plus 75 × 63 to 12 489. Ponad jedna trzecia gasu idzie na haszowanie. (Portfel liczy o dwa wiersze więcej niż rand-guest run, z powodu powiązania z transakcją, które chain 18 dodaje do segmentu publicznego wywołania.)

7. Weryfikacja przez klienta

Depozytariusz przekazuje każdemu klientowi jego ścieżkę: skrót i sumę sąsiada na każdym z pięciu poziomów.

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

Klient oblicza korzeń ponownie na podstawie własnego identyfikatora i salda i porównuje jego pierwsze 20 bajtów z wyjściami 2 do 6 potwierdzenia:

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

Ścieżka dla salda o jedną jednostkę wyższego niż w drzewie nie prowadzi do korzenia:

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

Całe sprawdzenie to funkcje leaf i parent z powyższego, zastosowane pięć razy. Klient, który nie chce uruchamiać skryptu depozytariusza, może napisać je samodzielnie.

Ścieżka pokazuje klientowi sumy jego sąsiadów. Pierwszy krok powyższej ścieżki ujawnia, że sąsiedni liść zawiera 6 600 000 000 jednostek, a każdy wyższy krok ujawnia sumę poddrzewa. Jest to nieodłączne od zwykłego drzewa sum. Tasowanie liści w każdej migawce ogranicza to, czego klient może się dowiedzieć w czasie, a całkowite ukrycie sum wymaga zobowiązań zamiast zwykłych liczb, czego ten przykład nie robi.

8. Wdrożenie

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

Identyfikator programu wiąże kwotę rezerw i etykietę migawki z kodem. Nowa migawka to nowe wdrożenie, za około jedną dziesiątą RAND, a jego identyfikator jest publicznym oświadczeniem nowego twierdzenia.

9. Wywołanie

$ 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, dwanaście kont i korzeń 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 w zapisie szesnastkowym. Nic w transakcji nie ujawnia salda ani sumy.

Jest to wywołanie na poziomie 14, więc najwolniejszy jest dowód wywołania: 123 s, następnie 7 s na autoryzację wydatku i 112 s na pakiet, łącznie pięć minut, przy szczycie 6,6 GB. Dowód ma 1 911 152 bajtów. Tablica SHA-256 odpowiada za około 0,4 MB z tego.

10. Sprawdź to sam

1. Twierdzenie. rand_getProgramPublic wywołane na identyfikatorze programu zwraca wartość rezerw i etykietę. To, czy powiernik rzeczywiście posiada te rezerwy, leży poza zakresem tego dowodu: wykazuje to saldo on-chain, opinia audytora albo, w przypadku aktywa pomostowanego, własne rand_getTokenSupply łańcucha.
2. Kod. Zbuduj ponownie my-guests/solvency z tego samego commita obwodów i porównaj hc z code_hash programu.
3. Pokwitowanie. Status 1, slot 7 różny od 3735928559 oraz program równy identyfikatorowi. Wyjścia od 2 do 6 tworzą korzeń, z którym porównuje się każdy klient.
4. Twój własny liść, jak w sekcji 7.

Każdy może powtórzyć wywołanie na kontach demonstracyjnych albo zmienić saldo i zobaczyć, jak zmienia się korzeń.

Czego dowód nie daje

• Samych rezerw. Dowód dotyczy zobowiązań wobec pewnej liczby. Ta liczba wymaga własnych dowodów.
• Kompletności bez klientów. Konto, które powiernik pominął, odnajdzie tylko klient, do którego ono należy. Im więcej klientów sprawdza, tym mniej jest miejsca na takie pominięcie.
• Chwili zgodnej z chwilą rezerw. Powiernik może pożyczyć środki na godzinę wykonania migawki. Częste migawki w niezapowiedzianych momentach ograniczają tę możliwość.
• Ukrytych sąsiadów. Ścieżka klienta pokazuje sumy sąsiednich węzłów (sekcja 7).
• Więcej niż 32 kont w jednym wywołaniu. Zob. budżet.