[Circuits] Alternatives to T7 and above

[ChihChengLiang]

Summary of discussion with @weijiekoh yesterday.

What's wrong

The circomlib assembly evm code supports up to Poseidon T6. To hash more than 5 items, we either need to implement new evm code or hash items with only T6.

How can we fix that

Currently, we have objects "Message" and "vote options" that need hashing more than 5 items. For vote options, since we expect supporting up to 2**10 of options, we build a merkle tree for it.

Poseidon t	number of elements	Use cases
t = 3	2	Build Merkle tree with HashLeftRight
t = 6	5	Hash stateLeaf

To hash 11 items in message, there are two options we can explore.

Option 1:

Hasher2(
    Hasher2 (
        Hasher5(a1, a2, a3, a4, a5),
        Hasher5(a6, a7, a8, a9, a10)
    ),
    a11
)

Option 2 (@kobigurk's proposal):

c= 0
out1_1, out1_2,out1_3,  out1_4, out1_5, c' = permutation6(a1,a2,a3,a4,a5, c)
out2_1, out2_2,out2_3,  out2_4, out2_5, c'' =permutation6(a6,a7,a8,a9,a10, c')
out_final, _, _, _, _, _ = permutation6(out1_1,out2_1,a11, 0, 0, c'')

Where permutation6 is Poseidon t=6, but we output all elements in the state, instead of only the first element.

SubTasks

• A README to explain Poseidon.
• Implement the circuit
• Gas cost benchmarking and number of constraints
  • for state update tree, and
  • the quad vote tally tree

[weijiekoh]

Thanks for this!

I'm currently modifying the codebase to use a Merkle tree to compute the vote tally commitment.

#89

It still uses MiMC but we can merge it into your branch and use PoseidonT3 later.