Uma votação anônima

Este programa permite que um membro de uma lista fixa registre um voto sem mostrar qual membro é. A lista é uma árvore de Merkle de hashes Keccak-256, construída do mesmo modo que uma lista de airdrop da Ethereum, de modo que as mesmas ferramentas a produzem. O programa está implantado na chain 18, e a última seção o chama com membros de demonstração que você mesmo pode usar.

Example programs traz a configuração comum às quatro páginas de exemplo: o checkout dos circuitos, a carteira e onde obter o código-fonte.

1. O que ele prova

Um organizador tem uma lista de membros. Cada membro guarda um segredo de 32 bytes. O organizador nunca vê os segredos: cada membro entrega uma folha, keccak256(secret ‖ tag), e o organizador constrói uma árvore de Merkle sobre as folhas.

Um voto é uma única chamada. Ela prova, sem revelar mais nada:

1. quem chama conhece um segredo cuja folha está na árvore;
2. a escolha publicada é uma das escolhas permitidas;
3. o nullifier publicado é keccak256(secret ‖ tag ‖ poll id).

O nullifier é o mesmo para todo voto que um segredo registra em uma mesma votação, e é diferente em qualquer outra votação. Quem apura os votos conta cada nullifier uma só vez. Ele não se liga à folha: para ir de um nullifier de volta a uma folha é preciso o segredo.

A chain não rejeita um segundo voto. Um programa na Rand não tem armazenamento, de modo que não pode lembrar um nullifier (Programs). Duas chamadas com o mesmo segredo são ambas verificadas e ambas deixam um recibo. A regra “um nullifier, um voto” é aplicada por quem apura, sobre os recibos. Qualquer pessoa pode executar a mesma contagem, e é isso que torna a apuração verificável.

2. A interface

A árvore, a votação e o número de escolhas são os mesmos em todo voto, por isso ficam no segmento público, fixado na implantação. O id do programa passa então a nomear esta votação e nenhuma outra.

Um hash de 32 bytes são oito palavras, e oito palavras é toda a saída disponível. Publicar 160 bits deixa espaço para o status e a escolha. Dois membros só compartilhariam um nullifier de 160 bits por uma colisão de hash, que exige cerca de 2⁸⁰ tentativas para ser encontrada.

Ordem dos bytes. O Keccak trabalha com bytes. A syscall KECCAK da máquina recebe o estado como palavras, com o byte i do estado no byte i mod 4 da palavra i / 4. Assim, 32 bytes viram oito palavras lendo quatro bytes por vez, em little-endian, e a raiz no segmento público é apenas os bytes da raiz lidos dessa forma.

3. O 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();
}

Três coisas nele merecem ser copiadas.

Uma permutação por hash. guest_sdk::keccak256 aceita qualquer cadeia de bytes e paga por isso com laços sobre bytes. Aqui toda mensagem tem exatamente 64 bytes, menos que a taxa de 136 bytes, de modo que o preenchimento são duas palavras constantes e o hash é uma única chamada KECCAK sobre um estado preenchido por cópias de palavras. Em termos de Ethereum, hash2(a, b, 0) é keccak256(abi.encodePacked(a, b)) para dois bytes32.

A folha e o nullifier não podem ser confundidos com um nó da árvore. Um nó faz o hash de dois hashes filhos de 32 bytes. Uma folha faz o hash de um segredo e de uma tag ASCII fixa, e um nullifier faz o hash de um segredo, de outra tag e do id da votação. Para que uma folha passasse por nó, um de seus filhos teria de ser igual à tag, o que significa encontrar uma pré-imagem do Keccak.

O caminho é percorrido sem ramificar pelo índice. A primeira versão escolhia a ordem das duas metades com uma troca mascarada, e o compilador transformou a máscara de volta em um desvio: a execução levava 9 ciclos a mais para cada bit 1 no índice da folha. A contagem de ciclos em si não é publicada, mas o limite de gas que uma chamada declara é arredondado a partir dela (seção 6), de modo que uma execução que dependa do índice pode vazar um pouco do índice. Escrever cada metade em um deslocamento calculado resolveu o problema: agora todo índice de folha executa os mesmos 3.208 ciclos.

4. O lado do host

O organizador e os eleitores precisam do mesmo Keccak que a máquina calcula. allowlist.py é um script Python sem dependências, com seu próprio Keccak-f[1600] (o hashlib.sha3_256 do Python é SHA-3, que faz o preenchimento de outro modo e dá resumos diferentes). Ele faz dois trabalhos:

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

A árvore inteira, nos termos do 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"))

Em produção, o organizador guarda folhas, não segredos, e cada eleitor monta sua própria testemunha a partir das folhas publicadas. O script recebe um arquivo de segredos porque a demonstração faz os dois papéis.

A votação de demonstração tem profundidade 10 (1.024 folhas), id de votação 1 e três escolhas. Os segredos de seus oito membros estão em demo-secrets.txt, um segredo de 64 dígitos hexadecimais por linha, e são públicos de propósito para que qualquer pessoa possa chamar o programa:

$ 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

A primeira palavra da raiz, 4151217614, é 0xf76e8dce: os primeiros quatro bytes da raiz, ce 8d 6e f7, lidos em little-endian.

5. Compilar e executar

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

O membro 5 vota na escolha 2. A testemunha tem 90 palavras: 8 para o segredo, o índice, a escolha e 80 para o caminho.

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

As cinco palavras do nullifier são as que o script calculou fora da máquina. As falhas terminam de forma limpa, com um status, de modo que também podem ser provadas. A mesma testemunha com a primeira palavra do segredo alterada resulta em out[0] = 2 e nada mais, e um membro que peça a escolha 3 de 3 resulta em out[0] = 3.

6. O orçamento

Cada nível extra de profundidade custa uma permutação e cerca de 270 ciclos. Uma árvore de profundidade 20 (um milhão de membros) mede 5.866 ciclos e 22 permutações, o que é o tier 14, o mais alto que uma chamada pode usar.

Desde a chain 18, uma chamada paga gas, e uma permutação Keccak é a instrução cara: 192 de gas contra 1 de um ciclo comum. A carteira imprime o gas exato de uma execução e o limite que declara para ela:

gas: 5636 (declaring 6144, tier 12)

Cada linha da execução custa 1 de gas, e uma linha de Keccak custa 191 a mais: 3.344 linhas mais 12 × 191 dá 5.636, e dois quintos disso são os doze hashes. A carteira conta duas linhas a mais do que rand-guest run contou. Na chain 18, a prova de uma chamada é vinculada à sua transação, e o vínculo viaja como oito palavras extras de segmento público, o que acrescenta duas linhas de digest. O limite declarado, 6.144, é o valor exato arredondado para cima até um múltiplo de 1.024. O limite é público e o valor exato não é.

Uma prova que carrega a tabela de Keccak é grande. Esta tem 3.346.865 bytes, contra um limite de 4.194.304 (4 MiB) nas chains 18 a 20. Os números de profundidade 20 acima são medições do emulador, e nenhuma prova foi feita nessa profundidade para esta página.

7. Implantar

A implantação carrega o segmento público, de modo que a taxa conta suas 11 palavras junto com as 427 palavras de código: 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)

O id que deploy imprime, ad2f719f…b970, não é o que rand-guest build imprimiu. Com um segmento público, o id é blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public), de modo que vincula a raiz, o id da votação e o número de escolhas. Uma segunda votação sobre os mesmos membros é uma segunda implantação do mesmo código com outro id de votação, e recebe outro id de programa e outros nullifiers.

hc também é escrito de outra forma: rand-guest imprime cada uma de suas oito palavras em big-endian e a carteira imprime os bytes de cada palavra em little-endian, de modo que 42087673 virou 73760842. É o mesmo 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
}

Qualquer pessoa pode ler o segmento público de volta. rand_getProgramPublic devolve as palavras como bytes little-endian, de modo que a raiz aparece como foi impressa:

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

rand call recebe um --input por palavra privada, em decimal. O sed transforma o arquivo de testemunha nesses flags:

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

O recibo é o que a cadeia guarda: status 1, escolha 2 e as cinco palavras de nullifier, sob o id de programa da votação. h_pub é o digest do segmento público da votação, o mesmo valor que program show imprimiu. h_in é um compromisso com sal sobre as 90 palavras privadas, e não abre nada sem o sal.

A chamada levou três minutos em um laptop Apple Silicon e atingiu o pico de 6,1 GB: 29 s para a prova da chamada, 8 s para a autorização de gasto e 117 s para o pacote que paga a taxa. A taxa, 0,0062 RAND, é composta sobretudo de bytes. Four programs on chain 20 traz a aritmética.

A linha da transcrição. Por padrão, a carteira sela as entradas privadas em um envelope que só a chave de visualização do chamador abre, e o publica junto com a chamada. Isso é um registro para o chamador, não uma divulgação: ninguém mais consegue abri-lo. Um eleitor que não quer nenhum registro passa --no-envelope. Depois disso, ninguém, nem mesmo o eleitor, poderá jamais demonstrar quais eram as entradas.

9. Contar os votos

Quem conta não precisa de nada além da cadeia:

1. A votação. Busque o segmento público do programa e confira a raiz com a lista publicada de folhas (reconstrua a árvore com levels, de allowlist.py). Reconstrua o guest a partir do código-fonte e compare hc com o code_hash do programa.
2. Os recibos. Tome todo recibo cujo program seja o id da votação e cuja saída 0 seja 1. Um recibo com qualquer outro status, ou com 3735928559 no slot 7, não é um voto.
3. A contagem. Agrupe pelas saídas 2 a 6. Conte cada nullifier uma só vez, pelo seu primeiro recibo na ordem da cadeia, e some a saída 1 dele ao total.

Três chamadas a mais foram feitas para dar ao contador o que fazer. O membro 5 votou uma segunda vez, agora na escolha 0. O membro 2 votou na escolha 1. O membro 3 votou na escolha 0, a partir de uma carteira que usou apenas o endpoint RPC público. Este é o segundo voto do 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

A cadeia aceitou o segundo voto, como deve: a prova é válida. O recibo dele traz as mesmas cinco palavras de nullifier que o primeiro.

tally.py aplica as três regras. Ele lê as chamadas do programa no explorador e cada recibo no RPC público, de modo que não precisa de carteira nem de nó:

$ 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

A mudança de ideia do membro 5 não contou, e nada nos quatro recibos indica que dois deles vieram do mesmo membro da lista, a não ser o próprio nullifier. A votação está aberta: vote como qualquer um dos oito membros de demonstração e execute a contagem de novo.

O que a prova não oferece

• Um voto por segredo, não um voto por pessoa. O organizador decide quem recebe uma folha. Um membro que registra duas folhas tem dois votos.
• O segredo do eleitor vale tanto quanto a sua aleatoriedade. Um segredo derivado de uma string previsível pode ser descoberto calculando o hash de tentativas e comparando com as folhas publicadas. Use 32 bytes aleatórios.
• A escolha é pública. Um recibo mostra em qual escolha um nullifier votou. Ninguém consegue dizer a qual membro o nullifier corresponde, mas uma votação com poucos eleitores e participação publicada é estatística de números pequenos, não criptografia.
• Horário e taxas são metadados. O pacote da taxa é shielded e não nomeia ninguém, mas um eleitor que financia a carteira e vota um minuto depois, em um horário de pouco movimento, disse algo a quem observa.
• A contagem é feita fora da cadeia. A cadeia armazena recibos. Contá-los e recusar um segundo nullifier cabe a quem os lê.