When discussing rollups, it's important to navigate through a substantial amount of technical information and clear up common misunderstandings (there are also controversies). For this article, I've decided to use the framework by L2BEAT, particularly their well-regarded risk assessment model, as a foundation.

L2BEAT provides thorough information on how rollups work and their associated risks, but it appears to be more suited for readers who already have a lot of familiarity with rollup technology. It can be quite overwhelming for newcomers. My objective here is to simplify this information and make it more accessible.

In analyzing rollup risks, L2BEAT categorizes them into five areas: State Validation, Data Availability, Exit Window, Sequencer Failure, and Proposer Failure. Each rollup listed has a brief description under these categories, usually with additional details that can be difficult to interpret. Let's break down these categories for a high-level, and then detailed understanding.

1. State Validation: Refers to the process of verifying the accuracy and correctness of state transitions of the rollup. This is about ensuring that the transactions and data are correct and haven't been tampered with.

2. Data Availability: Focuses on how accessible the data of the rollup is. Good data availability means users and validators can fully verify the blockchain's history and recover the state.

3. Exit Window: The time during which users can withdraw their assets from the rollup if they need to exit quickly, e.g. due to changes or issues with the rollup. A longer exit window is better because it gives users more security.

4. Sequencer Failure: Deals with the reliability and functionality of the sequencer. If the sequencer fails, it can lead to potential delays or loss of transaction data.

5. Proposer Failure: Focuses on the risks related to the proposer. If the proposer fails, it can lead to issues in processing transactions or updating the state of the rollup.

By understanding these risks, we can better assess the safety and reliability of rollups, which is essential for (some) people (sometimes).

The core difference between zk and optimistic rollups lies in their way of finalizing the state. By state, we understand the balance of all accounts, including smart contracts and regular wallets, deployed on a rollup.

Consider the rollup as a processor: it takes the existing state, processes the latest block's transactions, and updates it. This processor is what we call the state change function.

State validation is a critical aspect of rollup security and functionality, and it varies significantly between zk-rollups and optimistic rollups:

zk-Rollups use zero-knowledge proofs to validate transactions on L2 before posting to L1. In zk-rollups, the operator generates a cryptographic proof (a SNARK or STARK) for each batch of transactions processed on L2. This proof, which verifies the correctness of all transactions in the batch, is then posted to L1.

Optimistic Rollups rely on operators who run the rollup nodes. Transactions are aggregated and executed on L2, and the state is periodically committed to L1 in a batch without immediate verification. Instead, it assumes transactions are valid by default (hence "optimistic") unless challenged with fraud proof.

Fraud proof is an interactive protocol between the challenger (a full node) and the operator responsible for submitting the state (proposer), and includes the following steps:

• The challenger suspects that a state transition processed by the rollup is incorrect and submits the challenge together with justification.

• The proposer responds with a counterargument.

• Depending on the protocol, there might be several rounds of responses.

• Eventually, the process resolves, either because one party fails to respond in time or because the evidence is conclusive.

• After the dispute is resolved, the state transition is either confirmed or the rollup is rolled back to the last valid state.

There are two main types of challenges: single and multi-round.

Previously, Optimism used single-round challenges. This involved re-executing the questioned transaction on L1. However, this approach required the rollup to store all state transitions, which was data-intensive. Moreover, since all transactions were re-executed on L1, it also demanded significant amounts of gas, making it expensive. For these reasons, and to enhance security, Optimism has paused the ability to post fraud proofs and has been working on an alternative solution for almost two years.

Arbitrum uses interactive multi-round challenges. In this system, when a dispute arises, the parties recursively break down the block into segments, and the segments are isolated one by one to identify the incorrect transaction. This method is known as a bisection protocol.

In optimistic rollups, the security depends on having just one honest node. If this node catches any fraudulent transactions, it can submit fraud proof to challenge them. This means that optimistic rollups operate on a fairly low trust model, where only a single honest participant can keep the system secure.

Currently, however, users must place significant trust assumptions while entering an optimistic rollup. In an ideal setup, the ability for anyone to submit fraud proof would be a key feature. The reality is different. Many rollups, even as big as Optimism, are still in the process of developing their systems to accept fraud proofs, which means that such a critical mechanism isn't available.

On the flip side, Arbitrum has put in place a system where only specific approved entities can submit fraud proofs, with L2BEAT being an example of one such entity. Assuming these entities are independent of the rollup's creators, this arrangement needs significantly less trust.

Rollups work by processing transactions off the L1 blockchain and then posting either fraud (in case of incorrect state transitions) or validity proofs back onto L1. Data availability plays here a crucial role as for transactions to be verified, the transaction data must be available. This availability allows nodes to rerun the transactions, confirm their validity and, if required, submit fraud proof. This mechanism is the backbone of integrity in optimistic rollups.

Fraud proofs also are the reason why withdrawing funds from optimistic rollups takes such a long time. The funds need to be locked, usually for seven days, to allow enough time for the transactions to be checked for correctness. However, there are workarounds like using bridges that operate full nodes; they can instantly verify transactions and confirm their validity, which allows them to take risks on behalf of a user.

With zk-rollups, the process is simpler. Here, the operator posts a validity proof directly on L1. This proof confirms that all transactions are correct as soon as they are posted. However, validity proofs don't address one issue: recovering the state of the rollup. For this reason, the zk-rollups must also ensure that data is made available.

The challenge of storing a vast amount of transaction data in a publicly accessible way is known as the data availability problem and it lies at the heart of the blockchain trilemma. Discussing solutions to the data availability problem goes beyond what we cover today. Still, if you remember Reed-Solomon codes from my earlier pieces on zk-STARKs, you're on the right track.

Traditionally, rollups have posted their data directly on L1 blockchains. However, as the concept of modular blockchains gains traction, new solutions are emerging:

• Blockchains like Celestia are built specifically to solve the data availability problem. They provide a dedicated space for storing and accessing data.

• Solutions like EigenDA, secured by Ether that's restaked with EigenLayer, offer high-throughput options for managing data availability.

L2BEAT assesses how and where data is made available. This can significantly differ from one project to another:

• Arbitrum and Optimism make transaction data fully accessible on Ethereum.

• zk-Rollups only publish the data necessary to recover state changes. An exceptions are Polygon zkEVM, Scroll, or Linea, which post the entire transaction set.

• Validiums store the transaction data off-chain and manage it through committees rather than directly on-chain.

As we know, exiting an optimistic rollup involves a delay to account for the possibility of a successful fraud proof, while with zk-rollups exits happen right away. However, the L2BEAT risk assessment category highlights a separate problem: the risk that comes with malicious updates to the rollup's smart contracts and whether users are given sufficient time to withdraw their funds when they choose to.

The architecture of rollup consists of several types of smart contracts:

• Core: Responsible for managing the state root (the summary of the current rollup state), processing transactions, and facilitating communication between L1 and L2.

• Bridge: Enable the movement of assets between the L1 and L2. Needed for users to deposit and withdraw funds.

• Governance and Upgrades: Often combined with timelocks, provide a process for proposing, voting on, and implementing changes.

• Verification: In optimistic rollups, verification contracts manage the fraud proofs. In zk-rollups, handle the verification of validity proofs.

• Escrow: Manage the holding and transferring of assets within the rollup.

The upgradability of smart contracts introduces both flexibility and vulnerability. Currently, the update feature is typically managed by a multisig, so the integrity of the rollup is dependent on the security of this multisig:

• Arbitrum uses a 9 out of 12 multisig. The public identity of its participants gives transparency but also makes them easy targets for malicious attacks.

• Optimism uses a 5 out of 7 mulisig. The identities of the participants are private.

The ability to upgrade smart contracts ideally includes a delay between announcing changes and implementing them, providing users with a chance to leave the rollup if they're wary of malicious updates or don't agree with the changes. Yet, as highlighted by L2BEAT, the reality is that many rollups lack any safeguards against the misuse of their upgrade capabilities, meaning that the changes to the smart contracts apply immediately.

Arbitrum stands out with a three-day waiting period for any contract changes. However, this delay can still be overridden by the Security Council. During this standard waiting period, users have a two-day window to push a transaction through to L1 and exit the rollup.

If a sequencer or proposer encounters problems, it can significantly disrupt a rollup. Here’s a breakdown:

• Sequencer: Collects, orders, and processes transactions, updating the rollup's state. A failure in its operations can lead to delays in transaction processing, loss of transaction order integrity, and halts the rollup's ability to update its state.

• Proposer: Responsible for submitting transaction batches and their state roots to L1. A failure on the part of the proposer includes submitting incorrect state roots or failing to post transactions to L1. The requirement for proposers to post a bond aims to reduce this risk by providing a financial disincentive for fraudulent or negligent behavior.

• Verifiers: Full nodes in optimistic rollups or a verifier contract in zk-rollups. They ensure the correctness of transactions and state transitions.

With an understanding of the roles involved, let's walk through a typical day in the life of a transaction:

1. A user initiates the process by submitting a transaction to the rollup.

2. The sequencer picks up the transaction, orders it with others, and processes the batch, calculating the new rollup's state.

3. The proposer confirms the integrity of the batch and submits it to L1 with the new state root.

4. Verifiers check the correctness of the transaction and its inclusion in the state root.

5. If no issues are detected (including the potential fraud proof submission), the transaction is considered finalized on L1.

Most rollups currently offer the option to submit transactions directly to L1 via a bridge contract. This can be done either from within the rollup or directly on L1. However, this solution has limitations if the transaction includes assets native to the rollup, which may not be interoperable with L1. Moreover, if the operators don’t perform their roles, any funds locked in various protocols would not be possible to be moved.

Arbitrum provides a mechanism allowing users to self-propose blocks if the proposer has been inactive for 6 days and 8 hours to address potential proposer failures. Optimism currently doesn’t have a similar feature, which means users don’t have options for direct intervention if the proposer fails to act.

Aiming for decentralization of the operators is seen as a way to increase the security of rollups. However, decentralization introduces other challenges, such as potential delays in transaction processing, and an increased surface for MEV.

L2BEAT, with some help from Vitalik, grouped rollups into three tiers based on the security considerations discussed above. Here's an overview of how these stages are defined.

Stage 0: Full Training-wheels. The rollup is operated by the creators:

• Self-identification as a rollup.

• Posting L2 state roots on L1 for withdrawals.

• Providing data availability.

• Open source software to reconstruct the state available.

Stage 1: Limited Training wheels. Governance begins to transition to smart contracts:

• Use of a proper proof system.

• At least 5 external actors can submit fraud proof.

• Users can exit without the operator's coordination.

• At least a 7-day exit window for users in case of unwanted upgrades.

• A well-structured Security Council, with at least a 75% consensus threshold and diversity in membership.

Stage 2: No Training Wheels. The rollup is fully operated through smart contracts.

• Council acts only in case of undeniable bugs e.g. failure to submit valid proof.

• Temporary control to the council in specific, bug-related scenarios.

• Upgrades permitted with a minimum 30-day delay.

With Ethereum's shift towards a rollup-centric roadmap, the security of rollups has become crucial for both users and the broader crypto ecosystem. Despite advancements, there remain significant security gaps and trust assumptions in many widely used rollups.

Optimistic rollups were the first to launch, with both Optimism and Arbitrum becoming available to the public in 2021. The tech behind optimistic rollups is more mature, with Arbitrum making significant progress in its security. Optimism, while significantly lagging in security aspects, has shifted its focus towards improving the interoperability of its OP stack, which allows for the creation of other rollups using Optimism's technology. Despite security concerns, users appear relatively unbothered by these shortcomings.

On the ZK rollup front, Starknet, based on STARK technology, launched in 2021, marking an early entry. The first SNARK-based ZK rollup, zkSync, launched only in Q1 2023, making it a new kid on the block(chain). This freshness is evident in the risk assessments, which show that many security issues are yet to be addressed.

In summary, while both types of rollups advance the scalability and efficiency of Ethereum, they each come with distinct security considerations. Although we haven't yet experienced a major incident involving rollup security, the growing number of implementations suggests it's only a matter of time before we encounter some form of breach and loss of funds. L2BEAT work in monitoring the security of these systems is therefore essential for the users and the entire crypto space.

1. L2BEAT

2. Ethereum documentation, Scaling

3. Yuan Han Li, WTF is Data Availability?

4. Charles Yu, Optimism & Arbitrum: Tracking Decentralization Progress

5. James Prestwitch, The Definitive Guide to Sequencing

6. Luca Donno, Introducing Stages

In the first post on the ZK-STARK series, we:

• Defined the problem of proving the knowledge of the 12th number in the Lucas sequence.

• Arithmetized the problem by building a trace and converting it to a polynomial.

• Extended the domain of the polynomial by adding redundancy points.

• Based on the extended domain, we introduced constraints which then formed a single composition polynomial.

Since the composition polynomial is another, more sophisticated representation of the original problem and its solution, if we are to prove that we know this polynomial, we are automatically proving that we know the 12th number of the Lucas sequence.

If you haven’t read the previous article, I am encouraging you to do so.

FRI theory

FRI stands for Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In more detail:

• Fast: FRI has sublinear-time verification. This means that the verifier doesn't need to check the entire polynomial to be convinced that the prover doesn’t lie. Instead, the verifier can check a small portion of the function (randomly chosen) and still be confident about the overall correctness.

• Reed-Solomon: refers to Reed-Solomon codes that use redundancy and polynomials to recover lost pieces of data. We can recover the polynomial of degree with only n+1 points. In the FRI context, the Reed-Solomon code means a polynomial.

• Interactive Oracle Proof (IOP): In an IOP, the prover sends an oracle (a kind of "black-box" function) to the verifier, who can then query this oracle to decide whether to accept or reject the proof. The interaction can occur in multiple rounds, where in each round, the prover sends an oracle based on the verifier's previous queries.

• Proximity: In the FRI protocol the prover doesn’t prove that he knows any polynomial which intersects a certain set of points. There may be more than one polynomial that meets the criteria. The prover should know the polynomial of the degree n, but in fact, knowing a polynomial of degree close to n is good enough. Proximity refers to this closeness in degree with the given polynomial.

If the prover doesn’t need to prove low-degreness of the polynomial entirely, but only approximately, the first questions that come to mind are: what is a low degree, how close is close enough, and why.

• Low degree: in a STARK low degree depends on the degree of the composition polynomial and the length of the trace. In our case, the low degree is sixteen (the degree of the extended domain polynomial). For a more complex problem, it can be a few orders of magnitude more.

• Closeness: for polynomials p and f, distance is defined as the number of points that both f and p do not match on. If the distance between two functions is small, the closeness is high, and vice versa. Small in this situation depends on the degree of both polynomials.

The concept of proximity is not new and has been explored before in probabilistically checkable proofs of proximity (CPPs). The CPPs however get inefficient and less sound when the number of points to check increases. FRI protocol addresses these issues. Let’s explore how.

Vitalik’s STARK

Before we go deeper into the construction of FRI, let’s start with a simple example of a STARK presented by Vitalik in his article on FRI. This will help us conceptually grasp what the whole thing is about. The part I’m referring to is available in the section “A First Look at Sublinearity**”** and can be summarized as follows:

1. The goal is to prove that a large set of points (say, 1 billion) all lie on a polynomial of a certain degree (e.g., less than 1,000,000) without having to check every single point.

2. To achieve this, Vitalik introduces the concept of a bivariate polynomial. This polynomial is constructed such that when evaluated with specific values of x and y, it matches the original polynomial f(x). Specifically, g(x,x1000) = f(x).

3. The prover evaluates g(x,y) over a large square. The diagonal of this square represents the values of g(x,y) that match the values of f(x).

1. Instead of checking every point, the verifier selects a few rows and columns from this square. For each, he asks for a sample of points, ensuring that at least one point from each sample lies on the diagonal.

2. The verifier checks that the points match the original data (using Merkle branches) and correspond to a polynomial of the desired degree.

Conclusion: By checking these samples, the verifier gets a statistical proof that:

• Most rows and columns are populated by points on the desired polynomial.

• The diagonal line is mostly on the desired polynomial.

This sampling and verification process allows the verifier to be reasonably confident that most points on the diagonal correspond to the desired polynomial without having to check every single point. This is where the sublinearity comes in: the verifier can achieve this confidence with a computational effort that grows much slower than the size of the dataset.

In this example, the prover has to evaluate the polynomial g(x,y) on every single point, which is not very efficient. A better prover efficiency can be achieved with the application of modular math, which Vitalik presents in the subsequent section.

In short, instead of evaluating g(x,y) at every point in a large square, the prover evaluates it at points in a smaller grid and then uses modular arithmetic to extrapolate the values in the larger grid. This approach significantly reduces the prover’s computational complexity.

FRI practice

Here we are approaching the FRI protocol. In Vitalik’s examples, while the prover’s computational complexity was reduced, the verifier still had a significant amount of work to do. The verifier had to check a large number of points to ensure that they lie on the correct polynomial, which is computationally intensive.

To address this issue, STARKs introduce the concept of folding. The idea is to use the FRI protocol within itself to reduce the verifier's workload.

Instead of the verifier checking a large number of points directly, the prover generates proof that a smaller number of points lie on the correct polynomial. The verifier then only needs to check this smaller set of points and the STARK proof, significantly reducing their computational complexity.

This approach reduces the verifier's complexity from quadratic to logarithmic in terms of the size of the data. This is a substantial efficiency gain, making the protocol much more practical for large datasets.

To see how this plays out we will use the composition polynomial calculated based on the polynomial constraints from the previous article. The constraints are:

$$$ f_0(x) = \frac{p(x)-7}{x-g^4} $$$

$$$ f_1(x) = \frac{p(x)-11}{x-g^5} $$$

$$$ f_2(x) = \frac{p(x) - g^{i-1} - g^{i-2}}{\prod_{i=6}^{i=18} (x - g^i)} $$$

$$$ f_3(x) = \frac{p(x)-37}{x-g^{19}} $$$

Recall that if the division on the right-hand side of the f polynomials leaves no remainder (i.e., the result is another polynomial), then the constraints are met. Let's represent the polynomials in the denominators on the right-hand with z.

The polynomial p(x), constructed within the trace's extended domain mod 97, is defined as follows:

$$$ p(x) = 90x^{15} + 89x^{14} + 73x^{13} + 70x^{12} + 78x^{11} + 91x^{10} + 75x^9 + 33x^8 + 25x^7 + 51x^6 + 41x^5 + 41x^4 + 69x^3 + 43x^2 + 72x + 21 $$$

Now, with the below piece of code, we can calculate the constraint polynomials. Here for the first two constraints:

pip install galois import galois # Define the finite field GF(97) GF = galois.GF(97) # Define the polynomial p(x) with the coefficients coeffs = [90, 89, 73, 70, 78, 91, 75, 33, 25, 51, 41, 41, 69, 43, 72, 21] p_x_galois = galois.Poly(coeffs, field=GF) # Define the generator g and its powers for the constraints g = 5 g4 = pow(g, 4, 97) g5 = pow(g, 5, 97) # Define the numerators for the constraints numerator_f0 = p_x_galois - GF(7) numerator_f1 = p_x_galois - GF(11) # Define the denominators for the constraints denominator_f0 = galois.Poly([1, -GF(g4)], field=GF) denominator_f1 = galois.Poly([1, -GF(g5)], field=GF) # Perform the polynomial division for f0(x), f1(x), f2(x), and f3(x) quotient_f0, remainder_f0 = divmod(numerator_f0, denominator_f0) quotient_f1, remainder_f1 = divmod(numerator_f1, denominator_f1) # Print the results print("Galois implementation:") print(f"f0(x) quotient:", quotient_f0) print(f"f0(x) remainder:", remainder_f0) print(f"f1(x) quotient:", quotient_f1) print(f"f1(x) remainder:", remainder_f1)

$$$ \begin{align*} f_0(x) &= 90x^{14} + 79x^{13} + 75x^{12} + 94x^{11} + 46x^{10} + 32x^9 + 93x^8 + 55x^7 + 62x^6 + x^5 + 84x^4 + 64x^3 + 8x^2 + 96x + 29 \ f_1(x) &= 90x^{14} + 39x^{13} + 19x^{12} + 81x^{11} + 33x^{10} + 8x^9 + 49x^8 + 92x^7 + 17x^6 + 20x^5 + 73x^4 + 22x^3 + 46x^2 + 39x + 18 \ f_2(x) &= 76x^{12} + 11x^{11} + 21x^{10} + 78x^9 + 24x^8 + 45x^7 + 55x^6 + 53x^5 + 32x^4 + 21x^3 + 26x^2 + 65x + 68 \ f_3(x) &= 90x^{14} + 17x^{13} + 40x^{12} + 38x^{11} + 67x^{10} + 18x^9 + 80x^8 + 66x^7 + 11x^6 + 81x^5 + 15x^4 + 29x^3 + 7x^2 + 18x + 77 \end{align*} $$$

To finalize the process, let’s calculate the composition polynomial using the α values from the verifier. The composition polynomial is denoted as:

$$$ c(x) = \alpha_0 \cdot f_0(x) + \alpha_1 \cdot f_1(x) + \alpha_2 \cdot f_2(x) + \alpha_3 \cdot f_3(x) $$$

The alpha values are: α0 = 39, α1 = 93, α2 = 47, and α3 = 28. The resulting composition polynomial:

$$$ c(x) = 56x^{15} + 30x^{14} + 2x^{13} + 74x^{12} + 32x^{11} + 52x^{10} + 45x^9 + 88x^8 + 47x^7 + 25x^6 + 70x^5 + 37x^4 + 63x^3 + 56x^2 + 44x + 4 $$$

This polynomial c(x) represents the sum of the constraint polynomials f0, f1, f2, and f3, each multiplied by their respective α values. It also has been normalized to have degree 15, which allows us to have a more efficient folding mechanism that will come in handy when using the FRI protocol.

Now, after the commitment by the prover, we finally have arrived to the point when we can put the FRI protocol in action.

FRI querying

In the querying stage, the verifier's role is to check if the prover's polynomial is of a low degree and is related to the trace. Here's a breakdown of how it works:

Constraint verification

• The verifier picks random points in a domain larger than subgroup G. This is done to preserve the zero-knowledge aspect.

• At each point, the prover evaluates the trace polynomial and the constraint polynomials

• By calculating:

  $$$ z_i(x) = p(x) - g^i \cdot f(x) $$$

  and finding them to be vanishing polynomials, the verifier confirms that the constraint polynomials are related to the trace polynomial.

To illustrate, consider the first constraint:

$$$ f_0(x) = \frac{p(x)-7}{x-g^4} $$$

The verifier picks a random number, say 54, and compares if both sides of the below equation match. If yes, the verification is successful.

$$$ p(x) - 7 = x - g^{4} \cdot f_{0}(x) $$$

Let’s substitute. The left-hand side, calculated by the prover:

$$$ p(54) = 61 \quad \text{and} \quad 61 - 7 = 54 $$$

And the right-hand side, calculated by the verifier:

$$$ f_{0}(54) \times (54 - 43) = 49 \times 11 = 54 $$$

Since both sides are equal, the verification is successful, and the constraint holds. Note that the calculations are performed mod 97.

This process is repeated for other values and constraints. Importantly, the verifier only knows the right-hand side evaluations, preserving zero-knowledge. This step also ensures the prover cannot simply invent numbers, as the verifier's calculation must align.

Finally, with the constraints verified, the verifier confirms the polynomial's relation to the trace. Now is the time to confirm its low-degree nature.

Low-degree testing

Low-degree testing is vital for the soundness of the protocol. Without it, the prover could potentially use a high-degree polynomial that matches specific points on the composition polynomial c(x) to pass the verifier's checks. This is possible because a high-degree polynomial, due to its many oscillations, can be adjusted to pass through given points, unlike a low-degree polynomial.

The testing is performed with the so-called FRI operator. The FRI operator is instrumental in reducing the complexity of proving that a polynomial is of low degree. This is important because, in another way, the prover would have to send the entire polynomial or evaluations of the polynomial over some domain, which would be very costly.

Here's how the FRI operator works:

The operator first splits a given polynomial c(x) into even and odd parts, so:

$$$ c(x) = g_0(x^2) + xh_0(x^2) $$$

In our example. The even part:

$$$ g_0(x^2) = 30x^7 + 74x^6 + 52x^5 + 88x^4 + 25x^3 + 37x^2 + 56x + 4 $$$

And the odd part:

$$$ h_0(x^2) = 56x^7 + 2x^6 + 32x^5 + 45x^4 + 47x^3 + 70x^2 + 63x + 44 $$$

The prover receives a random value α from the verifier.

A new polynomial c1​(x) is created using a linear combination of g0​(x) and h0​(x), where α is used as a coefficient for the odd part. This reduces the polynomial's degree by half.

$$$ c_1​(x)=g0​(x)+αh0​(x) $$$

This process is repeated with each iteration halving the degree of the polynomial. For instance, after the second iteration with α=72, the polynomial becomes c2​(x), and so on.

After a logarithmic number of iterations, this process results in a constant or a very low-degree polynomial. In our case for α=69, the polynomial:

$$$ c_3(x) = 17x^3 + 29x^2 + 22x + 69 $$$

After the third iteration and for α=75 we get:

$$$ c_4(x) = 58x + 56 $$$

With each round, the prover commits to the newly formed polynomial using a Merkle Tree.

The verifier then checks if the FRI operator has been correctly applied by mirroring the process and aiming to arrive at the same constant. In our case, 50.

The verifier selects a point z (e.g. 109) from a larger domain, ensuring it’s not part of the subgroup G.

The prover evaluates the composition polynomial at z and −z, returning values c(z)=27 and c(−z)=−53.

With c(z) and c(−z), the verifier can find g0 and h0 by calculating:

$$$ c(z) = g_0(z^2) + zh_0(z^2); \text{ where } g_0(z^2) = 27 $$$

$$$ c(-z) = g_0(z^2) - zh_0(z^2); \text{ where } h_0(z^2) = 53 $$$

Using these values, the verifier computes the formula:

$$$ c_1(z^2) = g_0(z^2) + \alpha_0 h_0(z^2) $$$

and requests the prover to provide the corresponding Merkle path for c.

The verifier continues the process for the next iteration by querying:

$$$ c_1(-z^2) \text{ and solving for } g_1(z^n) \text{ and } h_1(z^n) $$$

The verifier can compute now:

$$$ c_2(z^n) = g_2(z^n) + \alpha_2 h_2(z^n) $$$

The verifier repeats this process for subsequent iterations, each time using a previously chosen scalar α and solving for the components of the polynomial.

The verifier then checks if the final value matches the constant provided by the prover in the commitment round. This confirmation validates the proof.

Since both parties arrived at the constant value of 50, the verifier is convinced that the polynomial c(x) is of a low degree.

The below code runs the perspective of the prover and the verifier. I encourage you to run the code to see what the process for both parties looks like at each step.

import galois # Define the finite field GF(97) GF = galois.GF(97) # Define the initial polynomial p(x) coeffs_p = [56, 30, 2, 74, 32, 52, 45, 88, 47, 25, 70, 37, 63, 56, 44, 4] p = galois.Poly(coeffs_p[::-1], field=GF) # Coefficients are in reverse order for galois.Poly # Define x as a polynomial x = galois.Poly([1, 0], field=GF) # x # The alpha values used in each iteration alpha_values = [72, 69, 75, 83] print("") # Function to apply the FRI operator, using alpha values from the list def apply_fri_operator_verbose(p, alpha_values, GF): for alpha in alpha_values: # Splitting p into even and odd coefficients coeffs_even = [p.coeffs[i*2] if i*2 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)] coeffs_odd = [p.coeffs[i*2 + 1] if i*2 + 1 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)] # Creating even and odd polynomials g = galois.Poly(coeffs_even, field=GF) h = galois.Poly(coeffs_odd, field=GF) print(f"Prover applying FRI Operator with alpha = {alpha}") print(f"Even part (g) = {g}") print(f"Odd part (h) = {h}") # Apply the FRI operator p = g + alpha * h print(f"Resulting polynomial = {p}\n") return p # Apply the FRI operator with the list of alpha values final_result = apply_fri_operator_verbose(p, alpha_values, GF) print(f"Final Prover Result: {final_result}\n") # Function to simulate the verifier's computation in each FRI iteration def verifier_fri_computation_verbose(p, alpha_values, GF, z): for alpha in alpha_values: # Splitting p into even and odd coefficients coeffs_even = [p.coeffs[i*2] if i*2 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)] coeffs_odd = [p.coeffs[i*2 + 1] if i*2 + 1 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)] # Creating even and odd polynomials g = galois.Poly(coeffs_even, field=GF) h = galois.Poly(coeffs_odd, field=GF) # Apply the FRI operator p_next = g + alpha * h # Evaluate at z and -z (square z in each iteration) z_squared = z**2 % GF.order result_z = p_next(z_squared) result_minus_z = p_next(-z_squared % GF.order) print(f"Verifier iteration with alpha = {alpha}") print(f"p(z) = {result_z}, p(-z) = {result_minus_z}") print(f"g = {g}, h = {h}") print(f"Next polynomial p_next = {p_next}\n") p = p_next # Update polynomial for next iteration z = z_squared # Update z for next iteration return p(z) # Final result # Random point z for verification (excluding the subgroup G) z = 109 # Verifier's computation verifier_result = verifier_fri_computation_verbose(p, alpha_values, GF, z) print(f"Final Verifier Result: {verifier_result}")

Decommitments

Let’s summarize where in the protocol the prover makes Merkle tree commitments and provides them to the verifier.

• After the prover calculates p(x) that maps inputs G to the trace and creates the composition polynomial c(x), the prover commits to both polynomials and sends the roots to the verifier.

• During the low-degree testing, the prover applies the FRI operator to reduce the polynomial’s degree. After each transformation, the prover commits to the polynomial and sends its root to the verifier. In our case, the prover sends commitments to the polynomials c1, c2, and c3.

Upon confirming that the Merklee roots provided by the prover are the same as the ones computed by the verifier the verification ends. Based on the constraints checks, low-degree testing, and decommitment processes the verifier can confirm if the claim made by the prover in the original statement is true.

Summary

We've made it! Now, let's take a moment to review the entire protocol, together with the parts we covered in the previous article:

1. Definition of the Problem

   • The prover and verifier agree on a computational integrity (CI) statement and the corresponding polynomial constraints. In our case, the CI statement is the Lucas sequence up to the 19th number.

2. Arithmetization

   • The prover constructs a polynomial p(x) that maps a subgroup G to the trace, which is a sequence of integers in the CI statement.

   • The prover extends the polynomial p(x) to a larger domain.

   • The prover combines the constraints with p(x) to create a constraint polynomials f(x).

   • The prover forms the composition polynomial p(x) from f(x).

   • The verifier queries the prover for specific values of p(x) and c(x), along with Merkle paths.

3. Low-Degree Testing (FRI protocol)

   • The prover folds polynomial c(x), reducing its degree.

   • The verifier queries the prover for specific folded polynomial values and Merkle paths at each stage of FRI.

4. Summary and Validation:

   • After the querying rounds, the verifier assesses the information provided by the prover. If the verifier's checks align with the prover's committed values and transformations, the CI statement is validated. This concludes the proof.

I must admit that my journey through KZG and FRI has been a rollercoaster. I had moments of doubt, but I'm proud to have made it this far!

From my perspective, FRI is more complex than KZG, particularly regarding (de)commitments, which aren't necessary for KZG. This added complexity, including computational aspects, is balanced by the elimination of the need for a trusted setup. Moreover, from what I've heard, FRI is more suitable for recursive proofs (so proofs of proofs), but I’m currently not experienced and knowledgeable enough to have any say on this.

In the next article about zero-knowledge proofs, I plan to better understand the concept of folding. This topic is currently generating significant buzz in the field, playing a crucial role in enhancing the efficiency of the proofs. Meanwhile, I want to express my gratitude for your time in reading this. Your attention means a great deal to me!

Sources

1. Starkware, STARK101

2. Aleksander Berentsen, Jeremias Lenzi, Remo Nyffenegger, A Walkthrough of a Simple zk-STARK

3. Vitalik Buterin, STARKs, Part II: Thank Goodness It's FRI-day

STARKs

zk-STARKs (Zero-Knowledge Scalable Transparent ARguments of Knowledge) are a type of cryptographic proof system that allows one party (the prover) to demonstrate to another party (the verifier) that a specific statement is true, without revealing any information about the underlying data or the statement itself. zk-STARKs are a subset of zero-knowledge proofs and offer several key characteristics that make them attractive:

1. Zero-knowledge: zk-STARKs enable provers to show the validity of a statement without revealing any information about the statement or the data it is based on, ensuring privacy in sensitive applications.

2. Scalability: zk-STARKs are designed to handle complex statements and large datasets efficiently, making them suitable for applications that require high-performance cryptographic proofs.

3. Transparency: Unlike SNARKs, zk-STARKs do not require a trusted setup. This makes them more secure and easier to deploy in decentralized systems like blockchains, where trust assumptions can be problematic.

4. Post-quantum security: zk-STARKs are believed to be resistant to attacks from quantum computers due to their reliance on different cryptographic assumptions.

STARKs leverage hash-based commitments, subsequently employing the FRI protocol to prove the low-degree nature of a polynomial. The acronym FRI stands for Fast Reed-Solomon Interactive Oracle Proof. The protocol was introduced by Eli Ben-Sasson and others in their 2016 publication, "Fast Reed-Solomon Interactive Oracle Proofs of Proximity." Building upon this, the comprehensive zero-knowledge protocol was outlined in the 2018 STARK paper by the same team. This work laid the foundation for the establishment of Starkware, co-founded by Ben-Sasson.

With this knowledge of STARKs, let's delve deeper into the intricacies of their work.

Starting off, it's essential to identify the problem we are working with. In the realm of zero-knowledge proofs, we refer to this as a "statement." This term is also used in the zk-STARK paper. Throughout this article, we will follow the STARK terminology, which might occasionally deviate from what's used in other SNARKs.

In our case, we are going to prove that we know the 12th number in the Lucas sequence (we don’t want to bore people with another example based on the Fibonacci sequence).

Wondering what Lucas numbers are? The Lucas sequence begins with 2 followed by 1. After that, every number in the sequence is the sum of its two immediate predecessors. Here's how the sequence shapes up: 2, 1, 3, 4, 7, 11, 18, 29... and so on. If it reminds you of another well-known sequence, it's purely coincidental!

Computers are not fans of calculating massive numbers, so let's work within a finite field of 97. If the terms 'finite fields' and 'modular arithmetic' sound a bit rusty, take a look at our previous article linked here. In essence, when we talk about operating in a finite field, it means that the integers we work with don't go on forever. Instead, they hit a limit (or a "modulus") and then loop back to the beginning. Think of how clocks work within a finite field of 12 hours, or how a day goes in a finite field of 24 hours.

Now, while determining the 12th Lucas number doesn't inherently pose challenges, we're using the finite field of 97 for illustrative purposes. So, when working within this field, the Lucas sequence looks like this: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 26… and so on. No number in this sequence will ever surpass 97.

In the context of our STARK, we will skip the initial four numbers, targeting the twelfth element as our final entry. This forms the basis of our statement. To phrase this more formally, given the modulo 97:

$$$ \begin{align*} a_0 &= 7, \ a_1 &= 11, \ a_n &= a_{n-1} + a_{n-2}, \quad \text{for } 4 < n < 12, \ a_8 &= 5. \end{align*}) $$$

The prover knows it. The verifier doesn’t and doesn't want to spend time computing it.

Arithmetization in STARKs is split between the following steps: (1) creation of the execution trace, (2) interpolation of the polynomial, (3) extending the domain of the polynomial

Step (1): Building the trace requires connecting each step of the computation with an element of a finite field in a structured way, such that it can be succinctly represented as an evaluation of a polynomial. This will allow the prover to commit to a single polynomial instead of committing to all elements in the execution trace individually.

Our computation is the computation of the 12th Lucas number. Each step of the computation is a Lucas number from the 5th to the 12th. These are the elements of our trace.

The trace is usually a matrix where each row corresponds to a different step in the computation, and each column corresponds to a different state variable. In our case, the computation is simple enough that there is only one state variable: the current Lucas number. This means our trace will be a single column.

The trace will be a representation of a polynomial p evaluated at values in the trace. As such, the results of the evaluation will be related to the trace.

The next step is to create a multiplicative group of order 96 (since the first element is 0) within our field = 97. A multiplicative group is a subset of a field where the operation is multiplication, excluding the zero element. This group is cyclic, which means there exists a generator g such that all other elements in the group can be written as powers of g. Each element of the trace should be associated with a different element of a multiplicative subgroup of the finite field.

We want to find an 8-element subgroup, and we need a generator 𝑔 in 𝔽 whose multiplicative order is 5. The elements of group G will serve as a coordinate x for our polynomial p.

The process of finding a generator for a finite field is trial and error. We start by picking an arbitrary element g from the field, then compute the powers of g modulo p until we reach:

$$$ g^{p-1} \equiv 1 \pmod{p} $$$

If we encounter 1 before reaching:

$$$ (g^{p-1}) $$$

then g is not a generator, and we should try a different element. If we reach it without encountering 1, then g is a generator of the field.

We can automate this process by using a simple Python program:

def find_generator(p): for g in range(2, p): powers = set() for i in range(1, p): powers.add(pow(g, i, p)) if len(powers) == p-1: return g return -1 print(find_generator(97))

This process might take a while for large primes, but it should be quick for p = 97.

Step (2): Next, we aim to find a polynomial p(x) with a degree less than 8. This polynomial, when provided with the respective element of the multiplicative subgroup as input, will compute the Lucas number at each computational step. In essence:

$$$ P(g^i) = L(i+1) \text{ for } 5 \leq i < 12 $$$

where L represents the Lucas number.

For each element of g, the polynomial will take values such that

$$$ f(g_i)=L(i) $$$

Now, let's interpolate this polynomial. We have a couple of methods to choose from: one is the Lagrange interpolation (discussed in the prior article) and the other is the Number Theoretic Transform (NTT). The NTT is similar to the Fast Fourier Transform (FFT) but functions within finite fields. For a more in-depth understanding of NTT, you might want to check out Vitalik's article on the subject.

Our polynomial p, has a degree 7, given that our trace comprises 8 elements. This polynomial, rounded to full integers, can be represented in coefficient form as:

$$$ 55x^{7} + 87x^{6} + 11x^{5} + 34x^{4} + 9x^{3} + 32x^{2} + 71x + 38 $$$

When we plot this polynomial on the coordinate plane, it looks as presented below. Keep in mind that what we are visualizing is the standard depiction of the polynomial. This visualization helps in making it more intuitive to understand the concept of low-degree extension we will undertake in the subsequent step.

For interested, below is a Python code that performs the Lagrange interpolation:

import galois import numpy as np # Create the finite field GF = galois.GF(97) # Define your generator g = GF(5) # Define the x and y values as galois.Array x_values = GF([g**i for i in range(4, 20)]) # Convert list to GF(97) array y_values = GF([7, 11, 18, 29, 47, 76, 26, 5, 31, 36, 67, 6, 73, 79, 55, 37]) # Convert list to GF(97) array # Compute the Lagrange interpolating polynomial L = galois.lagrange_poly(x_values, y_values) # Print the polynomial print("Lagrange Polynomial:", L) # Verify that the polynomial evaluates correctly at the given points assert np.array_equal(L(x_values), y_values), "The polynomial does not interpolate the points correctly." print("Verification passed: Polynomial matches the provided points.")

Step (3): Our next move is to extend the polynomial's domain. Within the STARKs framework, this equals evaluating the polynomial at extra points. For our purposes, we will double the domain, so there's redundancy to reconstruct the polynomial even if some original data points go missing. Typically, these extensions are much larger.

It's important to keep the new set of trace elements as a power of 2. This is required for the NTT, though it's not essential for Lagrange interpolation. When dealing with truly large polynomials (like those in practical applications), the interpolation is primarily executed using NTT, which has log-linear computational complexity (you read more about computational complexity types in this article - it is a must-read for zk enthusiasts). Given that interpolating the polynomial is arguably the most resource-intensive part of the entire protocol, any efficiency gains, like those offered by the NTT, are invaluable.

For our purposes, selecting random points on the polynomial will suffice. However, in real-world scenarios, an additional shift in the polynomial is calculated within the field. This step helps hide the original data, enhancing privacy. Now, let's visualize our polynomial within the expanded domain. Keep in mind, that this is a depiction of the polynomial on a Euclidean plane and not in a finite field.

Degree extension provides the redundancy to reconstruct the original polynomial if some data from the initial eight points goes missing. The Unisolvence Theorem tells us that a polynomial p(x) of degree n is uniquely defined when its values are at n + 1 distinct points.

If you're given n + 1 unique points, there is only one polynomial p(x) with a degree up to n that satisfies the expression:

$$$ P(x_i) = yi, \text {for } i = 1,2,3..,n. $$$

This essentially means that for n+1 unique points, there's a single polynomial, with a degree no greater than n, that intersects all these points. This polynomial is referred to as the interpolating polynomial. Thus, with n+1 points on this polynomial, we can retrieve any polynomial of degree n.

Within STARKs, this kind of polynomial serves two primary functions. First, the FRI protocol verifies its low degree. In our scenario, the polynomial's degree of less than 8 is low. Secondly, this polynomial acts as a foundational component for Reed-Solomon codes, which encode data blocks as polynomials over a finite field. When transmitting data, errors may occur, and some values may be received incorrectly. The task is then to recover the original polynomial, even if some values are erroneous.

This recovery is possible due to the properties of polynomials and the fact that more evaluations of the polynomial are sent than the minimum required by the Unisolvence Theorem. By evaluating the polynomial at more points, we can tolerate some errors and still uniquely recover the original polynomial, even if some of the received values are incorrect. This is what allows Reed-Solomon codes to correct errors in data transmission.

Returning to our data: we have encoded a polynomial based on the following trace. We expanded the domain of our initial polynomial by selecting extra random points that the polynomial passes through. Now it’s time to commit to this data.

The commitment process involves hashing the values representing our polynomial and constructing a Merkle tree using these hashes. Every data point, along with its subsequent branches, must be hashed. The root of the hash is then sent to the verifier. Let's take a look at its visual representation of a Merkle tree.

Here we come across the Fiat-Shamir. The Fiat-Shamir heuristic is a method used to convert an interactive proof, into a non-interactive proof.

The Fiat-Shamir heuristic turns this interactive proof into a non-interactive one by replacing the verifier's role with a cryptographic hash function. Instead of the verifier asking random questions, the prover computes the hash of the statement and previous responses to generate the next challenge. Depending on the specifics of the protocol, this might involve interpreting the hash as an integer and perhaps reducing it modulo some value. The exact way the hash is turned into a challenge depends on the details of the particular protocol being used. This allows the prover to create a proof without interacting with the verifier.

The heuristic's security is based on the assumption that the hash function behaves like a random oracle, meaning that it's computationally infeasible to predict its output without actually computing it.

Let's revisit the constraints we outlined at the start of our discussion, but this time we will adjust them to align with the expanded domain.

Basic Constraints:

Given the Lucas sequence, if we begin with the fifth number, add the sixth, and keep summing the last two numbers for six consecutive iterations, the sixteenth number, when reduced modulo 97, is 37. In formal terms:

1. The first element, a[0] = 7

2. The second element, a[1] = 11

3. The Lucas sequence rule, an​ = an−1​ + an−2​, is valid for elements 2 < n <= 14

4. The final element a[15] = 37

Polynomial Constraints:

Earlier, we transformed the execution trace that describes the problem into a polynomial p. Now, we will rewrite the constraints into polynomial form based on the trace polynomial p. The trace and its corresponding values are denoted with a and ai​. When presented as constraints in polynomial terms, it will look like this:

$$$ \begin{align*}

1. \quad p(x) &= 7, &\text{for } x &= g^4 \

2. \quad p(x) &= 11, &\text{for } x &= g^5 \ &\vdots \

3. \quad p(x) &= 37, &\text{for } x &= g^{19} \end{align*} $$$

When we evaluate the polynomial p at the specific trace value gi​, it yields the corresponding number from the Lucas sequence. This happens because we have mapped the elements of the group G with the numbers from the Lucas sequence and interpolated the polynomial based on this mapping.

Now, the third constraint, which is more challenging:

$$$ p(x) = g^{i-1} + g^{i-2}, \text{ for } x = g^i, \ 6 < i \leq 18 $$$

Putting it more simply: when we evaluate the polynomial p at the ith element of x, the outcome is

$$$ g^i. \text{ This } g^i \text{ is the sum of } g^{i-1} \text{ and } g^{i-2} $$$

This holds true for i values from 6 to 18, but no further, since these are the last two elements of the trace. The last element is described by the fourth constraint, while the one before cannot be calculated by the formula.

We have now translated our constraints into a polynomial form, echoing the exact constraints we started with. Hence, if these polynomial constraints hold up, then our initial statement is true.

Root Constraints

We will now transition from the polynomial form to the root form. When discussing polynomials, a root is essentially a value, let's say x = a, where the polynomial p(x) evaluates to zero. In simpler terms, if p(a) = 0, then a is considered a root of the polynomial p(x). Let's see what our constraints look like in the root format:

$$$ \begin{align*} \text{1. } p(x) - 7 &= 0, &\text{root: } x &= g^4 \ \text{2. } p(x) - 11 &= 0, &\text{root: } x &= g^5 \ \text{3. } p(x_i) - g^{i-1} - g^{i-2} &= 0, &\text{roots: } x &= g^i, \ 6 < i \leq 18 \ \text{4. } p(x) - 37 &= 0, &\text{root: } x &= g^{19} \end{align*} $$$

By this logic, if the values of x are the roots of p(x), then our initial statement is true.

Rational Functions Constraints

Based on the Polynomial Remainder Theorem when we divide a polynomial p(x) by x − z, the remainder is p(z). So, if p(z) = 0, it means that the division by x − z yields no remainder. This indicates that x − z is a factor of p(x), and consequently, z is a root of the polynomial p(x). As a result, there must exist another polynomial, say t(x), such that when t(x) is multiplied by x − z, we get p(x).

Given

$$$ p(x) = x^2 - 5x + 6 $$$

if we think x − 2 might be a factor, we can test it by calculating P(2) = 4 − 10 + 6 = 0. We confirm that indeed P(2) = 0, so x−2 is a factor. Now, when we divide p(x) by x − 2 the quotient is x − 3 and there is no remainder. So:

$$$ p(x) = (x-2)(x-3) $$$

Now, let’s transform the root constraints into rational functions.

$$$ \text{1. } g^4 \text{ is root of } p(x) - 7 \text{ if and only if } \frac{p(x) - 7}{x - g^4} \text{ leaves no remainder} $$$

$$$ \text{2. }g^5 \text{ is root of } p(x) - 11 \text{ if and only if } \frac{p(x) - 11}{x - g^5} \text{ leaves no remainder } $$$

$$$ 3. \ \forall i \in (6, 18], \ g^i \text{ roots } p(x) - g^{i-1} - g^{i-2} \text{ iff } \frac{p(x) - g^{i-1} - g^{i-2}}{\prod_{i=6}^{i=18} (x - g^i)} \text{ leaves no remainder} $$$

$$$ \text{4. }g^{19} \text{ is root of } p(x) - 37 \text{ if and only if } \frac{p(x) - 37}{x - g^{19}} \text{ leaves no remainder} $$$

Before moving forward let's dive deeper into the third constraint. Calculating the product of all the elements of g might seem daunting, especially when we aim for efficiency. Fortunately, there's a neat workaround that can make that job much easier.

Instead of the heavy calculation in the denominator, we can simply use:

$$$ x^n - 1 $$$

The key point: in group G, raising g to the power of N gives us 1. It can be easily verified that:

$$$ g^{97} = 1 $$$

Given this observation, if we factor the polynomial x^N-1 over the field, the roots are precisely the powers of g. Therefore x^N-1 can be expressed as a product of linear terms:

$$$ \prod (x - g^i) = x^n - 1 $$$

his is an illustration of the fundamental theorem of algebra which says that a polynomial of degree N has exactly N roots in a field containing those roots. In this context, the field contains the cyclic group generated by g, and x^N−1 has its roots as the powers of g.

The equation holds because every power of g is a root of x^N−1, and the polynomial can be expressed as a product of linear terms based on these roots.

In our case, since the trace has only 16 steps, the calculation will be manageable, so we will keep the constraint as is. To apply the simplification for our F = 97 and with only 16 trace steps, we would have to cancel all the remaining 81 steps/polynomials, which would cost us dearly in terms of the cost of computing.

We have now transformed the constraints from the root form to the rational function form. Since in each case the division leaves no remainder, the results are always polynomial.

We now can re-write the constraints as polynomials:

$$$ \begin{align*} f_0(x) &= \frac{p(x)-7}{x-g^4} \ f_1(x) &= \frac{p(x)-11}{x-g^5} \ f_2(x) &= \frac{p(x) - g^{i-1} - g^{i-2}}{\prod_{i=6}^{18} (x - g^i)} \ f_3(x) &= \frac{p(x)-37}{x-g^{19}} \end{align*} $$$

If these statements are polynomials, then our initial statement holds.

After transitioning our constraints from the basic form to rational functions, our next and final step is to create the composition polynomial denoted c(x).

The composition polynomial is created by multiplying our rational functions with a random value, α, from the field and then adding the results:

$$$ c(x) = \alpha_0 \cdot f_0(x) + \alpha_1 \cdot f_1(x) + \alpha_2 \cdot f_2(x) + \alpha_3 \cdot f_3(x) $$$

If f statements are polynomials, then c(x) is guaranteed to be a polynomial too. The next step is to use a Merkle Tree to commit to c(x).

And this commitment finalizes the zk-STARK's arithmetization. Though less intuitive than the SNARKs' arithmetic circuit method, the trace technique scales better and is apt for sequential and repetitive computations.

Summary

Let's take a step back and recap the steps and tools we used:

1. Problem Statement: Our goal was to prove the knowledge of the twelfth number in the Lucas sequence.

2. Algebraic Execution Trace: We constructed the algebraic execution trace, detailing the computation step by step. We limited the calculation to a field of 97 elements generated by a single element g.

3. Transformation to Polynomials: We converted the trace to a polynomial using Lagrange Interpolation. For larger traces, Fast Fourier Transform over finite fields (aka Number Theoretic Transform) would be a more efficient choice.

4. Domain Extension: We extended the polynomial through the addition of more points that lay on this polynomial. This ensures we can reconstruct the polynomial even if some of the original points are lost. The data recovery method with the use of polynomials is called Reed-Solomon codes.

5. Polynomial Commitment: We committed to the polynomial by hashing it into a Merkle Tree, which is then sent by a prover to the verifier. With the help of the Fiat-Shamir heuristic that introduces randomization based on the resulting hashes, we can make the protocol non-interactive.

6. Constraints Transformation: We described the constraints and transformed them subsequently to polynomial, root, and then rational function form. From these functions, we then formed the composition polynomial. Successfully proving that the composition polynomial is low-degree is equal to confirming that the original statement is true.

Indeed, in the next article, we will show how the FRI protocol is used to prove that the composition polynomial is low-degree. Keep an eye out for that!

P.S. I'm aiming to release the next piece sooner than in 6 months. Thanks for your patience.

I couldn’t write this blog post without the following sources:

1. Starkware, STARK101, (main inspiration and source)

2. Starkware, Arithmetization

3. Starkware, ethSTARK

4. Aleksander Berentsen, Jeremias Lenzi, Remo Nyffenegger, A Walkthrough of a Simple zk-STARK Proof

5. RISC Zero, STARK by hand

Zero-Knowledge Proofs

Zero-knowledge proofs (ZKPs) were first brought to light in 1989 with the publication of "The Knowledge Complexity of Interactive Proof Systems" by Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The concept received a lot of attention in the late 1990s, with the introduction of non-interactive ZKPs in "Succinct Non-Interactive Zero-Knowledge for a von Neumann Architecture" by Amit Sahai and Salil Vadhan. Despite its initial buzz, the use of ZKPs slowed down over the years, but has recently experienced a revival, especially in the context of blockchain technology. Early on, Zcash embraced the technology and became one of the first cryptocurrencies to implement ZKPs in 2014. Fast forward to today, and the crypto space is filled with new projects that utilize zero-knowledge proofs to enhance scalability and privacy. This innovative use of mathematics and cryptography has made ZKPs a buzzword in the crypto community.

ZKPs are a special kind of cryptographic proof that allows a prover to show to a verifier that they possess certain information, without revealing the information itself. For example, a prover could prove that a number x falls within a certain range [a,b] without revealing x's actual value. Similarly, it could be proved that an element z is part of a set S without revealing the value of the element, or prove that two numbers x and y are equal without revealing their values.

For ZKPs to work, the problem at hand must be in the NP class. NP stands for "nondeterministic polynomial time" and refers to problems that can be verified quickly and easily, even though they may be difficult to solve. Examples of NP problems include checking a hash function for a specific value, determining if a number is prime, or solving a sudoku puzzle.

In the blockchain world, ZKPs are a key tool for achieving two key goals: privacy and scalability. Privacy is the main reason for the adoption of ZKPs in cryptocurrencies like Zcash and decentralized applications like Tornado Cash, where ZKPs allow for transactions to be mixed without revealing information about the parties involved or the amount being transferred.

Scaling is another important reason for the use of ZKPs in blockchain. ZKPs allow for large amounts of data to be encoded into small-sized proofs that are easy to run and verify, making them a perfect solution for blockchains. In fact, Ethereum has introduced ZKPs in EIP-4844, also known as Proto-Danksharding, where the succinctness of ZKPs will be used to allow L2s to post transactions on Ethereum in "data blobs”.

For a ZKP system to be considered truly zero-knowledge, it must meet certain criteria. These include:

1. Completeness: If the statement is true, the verifier will be convinced of its validity.

2. Soundness: If the prover is lying, the verifier will not be convinced of the statement's validity.

3. Zero-knowledge: The proof reveals no information about the statement being proved beyond the fact that it is true.

Zero-knowledge proofs come in several different forms, each with its own method of proving a statement to a verifier. The main types of ZKPs include:

1. Interactive proofs: This type of proof involves a back-and-forth communication between the prover and verifier, where the prover provides pieces of information about the statement being proved, and the verifier asks questions (challenges) to verify the information. This process repeats until the verifier is confident that the statement is true.

2. Non-interactive proofs (SNARKs, if the succinctness requirement is met): In this type of proof, the prover sends all the information needed to verify the statement, along with pre-computed answers to potential challenges, to the verifier. This eliminates the need for further interaction and makes the process faster. However, a trusted setup between the parties is required to pre-determine the answers to the challenges.

3. Transparent proofs: Unlike non-interactive proofs, transparent proofs do not require a trusted setup and thus offer a more secure solution. They eliminate the risk of a malicious agent exploiting the system if the algorithms were to be compromised in the future.

SNARKs

SNARK stands for "Succinct Non-Interactive ARgument of Knowledge," meaning that the proof can be generated and verified quickly without any interaction between the prover and verifier. To understand how zk-SNARKs work, it is helpful to start with a basic understanding of arithmetic circuits. Any problem in the NP class can be translated into an arithmetic circuit, which consists of input gates, sum gates, and product gates. Input gates are labeled with either a variable or a value and have no incoming wires. Sum gates are labeled with "+" and perform addition, while product gates are labeled with "*" and perform multiplication.

For example, imagine a prover P wants to prove to a verifier V that he knows the value of x such that the polynomial p:

$$$ x^2 + x + 7 = 37 $$$

The arithmetic circuit for this polynomial would look as follows:

+ / \ + 7 / \ * x / \ x x

The input gates in the circuit are for the variable x and constant 7, and the circuit has three arithmetic gates performing three arithmetic operations. Although real-life arithmetic circuits have far more gates and create much more complicated polynomials, what's important to note is that an arithmetic circuit can always be expressed in the polynomial form.

To create a ZK-SNARK, the next step is to turn the arithmetic circuit into a set of equations using a system called the Rank 1 Constraint System (R1CS). This system allows the representation of the arithmetic circuit as a set of linear equations. For example, the R1CS representation of the polynomial p would look like this:

X = x A = X^2 B = A + X C = B + 7

The process of transforming the arithmetic circuit into a set of equations is called "flattening." In this process, X, A, B and C are the variables and the equations represent the operations carried out in the arithmetic circuit. To represent the system of linear equations in R1CS, a set of matrices is used:

s [1, 5, 37, 25, 30] A [0, 1, 0, 0, 0] [0, 1, 0, 1, 0] [7, 0, 0, 0, 1] B [0, 1, 0, 0, 0] [1, 0, 0, 0, 0] [1, 0, 0, 0, 0] C [0, 0, 0, 1, 0] [0, 0, 0, 0, 1] [0, 0, 1, 0, 0]

The vector s represents the solutions to the operations performed in the linear equations and is presented in the form[1, X, C, A, B].

In the process of calculating the matrices A, B, C we need to ensure that they meet a specific equation: s.A * s.B - s.C = 0, which is the same as s.A * s.B = s.C. We can verify this by taking the dot product of each element in the matrices and adding them up:

A [1, 5, 37, 25, 30].[0, 1, 0, 0, 0] = 5 [1, 5, 37, 25, 30].[0, 1, 0, 1, 0] = 30 (5+25) [1, 5, 37, 25, 30].[7, 0, 0, 0, 1] = 37 (30+7) B [1, 5, 37, 25, 30].[0, 1, 0, 0, 0] = 5 [1, 5, 37, 25, 30].[1, 0, 0, 0, 0] = 1 [1, 5, 37, 25, 30].[1, 0, 0, 1, 0] = 1 C [1, 5, 37, 25, 30].[0, 0, 0, 1, 0] = 25 [1, 5, 37, 25, 30].[0, 0, 0, 0, 1] = 30 [1, 5, 37, 25, 30].[0, 0, 1, 0, 0] = 37

Our calculation shows that s.A * s.B = s.C is met, since 5*5=25, 30*1=30, 37*1=37 This means that the prover P knows the right answer and that our arithmetic circuit is properly constructed. The purpose of the R1CS representation is to ensure that our arithmetic circuit produces the correct answer (also known as witness), and lays out all the conditions for our statement (constrains).

If you would like to understand the process better, you can use the Python code written by Vitalik to turn your set of equations into an R1CS.

The next step in the ZK-SNARK creation process is to convert the R1CS representation into a Quadratic Arithmetic Program (QAP). This is important because ZK-SNARKs rely on polynomials to prove statements, and while the R1CS matrices may confirm that the calculation is correct and the prover knows the witness, they are not suitable for ZK-SNARK purposes. The transformation from R1CS to QAP will convert the matrices into polynomials, making them suitable for use in a ZK-SNARK.

A polynomial of degree n has at least n + 1 points where it intersects with the coordinate plane. For example, a polynomial of degree 1, like a line, would intersect with the plane at two points. Meanwhile, a polynomial of degree 2, like a parabola, would have three points of intersection. Given that our R1CS matrices have three rows (or that our arithmetic circuits have three gates) we'll be constructing polynomials of the second degree.

We will be using the coordinates 1, 2, 3 for the x-axis, and for each column of each matrix created for the R1CS representation, we will use these values to find the corresponding y-axis coordinates. For example, consider the first column of the first matrix, 0, 0, 7. We will map these values to create the following set of coordinates (1,0), (2,0), (3,7).

Using Lagrange interpolation, we will find a polynomial that satisfies these coordinates. To do this, we create individual polynomials for each point and then combine them to form a final polynomial that passes through all three points. The final polynomial serves as an estimate for the underlying function that generated these points. Lagrange polynomials for coordinates(1,0), (2,0), (3,7) are, respectively:

$$$ L_1(x) = \frac{(x - 2)(x - 3)}{(1 - 2)(1 - 3)} \times 0 = 0 $$$

$$$ L_2(x) = \frac{(x - 1)(x - 3)}{(2 - 1)(2 - 3)} \times 0 = 0 $$$

$$$ L_3(x) = \frac{(x - 1)(x - 2)}{(3 - 1)(3 - 2)} \times 7 = \left(\frac{(x - 1)(x - 2)}{2}\right) \times 7 $$$

To find the Lagrange polynomial for the point (1,0), we first need to create a polynomial that is non-zero at x = 1 and zero at the two other points. This can be done using the formula (x - 2)(x - 3). We then divide this by (1 - 2)(1 - 3)to find the correct value of y. Finally, we multiply the polynomial by the value of y for our point.

We repeat this process for the two other points, and then add up all of the resulting polynomials to get the final Lagrange interpolating polynomial:

$$$ \begin{align*} p(x) &= L_1(x) + L_2(x) + L_3(x) \ &= 0 + 0 + \left( \frac{(x - 1)(x - 2)}{2} \times 7 \right) \ &= \frac{7}{2} \times (x - 1)(x - 2) \ &= \frac{7}{2} \times (x^2 - 3x + 2) \end{align*} $$$

The above result can also be written in the form of another polynomial:

$$$ \begin{align*} p(x) &= \frac{7}{2} \times (2 - 3x + x^2) \

&= 7 - 10.5x + 3.5x^2

\end{align*} $$$

Which then can be written in the form of a vector: [7, 10.5, 3.5]. We thus have transformed the first row of the matrix A of R1CS (transposed) to a polynomial. When we do the same with the remaining rows, we get the following matrix:

Ap [7.0, -10.5, 3.5] [0.0, 1.5, -0.5] [0.0, 0.0, 0.0] [-3.0, 4.0, -1.0] [1.0, -1.5, 0.5] Bp [-2.0, 2.5, -0.5] [3.0, -2.5, 0.5] [0.0, 0.0, 0.0] [0.0, 0.0, 0.0] [0.0, 0.0, 0.0] Cp [0.0, 0.0, 0.0] [0.0, 0.0, 0.0] [1.0, -1.5, 0.5] [3.0, -2.5, 0.5] [-3.0, 4.0, -1.0]

You can use the code written by Vitalik to get such QAP for your SNARK.

Now, our initial statement is represented in the form of polynomials, and soon we will be able to do some cryptography on it.

Recap

Before closing the first part of the article, let’s recap all the steps we went through:

1. We began by defining our statement, where the prover wants to prove to the verifier that they know the value of x such that the equation x^2 + x + 7 = 37 holds. This statement needs to be quickly verifiable for us to build a ZK-SNARK for it.

2. We then created an arithmetic circuit that represented the statement and flattened it by writing each calculation in the circuit as a separate polynomial. The circuits only accept addition and multiplication as possible operations.

3. From the flattened arithmetic circuit, we created an R1CS representation of the problem. R1CS consists of three matrices that must satisfy the equation: s.A * s.B - s.C = 0.

4. Finally, we transformed the R1CS to QAP using Lagrange interpolation. QAP is a matrix of polynomials that captures the underlying function of the original statement, with each row representing the coefficients of the polynomials.

To wrap up, our example was simple, but in reality, arithmetic circuits can become quite complex, with thousands of gates and wires. Performing manual calculations for these large circuits is not a feasible option. That's why tools such as Circom (Hardware Description Language), or programming languages with compilers such as zoKrates, and Cairo are utilized to build the circuits and perform the complex calculations.

In the next part of the article, we will explore the process of constructing an actual zk-SNARK from the polynomials we derived. We will look at how polynomial commitments are used to verify the set of polynomial equations, and how the final proofs for statements are created. Stay tuned!

• It makes trading a better experience, as transactions can be completed almost instantly.

• It helps to stabilize prices and reduce slippage, or the difference between the price you want to pay for an asset and the price you end up paying.

• It helps to prevent market manipulation.

In the real world, cash is considered a liquid asset because it can be easily exchanged for goods and services. On the other hand, real estate is not considered a liquid asset because it is difficult to quickly sell and convert into cash. In the crypto world, this concept can be applied to fungible coins with large market caps, which are generally considered much more liquid than NFTs.

The crypto industry has come a long way since the early days when bitcoins were traded for pizzas on online forums. We have witnessed the rise and fall of centralized exchanges such as MtGox, as well as the success of platforms like Binance and Coinbase. Currently, DEXes offer a way for users to trade crypto without the need for a third-party intermediary. In this article, we will explore the evolution of these exchanges, how they have attempted to solve the liquidity problem and what awaits us in the future.

The rise of Automated Market Makers (AMM)

DEXes were among the first blockchain-based applications, and the introduction of AMMs has been a breakthrough in their history. AMMs are algorithms that facilitate trades on DEXs, making it easier for users to buy and sell assets on-chain and increase the liquidity of the crypto markets. Let’s take a closer look at how AMMs work and how they have evolved.

Uniswap, now a DeFi juggernaut, introduced the constant product market maker (CPMM) model and the concept of liquidity pools. The CPMM model calculates the total amount of assets in a liquidity pool using the formula x*y=k, where x is the amount of asset A (e.g. ETH), y is the amount of asset B (e.g. USDC), and k is constant. To withdraw ETH from the pool, a user must deposit an amount of USDC determined by the ratio of total ETH to total USD. While this model has some limitations, including the need for a separate liquidity pool for each asset pair or impermanent loss, it was a major development that helped to kick-start the DeFi revolution.

Slippage is another common issue with AMMs and researchers have been looking for ways to optimize the model to address it. Curve Finance has found a solution to slippage for stable asset pairs such as USDC/USDT or ETH/stETH. Let’s see how it was achieved.

The price discovery mechanism in an AMM can be represented by a function, with the price of the assets shown as a point on this function. The CPMM model used by Uniswap (purple dashed line) is more sensitive to changes in the pool's reserves, resulting in a more curved function. On the other hand, in a pool where the price changes evenly (i.e. the withdrawal of token A causes the price of token B to change by the same amount), the function is linear (red dashed line). In this case, the sum of the prices of both assets is always constant. Curve elegantly combines the constant product and constant sum models in a way that the function is linear when the supply of coins is balanced but becomes more curved when there is a greater disparity in the reserves. This is the solution that allows the protocol to offer better prices for trades between stable assets.

Uniswap v3, released in May 2021, brought many improvements to the CPMM model, including the ability for liquidity providers to choose the price range in which they want to provide liquidity. In earlier versions, liquidity was evenly split across the entire curve, which resulted in underutilization of capital as trades often did not take place at the farthest points of the curve. With the ability to choose their price range, liquidity providers can now more effectively earn fees by providing liquidity in areas where it is most needed. This enhancement has significantly improved the capital efficiency of the AMM model.

Oracle-based DEXes

Oracle-based DEXes have attempted to address the issue of slippage by using external smart contracts that provide real-world data to blockchain apps. Bancor and GMX are examples of oracle-based DEXes that use this approach. Bancor uses a unique formula to determine the price of each asset in its liquidity pools, which is based on oracle-fed data. GMX, a perpetual exchange that also has a liquidity pool to trade blue-chip assets, uses Chainlink oracles to feed prices from centralized exchanges, thus enabling trading with no slippage.

While this is positive for traders, it leaves the protocol vulnerable to price manipulation. There have been several instances of oracle exploits, including a recent one on GMX in which an attacker manipulated the price of AVAX on centralized exchanges while simultaneously opening and closing long/short positions on GMX and costing liquidity providers an estimated $500 million.

Oracle-based price discovery relies on a third-party provider, which may not always be decentralized and could be exploited even if it functions flawlessly. This approach also does not solve the liquidity problem but rather avoids addressing it. Because of these issues, an oracle-based system is not a scalable and sustainable long-term solution for DEXes.

Will order book DEXes dominate DeFi?

AMMs and oracle-based DEXes have had their limitations, leading many in the industry to consider the potential for order book-based DEXes. Order book-based exchanges, such as Binance, and Coinbase are traditional centralized exchanges that use market makers to provide liquidity for their users. While the order book model is the standard for centralized exchanges, it hasn't been feasible for blockchain-based exchanges due to high transaction fees and low throughput.

There are currently only a few DEXes implementing the order-book model, such as dYdX, Solana's Serum (which rebranded as OpenBook after the FTX collapse), and Demex running on Cosmos' chain Carbon. However, the potential for order book-based DEXes to eventually take over the market has never been more appealing as the technology continues to progress.

The price discovery mechanism in an AMM can be represented by a function, with the price of the assets shown as a point on this function. The CPMM model used by Uniswap (purple dashed line) is more sensitive to changes in the pool's reserves, resulting in a more curved function. On the other hand, in a pool where the price changes evenly (i.e. the withdrawal of token A causes the price of token B to change by the same amount), the function is linear (red dashed line). In this case, the sum of the prices of both assets is always constant. Curve elegantly combines the constant product and constant sum models in a way that the function is linear when the supply of coins is balanced but becomes more curved when there is a greater disparity in the reserves. This is the solution that allows the protocol to offer better prices for trades between stable assets.

Uniswap v3, released in May 2021, brought several improvements to the CPMM model, including the ability for liquidity providers to choose the price range in which they want to provide liquidity. In earlier versions, liquidity was evenly split across the entire curve, which resulted in underutilization of capital as trades often did not take place at the farthest points of the curve. With the ability to choose their price range, liquidity providers can now more effectively earn fees by providing liquidity in areas where it is most needed. This enhancement has significantly improved the capital efficiency of the AMM model.

Oracle-based DEXes

Oracle-based DEXes have attempted to address the issue of slippage by using external smart contracts that provide real-world data to blockchain apps. Bancor and GMX are examples of oracle-based DEXes that use this approach. Bancor uses a unique formula to determine the price of each asset in its liquidity pools, which is based on oracle-fed data. GMX, a perpetual exchange that also has a liquidity pool to trade blue-chip assets, uses Chainlink oracles to feed prices from centralized exchanges, thus enabling trading with no slippage.

While this is positive for traders, it leaves the protocol vulnerable to price manipulation. There have been several instances of oracle exploits, including a recent one on GMX in which an attacker manipulated the price of AVAX on centralized exchanges while simultaneously opening and closing long/short positions on GMX and costing liquidity providers an estimated $500 million.

Oracle-based price discovery relies on a third-party provider, which may not always be decentralized and could be exploited even if it functions flawlessly. This approach also does not solve the liquidity problem but rather avoids addressing it. Because of these issues, an oracle-based system is not a scalable and sustainable long-term solution for DEXes.

Will order book DEXes dominate DeFi?

AMMs and oracle-based DEXes have had their limitations, leading many in the industry to consider the potential for order book-based DEXes. Order book-based exchanges, such as Binance, and Coinbase are traditional centralized exchanges that use market makers to provide liquidity for their users. While the order book model is the standard for centralized exchanges, it hasn't been feasible for blockchain-based exchanges due to high transaction fees and low throughput.

There are currently only a few DEXes implementing the order-book model, such as dYdX, Solana's Serum (which rebranded as OpenBook after the FTX collapse), and Demex running on Cosmos' chain Carbon. However, the potential for order book-based DEXes to eventually take over the market has never been more appealing as the technology continues to progress.

The provision (3) serves as a safeguard against market makers posting empty offers or spamming the exchange with offers that will never be fulfilled. It compensates offer takers for gas costs incurred when a maker decides or is forced to cancel an offer after a match, which can occur due to changing market conditions or the unavailability of the traded asset on the maker's side.

Later, when an offer is matched with a buy order, the callback function (4) is called twice. First, it is used to provide the asset for the trade, and then, after the trade is executed, to replenish the offer if the market maker has indicated this in the offer code. This helps to reduce the number of transactions needed to fill the order book, which in turn helps the protocol scale more efficiently.

On Mangrove, offer takers have the option to use a market order or a snipe when trying to fulfill a specific offer. A market order allows the taker to specify the highest price they are willing to pay for the offer, similar to a limit order on a traditional exchange. However, Mangrove does not offer a market order in the traditional sense, which is an order to buy a certain amount of an asset at the best available price. This is to protect users from MEV attacks, such as frontrunning or sandwiching.

The process of posting bids and asks on the exchange, including the actions of Mangrove's main smart contract, is illustrated in the following diagram:

Keeper bots, while not shown in the diagram, are a crucial part of maintaining the integrity of the Mangrove order book. These bots are responsible for calling offers that are likely to fail and collecting the provision paid by the maker. This incentivizes third parties to deploy bots that scan and clean the exchange's order book. The provision is always calculated using the upper gas bound, making it profitable for keepers to keep the order book organized. Overall, keepers are essential for ensuring that using Mangrove is a seamless and enjoyable experience.

When it comes to governance, Mangrove will issue a token. The specifics of the tokenomics have not yet been disclosed, but a portion of the initial supply will likely be allocated to outside investors. Once the token is released, Mangrove token holders will have the ability to vote on various aspects of the protocol, including potential incentives for liquidity providers or offer takers to use the platform. The Mangrove community will also be able to vote on which blockchains the protocol should expand to or build protocols on top of Mangrove (as the community does with Curve or GMX).

Navigating Mangrove's potential risks and uncertainties

While Mangrove is a promising new protocol, it is not guaranteed to succeed. There are a few potential challenges that the DEX may face. One question is whether the Polygon will be able to handle the high level of throughput required for a fully on-chain order book-based DEX. dYdX has argued that even L2s may not be able to support the scale of the order book and matching engine. One specific issue that may be difficult to manage at a reasonable cost is the need for constant order updates due to nonstop price changes. Mangrove addresses this issue by allowing for updates to be made in a single transaction, eliminating the need to cancel and repost offers.

Mangrove team surely has thoroughly researched this aspect and determined that Polygon is suitable for their needs. It's worth noting that other protocols that require a large amount of data and transactions, such as Lens Protocol (a decentralized social media platform), have also chosen Polygon as their home blockchain. If it turns out that using Polygon does not guarantee a smooth experience, there are always other L2 EVMs available as an alternative.

Another potential risk for Mangrove is the possibility of malicious code being attached to an offer due to the platform's fully permissionless market making. To address this concern, Mangrove contracts have undergone thorough auditing by Chainsecurity, which did not find any critical vulnerabilities in the code. While this does not guarantee the security of the protocol, it is a positive sign that the protocol has been well-designed.

Wrapping up

Any healthy market needs to have strong liquidity. Currently, the most popular liquidity provision methods have their drawbacks:

• AMMs often have high slippage, are generally not capital efficient, and spread capital across many pools.

• Oracle-based exchanges do not scale well, are at risk of market manipulation, and have no price discovery mechanism.

• Centralized exchanges aren’t either transparent or trustless, and don’t offer capital efficiency for market makers.

With these factors in mind, it is safe to say that bringing the order book model onto the blockchain presents a significant opportunity and will be one of the major narratives in the DeFi space in the coming months and beyond. Many competing projects will be trying to solve the challenges of operating an order book on the blockchain, but the first to succeed will have the chance not only to disrupt the current DEX model, but potentially make centralized exchanges obsolete in the longer term.

Mangrove, with its highly capital-efficient "code-is-offer" feature, is uniquely positioned to address all the pain points that both centralized and decentralized exchanges face. It probably will not be an overstatement to say that this is a once-in-a-lifetime disruption opportunity.

Staking vs. Restaking

A majority of you are already familiar with the concept of Ethereum staking. Yet, for clarity's sake: staking was introduced to Ethereum together with its transition to a proof-of-stake consensus mechanism. In essence, the consensus mechanism enables all participants in a blockchain network to achieve an agreement on the state of the blockchain and authenticate initiated transactions.

To participate as a validator in the Ethereum network, an individual or entity must stake at least 32 ETH, which might be prohibitively expensive for some. Upon staking Ether, it gets locked, and in exchange for verifying transactions, validators earn rewards. However, falling short in validation duties or engaging in malicious activities can lead to slashing of the portion of the staked ETH.

Given the high threshold of 32 ETH, staking pools and protocols have emerged. They allow individuals to collectively stake their ETH, reach the mandatory limit, and consequently share the rewards and risks. Lido, the most prominent among these platforms, has a staggering TVL of 14 billion USD.

This brings us to restaking and its soon-to-rise prominence (and the accompanying controversies) in the Ethereum community.

Restaking protocols, in essence, enable ETH – whether in its native form or as liquid staking tokens (LST) like stETH – to be used for consensus in other apps or protocols. In practical terms, a restaking service such as EigenLayer aggregates ETH, locks it up, and then uses it to secure apps or modules needing a consensus layer but lacking their own.

Let's dive into the nuances of EigenLayer – its mechanics, possibilities, and the reasons behind its controversial status.

The inception of EigenLayer started with Sreeram Kannan. As an academician, Sreeram's research spanned across fields as varied as information theory and computational biology. Interestingly, his dive into the realm of consensus mechanics was spurred by Yuval Noah Harari's best-selling book, "Sapiens". Harari proposes that homo sapiens’ unparalleled ability to create extensive cooperation networks, even among vast groups of unrelated individuals, set them apart from other species. For humans, consensus became paramount, and this inherent trait influenced Sreeram's research.

However, despite the initial enthusiasm, Sreeram hit a roadblock in his studies. That was until a colleague introduced him to blockchains. Recognizing the potential of blockchains as a modern manifestation of consensus systems, Sreeram pivoted back to his original research, culminating in the birth of EigenLayer.

At its core, EigenLayer is a collection of smart contracts on the Ethereum blockchain. The platform is currently anchored by two primary smart contracts: the EigenPod, for native Ether stakers, and the Strategy Manager, which facilitates LST restaking. As EigenLayer evolves, it will offer a sandbox where developers can introduce their smart contract modules. These modules, while serving their primary functions like bridging or validating transactions, will integrate with EigenLayer, allowing participants to provide ETH to validate the modules’ outputs.

For context, Ethereum operates on a dual-layered system with:

1. Beacon Chain (consensus layer) which Underpins the network's consensus mechanism, where transaction validation happens.

2. Ethereum Virtual Machine (execution layer) where the smart contracts’ code gets executed.

In essence, while the Beacon Chain guarantees that validators agree on a single, unified version of the transaction history, the EVM ensures these transactions are executed.

EigenLayer, in its vision and design, aims to leverage and extend this dual-layered structure, introducing the restaking mechanism to share the security of Ethereum across its broader ecosystem.

Actively Validated Services

Within the EigenLayer framework, the modules we have discussed are referred to as Actively Validated Services (AVS). These are apps in need of consensus for their operation. As detailed in the EigenLayer whitepaper, potential instances of AVS include sidechains, data availability layers, new virtual machines, keeper networks, oracle networks, and bridges, among others. A criterion for AVS is compatibility with the EVM. If a module cannot run on the EVM, it will not be able to leverage EigenLayer's restaking.

Why might an AVS choose to use EigenLayer's services? The primary reason is to tap into the robust security of Ethereum, arguably the most secure decentralized network in the world. However, there are other benefits:

1. Reduced capital costs: There's no need to set up and maintain expensive hardware nodes to keep the network running.

2. Enhanced Security: AVS secured by their tokens can be more vulnerable to threats from bad actors. For instance, an oracle secured by its token would likely be less secure than one secured by staked ETH.

AVS offers flexibility in determining the security of their protocols. For instance, they can set criteria such as only validators staking a certain amount of ETH can provide security; or only native stakers can participate, or limiting participation to smaller stakeholders only. The conditions for restaking depend solely on what the AVS needs. As a result, it can be argued that restaked Ether might offer better security than the one Ethereum has. This would be true if certain groups of stakers were excluded from securing specific modules based on these bespoke requirements.

Restakers

Let’s take a look from another angle - what’s there for a restaker (either native, LST, or ETH LP pair holder)? Of course, there are economic incentives. Restaking will allow to use of the staked Ether and provide security to other applications without resigning from staking on Ethereum. It means, that while earning fees offered by Ethereum, one can have additional income from multiple other modules, increasing the overall rate of return on capital. The rewards from these other protocols could come in their native tokens, or other assets.

So far so good, but with staking comes a risk of slashing. In proof of stake systems, a malicious actor who validates a block with an invalid transaction can be subject to slashing. With slashing, the part of the stake owned by the actor is taken away from him.

In EigenLayer the rules of slashing will be specified in smart contracts deployed by AVS and similarly to the rules of restaking, can be set differently for each module.

Eigenlayer provides pooled security, which means that the entire restaked ETH can, in theory, be used for the security of all modules running on the protocol. In practice, the limitations will be set by restakers who would be able to choose which modules and under which circumstances to support.

Risks

The broader Ethereum community is engaged in debates regarding the potential risks introduced by restaking, both to the ecosystem at large and to Ethereum itself. In the most severe scenarios, the integrity of the blockchain could be compromised. Fortunately, Shreeram and the EigenLayer team have shown an openness in addressing these concerns.

In relation to EigenLayer, three principal risks have been identified: (1) A synchronized attack on multiple AVSs concurrently, (2) An unintended slashing event affecting a considerable volume of staked Ether, and (3) Centralization.

(1) Concurrent Attacks on AVSs

EigenLayer's model enables stakers to secure multiple AVSs. However, not all stakers will choose to secure every single AVS, leading to potential discrepancies between the value of assets locked in an AVS and the security value offered by the stakers.

Consider a scenario where five AVSs lock a combined value of USD 10 million, yet they're secured by an ETH stake worth USD 6 million. How? Each AVS, locking in USD 2 million, may theoretically be secured by a stake larger than its locked value. Given that the collective restaked ETH exceeds this figure, each AVS might appear to be secured by an ETH stake worth 6 million. However, given that this 6 million can also support other AVSs, it creates an asymmetrical avenue for stakers to collude. This could allow them to, at the expense of up to USD 6 million, compromise modules valued at USD 10 million.

Such a vulnerability seems highly concerning. So, how does EigenLayer propose to mitigate this risk? They suggest the deployment of a Dashboard, dedicated to monitoring staker activities. This platform would enable AVS operators to preemptively spot potential attack vectors. The mechanism involves comparing the Total Value Locked (TVL) in an AVS to the stake securing it, as illustrated earlier. Should a substantial number of operators be found securing a specific AVS (and concurrently backing other modules via EigenLayer), the Dashboard will alert the AVS. Specifically, it would indicate if a group of stakers, who are also backing other AVSs, has a dominant stake that could enable abuse. To counteract this, the AVS might restrict its securing stakers to only those with a minimal number of other secured modules.

Is this a foolproof solution? There remain scenarios where sidelining a set of stakers might lower the bar for a successful attack by the remaining parties. And that’s probably not the only way to exploit this vulnerability.

(2) Unintended Slashing Events

Another possibility is the unintended slashing of a group of stakers that secure a large protocol or Layer 2. Such slashing might be initiated due to a vulnerability in a contract, leading to significant losses for honest participants.

How does EigenLayer intend to counter this risk? An assumption is that when an AVS begins to engage in restaking, it's reasonable to anticipate that restakers would act cautiously, refraining from committing a sizable chunk of their ETH to secure that module. Is this a sound expectation? Probably not in crypto.

Sometimes vulnerabilities come to light well after a protocol has been operational. This suggests that particularly during the early stages when slashing contracts are getting rolled out, the risks of slashing will be higher. EigenLayer's strategy is also to ensure thorough audits of every slashing contract prior to its deployment, though the effectiveness of this measure is also dubious.

A more robust safeguard against unintended slashing is the establishment of a veto committee. This body would have the authority to review any slashing incident, determining if the operator was genuinely at fault or if the slashing was unintended and hurtful to honest participants. Comprising highly reputable figures from the Ethereum and EigenLayer communities, this committee's decisions could be implemented via a multisig. However, this introduces another issue: if a slashing event impacts a significant module within the Ethereum ecosystem, would the committee overrule the slashing, even if it was rightly executed?

Further complicating matters, community sentiment might lean towards executing a hard fork of Ethereum to revert to a pre-slashing state in such scenarios. It's not implausible that, for particularly vital protocols, there exists a temptation of moral hazard, i.e., accepting heightened risk under the belief that any missteps would simply be rectified via a community-driven hard fork. This very risk, characterized as a grave threat to Ethereum brought about by restaking, is underscored by Vitalik in his article mentioned in the beginning.

(3) Risks of Centralization

In a manner similar to the risks tied to LSTs, with Lido being a dominant player, EigenLayer too faces potential centralization challenges. Given the complexities that EigenLayer introduces relative to standard or liquid staking (risks of slashing, knowledge of different types of modules, etc.), it's likely that better-financed validators will emerge as leaders. As a result, many users might find it reassuring to delegate their ETH or LSTs to these entities for restaking. If a validator can promise better returns on top of the standard rewards distributed by Ethereum, then there's little incentive for stakers to look elsewhere. EigenLayer's structure allows this. Consequently, the most technically sophisticated validators might amass a disproportionately large portion of restaked ETH or LSTs. This concentration of resources can evolve into a single point of vulnerability, undermining the decentralized ethos of the ecosystem.

Conclusions

At its core, blockchain is about decentralized consensus, and EigenLayer is stepping up to extend this consensus using the stake of what's widely seen as the most secure blockchain network - Ethereum. The magnitude of this shift cannot be understated.

EigenLayer stands out as one of the most pioneering, exciting, and influential projects in the current crypto space. It will establish a market where apps in need of security can tap into the resources of those ready to offer security at a price. While EigenLayer's approach is highly disruptive, it does carry inherent risks, some of which could be catastrophic for Ethereum.

Given the potential consequences of things going south with EigenLayer, it's paramount for the community, Ethereum's devs, and EigenLayer's team to closely monitor the protocol's evolution. Thankfully, Shreeram with his philosophical and highly technical approach appears to be the right person heading this project. Restaking was inevitable, so it is reassuring to see that he genuinely seems to have Ethereum's well-being at heart.

The endgame for EigenLayer is to become an integral part of the Ethereum protocol. While the debate on enshrining is a topic for another article, it could potentially be a solution to the restaking conundrum. Exciting times ahead, lads.

My main source for the article was Whitepaper of Eigenlayer.

Remember the matrix-form polynomials we obtained from the QAP transformation in our previous article? When we multiply them by the solution vector s [1, 5, 37, 25, 30], we get the following polynomials for each matrix: Ap [-38.0, 52.0, -9.0], Bp [13.0, -10.0, 2.0], and Cp [22.0, 2.0, 1.0]. After multiplying these polynomials together, we obtain the final polynomial:

$$$ -516x^4 + 1054x^3 - 714x^2 + 194x -18 $$$

This polynomial encapsulates the computations we performed and the ultimate solution to our initial problem. If someone knows this polynomial, they can claim to know the solution to the problem:

$$$ x^2 + x + 7 = 37 $$$

Polynomials are useful in cryptography because they can represent complex mathematical constructs and be used for encrypting and decrypting messages. They also can store large amounts of data, as we saw in the previous article. Furthermore, finding intersections between two slightly different polynomials by randomly picking points is extremely difficult, as we will see shortly.

The degree of a polynomial is determined by the highest exponent of an x coordinate within the polynomial. For example, the polynomial of degree 3:

$$$ x^3 - 2x^2 + 1 $$$

Let's compare this polynomial to another similar one:

$$$ x^3 - x^2 + 1 $$$

and see how they fit on the coordinate plane. Despite their near-identical nature, their positions on the plane differ significantly. The key takeaway is that finding two distinct polynomials with common points is almost impossible.

To find out if two polynomials share a common point (or cross paths), we need to set them equal to each other. Take this example:

$$$ x^3 - 2x^2 + 1 = x^3 - x^2 + 1 $$$

Solving for x gives us x = 1, a polynomial of degree 1. This means they only intersect at one point, which is x = 1. So, a polynomial of degree d can have up to d intersection points. This tells us that evaluating a polynomial at certain points gives us an accurate representation of the whole polynomial.

In this situation, a prover can show to a verifier, who knows a specific polynomial, that they know the polynomial too by evaluating it at certain points. For a polynomial of degree d and a coordinate x in the range

$$$ \langle 0, 10^{10} \rangle, \text{there's a} ; \frac{d}{10^{10}} $$$

chance that this polynomial has some overlapping points with another polynomial.

Another critical property of polynomials from a cryptography perspective is their ability to be factored. All polynomials with a valid solution (resulting in 0 after evaluation for x) can be reduced to separate degree 1 polynomials. For example, the polynomial:

$$$ x³ + 3x² + 2x $$$

is equivalent to (x+0)(x+1)(x+2). By looking at the factored polynomial, it's easy to identify its solutions (or roots): 0, -1, and -2.

Let's say a prover claims to know a degree 3 polynomial that has roots at -1 and -2. We can then determine that the polynomial will be (x+1)(x+2). As the prover knows a degree 3 polynomial, there must be another polynomial, z(x)which yields the desired result when multiplied with the target polynomial:

$$$ t(x) = (x+1)(x+2) $$$

Thus, we have the equation:

$$$ p(x) = t(x) * z(x) $$$

With this knowledge, how do we find z(x)? We can divide the polynomial p(x) by the target polynomial t(x), resulting in:

$$$ z(x) = \frac{p(x)}{t(x)} $$$

Now, if the polynomial p(x) indeed has roots at -1 and -2, the division outcome will not have a remainder. Let's examine this using our example and perform the calculation:

In the example above, we transformed the target polynomial t(x) from its factored form (x+1)(x+2) to x^2 + 3x + 2. This calculation gives us a result of z(x) = x, with no remainder. Now, let's see what happens when we make a small change to the polynomial p(x) for comparison.

The polynomial p(x) now begins with 2x³ instead of x², resulting in a division remainder of 7x+6!

With this understanding, we can develop a simple protocol where:

1. A verifier randomly generates a value x, evaluates the target polynomial t(x), and provides the value x to the prover.

2. The prover evaluates the polynomial p(x) at the given value x, calculates h(x), and provides evaluations of p and x to the verifier.

3. If the equation p(x) = t(x) * z(x) holds, then p(x) has factors t(x).

Note that the values the prover provides to the verifier are evaluations of the polynomial at x, so the verifier does not know the polynomial itself. However, this protocol allows the prover to cheat and compute another polynomial by merely selecting a random value of z(x). Additionally, it doesn't enforce the polynomial's degree, as the verifier can create a polynomial of any degree that makes p(x) = t(x) * z(x) hold. Both limitations will be addressed later.

Before we dive into commitment schemes, let's explore modular math and prime fields.

A prime field p is a group with p elements that is generated by a single element g, and every element in the group can be written as g^k for some integer k in the range {0, 1, 2, ..., p-1}. The group's order is equal to the number of elements in the group, which is p. A simple example of a prime order p group is the group of integers modulo a prime number p.

For example, if we choose p = 7, then Z_7 is the cyclic group {0, 1, 2, 3, 4, 5, 6}. Let's choose the generator g = 3, which means that the powers of 3 modulo 7 generate all the elements in the group:

$$$ \begin{align*} 3^0 &\equiv 1 \pmod{7} \ 3^1 &\equiv 3 \pmod{7} \ 3^2 &\equiv 2 \pmod{7} \ 3^3 &\equiv 6 \pmod{7} \ 3^4 &\equiv 4 \pmod{7} \ 3^5 &\equiv 5 \pmod{7} \ 3^6 &\equiv 1 \pmod{7} \end{align*} $$$

In modular math, the result of a calculation is expressed as the "remainder" from the calculation on the left-hand side and division by p. In the above example, the first two results don't leave any remainder, as the numbers are smaller than p. But, for any calculation where the result is greater than or equal to p, the modular calculation outcome will be the remainder (though division is more complex).

Why is this important? In cryptography, modular arithmetic is useful to ensure that a committed value or hashed input remains concealed. If we operated on natural numbers, it could be easier to reverse engineer the hiding of an underlying value, weakening the protocol. But, when using modular arithmetic and limiting the results of any calculation to a few possible outcomes, it's much harder to return to the original value, as many different starting points can lead to the same result.

Now that we've learned about two powerful mathematical tools in cryptography - polynomials and modular math - let's delve deeper.

A cryptographic commitment scheme is a technique that allows someone to commit to a value without revealing it and later prove that the value hasn't been changed or tampered with.

In a commitment scheme, the committing party uses a mathematical algorithm (like a hash function) to create a commitment, which is a fixed-length string representing the hidden value. The commitment is shared with the other party, who can't deduce anything about the value from the commitment itself.

To illustrate this idea, imagine Alice and Bob, two friends who love playing games together. Alice has to leave town for a while, but they decide to keep playing games over the phone. They choose rock-paper-scissors but, being competitive, they don't trust each other to reveal their picks honestly. So, Alice and Bob create a protocol for playing rock-paper-scissors remotely:

1. They agree on a cryptographic hash function, such as SHA-256.

2. They agree on a secret "salt" value that'll be added to each move before hashing to prevent pre-computed hashes. The salt should remain secret and change after each round.

3. Alice and Bob secretly pick a move each.

4. They both compute a commitment to their move by hashing their move and the salt value with the agreed hash function. For instance, Alice might calculate: H(Alice's move) = SHA-256("rock" || salt) where "rock" is her move and "salt" is the secret salt. Bob does the same for his move.

5. They exchange commitments over the phone, without disclosing their moves or the salt value.

6. After exchanging commitments, they "reveal" their moves and the salt value by telling each other their choices and the salt value.

7. They verify that the other player's commitment matches the revealed move and the correct salt value by hashing the move and salt value together.

Alice and Bob can now repeat steps 4-7 for as many rounds as desired, changing the salt value after each round.

Polynomial commitment schemes (PCS) work like cryptographic commitments, but for carrying information they use polynomials instead of regular statements. In a PCS, a prover wants to show to a verifier that they know a polynomial without revealing its coefficients. To do this, the prover creates a commitment to the polynomial and the verifier can then use this commitment to make sure the polynomial is correctly computed at specific points, without actually seeing the coefficients.

Each PCS needs to have the following properties:

• Binding - different polynomials can't result in the same commitment.

• Hiding - a commitment doesn't give away any information about the polynomial.

These properties are similar to the one-wayness and collision resistance of hash functions. There are different types of PCS used in ZK-SNARKs, and each has its pros and cons. The most popular commitment scheme is KZG (from Kate, Zaverucha, Goldberg). Other commitment schemes with different properties used in SNARKs are FRI and DARK.

KZG boasts several distinct features that make it particularly useful for SNARKs:

• Generates constant-size proofs regardless of polynomial length (a single elliptic curve group element).

• Offers constant verification time (two pairing operations).

• Uses elliptic curve pairings as its cryptographic engine.

However, KZG needs a trusted setup, which means a trusted party (or parties) has to generate secret, random values to hide the polynomial (akin to Alice and Bob's "salt" value in their phone game). These values, used to calculate a common reference string (CRS), should then be destroyed so nobody can learn them and break the protocol.

In practice, to lower the risk of a malicious agent, multiple parties join the trusted setup creation process and generate their own parameters ("salt" values), which are multiplied by values created by other participants (Multi-Party Computation, or MPC). With this approach, as long as one party is honest and doesn't share its generated parameters, the whole procedure stays safe. When you hear about a "ceremony" for a trusted setup, that's what's going on.

Elliptic curve pairings are a complex encryption technique that employs advanced mathematical algorithms to protect data. They utilize an elliptic curve along with a special mathematical operation called a pairing to perform cryptographic tasks.

An elliptic curve is a mathematical object that looks like a wavy line on a coordinate plane. It is defined by the equation:

$$$ y^2 = x^3 + a*x + b $$$

representing a smooth curve in a two-dimensional space (over a prime field). In the context of cryptography, elliptic curves are usually defined over finite fields, particularly over prime fields (integers modulo a prime number).

Pairing is a unique kind of function that combines two points on an elliptic curve to generate an element of a target group (a multiplicative group of a finite field). Bilinear pairings are the most frequently used pairings in cryptography. For a pairing e: G1 x G2 → GT, where G1 and G2 are cyclic groups and GT is the target group, the function e is bilinear if it satisfies the equation

$$$ e(g^a, f^b) = e(a^g, b^f) = e(ab^{gf}) \quad \forall g \in G_1, f \in G_2 $$$

and integers a and b. Elliptic curve pairings thus enable the multiplication of exponents in the polynomial encrypted in this form, which is not possible with other encryption forms (e.g., hashes).

With all this information, we are now ready to build our zk-SNARK.

Constructing a zk-SNARK with the KZG polynomial commitment scheme

Step 1 » Calculating the polynomial

We begin by calculating the polynomial using the QAP procedure discussed in the previous article. The polynomial is represented as t(x) with degree d

$$$ t(x) = -516x^4 + 1054x^3 - 714x^2 + 194x - 18 $$$

Step 2 » Establishing the trusted setup

• A trusted party (or multiple parties in MPC) generates a secret, random value s used to encrypt the polynomial. This secret value s is produced in the prime group g as:

  $$$ g^s, g^{s^2}, g^{s^3}, \ldots, g^{s^n}

  $$$

• Group g constrains the degree of the polynomial used in the commitment.

• The secret value s and group g form a Common Reference String (CRS) when evaluated with the polynomial’s coefficients, with each coefficient evaluation being a point on the elliptic curve. After generating the CRS, the value s must be deleted.

• With the trusted setup in place, we can commit to polynomial t at point s, as shown in the expression below:

  $$$ t(s) = g^{t(s)} = g^{-516s^4 + 1054s^3 - 714s^2 + 194s - 18} $$$

Step 3 » Proof generation (opening)

• To prove the commitment to the polynomial t(x), the prover must "open" the commitment at the point s (even though its value remains unknown). The prover evaluates the polynomial using the CRS's publicly available values, all hidden within the group g.

• Next, the verifier selects another point z and provides it to the prover. The prover calculates the polynomial:

  $$$ h(x) = \frac{p(s) - p(z)}{s - z}

  $$$

  Now, let’s revisit our earlier example with the target (vanishing) polynomial. The prover has to find a polynomial that satisfies the condition p(s) - p(z) = 0, which naturally occurs when s = z. Consequently, the value s - z divides the polynomial p(s) - p(z) without remainder. The fact that there is no remainder will serve as proof of the evaluation of the polynomial at the point z.

  Although complex, this calculation lies at the heart of the KZG polynomial commitment scheme, making it essential to understand. Feel free to get back to the section about polynomial properties, if required.

• As x can take any value, the prover evaluates the proof h(x) at s instead of x. This results in equality

  $$$ p(s) - p(z) = (s - z) * h(s) $$$

  which serves as proof of the evaluation. The prover sends this proof to the verifier.

Step 4 » Evaluation

• The proof received by the verifier requires further transformation because s is unknown. To represent x as a point on an elliptic curve [x], we add x to itself g times, where g is a prime field group. The original polynomial evaluates to:

  $$$ [p(s)] = g \times (-516s^4 + 1054s^3 - 714s^2 + 194s - 18)

  $$$

• The relationship to be verified looks then as follows:

  $$$ [h(s)] * [s - z] = [p(s)] - [p(z)] $$$

• Each value has been transformed into a point on an elliptic curve:

  • [h(s)] represents the evaluation of h(x) using CRS values, added to itself g times, equivalent to a commitment to h(s).

  • [p(s)] represents the evaluation of the original polynomial p(x) at CRS values, added to itself g times.

  • [p(z)] represents the evaluation of the polynomial p(x) at the verifier-provided value z, added to itself g times.

  • [s - z] corresponds to the difference between s and z, evaluated at CRS values. However, we can't do much about it now since s is secret.

Also, note that elliptic curve points can't be directly multiplied, so calculating the below part will require the elliptic curve pairings:

$$$ [h(s)] * [s - z] $$$

Step 5 » Verification

• To verify the proof, we work with two prime groups, G1 and G2, and their generators g and f, respectively.

• Let’s denote the addition of the secret point s in group G1 g times as [s]1, and the addition of s in group G2 f times as [s]2.

• The pairing of G1 and G2 is denoted as GT, a multiplicative target group.

• With [s - z] in group G2 and [p(z)] in group G1, the verifier checks the equality:

  $$$ e(h(s), [s - z]^2) = e([p(s) - p(z)]^1, f)

  $$$

• The above equation presented in the pairing group looks as follows:

  $$$ [h(s) \cdot (s - z)]^T = [p(s) - p(z)]^T, \quad \text{where} ; [x]^T = e(g,f)^x

  $$$

• This equation is equivalent to our familiar

  $$$ h(s) * (s - z) = p(s) - p(z) $$$

• and the verifier can finally confirm if it holds! Let's take a breath and review each part once again:

  • [h(s)] is provided by the prover.

  • z is selected by the verifier.

  • [s - z]2 can be computed using [s]2 (calculated in group G2 during the trusted setup) and verifier-selected z. Calculating [s - z]2 is equivalent to [s]2 - [z]2.

  • [p(s)] is the commitment provided by the prover.

  • [p(z)]1 is calculated and provided by the prover at the verifier's request.

And there you have it! The verifier successfully confirmed whether the prover truly knows the polynomial they claimed to know. Quite the adventure, right?! To summarize the entire process:

1. In the trusted setup, a random value s is generated along with two sets of elliptic curve points [s]1 and [s]2. The value s is then discarded.

2. The prover commits to the polynomial p(x) using CRS elements from the trusted setup.

3. The verifier selects point z and shares it with the prover, requesting the evaluation of z with p(x).

4. The prover evaluates p(z) and shares the proof with the verifier in the form of an elliptic curve point h(x).

5. The prover calculates the pairing equation and confirms if it holds.

Congratulations if you made it through! Don't hesitate to re-read any sections you didn't fully understand. It took me some time for all of this to click, so don't be discouraged if everything isn't clear even after a few reads.

In Part III of this article series, we will look into other types of commitments focusing on transparent proofs, an alternative method that doesn't require a trusted setup. Stay tuned as we explore their inner workings, advantages, and drawbacks.

I couldn’t write this piece without the following sources:

• Vitalik Buterin, Understanding PLONK

• Dankrad Feist, KZG Polynomial Commitments

• Ozgur Ozerk, KZG Polynomial Commitments (based on Dankrad’s article)

• Alexander Comerford, Understanding KZG Polynomial Commitments

• David Wong, How does PLONK work?

• Maksym Petkus, Why and How zk-SNARK Works: Definitive Explanation

GMX is a great example of a protocol that has embraced this philosophy. It has been available for just over a year but has already established itself as a major player in the space thanks to its impressive fee generation and TVL. As with many great projects, its success is the result of a combination of elegant design and innovative thinking. But what sets GMX apart? Let's take a closer look.

What is GMX and how does it make money?

GMX is a perpetual exchange that runs on the Arbitrum and Avalanche blockchains, with the majority of activity happening on the former. Perpetual exchanges are platforms for trading perpetual futures contracts, which are like regular futures but don't have an expiration date. With GMX, you can speculate on the price of an asset without actually owning it.

GMX has two tokens: GMX for governance and GLP for pooling assets from lenders. The GLP token is an index of blue-chip tokens that consists of about half stable assets and half risky assets. Users can deposit supported tokens into the pool in exchange for GLP tokens. The current index composition and target weights on the Arbitrum chain (which will be used for all future references) are as follows:

A crucial feature around which GMX is built is that, unlike traditional DEXes that rely on the constant product market maker model (x*y=k), GMX utilizes Chainlink oracles to feed price data from centralized exchanges, enabling trades with no slippage. While this is a positive for traders, it also leaves the protocol vulnerable to price manipulation and limits its scalability potential. We will delve into these issues later on.

GMX incentivizes participants to deposit underweight assets or withdraw overweight assets by structuring the fees accordingly - it’s less expensive to deposit underweight assets or withdraw overweight ones than another way around. This is the first way the protocol generates revenue - through the minting and burning of GLP tokens.

The protocol can also function as a DEX, where GLP index tokens are traded. To incentivize users to maintain the optimal asset mix in the pool, GMX adjusts trading fees based on the desired balance of assets. This is the second way the protocol makes money.

The third way GMX generates revenue is through margin trading. The protocol charges a fee of 0.01% on the size of the position whenever a position is opened or closed. Additionally, GMX has a borrow fee of 0.01% per hour, which is calculated based on the ratio of borrowed assets to total assets in GLP. When a position is closed at a loss or liquidated, the resulting profit goes to the protocol. This is where the majority of GMX’s earnings come from, so let’s take a look at those in more detail:

Since its debut in September 2021, GMX has generated an impressive $40 million in profits (on Arbitrum alone and not including fees). When you factor in the fees, the protocol has been wildly successful, with a total haul of $135 million on Arbitrum and an additional $31 million on Avalanche.

The generated earnings are then shared with GLP and GMX token holders. The protocol rewards GLP holders with a 70% cut of the fees they earn, which can translate to APR in the 20-40% range (depending on the amount of fees collected in a given week). It is not discouraging that the rewards are paid in wETH/AVAX and escrowed GMX. GMX token holders receive the remaining 30% of the accrued fees, which amounts to approximately 10-20% APR.

GMX is self-funded, so no VCs are lurking around ready to dump on retail. The protocol is designed to prioritize the community, with the distribution that allocates only 2% of the GMX tokens to the team (250,000 out of a total of 13 million). As for the future, the number of tokens in circulation may increase beyond the current 13 million if the DAO votes in favor of it.

As a GMX token holder, staking your tokens not only allows you to earn rewards but also grants you the opportunity to participate in governance and rack up Multiplier Points to enhance your rewards (similar to veCRV in Curve Finance). While the esGMX tokens are locked up for a year, they can still be staked to earn rewards just like regular GMX tokens.

Holding GMX tokens is essentially a bet on the continued growth and adoption of the protocol, without exposing investors to the risks of being a counterparty to traders via holding GLP. However, if something were to happen to GLP, the value of GMX tokens would plummet in no time.

Risks for GMX and GLP holders

While the protocol is well-thought-out in terms of earnings and rewards, are there any design flaws that could hinder its scalability or cause it to crash? To answer this question, we need to dive a little deeper into how GMX operates.

As previously mentioned, the protocol relies on Chainlink oracles to feed asset prices to its ecosystem. This eliminates slippage but also exposes GLP holders to market manipulation. In early 2022, a trader on Avalanche exploited this vulnerability by opening and closing a series of long/short AVAX positions on GMX while simultaneously manipulating the price of the coin on centralized exchanges. This scheme resulted in a loss of approximately $500,000 for GLP holders, although it's possible that the attacker didn't profit at all due to the overall costs incurred. The GMX team responded swiftly by imposing limits on AVAX's open interests, though this isn't exactly the embodiment of a trustless protocol.

Might something akin to the AVAX incident occur on Arbitrum? It's not out of the realm of possibility, although the greater liquidity of ETH and its larger market cap make it less prone to price manipulation.

Another potential danger for the GLP pool is during times of extreme volatility. This could occur in the following way:

1. Multiple leveraged short positions are opened during a market downturn (resulting in a large net open short position in the protocol).

2. A significant piece of negative news hits the market.

3. The swift decrease in the value of risk-on assets in the liquidity pool causes the price of GLP to plummet.

4. The leveraged shorts’ profits are paid out from the stablecoins in the pool.

GLP is designed to fully back any open positions in GMX. As such, it's not possible to open a short position with more capital than is available in the pool (so that when all positions close, the protocol will still be able to pay out the rewards to all successful traders). This feature, combined with the restriction on short open interest, should prevent such an attack from occurring or having an outsized impact.

However, imposing a cap on open interest may present scalability issues. If the platform's GLP deposits increase while GMX is simultaneously capping short interest, the fees generated from trading will be limited, resulting in reduced returns for GLP holders and leading to the withdrawal of the funds from the pool.

A partial solution to this problem may be the introduction of something akin to a funding rate used on centralized perp exchanges. The funding rate is a fee paid by one side of a trade to another to ensure that the price of the contract stays aligned with the underlying asset. In the GMX context, if there is an excess of short or long open interest, the funding rate can be adjusted to even out the net difference in the positions.

One way to monitor the risk of the GLP pool is to keep track of net open interest on the platform. If the stablecoin portion of the pool is significantly greater, in USD terms, than the net short open interest in the protocol, GLP can be considered healthy. For example, if traders are net short USD 25 million and the stablecoins deposited in GLP are worth USD 200 million, the ratio would be 1/8, which would typically be considered healthy. The threshold for what is considered unhealthy may vary based on an individual's risk tolerance; for my part, I would consider leaving GLP if the ratio reached around 1/4. It's worth noting that liquidity providers can withdraw stablecoins up to the amount of the open short interest.

Since it is vital to keep an eye on the health of GLP, feel free to use my Dune query to check on the health of GLP here.

The query shows the current short, long, and net open interests along with the amount of stablecoins in GLP. The Health Factor is the ratio of net open interest (calculated only if negative), to the USD value of the stablecoins in the pool. Using the numbers from my above example, the factor of 12,5 should be safe, but if it goes up to 25, I would be thinking about getting out. This is a hypothetical scenario and most likely, if short interest were to run amok, the team would step in to tame it.

Glance at valuations

This article begins by highlighting the shift in the crypto industry towards a focus on financially sound, long-lasting protocols. Let’s then see how GMX performs when evaluated using some crucial metrics. For the sake of comparison, we will also assess dYdX, a competing crypto perp exchange that, much like centralized exchanges, follows the order book model. This model involves matching buy and sell orders and using a funding rate to balance the open interest between long and short contracts.

In December 2022, both protocols had a similar TVL of $460 million. However, over the past six months, GMX has generated $59 million in earnings, while dYdX has made approximately half of this at $38 million. That is what you call capital efficiency.

When looking at the price-to-sales ratio on the fully diluted market cap over the same time frame, GMX presents a relatively favorable factor of 12, while dYdX's ratio is less impressive at 24. For reference, Apple currently boasts a P/E of 23. It's important to keep in mind, however, that when evaluating businesses, expected future earnings are crucial. A company or protocol may have a high P/E or P/S ratio, but if it is anticipating to significantly grow earnings or sales in the future, the high ratio can be justified.

GMX is determined to increase its TVL by not only introducing new or upgrading existing products (stay tuned for the highly anticipated X4 release), but also by expanding to other blockchains. It will be fascinating to see if the protocol can maintain its advantage over dYdX, and how its oracle-based model holds against order book or AMM approaches.

Final thoughts

GMX is a formidable project that has carved out its niche in the DeFi world, proven itself to be resilient in difficult circumstances, boasts solid foundations, and has a flourishing ecosystem and grand expansion plans. Sure, there will be obstacles to overcome, particularly in terms of vertical scaling, but let's be real - creating a blue-chip protocol is no walk in the park.

From a user perspective, there are certain risks associated with holding GMX or GLP, but they are manageable, particularly given the robust and sustainable returns offered by the protocol. Does anyone still remember DeFi 2.0? I would argue it came with GMX.

Curve Finance is a decentralized exchange (DEX), that allows users to swap between stablecoins with minimal slippage. The protocol is based on the constant product market maker formula, a major innovation brought by Uniswap.

Decentralized exchanges such as Uniswap are great for trading assets with fluctuating price, but do not work well for pairs of stablecoins. The main issue is the price discovery mechanism of the constant product market maker model (CPMM) used by Uniswap and similar DEXes. This inherited design flaw may go unnoticed for trades where the price of at least one of the tokens is fluctuating (e.g. when buying ETH for USDC). However, when trading two coins with a similar price (e.g. USDC for USDT or ETH for sETH), it is much more annoying as it leads to bigger price difference between assets that should be priced 1:1. Let’s see how Curve optimizes this price discovery mechanism for stablecoins.

In the regular CPMM model, the total amount of coins in the liquidity pool is determined by the formula x*y=k, where x is the amount of token A (e.g. ETH), y is the amount of a token B (e.g. USDC), and k is constant. Since k is constant, to withdraw ETH from the pool, the user must deposit USDC in the amount determined as total ETH/total USD. Each ETH withdrawn will reduce the supply of ETH in the pool and increase the supply of USDC, thus driving up the price of ETH. This process can be represented by the following function, with the asset price shown as a point on this function.

As seen above, the price of two assets in the Uniswap model (purple dashed line) is more sensitive to changes in the pools’ reserves, resulting in a more curved invariant.

On the other hand, in the pool where the price changes evenly (the withdrawal of token A changes the price of token B by the same amount), the function is linear. As such, in this model, the sum of the prices of both assets is always constant.

Curve's innovative approach combines the best of both worlds by implementing the constant product and constant sum models in a way that the function is linear when the supply of coins is balanced but becomes more curved when there is a greater difference between the reserves. Thanks to this elegant solution, the protocol can offer better prices for trades between stable assets.

Tokenomics and governance

Curve attracts more trades by maintaining liquidity pools in balance and thus offering better swap prices. In turn, this earns more fees for the protocol, which are then distributed to liquidity providers in the form of the CRV token.

The CRV token is used to reward liquidity providers, share the revenue with the token holders, and to govern the protocol. The total token distribution is following:

While this is the release schedule:

Although initially aggressive, the issuance of CRV slows significantly over time. Additionally, the governance mechanism incentivizes holders to lock the CRV token for a period of up to four years, which significantly reduces selling pressure. Currently, the average lock time is 3.53 years. Upon locking the CRV tokens user gets vote escrow tokens or veCRV. The longer the locking period, the more ve tokens the user gets at the end of the lock period (the boost can get up to 250% in the case of the 4-year lock).

The CRV token is a reward for providing liquidity to the Curve pools. Every week, the holders of the veCRV tokens decide which pool receives the daily token emissions and how much of the emissions it receives (known as gauge weights).

Enter Curve Wars

The liquidity of a token is extremely important for the protocol issuing it. If there is deep liquidity, users can easily exchange the token without slippage. Additionally, it reduces the price impact of whales dumping their bags.

The governance and reward system of the Curve protocol incentivizes other protocols to accumulate CRV tokens, lock them into veCRV, and direct the rewards to their own pools. This make it worth for the protocols to convince liquidity providers to direct their tokens into the pools offering the most attractive yields.

The Curve Wars began when a few well-known protocols competed for the largest share of the veCRV market. The winner of the wars was Convex, a protocol originally designed to live in symbiosis with the Curve ecosystem.

Liquidity providers earn CRV tokens for providing liquidity to the pools in the Curve protocol. The yield on their LP positions depends on, among other things, the amount of veCRV tokens they own, as shown below. Individual holdings would have an insignificant impact, but what if you pool the scattered resources?

The Convex protocol enables users to collect CRV tokens from their holders, put them in the Curve LPs, and then share the rewards among the investors. In addition, the investors also receive the Convex CVX token as a reward. Through this clever incentive structure, Convex won the Curve wars and currently controls whopping 53% of the total veCVR supply.

The story here just keeps getting more complicated. For every CRV locked into the protocol, Convex gives the investors cvxCRV tokens. These tokens can be exchanged freely, so Convex provides a way to get the benefits of locked CVR in a liquid form. Another advantage of holding cvxCRV is that you can set gauge weights in the Curve liquidity pools.

Let’s recap how we got to this point:

1. The investor deposits CRV tokens into Convex and receives liquid cvxCRV in exchange

2. Convex locks pooled CRV tokens into Curve and directs future CRV emissions to the Curve liquidity pools of its choice through a Curve DAO vote

3. The vote is made through Convex DAO by cvxCRV holders

Now, if a protocol wants to direct CRV emissions to their pools, instead of buying the CRV tokens, the protocol can load onto the cvxCRV and rule the gauge weights in Curve! Or does it have to? Maybe a little bribe here and there would be good enough?

Bribery

In the world of DeFi, even bribes are public. There's no need to panic, everything is alright.

This is where Votium comes in. Votium allows protocols that are interested in increasing the liquidity of their tokens (which is why the complex machinery described in this article was put in place, in case you forgot) to bribe CVX holders to direct the Curve emissions to their pools.

The whole idea is based on a simple incentive - it is cheaper to buy a vote with CVX tokens than it is to become a CVX holder. For the last couple of months, one CVX vote has cost between $0.05 and $0.09, while one CVX token, at the time of writing, buys around 5.7 votes and costs $3.9. That’s a 10x difference! What’s more, by staking CVX tokens, you receive further rewards from the Convex protocol at around 3%, and another 27% from the bribes on Votium (if you vote or delegate your votes there).

These are the Cruve Wars, won by Convex, fueled by the Votium bribes.

Personal take

Curve Finance is a masterpiece of crypto innovation and the protocol governance. The design of the rewards, sustainable tokenomics and innovative stableswap feature make it clear why Curve is and will remain one of the top DeFi protocols for a long time.

The decentralized finance revolution began a few years ago and flourished in 2020 during DeFi Summer. It's only a matter of time before it becomes mainstream.

I’m here for the journey and will write about other protocols that bring innovation and move the industry forward, so stay tuned!