Un dépositaire doit à chaque client un solde. Ce programme prouve que la somme des soldes ne dépasse pas un chiffre de réserves que le dépositaire a publié, sans publier ni un solde ni le total. Chaque client peut vérifier, avec quelques lignes de Python et sans outillage particulier, que son propre solde a été compté.
Example programs présente la mise en place commune aux quatre pages d’exemples.
1. Ce qu’il prouve
Le dépositaire construit un arbre de Merkle à sommes. Une feuille est un compte : un hachage de l’identifiant du client et de son solde, avec le solde à côté. Un nœud est un hachage de ses deux enfants et de leurs sommes, avec la somme des deux à côté. La racine porte donc le total de tous les soldes situés en dessous.
L’arbre est construit à l’intérieur du programme, à partir de la liste privée des comptes. L’appel prouve que :
- la racine publiée dans le reçu est la racine d’un arbre à sommes portant sur les comptes fournis par le dépositaire ;
- chaque somme y est la vraie somme des deux qui se trouvent en dessous, sans débordement ;
- le total à la racine est au plus égal au chiffre de réserves fixé au déploiement.
Le point 2 est ce qu’un arbre à sommes publié sans preuve ne peut pas offrir. L’attaque connue contre un arbre à sommes nu est celle d’un dépositaire qui inscrit pour un parent une somme inférieure à celle de ses enfants, ce qu’aucun client ne peut détecter à partir d’un seul chemin. Ici, les sommes sont calculées par le programme, et il n’existe pas de preuve pour une autre arithmétique.
Ce que la preuve ne couvre pas, c’est l’exhaustivité : le dépositaire choisit quels comptes y figurent. Cette lacune est comblée par les clients. Chacun vérifie qu’une feuille portant son identifiant et son solde se trouve sous la racine publiée (section 7). Un compte omis est découvert par son titulaire.
2. L’interface
| mot public | signification |
|---|---|
| 0, 1 | le chiffre de réserves, un u64 dans les plus petites unités de l’actif, mot de poids faible puis mot de poids fort |
| 2 | une étiquette d’instantané ; le programme ne la lit pas, mais l’identifiant du programme la lie |
| mot privé | signification |
|---|---|
| 0 | le nombre de comptes n, au plus 32 |
| puis, par compte | l’identifiant (16 octets sous forme de quatre mots big-endian), le mot de poids faible du solde, le mot de poids fort du solde |
| emplacement de sortie | signification |
|---|---|
| 0 | statut : 1 couvert, 2 non couvert, 3 plus de 32 comptes, 4 une somme a débordé |
| 1 | n |
| 2 à 6 | les 20 premiers octets du hachage de la racine, sous forme de cinq mots big-endian |
| 7 | inutilisé ; une panique Rust y écrit 0xdeadbeef |
Le chiffre de réserves se trouve dans le segment public et non dans les sorties, pour deux raisons. Il n’y a pas de place : le statut, le compte et une racine de 160 bits remplissent les emplacements. Et il énonce l’affirmation avant que la preuve n’existe : déployer le programme publie « réserves de R, instantané S », puis l’appel prouve soit que les soldes tiennent sous R, soit renvoie le statut 2.
Les hachages, exactement :
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 0L’arbre compte toujours 32 feuilles. Les comptes le remplissent depuis la gauche et des feuilles vides occupent le reste. Les 0 et 1 initiaux empêchent qu’une feuille soit jamais lue comme un nœud.
Ordre des octets. SHA-256 est big-endian de bout en bout, et l’appel système SHA256 prend son bloc de 64 octets sous forme de seize mots big-endian. Ce programme lit donc un identifiant comme quatre mots big-endian et publie la racine sous forme de mots big-endian : la sortie 2 affichée en hexadécimal correspond aux huit premiers chiffres hexadécimaux de la racine. C’est la convention inverse de celle de the Keccak program, car les deux hachages sont définis sur des ordres d’octets opposés.
3. Le programme invité
my-guests/solvency/src/main.rs, complet :
#![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();
}Le bourrage est écrit à la main. guest_sdk::sha256 accepte n’importe quelle chaîne d’octets et la copie octet par octet. Chaque message ici est composé de mots entiers de longueur connue ; le programme remplit donc directement le bloc de 16 mots : les mots du message, puis 0x80000000, des zéros, et la longueur en bits dans le dernier mot. Une feuille tient en une compression. Les 84 octets d’un nœud débordent sur un second bloc : un nœud en demande donc deux.
Les soldes sont des u64 et les sommes sont vérifiées. Un solde ne peut pas être négatif, car le type n’a pas de valeurs négatives, ce qui supprime l’autre moyen classique de réduire un total. checked_add transforme un débordement en statut 4 au lieu d’une somme tronquée.
Un résultat d’insolvabilité reste un résultat. Le statut 2 est un arrêt ordinaire, avec la racine publiée. Un dépositaire ne peut pas obtenir un reçu de statut 1 pour des soldes qui dépassent le chiffre de réserves, et un reçu de statut 2 est précisément la preuve du contraire.
4. Côté hôte
solvency.py n’utilise que la bibliothèque standard de 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 rootLes deux hachages qu’il contient forment toute la spécification dont un client a besoin :
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]La démonstration comporte douze comptes dans demo-accounts.csv, un id,balance par ligne, avec des soldes en unités de 10⁻⁸ (la précision qu’utilise un jeton ponté tel que zUSD). Ils totalisent 100 215,185678. Le dépositaire déclare des réserves de 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 vaut 10 100 000 000 000. La ligne liabilities est la vue propre du dépositaire. Elle n’est jamais publiée.
Les identifiants doivent être uniques et impossibles à deviner. Si deux clients ayant le même solde recevaient la même feuille, le dépositaire pourrait ne compter qu’un seul engagement pour les deux. Un identifiant que seul son client peut reconnaître comme le sien l’empêche, et un identifiant impossible à deviner empêche un client qui voit le hachage d’un voisin de tester des hypothèses sur le solde de ce voisin. La démonstration utilise les 16 premiers octets d’un hachage. Un déploiement réel dériverait l’identifiant du compte du client et d’un nonce propre à chaque instantané, puis le montrerait au client.
5. Compiler et exécuter
$ 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)Statut 1, douze comptes, et les cinq mots de la racine que le script a affichés. Le témoin compte 73 mots : le compte, puis six par compte.
Avec le chiffre de réserves abaissé à 100 unités (--public 100 0 1), les mêmes comptes donnent out[0] = 2. Un nombre de comptes de 33 donne out[0] = 3. Deux comptes dont les soldes additionnés dépassent 2⁶⁴ donnent out[0] = 4.
6. Le budget
| 12 comptes | 32 comptes | |
|---|---|---|
| mots privés | 73 | 193 |
| cycles | 7 492 | 10 681 |
| compressions SHA-256 | 75 | 95 |
| palier | 14 | 14 |
Le nombre de compressions est de n feuilles, une feuille vide (calculée une fois puis copiée), et deux pour chacun des 31 nœuds. Un appel peut utiliser au plus 128 compressions, et le palier 14 est le plus élevé qu’un appel puisse employer : 32 comptes, c’est à peu près ce qu’un seul appel peut prouver dans cette conception. Un arbre de 64 feuilles demande 190 compressions et ne tient pas.
C’est une taille de démonstration. Aller au-delà suppose de répartir l’arbre sur plusieurs appels et de reporter un engagement sur la racine et la somme de chaque sous-arbre dans un appel final, le schéma que Write a program décrit pour tout travail qui dépasse le budget. Cet exemple ne le fait pas.
Depuis la chaîne 18, une compression coûte 64 gas, contre 1 pour un cycle ordinaire. Le portefeuille affiche le gas exact d’une exécution et la limite qu’il déclare :
gas: 12489 (declaring 16384, tier 14)Chaque ligne coûte 1 gas et une compression en coûte 63 de plus : 7 764 lignes plus 75 × 63 donnent 12 489. Plus du tiers du gas va au hachage. (Le portefeuille compte deux lignes de plus que rand-guest run, à cause de la liaison de transaction que la chaîne 18 ajoute au segment public d’un appel.)
7. La vérification d’un client
Le dépositaire remet à chaque client son chemin : le hachage frère et la somme sœur à chacun des cinq niveaux.
$ 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,Le client recalcule la racine à partir de son propre identifiant et de son solde, puis compare ses 20 premiers octets avec les sorties 2 à 6 du reçu :
$ python3 solvency.py verify proof6.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix 46b78564d60f75bdc9552d8ad1c4aadf41135405 MATCHUn chemin pour un solde supérieur d’une unité à celui de l’arbre n’atteint pas la racine :
$ python3 solvency.py verify tampered.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix e9a1b4cbe49e412214b97afe73348fa7c555fa7a DOES NOT MATCHLa vérification complète consiste à appliquer cinq fois les fonctions leaf et parent ci-dessus. Un client qui ne souhaite pas exécuter le script du dépositaire peut l’écrire lui-même.
Un chemin montre au client les sommes de ses frères. La première étape du chemin ci-dessus révèle que la feuille voisine contient 6 600 000 000 unités, et chaque étape supérieure révèle le total d’un sous-arbre. C’est inhérent à un arbre à sommes simple. Mélanger les feuilles à chaque instantané limite ce qu’un client peut apprendre au fil du temps, et masquer entièrement les sommes exige des engagements à la place de nombres en clair, ce que cet exemple ne fait pas.
8. Déploiement
$ 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)L’identifiant du programme lie le chiffre de réserves et l’étiquette d’instantané au code. Un nouvel instantané est un nouveau déploiement, pour environ un dixième de RAND, et son identifiant est l’énoncé public de la nouvelle affirmation.
9. Appel
$ 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`Statut 1, douze comptes, et la racine 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 en hexadécimal. Rien dans la transaction n’indique un solde ni le total.
Il s’agit d’un appel de niveau 14 : la preuve d’appel est donc l’étape la plus lente. Elle prend 123 s, auxquelles s’ajoutent 7 s pour l’autorisation de dépense et 112 s pour le bundle, soit cinq minutes au total, avec un pic de 6,6 GB. La preuve pèse 1 911 152 octets, dont environ 0,4 MB pour la table SHA-256.
10. Vérifier soi-même
- L’affirmation.
rand_getProgramPublicappelé sur l’identifiant du programme renvoie le chiffre des réserves et le libellé. Que le dépositaire détienne réellement ces réserves ne relève pas de cette preuve : on le montre par un solde on-chain, par une lettre d’auditeur ou, pour un actif ponté, par lerand_getTokenSupplyde la chaîne elle-même. - Le code. Reconstruisez
my-guests/solvencyau même commit de circuits et comparezhcaucode_hashdu programme. - Le reçu. Statut
1, emplacement 7 différent de3735928559, etprogramégal à l’identifiant. Les sorties 2 à 6 forment la racine que chaque client vérifie. - Votre propre feuille, comme à la section 7.
Chacun peut refaire l’appel avec les comptes de démonstration, ou modifier un solde et observer le déplacement de la racine.
Ce que la preuve ne vous apporte pas
- Les réserves elles-mêmes. La preuve porte sur des engagements au regard d’un nombre. Ce nombre exige ses propres justificatifs.
- L’exhaustivité sans les clients. Un compte que le dépositaire a écarté n’est découvert que par le client auquel il appartient. Plus les clients vérifient, moins la marge est grande.
- Un instant qui coïncide avec celui des réserves. Un dépositaire peut emprunter des fonds pour l’heure de l’instantané. Des instantanés fréquents, à des moments non annoncés, réduisent cette possibilité.
- Des voisins masqués. Le chemin d’un client montre les sommes des nœuds frères (section 7).
- Plus de 32 comptes dans un seul appel. Voir le budget.