The Single Secret Leader Election Snark protocol proposed here suggests to do the following:
Protocol
- Generate N signature pairs pub/priv
- ∀ pair, we generate a SNARK (since participants have to send proof that they are eligible)
- We choose one party (hash h) to be the block proposer by picking the one at position m modulo number of participants.
- The party that was chosen will publish the sig that proves they are the right person.
The other parties verify the sig to verify if the msg m was actually signed by the corresponding private key.
The circuit verifies:
- that the leaf exists within the merkle tree
assert root == merkle_authenticate(path_var, address_bits, leaf_hash)
- that prover knows the secret (signature) for that hash
assert eddsa_verify(pk, m, signature)
- that prover signed the message m (random beacon)
assert hash == H(signed(m))
Circuit complexity
The circuit complexity is dominated by the single hash computation (preimage proof) + merkle proof + signature verification. We can reduce the overhead of the circuit by hashing multiple public inputs into a single variable because the cost of hashing data on-chain is less than each public input. Each hashed input costs 20k gas, whereas every public SNARK input costs 40k gas.
Merkle proof
The hash function MiMC operates over a prime field rather than on bytes and bits and offers the following advantages:
- Minimal multiplicative complexity
- MIMC reduces the number of constraints for a whole merkle tree proof down to fewer than it needs to perform 1 SHA256 operation.
- Easier to work with than Pedersen hashes.
- MIMC let us do potentially transactions per second rather than seconds per transaction.
- Reduces the memory overhead.
- MIMC offers a factor of 10 improvement ( MiMC takes ≈ 7.8 ms while SHA-256 takes ≈ 73 ms)
If we were to use BLS12-381 or Baby_JubJub which is built on top of alt_bn128 in ETHSnarks where each has 255 bits, so the recommended number of MiMC rounds would be 161 with exponent 3.
As I have mentioned in my previous comment, It’s also possible to use exponent 7 instead which is slightly more expensive, but requires fewer rounds so 91 instead of 161. This choice needs 4 constraints per round, so 91*4=364 per invocation when using a round-constants.
For a tree depth of 16, a Merkle proof would be (364 + 1) * 16 = 5840 constraints.
We can also reduce the hashing down to under 100 constraints by using poseidon hash function family instead.
Signature verification
The eddsa (Ed25519) has the following advantages over other signature schemes:
- Avoid side-channel attacks on signing.
- Avoid attacks on ECDSA based on not-perfectly-random nonces
- Reduce reliance on collision resistance for the message hashing
- Small public keys (32 bytes), small private keys(32 bytes) and small signatures(64 bytes) with high security level at the same time (128-bit).
- The EdDSA algorithm is slightly faster than ECDSA.
Checking is a signature is valid for eddsa (with baby jubjub curve) takes about ~10k constraints in ethsnarks, from which 1881 constraints for the Pedersen hash used. There are several checks that we can dismiss to optimise the verification time like checking if a point is on a curve and is not of low order which currently takes 5415 constraints which would leave us with 7000 constraints plus the hash complexity.
Preimage proof
By using MIMC function, we avoid the bits<->field-element conversion at every step, if the initial input is bits it requires one constraint (in addition to validating that the inputs are bits), but the whole chain avoids an extra ~255 constraints at every level because no additional checks are required at each step especially in the case of Merkle proof.
The total complexity of preimage proof is 366 constraints
def preimage_check(Hash,M):
compute H(M) # 364 constraints using MIMC
Hash == H(M) # 2 constraints
** Proving time **
The total complexity is 364 + 10k + 5840 = 16204 constraints (before applying optimisation to eddsa verification). On a laptop with 8 GB of ram proofs can be made in ~2 to 3 seconds which is less than the slot period (6 seconds).