zk-merkle-tree库: 使用 zkSNARK 在以太坊上进行匿名投票
- 翻译小组
- 更新于 2023-11-15 08:44
- 阅读 2635
zk-merkle-tree 库: 使用 zkSNARK 在以太坊上进行匿名投票
照片由Kristina Flour在Unsplash拍摄
在投票中保持匿名性是基本要求之一，但在像区块链这样的公共网络上，实现它并不是一件简单的事情。幸运的是，零知识证明（ZKP）技术使这成为可能，但不幸的是，ZKP是一项非常复杂的技术。这就是我构建 zk-merkle-tree 的原因，它是一个JavaScript库，几乎隐藏了 zkSNARK 的所有复杂性。
还有其他类似解决方案的库，比如 semaphore。zk-merkle-tree 的优势在于它非常简单。我还有一个示例项目，你可以在其中看到如何在自己的项目中使用它。
在本文中，我将逐步展示我是如何基于硬币混合应用程序 Tornado Cash 的源代码构建了这个库，因此本文不仅是一个库介绍，还是一个关于如何构建基于通用zkSNARK的应用程序的教程。
我之前有关于零知识证明和zkSNARK的文章。强烈建议在阅读本文之前阅读它们，因为本文是基于它们的。
我想首先谈谈哈希。在以太坊世界中，我们使用SHA算法的变体（如SHA-256、Keccak-256等）进行哈希。不幸的是，使用这些算法进行ZKP计算是昂贵的，因此我们必须使用ZK友好的哈希。有一些ZK友好的算法，比如MiMC和Pedersen，它们被Tornado Cash（也是zk-merkle-tree）使用，或者Semaphore使用的Poseidon。这些哈希可以在ZK电路中计算更便宜，但在区块链上比SHA变体稍微昂贵一些。
Tornado Cash和zk-merkle-tree使用MiMC哈希来构建默克尔树。Circomlib.js包含了它的实现以及一个智能合约生成器，你可以使用它部署到区块链上。
const MiMCSponge = new ethers.ContractFactory(
mimcSpongecontract.abi,
mimcSpongecontract.createCode(SEED, 220),
signers[0]
)
mimcsponge = await MiMCSponge.deploy()上面的代码来自zktree_test.ts，并使用ethers将MiMC哈希合约部署到区块链上。
JS端的哈希器可以通过以下方式生成：
mimc = await buildMimcSponge();你可以通过以下代码测试你的合约：
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));第一行通过使用智能合约计算哈希，第二行也通过JS函数计算哈希。唯一有趣的部分是通过F.toString进行的数字转字符串转换。在zk-SNARK中，每个计算都是在有限域中进行的，因此我们必须使用mimc.F.toString进行转换。
现在我们可以计算ZK友好的MiMC哈希，所以一切准备就绪，可以构建默克尔树了。Solidity 树的实现完全参考TornadoCash ：
// based on 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;
// the following variables are made public for easier testing and debugging and
// are not supposed to be accessed in regular code
// filledSubtrees and roots could be bytes32[size], but using mappings makes it cheaper because
// it removes index range check on every interaction
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 should be greater than zero");
require(_levels < 32, "_levels should be less than 32");
levels = _levels;
hasher = _hasher;
for (uint32 i = 0; i < _levels; i++) {
filledSubtrees[i] = zeros(i);
}
roots[0] = zeros(_levels - 1);
}
/**
@dev Hash 2 tree leaves, returns MiMC(_left, _right)
*/
function hashLeftRight(
uint256 _left,
uint256 _right
) public view returns (bytes32) {
require(
_left < FIELD_SIZE,
"_left should be inside the field"
);
require(
_right < FIELD_SIZE,
"_right should be inside the field"
);
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,
"Merkle tree is full. No more leaves can be added"
);
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 Whether the root is present in the root history
*/
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 Returns the last root
*/
function getLastRoot() public view returns (bytes32) {
return roots[currentRootIndex];
}
/// @dev provides Zero (Empty) elements for a MiMC MerkleTree. Up to 32 levels
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("Index out of bounds");
}
}合约有两个初始参数。树的层级和 MiMC 哈希器合约的地址。
hashLeftRight 私有方法计算元素对的 MiMC 哈希。
_insert 方法插入一个元素并计算新的默克尔树根。树存储了最后30个根的历史记录，因为以太坊交易不是实时的。你可能在发送默克尔树证明到区块链之前，有人插入了一个新元素，改变了默克尔树根。由于有历史记录，你的默克尔树证明仍然有效，因为你用于证明的根在历史记录中。这个根的检查是通过isKnownRoot方法完成的。
现在我们有了一个ZK友好的默克尔树，我们可以在其中存储承诺。让我们看看如何为我们的承诺计算一个默克尔树证明：
// calculates Merkle root from elements and a path to the given element
export function calculateMerkleRootAndPath(mimc: any, levels: number, elements: any[], element?: any) {
const capacity = 2 ** levels
if (elements.length > capacity) throw new Error('Tree is full')
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())
}
}这个方法来自zktree.ts，并为给定的元素计算了默克尔树证明。对于默克尔树根的计算，我们需要先前添加的元素并构建默克尔树。我们可以从区块链中读取这些信息，因为每次插入操作都会发出一个 Commit 事件。下面的代码收集这些事件，并从中计算默克尔树证明：
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)
}现在我们在区块链上有了一个默克尔树，可以向其中插入元素，并且可以在客户端生成默克尔树证明，让我们看看ZK部分：
// based on https://github.com/tornadocash/tornado-core/blob/master/circuits/merkleTree.circom
pragma circom 2.0.0;
include "../node_modules/circomlib/circuits/mimcsponge.circom";
// Computes MiMC([left, right])
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];
}
// if s == 0 returns [in[0], in[1]]
// if s == 1 returns [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];
}
// Verifies that merkle proof is correct for given merkle root and a leaf
// pathIndices input is an array of 0/1 selectors telling whether given pathElement is on the left or right side of merkle path
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;
}Merkle proof validator circuit 也是从 Tornado Cash 的源代码中复制的，就像默克尔树合约本身一样。该电路对路径元素进行迭代并计算默克尔树根。当选民投票时，她不必将默克尔树证明发送到智能合约，只需发送默克尔树根和可以成功使用此电路和仅她知道的默克尔树证明（这是ZKP的私有部分）计算根的ZK证明。
最后一步是承诺/nullifier生成方法。为了确保一个选民只投一次票，她必须向区块链发送一个 nullifier ，由智能合约注册，并且只能使用一次。nullifier 必须是唯一的，并且分配给承诺。因此，一个承诺只有一个 nullifier ，但由于 ZKP 的存在，没有人知道（只有选民知道）哪个 nullifier 分配给哪个承诺。在 zk-merkle-tree 中，nullifier 标记是由 MiMC 生成的：
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
}
}正如你所看到的，承诺是nullifier和秘密的哈希。公共部分是nullifier和承诺哈希的哈希，秘密是私有的。很容易看出，没有秘密，没有人可以将承诺与 nullifier 关联起来。
让我们看看整个验证器电路：
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);电路相对简单。CommitmentHasher 通过使用 nullifier 和秘密作为私有参数验证承诺和 nullifier 的哈希。如果承诺有效，它将在下一步验证给定的默克尔树证明。
现在我们拥有了一切所需的东西，让我们把事情放在一起：
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
}
}选民生成承诺后，将其发送到存储在默克尔树中的智能合约。在投票阶段，选民使用 calculateMerkleRootAndZKProof 方法，该方法从智能合约发出的Commit事件中计算默克尔树证明。该方法计算零知识证明并将其转换为验证器智能合约的正确形式。
验证器智能合约是由 snarkjs 从验证器电路生成的。可以通过以下命令完成：
npx snarkjs zkey export solidityverifier build/Verifier.zkey contracts/Verifier.sol有关更多信息，请查看prepare.sh脚本，以及我关于该主题的先前文章。
完整的ZKTree合约如下：
// based on 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], "The commitment has been submitted");
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], "The nullifier has been submitted");
require(isKnownRoot(_root), "Cannot find your merkle root");
require(
verifier.verifyProof(
_proof_a,
_proof_b,
_proof_c,
[uint256(_nullifier), uint256(_root)]
),
"Invalid proof"
);
nullifiers[_nullifier] = true;
}
}该合约继承自 MerkleTree 合约，有 3 个初始参数。默克尔树的层级和哈希器，以及由snarkjs从验证器电路生成的Verifier合约的地址。
_commit 方法将承诺插入到默克尔树中，并发出用于计算默克尔树根的Commit事件。
_nullify 方法检查 nullifier 是否被使用（一个选民只能投一次票），通过isKnownRoot方法检查根，并验证零知识证明。
_commit和_nullify方法是抽象的，因此你不能直接使用ZKTree合约，你必须继承它，实现你自己的合约。这个顶层合约将负责选民验证和投票注册。
你可以在zktree-vote项目中找到一个最小的实现（我有一篇关于完整文章）。
总之，实现和投票过程如下：
- 你必须实现ZKTree合约并部署它。你的合约将负责选民和投票注册。
- 选民通过 generateCommitment 方法生成承诺，并在注册阶段将承诺发送到智能合约。
- 在投票阶段，选民通过 calculateMerkleRootAndZKProof 方法生成零知识证明，并将其与nullifier一起发送到智能合约，智能合约验证并注册投票。
就是这样。希望本文能帮助你了解如何使用JavaScript和Solidity（不仅仅是用于投票）使用零知识证明。
有关更多信息，请查看zk-merkle-tree存储库，以及zk-merkle-tree存储库，这是该库的一个示例实现。
本翻译由 DeCert.me 协助支持， 在 DeCert 构建可信履历，为自己码一个未来。
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。
