커스터디언은 각 고객에게 잔액을 지급할 의무를 집니다. 이 프로그램은 잔액을 하나도 공개하지 않고 총액도 공개하지 않은 채, 잔액의 합이 커스터디언이 공표한 준비금 수치를 넘지 않음을 증명합니다. 각 고객은 특별한 도구 없이 몇 줄의 Python만으로 자신의 잔액이 계산에 포함되었는지 확인할 수 있습니다.
Example programs에는 네 개의 예제 페이지가 공통으로 쓰는 설정이 있습니다.
1. 증명하는 내용
커스터디언은 Merkle 합계 트리를 만듭니다. 리프는 계정 하나이며, 고객의 id와 잔액을 합친 해시에 잔액이 함께 붙습니다. 노드는 두 자식과 그 합계를 합친 해시이며, 두 합계를 더한 값이 함께 붙습니다. 따라서 루트에는 그 아래에 있는 모든 잔액의 총합이 담깁니다.
트리는 비공개 계정 목록으로부터 프로그램 내부에서 만들어집니다. 이 호출은 다음을 증명합니다.
- 영수증에 공개된 루트는 커스터디언이 제공한 계정들에 대한 합계 트리의 루트입니다.
- 트리의 모든 합계는 그 아래 두 합계의 실제 합이며, 오버플로가 없습니다.
- 루트의 총합은 배포 시점에 고정된 준비금 수치 이하입니다.
2번은 증명 없이 공개된 합계 트리가 제공할 수 없는 부분입니다. 단순 합계 트리에 대한 알려진 공격은 커스터디언이 부모의 합계를 자식들의 합계보다 작게 기록하는 것인데, 고객은 경로 하나만으로는 이를 알아낼 수 없습니다. 여기서는 합계를 프로그램이 계산하므로, 다른 산술에 대한 증명은 존재하지 않습니다.
증명이 다루지 않는 것은 완전성입니다. 어떤 계정을 넣을지는 커스터디언이 선택합니다. 이 틈은 고객이 메웁니다. 각 고객은 자신의 id와 잔액을 가진 리프가 공개된 루트 아래에 있는지 확인합니다(7절). 누락된 계정은 그 소유자가 찾아냅니다.
2. 인터페이스
| 공개 워드 | 의미 |
|---|---|
| 0, 1 | 준비금 수치. 자산의 최소 단위로 표시한 u64이며, 하위 워드가 먼저, 상위 워드가 그다음 |
| 2 | 스냅샷 레이블. 프로그램은 읽지 않지만 프로그램 id가 이를 바인딩함 |
| 비공개 워드 | 의미 |
|---|---|
| 0 | 계정 수 n, 최대 32 |
| 이후 계정마다 | id(4개의 빅엔디언 워드로 된 16바이트), 잔액 하위 워드, 잔액 상위 워드 |
| 출력 슬롯 | 의미 |
|---|---|
| 0 | 상태: 1 충족, 2 미충족, 3 계정 수가 32개 초과, 4 합계 오버플로 |
| 1 | n |
| 2 to 6 | 루트 해시의 처음 20바이트를 5개의 빅엔디언 워드로 나타낸 값 |
| 7 | 미사용. Rust 패닉이 여기에 0xdeadbeef를 기록함 |
준비금 수치가 출력이 아니라 공개 세그먼트에 있는 데에는 두 가지 이유가 있습니다. 하나는 공간이 없다는 점입니다. 상태, 계정 수, 160비트 루트가 슬롯을 모두 채웁니다. 다른 하나는 증명이 존재하기 전에 주장을 먼저 밝힌다는 점입니다. 프로그램을 배포하면 “준비금 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진수로 출력하면 루트의 처음 여덟 자리 16진수가 됩니다. 두 해시가 서로 반대의 바이트 순서로 정의되어 있으므로, 이는 Keccak 프로그램과 반대되는 규약입니다.
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은 임의의 바이트열을 받아 한 번에 한 바이트씩 복사합니다. 여기서 모든 메시지는 길이가 알려진 온전한 워드들이므로, 프로그램은 16워드 블록을 직접 채웁니다. 메시지 워드, 그다음 0x80000000, 0들, 마지막 워드에 비트 길이를 넣습니다. 리프는 압축 한 번입니다. 노드의 84바이트는 두 번째 블록으로 넘어가므로 노드는 두 번입니다.
잔액은 u64이고 합계는 검사됩니다. 타입에 음수 값이 없으므로 잔액은 음수가 될 수 없고, 이로써 총합을 줄이는 또 하나의 고전적인 방법이 사라집니다. 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여기 있는 두 해시가 고객에게 필요한 명세의 전부입니다.
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에 열두 개의 계정이 있으며, 한 줄에 id,balance 하나씩이고 잔액은 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 202609302351 × 2³² + 2531887104는 10,100,000,000,000입니다. liabilities 줄은 커스터디언 자신의 관점이며 공개되지 않습니다.
id는 고유하고 추측할 수 없어야 합니다. 잔액이 같은 두 고객에게 같은 리프가 주어진다면, 커스터디언은 둘에 대해 부채를 하나만 계산할 수 있습니다. 해당 고객만 자신의 것으로 알아볼 수 있는 id는 이를 막고, 추측할 수 없는 id는 형제 해시를 본 고객이 이웃의 잔액을 짐작해 대입해 보는 일을 막습니다. 데모는 해시의 처음 16바이트를 사용합니다. 실제 배포에서는 고객의 계정과 스냅샷별 nonce로부터 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, 계정 열두 개, 그리고 스크립트가 출력한 다섯 개의 루트 워드가 나옵니다. 위트니스는 73워드이며, 계정 수 하나와 계정당 여섯 워드입니다.
준비금 수치를 100 단위로 낮추면(--public 100 0 1) 같은 계정들이 out[0] = 2를 냅니다. 계정 수가 33이면 out[0] = 3이 됩니다. 잔액의 합이 2⁶⁴를 넘는 두 계정은 out[0] = 4를 냅니다.
6. 예산
| 계정 12개 | 계정 32개 | |
|---|---|---|
| 비공개 워드 | 73 | 193 |
| 사이클 | 7,492 | 10,681 |
| SHA-256 압축 | 75 | 95 |
| 티어 | 14 | 14 |
압축 횟수는 리프 n개, 빈 리프 하나(한 번 계산해 복사), 그리고 31개 노드 각각에 두 번씩입니다. 한 호출은 최대 128번의 압축을 쓸 수 있고, 티어 14는 호출이 쓸 수 있는 가장 높은 티어이므로, 32개 계정은 이 설계에서 한 호출이 증명할 수 있는 한계에 가깝습니다. 64개 리프의 트리는 190번의 압축이 필요하여 들어맞지 않습니다.
이는 시연용 규모입니다. 이를 넘으려면 트리를 여러 호출로 나누고, 각 서브트리의 루트와 합계에 대한 커밋먼트를 최종 호출로 넘겨야 합니다. 이는 예산을 넘는 모든 작업에 대해 Write a program이 설명하는 패턴입니다. 이 예제는 그렇게 하지 않습니다.
체인 18부터 압축 한 번의 비용은 64 gas이며, 일반 사이클은 1입니다. 지갑은 실행의 정확한 gas와 선언한 한도를 출력합니다.
gas: 12489 (declaring 16384, tier 14)모든 행은 1 gas가 들고 압축 한 번은 63이 더 듭니다. 7,764개 행에 75 × 63을 더하면 12,489입니다. gas의 3분의 1 이상이 해싱입니다. (체인 18이 호출의 공개 세그먼트에 추가하는 트랜잭션 바인딩 때문에, 지갑은 rand-guest run보다 두 개 더 많은 행을 셉니다.)
7. 고객의 확인
커스터디언은 각 고객에게 그 고객의 경로, 즉 다섯 레벨 각각의 형제 해시와 형제 합계를 줍니다.
$ 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트리에 있는 값보다 한 단위 높은 잔액에 대한 경로는 루트에 도달하지 못합니다.
$ python3 solvency.py verify tampered.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix e9a1b4cbe49e412214b97afe73348fa7c555fa7a DOES NOT MATCH확인 전체는 위의 leaf와 parent 함수를 다섯 번 적용하는 것입니다. 커스터디언의 스크립트를 실행하고 싶지 않은 고객은 직접 작성할 수 있습니다.
경로는 고객에게 형제들의 합계를 보여 줍니다. 위 경로의 첫 단계는 이웃 리프가 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, 계정 열두 개, 그리고 16진수로 46b78564 d60f75bd c9552d8a d1c4aadf 41135405인 루트가 나옵니다. 트랜잭션의 어디에도 잔액이나 총합은 나타나지 않습니다.
This is a tier-14 call이므로, 호출 증명이 느린 부분입니다. 호출 증명에 123초, 지출 승인에 7초, 번들에 112초가 걸려 모두 5분이며, 최대 메모리 사용량은 6.6 GB입니다. 증명의 크기는 1,911,152바이트입니다. 이 중 SHA-256 테이블이 약 0.4 MB를 차지합니다.
10. 직접 확인하기
- 주장. 프로그램 id에 대한
rand_getProgramPublic은 준비금 수치와 레이블을 반환합니다. 수탁자가 실제로 그 준비금을 보유하고 있는지는 이 증명의 범위 밖입니다. 그것은 온체인 잔액, 감사인의 서한, 또는 브리지된 자산의 경우 체인 자체의rand_getTokenSupply로 확인됩니다. - 코드. 동일한 circuits 커밋에서
my-guests/solvency를 다시 빌드하고hc를 프로그램의code_hash와 비교합니다. - 영수증. 상태가
1이고, 슬롯 7이3735928559가 아니며,program이 id와 같아야 합니다. 출력 2~6은 모든 고객이 대조하는 루트입니다. - 본인의 리프를 7절에서와 같이 확인합니다.
누구나 데모 계정으로 호출을 반복하거나, 잔액을 바꾸어 루트가 달라지는 것을 확인할 수 있습니다.
증명이 보장하지 않는 것
- 준비금 자체. 이 증명은 어떤 수치에 대한 부채의 증명입니다. 그 수치에는 별도의 근거가 필요합니다.
- 고객 없이는 완전성을 보장할 수 없습니다. 수탁자가 누락한 계정은 그 계정이 속한 고객만이 발견할 수 있습니다. 확인하는 고객이 많을수록 여지는 줄어듭니다.
- 준비금과 일치하는 시점. 수탁자는 스냅샷 시간대에만 자금을 빌릴 수 있습니다. 예고 없는 시점에 스냅샷을 자주 찍으면 이를 줄일 수 있습니다.
- 숨겨진 이웃. 고객의 경로에는 형제 노드의 합계가 드러납니다(7절).
- 한 번의 호출에서 32개를 넘는 계정. 예산을 참조하십시오.