Un voto anonimo

Questo programma permette a un membro di un elenco fisso di esprimere un voto senza rivelare quale membro sia. L’elenco è un albero di Merkle di hash Keccak-256, costruito come si costruisce l’elenco di un airdrop su Ethereum, quindi lo stesso strumentario lo produce. Il programma è distribuito sulla chain 18, e l’ultima sezione lo invoca con membri dimostrativi che puoi usare tu stesso.

Programmi di esempio contiene la configurazione che tutte e quattro le pagine di esempio condividono: il checkout dei circuiti, il wallet e dove ottenere i sorgenti.

1. Cosa dimostra

Un organizzatore ha un elenco di membri. Ogni membro possiede un segreto di 32 byte. L’organizzatore non vede mai i segreti: ogni membro consegna una foglia, keccak256(secret ‖ tag), e l’organizzatore costruisce un albero di Merkle sulle foglie.

Un voto è una sola chiamata. Dimostra, senza rivelare nient’altro, che:

1. il chiamante conosce un segreto la cui foglia è nell’albero;
2. la scelta pubblicata è una di quelle consentite;
3. il nullifier pubblicato è keccak256(secret ‖ tag ‖ poll id).

Il nullifier è lo stesso per ogni voto che un segreto esprime in una stessa votazione, e diverso in ogni altra votazione. Chi conta i voti conta ogni nullifier una sola volta. Non è collegato alla foglia: risalire da un nullifier a una foglia richiede il segreto.

La chain non rifiuta un secondo voto. Un programma su Rand non ha storage, quindi non può ricordare un nullifier (Programmi). Due chiamate con lo stesso segreto vengono entrambe verificate e lasciano entrambe una ricevuta. La regola «un nullifier, un voto» è applicata dal conteggio, sulle ricevute. Chiunque può eseguire lo stesso conteggio, ed è questo che rende verificabile lo spoglio.

2. L’interfaccia

L’albero, la votazione e il numero di scelte sono gli stessi per ogni voto, quindi stanno nel segmento pubblico, fissato al momento del deploy. L’id del programma identifica allora questa votazione e nessun’altra.

Un hash di 32 byte sono otto parole, e otto parole sono tutto l’output disponibile. Pubblicare 160 bit lascia spazio allo stato e alla scelta. Due membri condividerebbero un nullifier di 160 bit solo per una collisione di hash, che richiede circa 2⁸⁰ tentativi per essere trovata.

Ordine dei byte. Keccak lavora su byte. La syscall KECCAK della macchina riceve lo stato come parole, con il byte i dello stato nel byte i mod 4 della parola i / 4. Quindi 32 byte diventano otto parole leggendo quattro byte alla volta, in little-endian, e la radice nel segmento pubblico è semplicemente la sequenza di byte della radice letta in quel modo.

3. Il guest

my-guests/allowlist/src/main.rs, completo:

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

Tre aspetti sono da copiare.

Una permutazione per hash. guest_sdk::keccak256 accetta qualsiasi stringa di byte, e lo paga con cicli sui byte. Qui ogni messaggio è esattamente di 64 byte, meno dei 136 byte del rate, quindi il padding è fatto di due parole costanti e l’hash è una sola chiamata KECCAK su uno stato riempito con copie di parole. In termini Ethereum, hash2(a, b, 0) è keccak256(abi.encodePacked(a, b)) per due bytes32.

La foglia e il nullifier non si possono confondere con un nodo dell’albero. Un nodo calcola l’hash di due hash figli di 32 byte. Una foglia calcola l’hash di un segreto e di un tag ASCII fisso, e un nullifier l’hash di un segreto, di un altro tag e del poll id. Perché una foglia passi per un nodo, uno dei suoi figli dovrebbe essere uguale al tag, il che significa trovare una preimmagine di Keccak.

Il percorso viene percorso senza diramazioni sull’indice. La prima versione sceglieva l’ordine delle due metà con uno scambio mascherato, e il compilatore ha trasformato la maschera di nuovo in un salto condizionale: l’esecuzione richiedeva 9 cicli in più per ogni bit 1 dell’indice della foglia. Il numero di cicli in sé non è pubblicato, ma il limite di gas che una chiamata dichiara è arrotondato a partire da esso (sezione 6), quindi un’esecuzione che dipende dall’indice può rivelarne un poco. Scrivere ciascuna metà a un offset calcolato ha risolto il problema: ogni indice di foglia ora esegue gli stessi 3,208 cicli.

4. Il lato host

L’organizzatore e i votanti hanno bisogno dello stesso Keccak che calcola la macchina. allowlist.py è uno script Python senza dipendenze con un proprio Keccak-f[1600] (hashlib.sha3_256 di Python è SHA-3, che applica un padding diverso e produce digest diversi). Svolge due compiti:

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’intero albero, nei termini dello 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"))

In produzione l’organizzatore detiene le foglie, non i segreti, e ogni votante costruisce il proprio witness a partire dalle foglie pubblicate. Lo script accetta un file di segreti perché la demo recita entrambi i ruoli.

La votazione dimostrativa ha profondità 10 (1,024 foglie), poll id 1 e tre scelte. I segreti dei suoi otto membri sono in demo-secrets.txt, un segreto di 64 cifre esadecimali per riga, e sono pubblici di proposito, perché chiunque possa invocare il programma:

$ 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

La prima parola della radice, 4151217614, è 0xf76e8dce: i primi quattro byte della radice ce 8d 6e f7 letti in little-endian.

5. Compilazione ed esecuzione

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

Il membro 5 vota per la scelta 2. Il witness è di 90 parole: 8 per il segreto, l’indice, la scelta e 80 per il percorso.

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

Le cinque parole del nullifier sono quelle che lo script ha calcolato fuori dalla macchina. I casi di errore terminano in modo pulito con uno stato, quindi possono essere dimostrati anch’essi. Lo stesso witness con la prima parola del segreto modificata dà out[0] = 2 e nient’altro, e un membro che chiede la scelta 3 su 3 dà out[0] = 3.

6. Il budget

Ogni livello aggiuntivo di profondità costa una permutazione e circa 270 cicli. Un albero di profondità 20 (un milione di membri) misura 5,866 cicli e 22 permutazioni, che è il tier 14, il più alto che una chiamata possa usare.

Dalla chain 18 una chiamata paga il gas, e una permutazione Keccak è l’istruzione costosa: 192 gas contro 1 per un ciclo ordinario. Il wallet stampa il gas esatto di un’esecuzione e il limite che dichiara per essa:

gas: 5636 (declaring 6144, tier 12)

Ogni riga dell’esecuzione costa 1 gas, e una riga Keccak ne costa 191 in più: 3,344 righe più 12 × 191 fanno 5,636, e due quinti di questo sono i dodici hash. Il wallet conta due righe in più di quante ne contasse rand-guest run. Sulla chain 18 la prova di una chiamata è vincolata alla propria transazione, e il vincolo viaggia come otto parole aggiuntive di segmento pubblico, che aggiungono due righe di digest. Il limite dichiarato, 6,144, è la cifra esatta arrotondata per eccesso a un multiplo di 1,024. Il limite è pubblico e la cifra esatta no.

Una prova che porta con sé la tabella Keccak è grande. Questa è di 3,346,865 byte, contro un limite di 4,194,304 (4 MiB) sulle chain da 18 a 20. Le cifre per la profondità 20 sopra riportate sono misure dell’emulatore, e per questa pagina non è stata generata alcuna prova a quella profondità.

7. Deploy

Il deploy porta con sé il segmento pubblico, quindi la commissione ne conta le 11 parole insieme alle 427 parole di codice: 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’id che deploy stampa, ad2f719f…b970, non è quello che ha stampato rand-guest build. Con un segmento pubblico l’id è blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public), quindi vincola la radice, il poll id e il numero di scelte. Una seconda votazione sugli stessi membri è un secondo deploy dello stesso codice con un poll id diverso, e ottiene un id di programma diverso e nullifier diversi.

Anche hc è scritto in modo diverso: rand-guest stampa ciascuna delle sue otto parole in big-endian e il wallet stampa i byte di ciascuna parola in little-endian, quindi 42087673 è diventato 73760842. È lo stesso digest.

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

Chiunque può rileggere il segmento pubblico. rand_getProgramPublic restituisce le parole come byte little-endian, quindi la radice compare così come è stata stampata:

$ 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. Votare

rand call accetta un --input per ogni parola privata, in decimale. Il sed trasforma il file del witness in quei flag:

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

La ricevuta è ciò che la chain conserva: stato 1, scelta 2 e le cinque parole del nullifier, sotto l’id di programma del sondaggio. h_pub è il digest del segmento pubblico del sondaggio, lo stesso valore che ha stampato program show. h_in è un impegno con sale (salted commitment) sulle 90 parole private e non apre nulla senza il sale.

La chiamata ha richiesto tre minuti su un laptop Apple Silicon, con un picco di 6,1 GB: 29 s per la prova della chiamata, 8 s per l’autorizzazione di spesa e 117 s per il bundle che paga la commissione. La commissione, 0,0062 RAND, è fatta soprattutto di byte. Four programs on chain 20 contiene il calcolo.

La riga della trascrizione. Per impostazione predefinita il wallet sigilla gli input privati in una busta che solo la viewing key del chiamante apre, e la pubblica insieme alla chiamata. È una registrazione per il chiamante, non una divulgazione: nessun altro può aprirla. Chi vota e non vuole alcuna registrazione passa --no-envelope. Dopo di ciò nessuno, nemmeno chi ha votato, potrà mai mostrare quali fossero gli input.

9. Contare i voti

Per contare servono solo la chain:

1. Il sondaggio. Recupera il segmento pubblico del programma e verifica la radice rispetto all’elenco pubblicato delle foglie (ricostruisci l’albero con levels di allowlist.py). Ricostruisci il guest dal sorgente e confronta hc con il code_hash del programma.
2. Le ricevute. Prendi ogni ricevuta il cui program è l’id del sondaggio e il cui output 0 vale 1. Una ricevuta con qualunque altro stato, o con 3735928559 nello slot 7, non è un voto.
3. Il conteggio. Raggruppa per output da 2 a 6. Conta ogni nullifier una sola volta, con la sua prima ricevuta in ordine di chain, e somma il suo output 1 al totale.

Sono state fatte altre tre chiamate per dare qualcosa da fare a chi conta. Il membro 5 ha votato una seconda volta, ora per la scelta 0. Il membro 2 ha votato per la scelta 1. Il membro 3 ha votato per la scelta 0, da un wallet che usava solo l’endpoint RPC pubblico. Questo è il secondo voto del membro 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 chain ha accettato il secondo voto, com’è giusto: la prova è valida. La sua ricevuta riporta le stesse cinque parole di nullifier della prima.

tally.py applica le tre regole. Legge le chiamate del programma dall’explorer e ogni ricevuta dall’RPC pubblico, quindi non servono né un wallet né un nodo:

$ 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

Il ripensamento del membro 5 non è stato conteggiato, e nulla nelle quattro ricevute dice che due di esse provengano dallo stesso membro dell’elenco, se non il nullifier stesso. Il sondaggio è aperto: vota come uno qualsiasi degli otto membri demo e rilancia il conteggio.

Cosa la prova non ti dà

• Un voto per segreto, non un voto per persona. L’organizzatore decide chi riceve una foglia. Un membro che registra due foglie ha due voti.
• Il segreto di chi vota vale quanto la sua casualità. Un segreto derivato da una stringa indovinabile può essere trovato calcolando l’hash dei tentativi e confrontandolo con le foglie pubblicate. Usa 32 byte casuali.
• La scelta è pubblica. Una ricevuta mostra per quale scelta ha votato un nullifier. Nessuno può dire quale membro sia il nullifier, ma un sondaggio con pochi votanti e un’affluenza pubblicata è statistica sui piccoli numeri, non crittografia.
• Tempi e commissioni sono metadati. Il bundle della commissione è shielded e non nomina nessuno, ma un votante che finanzia il proprio wallet e vota un minuto dopo in un’ora tranquilla ha detto qualcosa a un osservatore.
• Il conteggio avviene off chain. La chain conserva le ricevute. Contarle e rifiutare un secondo nullifier spetta a chi le legge.