1. 引言

前序博客有：

• Polygon zkEVM中的Merkle tree
• Polygon zkEVM中Goldilocks域元素circom约束

代码见：

• https://github.com/0xPolygonHermez/pil-stark/tree/main/circuits.gl

2. Poseidon哈希circom约束

3. LinearHash circom约束

template LinearHash(nInputs, eSize) {signal input in[nInputs][eSize]; //输入in元素数为nInputs*eSizesignal output out[4];var nHashes;if (nInputs*eSize <= 4) {nHashes = 0;} else {nHashes = (nInputs*eSize - 1)\8 +1;}component hash[nHashes];if (nInputs*eSize <= 4) {var curI=0;var curE=0;for (var i=0; i<4; i++) {if (i0) {hash[i].capacity[k] <== hash[i-1].out[k];} else {hash[i].capacity[k] <== 0;}}}for (var k=0; k<4; k++) {out[k] <== hash[nHashes-1].out[k];}}
}

4. Merkle tree circom约束

template Merkle(nLevels) { //nLevels表示树高度signal input value[4]; //叶子节点数据对应4个Goldilocks元素signal input siblings[nLevels][4]; //每个节点哈希值对应4个Goldilocks元素signal input key[nLevels]; //key数组表示所在各层的位置signal output root[4];component hash[nLevels];for (var i=0; i0) {hash[i].in[k  ] <== key[i]*(siblings[i][k]   - hash[i-1].out[k]) + hash[i-1].out[k];hash[i].in[k+4] <== key[i]*(hash[i-1].out[k] - siblings[i][k]  ) + siblings[i][k];} else {hash[i].in[k] <== key[i]*(siblings[i][k]   - value[k]        ) + value[k];hash[i].in[k+4] <== key[i]*(value[k]         - siblings[i][k]  ) + siblings[i][k];}hash[i].capacity[k] <== 0;}}for (var k=0; k<4; k++) {root[k] <== hash[nLevels-1].out[k];}}

5. MerkleHash circom约束

MerkleHash本质为：以values、siblings、key为输入，以root为输出，验证相应的Merkle证明与root是否匹配。
以 s0_merkle1[q] = MerkleHash(1, 2, 2048)=MerkleHash(eSize, elementsInLinear, nLinears) 为例：

• 1）eSize：表示单个数据所需的Goldilocks元素数
• 2）elementsInLinear：表示叶子节点对应的数据数
• 3）nLinears：表示Merkle树中总的节点树

template MerkleHash(eSize, elementsInLinear, nLinears) {var nBits = log2(nLinears); //2^11=2048，nBits为Merkle树高度assert(1 << nBits == nLinears); //要求nLinears为2的某幂次运算signal input values[elementsInLinear][eSize]; //values[2][1]signal input siblings[nBits][4]; //Merkle证明路径，每个节点为哈希值对应4个Goldilocks元素。signal input key[nBits];  //key数组表示所在各层的位置signal output root[4];//对 叶子节点下原始数据进行处理，为4个Goldilocks元素。component linearHash = LinearHash(elementsInLinear, eSize);for (var i=0; i

template TreeSelector(nLevels, eSize) {var n = 1 << nLevels;signal input values[n][eSize];signal input key[nLevels];signal output out[eSize];signal im[n-1][eSize];var levelN = n\2;var o = 0;var lo = 0;for (var i=0; i