Anonimowe głosowanie

Ten program pozwala członkowi ustalonej listy oddać jeden głos bez ujawniania, którym członkiem jest. Lista jest drzewem Merkle’a z hashy Keccak-256, zbudowanym tak, jak buduje się listy airdropów na Ethereum, więc to samo narzędzie je tworzy. Program jest wdrożony w łańcuchu 18, a ostatnia sekcja wywołuje go z użyciem demonstracyjnych członków, z których można skorzystać samodzielnie.

Programy przykładowe zawierają konfigurację wspólną dla wszystkich czterech stron z przykładami: checkout circuits, portfel oraz miejsce, skąd pobrać źródła.

1. Co dowodzi

Organizator ma listę członków. Każdy członek posiada 32-bajtowy sekret. Organizator nigdy nie widzi sekretów: każdy członek przekazuje liść (leaf), keccak256(secret ‖ tag), a organizator buduje drzewo Merkle’a nad liśćmi.

Głos to jedno wywołanie. Dowodzi ono, niczego poza tym nie ujawniając, że:

1. wywołujący zna sekret, którego liść znajduje się w drzewie;
2. opublikowany wybór jest jednym z dozwolonych wyborów;
3. opublikowany nullifier to keccak256(secret ‖ tag ‖ poll id).

Nullifier jest taki sam dla każdego głosu oddanego jednym sekretem w jednym głosowaniu i inny w każdym innym głosowaniu. Kto liczy głosy, liczy każdy nullifier raz. Nullifier nie wiąże się z liściem: przejście od nullifiera z powrotem do liścia wymaga sekretu.

Łańcuch nie odrzuca drugiego głosu. Program w Rand nie ma pamięci trwałej, więc nie może zapamiętać nullifiera (Programy). Dwa wywołania z tym samym sekretem obydwa przechodzą weryfikację i obydwa zostawiają potwierdzenie. Zasadę „jeden nullifier, jeden głos” stosuje liczący, na podstawie potwierdzeń. Każdy może przeprowadzić to samo liczenie, dzięki czemu wynik można sprawdzić.

2. Interfejs

Drzewo, głosowanie i liczba wyborów są takie same dla każdego głosu, więc trafiają do segmentu publicznego, ustalanego przy wdrożeniu. Identyfikator programu wskazuje wtedy to głosowanie i żadne inne.

32-bajtowy hash to osiem słów, a osiem słów to całe wyjście. Opublikowanie 160 bitów zostawia miejsce na status i wybór. Dwaj członkowie mieliby wspólny 160-bitowy nullifier tylko przez kolizję hasha, a jej znalezienie wymaga około 2⁸⁰ prób.

Kolejność bajtów. Keccak działa na bajtach. Syscall KECCAK maszyny przyjmuje stan jako słowa, z bajtem i stanu w bajcie i mod 4 słowa i / 4. Zatem 32 bajty stają się ośmioma słowami przez czytanie po cztery bajty, w kolejności little-endian, a korzeń w segmencie publicznym to po prostu bajty korzenia odczytane w ten sposób.

3. Gość (guest)

my-guests/allowlist/src/main.rs, w całości:

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

Trzy rzeczy w nim warto skopiować.

Jedna permutacja na hash. guest_sdk::keccak256 przyjmuje dowolny ciąg bajtów i płaci za to pętlami po bajtach. Każda wiadomość ma tu dokładnie 64 bajty, mniej niż 136-bajtowy rate, więc padding to dwa stałe słowa, a hash to jedno wywołanie KECCAK na stanie wypełnionym kopiowaniem słów. W terminach Ethereum hash2(a, b, 0) to keccak256(abi.encodePacked(a, b)) dla dwóch bytes32.

Liścia i nullifiera nie da się pomylić z węzłem drzewa. Węzeł hashuje dwa 32-bajtowe hashe potomne. Liść hashuje sekret i stały tag ASCII, a nullifier hashuje sekret, inny tag i identyfikator głosowania. Aby liść uchodził za węzeł, jedno z jego dzieci musiałoby być równe tagowi, a to oznacza znalezienie przeciwobrazu Keccaka.

Ścieżka jest przechodzona bez rozgałęzień zależnych od indeksu. Pierwsza wersja wybierała kolejność dwóch połówek za pomocą zamiany z maską, a kompilator zamienił maskę z powrotem w rozgałęzienie: przebieg trwał o 9 cykli dłużej dla każdego bitu 1 w indeksie liścia. Sama liczba cykli nie jest publikowana, ale limit gas deklarowany przez wywołanie jest z niej zaokrąglany (sekcja 6), więc przebieg zależny od indeksu może ujawnić drobną część indeksu. Naprawiło to zapisywanie każdej połówki pod obliczonym offsetem: każdy indeks liścia wykonuje się teraz w tych samych 3 208 cyklach.

4. Strona hosta

Organizator i wyborcy potrzebują tego samego Keccaka, który liczy maszyna. allowlist.py to skrypt w Pythonie bez zależności, z własnym Keccak-f[1600] (hashlib.sha3_256 w Pythonie to SHA-3, który dopełnia inaczej i daje inne skróty). Wykonuje dwa zadania:

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

Całe drzewo, w terminach skryptu:

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

W produkcji organizator trzyma liście, a nie sekrety, i każdy wyborca buduje własnego świadka (witness) z opublikowanych liści. Skrypt przyjmuje plik z sekretami, ponieważ demo odgrywa obie role.

Demonstracyjne głosowanie ma głębokość 10 (1 024 liści), identyfikator głosowania 1 i trzy wybory. Sekrety jego ośmiu członków znajdują się w demo-secrets.txt, po jednym 64-znakowym sekrecie hex w wierszu, i są publiczne celowo, aby każdy mógł wywołać program:

$ 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

Pierwsze słowo korzenia, 4151217614, to 0xf76e8dce: pierwsze cztery bajty korzenia ce 8d 6e f7 odczytane w kolejności little-endian.

5. Budowanie i uruchomienie

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

Członek 5 głosuje na wybór 2. Świadek ma 90 słów: 8 na sekret, indeks, wybór i 80 na ścieżkę.

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

Pięć słów nullifiera to te, które skrypt obliczył poza maszyną. Błędy kończą się czystym zatrzymaniem ze statusem, więc można je również udowodnić. Ten sam świadek ze zmienionym pierwszym słowem sekretu daje out[0] = 2 i nic więcej, a członek żądający wyboru 3 z 3 daje out[0] = 3.

6. Budżet

Każdy dodatkowy poziom głębokości kosztuje jedną permutację i około 270 cykli. Drzewo o głębokości 20 (milion członków) mierzy 5 866 cykli i 22 permutacje, co daje poziom 14, najwyższy, jakiego wywołanie może użyć.

Od łańcucha 18 wywołanie płaci za gas, a permutacja Keccak jest instrukcją kosztowną: 192 gas wobec 1 dla zwykłego cyklu. Portfel wypisuje dokładny gas przebiegu i limit, który dla niego deklaruje:

gas: 5636 (declaring 6144, tier 12)

Każdy wiersz przebiegu kosztuje 1 gas, a wiersz Keccak kosztuje 191 więcej: 3 344 wiersze plus 12 × 191 to 5 636, a dwie piąte tej sumy to dwanaście hashów. Portfel liczy o dwa wiersze więcej niż rand-guest run. W łańcuchu 18 dowód wywołania jest powiązany ze swoją transakcją, a powiązanie podróżuje jako osiem dodatkowych słów segmentu publicznego, co dodaje dwa wiersze skrótów. Zadeklarowany limit, 6 144, to dokładna wartość zaokrąglona w górę do wielokrotności 1 024. Limit jest publiczny, a dokładna wartość nie.

Dowód zawierający tabelę Keccak jest duży. Ten ma 3 346 865 bajtów, przy limicie 4 194 304 (4 MiB) w łańcuchach od 18 do 20. Wartości dla głębokości 20 podane powyżej to pomiary emulatora i dla tej strony nie wykonano dowodu przy takiej głębokości.

7. Wdrożenie

Wdrożenie zawiera segment publiczny, więc opłata obejmuje jego 11 słów wraz z 427 słowami kodu: 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)

Identyfikator wypisany przez deploy, ad2f719f…b970, nie jest tym, który wypisał rand-guest build. Przy segmencie publicznym identyfikator to blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public), więc wiąże korzeń, identyfikator głosowania i liczbę wyborów. Drugie głosowanie nad tymi samymi członkami to drugie wdrożenie tego samego kodu z innym identyfikatorem głosowania, które otrzymuje inny identyfikator programu i inne nullifiery.

hc jest również zapisany inaczej: rand-guest wypisuje każde ze swoich ośmiu słów w kolejności big-endian, a portfel wypisuje bajty każdego słowa w kolejności little-endian, więc 42087673 stało się 73760842. To ten sam skrót.

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

Każdy może odczytać segment publiczny z powrotem. rand_getProgramPublic zwraca słowa jako bajty little-endian, więc korzeń pojawia się tak, jak został wypisany:

$ 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. Głosowanie

rand call przyjmuje jedno --input na każde słowo prywatne, w zapisie dziesiętnym. sed zamienia plik świadka na te flagi:

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

Paragon to to, co łańcuch przechowuje: status 1, wybór 2 oraz pięć słów nullifiera, pod identyfikatorem programu głosowania. h_pub to skrót segmentu publicznego głosowania, ta sama wartość, którą wypisało program show. h_in to solone zobowiązanie do 90 słów prywatnych i bez soli niczego nie ujawnia.

Wywołanie trwało trzy minuty na laptopie z Apple Silicon i osiągnęło szczyt 6,1 GB: 29 s na dowód wywołania, 8 s na autoryzację wydatku i 117 s na pakiet, który płaci opłatę. Opłata, 0,0062 RAND, to głównie bajty. Rachunek znajdziesz w Four programs on chain 20.

Wiersz transkrypcji. Domyślnie portfel zapieczętowuje prywatne wejścia w kopercie, którą otwiera tylko klucz podglądu wywołującego, i publikuje ją razem z wywołaniem. To zapis dla wywołującego, a nie ujawnienie: nikt inny nie może jej otworzyć. Głosujący, który nie chce żadnego zapisu, podaje --no-envelope. Potem nikt, łącznie z głosującym, nie może już nigdy wykazać, jakie były te wejścia.

9. Policz głosy

Osoba liczącą głosy potrzebuje tylko łańcucha:

1. Głosowanie. Pobierz segment publiczny programu i sprawdź korzeń względem opublikowanej listy liści (odbuduj drzewo za pomocą levels z allowlist.py). Odbuduj gościa ze źródeł i porównaj hc z code_hash programu.
2. Paragony. Weź każdy paragon, którego program jest identyfikatorem głosowania, a wyjście 0 wynosi 1. Paragon z innym statusem albo z 3735928559 w slocie 7 nie jest głosem.
3. Wynik. Pogrupuj według wyjść od 2 do 6. Każdy nullifier policz raz, według pierwszego paragonu w kolejności łańcucha, i dodaj jego wyjście 1 do wyniku.

Wykonano jeszcze trzy wywołania, żeby osoba licząca miała co robić. Członek 5 zagłosował drugi raz, tym razem na wybór 0. Członek 2 zagłosował na wybór 1. Członek 3 zagłosował na wybór 0, z portfela, który korzystał wyłącznie z publicznego punktu końcowego RPC. Oto drugi głos członka 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ńcuch przyjął drugi głos, tak jak powinien: dowód jest poprawny. Jego paragon zawiera te same pięć słów nullifiera co pierwszy.

tally.py stosuje te trzy reguły. Czyta wywołania programu z eksploratora, a każdy paragon z publicznego RPC, więc nie potrzebuje ani portfela, ani węzła:

$ 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

Zmiana zdania członka 5 nie została policzona, a nic w czterech paragonach nie mówi, że dwa z nich pochodzą od tego samego członka listy, poza samym nullifierem. Głosowanie jest otwarte: zagłosuj jako dowolny z ośmiu członków demonstracyjnych i uruchom liczenie ponownie.

Czego dowód nie daje

• Jeden głos na sekret, a nie jeden głos na osobę. Organizator decyduje, kto dostaje liść. Członek, który zarejestruje dwa liście, ma dwa głosy.
• Sekret głosującego jest tak dobry, jak jego losowość. Sekret wyprowadzony z łatwego do odgadnięcia ciągu można znaleźć, haszując przypuszczenia i porównując je z opublikowanymi liśćmi. Użyj 32 losowych bajtów.
• Wybór jest publiczny. Paragon pokazuje, na jaki wybór zagłosował dany nullifier. Nikt nie może stwierdzić, którym członkiem jest ten nullifier, ale głosowanie z niewielką liczbą głosujących i opublikowaną frekwencją to statystyka małych liczb, a nie kryptografia.
• Czas i opłaty to metadane. Pakiet opłaty jest zashieldowany i nikogo nie wskazuje, ale głosujący, który zasila portfel i głosuje minutę później w spokojnej godzinie, coś zdradził obserwatorowi.
• Wynik jest liczony poza łańcuchem. Łańcuch przechowuje paragony. Policzenie ich i odrzucenie drugiego nullifiera należy do tego, kto je czyta.