An anonymous vote

This program lets a member of a fixed list cast one vote without showing which member they are. The list is a Merkle tree of Keccak-256 hashes, built the way an Ethereum airdrop list is built, so the same tooling makes it. The program is deployed on chain 18, and the last section calls it with demo members you can use yourself.

Example programs has the setup all four example pages share: the circuits checkout, the wallet, and where to get the sources.

1. What it proves

An organiser has a list of members. Each member holds a 32-byte secret. The organiser never sees the secrets: each member hands over a leaf, keccak256(secret ‖ tag), and the organiser builds a Merkle tree over the leaves.

A vote is one call. It proves, without revealing anything else:

1. the caller knows a secret whose leaf is in the tree;
2. the published choice is one of the allowed choices;
3. the published nullifier is keccak256(secret ‖ tag ‖ poll id).

The nullifier is the same for every vote a secret casts in one poll, and different in every other poll. Whoever counts the votes counts each nullifier once. It does not link to the leaf: going from a nullifier back to a leaf needs the secret.

The chain does not reject a second vote. A program on Rand has no storage, so it cannot remember a nullifier (Programs). Two calls with the same secret both verify and both leave a receipt. The rule “one nullifier, one vote” is applied by the counter, over the receipts. Anyone can run the same count, which is what makes the tally checkable.

2. The interface

The tree, the poll and the number of choices are the same for every vote, so they go in the public segment, fixed at deploy. The program id then names this poll and no other.

A 32-byte hash is eight words, and eight words is all the output there is. Publishing 160 bits leaves room for the status and the choice. Two members would share a 160-bit nullifier only by a hash collision, which takes about 2⁸⁰ tries to find.

Byte order. Keccak works on bytes. The machine’s KECCAK syscall takes the state as words, with byte i of the state in byte i mod 4 of word i / 4. So 32 bytes become eight words by reading four bytes at a time, little-endian, and the root in the public segment is just the root’s bytes read that way.

3. The guest

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

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

Three things in it are worth copying.

One permutation per hash. guest_sdk::keccak256 takes any byte string, and pays for that with byte loops. Every message here is exactly 64 bytes, less than the 136-byte rate, so the padding is two constant words and the hash is one KECCAK call on a state filled by word copies. In Ethereum terms, hash2(a, b, 0) is keccak256(abi.encodePacked(a, b)) for two bytes32.

The leaf and the nullifier cannot be confused with a tree node. A node hashes two 32-byte child hashes. A leaf hashes a secret and a fixed ASCII tag, and a nullifier hashes a secret, another tag and the poll id. For a leaf to pass as a node, one of its children would have to equal the tag, which means finding a Keccak preimage.

The path is walked without branching on the index. The first version chose the order of the two halves with a masked swap, and the compiler turned the mask back into a branch: the run took 9 more cycles for every 1 bit in the leaf index. The cycle count itself is not published, but the gas limit a call declares is rounded from it (section 6), so a run that depends on the index can leak a little of the index. Writing each half at a computed offset fixed it: every leaf index now runs the same 3,208 cycles.

4. The host side

The organiser and the voters need the same Keccak the machine computes. allowlist.py is a dependency-free Python script with its own Keccak-f[1600] (Python’s hashlib.sha3_256 is SHA-3, which pads differently and gives different digests). It does two jobs:

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

The whole tree, in the script’s terms:

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

In production the organiser holds leaves, not secrets, and each voter builds their own witness from the published leaves. The script takes a secrets file because the demo plays both roles.

The demo poll has depth 10 (1,024 leaves), poll id 1 and three choices. Its eight members’ secrets are in demo-secrets.txt, one 64-hex secret per line, and they are public on purpose so that anyone can call the 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

The first root word, 4151217614, is 0xf76e8dce: the root’s first four bytes ce 8d 6e f7 read little-endian.

5. Build and run

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

Member 5 votes for choice 2. The witness is 90 words: 8 for the secret, the index, the choice and 80 for the path.

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

The five nullifier words are the ones the script computed outside the machine. The failures halt cleanly with a status, so they can be proved too. The same witness with the first word of the secret changed gives out[0] = 2 and nothing else, and a member asking for choice 3 of 3 gives out[0] = 3.

6. The budget

Each extra level of depth costs one permutation and about 270 cycles. A depth-20 tree (a million members) measures 5,866 cycles and 22 permutations, which is tier 14, the highest tier a call may use.

Since chain 18 a call pays for gas, and a Keccak permutation is the expensive instruction: 192 gas against 1 for an ordinary cycle. The wallet prints the exact gas of a run and the limit it declares for it:

gas: 5636 (declaring 6144, tier 12)

Every row of the run costs 1 gas, and a Keccak row costs 191 more: 3,344 rows plus 12 × 191 is 5,636, and two fifths of it is the twelve hashes. The wallet counts two more rows than rand-guest run did. On chain 18 a call proof is bound to its transaction, and the binding travels as eight extra words of public segment, which adds two digest rows. The declared limit, 6,144, is the exact figure rounded up to a multiple of 1,024. The limit is public and the exact figure is not.

A proof that carries the Keccak table is large. This one is 3,346,865 bytes, against a cap of 4,194,304 (4 MiB) on chains 18 to 20. The depth-20 figures above are emulator measurements, and no proof was made at that depth for this page.

7. Deploy

The deploy carries the public segment, so the fee counts its 11 words with the 427 code words: 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)

The id deploy prints, ad2f719f…b970, is not the one rand-guest build printed. With a public segment the id is blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public), so it binds the root, the poll id and the number of choices. A second poll over the same members is a second deploy of the same code with a different poll id, and gets a different program id and different nullifiers.

hc is also spelled differently: rand-guest prints each of its eight words big-endian and the wallet prints each word’s bytes little-endian, so 42087673 became 73760842. It is the same 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
}

Anyone can read the public segment back. rand_getProgramPublic returns the words as little-endian bytes, so the root appears as it was printed:

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

rand call takes one --input per private word, in decimal. The sed turns the witness file into those 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`

The receipt is what the chain keeps: status 1, choice 2, and the five nullifier words, under the poll’s program id. h_pub is the digest of the poll’s public segment, the same value program show printed. h_in is a salted commitment to the 90 private words, and it opens nothing without the salt.

The call took three minutes on an Apple Silicon laptop and peaked at 6.1 GB: 29 s for the call proof, 8 s for the spend authorisation and 117 s for the bundle that pays the fee. The fee, 0.0062 RAND, is mostly bytes. Four programs on chain 20 has the arithmetic.

The transcript line. By default the wallet seals the private inputs in an envelope only the caller’s viewing key opens, and publishes it with the call. That is a record for the caller, not a disclosure: nobody else can open it. A voter who wants no record at all passes --no-envelope. After that nobody, the voter included, can ever show what the inputs were.

9. Count the votes

A counter needs nothing but the chain:

1. The poll. Fetch the program’s public segment and check the root against the published list of leaves (rebuild the tree with allowlist.py’s levels). Rebuild the guest from source and compare hc with the program’s code_hash.
2. The receipts. Take every receipt whose program is the poll’s id and whose output 0 is 1. A receipt with any other status, or with 3735928559 in slot 7, is not a vote.
3. The count. Group by outputs 2 to 6. Count each nullifier once, its first receipt in chain order, and add its output 1 to the tally.

Three more calls were made to give the counter something to do. Member 5 voted a second time, now for choice 0. Member 2 voted for choice 1. Member 3 voted for choice 0, from a wallet that used only the public RPC endpoint. This is member 5’s second vote:

$ 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

The chain accepted the second vote, as it must: the proof is valid. Its receipt carries the same five nullifier words as the first.

tally.py applies the three rules. It reads the program’s calls from the explorer and each receipt from the public RPC, so it needs no wallet and no 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

Member 5’s change of mind did not count, and nothing in the four receipts says that two of them came from the same member of the list except the nullifier itself. The poll is open: vote as any of the eight demo members and run the tally again.

What the proof does not give you

• One vote per secret, not one vote per person. The organiser decides who gets a leaf. A member who registers two leaves has two votes.
• The voter’s secret is only as good as its randomness. A secret derived from a guessable string can be found by hashing guesses and comparing with the published leaves. Use 32 random bytes.
• The choice is public. A receipt shows which choice a nullifier voted for. Nobody can tell which member the nullifier is, but a poll with few voters and a published turnout is small-number statistics, not cryptography.
• Timing and fees are metadata. The fee bundle is shielded and names nobody, but a voter who funds their wallet and votes a minute later in a quiet hour has told a watcher something.
• The tally is off chain. The chain stores receipts. Counting them, and refusing a second nullifier, is done by whoever reads them.