-
Notifications
You must be signed in to change notification settings - Fork 4
/
verify-merkle-path.circom
51 lines (40 loc) · 1.6 KB
/
verify-merkle-path.circom
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Credit Sismo: https://github.com/sismo-core/hydra-s1-zkps/blob/main/circuits/common/verify-merkle-path.circom
// Highly inspired from tornado cash https://github.com/tornadocash/tornado-core/tree/master/circuits
pragma circom 2.0.0;
include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/bitify.circom";
include "circomlib/circuits/comparators.circom";
// if s == 0 returns [in[0], in[1]]
// if s == 1 returns [in[1], in[0]]
template PositionSwitcher() {
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 path is correct for a given merkle root and 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 VerifyMerklePath(levels) {
signal input leaf;
signal input root;
signal input pathElements[levels];
signal input pathIndices[levels];
component selectors[levels];
component hashers[levels];
signal computedPath[levels];
for (var i = 0; i < levels; i++) {
selectors[i] = PositionSwitcher();
selectors[i].in[0] <== i == 0 ? leaf : computedPath[i - 1];
selectors[i].in[1] <== pathElements[i];
selectors[i].s <== pathIndices[i];
hashers[i] = Poseidon(2);
hashers[i].inputs[0] <== selectors[i].out[0];
hashers[i].inputs[1] <== selectors[i].out[1];
computedPath[i] <== hashers[i].out;
}
root === computedPath[levels - 1];
}
component main = VerifyMerklePath(32);