Bukti liabiliti

Seorang kustodian berhutang baki kepada setiap pelanggan. Program ini membuktikan bahawa jumlah baki tidak melebihi angka rizab yang telah diterbitkan oleh kustodian, tanpa menerbitkan sebarang baki atau jumlah keseluruhan. Setiap pelanggan boleh menyemak, dengan beberapa baris Python dan tanpa perkakas khas, bahawa baki mereka sendiri telah dikira.

Program contoh mengandungi persediaan yang dikongsi oleh keempat-empat halaman contoh.

1. Apa yang dibuktikan

Kustodian membina pokok jumlah Merkle. Satu daun ialah satu akaun: cincangan bagi id dan baki pelanggan, dengan baki di sebelahnya. Satu nod ialah cincangan bagi dua anaknya beserta jumlah kedua-duanya, dengan hasil tambah kedua-dua jumlah itu di sebelahnya. Oleh itu, akar membawa jumlah semua baki di bawahnya.

Pokok ini dibina di dalam program, daripada senarai akaun persendirian. Panggilan tersebut membuktikan bahawa:

1. akar yang diterbitkan dalam resit ialah akar bagi pokok jumlah ke atas akaun yang dibekalkan oleh kustodian;
2. setiap jumlah di dalamnya ialah hasil tambah sebenar bagi dua jumlah di bawahnya, tanpa limpahan;
3. jumlah pada akar tidak melebihi angka rizab yang ditetapkan semasa penggunaan.

Perkara 2 ialah sesuatu yang tidak dapat diberikan oleh pokok jumlah yang diterbitkan tanpa bukti. Serangan yang diketahui terhadap pokok jumlah kosong ialah kustodian yang menulis jumlah induk sebagai nilai yang lebih kecil daripada jumlah anak-anaknya, dan tiada pelanggan dapat mengesannya daripada satu laluan sahaja. Di sini, jumlah dikira oleh program, dan bukti bagi sebarang aritmetik lain tidak wujud.

Apa yang tidak dilindungi oleh bukti ini ialah kelengkapan: kustodian memilih akaun yang dimasukkan. Jurang itu ditutup oleh pelanggan. Setiap seorang menyemak bahawa terdapat daun dengan id dan baki mereka di bawah akar yang diterbitkan (bahagian 7). Akaun yang ditinggalkan akan ditemui oleh pemiliknya.

2. Antara muka

Angka rizab berada dalam segmen awam dan bukan dalam output atas dua sebab. Pertama, tiada ruang: status, bilangan dan akar 160-bit memenuhi slot. Kedua, ia menyatakan tuntutan sebelum bukti wujud: penggunaan program menerbitkan “rizab sebanyak R, syot kilat S”, dan panggilan kemudian sama ada membuktikan baki muat di bawah R atau mengembalikan status 2.

Cincangan, dengan tepat:

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

Pokok sentiasa mempunyai 32 daun. Akaun mengisinya dari kiri dan daun kosong mengisi selebihnya. 0 dan 1 di hadapan menghalang daun daripada pernah dibaca sebagai nod.

Susunan bait. SHA-256 ialah big-endian sepenuhnya, dan syscall SHA256 mengambil blok 64 baitnya sebagai enam belas perkataan big-endian. Oleh itu, program ini membaca id sebagai empat perkataan big-endian dan menerbitkan akar sebagai perkataan big-endian: output 2 yang dicetak dalam hex ialah lapan digit hex pertama bagi akar. Ini ialah konvensyen yang bertentangan dengan program Keccak, kerana kedua-dua cincangan itu ditakrifkan pada susunan bait yang bertentangan.

3. Tetamu

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

Pelapik ditulis dengan tangan. guest_sdk::sha256 menerima sebarang rentetan bait dan menyalinnya satu bait pada satu masa. Setiap mesej di sini terdiri daripada perkataan penuh dengan panjang yang diketahui, jadi program mengisi blok 16 perkataan secara langsung: perkataan mesej, kemudian 0x80000000, sifar, dan panjang bit pada perkataan terakhir. Satu daun ialah satu pemampatan. 84 bait sebuah nod melimpah ke blok kedua, jadi satu nod ialah dua pemampatan.

Baki ialah u64 dan jumlah disemak. Baki tidak boleh negatif kerana jenis itu tidak mempunyai nilai negatif, dan ini menghapuskan satu lagi cara klasik untuk mengecilkan jumlah. checked_add menukarkan limpahan kepada status 4 dan bukannya jumlah yang berbalik semula.

Keputusan tidak solven tetap merupakan keputusan. Status 2 ialah penghentian biasa dengan akar diterbitkan. Kustodian tidak dapat memperoleh resit status 1 bagi baki yang melebihi angka rizab, dan resit status 2 ialah bukti tepat tentang perkara itu.

4. Bahagian hos

solvency.py hanya menggunakan pustaka standard 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-dua cincangan di dalamnya ialah keseluruhan spesifikasi yang diperlukan oleh pelanggan:

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 mempunyai dua belas akaun dalam demo-accounts.csv, satu id,balance setiap baris, dengan baki dalam unit 10⁻⁸ (ketepatan yang digunakan oleh token yang dijambatankan seperti zUSD). Jumlahnya ialah 100,215.185678. Kustodian menuntut rizab sebanyak 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 ialah 10,100,000,000,000. Baris liabilities ialah pandangan kustodian sendiri. Ia tidak pernah diterbitkan.

Id mestilah unik dan tidak boleh diteka. Jika dua pelanggan dengan baki yang sama diberikan daun yang sama, kustodian boleh mengira satu liabiliti untuk kedua-duanya. Id yang hanya boleh dikenali oleh pelanggannya sebagai milik mereka menghalang perkara itu, dan id yang tidak boleh diteka menghalang pelanggan yang melihat cincangan adik-beradiknya daripada menguji andaian baki jirannya. Demo ini menggunakan 16 bait pertama sesuatu cincangan. Penggunaan sebenar akan memperoleh id daripada akaun pelanggan dan nonce bagi setiap syot kilat, dan menunjukkannya kepada pelanggan.

5. Bina 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 akaun, dan lima perkataan akar yang dicetak oleh skrip. Saksi ialah 73 perkataan: bilangan dan enam bagi setiap akaun.

Dengan angka rizab diturunkan kepada 100 unit (--public 100 0 1), akaun yang sama memberikan out[0] = 2. Bilangan 33 memberikan out[0] = 3. Dua akaun yang bakinya berjumlah melebihi 2⁶⁴ memberikan out[0] = 4.

6. Bajet

Bilangan pemampatan ialah n daun, satu daun kosong (dikira sekali dan disalin), dan dua bagi setiap satu daripada 31 nod. Satu panggilan boleh menggunakan paling banyak 128 pemampatan, dan peringkat 14 ialah peringkat tertinggi yang boleh digunakan oleh panggilan, jadi 32 akaun hampir menjadi had yang boleh dibuktikan oleh satu panggilan dalam reka bentuk ini. Pokok 64 daun memerlukan 190 pemampatan dan tidak muat.

Itu ialah saiz demonstrasi. Melepasinya bermakna memecahkan pokok merentasi beberapa panggilan dan membawa komitmen kepada akar dan jumlah setiap subpokok ke dalam panggilan akhir, corak yang diterangkan oleh Tulis program bagi mana-mana tugas yang melebihi bajet. Contoh ini tidak melakukannya.

Sejak chain 18, satu pemampatan berharga 64 gas, berbanding 1 bagi kitaran biasa. Dompet mencetak gas tepat bagi sesuatu larian dan had yang diisytiharkannya:

gas: 12489 (declaring 16384, tier 14)

Setiap baris berharga 1 gas dan satu pemampatan menambah 63 lagi: 7,764 baris campur 75 × 63 ialah 12,489. Lebih sepertiga daripada gas digunakan untuk pencincangan. (Dompet mengira dua baris lebih banyak daripada rand-guest run, bagi pengikatan transaksi yang ditambah oleh chain 18 pada segmen awam sesuatu panggilan.)

7. Semakan pelanggan

Kustodian memberikan setiap pelanggan laluan mereka: cincangan adik-beradik dan jumlah adik-beradik pada setiap satu daripada lima aras.

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

Pelanggan mengira semula akar daripada id dan baki mereka sendiri dan membandingkan 20 bait pertamanya dengan output 2 hingga 6 resit:

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

Laluan bagi baki yang lebih tinggi satu unit daripada baki dalam pokok tidak sampai ke akar:

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

Keseluruhan semakan ialah fungsi leaf dan parent di atas yang digunakan lima kali. Pelanggan yang tidak mahu menjalankan skrip kustodian boleh menulisnya sendiri.

Laluan menunjukkan kepada pelanggan jumlah adik-beradik mereka. Langkah pertama laluan di atas mendedahkan bahawa daun bersebelahan memegang 6,600,000,000 unit, dan setiap langkah yang lebih tinggi mendedahkan jumlah subpokok. Itu wujud secara semula jadi dalam pokok jumlah biasa. Mengocok daun pada setiap syot kilat mengehadkan apa yang boleh dipelajari oleh pelanggan dari semasa ke semasa, dan menyembunyikan jumlah sepenuhnya memerlukan komitmen sebagai ganti nombor biasa, yang tidak dilakukan oleh contoh ini.

8. Gunakan

$ 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 rizab dan label syot kilat bersama kod. Syot kilat baharu ialah penggunaan baharu, pada kira-kira sepersepuluh RAND, dan idnya ialah pernyataan awam bagi tuntutan baharu itu.

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 akaun, dan akar 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 dalam hex. Tiada apa-apa dalam transaksi yang menyatakan sebarang baki atau jumlah keseluruhan.

Ini ialah panggilan tier-14, jadi bukti panggilan merupakan bahagian yang paling perlahan: 123 s, kemudian 7 s untuk kebenaran perbelanjaan dan 112 s untuk bundle, lima minit kesemuanya, dengan puncak 6.6 GB. Bukti itu berukuran 1,911,152 bait. Jadual SHA-256 menyumbang kira-kira 0.4 MB daripadanya.

10. Semak sendiri

1. Tuntutan. rand_getProgramPublic pada id program memulangkan angka rizab dan label. Sama ada pemegang amanah benar-benar memegang rizab itu berada di luar bukti ini: ia ditunjukkan oleh baki dalam rantaian, surat juruaudit, atau, bagi aset yang dijambatani, rand_getTokenSupply milik rantaian itu sendiri.
2. Kod. Bina semula my-guests/solvency pada commit circuits yang sama dan bandingkan hc dengan code_hash program.
3. Resit. Status 1, slot 7 bukan 3735928559, dan program sama dengan id. Output 2 hingga 6 ialah root yang disemak oleh setiap pelanggan.
4. Daun anda sendiri, seperti dalam bahagian 7.

Sesiapa sahaja boleh mengulangi panggilan itu dengan akaun demo, atau mengubah satu baki dan melihat root berubah.

Perkara yang tidak diberikan oleh bukti ini

• Rizab itu sendiri. Bukti ini ialah bukti liabiliti berbanding satu angka. Angka itu memerlukan buktinya sendiri.
• Kelengkapan tanpa pelanggan. Akaun yang ditinggalkan oleh pemegang amanah hanya akan ditemui oleh pelanggan yang memilikinya. Semakin ramai pelanggan menyemak, semakin kecil ruang yang ada.
• Detik masa yang sepadan dengan rizab. Pemegang amanah boleh meminjam dana untuk tempoh sejam semasa petikan keadaan (snapshot) diambil. Petikan keadaan yang kerap pada waktu yang tidak diumumkan mengurangkan kemungkinan ini.
• Jiran tersembunyi. Laluan seseorang pelanggan menunjukkan jumlah nod adik-beradik (bahagian 7).
• Lebih daripada 32 akaun dalam satu panggilan. Lihat bajet.