匿名投票

この例のプログラムでは、固定されたリストのメンバーが、自分がどのメンバーかを明かさずに1票を投じられます。リストは Keccak-256 ハッシュのマークル木で、Ethereum のエアドロップ用リストと同じ方法で作ります。そのため、同じツールで生成できます。プログラムはチェーン18にデプロイされており、最後のセクションでは、自分で使えるデモ用メンバーを使って呼び出します。

Example programs では、4つのサンプルページに共通するセットアップ(circuits のチェックアウト、ウォレット、ソースの入手先)を説明しています。

1. 証明すること

主催者はメンバーのリストを持っています。各メンバーは32バイトのシークレットを持っています。主催者がシークレットを見ることはありません。各メンバーはリーフ keccak256(secret ‖ tag) を主催者に渡し、主催者はリーフの上にマークル木を構築します。

投票は1回の呼び出しです。この呼び出しは、ほかには何も明かさずに、次のことを証明します。

1. 呼び出し元が、リーフが木に含まれるシークレットを知っていること。
2. 公開された選択肢が、許可された選択肢のいずれかであること。
3. 公開されたヌリファイアが keccak256(secret ‖ tag ‖ poll id) であること。

ヌリファイアは、同じシークレットが1つの投票で投じるすべての票で同じ値になり、ほかの投票ではすべて異なる値になります。票を集計する側は、各ヌリファイアを1回だけ数えます。ヌリファイアはリーフとは結び付きません。ヌリファイアからリーフへ遡るにはシークレットが必要だからです。

チェーンは2回目の投票を拒否しません。 Rand のプログラムにはストレージがなく、ヌリファイアを記憶できないためです(Programs)。同じシークレットによる2回の呼び出しは、どちらも検証に通り、どちらもレシートを残します。「1つのヌリファイアにつき1票」というルールは、集計者がレシートに対して適用します。誰でも同じ集計を実行できるので、集計結果を検証できます。

2. インターフェース

木、投票、選択肢の数はすべての票で共通なので、公開セグメントに置き、デプロイ時に固定します。こうすると、プログラム id はこの投票だけを指します。

32バイトのハッシュは8ワードで、出力に使えるのも8ワードだけです。160ビットを公開すれば、ステータスと選択肢の分の余地が残ります。2人のメンバーが160ビットのヌリファイアを共有するのはハッシュの衝突が起きた場合だけで、それを見つけるには約2⁸⁰回の試行が必要です。

バイト順。 Keccak はバイト単位で動作します。マシンの KECCAK システムコールは、状態をワード列として受け取り、状態のバイト i をワード i / 4 のバイト i mod 4 に置きます。したがって、32バイトを8ワードにするには4バイトずつリトルエンディアンで読み、公開セグメントのルートは、ルートのバイト列をそのように読んだものです。

3. ゲスト

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

このコードには、手本にする価値のある点が3つあります。

ハッシュごとに順列1回。 guest_sdk::keccak256 は任意のバイト列を受け取れますが、その代償としてバイト単位のループが必要になります。ここでのメッセージはすべてちょうど64バイトで、レート136バイトより短いので、パディングは2つの定数ワードになり、ハッシュはワードのコピーで埋めた状態に対する KECCAK 1回の呼び出しで済みます。Ethereum の言い方では、hash2(a, b, 0) は2つの bytes32 に対する keccak256(abi.encodePacked(a, b)) です。

リーフとヌリファイアは木のノードと取り違えられません。 ノードは2つの32バイトの子ハッシュをハッシュしたものです。リーフはシークレットと固定の ASCII タグをハッシュしたもので、ヌリファイアはシークレット、別のタグ、poll id をハッシュしたものです。リーフがノードとして通用するには、その子の1つがタグと等しくなければならず、それは Keccak の原像を見つけることを意味します。

パスはインデックスで分岐せずにたどります。 最初のバージョンでは、マスク付きのスワップで2つの半分の順序を選んでいましたが、コンパイラがそのマスクを分岐に戻してしまい、リーフインデックスの 1 のビット1つにつき、実行が9サイクル余分にかかっていました。サイクル数そのものは公開されませんが、呼び出しが宣言するガスリミットはそこから丸めて決まります(section 6)。そのため、インデックスに依存する実行は、インデックスの情報を少し漏らす可能性があります。それぞれの半分を計算したオフセットに書き込むことで解消し、現在はどのリーフインデックスでも同じ3,208サイクルで実行されます。

4. ホスト側

主催者と投票者には、マシンが計算するものと同じ Keccak が必要です。allowlist.py は、独自の Keccak-f[1600] を備えた、依存ライブラリのない Python スクリプトです(Python の hashlib.sha3_256 は SHA-3 で、パディングが異なり、別のダイジェストを返します)。このスクリプトは2つの仕事をします。

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、選択肢3つです。8人のメンバーのシークレットは demo-secrets.txt に1行1つの64桁の16進数で収められており、誰でもプログラムを呼び出せるように、意図的に公開されています。

$ 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 です。ルートの先頭4バイト 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)

5つのヌリファイアのワードは、スクリプトがマシンの外で計算したものと同じです。失敗の場合もステータスを残して正常に停止するので、それらも証明できます。同じウィットネスでシークレットの最初のワードだけを変えると out[0] = 2 となり、ほかは何も出力されません。また、3つの選択肢のうち選択肢3を求めたメンバーは out[0] = 3 になります。

6. バジェット

深さが1つ増えるごとに、順列1回と約270サイクルかかります。深さ20の木(100万人のメンバー)では、5,866サイクルと22回の順列を計測しており、これはティア14、つまり呼び出しが使える最高のティアです。

チェーン18以降、呼び出しはガスを支払い、Keccak の順列は高価な命令です。通常のサイクルが 1 であるのに対し、192 ガスかかります。ウォレットは、実行の正確なガスと、そのために宣言するリミットを表示します。

gas: 5636 (declaring 6144, tier 12)

実行の各行は 1 ガスで、Keccak の行はさらに 191 かかります。3,344行に 12 × 191 を足すと 5,636 で、その5分の2が12回のハッシュによるものです。ウォレットが数える行は、rand-guest run より2行多くなります。チェーン18では、呼び出しの証明がそのトランザクションに束縛され、その束縛は8ワード分の追加の公開セグメントとして運ばれるため、ダイジェスト行が2行増えるからです。宣言されるリミットの 6,144 は、正確な値を 1,024 の倍数に切り上げたものです。リミットは公開され、正確な値は公開されません。

Keccak テーブルを含む証明は大きくなります。この証明は 3,346,865 バイトで、チェーン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、選択肢の数に束縛されます。同じメンバーに対する2つ目の投票は、同じコードを別の poll id でもう一度デプロイすることになり、異なるプログラム id と異なるヌリファイアが得られます。

hc も表記が異なります。rand-guest は8つのワードをそれぞれビッグエンディアンで表示し、ウォレットは各ワードのバイトをリトルエンディアンで表示するため、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 を1つ、10進数で受け取ります。sed は witness ファイルをそれらのフラグに変換します。

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

レシートはチェーンが保持するものです。status は 1、choice は 2、そして5つの nullifier ワードが、投票プログラムの program id のもとに記録されます。h_pub は投票の公開セグメントのダイジェストで、program show が出力したものと同じ値です。h_in は90個のプライベートワードに対するソルト付きコミットメントであり、ソルトがなければ何も開示しません。

この呼び出しには Apple Silicon 搭載のノート PC で3分かかり、ピークは 6.1 GB でした。内訳は、呼び出しの証明が 29 秒、支出の承認が 8 秒、手数料を支払うバンドルが 117 秒です。手数料の 0.0062 RAND は、大部分がバイト数に由来します。計算の詳細は Four programs on chain 20 にあります。

トランスクリプトの行。 既定では、ウォレットはプライベート入力を、呼び出し元のビューイングキーでのみ開けるエンベロープに封じ、呼び出しとともに公開します。これは呼び出し元のための記録であり、開示ではありません。ほかの誰もそれを開けません。記録をまったく残したくない投票者は --no-envelope を指定します。そうすると、入力が何だったかを示すことは、投票者本人を含めて誰にもできなくなります。

9. 投票を集計する

集計者に必要なのはチェーンだけです。

1. 投票。 プログラムの公開セグメントを取得し、そのルートを公開済みのリーフ一覧と照合します(allowlist.py の levels でツリーを再構築します)。ガestをソースから再ビルドし、hc をプログラムの code_hash と比較します。
2. レシート。 program が投票プログラムの id であり、出力 0 が 1 であるレシートをすべて集めます。status がそれ以外のレシート、またはスロット 7 に 3735928559 があるレシートは、投票ではありません。
3. 集計。 出力 2 から 6 でグループ化します。各 nullifier は1回だけ、つまりチェーン順で最初のレシートだけを数え、その出力 1 を集計に加算します。

集計者に作業を与えるため、さらに3回の呼び出しを行いました。メンバー 5 が、今度は choice 0 に2度目の投票をしました。メンバー 2 は choice 1 に投票しました。メンバー 3 は、公開 RPC エンドポイントだけを使うウォレットから choice 0 に投票しました。次はメンバー 5 の2度目の投票です。

$ 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

チェーンは2度目の投票を受理しました。証明が有効である以上、そうなるのが当然です。そのレシートには、1度目と同じ5つの nullifier ワードが含まれます。

tally.py は3つのルールを適用します。プログラムの呼び出しはエクスプローラーから、各レシートは公開 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 の気の変化は数えられませんでした。4つのレシートのうち2つが一覧の同じメンバーによるものだと示すのは、nullifier 自体だけです。この投票は開かれています。8人のデモメンバーの誰かとして投票し、もう一度集計を実行してみてください。

証明が保証しないこと

• 1つのシークレットにつき1票であり、1人につき1票ではありません。 誰にリーフを与えるかは主催者が決めます。2つのリーフを登録したメンバーは、2票を持ちます。
• 投票者のシークレットの強度は、その乱数性で決まります。 推測しやすい文字列から導いたシークレットは、推測をハッシュして公開済みのリーフと照合することで見つけられてしまいます。32バイトの乱数を使ってください。
• 選択は公開されます。 レシートには、ある nullifier がどの選択に投票したかが示されます。その nullifier がどのメンバーかは誰にも分かりませんが、投票者が少なく投票率が公開されている投票は、暗号ではなく少数統計の問題です。
• タイミングと手数料はメタデータです。 手数料のバンドルはシールドされていて誰の名前も示しませんが、ウォレットに入金して1分後、人の少ない時間帯に投票した投票者は、観察者に何かを伝えてしまっています。
• 集計はオフチェーンです。 チェーンが保存するのはレシートです。それらを数え、2つ目の nullifier を拒否するのは、レシートを読む側の仕事です。