Introducing Provers in Aleo Testnet 3

We’re excited to announce Phase 2 of Aleo Testnet 3! In this release, we will be deploying many of the key features outlined in our original roadmap for Testnet 3, such as deploying and executing user-defined programs, as well as a puzzle for incentivizing the development of hardware for zkSNARK proving.

What is Aleo?

Aleo is a new layer-1 blockchain that leverages zero-knowledge cryptography to enable scalable and private decentralized applications. In our architecture, applications are not executed on-chain; rather, users execute the application off-chain, and publish to the chain zkSNARKs (short zero-knowledge proofs) that attest to the correctness of the execution in a privacy-preserving manner. The chain then verifies these short proofs in time that is *independent* of the running time of the application. This plan works well, except for one hiccup: creating a zero-knowledge proof of correct application execution can be *much* more expensive than just directly executing the application. For many useful programs (e.g. payments), this overhead is manageable, even when proving on a commodity device such as a mobile phone or a laptop. However, for other, more compute-intensive applications such as machine learning, gaming, or authentication, the overhead of proving on commodity devices might be prohibitive, seemingly rendering these use cases out of reach.

However, Aleo’s design allows clients a choice of whether to outsource proof generation to a third-party “proving service” that may have more computational resources to help with computing zkSNARKs for large computations, such as CPUs with many cores, large amounts of RAM, or even custom proving hardware. The problem then becomes one of incentivizing the development of better architectures of proving. Solving this latter problem is one of the key motivations behind the design of Aleo’s new consensus algorithm, AleoBFT. At a high level, AleoBFT is a hybrid architecture that leverages proof-of-stake to achieve instant finality for block confirmation, and leverages a proof-of-work-type “coinbase puzzle” that rewards the development of faster techniques for proof generation. In this post, we will dive a bit deeper into the details of this puzzle.

The Coinbase Puzzle

The coinbase puzzle is a proof-of-work-type puzzle that is intended to incentivize the development of faster software and hardware for generating zero-knowledge proofs. To achieve this, our coinbase puzzle has two unique features: - Cryptographic: Unlike a traditional PoW like you’ll find in Bitcoin or Ethereum, the coinbase puzzle requires creating efficient routines for “useful” algorithms for the main subcomponents of zkSNARK proving.

- Economic: Unlike a traditional PoW, where each block can contain only one valid puzzle solution, our coinbase puzzle accepts multiple valid solutions per block, preventing a “winner-takes-all” and leading to a more widespread distribution of proving rewards.

Let’s dive a bit deeper into the puzzle design, starting with the cryptographic portion:

Puzzle Design

A quick primer on zkSNARK design: The time to generate a proof in modern zkSNARKs is dominated by the proving time of two sub components: a polynomial IOP, and a polynomial commitment scheme. Our coinbase puzzle efficiently incentivizes speeding up exactly these subcomponents. Let’s see how it does this by looking at the protocol flow, which consists of two steps:

1) Generating candidate solutions (Prover) To generate a candidate solution, the prover generates (from a nonce) and multiplies a random looking polynomial, and then commits to the resulting product polynomial via a polynomial commitment scheme (the KZG10 scheme, in our case). This resulting commitment is then hashed, and if this hash matches the target difficulty, it is a valid solution that can be sent to the aggregator (along with an evaluation proof to enable efficient aggregation). The resulting puzzle consists of 2 group elements and 1 field element, an address, and a nonce, and can be verified in D field multiplications and a pairing, where D is the degree of the generated polynomial.

2) Aggregating valid solutions (BFT Leader) While a valid puzzle solution can be verified by anybody as is, adding every puzzle solution to the chain would result in state bloat. To avoid this, our coinbase puzzle enables the BFT leader to aggregate valid solutions. We won’t go into the details of how this is done, but the overall result is that on-chain storage is dominated by the cost of n + 1 group elements, and 1 field element is a substantial improvement. As a side benefit, puzzle verification is also faster.

Conclusion

AleoBFT is a novel consensus mechanism that combines the finality of proof-of-stake with the powerful incentive mechanism of proof-of-work. In our case, the coinbase puzzle incentivizes acceleration of zkSNARK proving. This work is useful because it carries over directly to every other program execution in Aleo. With this mechanism, we hope to incentivize a strong proving ecosystem which benefits Aleo users by reducing costs and decreasing latency for program execution.

One final note: this phase of the testnet will be incentivized. However, the publication of this blog post does not signify the start of the incentive program. Please join our community on Discord and follow us on Twitter to receive the latest updates about the timeline for incentives.