Low-overhead secret single-leader election

Sharding
1

TLDR: We present a simple secret single-leader election with a per-block overhead of one SNARK plus 32 bytes. (Related posts here, here, and here.) Thanks to Kobi Gurkan for helpful discussions.

Construction

Let g be an elliptic curve generator. Let v_1, ..., v_k be a list of validators to secretly shuffle for block proposals. Every validator v_i has a permanent public key pk_i as part of their validator record where pk_i = g^{sk_i} for some secret key sk_i. Let n be a nonce, e.g. an election period counter.

To participate in the election a validator v broadcasts (e.g. over Tor) an ephemeral public key epk and a corresponding SNARK proof p with:

  • public inputs: pk_1, ..., pk_k, n, epk
  • private inputs: sk, i
  • statement: pk_i = g^{sk} and epk = g^{H(sk, n)}

After sufficient time for the ephemeral public keys and proofs to be included onchain, the received ephemeral public keys are shuffled using onchain randomness into an ordered list. A validator v then signs the block at position j using the ephemeral secret key esk = H(sk, n) corresponding to the ephemeral public key at position j in the ordered list.

Onchain overhead

For concreteness we assume Groth16, the BLS12-381 pairing-friendly curve, and we let g be a Jubjub generator. The onchain overhead is as follows (where 32 bytes is the size of a compressed Jubjub point):

  • state: 32 bytes per validator for the permanent public keys
  • computation: ~3ms per block for the SNARK verification
  • data: 32 bytes per block for the ephemeral public keys plus 127 bytes for the SNARK data

Offchain overhead

Notice the circuit complexity is dominated by the single hash computation H(sk, n). If H is a SNARK-friendly hash function (e.g. MiMC) we expect the proving time to be ~0.1s on a commodity laptop. If H is SHA256 the proving is ~1s. In the context of Eth2 shard persistent committees, this proving time is marginal relative to the preparation time validators have prior to elections.

To benefit from a universal trusted setup one can use Sonic instead of Groth16. The main drawback is increased prover time by ~30x. (There are rumours of a ā€œSonic 2.0ā€ which may bring improvement to prover time. And in general the SNARK stackā€”proof systems, circuits, prover algorithms, hardwareā€”is rapidly improving.)

Finally, there is overhead from using a private network such as Tor to disseminate the ephemeral public keys and proofs. The concrete overhead is small because the corresponding messages are tiny.

9 Likes
2

This seems like part of the ever expanding class of problems which are solved if we had an accumulator that supports efficient batchable updates and zero knowledge proofs of membership.

4 Likes
4

To clarify, pk_i would be private when v_i broadcasts epk_i and the proof, correct? If so, it seems like the SNARK would need a proof of inclusion to privately show that pk_i was in the validator set, or maybe Iā€™m misunderstanding?

1 Like
5

One could achieve a moderate level of leader secrecy (eg. anonymity set 8-32) by just using a regular linkable ring signature or some bulletproof-based construction, right? And do we need anon sets larger than that?

2 Likes
6

Correct. More precisely, the validator index i corresponding to epk_i is private. Itā€™s why I chose the notation epk without being explicit about the index. Note that the actual values pk_1, ... pk_k are (as a group) public inputs.

Yes. This is done with the first part of the SNARK statement pk_i = g^{sk}. The SNARK is given the set of validator permanent public keys pk_1, ... pk_k as public inputs, and the specific index i as a private input. (The private input i is technically not necessary. I expect it may allow for a circuit optimisation which avoids looping through the pk_j by using a muxer to select pk_i.)

Right. Having said that, regular linkable ring signatures seem to have worse properties (e.g. larger and slower to verify proofs) than the proposed solution. I want to make more extensive literature research on ring signatures, but so far I could not find anything remotely close to 127+32 = 159 bytes of data and 3ms verification time per proof.

Take Monero as a proxy for evaluating ring signatures in practice. They have a dedicated ring signature research team and Iā€™m assuming they are using state of the art technology. As I understand, their ring size is limited to 11, their transactions are ~10kB in size, and the verification time is tens to hundreds of milliseconds (source here).

The main downside of the suggested construction from a performance standpoint is prover time. I expect we can easily get <1s (likely ~100ms) prover time. The good news is that, in our specific application, prover time is not critical because we can give validators hours of preparation time.

One thing to consider is that, in practice, there are ā€œheuristicsā€ that one can use to partially deanonymise the validator set. For example, one could analyse the timing of packets, and some validators may not even bother using Tor. So my initial gut feel is that 8 is on the low side and that 32 may be fine :slight_smile:

7

Oh I see. Yeah a MUX with 32 inputs should be extremely lightweight ā€“ just 5 constraints for splitting the index into bits, and 31 constraints for selecting inputs based on the index bits.

I think Merkle proofs would also be reasonable though. BLS12-381 is 255 bits, so the recommended number of MiMC rounds would be 161. Each round is 2 constraints, so 322 constraints per invocation. The additive variant Davies-Meyer would be ā€œfreeā€, so for a tree depth of 16, a Merkle proof would be (322 + 1) * 16 = 5168 constraints.

Sapling is ~100k constraints and was benchmarked at 2.3 seconds (not sure what kind of hardware was used), so I think a proof with 5168 constraints would take something like ~0.12 seconds.

MiMC requires \gcd(3, p - 1) = 1 for cubing to be a permutation, which isnā€™t the case with Zcashā€™s curve parameters, but you could generate new parameters, or use x^5 at the cost of an extra constraint per round.

I think Zcash wanted to avoid MiMC for now since itā€™s relatively new, but maybe the risk would be acceptable for this use case? It seems like the worst case scenario is that an attacker could take over consensus by registering many ephemeral public keys, but at least that could be detected and rolled back.

1 Like
8

Since the exponent 5 adds a 50% overhead (483 constraints per invocation instead of 322), it would be better to use LongsightL-161/p/3 instead of LongsightL-161/p/5 and generate new parameters for the curve as there is no obligation to use Zcash curve. Also, I have seen that Daira from Zcash had suggested to use the Rescue sponge permutation instead of Davies-Meyer as itā€™s more efficient.

Itā€™s also possible to use exponent 7 instead which is slightly more expensive, but requires fewer rounds. For example, ethsnarks uses exponent 7 with 91 as the number of rounds (instead of 161 in the previous case with exponent 3 or 5). This choice needs 4 constraints per round, so 91*4=364 per invocation when using a round-constants.

9

The Single Secret Leader Election Snark protocol proposed here suggests to do the following:

Protocol

  1. Generate N signature pairs pub/priv
  2. āˆ€ pair, we generate a SNARK (since participants have to send proof that they are eligible)
  3. We choose one party (hash h) to be the block proposer by picking the one at position m modulo number of participants.
  4. 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).

11

One thing that eludes most readings about SSLE is how to guarantee fairness:
" a leader should be elected in proportion to its stake / power in the network "
In this case, the shuffling will give uniform probability of being selected right ? It seems using a weighted RNG could bring us closer to get fairness, but the question on how to create the weighted list in the first place in zero knowledge seems tediousā€¦

Seems like thatā€™s what BEHG20 proposes for their DDH based scheme but itā€™s unclear how to do that zk ? Otherwise it seems it reveals the associated power, so it doesnā€™t sound anonymized at all. As well, I got the impression that it requires a drastically huge list now to get a fine grain level on the power.

1 Like