O anonimato na votação é um dos requisitos básicos, mas em uma rede pública como uma blockchain, não é trivial implementá-lo. Felizmente, a tecnologia de prova de conhecimento zero (ZKP) torna isso possível, mas, infelizmente, ZKP é uma tecnologia muito complexa. É por isso que construí zk-merkle-tree, uma biblioteca JavaScript que oculta quase todas as complexidades do zkSNARK.
Existem outras bibliotecas como Semaphore, que resolvem esse problema. A vantagem da zk-merkle-tree é que ela é muito simples. Também tenho um projeto de exemplo, onde você pode ver como pode usá-la em seu próprio projeto.
Neste artigo, mostrarei passo a passo como construí esta biblioteca com base no código-fonte do aplicativo misturador de moedas, Tornado Cash, portanto, este artigo não será apenas uma introdução à biblioteca, mas um tutorial de como você pode criar uma aplicação geral baseada no zkSNARK.
Tenho artigos anteriores sobre prova de conhecimento zero e zkSNARK. É altamente recomendável lê-los antes deste artigo, porque este artigo é baseado neles.
A primeira coisa sobre a qual quero falar é o hashing. No mundo Ethereum, estamos usando variações do algoritmo SHA (SHA-256, Keccak-256, etc.) para hashing. Infelizmente, o cálculo da ZKP usando esses algoritmos é caro, então temos que usar hashing compatível com ZK. Existem alguns algoritmos compatíveis com ZK, como MiMC e Pedersen que são usados pelo Tornado Cash (e também zk-merkle-tree), ou Poseidon que é usado pela Semaphore. Esses hashes podem ser calculados de forma barata em circuitos ZK, mas são um pouco mais caros na blockchain do que as variações SHA.
Tornado Cash e zk-merkle-tree estão usando hashes MiMC para construir a árvore de Merkle. Circonlibjs contém uma implementação dela e um gerador de contrato inteligente que você pode usar para implantá-la na blockchain.
const MiMCSponge = new ethers.ContractFactory(
mimcSpongecontract.abi,
mimcSpongecontract.createCode(SEED, 220),
signers[0]
)
mimcsponge = await MiMCSponge.deploy()
O código acima é de zktree_test.ts e usa ethers para implantar o contrato de hash MiMC na blockchain.
O hasher no lado JS pode ser gerado pelo seguinte:
mimc = await buildMimcSponge();
Você pode testar seu contrato por este código:
const res = await mimcsponge["MiMCSponge"](1, 2, 3);
const res2 = mimc.hash(1, 2, 3);
assert.equal(res.xL.toString(), mimc.F.toString(res2.xL));
assert.equal(res.xR.toString(), mimc.F.toString(res2.xR));
A primeira linha calcula o hash usando o contrato inteligente e a segunda linha também calcula pela função JS. A única parte interessante é a conversão de número para string por F.toString. Na zk-SNARK, todo cálculo é feito em um campo finito, então temos que usar mimc.F.toString para a conversão.
Agora podemos calcular hashes MiMC compatíveis com ZK, então tudo está pronto para construir a árvore de Merkle. A implementação do Solidity da árvore de Merkle é totalmente importada do TornadoCash:
// baseado em https://github.com/tornadocash/tornado-core/blob/master/contracts/MerkleTreeWithHistory.sol
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;
import "hardhat/console.sol";
interface IHasher {
function MiMCSponge(
uint256 in_xL,
uint256 in_xR,
uint256 k
) external pure returns (uint256 xL, uint256 xR);
}
contract MerkleTreeWithHistory {
uint256 public constant FIELD_SIZE =
21888242871839275222246405745257275088548364400416034343698204186575808495617;
uint256 public constant ZERO_VALUE =
21663839004416932945382355908790599225266501822907911457504978515578255421292; // = keccak256("tornado") % FIELD_SIZE
IHasher public immutable hasher;
uint32 public levels;
// as seguintes variáveis são tornadas públicas para facilitar os testes e a depuração e não devem ser acessadas em código normal
// filledSubtrees e roots poderiam ser bytes32[tamanho], mas o uso de mapeamentos os tornam mais barato porque removem a verificação da faixa de índice em cada interação
mapping(uint256 => bytes32) public filledSubtrees;
mapping(uint256 => bytes32) public roots;
uint32 public constant ROOT_HISTORY_SIZE = 30;
uint32 public currentRootIndex = 0;
uint32 public nextIndex = 0;
constructor(uint32 _levels, IHasher _hasher) {
require(_levels > 0, "_levels devem ser maiores que zero");
require(_levels < 32, "_levels deve ser inferior a 32");
levels = _levels;
hasher = _hasher;
for (uint32 i = 0; i < _levels; i++) {
filledSubtrees[i] = zeros(i);
}
roots[0] = zeros(_levels - 1);
}
/**
@dev Hash 2 folhas da árvore, returna MiMC(_left, _right)
*/
function hashLeftRight(
uint256 _left,
uint256 _right
) public view returns (bytes32) {
require(
_left < FIELD_SIZE,
"_left deve estar dentro do campo"
);
require(
_right < FIELD_SIZE,
"_right deve estar dentro do campo"
);
uint256 R = _left;
uint256 C = 0;
(R, C) = hasher.MiMCSponge(R, C, 0);
R = addmod(R, _right, FIELD_SIZE);
(R, C) = hasher.MiMCSponge(R, C, 0);
return bytes32(R);
}
function _insert(bytes32 _leaf) internal returns (uint32 index) {
uint32 _nextIndex = nextIndex;
require(
_nextIndex != uint32(2) ** levels,
"A árvore de Merkle está cheia. Não é possível acrescentar mais folhas."
);
uint32 currentIndex = _nextIndex;
bytes32 currentLevelHash = _leaf;
bytes32 left;
bytes32 right;
for (uint32 i = 0; i < levels; i++) {
if (currentIndex % 2 == 0) {
left = currentLevelHash;
right = zeros(i);
filledSubtrees[i] = currentLevelHash;
} else {
left = filledSubtrees[i];
right = currentLevelHash;
}
currentLevelHash = hashLeftRight(uint256(left), uint256(right));
currentIndex /= 2;
}
uint32 newRootIndex = (currentRootIndex + 1) % ROOT_HISTORY_SIZE;
currentRootIndex = newRootIndex;
roots[newRootIndex] = currentLevelHash;
nextIndex = _nextIndex + 1;
return _nextIndex;
}
/**
@dev Se a raiz está presente no histórico da raiz
*/
function isKnownRoot(bytes32 _root) public view returns (bool) {
if (_root == 0) {
return false;
}
uint32 _currentRootIndex = currentRootIndex;
uint32 i = _currentRootIndex;
do {
if (_root == roots[i]) {
return true;
}
if (i == 0) {
i = ROOT_HISTORY_SIZE;
}
i--;
} while (i != _currentRootIndex);
return false;
}
/**
@dev Retorna a última raiz
*/
function getLastRoot() public view returns (bytes32) {
return roots[currentRootIndex];
}
/// @dev fornece Zero (Vazio) elementos para um MerkleTree MiMC. Até 32 níveis
function zeros(uint256 i) public pure returns (bytes32) {
if (i == 0)
return
bytes32(
0x2fe54c60d3acabf3343a35b6eba15db4821b340f76e741e2249685ed4899af6c
);
else if (i == 1)
return
bytes32(
0x256a6135777eee2fd26f54b8b7037a25439d5235caee224154186d2b8a52e31d
);
else if (i == 2)
return
bytes32(
0x1151949895e82ab19924de92c40a3d6f7bcb60d92b00504b8199613683f0c200
);
else if (i == 3)
return
bytes32(
0x20121ee811489ff8d61f09fb89e313f14959a0f28bb428a20dba6b0b068b3bdb
);
else if (i == 4)
return
bytes32(
0x0a89ca6ffa14cc462cfedb842c30ed221a50a3d6bf022a6a57dc82ab24c157c9
);
else if (i == 5)
return
bytes32(
0x24ca05c2b5cd42e890d6be94c68d0689f4f21c9cec9c0f13fe41d566dfb54959
);
else if (i == 6)
return
bytes32(
0x1ccb97c932565a92c60156bdba2d08f3bf1377464e025cee765679e604a7315c
);
else if (i == 7)
return
bytes32(
0x19156fbd7d1a8bf5cba8909367de1b624534ebab4f0f79e003bccdd1b182bdb4
);
else if (i == 8)
return
bytes32(
0x261af8c1f0912e465744641409f622d466c3920ac6e5ff37e36604cb11dfff80
);
else if (i == 9)
return
bytes32(
0x0058459724ff6ca5a1652fcbc3e82b93895cf08e975b19beab3f54c217d1c007
);
else if (i == 10)
return
bytes32(
0x1f04ef20dee48d39984d8eabe768a70eafa6310ad20849d4573c3c40c2ad1e30
);
else if (i == 11)
return
bytes32(
0x1bea3dec5dab51567ce7e200a30f7ba6d4276aeaa53e2686f962a46c66d511e5
);
else if (i == 12)
return
bytes32(
0x0ee0f941e2da4b9e31c3ca97a40d8fa9ce68d97c084177071b3cb46cd3372f0f
);
else if (i == 13)
return
bytes32(
0x1ca9503e8935884501bbaf20be14eb4c46b89772c97b96e3b2ebf3a36a948bbd
);
else if (i == 14)
return
bytes32(
0x133a80e30697cd55d8f7d4b0965b7be24057ba5dc3da898ee2187232446cb108
);
else if (i == 15)
return
bytes32(
0x13e6d8fc88839ed76e182c2a779af5b2c0da9dd18c90427a644f7e148a6253b6
);
else if (i == 16)
return
bytes32(
0x1eb16b057a477f4bc8f572ea6bee39561098f78f15bfb3699dcbb7bd8db61854
);
else if (i == 17)
return
bytes32(
0x0da2cb16a1ceaabf1c16b838f7a9e3f2a3a3088d9e0a6debaa748114620696ea
);
else if (i == 18)
return
bytes32(
0x24a3b3d822420b14b5d8cb6c28a574f01e98ea9e940551d2ebd75cee12649f9d
);
else if (i == 19)
return
bytes32(
0x198622acbd783d1b0d9064105b1fc8e4d8889de95c4c519b3f635809fe6afc05
);
else if (i == 20)
return
bytes32(
0x29d7ed391256ccc3ea596c86e933b89ff339d25ea8ddced975ae2fe30b5296d4
);
else if (i == 21)
return
bytes32(
0x19be59f2f0413ce78c0c3703a3a5451b1d7f39629fa33abd11548a76065b2967
);
else if (i == 22)
return
bytes32(
0x1ff3f61797e538b70e619310d33f2a063e7eb59104e112e95738da1254dc3453
);
else if (i == 23)
return
bytes32(
0x10c16ae9959cf8358980d9dd9616e48228737310a10e2b6b731c1a548f036c48
);
else if (i == 24)
return
bytes32(
0x0ba433a63174a90ac20992e75e3095496812b652685b5e1a2eae0b1bf4e8fcd1
);
else if (i == 25)
return
bytes32(
0x019ddb9df2bc98d987d0dfeca9d2b643deafab8f7036562e627c3667266a044c
);
else if (i == 26)
return
bytes32(
0x2d3c88b23175c5a5565db928414c66d1912b11acf974b2e644caaac04739ce99
);
else if (i == 27)
return
bytes32(
0x2eab55f6ae4e66e32c5189eed5c470840863445760f5ed7e7b69b2a62600f354
);
else if (i == 28)
return
bytes32(
0x002df37a2642621802383cf952bf4dd1f32e05433beeb1fd41031fb7eace979d
);
else if (i == 29)
return
bytes32(
0x104aeb41435db66c3e62feccc1d6f5d98d0a0ed75d1374db457cf462e3a1f427
);
else if (i == 30)
return
bytes32(
0x1f3c6fd858e9a7d4b0d1f38e256a09d81d5a5e3c963987e2d4b814cfab7c6ebb
);
else if (i == 31)
return
bytes32(
0x2c7a07d20dff79d01fecedc1134284a8d08436606c93693b67e333f671bf69cc
);
else revert("Índice fora dos limites");
}
}
O contrato tem 2 parâmetros iniciais. O nível da árvore e o endereço do contrato hasher MiMC.
O método privado hashLeftRight calcula o hash MiMC do par de elementos.
O método _insert insere um elemento e calcula a nova raiz de Merkle. A árvore armazena o histórico das últimas 30 raízes porque as transações Ethereum não são em tempo real. É possível que você envie sua prova de Merkle para a blockchain, mas antes de sua transação, alguém insere um novo elemento que altera a raiz de Merkle. Por causa do histórico, sua prova de Merkle ainda será válida, porque a raiz que você usou para sua prova está no histórico. Essa verificação de raiz é feita pelo método isKnownRoot.
Agora temos uma árvore de Merkle compatível com ZK, onde podemos armazenar os compromissos. Vejamos como podemos calcular uma prova de Merkle para nosso compromisso:
// calcula a raiz de Merkle a partir de elementos e um caminho para o elemento dado
export function calculateMerkleRootAndPath(mimc: any, levels: number, elements: any[], element?: any) {
const capacity = 2 ** levels
if (elements.length > capacity) throw new Error('A árvore está cheia')
const zeros = generateZeros(mimc, levels);
let layers = []
layers[0] = elements.slice()
for (let level = 1; level <= levels; level++) {
layers[level] = []
for (let i = 0; i < Math.ceil(layers[level - 1].length / 2); i++) {
layers[level][i] = calculateHash(
mimc,
layers[level - 1][i * 2],
i * 2 + 1 < layers[level - 1].length ? layers[level - 1][i * 2 + 1] : zeros[level - 1],
)
}
}
const root = layers[levels].length > 0 ? layers[levels][0] : zeros[levels - 1]
let pathElements = []
let pathIndices = []
if (element) {
const bne = BigNumber.from(element)
let index = layers[0].findIndex(e => BigNumber.from(e).eq(bne))
for (let level = 0; level < levels; level++) {
pathIndices[level] = index % 2
pathElements[level] = (index ^ 1) < layers[level].length ? layers[level][index ^ 1] : zeros[level]
index >>= 1
}
}
return {
root: root.toString(),
pathElements: pathElements.map((v) => v.toString()),
pathIndices: pathIndices.map((v) => v.toString())
}
}
Este método é do zktree.ts e calcula a prova de Merkle para o elemento fornecido. Para o cálculo da raiz de Merkle, precisamos dos elementos adicionados anteriormente e construímos a árvore de Merkle. Podemos ler essas informações da blockchain porque toda operação de inserção emite um evento Commit. O código abaixo coleta esses eventos e calcula a prova de Merkle a partir deles:
export async function calculateMerkleRootAndPathFromEvents(mimc: any, address: any, provider: any, levels: number, element: any) {
const abi = [
"event Commit(bytes32 indexed commitment,uint32 leafIndex,uint256 timestamp)"
];
const contract = new Contract(address, abi, provider)
const events = await contract.queryFilter(contract.filters.Commit())
let commitments = []
for (let event of events) {
commitments.push(BigNumber.from(event.args.commitment))
}
return calculateMerkleRootAndPath(mimc, levels, commitments, element)
}
Agora temos uma árvore de Merkle na blockchain, podemos inserir elementos nela e podemos gerar provas de Merkle no lado do cliente, então vamos ver a parte ZK:
// baseado em https://github.com/tornadocash/tornado-core/blob/master/circuits/merkleTree.circom
pragma circom 2.0.0;
include "../node_modules/circomlib/circuits/mimcsponge.circom";
// Calcula MiMC([esquerda, direita])
template HashLeftRight() {
signal input left;
signal input right;
signal output hash;
component hasher = MiMCSponge(2, 220, 1);
hasher.ins[0] <== left;
hasher.ins[1] <== right;
hasher.k <== 0;
hash <== hasher.outs[0];
}
// se s == 0 returna [in[0], in[1]]
// se s == 1 returna [in[1], in[0]]
template DualMux() {
signal input in[2];
signal input s;
signal output out[2];
s * (1 - s) === 0;
out[0] <== (in[1] - in[0])*s + in[0];
out[1] <== (in[0] - in[1])*s + in[1];
}
// Verifica se a prova de merkle está correta para determinada raiz de merkle e uma folha
// A entrada pathIndices é uma matriz de seletores 0/1 informando se determinado pathElement está no lado esquerdo ou direito do caminho de merkle
template MerkleTreeChecker(levels) {
signal input leaf;
signal input pathElements[levels];
signal input pathIndices[levels];
signal output root;
component selectors[levels];
component hashers[levels];
for (var i = 0; i < levels; i++) {
selectors[i] = DualMux();
selectors[i].in[0] <== i == 0 ? leaf : hashers[i - 1].hash;
selectors[i].in[1] <== pathElements[i];
selectors[i].s <== pathIndices[i];
hashers[i] = HashLeftRight();
hashers[i].left <== selectors[i].out[0];
hashers[i].right <== selectors[i].out[1];
}
root <== hashers[levels - 1].hash;
}
O circuito do validador de prova de Merkle também é copiado da fonte do Tornado Cash, como o próprio contrato da árvore de Merkle. O circuito faz iterações nos elementos de caminho e calcula a raiz de Merkle. Quando o eleitor vota, ele não precisa enviar a prova de Merkle para o contrato inteligente, apenas a raiz de Merkle, e a prova ZK de que ela pode calcular com sucesso a raiz usando este circuito e a prova de Merkle que é conhecida apenas por ela (esta é a parte privada do ZKP).
A última etapa é o método de geração de compromisso/anulador. Para garantir que um eleitor vote apenas uma vez, ele precisa enviar um anulador para a blockchain, que é registrado pelo contrato inteligente e pode ser usado apenas uma vez. O anulador deve ser exclusivo e atribuído ao compromisso. Assim, um compromisso tem apenas um anulador, mas por causa do ZKP, ninguém sabe (apenas o eleitor) qual anulador está atribuído a qual compromisso. O anulador é gerado pelo MiMC em zk-merkle-tree:
export async function generateCommitment() {
const mimc = await buildMimcSponge();
const nullifier = BigNumber.from(crypto.randomBytes(31)).toString()
const secret = BigNumber.from(crypto.randomBytes(31)).toString()
const commitment = mimc.F.toString(mimc.multiHash([nullifier, secret]))
const nullifierHash = mimc.F.toString(mimc.multiHash([nullifier]))
return {
nullifier: nullifier,
secret: secret,
commitment: commitment,
nullifierHash: nullifierHash
}
}
Como você pode ver, o compromisso é um hash do anulador e um segredo. A parte pública é o hash do anulador e o hash de compromisso, o segredo é privado. É fácil ver que, sem o segredo, ninguém pode vincular o compromisso ao anulador.
Vamos ver todo o circuito do validador:
pragma circom 2.0.0;
include "CommitmentHasher.circom";
include "MerkleTreeChecker.circom";
template Verifier(levels) {
signal input nullifier;
signal input secret;
signal input pathElements[levels];
signal input pathIndices[levels];
signal output nullifierHash;
signal output root;
component commitmentHasher = CommitmentHasher();
component merkleTreeChecker = MerkleTreeChecker(levels);
commitmentHasher.nullifier <== nullifier;
commitmentHasher.secret <== secret;
merkleTreeChecker.leaf <== commitmentHasher.commitment;
for (var i = 0; i < levels; i++) {
merkleTreeChecker.pathElements[i] <== pathElements[i];
merkleTreeChecker.pathIndices[i] <== pathIndices[i];
}
nullifierHash <== commitmentHasher.nullifierHash;
root <== merkleTreeChecker.root;
}
component main = Verifier(20);
O circuito é relativamente simples. O CommitmentHasher valida o compromisso e os hashes do anulador usando o anulador e o segredo como parâmetros privados. Se o compromisso for válido, ele valida a prova de Merkle fornecida na próxima etapa.
Agora temos tudo o que precisamos, então vamos juntar as coisas:
export async function calculateMerkleRootAndZKProof(address: any, provider: any, levels: number, commitment: any, zkey: any) {
const mimc = await buildMimcSponge();
const rootAndPath = await calculateMerkleRootAndPathFromEvents(mimc, address, provider, levels, commitment.commitment);
const { proof, publicSignals } = await snarkjs.groth16.fullProve(
{
nullifier: commitment.nullifier, secret: commitment.secret,
pathElements: rootAndPath.pathElements, pathIndices: rootAndPath.pathIndices
},
getVerifierWASM(),
zkey);
const cd = convertCallData(await snarkjs.groth16.exportSolidityCallData(proof, publicSignals));
return {
nullifierHash: publicSignals[0],
root: publicSignals[1],
proof_a: cd.a,
proof_b: cd.b,
proof_c: cd.c
}
}
Depois que o eleitor gera o compromisso, ele o envia para o contrato inteligente que o armazena na árvore de Merkle. Na fase de votação, ela usa o método calculateMerkleRootAndZKProof que calcula a prova de Merkle a partir dos eventos Commit que são emitidos pelo contrato inteligente. Este método calcula a prova de conhecimento zero e a converte na forma correta para o contrato inteligente do validador.
O contrato inteligente Validator é gerado a partir do circuito Validator pelo snarkjs. Pode ser feito pelo seguinte comando:
npx snarkjs zkey export solidityverifier build/Verifier.zkey contracts/Verifier.sol
Para obter mais informações, verifique o script prepare.sh e meu artigo anterior sobre o assunto.
O contrato ZKTree completo é assim:
// baseado em https://github.com/tornadocash/tornado-core/blob/master/contracts/Tornado.sol
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;
import "./MerkleTreeWithHistory.sol";
interface IVerifier {
function verifyProof(
uint[2] memory a,
uint[2][2] memory b,
uint[2] memory c,
uint[2] memory input
) external pure returns (bool r);
}
contract ZKTree is MerkleTreeWithHistory {
mapping(bytes32 => bool) public nullifiers;
mapping(bytes32 => bool) public commitments;
IVerifier public immutable verifier;
event Commit(
bytes32 indexed commitment,
uint32 leafIndex,
uint256 timestamp
);
constructor(
uint32 _levels,
IHasher _hasher,
IVerifier _verifier
) MerkleTreeWithHistory(_levels, _hasher) {
verifier = _verifier;
}
function _commit(bytes32 _commitment) internal {
require(!commitments[_commitment], "O compromisso foi submetido");
commitments[_commitment] = true;
uint32 insertedIndex = _insert(_commitment);
emit Commit(_commitment, insertedIndex, block.timestamp);
}
function _nullify(
bytes32 _nullifier,
bytes32 _root,
uint[2] memory _proof_a,
uint[2][2] memory _proof_b,
uint[2] memory _proof_c
) internal {
require(!nullifiers[_nullifier], "O anulador foi submetido");
require(isKnownRoot(_root), "Não consegue encontrar sua raiz de merkle");
require(
verifier.verifyProof(
_proof_a,
_proof_b,
_proof_c,
[uint256(_nullifier), uint256(_root)]
),
"Prova inválida"
);
nullifiers[_nullifier] = true;
}
}
O contrato é herdado do contrato MerkleTree e possui 3 parâmetros iniciais. O nível e o hasher para a árvore de Merkle e o endereço do contrato Verifier que é gerado pelo snarkjs do circuito Verifier.
O método _commit insere o compromisso na árvore de Merkle e emite o evento Commit para o cálculo da raiz de Merkle.
O método _nullify verifica se o anulador não é usado (um eleitor pode votar apenas uma vez), verifica a raiz pelo método isKnownRoot e verifica a prova de conhecimento zero.
Os métodos _commit e _nullify são abstratos, então você não pode usar o contrato ZKTree diretamente, você tem que herdar seu próprio contrato dele. Este contrato de nível superior será responsável pela validação do eleitor e registro dos votos.
Você pode encontrar uma implementação mínima no projeto zktree-vote (tenho um artigo completo sobre isso).
Em resumo, a implementação e o processo de votação são os seguintes:
- Você tem que implementar o contrato ZKTree e implantá-lo. Seu contrato será responsável pelo registro de eleitor e voto.
- O eleitor gera um compromisso pelo método generateCommitment e envia o compromisso para o contrato inteligente na fase de registro.
- Na fase de votação, o eleitor gera a prova de zero conhecimento pelo método calculateMerkleRootAndZKProof e a envia com o anulador para o contrato inteligente, que a verifica e registra o voto.
Isso é tudo. Espero que este artigo ajude você a entender como as provas de conhecimento zero podem ser usadas com JavaScript e Solidity (não apenas para votação).
Para obter mais informações, verifique o repositório zk-merkle-tree e o repositório zktree-vote, que é um exemplo de implementação da biblioteca.
Artigo escrito por Laszlo Fazekas e traduzido por Marcelo Panegali.
Top comments (0)