Анонимное голосование

Эта программа позволяет участнику фиксированного списка отдать один голос, не показывая, кто именно из участников голосует. Список — это дерево Меркла из хешей Keccak-256, построенное так же, как строятся списки для эирдропов в Ethereum, поэтому его создают те же инструменты. Программа развёрнута в chain 18, а последний раздел вызывает её с демонстрационными участниками, которыми вы можете воспользоваться сами.

Example programs содержит настройку, общую для всех четырёх страниц с примерами: checkout circuits, кошелёк и источник, откуда взять исходный код.

1. Что она доказывает

У организатора есть список участников. У каждого участника есть 32-байтовый секрет. Организатор секретов не видит: каждый участник передаёт лист — keccak256(secret ‖ tag), — а организатор строит дерево Меркла по листьям.

Голосование — это один вызов. Он доказывает, не раскрывая ничего больше, что:

1. вызывающий знает секрет, лист которого входит в дерево;
2. публикуемый выбор — один из допустимых вариантов;
3. публикуемый нуллификатор равен keccak256(secret ‖ tag ‖ poll id).

Нуллификатор один и тот же для всех голосов, поданных одним секретом в одном опросе, и разный в каждом другом опросе. Тот, кто подсчитывает голоса, учитывает каждый нуллификатор один раз. Он не связан с листом: чтобы от нуллификатора вернуться к листу, нужен секрет.

Цепочка не отклоняет второй голос. У программы в Rand нет хранилища, поэтому она не может запомнить нуллификатор (Programs). Два вызова с одним и тем же секретом оба проходят проверку и оба оставляют квитанцию. Правило «один нуллификатор — один голос» применяет счётчик голосов, работая с квитанциями. Тот же подсчёт может выполнить любой, и именно поэтому итог поддаётся проверке.

2. Интерфейс

Дерево, опрос и число вариантов одинаковы для каждого голоса, поэтому они помещены в публичный сегмент, фиксируемый при развёртывании. Тогда идентификатор программы называет именно этот опрос и никакой другой.

32-байтовый хеш — это восемь слов, и восемь слов — весь доступный выход. Публикация 160 бит оставляет место для статуса и выбора. Два участника получили бы одинаковый 160-битный нуллификатор только при коллизии хеша, на поиск которой уходит около 2⁸⁰ попыток.

Порядок байтов. Keccak работает с байтами. Системный вызов KECCAK машины принимает состояние как слова, причём байт i состояния лежит в байте i mod 4 слова i / 4. Поэтому 32 байта превращаются в восемь слов чтением по четыре байта в порядке little-endian, а корень в публичном сегменте — это просто байты корня, прочитанные таким образом.

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

В ней стоит перенять три момента.

Одна перестановка на хеш. guest_sdk::keccak256 принимает любую байтовую строку и платит за это байтовыми циклами. Каждое сообщение здесь занимает ровно 64 байта, меньше 136-байтового rate, поэтому дополнение — это два постоянных слова, а хеш — один вызов KECCAK над состоянием, заполненным копированием слов. В терминах Ethereum hash2(a, b, 0) — это keccak256(abi.encodePacked(a, b)) для двух bytes32.

Лист и нуллификатор нельзя спутать с узлом дерева. Узел хеширует два 32-байтовых дочерних хеша. Лист хеширует секрет и фиксированный ASCII-тег, а нуллификатор — секрет, другой тег и идентификатор опроса. Чтобы лист сошёл за узел, один из его дочерних элементов должен был бы совпасть с тегом, а для этого нужно найти прообраз Keccak.

Путь проходится без ветвления по индексу. В первой версии порядок двух половин выбирался маскированным обменом, и компилятор превратил маску обратно в ветвление: прогон занимал на 9 циклов больше за каждый бит 1 в индексе листа. Само число циклов не публикуется, но лимит газа, объявляемый вызовом, округляется от него (раздел 6), поэтому прогон, зависящий от индекса, может немного раскрывать индекс. Запись каждой половины по вычисляемому смещению исправила это: теперь любой индекс листа выполняется ровно за 3 208 циклов.

4. Сторона хоста

Организатору и голосующим нужен тот же Keccak, который вычисляет машина. allowlist.py — скрипт на Python без зависимостей с собственной реализацией Keccak-f[1600] (hashlib.sha3_256 в Python — это 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"))

В реальной работе организатор хранит листья, а не секреты, и каждый голосующий строит свой свидетель (witness) из опубликованных листьев. Скрипт принимает файл секретов, потому что демонстрация исполняет обе роли.

У демонстрационного опроса глубина 10 (1 024 листа), идентификатор опроса 1 и три варианта. Секреты его восьми участников лежат в demo-secrets.txt, по одному 64-символьному hex-секрету в строке, и они публичны намеренно, чтобы любой мог вызвать программу:

$ 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, прочитанные в порядке little-endian.

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 на секрет, индекс, выбор и 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 перестановки, то есть tier 14 — наивысший tier, который может использовать вызов.

Начиная с chain 18 вызов оплачивает газ, а перестановка Keccak — самая дорогая инструкция: 192 газа против 1 у обычного цикла. Кошелёк печатает точный расход газа для прогона и лимит, который он для него объявляет:

gas: 5636 (declaring 6144, tier 12)

Каждая строка прогона стоит 1 газ, а строка Keccak — ещё на 191 больше: 3 344 строки плюс 12 × 191 дают 5 636, и две пятых этой суммы приходится на двенадцать хешей. Кошелёк насчитывает на две строки больше, чем rand-guest run. В chain 18 доказательство вызова привязано к его транзакции, и эта привязка передаётся восемью дополнительными словами публичного сегмента, что добавляет две строки дайджеста. Объявленный лимит, 6 144, — это точное значение, округлённое вверх до кратного 1 024. Лимит публичен, а точное значение — нет.

Доказательство, несущее таблицу Keccak, велико. Это — 3 346 865 байт при лимите 4 194 304 (4 MiB) в chain 18–20. Приведённые выше цифры для глубины 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, ad2f719f…b970, — не тот, что напечатал rand-guest build. При наличии публичного сегмента идентификатор равен blake3("rand-program-2", base_pc ‖ len ‖ words ‖ len ‖ public), поэтому он привязан к корню, идентификатору опроса и числу вариантов. Второй опрос по тем же участникам — это второе развёртывание того же кода с другим идентификатором опроса; оно получает другой идентификатор программы и другие нуллификаторы.

hc тоже записан иначе: rand-guest печатает каждое из своих восьми слов в порядке big-endian, а кошелёк печатает байты каждого слова в порядке little-endian, поэтому 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 возвращает слова как байты little-endian, поэтому корень выглядит так, как был напечатан:

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

Chain хранит квитанцию: статус 1, выбор 2 и пять слов нуллификатора под идентификатором программы голосования. h_pub — дайджест публичного сегмента голосования, то же значение, что вывел program show. h_in — солёное обязательство на 90 закрытых слов; без соли оно ничего не раскрывает.

Вызов занял три минуты на ноутбуке с Apple Silicon, пиковое потребление памяти составило 6,1 GB: 29 s на доказательство вызова, 8 s на авторизацию траты и 117 s на пакет, оплачивающий комиссию. Комиссия, 0,0062 RAND, — это в основном байты. Арифметика приведена в разделе Four programs on chain 20.

Строка транскрипта. По умолчанию кошелёк запечатывает закрытые входные данные в конверт, который открывает только ключ просмотра вызывающего, и публикует его вместе с вызовом. Это запись для вызывающего, а не раскрытие: больше никто не может её открыть. Избиратель, которому не нужна никакая запись, передаёт --no-envelope. После этого никто, включая самого избирателя, никогда не сможет показать, какими были входные данные.

9. Подсчёт голосов

Счётчику не нужно ничего, кроме блокчейна:

1. Голосование. Получите публичный сегмент программы и сверьте корень с опубликованным списком листьев (перестройте дерево с помощью levels из allowlist.py). Пересоберите гостевую программу из исходного кода и сравните hc с code_hash программы.
2. Квитанции. Возьмите каждую квитанцию, у которой program совпадает с идентификатором голосования, а выход 0 равен 1. Квитанция с любым другим статусом или с 3735928559 в слоте 7 голосом не является.
3. Подсчёт. Сгруппируйте по выходам с 2 по 6. Каждый нуллификатор учитывается один раз, по его первой квитанции в порядке цепочки, и его выход 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

Chain принял второй голос, как и должен был: доказательство верно. Его квитанция содержит те же пять слов нуллификатора, что и первая.

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 не был засчитан, и ничто в четырёх квитанциях не указывает, что две из них пришли от одного и того же участника списка, кроме самого нуллификатора. Голосование открыто: проголосуйте от имени любого из восьми демонстрационных участников и запустите подсчёт снова.

Что доказательство не даёт

• Один голос на секрет, а не один голос на человека. Организатор решает, кто получает лист. Участник, зарегистрировавший два листа, получает два голоса.
• Секрет избирателя надёжен ровно настолько, насколько надёжна его случайность. Секрет, выведенный из угадываемой строки, можно найти, хешируя догадки и сравнивая их с опубликованными листьями. Используйте 32 случайных байта.
• Выбор публичен. Квитанция показывает, за какой вариант проголосовал нуллификатор. Никто не может определить, какому участнику соответствует нуллификатор, но голосование с малым числом избирателей и опубликованной явкой — это статистика малых чисел, а не криптография.
• Время и комиссии — это метаданные. Пакет комиссии экранирован и никого не называет, но избиратель, который пополняет кошелёк и голосует минутой позже в тихий час, кое-что сообщил наблюдателю.
• Подсчёт ведётся вне цепочки. Блокчейн хранит квитанции. Подсчёт и отказ принимать второй нуллификатор выполняет тот, кто их читает.