# The Aleo Whitepaper [For a16z] Howard Wu (October 29, 2023) <!-- LaTeX Commands --> $\newcommand{\target}{\mathsf{target}_\mathsf{coinbase}} \newcommand{\prooftarget}{\mathsf{target}_\mathsf{proof}} \newcommand{\puzzletarget}{\mathsf{target}_\mathsf{puzzle}} \newcommand{\anchortarget}{\mathsf{target}_\mathsf{anchor}} \newcommand{\anchortime}{\mathsf{time}_\mathsf{anchor}} \newcommand{\anchortimestamp}{\mathsf{timestamp}_\mathsf{anchor}} \newcommand{\anchorreward}{\mathsf{reward}_\mathsf{anchor}} \newcommand{\startingsupply}{\mathsf{supply}_\mathsf{starting}} \newcommand{\factor}{\mathsf{factor}} \newcommand{\timeout}{\mathsf{timeout}_\mathsf{round}} \newcommand{\Propose}{\mathsf{Propose}} \newcommand{\Timeout}{\mathsf{Timeout}} \newcommand{\Vote}{\mathsf{Vote}} \newcommand{\Hash}{\mathsf{Hash}} \newcommand{\round}{\mathsf{round}} \newcommand{\prover}{\mathsf{prover}} \newcommand{\timestamp}{\mathsf{timestamp}} \newcommand{\leader}{\mathsf{leader}} \newcommand{\validator}{\mathsf{validator}} \newcommand{\staker}{\mathsf{staker}} \newcommand{\score}{\mathsf{score}} \newcommand{\total}{\mathsf{total}} \newcommand{\stake}{\mathsf{stake}} \newcommand{\reward}{\mathsf{reward}} \newcommand{\height}{\mathsf{height}} \newcommand{\signature}{\mathsf{signature}} \newcommand{\rat}{\mathsf{ratification}} \newcommand{\sol}{\mathsf{solution}} \newcommand{\tx}{\mathsf{tx}} \newcommand{\aborted}{\mathsf{aborted}} \newcommand{\header}{\mathsf{header}} \newcommand{\provingreward}{\mathsf{reward}_\mathsf{coinbase}} \newcommand{\stakingreward}{\mathsf{reward}_\mathsf{staking}} \newcommand{\priorityfees}{\mathsf{fees}_\mathsf{priority}} \newcommand{\priorityfee}{\mathsf{fee}_\mathsf{priority}} \newcommand{\block}{\mathsf{block}} \newcommand{\certificate}{\mathsf{certificate}}$ ## Table of Contents - [Introduction](#Introduction) - [Terminology](#Terminology) - [AleoBFT](#AleoBFT) - [Design of AleoBFT](#Design-Of-AleoBFT) - [Coinbase Puzzle](#Coinbase-Puzzle) - [Target Adjustment](#Target-Adjustment-Algorithm) - [Supply Curve](#Supply-Curve) - [Network Rewards](#Network-Rewards) - [Incentives](#Incentives) ## Introduction AleoBFT is a DAG-based BFT protocol that assumes the number of validators $n = 3f + 1$, tolerating up to $f$ Byzantine validators. Validators communicate with one another using batch proposals over reliable channels, to reach agreement over the canonical ordered history of the decentralized ledger. Each batch proposal contains a set of transmissions - *solutions* and *transactions* - along with references to $2f + 1$ previous batch proposals that each individually achieved quorum threshold. To model failures, we define an adversary as capable of controlling the behavior of a validator, as well as delays in the network. An honest validator adheres to the protocol and is not controlled by an adversary. A Byzantine validator is controlled by the adversary and behaves arbitrarily. This means a Byzantine validator may collude with another Byzantine validator, and may send incorrect messages at any time in the protocol. ## Terminology A **credit** is the native asset of the network, and 1 credit is subdivisible 1,000 millicredits or 1,000,000 microcredits. A **microcredit** is the base unit of the native asset. Credits are used to pay for the deployment fee and execution fee of zero-knowledge programs on the network. In addition, credits are staked on the network as a form of governance to protect the integrity and security of the protocol. A **validator** is a node that has bonded credits as their stake. A **delegator** is a token holder who bonds their stake with a validator. A **staker** is either a validator or a delegator. A **prover** is a node that computes zero-knowledge proofs on the network. There are two types of proofs that provers commonly execute -- **solutions** and **transactions**. A **solution** attests to the execution of a randomly-sampled Aleo program, for which a reward is distributed to prover and stakers of the network in return. A **transaction** attests to the execution of user-deployed Aleo program, for which a transaction fee is a reward distributed to the network in return. By design, provers are incentivized to be stakers, and vice-versa. ## AleoBFT AleoBFT is a DAG-based BFT protocol based upon [Narwhal](https://arxiv.org/pdf/2105.11827.pdf) and [Bullshark](https://arxiv.org/pdf/2201.05677.pdf). The protocol operates in monotonically-increasing rounds. Informally, in each round, each validator proposes a batch of transmissions, broadcasts their batch proposal to all other validators, and awaits for $2f + 1$ signatures to return to them. Once a validator has received $2f + 1$ signatures for their batch, they certify their batch, proceed to broadcast it to all other validators, and advance to the next round. In practice, this quorum property ensures that each validator advances to the next round at roughly the same time as every other validator, assuming an honest majority. On every odd round, each validator elects the leader for the (previous) even round. Namely, if each validator sees at least $f+1$ validators have included (in their current odd round) the leader's batch certificate in the (previous) even round, then the availability threshold $f+1$ is reached, and a leader for the (previous) even round has been made. With each even round, there are 2 ways to achieve quorum for block production: 1. **A leader was elected with $f+1$ proposals from the next (odd) round** - The leader has a batch certificate in the even round that contains at least $2f + 1$ batch certificates from the prior (odd) round - The leader has a batch certificate for the even round that has been included by at least $f+1$ batch certificates for the next (odd) round - Note: This is by definition **quorum intersection**, and is a core principle for making this BFT protocol work in practice. 2. **Quorum $2f+1$ was achieved *without the leader* in the even round** - In case of a timeout while waiting for the leader, if the even round contains more than $2f+1$ batch certificates *without the leader*, the validators can proceed without leader. Once an even round has achieved quorum, either with or without the leader, each validator will perform the **commit rule**, which works as follows: 1. Traverse (using depth-first search) a total ordering of the batch certificates starting from the leader's batch certificate all the way batch to the previously-committed round. 2. With this ordered DAG of batch certificates, proceed to linearize the transmissions (solutions & transactions) into a canonical ordering. 3. Speculatively execute every transmission in the VM, constructing the list of *accepted*, *rejected*, and *aborted* transmissions. - Note: The VM filters out any *existing* or *duplicate* transmissions, which is technically allowed in the memory pool to ensure censorship-resistance. 4. Produce and store the next block, comprised of the ordered list of accepted, rejected, and aborted transmissions. There are two key takeaways from this process that make AleoBFT unique from existing BFT protocols: 1. **As more validators are introduced, this design scales up in TPS** (within practical limits), because the dissemination of transmissions is decoupled from the BFT protocol itself. - Namely, validators are sign for each batch header, only after they have confirmed the existing of the claimed transmissions in their own storage. - This means, the process of retrieving transmissions can be decoupled into a separate out-of-band process, whereby reliable broadcast protocols on any architecture can be used to guarantee the validator has the necessary transmissions. 2. **Validators do NOT need to propogate blocks to one another.** - Because quorum is achieved over a DAG, validators are guaranteed to have the necessary state to construct the canonical block in the ledger themselves, using just the history of batch certificates. - This means, there is no risk of poisoning the block history of another validator, because each validator must independently construct their blocks using the state of the DAG. ## Design of AleoBFT AleoBFT operates over a simple set of data structures - *a committee, batch proposal, and block.* Intuitively, a committee is formed after each block is produced, to denote the validators (and their corresponding state) for the next round. These validators proceed to propose, sign, and certify rounds, until the next leader is elected (or quorum is reached without the leader in an even round), and the next block is produced. Upon creating the next block, the next committee is formed and the process repeats itself. ### Committee Each round is governed by a committee, which is composed of bonded validators. To be a validator in the BFT protocol, a node must bond at least 1,000,000 credits in order to become a committee member. Each committee member must also specify whether they accept delegators to stake with them. The committee is comprised of the following: 1. **The starting round** - the round with which this committee will be in charge of the BFT protocol for (until the next commmitee is formed) 2. **The total stake** - the sum of all bonded stake from validators and delegators 3. **The committee members** - the list of validator addresses, alongside their stake amount and a boolean flag `is_open` indicating their acceptance of delegators #### Bonding and Unbonding In each round, validators and delegators are permitted to bond and unbond. This allows new validators to join the committee and for current validators to leave the committee at any time. A new validator is required to bond at least 1,000,000 credits as stake in order to join the committee. Similarly, current validators are required to maintain at least 1,000,000 credits in order to stay in the committee. Delegators are allowed to bond and unbond any nonzero amount of credits, however they must maintain at least 10 credits of stake with a validator. #### Leader Election Leader election uses a (SNARK-friendly) cryptographic hash function as a form of deterministic randomness to select a validator from the committee as the leader for a given even round. The leader election algorithm takes into account the current round number, the number of validators, and the amount of stake bonded to each validator. This means the probability that a given validator becomes the leader of a round (on average) is proportional to the ratio of their stake and the total amount staked in the committee. In simple terms, the more that a validator stakes, the more frequently that validator is selected as the leader of a round. ### Batch Proposal In each round of AleoBFT, every committee member proposes a batch to be certified. The batch proposal is the primary communication message used to achieve non-equivocation about the state of the DAG. #### Batch ID Each proposal is identified by a batch ID, which is a (SNARK-friendly) hash over the contents of the batch header, described below. #### Batch Header Each proposal contains a batch header, which consists of the following: 1. An author (the validator of the address) 2. A timestamp (the UNIX epoch timestamp) 3. A set of transmissions (solutions & transactions) 4. A set of certified batches from the previous round 5. A signature on the batch ID #### Batch Certificate Each proposal is certified once it has received $2f + 1$ signatures, forming a batch certificate consisting of the following: 1. A batch header 2. A list of signatures from validators (excluding the author) Each batch proposal is identified by its batch ID, and it is the job of each validator in the committee to retrieve any missing transmissions and previous batch certificates that they see from their peers' batch header. Once a validator has retrieved all missing state, they can proceed to sign the batch ID and send that back to the proposing validator. It should be observed that signing a batch is an acknowledgement for a proof-of-availability. Namely, by enforcing a validator only signs for another validator's batch proposal after collecting any missing transmissions and previous batch certificates, it means they now have all transmission state and the full DAG state up to that certificate. It is with this property that we can achieve quorum consensus in AleoBFT. ### Solutions A solution contains a puzzle proof $\pi$ attesting to a randomly-sampled Aleo program (once per epoch) with a nonce that satisfies a target that is at least the $\prooftarget$. This requirement prevents griefing attacks from low $\prooftarget$ solutions. The target update algorithm is described in [Target Adjustment Algorithm](#Target-Adjustment-Algorithm). ### Transaction A **transaction** contains either a deployment or an execution from a user. A deployment transaction is used to deploy a user-defined program onto the network. An execution transaction is used to perform a state update to one or more programs on the network. Each transaction is comprised of a list of **transitions**, which themselves contain the following: - **Transition ID** - a Merkle root over the inputs and outputs - **Program ID** - an identifier for the program in reference - **Function Name** - an identifer for the function invoked - **Inputs** - a list of user-defined public values, private value, and/or records - **Outputs** - a list of user-defined public values, private value, and/or records - **TPK** - the transition public key - **TCM** - the transition commitment #### Transaction Fee In addition, each transaction contains a fee, which can include a public or private payer. Every transaction fee is composed of two parts - a **base fee** and a **priority fee**. The base fee is calculated based on a set of criteria for the transaction type, while the priority fee is arbitrary and can be user-specified. For a deployment transaction, the base fee is comprised of the **storage fee**, which is the (# of bytes in the program) * (deployment fee multiplier). Currently, the deployment fee multiplier is set to 1,000. For an execution transaction, the base fee is comprised of the **storage fee** and **finalize fee**, where the storage fee is the # of bytes in the program, and the finalize fee is computed by the opcodes in the Aleo program and summed up. #### Life of a Transaction Every transaction starts of as an unconfirmed transaction. Once it has been certified in a batch, and included in a subdag for a block, it is now a confirmed transaction. There are several states that an unconfirmed transaction can become: 1. **Confirmed Transaction - Accepted Deployment** - A program was successfully deployed onto the network, and the fee was consumed. 2. **Confirmed Transaction - Accepted Execution** - One or more programs' state was successfully updated on the network, and the fee was consumed. 3. **Confirmed Transaction - Rejected Deployment** - A program failed to deploy, and the fee was consumed. 4. **Confirmed Transaction - Rejected Execution** - No programs' state was updated, and the fee was consumed. 5. **Aborted Transaction** - No state changed and no fee was consumed. 6. **Existing Transaction** - No state changed and no fee was consumed. ### Block A **block** is produced upon triggering the commit rule in AleoBFT, and consists of a block header, an ordered list of batch certificates, a list of ratifications, a list of solutions, a list of transactions, and a list of aborted transmission IDs. Each block is composed of the following: - $\header$ -- the block header - $[\certificate]$ -- the ordered list of batch certificates - $[\rat]$ -- a list of ratifications - $[\sol]$ -- a list of solutions - $[\tx]$ -- a list of transactions - $[\aborted]$ -- a list of aborted transmission IDs #### Header The block $\header$ consists of network-wide parameters used for consensus and by applications. Each member in the block header is updated with each round of the protocol. Each block header is composed of the following: - $\round$ -- the current round number - $\height$ -- the current block height - $\target$ -- the coinbase target for $\block_{i+1}$ - $\prooftarget$ -- the minimum target for each coinbase proof $\pi$ in $\block_{i+1}$ - $\timestamp_i$ -- the timestamp of $\block_{i}$ ##### Round Number Every block must include the current $\round$ number. Each $\round$ number must increment monotonically. Concretely, the $\round$ number is represented as a `u64` variable. ##### Block Height Every block must include the current block $\height$. The block $\height$ (denoted as $i$ in $\block_i$) is a consecutively increasing number that represents the distance of this block from the genesis block. Concretely, the block $\height$ is represented as a `u32` variable. ##### Coinbase Target The $\target$ encodes the required cumulative target from coinbase proofs in order for provers and stakers to be compensated in the next $\block_{i+1}$. The $\target$ is updated dynamically with each round based on the difference between the current $\timestamp$ and the previous $\timestamp$. The value is updated according to the [Target Adjustment Algorithm](#Target-Adjustment-Algorithm). ##### Proof Target The $\prooftarget$ encodes the required target for each solution to be admitted into the next $\block_{i+1}$. The $\prooftarget$ is updated dynamically with each round based on the $\target$. The value is updated according to the [Target Adjustment Algorithm](#Target-Adjustment-Algorithm). ##### Timestamp The $\timestamp_i$ in $\block_i$ is computed as the **median** timestamp of the batch certificates $[\certificate]$. Validators ensure the $\timestamp_i$ is greater than $\timestamp_{i-1}$ from $\block_{i-1}$. It follows from the honest majority assumption that if $n = 3f + 1$, then the **median** timestamp is safe from corruption as it is derived from at least $(n-f)$ batch certificates. Thus, in the worst case scenario, at least $1/2$ of the reported timestamps are honest and the median cannot be corrupted. ## Coinbase Puzzle Aleo introduces a coinbase puzzle as part of its consensus mechanism, which enables provers to produce puzzle proofs over randomly-sampled Aleo programs and earn rewards for their contributions. The motivation for the coinbase puzzle is largely to serve two purposes: 1. Incentivize provers to develop hardware acceleration for zkSNARKs 2. Stochastically distribute Aleo credits into the broader ecosystem Informally, at each epoch, a random Aleo program is deterministically synthesized using the state of the new epoch, that takes as input a nonce, and outputs a proof attesting to the execution of the Aleo program using the nonce. In each iteration of the puzzle, provers sample a random nonce, synthesize the assignments to the Aleo program using the nonce, and produce a puzzle proof for that nonce. If the solution satisfies both the $\puzzletarget$ and $\prooftarget$, the prover will have found a valid solution and broadcasts it to the network for inclusion. When a solution is included into a block, regardless of whether the $\target$ is reached, the prover is compensated with a reward for having found a valid solution. Namely, provers are compensated their pro-rata share of the $\provingreward$ (i.e. $\prooftarget / \target$, capped by the $\target$). Then, when the cumulative sum of the $\prooftarget$ from solutions (across blocks) has reached the $\target$, then the $\puzzletarget$, $\prooftarget$, and $\target$ are adjusted using the [Target Adjustment Algorithm](#Target-Adjustment-Algorithm) to reflect an easier or harder puzzle. Intuitively, if the $\target$ was reached sooner than expected, the target difficulty is increased, and if the $\target$ was reached later than expected, then the target difficulty is decreased. Once the epoch is over, the new state of the epoch will kickoff the same process again, with a newly-sampled Aleo program as the puzzle. This approach to compensating provers ensures they earn rewards as soon as a solution is found, and the frequent epoch refresh to the puzzle itself mitigates withholding attacks by incentivizing provers to broadcast solutions once they are found. ## Target Adjustment Algorithm The target adjustment algorithm is a memoryless, temporal algorithm to dynamically update the $\target$ from each $\block_i$. The algorithm is used to keep incentives for provers and stakers in check as proving capacity evolves in the network. Concretely, the algorithm computes the target for each puzzle proof $\pi$ as follows: $$ \mathsf{target}(\pi) = \mathsf{Truncate}_{\mathsf{U64}}(\mathsf{Hash}(\pi)) $$ The algorithm computes the next $\target'$ using a fixed $\anchortime$, a fixed $\anchortimestamp$, the current block $\height_i$, the current $\target$, and the current number of validators $n_i$ as follows: $$ \begin{aligned} &\target' := \target \cdot 2^\factor \end{aligned} $$ where the $\factor$ is defined as: $$ \begin{aligned} &\factor := \frac{\timestamp_i - \anchortimestamp - (\height_i \cdot \anchortime)}{n_i \cdot \anchortime}. \end{aligned} $$ The intuition of this algorithm is that 1) the expected time it takes to reach $\target$ for $\block_i$ approximates $\anchortime$, and 2) it takes $n_i$ blocks (where $n_i$ is the number of validators) to double the current $\target$ value from $\block_i$. For instance, if each block from $\block_0$ to $\block_i$ is precisely $\anchortime$ distance apart, observe that the $\factor$ for $\block_{i+1}$ is zero, and the $\target'$ for $\block_{i+1}$ remains unchanged. Then if $\block_{i+1}$ has a slower $\timestamp_{i+1}$ (i.e. due to round timeouts) where the $(\timestamp_{i+1} - \timestamp_i) > \anchortime$, then the $\factor > 0$ and the $\target' > \target$. Similarly if $\block_{i+1}$ is faster than expected, then the $\factor < 0$ and $\target' < \target$. Observe that the $\target'$ is then a $\factor$ of how quick the majority of the validators receive and vote on $\block_i$ (by way of the median $\timestamp_i$ rule). In practice, to ensure the computation of $\factor$ remains deterministic under all conditions, we utilize an approximation using fixed-point integers with adequate precision. We discuss the parametrization of the anchor values in [Supply Curve](#Supply-Curve) along with their rewards in [Incentives](#Incentives). ## Supply Curve Aleo starts at genesis $\block_0$ with a $\startingsupply$ in credits that is distributed amongst stakeholders, which include provers, developer grantees, investors, and the Aleo Foundation. The $\startingsupply$ is defined (in credits) to be: $$ \startingsupply := 1,500,000,000 \textsf{ credits} $$ Informally, over the first decade, if each $\block_i$ successfully reaches the $\target$, then the total supply effectively doubles. The network is designed to incentivize the gradual increase of proving capacity over the first decade, and the $\provingreward$ is the primary contributor to the increase in supply. Formally, the supply curve grows as a function of the $\startingsupply$ and the cumulative sum of the $\reward(\height_i)$ from each $\block_i$. If each block from $\block_0$ up to $\block_{\height_{Y10}}$ reaches the $\target$ at the expected anchor time, the total supply doubles approximately to $2 \cdot \startingsupply$ at block $\height_{Y10}$. ## Network Rewards Each block emits a $\reward$ that is computed using a linear function with the block $\height_i$ defined as follows: $$ \reward(\height_i) := \priorityfees + \stakingreward + \provingreward(\height_i). $$ Intuitively, at each block, stakers are compensated their pro-rata share of the $\priorityfees$ and $\stakingreward$. In addition, provers and stakers are compensated a distrubution of the $\provingreward(\height_i)$ if valid solutions were included in the block. Thus, it follows that the supply curve is not fixed; rather it is performance-based, dependent on how well the network (as a whole) scales proving capacity for developers and users of Aleo. To incentivize each party to achieve the maximal supply curve, the [Incentives](#Incentives) section defines how each reward is computed, how it is distributed as compensation amongst the parties, and analyzes the incentives of each party. At genesis, it is expected that $\stakingreward << \provingreward$, and over the first decade, the compensation is expected to change (due to the supply curve, target adjustment, and transaction usage) to be $0 == \provingreward < \stakingreward$. ### $\priorityfees$ The $\priorityfees$ is the sum of the priority fees from confirmed transactions that are included in $\block_i$, and is defined as $\priorityfees := \sum_{\tx \in [\tx]} \tx.\priorityfee$. ### $\stakingreward$ The $\stakingreward$ is a fixed, constant amount in each block that is rewarded to all stakers, based on their stake weight. The $\stakingreward$ for each block is defined as: $$ \stakingreward := \mathsf{floor}((0.05 \cdot \startingsupply) / \height_{Y1}) $$ where the $\height_{Y1}$ is a fixed constant defined as $\height_{Y1} := 365 \cdot 24 \cdot 3600 / \anchortime$. ### $\provingreward$ Provers and stakers are compensated whenever a solution is included in a block. The $\provingreward$ is split between the prover (with 66%) and all stakers (with 33%) in the block, with the $\provingreward$ defined as: $$ \provingreward(\height_i) := \arg\max_{x}\{0, \height_{Y10} - \height_i\} \cdot \anchorreward \cdot 2^{\mathsf{-factor}_i} $$ where the $\height_{Y10} := 10 \cdot \height_{Y1}$, the $\factor_i$ is determined by the average block time since genesis (see [Target Adjustment Algorithm](#Target-Adjustment-Algorithm)), and the $\anchorreward$ is a fixed constant defined as: $$ \anchorreward := \mathsf{floor}\bigg(\frac{2 \cdot \startingsupply}{\height_{Y10} \cdot (\height_{Y10} + 1)}\bigg). $$ Observe that after the first decade, the $\provingreward$ goes to zero, and the remaining network rewards come solely from $\priorityfees$ and $\stakingreward$. To illustrate an example, for instance, if the $\anchortime = 20$, then $\height_{Y10} = 15,768,000$, $\stakingreward = 15,854,895$ gates, and $\provingreward(\height_i) = (15,768,000 - \height_i) \cdot 8$ gates over the first decade. After the first decade, the $\provingreward = 0$. ## Incentives This section outlines the incentives for provers and stakers to participate in the network. ### Provers Provers earn compensation by producing solutions that satisfy the $\puzzletarget$ and $\prooftarget$. When a prover's solution is included in a block, the prover is compensated their proportional share of the $\provingreward$ as follows: $$ \mathsf{compensation}_\prover = \frac{2}{3} \cdot \provingreward \cdot \frac{\mathsf{target}(\pi_\prover)}{\mathsf{target}([\pi_\block])} $$ In addition to network rewards, provers over the first decade gradually earn increased compensation from executing transactions (with diminishing earnings from solutions over the decade). Lastly, provers and stakers are not mutually-exclusive in the design, and it is in each prover's interest to stake their compensation as a validator or delegator to earn further compensation and help in securing the network. This is discussed in further detail in the analysis section. ### Stakers Stakers earn compensation proportional to their bonded stake with each block that is produced. Informally, as the total supply grows over time, the distribution of stake (i.e the pie) for each staker remains the same to provide an equitable distribution. Each staker is compensated their proportional share of the total stake for each round (in the optimistic case) as follows: $$ \mathsf{compensation}_\staker = \bigg(\frac{1}{3} \cdot \provingreward + \stakingreward \bigg) \cdot \frac{\stake_{(r,\, \staker)}}{\stake_{(r,\,\total)}} $$ Recall the $\stakingreward$ per block is a fixed constant of the total supply, with the exact compensation in credits per block determined based on the starting supply of credits in the network.