Una votación anónima

Este programa permite que un miembro de una lista fija emita un voto sin mostrar qué miembro es. La lista es un árbol de Merkle de hashes Keccak-256, construido como se construye una lista de airdrop de Ethereum, de modo que las mismas herramientas la generan. El programa está desplegado en la chain 18, y la última sección lo invoca con miembros de demostración que usted mismo puede utilizar.

Programas de ejemplo contiene la configuración que comparten las cuatro páginas de ejemplo: el checkout de circuits, la wallet y dónde obtener las fuentes.

1. Qué demuestra

Un organizador tiene una lista de miembros. Cada miembro posee un secreto de 32 bytes. El organizador nunca ve los secretos: cada miembro entrega una hoja, keccak256(secret ‖ tag), y el organizador construye un árbol de Merkle sobre las hojas.

Un voto es una sola llamada. Demuestra, sin revelar nada más:

1. que quien llama conoce un secreto cuya hoja está en el árbol;
2. que la opción publicada es una de las opciones permitidas;
3. que el nullifier publicado es keccak256(secret ‖ tag ‖ poll id).

El nullifier es el mismo para todos los votos que un secreto emite en una misma votación, y distinto en cualquier otra votación. Quien cuenta los votos cuenta cada nullifier una sola vez. No se vincula con la hoja: pasar de un nullifier a una hoja requiere el secreto.

La cadena no rechaza un segundo voto. Un programa en Rand no tiene almacenamiento, por lo que no puede recordar un nullifier (Programas). Dos llamadas con el mismo secreto se verifican ambas y ambas dejan un recibo. La regla «un nullifier, un voto» la aplica quien cuenta, sobre los recibos. Cualquiera puede ejecutar el mismo recuento, y eso es lo que hace verificable el resultado.

2. La interfaz

El árbol, la votación y el número de opciones son los mismos para todos los votos, por lo que van en el segmento público, fijado en el despliegue. El id del programa nombra entonces esta votación y ninguna otra.

Un hash de 32 bytes son ocho palabras, y ocho palabras es toda la salida disponible. Publicar 160 bits deja espacio para el estado y la opción. Dos miembros compartirían un nullifier de 160 bits solo por una colisión de hash, que requiere unos 2⁸⁰ intentos para encontrarse.

Orden de bytes. Keccak opera sobre bytes. La syscall KECCAK de la máquina toma el estado como palabras, con el byte i del estado en el byte i mod 4 de la palabra i / 4. Así, 32 bytes se convierten en ocho palabras leyendo cuatro bytes a la vez, en little-endian, y la raíz en el segmento público es simplemente los bytes de la raíz leídos de esa manera.

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

Hay tres cosas en él que vale la pena copiar.

Una permutación por hash. guest_sdk::keccak256 acepta cualquier cadena de bytes, y lo paga con bucles sobre bytes. Aquí cada mensaje mide exactamente 64 bytes, menos que la tasa de 136 bytes, así que el relleno son dos palabras constantes y el hash es una sola llamada a KECCAK sobre un estado llenado mediante copias de palabras. En términos de Ethereum, hash2(a, b, 0) es keccak256(abi.encodePacked(a, b)) para dos bytes32.

La hoja y el nullifier no pueden confundirse con un nodo del árbol. Un nodo aplica el hash a dos hashes hijos de 32 bytes. Una hoja aplica el hash a un secreto y a un tag ASCII fijo, y un nullifier aplica el hash a un secreto, otro tag y el id de la votación. Para que una hoja pase por un nodo, uno de sus hijos tendría que ser igual al tag, lo que implica encontrar una preimagen de Keccak.

La ruta se recorre sin bifurcar según el índice. La primera versión elegía el orden de las dos mitades con un intercambio enmascarado, y el compilador convirtió la máscara de nuevo en una bifurcación: la ejecución tardaba 9 ciclos más por cada bit 1 del índice de la hoja. El número de ciclos en sí no se publica, pero el límite de gas que declara una llamada se redondea a partir de él (sección 6), de modo que una ejecución que dependa del índice puede filtrar un poco del índice. Escribir cada mitad en un desplazamiento calculado lo resolvió: ahora todos los índices de hoja ejecutan los mismos 3,208 ciclos.

4. El lado del host

El organizador y los votantes necesitan el mismo Keccak que calcula la máquina. allowlist.py es un script de Python sin dependencias con su propio Keccak-f[1600] (hashlib.sha3_256 de Python es SHA-3, que rellena de otra manera y da resúmenes distintos). Realiza dos tareas:

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

El árbol completo, en los términos del 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 producción el organizador conserva hojas, no secretos, y cada votante construye su propio testigo a partir de las hojas publicadas. El script toma un archivo de secretos porque la demostración desempeña ambos papeles.

La votación de demostración tiene profundidad 10 (1,024 hojas), id de votación 1 y tres opciones. Los secretos de sus ocho miembros están en demo-secrets.txt, un secreto de 64 hex por línea, y son públicos a propósito para que cualquiera pueda invocar el 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

La primera palabra de la raíz, 4151217614, es 0xf76e8dce: los primeros cuatro bytes de la raíz ce 8d 6e f7 leídos en little-endian.

5. Compilar y ejecutar

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

El miembro 5 vota por la opción 2. El testigo tiene 90 palabras: 8 del secreto, el índice, la opción y 80 de la ruta.

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

Las cinco palabras del nullifier son las que el script calculó fuera de la máquina. Los fallos se detienen limpiamente con un estado, de modo que también pueden demostrarse. El mismo testigo con la primera palabra del secreto cambiada da out[0] = 2 y nada más, y un miembro que pide la opción 3 de 3 da out[0] = 3.

6. El presupuesto

Cada nivel adicional de profundidad cuesta una permutación y unos 270 ciclos. Un árbol de profundidad 20 (un millón de miembros) mide 5,866 ciclos y 22 permutaciones, que es el nivel 14, el más alto que puede usar una llamada.

Desde la chain 18 una llamada paga gas, y una permutación de Keccak es la instrucción costosa: 192 de gas frente a 1 de un ciclo ordinario. La wallet imprime el gas exacto de una ejecución y el límite que declara para ella:

gas: 5636 (declaring 6144, tier 12)

Cada fila de la ejecución cuesta 1 de gas, y una fila de Keccak cuesta 191 más: 3,344 filas más 12 × 191 son 5,636, y dos quintas partes de esa cifra corresponden a los doce hashes. La wallet cuenta dos filas más que rand-guest run. En la chain 18 una prueba de llamada queda vinculada a su transacción, y ese vínculo viaja como ocho palabras adicionales de segmento público, lo que añade dos filas de resumen. El límite declarado, 6,144, es la cifra exacta redondeada hacia arriba a un múltiplo de 1,024. El límite es público y la cifra exacta no.

Una prueba que incluye la tabla de Keccak es grande. Esta mide 3,346,865 bytes, frente a un tope de 4,194,304 (4 MiB) en las chains 18 a 20. Las cifras de profundidad 20 anteriores son mediciones del emulador, y no se generó ninguna prueba con esa profundidad para esta página.

7. Despliegue

El despliegue lleva el segmento público, así que la comisión cuenta sus 11 palabras junto con las 427 palabras 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)

El id que imprime deploy, ad2f719f…b970, no es el que imprimió rand-guest build. Con un segmento público el id es blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public), de modo que vincula la raíz, el id de la votación y el número de opciones. Una segunda votación sobre los mismos miembros es un segundo despliegue del mismo código con un id de votación distinto, y obtiene un id de programa distinto y nullifiers distintos.

hc también se escribe de otra manera: rand-guest imprime cada una de sus ocho palabras en big-endian y la wallet imprime los bytes de cada palabra en little-endian, así que 42087673 pasó a ser 73760842. Es el mismo resumen.

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

Cualquiera puede leer de vuelta el segmento público. rand_getProgramPublic devuelve las palabras como bytes little-endian, de modo que la raíz aparece tal como se imprimió:

$ 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 toma un --input por cada palabra privada, en decimal. El sed convierte el archivo de testigo en esos 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`

El recibo es lo que la cadena conserva: estado 1, opción 2 y las cinco palabras del nullifier, bajo el id de programa de la votación. h_pub es el digest del segmento público de la votación, el mismo valor que mostró program show. h_in es un compromiso con sal de las 90 palabras privadas, y no abre nada sin la sal.

La llamada tardó tres minutos en un portátil con Apple Silicon y alcanzó un pico de 6,1 GB: 29 s para la prueba de la llamada, 8 s para la autorización de gasto y 117 s para el paquete que paga la comisión. La comisión, 0,0062 RAND, es sobre todo bytes. Four programs on chain 20 contiene la aritmética.

La línea de transcripción. Por defecto, la wallet sella las entradas privadas en un sobre que solo abre la viewing key del llamante, y lo publica junto con la llamada. Es un registro para el llamante, no una divulgación: nadie más puede abrirlo. Un votante que no quiera ningún registro pasa --no-envelope. A partir de entonces nadie, ni siquiera el votante, podrá demostrar cuáles fueron las entradas.

9. Contar los votos

Un contador no necesita nada más que la cadena:

1. La votación. Obtenga el segmento público del programa y compruebe la raíz contra la lista publicada de hojas (reconstruya el árbol con levels de allowlist.py). Reconstruya el guest desde el código fuente y compare hc con el code_hash del programa.
2. Los recibos. Tome cada recibo cuyo program sea el id de la votación y cuya salida 0 sea 1. Un recibo con cualquier otro estado, o con 3735928559 en la ranura 7, no es un voto.
3. El recuento. Agrupe por las salidas 2 a 6. Cuente cada nullifier una sola vez, con su primer recibo en el orden de la cadena, y sume su salida 1 al total.

Se hicieron tres llamadas más para dar algo que hacer al contador. El miembro 5 votó por segunda vez, ahora por la opción 0. El miembro 2 votó por la opción 1. El miembro 3 votó por la opción 0, desde una wallet que usó solo el endpoint RPC público. Este es el segundo voto del miembro 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 cadena aceptó el segundo voto, como debe ser: la prueba es válida. Su recibo lleva las mismas cinco palabras de nullifier que el primero.

tally.py aplica las tres reglas. Lee las llamadas del programa desde el explorador y cada recibo desde el RPC público, de modo que no necesita wallet ni 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

El cambio de opinión del miembro 5 no contó, y nada en los cuatro recibos indica que dos de ellos provienen del mismo miembro de la lista, salvo el propio nullifier. La votación está abierta: vote como cualquiera de los ocho miembros de demostración y ejecute de nuevo el recuento.

Lo que la prueba no le da

• Un voto por secreto, no un voto por persona. El organizador decide quién recibe una hoja. Un miembro que registra dos hojas tiene dos votos.
• El secreto del votante vale tanto como su aleatoriedad. Un secreto derivado de una cadena adivinable puede descubrirse calculando hashes de suposiciones y comparándolos con las hojas publicadas. Use 32 bytes aleatorios.
• La opción es pública. Un recibo muestra por qué opción votó un nullifier. Nadie puede saber qué miembro es el nullifier, pero una votación con pocos votantes y una participación publicada es estadística de números pequeños, no criptografía.
• El momento y las comisiones son metadatos. El paquete de la comisión es shielded y no nombra a nadie, pero un votante que financia su wallet y vota un minuto después en una hora tranquila le ha dicho algo a un observador.
• El recuento se hace fuera de la cadena. La cadena almacena recibos. Contarlos y rechazar un segundo nullifier corre por cuenta de quien los lea.