Bukti kewajiban

Seorang kustodian berutang saldo kepada setiap nasabah. Program ini membuktikan bahwa jumlah seluruh saldo tidak melebihi angka cadangan yang telah dipublikasikan kustodian, tanpa mempublikasikan satu pun saldo maupun totalnya. Setiap nasabah dapat memeriksa, dengan beberapa baris Python dan tanpa perangkat khusus, bahwa saldonya sendiri telah dihitung.

Example programs memuat penyiapan yang dipakai bersama oleh keempat halaman contoh.

1. Apa yang dibuktikan

Kustodian membangun sebuah Merkle sum tree. Sebuah daun adalah satu akun: hash dari id nasabah dan saldonya, dengan saldo di sampingnya. Sebuah simpul adalah hash dari kedua anaknya beserta jumlah keduanya, dengan hasil penjumlahan kedua jumlah itu di sampingnya. Dengan demikian, akar membawa total dari seluruh saldo di bawahnya.

Pohon dibangun di dalam program, dari daftar akun yang bersifat privat. Pemanggilan ini membuktikan bahwa:

1. akar yang dipublikasikan dalam receipt adalah akar dari sebuah sum tree atas akun-akun yang diberikan kustodian;
2. setiap jumlah di dalamnya adalah jumlah yang benar dari dua jumlah di bawahnya, tanpa overflow;
3. total pada akar paling banyak sama dengan angka cadangan yang ditetapkan saat deploy.

Poin 2 adalah hal yang tidak dapat diberikan oleh sum tree yang dipublikasikan tanpa bukti. Serangan yang dikenal pada sum tree polos adalah kustodian yang menuliskan jumlah sebuah induk lebih kecil daripada jumlah anak-anaknya, yang tidak dapat dideteksi nasabah mana pun dari satu jalur saja. Di sini jumlah dihitung oleh program, dan bukti untuk aritmetika lain apa pun tidak ada.

Yang tidak dicakup bukti adalah kelengkapan: kustodian yang memilih akun mana saja yang dimasukkan. Celah itu ditutup oleh para nasabah. Masing-masing memeriksa bahwa sebuah daun dengan id dan saldo mereka berada di bawah akar yang dipublikasikan (bagian 7). Akun yang dilewatkan akan ditemukan oleh pemiliknya.

2. Antarmuka

Angka cadangan berada di segmen publik dan tidak di output karena dua alasan. Tidak ada ruang: status, jumlah, dan akar 160-bit memenuhi slot. Dan angka itu menyatakan klaim sebelum buktinya ada: men-deploy program mempublikasikan “cadangan sebesar R, snapshot S”, lalu pemanggilan akan membuktikan bahwa saldo muat di bawah R atau mengembalikan status 2.

Hash-nya, secara persis:

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

Pohon selalu memiliki 32 daun. Akun mengisinya dari kiri dan daun kosong mengisi sisanya. Awalan 0 dan 1 mencegah sebuah daun terbaca sebagai simpul.

Urutan byte. SHA-256 bersifat big-endian sepenuhnya, dan syscall SHA256 menerima blok 64 byte-nya sebagai enam belas word big-endian. Karena itu program ini membaca id sebagai empat word big-endian dan mempublikasikan akar sebagai word big-endian: output 2 yang dicetak dalam heksadesimal adalah delapan digit heksadesimal pertama dari akar. Ini adalah konvensi yang berlawanan dengan program Keccak, karena kedua hash itu didefinisikan pada urutan byte yang berlawanan.

3. Guest

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

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

Padding ditulis dengan tangan. guest_sdk::sha256 menerima string byte apa pun dan menyalinnya satu byte demi satu byte. Setiap pesan di sini terdiri dari word utuh dengan panjang yang diketahui, sehingga program mengisi blok 16 word secara langsung: word pesan, lalu 0x80000000, nol, dan panjang dalam bit pada word terakhir. Sebuah daun adalah satu kompresi. 84 byte sebuah simpul meluber ke blok kedua, sehingga sebuah simpul adalah dua kompresi.

Saldo bertipe u64 dan penjumlahan diperiksa. Saldo tidak dapat negatif karena tipe tersebut tidak memiliki nilai negatif, yang menghilangkan cara klasik lain untuk memperkecil total. checked_add mengubah overflow menjadi status 4 alih-alih jumlah yang berputar kembali.

Hasil insolven tetap sebuah hasil. Status 2 adalah halt biasa dengan akar yang dipublikasikan. Kustodian tidak dapat memperoleh receipt berstatus 1 untuk saldo yang melebihi angka cadangan, dan receipt berstatus 2 adalah bukti persis tentang hal itu.

4. Sisi host

solvency.py hanya menggunakan pustaka standar 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

Kedua hash di dalamnya adalah seluruh spesifikasi yang dibutuhkan seorang nasabah:

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 ini memiliki dua belas akun dalam demo-accounts.csv, satu id,balance per baris, dengan saldo dalam satuan 10⁻⁸ (presisi yang digunakan token bridged seperti zUSD). Totalnya 100.215,185678. Kustodian mengklaim cadangan sebesar 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 adalah 10.100.000.000.000. Baris liabilities adalah pandangan kustodian sendiri. Baris itu tidak pernah dipublikasikan.

Id harus unik dan tidak dapat ditebak. Jika dua nasabah dengan saldo yang sama diberi daun yang sama, kustodian dapat menghitung satu kewajiban untuk keduanya. Id yang hanya dapat dikenali sebagai milik nasabahnya sendiri mencegah hal itu, dan id yang tidak dapat ditebak menghentikan nasabah yang melihat hash saudaranya agar tidak mencoba menebak saldo tetangganya. Demo ini menggunakan 16 byte pertama dari sebuah hash. Deployment sungguhan akan menurunkan id dari akun nasabah dan sebuah nonce per snapshot, lalu menunjukkannya kepada nasabah.

5. Build dan jalankan

$ 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, dua belas akun, dan lima word akar yang dicetak skrip. Witness terdiri dari 73 word: jumlah akun dan enam per akun.

Dengan angka cadangan diturunkan menjadi 100 satuan (--public 100 0 1), akun-akun yang sama menghasilkan out[0] = 2. Jumlah 33 menghasilkan out[0] = 3. Dua akun yang saldonya berjumlah melebihi 2⁶⁴ menghasilkan out[0] = 4.

6. Anggaran

Jumlah kompresi adalah n daun, satu daun kosong (dihitung sekali lalu disalin), dan dua untuk masing-masing dari 31 simpul. Satu pemanggilan boleh menggunakan paling banyak 128 kompresi, dan tier 14 adalah tier tertinggi yang boleh digunakan sebuah pemanggilan, sehingga 32 akun mendekati batas yang dapat dibuktikan satu pemanggilan dalam rancangan ini. Pohon 64 daun membutuhkan 190 kompresi dan tidak muat.

Itu adalah ukuran demonstrasi. Melampauinya berarti memecah pohon ke dalam beberapa pemanggilan dan membawa komitmen atas akar dan jumlah setiap subpohon ke pemanggilan akhir, pola yang dijelaskan Write a program untuk pekerjaan apa pun yang melebihi anggaran. Contoh ini tidak melakukannya.

Sejak chain 18, satu kompresi berbiaya 64 gas, dibandingkan 1 untuk siklus biasa. Wallet mencetak gas yang tepat dari sebuah eksekusi dan batas yang dideklarasikannya:

gas: 12489 (declaring 16384, tier 14)

Setiap baris berbiaya 1 gas dan satu kompresi berbiaya 63 tambahan: 7.764 baris ditambah 75 × 63 adalah 12.489. Lebih dari sepertiga gas adalah untuk hashing. (Wallet menghitung dua baris lebih banyak daripada rand-guest run, karena pengikatan transaksi yang ditambahkan chain 18 pada segmen publik sebuah pemanggilan.)

7. Pemeriksaan oleh nasabah

Kustodian memberikan jalur masing-masing kepada setiap nasabah: hash saudara dan jumlah saudara pada tiap dari lima level.

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

Nasabah menghitung ulang akar dari id dan saldonya sendiri, lalu membandingkan 20 byte pertamanya dengan output 2 sampai 6 pada receipt:

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

Jalur untuk saldo yang lebih tinggi satu satuan daripada yang ada di pohon tidak sampai ke akar:

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

Seluruh pemeriksaan hanyalah fungsi leaf dan parent di atas yang diterapkan lima kali. Nasabah yang tidak ingin menjalankan skrip kustodian dapat menuliskannya sendiri.

Sebuah jalur menunjukkan kepada nasabah jumlah milik saudara-saudaranya. Langkah pertama jalur di atas mengungkap bahwa daun tetangga memegang 6.600.000.000 satuan, dan setiap langkah yang lebih tinggi mengungkap total sebuah subpohon. Itu melekat pada sum tree polos. Mengacak daun pada setiap snapshot membatasi apa yang dapat diketahui nasabah dari waktu ke waktu, dan menyembunyikan jumlah sepenuhnya membutuhkan komitmen sebagai pengganti angka polos, yang tidak dilakukan contoh ini.

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)

Id program mengikat angka cadangan dan label snapshot bersama kode. Snapshot baru adalah deploy baru, dengan biaya sekitar sepersepuluh RAND, dan id-nya adalah pernyataan publik atas klaim yang baru.

9. Panggil

$ 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, dua belas akun, dan akar 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 dalam heksadesimal. Tidak ada dalam transaksi yang menyatakan saldo maupun total.

Ini adalah panggilan tier-14, sehingga bukti panggilan menjadi bagian yang paling lambat: 123 s, lalu 7 s untuk otorisasi pembelanjaan dan 112 s untuk bundel, total lima menit, dengan puncak memori 6,6 GB. Ukuran bukti adalah 1.911.152 byte. Tabel SHA-256 menyumbang sekitar 0,4 MB dari ukuran tersebut.

10. Periksa sendiri

1. Klaimnya. rand_getProgramPublic pada id program mengembalikan angka cadangan dan labelnya. Apakah kustodian benar-benar memegang cadangan tersebut berada di luar bukti ini: hal itu ditunjukkan oleh saldo on-chain, surat dari auditor, atau, untuk aset yang dijembatani, oleh rand_getTokenSupply milik chain itu sendiri.
2. Kodenya. Bangun ulang my-guests/solvency pada commit circuits yang sama, lalu bandingkan hc dengan code_hash milik program.
3. Tanda terima. Status 1, slot 7 bukan 3735928559, dan program sama dengan id. Keluaran 2 hingga 6 adalah root yang diperiksa oleh setiap nasabah.
4. Daun Anda sendiri, seperti pada bagian 7.

Siapa pun dapat mengulangi panggilan tersebut dengan akun demo, atau mengubah satu saldo dan melihat root bergeser.

Apa yang tidak diberikan oleh bukti ini

• Cadangan itu sendiri. Bukti ini adalah bukti kewajiban terhadap sebuah angka. Angka tersebut memerlukan buktinya sendiri.
• Kelengkapan tanpa para nasabah. Akun yang dihilangkan oleh kustodian hanya dapat ditemukan oleh nasabah pemilik akun itu. Semakin banyak nasabah yang memeriksa, semakin sempit ruang geraknya.
• Waktu yang selaras dengan waktu cadangan. Kustodian dapat meminjam dana selama satu jam saat snapshot diambil. Snapshot yang sering pada waktu yang tidak diumumkan mempersempit celah itu.
• Tetangga yang tersembunyi. Jalur seorang nasabah menampilkan jumlah simpul sejawat (bagian 7).
• Lebih dari 32 akun dalam satu panggilan. Lihat anggaran.