匿名投票

本程式讓固定名單中的成員投一票，而不顯示自己是哪一位成員。名單是以 Keccak-256 哈希構成的 Merkle 樹，建法與 Ethereum 空投名單相同，因此可用同一套工具製作。程式已部署於 chain 18，最後一節會以示範成員呼叫它，你也可以自行使用。

Example programs 載有四個示範頁面共用的設定：circuits 的 checkout、錢包，以及原始碼的取得方式。

1. 證明內容

主辦方持有一份成員名單。每位成員持有一個 32 位元組的秘密值。主辦方從不看到這些秘密值：每位成員交出一片葉，即 keccak256(secret ‖ tag)，主辦方再以這些葉建構 Merkle 樹。

一次投票即一次呼叫。它在不透露其他任何資料的前提下證明：

1. 呼叫者知道某個秘密值，而其葉位於樹中；
2. 所公佈的選項是允許的選項之一；
3. 所公佈的作廢符等於 keccak256(secret ‖ tag ‖ poll id)。

同一個秘密值在同一次投票活動中所投的每一票，作廢符都相同；在其他投票活動中則各不相同。點票者對每個作廢符只計一次。作廢符不會連結到葉：要由作廢符回推葉，必須持有秘密值。

鏈不會拒絕第二次投票。 Rand 上的程式沒有儲存空間，因此無法記住作廢符（Programs）。以同一秘密值發出的兩次呼叫都會通過驗證，也都會留下收據。「一個作廢符，一票」這條規則由點票者對收據施行。任何人都可以進行同樣的點算，計票結果因而可供核實。

2. 介面

樹、投票活動及選項數目對每一票都相同，因此放在公開段，於部署時固定。程式 id 於是只指向這一次投票活動，不指向其他。

一個 32 位元組的哈希是八個字，而輸出的全部空間就只有八個字。公佈 160 位元，可為狀態和選項留出位置。兩位成員只有在哈希碰撞時才會共用同一個 160 位元作廢符，而要找出碰撞，約需 2⁸⁰ 次嘗試。

位元組順序。 Keccak 以位元組運算。機器的 KECCAK 系統呼叫以字為單位接收狀態，狀態的第 i 個位元組位於第 i / 4 個字的第 i mod 4 個位元組。因此 32 個位元組以每次四個位元組、小端序的方式讀取，便成為八個字，而公開段中的根，正是按此方式讀取的根之位元組。

3. Guest

my-guests/allowlist/src/main.rs，完整內容：

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

其中有三點值得仿效。

每次哈希只做一次置換。 guest_sdk::keccak256 接受任意位元組串，代價是要使用位元組迴圈。這裏每則訊息都恰為 64 位元組，小於 136 位元組的速率，因此填充只是兩個常數字，而哈希只需對一個以字複製填好的狀態執行一次 KECCAK 呼叫。以 Ethereum 的說法，hash2(a, b, 0) 即對兩個 bytes32 計算 keccak256(abi.encodePacked(a, b))。

葉和作廢符不會與樹節點混淆。 節點是對兩個 32 位元組的子哈希進行哈希。葉是對秘密值和一個固定的 ASCII 標籤進行哈希，作廢符則是對秘密值、另一個標籤和 poll id 進行哈希。葉若要冒充節點，其中一個子節點就必須等於該標籤，而這意味着要找出 Keccak 的原像。

走訪路徑時不依索引分支。 第一個版本以遮罩交換來決定兩半的順序，編譯器卻把遮罩還原成分支：葉索引中每有一個 1 位元，運行便多用 9 個週期。週期數本身並不公開，但呼叫所聲明的 gas 上限是由它進位而得（第 6 節），所以與索引有關的運行可能洩漏少量索引資訊。改為把每一半寫到計算所得的偏移位置後問題得以解決：現在每個葉索引都運行相同的 3,208 個週期。

4. 主機端

主辦方和投票者需要與機器所計算的相同的 Keccak。allowlist.py 是一個無須任何依賴的 Python 腳本，內含自備的 Keccak-f[1600]（Python 的 hashlib.sha3_256 是 SHA-3，填充方式不同，得出的摘要也不同）。它承擔兩項工作：

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

整棵樹，以腳本的方式表示：

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

在實際使用中，主辦方持有的是葉而非秘密值，各投票者再根據已公佈的葉自行建構見證。腳本接受秘密值檔案，是因為示範同時扮演兩個角色。

示範投票活動的深度為 10（1,024 片葉），poll id 為 1，共有三個選項。八位成員的秘密值存放於 demo-secrets.txt，每行一個 64 位十六進位秘密值。這些秘密值是刻意公開的，好讓任何人都能呼叫該程式：

$ 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

根的第一個字 4151217614 即 0xf76e8dce：根的首四個位元組 ce 8d 6e f7 以小端序讀取的結果。

5. 建構與運行

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

成員 5 投票予選項 2。見證共 90 個字：秘密值 8 個、索引 1 個、選項 1 個，以及路徑 80 個。

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

這五個作廢符字，與腳本在機器之外所算出的相同。失敗的情況會乾淨地停機並給出狀態，因此同樣可以被證明。同一份見證若把秘密值的第一個字改動，會得出 out[0] = 2 而無其他輸出；成員若在 3 個選項中要求選項 3，則得出 out[0] = 3。

6. 預算

深度每增加一層，便多一次置換和約 270 個週期。深度為 20 的樹（一百萬名成員）量度所得為 5,866 個週期和 22 次置換，屬於層級 14，即呼叫可使用的最高層級。

自 chain 18 起，呼叫須支付 gas，而 Keccak 置換是代價高昂的指令：192 gas，普通週期則為 1。錢包會列印一次運行的確切 gas 及其為此聲明的上限：

gas: 5636 (declaring 6144, tier 12)

運行的每一列耗 1 gas，Keccak 列則額外耗 191：3,344 列加 12 × 191 為 5,636，其中五分之二是那十二次哈希。錢包計算的列數比 rand-guest run 多兩列。在 chain 18 上，呼叫證明與其交易綁定，而該綁定以八個額外的公開段字攜帶，使摘要列增加兩列。所聲明的上限 6,144，是把確切數字進位至 1,024 的倍數。上限是公開的，確切數字則不公開。

攜帶 Keccak 表的證明相當龐大。這一個為 3,346,865 位元組，而 chain 18 至 20 的上限為 4,194,304（4 MiB）。上文深度為 20 的數字是模擬器的量度結果，本頁並未在該深度生成證明。

7. 部署

部署帶有公開段，因此費用計入其 11 個字及 427 個程式碼字：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)

deploy 所列印的 id ad2f719f…b970，與 rand-guest build 所列印的不同。有公開段時，id 為 blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public)，因此它綁定了根、poll id 和選項數目。以同一批成員進行第二次投票活動，即以不同的 poll id 再部署一次相同的程式碼，會得到不同的程式 id 和不同的作廢符。

hc 的寫法也不同：rand-guest 以大端序列印其八個字，而錢包則以小端序列印每個字的位元組，所以 42087673 變成 73760842。兩者是同一個摘要。

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

任何人都可以讀回公開段。rand_getProgramPublic 以小端序位元組返回各個字，因此根會以當初列印的樣子出現：

$ 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. 投票

rand call 對每個私有字詞接受一個 --input,以十進位表示。sed 會把見證檔案轉成這些旗標:

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

回執是鏈上保留的內容:狀態 1、選項 2,以及五個 nullifier 字詞,記錄於該投票的程式 id 之下。h_pub 是投票公開區段的摘要,與 program show 所印出的數值相同。h_in 是對 90 個私有字詞的加鹽承諾,沒有鹽值便無法開啟任何內容。

該次調用在 Apple Silicon 手提電腦上歷時三分鐘,峰值記憶體為 6.1 GB:調用證明 29 秒,花費授權 8 秒,支付費用的捆綁包 117 秒。費用 0.0062 RAND 主要來自位元組數。Four programs on chain 20 載有計算過程。

轉錄紀錄一行。 預設情況下,錢包會把私有輸入封入一個只有調用者的檢視密鑰才能開啟的信封,並隨調用一併發佈。這是給調用者本人的紀錄,而非披露:其他人無法開啟。不想留下任何紀錄的投票者可傳入 --no-envelope。此後無人,包括投票者本人,能再證明輸入內容為何。

9. 點算選票

點票者只需要鏈本身:

1. 投票。 取得程式的公開區段,並把根值與已公佈的葉節點清單核對(以 allowlist.py 的 levels 重建樹)。從源碼重建 guest,並把 hc 與程式的 code_hash 比對。
2. 回執。 取出所有 program 為該投票 id 且輸出 0 為 1 的回執。狀態為其他數值,或第 7 槽為 3735928559 的回執,不算作選票。
3. 點算。 按輸出 2 至 6 分組。每個 nullifier 只計一次,以其在鏈上順序中的第一份回執為準,並把其輸出 1 加進得票總數。

為了讓點票者有事可做,另外進行了三次調用。成員 5 第二次投票,這次投給選項 0。成員 2 投給選項 1。成員 3 投給選項 0,所用錢包只使用公開 RPC 端點。以下是成員 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

鏈接受了第二次投票,理應如此:證明有效。其回執所載的五個 nullifier 字詞與第一次相同。

tally.py 應用上述三條規則。它從瀏覽器讀取程式的調用,並從公開 RPC 讀取每份回執,因此無需錢包,也無需節點:

$ 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

成員 5 改變主意並不計算在內,而四份回執中,除了 nullifier 本身,沒有任何內容顯示其中兩份出自名單上的同一名成員。投票仍然開放:你可以以八名示範成員中任何一人的身分投票,然後再次運行點算。

證明不能給你的保證

• 每個密鑰一票,而非每人一票。 誰獲分配葉節點由組織者決定。登記兩個葉節點的成員便有兩票。
• 投票者的密鑰,其強度取決於隨機性。 由可猜測字串衍生的密鑰,可透過對猜測內容求雜湊並與已公佈的葉節點比對而被找出。請使用 32 個隨機位元組。
• 選項是公開的。 回執會顯示某個 nullifier 投給哪個選項。沒有人能分辨該 nullifier 屬於哪名成員,但投票人數不多而又公佈投票率的投票,屬於小數統計,而非密碼學。
• 時間與費用屬於元數據。 費用捆綁包是屏蔽的,不會點名任何人,但投票者若為錢包注資,並在清靜時段一分鐘後投票,便已向旁觀者透露了一些資訊。
• 點算在鏈下進行。 鏈只儲存回執。點算回執以及拒絕第二個 nullifier,由閱讀這些回執的人負責。