Analysis of Aleo Testnet3 Algorithm for provers

The Aleo team recently launched Testnet3 where provers will have to solve coinbase puzzles to earn credits.   This is vastly different from the Proof of Succint Work (PoSW) algorithm of Testnet2.

In this paper, we will introduce the principles behind the Testnet2 and Testnet3 algorithms and discuss the differences between them.

First, a brief introduction of the terms used:

Testnet

When discussing Aleo's testnets, we are referring to Testnet2 (https://www.aleo.org/post/incentivized-testnet-announcement) and Testnet3 (https://www.aleo.org/post/announcing-testnet-3).   

Testnet2 has ended.   Testnet3 has 3 phases:   Phase 1 is for developers, and was recently launched; Phase 2 is for provers where mining rewards will be awarded.

Prover

Aleo's provers, also known as miners, are responsible for providing computng equipment, executing algorithms specified by the blockchain, and in return earn mining rewards.   Testnet2 used the Proof of Succint Work (PoSW) algorithm; while Testnet3 will be using the coinbase puzzle algorithm.   Do note that this "coinbase" refers to a blockchain token database, and not the US-listed crypto exchange Coinbase.

Hashrate unit

Hashrate is a measure of the computing power on a blockchain network.   Hashrate is determined by the number of proofs that can be generated per unit of time.   In the case of Aleo, hashrate is measured by the number of zero-knowledge Proofs generated Per Second (PPS).   The higher the PPS, the higher the computing power and the more coins are produced.   Every prover aims to produce the highest computing power at the lowest cost.

The principle behind Testnet2 PoSW algorithm

Testnet2 uses the PoSW algorithm which is based on the Marlin protocol.   The Marlin protocol consists of multi-scalar multiplication (MSM) and fast-fourier transforms (FFT).

Provers earn rewards by generating valid zero-knowledge proofs.   Every proof generation is made up of 3 steps:   generate proofs, validate proofs, generate blocks.   Step 1 is the most intensive; involving 11 iterations of FFT+MSM, complex logic, and high resource consumption.   FFT consumes CPU resources; and MSM, which accounts for 70%, consumes CPU and GPU resources.

Here are the related codes, let us analyze it.

Branch: https://github.com/AleoHQ/snarkVM/commits/testnet2

commit id:3887cbbe73dc961c2fe80641b7a70424a743d7c5

The PoSW of TestNet2 uses the Marlin algorithm.   The main entry is under dpc/src/posw:

<prove_with_terminator> is used to generate the proof of PoSW.   When you study the codes, you will find that the implementation of <prove_with_terminator> is very complex, and the codes are very verbose and long.   This is because the Marlin algorithm in itself is very complex.   If you continue to study the codes, you will see 11 iterations of MSM.   Let us extract part of the codes to show you.   See below for an example of a single MSM iteration.

The principle behind Testnet3 algorithm

In the core algorithm for Testnet3, consensus block generation is no longer required.   Provers only need to generate proof and verify proof.

Coinbase only needs to calculate the MSM 3 times for each proof; each MSM has a polynomial length of 2^13 power.

In comparison, the PoSW algorithm used in Testnet2 computes the MSM 11 times; each MSM has a polynomial length of 2^15.

Here are the algorithm change codes, let us analyze it.

Branch: https://github.com/AleoHQ/snarkVM/commits/testnet3

commit id:eeaa9243b7a23cb329cb723e48c4bbe714e1fb9c

The core of the coinbase puzzle implementation of Testnet3 is in the synthesizer/coinbase_puzzle directory of the snarkvm code. The main implementation screenshots of the prover generation proof are as follows:

KZG 10::c ommit_lagrange and KZG 10:: open_lagrange are the key two steps to generate prover to generate coinbase puzzle proofs. If you trace it, open_lagrange will call commit_lagrange. Let's see commit_lagrange implementation:

MSM only needs to be called twice to generate the commitment required by coinbase puzzle.   A total of 4 MSM is called, compared to 11 in Testnet2.   This greatly reduces the amount of computing power required.

Another key change that reduces the computation effort is that the length of the polynomial parameter passed in for the MSM computation is smaller, at 2 ^ 13.   The code is defined as follows:

This also reduces the computation of a single MSM to a quarter of the MSM computation used by Testnet2's PoSW algorithm!

From the above, we can clearly see that the computational resources required for Testnet3 algorithm is much lower than that of Testnet2.   Simply by switching from Testnet2 to Testnet3, and with no other changes, the same hardware equipment will perform better and deliver higher computing power.

We must emphasize that Aleo is still in a highly active development stage.   Proof algorithm for provers will continue to evolve until the launch of the mainnet.

However, it is important to know that no matter how the algorithm changes, the speed of proof generation can always be improved.   Our expert R&D team continues to improve the speed of proof generation, through on-chip acceleration and code optimization.   Our proactive efforts to improve computing efficiency propels our solutions way ahead of others who have not made any improvements to their software and hardware solutions.

Our team will continue to monitor and support Aleo's development and progress; and we will continue to share our analysis and professional views so as to help more people enter the Aleo ecosystem.