Overview
Espresso developed a new ZK light client contract tailored for efficient verification of Hotshot consensus on the Ethereum blockchain. The scheme enables Hotshot to leverage consensus-friendly signatures, such as BLS aggregate signatures, optimizing for high throughput and low latency. On the other hand, the contract only needs to check a SNARK proof that verifies the correctness of a bunch of signatures. Notably, the signature used in the SNARK circuit can differ from those employed in the Hotshot consensus, enhancing SNARK-friendliness. As a result, without affecting the architecture of the underlying consensus, this approach significantly reduces the end-to-end proof generation time while maintaining cheap gas consumption per state update. (We will give a more detailed comparison in the table below.)
Background
Hotshot is the core consensus protocol underlying the Espresso network to achieve high throughput and fast finality. However, Ethereum users who do not participate in the Hotshot consensus still require an efficient means to monitor the consensus state. A common approach is to run a Hotshot light client in an Ethereum smart contract. Yet, naively running the client involves checking the authenticity of potentially hundreds to thousands of staking keys and then combining the staking keys together to verify an aggregate signature. This leads to excessive gas consumption. For example, given the gas estimate of BN curve addition and pairings and the Keccak hash function, the contract consumes more than 120,000 + n * (500 + 1000*log(n)) gas for checking n staking keys. Even with only 200 staking keys, this already accounts for 1.82 million gas. Even worse, one would have to compute a hash to group function over the G2 group for which Ethereum has no precompiles yet. This makes it even more infeasible to instantiate the aggregate signature solution.
An alternative approach that aims to alleviate gas consumption is letting a prover submit a succinct proof validating that the aggregated verification key is computed correctly and the signature verifies. Subsequently, the light client contract only needs to check the succinct proof, resulting in significantly improved gas efficiency. For example, a Halo2 Plonk verifier takes less than 320k gas to execute on the smart contract.
However, this alternative strategy places a heavy burden on the prover. Hotshot employs BLS aggregate signatures, optimizing for high throughput and low latency. With potentially hundreds to thousands of staking keys involved in the consensus, proof generation becomes more time-consuming. In particular, the proof generation requires simulating the correct additions of hundreds to thousands of elliptic curve points represented using a base field Fp. Yet, for short proofs, the circuit must operate over a scalar field Fr which is different from the base field Fp. This necessitates complex statements for proving each point addition, significantly increases the proof generation time (which also harms the user latency). For instance, assuming that there are 1,000 staking keys in the consensus, we estimate that the proof generation can take more than 80 minutes according to the benchmark from the Succinct Lab.
The Signature Switching Technique
The inefficiency stems from the fact that the succinct proof system (that supports constant-sized proof/verification, e.g., Plonk or Groth16) and the BLS signature both require pairings, while the Ethereum only supports a single pairing curve, specifically the BN curve. Consequently, the prover must emulate signature verifications over a different field, leading to inefficiencies. However, in the cryptography world, there do exist efficient pairing-free signatures, such as Schnorr signatures. By employing Schnorr signatures, we can exploit a key property of the BN curve: the existence of another efficient pairing-free curve known as the BabyJubjub curve, whose base field matches the scalar field of the BN curve. Thus, we can implement Schnorr signatures using the BabyJubjub field while employing the BN curve for the proof system. This enables the signature verification process to be represented directly in the scalar field of the BN curve, resulting in a significantly more efficient proving algorithm. In particular, we emphasize that natively simulating Schnorr signature verifications is always more efficient than non-natively simulating the BLS key aggregations and the aggregate signature verification in the SNARK circuit, no matter how large the consensus validator size is.
Unfortunately, unlike BLS signatures, Schnorr signatures do not support efficient aggregations, which are crucial for achieving high throughput and low latency in the Hotshot consensus. Consequently, a natural question arises: can we retain the use of BLS signatures in Hotshot for high throughput and low latency, while utilizing a more SNARK-friendly signature (such as the Schnorr signature) when computing the ZK light client proof?
The answer is affirmative. Our scheme requires minimal modifications to the underlying consensus protocol; Hotshot can continue employing BLS signatures for consensus efficiency. Meanwhile, the ZK client prover can operate using a different, more SNARK-friendly signature (e.g., the Schnorr signature).
For simplicity, we assume an altruistic, honest prover, although we could extend the design to incorporate a decentralized prover market. In this scheme, each honest consensus node, upon receiving a new quorum certificate, not only participates in the consensus voting but also temporarily stores a corresponding Schnorr signature. The prover then retrieves a sufficient number of Schnorr signatures from the network and efficiently computes a succinct proof to validate the correctness of these signatures. Subsequently, the ZK light client contract can verify the succinct proof efficiently. Essentially, under the same honest majority assumption from Hotshot, we can argue that the prover can fetch sufficiently many Schnorr signatures if and only if the consensus state is finalized (i.e., sufficiently many BLS signatures were collected). Therefore, the light client contract can safely update the consensus state.
Table for performance comparison
We roughly estimate the proof generation time and gas consumption of various solutions, including our scheme, the Succinct Lab’s solution, and the naive approach of verifying staking keys and signatures in smart contracts without SNARKs. The gas cost of our contract is dominated by the Plonk proof verification (590K). This is higher than Halo2’s Plonk verifier contract’s gas cost, and we could potentially achieve the same level of efficiency by applying further optimizations. We chose to keep the current implementation for simplicity and clarity of the contract.
Future Work
Our current solution is well-suited for applications with no more than a few thousand consensus nodes. However, the proof generation time is linear to the number of nodes, making it hard to scale to potentially hundreds of thousands of nodes. One option to accelerate proof generation could be using a threshold signature where the SNARK proof only needs to prove the correctness of a single signature verification. However, threshold signatures require the consensus committee to run a distributed key generation (DKG) protocol whenever the committee changes, which is still quite expensive. It is an interesting open problem on how to efficiently prove large-scale dynamic consensus without frequently running expensive DKG protocols.