負債の証明

カストディアンは各顧客に対して残高の支払義務を負っています。このプログラムは、残高の合計がカストディアンの公表した準備金額を超えないことを、個々の残高も合計も公開せずに証明します。各顧客は、数行の Python と特別なツールなしで、自分の残高が計上されていることを確認できます。

Example programs には、4つのサンプルページに共通するセットアップがあります。

1. 何を証明するか

カストディアンは マークル和木 を構築します。リーフは1つのアカウントを表し、顧客の id と残高のハッシュに、残高を添えたものです。ノードは、2つの子とそれぞれの合計のハッシュに、2つの合計を足した値を添えたものです。したがってルートは、その下にあるすべての残高の合計を持ちます。

この木は、非公開のアカウント一覧から プログラムの内部で 構築されます。この呼び出しは次のことを証明します。

1. レシートで公開されたルートは、カストディアンが提供したアカウントに対する和木のルートである。
2. 木のすべての合計は、その下の2つの合計の真の和であり、オーバーフローしていない。
3. ルートの合計は、デプロイ時に固定された準備金額以下である。

2点目は、証明なしで公開された和木には与えられないものです。単純な和木に対する既知の攻撃は、カストディアンが親の合計を子の合計より小さい値として書くもので、1本のパスからは顧客がこれを検知できません。ここでは合計をプログラムが計算するため、それ以外の算術に対する証明は存在しません。

証明が対象としないのは 網羅性 です。どのアカウントを含めるかはカストディアンが選びます。この隙間を埋めるのは顧客です。各顧客は、自分の id と残高を持つリーフが公開ルートの下にあることを確認します(セクション7)。除外されたアカウントは、その所有者が見つけます。

2. インターフェース

準備金額が出力ではなくパブリックセグメントにあるのには、2つの理由があります。1つは余裕がないことです。ステータス、件数、160ビットのルートでスロットが埋まります。もう1つは、証明が存在する前に主張を述べることです。プログラムをデプロイすると「準備金 R、スナップショット S」が公開され、その後の呼び出しは、残高が R に収まることを証明するか、ステータス 2 を返すかのどちらかになります。

ハッシュ は正確には次のとおりです。

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

木は常に32個のリーフを持ちます。アカウントは左から順に埋まり、残りは空のリーフで埋められます。先頭の 0 と 1 により、リーフがノードとして読まれることはありません。

バイト順。 SHA-256 は全体を通してビッグエンディアンで、SHA256 システムコールは64バイトのブロックを16個のビッグエンディアンワードとして受け取ります。そのためこのプログラムは、id を4つのビッグエンディアンワードとして読み、ルートもビッグエンディアンのワードとして公開します。出力2を16進数で表示すると、ルートの先頭8桁の16進数になります。これは Keccak のプログラム とは逆の規約です。2つのハッシュが逆のバイト順で定義されているためです。

3. ゲスト

my-guests/solvency/src/main.rs の全体:

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

パディングは手書きです。 guest_sdk::sha256 は任意のバイト列を受け取り、1バイトずつコピーします。ここでのメッセージはすべて長さが既知の整数ワードなので、プログラムは16ワードのブロックを直接埋めます。メッセージのワード、0x80000000、ゼロ、そして最後のワードにビット長です。リーフは圧縮1回です。ノードの84バイトは2つ目のブロックにはみ出すため、ノードは圧縮2回です。

残高は u64、合計は検査付きです。 型に負の値がないため、残高が負になることはありません。これにより、合計を縮めるもう1つの古典的な方法も排除されます。checked_add は、オーバーフローを、折り返した合計ではなくステータス 4 に変えます。

支払不足という結果も、れっきとした結果です。 ステータス 2 は、ルートを公開した通常の停止です。カストディアンは、準備金額を超える残高に対してステータス 1 のレシートを得ることはできず、ステータス 2 のレシートはまさにそのことの証明です。

4. ホスト側

solvency.py は 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

その中の2つのハッシュが、顧客に必要な仕様のすべてです。

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-accounts.csv に12個のアカウントがあり、1行に id,balance が1つ、残高の単位は 10⁻⁸ です(zUSD のようなブリッジされたトークンが使う精度です)。合計は 100,215.185678 です。カストディアンは準備金 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 は 10,100,000,000,000 です。liabilities の行はカストディアン自身の見方であり、公開されることはありません。

id は一意で、推測できないものでなければなりません。 同じ残高の2人の顧客に同じリーフが与えられた場合、カストディアンは1つの負債を両方の分として数えられてしまいます。その顧客だけが自分のものと認識できる id なら、これを防げます。また、推測できない id であれば、隣のハッシュを見た顧客が隣の残高を当てずっぽうで試すことも防げます。デモではハッシュの先頭16バイトを使っています。実際のデプロイでは、顧客のアカウントとスナップショットごとのナンスから id を導出し、顧客に示すことになります。

5. ビルドと実行

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

ステータス 1、12アカウント、そしてスクリプトが出力した5つのルートワードです。ウィットネスは73ワードで、件数とアカウントごとの6ワードからなります。

準備金額を100単位(--public 100 0 1)に下げると、同じアカウントで out[0] = 2 になります。件数が33なら out[0] = 3 です。残高の合計が 2⁶⁴ を超える2つのアカウントでは out[0] = 4 になります。

6. バジェット

圧縮の回数は、n 個のリーフ、空のリーフ1個(一度だけ計算してコピー)、そして31個のノードのそれぞれ2回です。1回の呼び出しで使える圧縮は最大128回で、ティア14は呼び出しが使える最上位のティアです。したがって この設計では、32アカウントが1回の呼び出しで証明できる上限に近い数です。64リーフの木には190回の圧縮が必要で、収まりません。

これはデモンストレーション用の規模です。これを超えるには、木を複数の呼び出しに分割し、各部分木のルートと合計へのコミットメントを最終の呼び出しに引き継ぎます。これは、バジェットを超える任意の処理について Write a program が説明しているパターンです。このサンプルはそれを行いません。

チェーン18以降、圧縮1回のコストは 64 gas で、通常のサイクルは1です。ウォレットは、実行の正確な gas と宣言された上限を表示します。

gas: 12489 (declaring 16384, tier 14)

各行は 1 gas で、圧縮1回につきさらに63かかります。7,764行に 75 × 63 を加えると 12,489 です。gas の3分の1以上がハッシュ計算です。(ウォレットは rand-guest run より2行多く数えます。チェーン18が呼び出しのパブリックセグメントに加えるトランザクション束縛の分です。)

7. 顧客による確認

カストディアンは各顧客に、そのパスを渡します。5つの各レベルにおける兄弟ハッシュと兄弟の合計です。

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

顧客は、自分の id と残高からルートを再計算し、その先頭20バイトをレシートの出力2〜6と比較します。

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

木にある残高より1単位大きい残高のパスは、ルートに到達しません。

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

確認のすべては、上の leaf 関数と parent 関数を5回適用するだけです。カストディアンのスクリプトを実行したくない顧客は、自分で書くこともできます。

パスは、顧客に兄弟の合計を見せます。 上のパスの最初のステップから、隣のリーフが 6,600,000,000 単位を保有していることがわかり、上位の各ステップは部分木の合計を明らかにします。これは単純な和木に本質的に付随するものです。スナップショットごとにリーフをシャッフルすれば、顧客が時間をかけて知り得る情報を制限できます。合計を完全に隠すには、平文の数値の代わりにコミットメントが必要ですが、このサンプルはそれを行いません。

8. デプロイ

$ 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 は、準備金額とスナップショットのラベルをコードとともに束縛します。新しいスナップショットは新しいデプロイであり、費用は約 RAND の10分の1で、その id が新しい主張の公開表明となります。

9. 呼び出し

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

ステータス 1、12アカウント、そして16進数でのルート 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 です。トランザクションのどこにも、残高も合計も記されていません。

これはティア14の呼び出しであり、呼び出しの証明が最も時間のかかる部分です。123秒、続いて支出承認に7秒、バンドルに112秒かかり、合計で5分、ピークメモリは6.6 GBです。証明のサイズは1,911,152バイトで、そのうち SHA-256 テーブルが約0.4 MBを占めます。

10. 自分で確認する

1. 主張。 プログラム ID に対して rand_getProgramPublic を呼ぶと、準備金の額とラベルが返ります。カストディアンが実際にその準備金を保有しているかどうかは、この証明の対象外です。それはオンチェーン残高、監査人の書簡、あるいはブリッジされた資産であればチェーン自身の rand_getTokenSupply によって示されます。
2. コード。 同じ circuits コミットで my-guests/solvency を再ビルドし、hc をプログラムの code_hash と比較します。
3. レシート。 ステータスが 1 であること、スロット 7 が 3735928559 ではないこと、そして program が ID と一致していることを確認します。出力 2 から 6 は、すべての顧客が照合するルートです。
4. 自分自身のリーフ。 第7節と同じ手順で確認します。

誰でもデモアカウントを使って呼び出しを再現できます。残高を変更して、ルートが動くのを確認することもできます。

証明が保証しないこと

• 準備金そのもの。 この証明は、ある数値に対する負債の証明です。その数値には別途、独自の証拠が必要です。
• 顧客なしでの網羅性。 カストディアンが除外したアカウントを見つけられるのは、そのアカウントの持ち主である顧客だけです。確認する顧客が増えるほど、不正の余地は小さくなります。
• 準備金と一致する時点。 カストディアンは、スナップショットの時間帯だけ資金を借りることができます。予告なしの時刻に頻繁にスナップショットを取ることで、この余地は狭まります。
• 隠れた隣接ノード。 顧客のパスには、兄弟ノードの合計値が表示されます(第7節)。
• 1回の呼び出しで32アカウントを超えること。 予算を参照してください。