Suara anonim

Program ini memungkinkan anggota dari sebuah daftar tetap memberikan satu suara tanpa menunjukkan anggota yang mana dirinya. Daftar tersebut adalah pohon Merkle dari hash Keccak-256, dibangun dengan cara yang sama seperti daftar airdrop Ethereum, sehingga perangkat yang sama dapat membuatnya. Program ini telah di-deploy di chain 18, dan bagian terakhir memanggilnya dengan anggota demo yang dapat Anda gunakan sendiri.

Program contoh memuat persiapan yang sama untuk keempat halaman contoh: checkout circuits, wallet, dan tempat memperoleh sumbernya.

1. Apa yang dibuktikan

Seorang penyelenggara memiliki daftar anggota. Setiap anggota memegang secret sebesar 32 byte. Penyelenggara tidak pernah melihat secret tersebut: setiap anggota menyerahkan sebuah daun (leaf), keccak256(secret ‖ tag), dan penyelenggara membangun pohon Merkle di atas daun-daun itu.

Satu suara adalah satu panggilan. Panggilan itu membuktikan, tanpa mengungkap hal lain:

1. pemanggil mengetahui sebuah secret yang daunnya ada di dalam pohon;
2. pilihan yang dipublikasikan adalah salah satu pilihan yang diizinkan;
3. nullifier yang dipublikasikan adalah keccak256(secret ‖ tag ‖ poll id).

Nullifier bernilai sama untuk setiap suara yang diberikan satu secret dalam satu poll, dan berbeda di setiap poll lain. Pihak yang menghitung suara menghitung setiap nullifier satu kali. Nullifier tidak terhubung ke daun: untuk berpindah dari nullifier kembali ke daun diperlukan secret.

Chain tidak menolak suara kedua. Program di Rand tidak memiliki storage, sehingga tidak dapat mengingat nullifier (Program). Dua panggilan dengan secret yang sama keduanya terverifikasi dan keduanya meninggalkan receipt. Aturan “satu nullifier, satu suara” diterapkan oleh penghitung, atas receipt-receipt tersebut. Siapa pun dapat menjalankan penghitungan yang sama, dan inilah yang membuat hasil penghitungan dapat diperiksa.

2. Antarmuka

Pohon, poll, dan jumlah pilihan sama untuk setiap suara, sehingga semuanya ditempatkan di segmen publik (public segment), yang ditetapkan saat deploy. Dengan demikian, id program hanya menamai poll ini dan tidak yang lain.

Hash 32 byte adalah delapan word, dan delapan word adalah seluruh output yang tersedia. Mempublikasikan 160 bit menyisakan ruang untuk status dan pilihan. Dua anggota hanya akan memiliki nullifier 160 bit yang sama melalui tabrakan hash, yang membutuhkan sekitar 2⁸⁰ percobaan untuk ditemukan.

Urutan byte. Keccak bekerja pada byte. Syscall KECCAK pada mesin menerima state sebagai word, dengan byte i dari state berada di byte i mod 4 dari word i / 4. Jadi 32 byte menjadi delapan word dengan membaca empat byte sekaligus, secara little-endian, dan root di segmen publik hanyalah byte-byte root yang dibaca dengan cara itu.

3. Guest

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

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

Tiga hal di dalamnya patut ditiru.

Satu permutasi per hash. guest_sdk::keccak256 menerima byte string apa pun, dan harganya adalah loop byte. Setiap pesan di sini tepat 64 byte, kurang dari rate 136 byte, sehingga padding-nya berupa dua word konstan dan hash-nya adalah satu panggilan KECCAK pada state yang diisi dengan salinan word. Dalam istilah Ethereum, hash2(a, b, 0) adalah keccak256(abi.encodePacked(a, b)) untuk dua bytes32.

Daun dan nullifier tidak dapat tertukar dengan node pohon. Sebuah node meng-hash dua hash anak sebesar 32 byte. Sebuah daun meng-hash secret dan tag ASCII tetap, dan sebuah nullifier meng-hash secret, tag lain, dan poll id. Agar sebuah daun dapat lolos sebagai node, salah satu anaknya harus sama dengan tag, yang berarti harus menemukan preimage Keccak.

Jalur ditelusuri tanpa percabangan pada indeks. Versi pertama memilih urutan dua separuh dengan masked swap, dan compiler mengubah mask itu kembali menjadi percabangan: proses berjalan 9 siklus lebih banyak untuk setiap bit 1 pada indeks daun. Jumlah siklus itu sendiri tidak dipublikasikan, tetapi batas gas yang dideklarasikan sebuah panggilan dibulatkan darinya (bagian 6), sehingga proses yang bergantung pada indeks dapat membocorkan sedikit dari indeks tersebut. Menulis setiap separuh pada offset yang dihitung memperbaikinya: setiap indeks daun kini berjalan dengan 3.208 siklus yang sama.

4. Sisi host

Penyelenggara dan pemilih memerlukan Keccak yang sama dengan yang dihitung mesin. allowlist.py adalah skrip Python tanpa dependensi dengan Keccak-f[1600] sendiri (hashlib.sha3_256 pada Python adalah SHA-3, yang menggunakan padding berbeda dan menghasilkan digest berbeda). Skrip ini mengerjakan dua tugas:

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

Seluruh pohon, dalam istilah skrip:

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

Dalam produksi, penyelenggara memegang daun, bukan secret, dan setiap pemilih membangun witness-nya sendiri dari daun-daun yang dipublikasikan. Skrip ini menerima berkas secret karena demo memerankan kedua peran.

Poll demo memiliki kedalaman 10 (1.024 daun), poll id 1, dan tiga pilihan. Secret kedelapan anggotanya ada di demo-secrets.txt, satu secret 64-hex per baris, dan sengaja dipublikasikan agar siapa pun dapat memanggil 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

Word root pertama, 4151217614, adalah 0xf76e8dce: empat byte pertama root ce 8d 6e f7 yang dibaca secara little-endian.

5. Build dan jalankan

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

Anggota 5 memilih pilihan 2. Witness-nya terdiri dari 90 word: 8 untuk secret, indeks, pilihan, dan 80 untuk jalur.

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

Kelima word nullifier sama dengan yang dihitung skrip di luar mesin. Kegagalan berhenti dengan bersih beserta status, sehingga dapat dibuktikan juga. Witness yang sama dengan word pertama secret diubah menghasilkan out[0] = 2 dan tidak ada yang lain, dan anggota yang meminta pilihan 3 dari 3 menghasilkan out[0] = 3.

6. Anggaran

Setiap tambahan satu level kedalaman membutuhkan satu permutasi dan sekitar 270 siklus. Pohon berkedalaman 20 (satu juta anggota) terukur 5.866 siklus dan 22 permutasi, yaitu tier 14, tier tertinggi yang boleh digunakan sebuah panggilan.

Sejak chain 18, sebuah panggilan membayar gas, dan permutasi Keccak adalah instruksi yang mahal: 192 gas dibandingkan 1 untuk siklus biasa. Wallet mencetak gas yang tepat dari sebuah proses dan batas yang dideklarasikan untuknya:

gas: 5636 (declaring 6144, tier 12)

Setiap baris proses berbiaya 1 gas, dan baris Keccak berbiaya 191 lebih banyak: 3.344 baris ditambah 12 × 191 adalah 5.636, dan dua perlimanya adalah kedua belas hash itu. Wallet menghitung dua baris lebih banyak daripada rand-guest run. Di chain 18, bukti panggilan terikat pada transaksinya, dan pengikatan itu dibawa sebagai delapan word tambahan pada segmen publik, yang menambah dua baris digest. Batas yang dideklarasikan, 6.144, adalah angka tepat yang dibulatkan ke atas ke kelipatan 1.024. Batas itu publik dan angka tepatnya tidak.

Bukti yang membawa tabel Keccak berukuran besar. Bukti ini 3.346.865 byte, dibandingkan batas 4.194.304 (4 MiB) pada chain 18 sampai 20. Angka kedalaman 20 di atas adalah hasil pengukuran emulator, dan tidak ada bukti yang dibuat pada kedalaman itu untuk halaman ini.

7. Deploy

Deploy membawa segmen publik, sehingga biayanya menghitung 11 word-nya bersama 427 word kode: 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)

Id yang dicetak deploy, ad2f719f…b970, bukan yang dicetak rand-guest build. Dengan segmen publik, id-nya adalah blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public), sehingga mengikat root, poll id, dan jumlah pilihan. Poll kedua atas anggota yang sama adalah deploy kedua dari kode yang sama dengan poll id berbeda, dan mendapat id program yang berbeda serta nullifier yang berbeda.

hc juga dieja secara berbeda: rand-guest mencetak setiap dari delapan word-nya secara big-endian dan wallet mencetak byte setiap word secara little-endian, sehingga 42087673 menjadi 73760842. Digest-nya sama.

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

Siapa pun dapat membaca kembali segmen publik. rand_getProgramPublic mengembalikan word sebagai byte little-endian, sehingga root muncul seperti saat dicetak:

$ 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. Memberikan suara

rand call menerima satu --input untuk setiap kata privat, dalam bentuk desimal. sed mengubah berkas witness menjadi flag-flag tersebut:

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

Receipt adalah yang disimpan oleh chain: status 1, pilihan 2, dan lima kata nullifier, di bawah id program poll. h_pub adalah digest dari segmen publik poll, nilai yang sama dengan yang ditampilkan program show. h_in adalah komitmen bergaram atas 90 kata privat, dan tidak membuka apa pun tanpa salt-nya.

Panggilan tersebut memakan waktu tiga menit pada laptop Apple Silicon dan mencapai puncak 6,1 GB: 29 detik untuk bukti panggilan, 8 detik untuk otorisasi pembelanjaan, dan 117 detik untuk bundel yang membayar biaya. Biayanya, 0,0062 RAND, sebagian besar berupa byte. Four programs on chain 20 memuat perhitungannya.

Baris transkrip. Secara bawaan, wallet menyegel input privat dalam sebuah amplop yang hanya dapat dibuka oleh viewing key milik pemanggil, lalu memublikasikannya bersama panggilan. Itu adalah catatan bagi pemanggil, bukan pengungkapan: tidak ada orang lain yang dapat membukanya. Pemilih yang tidak menghendaki catatan sama sekali dapat menyertakan --no-envelope. Setelah itu, tidak seorang pun, termasuk pemilih itu sendiri, yang akan pernah dapat menunjukkan apa input tersebut.

9. Hitung suara

Penghitung suara tidak membutuhkan apa pun selain chain:

1. Poll. Ambil segmen publik program dan periksa root terhadap daftar daun yang dipublikasikan (bangun ulang pohon dengan levels milik allowlist.py). Bangun ulang guest dari sumbernya dan bandingkan hc dengan code_hash program.
2. Receipt. Ambil setiap receipt yang program-nya adalah id poll dan yang output 0-nya bernilai 1. Receipt dengan status lain, atau dengan 3735928559 pada slot 7, bukan suara.
3. Penghitungan. Kelompokkan berdasarkan output 2 sampai 6. Hitung setiap nullifier hanya sekali, yaitu receipt pertamanya menurut urutan chain, lalu tambahkan output 1-nya ke tally.

Tiga panggilan lagi dibuat agar penghitung suara memiliki sesuatu untuk dikerjakan. Anggota 5 memberikan suara untuk kedua kalinya, kali ini untuk pilihan 0. Anggota 2 memilih pilihan 1. Anggota 3 memilih pilihan 0, dari wallet yang hanya menggunakan endpoint RPC publik. Berikut suara kedua anggota 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

Chain menerima suara kedua tersebut, sebagaimana mestinya: buktinya valid. Receipt-nya memuat lima kata nullifier yang sama dengan yang pertama.

tally.py menerapkan ketiga aturan tersebut. Skrip ini membaca panggilan program dari explorer dan setiap receipt dari RPC publik, sehingga tidak memerlukan wallet maupun node:

$ 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

Perubahan pilihan anggota 5 tidak dihitung, dan tidak ada apa pun dalam keempat receipt yang menyatakan bahwa dua di antaranya berasal dari anggota daftar yang sama kecuali nullifier itu sendiri. Poll ini terbuka: berikan suara sebagai salah satu dari delapan anggota demo, lalu jalankan penghitungan sekali lagi.

Yang tidak diberikan oleh bukti ini

• Satu suara per secret, bukan satu suara per orang. Penyelenggara menentukan siapa yang mendapat daun. Anggota yang mendaftarkan dua daun memiliki dua suara.
• Secret pemilih hanya sebaik keacakannya. Secret yang diturunkan dari string yang dapat ditebak dapat ditemukan dengan melakukan hash atas tebakan-tebakan dan membandingkannya dengan daun yang dipublikasikan. Gunakan 32 byte acak.
• Pilihan bersifat publik. Receipt menunjukkan pilihan mana yang dipilih oleh sebuah nullifier. Tidak seorang pun dapat mengetahui anggota mana yang menjadi nullifier tersebut, tetapi poll dengan sedikit pemilih dan jumlah partisipasi yang dipublikasikan adalah statistik angka kecil, bukan kriptografi.
• Waktu dan biaya adalah metadata. Bundel biaya bersifat shielded dan tidak menyebut siapa pun, tetapi pemilih yang mendanai wallet-nya dan memberikan suara semenit kemudian pada jam yang sepi telah memberi tahu pengamat sesuatu.
• Penghitungan dilakukan di luar chain. Chain menyimpan receipt. Menghitungnya, dan menolak nullifier kedua, dilakukan oleh siapa pun yang membacanya.