Implement merkle root chip/gadget for Poseidon

[parazyd]

[narodnik]

You can swap 2 items (the left and right values for the path) when you have a binary value b by doing:

new_left == b * left + (1 - b) * right
new_right == b * right + (1 - b) * left

b can only ever be 0 or 1 since it is a boolean value which is also something that must be enforced somewhere in the circuit using: (b - 0)(b - 1) == 0 or writing is another way: b^2 - b == 0. This polynomial is only 0 when b is 0 or 1.

[parazyd]

• https://zcash.github.io/halo2/user/simple-example.html
• https://github.com/darkrenaissance/darkfi/blob/master/src/zk/arith_chip.rs
• https://github.com/zcash/halo2/blob/main/halo2_proofs/examples/simple-example.rs
• https://zcash.github.io/halo2/design/gadgets/sinsemilla/merkle-crh.html
• https://docs.rs/halo2/0.1.0-beta.1/halo2/
• https://github.com/vocdoni/halo2-franchise-proof/blob/main/src/franchise.rs
• https://github.com/zcash/halo2/blob/main/halo2_gadgets/src/sinsemilla/merkle.rs
• https://github.com/zcash/halo2/blob/main/halo2_gadgets/src/sinsemilla/merkle/chip.rs

[narodnik]

I can't remember this issue? Is this still relevant?

[parazyd]

Nah we just use sinsemilla. The upstream gadget will eventually be generalized for different hashing algos.