Un vote anonyme

Ce programme permet à un membre d’une liste fixe de déposer un vote sans révéler de quel membre il s’agit. La liste est un arbre de Merkle de hachages Keccak-256, construit comme on construit une liste d’airdrop Ethereum : le même outillage suffit donc à le produire. Le programme est déployé sur la chain 18, et la dernière section l’appelle avec des membres de démonstration que vous pouvez utiliser vous-même.

Example programs présente la configuration commune aux quatre pages d’exemples : le checkout des circuits, le wallet et l’origine des sources.

1. Ce que le programme prouve

Un organisateur dispose d’une liste de membres. Chaque membre détient un secret de 32 octets. L’organisateur ne voit jamais les secrets : chaque membre lui remet une feuille, keccak256(secret ‖ tag), et l’organisateur construit un arbre de Merkle sur les feuilles.

Un vote tient en un appel. Il prouve, sans rien révéler d’autre :

1. l’appelant connaît un secret dont la feuille figure dans l’arbre ;
2. le choix publié fait partie des choix autorisés ;
3. le nullifier publié est keccak256(secret ‖ tag ‖ poll id).

Le nullifier est identique pour tous les votes qu’un même secret dépose dans un même scrutin, et différent dans tout autre scrutin. Celui qui dépouille les votes compte chaque nullifier une seule fois. Il n’est pas lié à la feuille : remonter d’un nullifier à une feuille exige le secret.

La chain ne rejette pas un second vote. Un programme sur Rand n’a pas de stockage et ne peut donc pas mémoriser un nullifier (Programs). Deux appels avec le même secret sont tous deux valides et laissent chacun un reçu. La règle « un nullifier, un vote » est appliquée par le décompte, sur les reçus. N’importe qui peut refaire le même décompte, ce qui rend le résultat vérifiable.

2. L’interface

L’arbre, le scrutin et le nombre de choix sont les mêmes pour tous les votes ; ils vont donc dans le segment public, fixé au déploiement. L’identifiant du programme désigne alors ce scrutin et aucun autre.

Un hachage de 32 octets fait huit mots, et huit mots, c’est toute la sortie disponible. Publier 160 bits laisse de la place pour le statut et le choix. Deux membres ne partageraient un nullifier de 160 bits que par une collision de hachage, qu’il faut environ 2⁸⁰ essais pour trouver.

Ordre des octets. Keccak travaille sur des octets. L’appel système KECCAK de la machine prend l’état sous forme de mots, l’octet i de l’état se trouvant dans l’octet i mod 4 du mot i / 4. Ainsi, 32 octets deviennent huit mots en les lisant quatre par quatre, en little-endian, et la racine du segment public n’est que les octets de la racine lus de cette façon.

3. Le guest

my-guests/allowlist/src/main.rs, en entier :

#![no_std]
#![no_main]

use guest_sdk::{halt, keccak, read_input, read_public, write_output};

const MAX_DEPTH: u32 = 20;

const OK: u32 = 1;
const NOT_MEMBER: u32 = 2;
const BAD_CHOICE: u32 = 3;
const BAD_SETUP: u32 = 4;

/// The 32 bytes hashed after a secret to make its leaf: the ASCII tag, zero-padded.
const LEAF_TAG: [u32; 8] = tag_words(b"rand-allowlist-leaf-v1");
/// The first 28 bytes hashed after a secret to make its nullifier; the poll id is the last 4.
const NULL_TAG: [u32; 8] = tag_words(b"rand-allowlist-null-v1");

/// An ASCII tag as eight words: byte `i` of the tag is byte `i % 4` of word `i / 4`.
const fn tag_words(tag: &[u8]) -> [u32; 8] {
    let mut w = [0u32; 8];
    let mut i = 0;
    while i < tag.len() {
        w[i / 4] |= (tag[i] as u32) << (8 * (i % 4));
        i += 1;
    }
    w
}

/// Keccak-256 of a 64-byte message, the hash Ethereum calls `keccak256(abi.encodePacked(a, b))`.
/// The message is one rate block, so this is one permutation: the two halves go into the first
/// 16 words of the state, `0x01` follows them, and `0x80` closes the 136-byte rate.
///
/// `a_second` is 0 or 1. When it is 1 the halves trade places. The place is computed as an
/// offset, not chosen by a branch, so both orders execute the same instructions.
fn hash2(a: &[u32; 8], b: &[u32; 8], a_second: u32) -> [u32; 8] {
    let at = 8 * (a_second & 1) as usize;
    let mut st = [0u32; 50];
    st[at..at + 8].copy_from_slice(a);
    st[8 - at..16 - at].copy_from_slice(b);
    st[16] = 0x01;
    st[33] = 0x8000_0000;
    keccak(&mut st);
    let mut out = [0u32; 8];
    out.copy_from_slice(&st[..8]);
    out
}

fn read8(at: u32) -> [u32; 8] {
    let mut w = [0u32; 8];
    for (i, x) in w.iter_mut().enumerate() {
        *x = read_input(at + i as u32);
    }
    w
}

/// Public segment, fixed at deploy: [depth, poll id, number of choices, root (8 words)].
/// Private input: [secret (8 words), leaf index, choice, siblings (8 words per level)].
/// Outputs: [status, choice, nullifier (5 words), 0].
#[no_mangle]
pub extern "C" fn main() -> ! {
    let depth = read_public(0);
    let poll = read_public(1);
    let choices = read_public(2);
    if depth == 0 || depth > MAX_DEPTH {
        write_output(0, BAD_SETUP);
        halt();
    }

    let secret = read8(0);
    let index = read_input(8);
    let choice = read_input(9);

    // Walk from the leaf to the root. Bit `level` of the index says whether the running hash
    // is the right child at that level.
    let mut cur = hash2(&secret, &LEAF_TAG, 0);
    let mut level = 0;
    while level < depth {
        let sib = read8(10 + 8 * level);
        cur = hash2(&cur, &sib, index >> level);
        level += 1;
    }

    let mut diff = 0u32;
    for k in 0..8 {
        diff |= cur[k] ^ read_public(3 + k as u32);
    }

    let mut ctx = NULL_TAG;
    ctx[7] = poll;
    let nullifier = hash2(&secret, &ctx, 0);

    if diff != 0 {
        write_output(0, NOT_MEMBER);
    } else if choice >= choices {
        write_output(0, BAD_CHOICE);
    } else {
        write_output(0, OK);
        write_output(1, choice);
        for k in 0..5 {
            write_output(2 + k as u32, nullifier[k]);
        }
    }
    halt();
}

Trois points méritent d’être repris.

Une permutation par hachage. guest_sdk::keccak256 accepte n’importe quelle chaîne d’octets, et le paie en boucles sur les octets. Ici, chaque message fait exactement 64 octets, soit moins que le débit de 136 octets : le bourrage se réduit à deux mots constants et le hachage à un seul appel KECCAK sur un état rempli par copies de mots. En termes Ethereum, hash2(a, b, 0) est keccak256(abi.encodePacked(a, b)) pour deux bytes32.

La feuille et le nullifier ne peuvent pas être confondus avec un nœud de l’arbre. Un nœud hache deux hachages enfants de 32 octets. Une feuille hache un secret et un tag ASCII fixe, et un nullifier hache un secret, un autre tag et l’identifiant du scrutin. Pour qu’une feuille passe pour un nœud, l’un de ses enfants devrait être égal au tag, ce qui revient à trouver une préimage de Keccak.

Le chemin est parcouru sans branchement sur l’indice. La première version choisissait l’ordre des deux moitiés par un échange masqué, et le compilateur a retransformé le masque en branchement : l’exécution coûtait 9 cycles de plus pour chaque bit à 1 de l’indice de la feuille. Le nombre de cycles n’est pas publié, mais la limite de gas qu’un appel déclare en est un arrondi (section 6) ; une exécution qui dépend de l’indice peut donc en laisser fuir un peu. Écrire chaque moitié à un décalage calculé a réglé le problème : chaque indice de feuille s’exécute désormais en 3 208 cycles, ni plus ni moins.

4. Côté hôte

L’organisateur et les votants ont besoin du même Keccak que celui que calcule la machine. allowlist.py est un script Python sans dépendance, avec son propre Keccak-f[1600] (le hashlib.sha3_256 de Python est du SHA-3, dont le bourrage diffère et qui donne d’autres condensats). Il remplit deux tâches :

allowlist.py setup  <depth> <poll id> <choices> <secrets file>   writes public.txt, prints the root
allowlist.py witness <depth> <poll id> <secrets file> <member> <choice>
                                                   prints the private words and the nullifier

L’arbre entier, dans les termes du script :

LEAF_TAG = b"rand-allowlist-leaf-v1".ljust(32, b"\0")
NULL_TAG = b"rand-allowlist-null-v1".ljust(28, b"\0")
EMPTY = bytes(32)  # an unused leaf: no secret hashes to it

def levels(depth, secrets):
    row = [keccak256(s + LEAF_TAG) for s in secrets]
    row += [EMPTY] * ((1 << depth) - len(row))
    out = [row]
    while len(row) > 1:
        row = [keccak256(row[i] + row[i + 1]) for i in range(0, len(row), 2)]
        out.append(row)
    return out

nullifier = keccak256(secret + NULL_TAG + poll.to_bytes(4, "little"))

En production, l’organisateur détient des feuilles, pas des secrets, et chaque votant construit son propre témoin à partir des feuilles publiées. Le script prend un fichier de secrets parce que la démo joue les deux rôles.

Le scrutin de démonstration a une profondeur de 10 (1 024 feuilles), l’identifiant de scrutin 1 et trois choix. Les secrets de ses huit membres figurent dans demo-secrets.txt, un secret de 64 caractères hexadécimaux par ligne, et ils sont publics à dessein pour que chacun puisse appeler le programme :

$ python3 allowlist.py setup 10 1 3 demo-secrets.txt
root ce8d6ef78a2ccaab688afa50ff969b0f89b23e7f32d8c3746848b46f773f4750
wrote public.txt
$ cat public.txt
10 1 3 4151217614 2882153610 1358596712 261854975 2134815369 1958991922 1874085992 1346846583

Le premier mot de la racine, 4151217614, vaut 0xf76e8dce : les quatre premiers octets de la racine ce 8d 6e f7, lus en little-endian.

5. Compiler et exécuter

$ rand-guest build my-guests/allowlist --max-words 65535
427 words against a cap of 65535 (fits); 0 ecall(s) with a non-static a7
OK
wrote my-guests/allowlist/image.bin and its .sha256 (427 words, hc 420876739f0987ae7f0fbd23a98312ed4452b7e77cf6153e424ed02aca7b5afe, program id 93c780859b60516408099dc45247a21aead612f0c65c667248253533dd932bb3)

Le membre 5 vote pour le choix 2. Le témoin compte 90 mots : 8 pour le secret, l’indice, le choix et 80 pour le chemin.

$ cd my-guests/allowlist
$ python3 allowlist.py witness 10 1 demo-secrets.txt 5 2 > witness.txt
nullifier b5516c17d7f51034998f837217777deb8bc90886
nullifier words 392974773 873526743 1921224601 3950868247 2248722827
$ rand-guest run image.bin --public $(cat public.txt) --input $(cat witness.txt) --tier 14
out[0] = 1
out[1] = 2
out[2] = 392974773
out[3] = 873526743
out[4] = 1921224601
out[5] = 3950868247
out[6] = 2248722827
out[7] = 0
cycles 3208
tier 12
tier 14: fits (cycles 3342 of 16383, Poseidon2 permutations 134 of 2048)

Les cinq mots du nullifier sont ceux que le script a calculés hors de la machine. Les échecs s’arrêtent proprement avec un statut, et peuvent donc eux aussi être prouvés. Le même témoin avec le premier mot du secret modifié donne out[0] = 2 et rien d’autre, et un membre qui demande le choix 3 sur 3 donne out[0] = 3.

6. Le budget

Chaque niveau de profondeur supplémentaire coûte une permutation et environ 270 cycles. Un arbre de profondeur 20 (un million de membres) mesure 5 866 cycles et 22 permutations, ce qui correspond au palier 14, le plus élevé qu’un appel puisse utiliser.

Depuis la chain 18, un appel paie du gas, et une permutation Keccak est l’instruction coûteuse : 192 gas contre 1 pour un cycle ordinaire. Le wallet affiche le gas exact d’une exécution et la limite qu’il déclare pour elle :

gas: 5636 (declaring 6144, tier 12)

Chaque ligne de l’exécution coûte 1 gas, et une ligne Keccak en coûte 191 de plus : 3 344 lignes plus 12 × 191 font 5 636, dont deux cinquièmes viennent des douze hachages. Le wallet compte deux lignes de plus que ne le faisait rand-guest run. Sur la chain 18, une preuve d’appel est liée à sa transaction, et cette liaison voyage sous forme de huit mots supplémentaires de segment public, ce qui ajoute deux lignes de condensat. La limite déclarée, 6 144, est le chiffre exact arrondi au multiple de 1 024 supérieur. La limite est publique, le chiffre exact ne l’est pas.

Une preuve qui porte la table Keccak est volumineuse. Celle-ci fait 3 346 865 octets, pour un plafond de 4 194 304 (4 MiB) sur les chains 18 à 20. Les chiffres de profondeur 20 ci-dessus sont des mesures de l’émulateur, et aucune preuve n’a été produite à cette profondeur pour cette page.

7. Déployer

Le déploiement porte le segment public ; les frais comptent donc ses 11 mots avec les 427 mots de code : 0.001 + 0.0001 × 438 = 0,0448 RAND.

$ rand fee deploy 427 --public-words 11
0.0448 RAND
$ rand program deploy image.bin --public public.txt
program id: ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970 (427 words, hc 73760842ae87099f23bd0f7fed1283a9e7b752443e15f67c2ad04e42fe5a7bca, public input 11 words, digest 2296cfca8db9d38bd0b7579056c9dea3c8d8005df7b42e2b1e954a75fed67510)
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 22.9s: tier 10, 1370827 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 190.2s: tier 14, 1497544 bytes
submitted deploy 05f8bfcbf9fccedbd53c3ba41bcc32dc8070ed3433364fc591b4f00699438de6
  0 RAND out, 59.9552 RAND change, fee 0.0448 RAND, anchored at height 97632, proved in 190.2s (bundle) + 22.9s (auth)

L’identifiant qu’affiche deploy, ad2f719f…b970, n’est pas celui qu’affichait rand-guest build. Avec un segment public, l’identifiant est blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public) : il lie donc la racine, l’identifiant du scrutin et le nombre de choix. Un second scrutin sur les mêmes membres est un second déploiement du même code avec un identifiant de scrutin différent, et obtient un identifiant de programme différent ainsi que d’autres nullifiers.

hc s’écrit lui aussi autrement : rand-guest affiche chacun de ses huit mots en big-endian, tandis que le wallet affiche les octets de chaque mot en little-endian ; 42087673 est ainsi devenu 73760842. C’est le même condensat.

$ rand program show ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970
{
  "base_pc": 4096,
  "code_hash": "73760842ae87099f23bd0f7fed1283a9e7b752443e15f67c2ad04e42fe5a7bca",
  "deployed_at": 97821,
  "id": "ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970",
  "public_digest": "2296cfca8db9d38bd0b7579056c9dea3c8d8005df7b42e2b1e954a75fed67510",
  "public_words_len": 11,
  "words_len": 427
}

N’importe qui peut relire le segment public. rand_getProgramPublic renvoie les mots sous forme d’octets little-endian, de sorte que la racine apparaît telle qu’elle a été imprimée :

$ curl -s https://rpc.randprotocol.org -H 'content-type: application/json' \
    -d '{"jsonrpc":"2.0","id":1,"method":"rand_getProgramPublic","params":["ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970"]}'
{"id":1,"jsonrpc":"2.0","result":"0a0000000100000003000000ce8d6ef78a2ccaab688afa50ff969b0f89b23e7f32d8c3746848b46f773f4750"}

8. Voter

rand call prend un --input par mot privé, en décimal. Le sed transforme le fichier de témoin en ces options :

$ rand call ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970 \
    $(sed 's/[0-9][0-9]*/--input &/g' witness.txt)

proving the call locally (90 inputs stay private, over the program's 11-word public input)…
gas: 5636 (declaring 6144, tier 12)
fee 0.006191437 RAND (incl. two price steps of headroom)
proved in 29.2s: tier 12, 3346865 bytes, outputs [1, 2, 392974773, 873526743, 1921224601, 3950868247, 2248722827, 0]
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 8.2s: tier 10, 1367303 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 117.2s: tier 14, 1504260 bytes
submitted call 8aa13d1f76d28f63a46c30bb09ef44b1ba35083ca80ba7301997f98e5f783666
  0 RAND out, 59.716708563 RAND change, fee 0.006191437 RAND, anchored at height 98185, proved in 117.2s (bundle) + 8.2s (auth)
{
  "h_in": "ea71e7701e62d49cac37b239bef132178f481835027d62b34da45fd6cf2667c6",
  "h_pub": "2296cfca8db9d38bd0b7579056c9dea3c8d8005df7b42e2b1e954a75fed67510",
  "height": 98335,
  "index": 0,
  "outputs": [
    1,
    2,
    392974773,
    873526743,
    1921224601,
    3950868247,
    2248722827,
    0
  ],
  "program": "ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970",
  "tier": 12,
  "tx": "8aa13d1f76d28f63a46c30bb09ef44b1ba35083ca80ba7301997f98e5f783666"
}
input transcript published; open it with `rand open-call 8aa13d1f76d28f63a46c30bb09ef44b1ba35083ca80ba7301997f98e5f783666`

Le reçu est ce que la chaîne conserve : le statut 1, le choix 2 et les cinq mots de nullifier, sous l’identifiant de programme du scrutin. h_pub est le condensat du segment public du scrutin, la même valeur que celle affichée par program show. h_in est un engagement salé portant sur les 90 mots privés ; sans le sel, il n’ouvre rien.

L’appel a pris trois minutes sur un ordinateur portable Apple Silicon, avec un pic à 6,1 GB : 29 s pour la preuve de l’appel, 8 s pour l’autorisation de dépense et 117 s pour le lot qui paie les frais. Les frais, 0,0062 RAND, sont pour l’essentiel des octets. Four programs on chain 20 en donne le calcul.

La ligne de transcription. Par défaut, le portefeuille scelle les entrées privées dans une enveloppe que seule la clé de visualisation de l’appelant peut ouvrir, et la publie avec l’appel. C’est un enregistrement pour l’appelant, non une divulgation : personne d’autre ne peut l’ouvrir. Un votant qui ne veut aucune trace passe --no-envelope. Ensuite, plus personne, le votant compris, ne pourra jamais montrer quelles étaient les entrées.

9. Compter les votes

Un décompte n’exige rien d’autre que la chaîne :

1. Le scrutin. Récupérez le segment public du programme et vérifiez la racine par rapport à la liste publiée des feuilles (reconstruisez l’arbre avec levels de allowlist.py). Reconstruisez le guest à partir des sources et comparez hc au code_hash du programme.
2. Les reçus. Prenez chaque reçu dont le program est l’identifiant du scrutin et dont la sortie 0 vaut 1. Un reçu avec un autre statut, ou avec 3735928559 dans l’emplacement 7, n’est pas un vote.
3. Le décompte. Regroupez par sorties 2 à 6. Comptez chaque nullifier une seule fois, à son premier reçu dans l’ordre de la chaîne, et ajoutez sa sortie 1 au total.

Trois appels supplémentaires ont été faits pour donner quelque chose à compter. Le membre 5 a voté une seconde fois, cette fois pour le choix 0. Le membre 2 a voté pour le choix 1. Le membre 3 a voté pour le choix 0, depuis un portefeuille qui n’utilisait que le point d’accès RPC public. Voici le second vote du membre 5 :

$ python3 allowlist.py witness 10 1 demo-secrets.txt 5 0 > witness.txt
nullifier b5516c17d7f51034998f837217777deb8bc90886
nullifier words 392974773 873526743 1921224601 3950868247 2248722827
$ rand call ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970 \
    $(sed 's/[0-9][0-9]*/--input &/g' witness.txt)
…
proved in 31.0s: tier 12, 3345265 bytes, outputs [1, 0, 392974773, 873526743, 1921224601, 3950868247, 2248722827, 0]
…
submitted call 0f596b87f5137a165d6abc691dbe04f7533db619911d81449fea9ede602c40d0

La chaîne a accepté le second vote, comme elle le doit : la preuve est valide. Son reçu porte les mêmes cinq mots de nullifier que le premier.

tally.py applique les trois règles. Il lit les appels du programme depuis l’explorateur et chaque reçu depuis le RPC public, de sorte qu’il n’a besoin ni de portefeuille ni de nœud :

$ python3 tally.py ad2f719f12d01c9f3c0962092b9898b75b0914bbb817031d51be13e54c05b970
8aa13d1f…  height 98335  choice 2  nullifier b5516c17d7f51034…  counted
0f596b87…  height 99194  choice 0  nullifier b5516c17d7f51034…  repeat, dropped
2db517df…  height 99339  choice 1  nullifier 52f2455918bbc811…  counted
fdbcc960…  height 101833  choice 0  nullifier cd86c5454b809914…  counted
tally: choice 0: 1, choice 1: 1, choice 2: 1

Le revirement du membre 5 n’a pas été compté, et rien dans les quatre reçus n’indique que deux d’entre eux proviennent du même membre de la liste, hormis le nullifier lui-même. Le scrutin est ouvert : votez en tant que l’un des huit membres de démonstration et relancez le décompte.

Ce que la preuve ne vous donne pas

• Un vote par secret, non un vote par personne. L’organisateur décide qui obtient une feuille. Un membre qui enregistre deux feuilles dispose de deux votes.
• Le secret du votant ne vaut que par son aléa. Un secret dérivé d’une chaîne devinable peut être retrouvé en hachant des hypothèses et en les comparant aux feuilles publiées. Utilisez 32 octets aléatoires.
• Le choix est public. Un reçu montre pour quel choix un nullifier a voté. Personne ne peut dire de quel membre il s’agit, mais un scrutin comptant peu de votants et dont la participation est publiée relève de la statistique sur petits nombres, non de la cryptographie.
• L’horodatage et les frais sont des métadonnées. Le lot des frais est protégé (shielded) et ne nomme personne, mais un votant qui alimente son portefeuille puis vote une minute plus tard, à une heure creuse, a appris quelque chose à un observateur.
• Le décompte se fait hors chaîne. La chaîne stocke les reçus. Les compter, et refuser un second nullifier, revient à quiconque les lit.