Detailed explanation of Boojum upgrade: why zkSync Era chose the STARK proof system

Author: zkSync; translation: Jinse Finance xiaozou

Main points of this article:

Upgrade: zkSync Era is transitioning to a new Boojum proof system without regenesis.

**Performance: **Boojum has demonstrated world-class proof performance, helping the performance of the zkSync Era sorter, which can already handle over 100 TPS.

**Decentralization: **Boojum prover (certifier) only needs 16 GB RAM, which supports large-scale decentralization of prover in the future.

**Ready:**Shadow proving (shadow proof) has been launched on the mainnet!

As we articulated in our ZK Credo manifesto, zkSync's mission is to advance personal liberty for all by building a blockchain network that is trustless, secure, permissionless, affordable, easy to use, resilient, and infinitely scalable , making digital self-ownership generally available.

In pursuit of this mission, the Alpha version of zkSync Era was opened to the public more than three months ago and has received an amazing response. We've seen a lot of activity on the web during this time.

Network Highlights:

· $577 million in total locked value (source: L2Beat).

23.75 million transactions processed in the past 30 days - the most by L2 (source: L2Beat).

· 9735 source code verified smart contracts.

In March 2023, we launched zkSync Era, using a SNARK-based system to support our zkEVM, utilizing the proven circuit framework, and has supported zkSync Lite on mainnet for nearly three years. However, we know this is not the end of the zkSync Era proof system, we designed the system to allow radical changes without performing regenesis. This means we can make important encryption upgrades without disrupting developers and users.

We have long been working on encryption upgrades. Today, we are happy to announce our first encryption upgrade: zkSync Era is transitioning to a new STARK** based proof system, said for "Boojum". **

1. Introduction to Boojum

Boojum is the name of our Rust-based library of algorithms and constraints that we use to implement zkSync Era and ZK Stack's upgraded version of ZK circuits. The name Boojum was inspired by the poem The Hunting of The Snark by Lewis Carroll, and Boojum represents the most terrifying type of Snark.

**(1) What is Boojum? **

Boojum's design has a number of attractive features:

· PLONK** type algorithm: **For zero-knowledge protocols, algorithm (arithmetization) is the process of converting general calculations into mathematical forms. As far as the current proof system is concerned, our upgraded system continues to use the PLONK type algorithm. Using this approach, ZK circuits are easier to write than some other alternatives, and the system is easier to develop, audit, maintain, and upgrade.

· **Powerful Commitment Scheme: **The core of Boojum is the FRI commitment scheme. The FRI commitment is a key component, which allows us to make a commitment to a bounded polynomial, and then efficiently prove that the (polynomial) claimed opening is indeed Belongs to low-order polynomials.

**Efficiency of the "boring" part of the system: **Although witness generation is sometimes ignored when people talk about prover performance, in the current version of the proof system, optimized The GPU prover is very efficient, and the witness generation time is comparable to the proof generation time. With Boojum, we provide automated parallel (if the dependency graph allows) witness generation, while still making it easy to define witness generation functions like |(a, b)| a + b.

· Easy to extend: The basic constraint system abstraction is very shallow, but it allows users to add their custom gate constraint types in various ways, such as adding some specialized polynomials, or reusing common columns. After users define a simple geometry for their circuit, the extension interface provides them with the ability to automatically generate provers, verifiers, and recursive verifiers. This will allow for a very efficient development process; if the user changes the circuit structure and chooses to use a different type of gate, they can call the interface again and it will regenerate the keys and ensure they are using the correct prover and verifier programs.

· Single-stack: With Boojum, all of the above can be expressed in just standard, idiomatic Rust, and use the expressiveness of its type system. The computationally heavy parts of the GPU prover are written in CUDA C++, but we provide Rust bindings for the composition.

By default, Boojum operates on a prime number field of size 2^64 - 2^32 + 1 (called "Goldilocks field", originally proposed by Mike Hamburg, using specific parameters suggested by Hamish Ivey-Law), and provides the corresponding field binding primitive implementations of cryptographic primitives such as the Poseidon2 hash function, and implementations of more standard cryptographic primitives based on lookup tables such as SHA256, Keccak256, and Blake2s.

Importantly, in the final step of our deployment, we will use an opaque pairing-based SNARK—essentially a slightly upgraded version of the current proof system—to wrap the STARK proof, and this SNARK will be available on Ethereum. authenticating. Such proofs are much smaller and much cheaper to verify; this step reduces the cost of the proof system and thus the transaction itself.

Boojum has benefited from the contributions of many people in the community, and we are grateful for the variety of ideas we receive. We draw inspiration from the underlying documents of STARK, FRI, and DEEP-FRI, the advancement of hash functions proposed in Poseidon and Poseidon2, and the development of the PLONK algorithm proposed by Gabizon, Williamson, and Ciobotaru. Also, the innovative approach of the Plonky2 project (Farmer, Lubarov, Borgeaud, etc.) - including the choice of Poseidon MDS and the use of round constants, and the novel insights of cached quotients and multivariate lookup research by Eagen, Fiore, Gabizon, and Haböck. It is these valuable contributions that together shape the design of Boojum.

**2. Why choose Boojum? **

When designing Boojum, our decision considered two key factors: (1) world-class proof performance, and (2) reduced hardware requirements for decentralization.

(1) World-Class Performance

Our current SNARK-based system, while currently functioning effectively, cannot scale to the high-volume, near-real-time transactions that the ZK Stack plans to support over the next few years. We envision a future for these systems in which proofs can be generated and verified cheaply and quickly, enabling fast finality and interoperability between hyperchains.

The performance of the proof system directly affects the price users pay for their transactions, and these costs need to approach zero over time. The current version of the proof system is powerful enough to build a zkEVM and process millions of transactions in just a few months, but with Boojum we can do even better!

To measure the proof generation time of the network (and other key metrics related to performance), we partnered with Celer, a team with extensive experience in benchmarking and analyzing multi-proof systems. You can see from the graph below that Boojum significantly outperforms most systems. The results speak for themselves: **Our deployment demonstrates world-class proof performance, which is, to our knowledge, the fastest proof system in use. **

For a like-for-like comparison, Celer performed these benchmarks against a CPU-based prover, but our mainnet system uses a faster GPU-based prover.

The shift to a STARK-based proof system will bring significant performance improvements and will help ensure low-latency end results and support increased activity on zkSync Era and other ZK Stack-based systems.

(2) Reduce hardware requirements for decentralization

These performance results are especially impressive given that this wasn't the only metric we were optimizing for - we wanted to improve system performance while reducing the hardware requirements for the system to run on.

Today's popular proof systems, including our current proof system, are obviously very demanding on hardware. Our current verification system runs on a cluster of A100 GPUs with 80 GB RAM each. This need for expensive, powerful machines poses a significant obstacle to our goal of enabling a future of user-driven, decentralized proof generation. To achieve this goal, it is not enough to make proof generation permissionless; users should also not need expensive machines and hundreds of gigabytes of RAM.

This is yet another area where we have made great progress! The GPU prover we use in Boojum only requires 16GB RAM, such a low threshold is an important step towards our future vision. CPU-based validation is also possible with as little as 64 GB of RAM (we hope it can be as low as 32 GB), and can take maximum advantage of modern multi-core processors. After we have fully migrated to the new proof system, we will release more information about its decentralization plans.

Finally, the Rust-based zkSync Era sequencer is already capable of processing over 100 transactions per second (TPS). The introduction of the new proof system not only improves performance, but also reduces hardware requirements, making it an ideal booster for sorters. Boojum's increased performance also means the system can prove transactions faster, and the reduction in hardware requirements gives the network access to lower-cost machines, increasing horizontal scalability.

3**, Boojum’s Road to Mainnet**

The team has been working on this upgrade for months and we are excited to finally bring the system to mainnet. We also wanted to share some stories so far.

(1) Upgrade zkSync Era

First, let's briefly describe how we perform such an upgrade. First, the design of zkSync Era allows us to upgrade each component over time, and the proof system is no exception.

Similar to Ethereum, we use a Merkle tree data structure to store information about the state of the network. This information is needed to prove the system because we are proving a statement about the state of the system. A key design decision of this Merkle tree (and the way the proof system interacts with it) is the use of non-algebraic hash functions, specifically Blake2s. If we were optimizing purely for ease of proof generation, we would use an algebraic hash function (e.g. Poseidon2), but this choice would couple observable state to proof system parameters - such as the choice of prime field. Any upgrade to the proof system would require a full regenesis of the state, which would be a hugely disruptive experience for zkSync Era users. All we need to do to upgrade our proof system is redeploy Blake2s within the circuit.

(2) Boojum: From Design to Review

About a month ago, we began to focus our efforts on the implementation of a complete end-to-end version of the new proof system. Given the complexity of this update and the importance of system correctness, we began a series of internal and external audits .

The zkEVM circuit and the Boojum algorithm library were still under active development at the time, but we worked with external security auditors who focused on the early identification of potential issues related to the reliability of the main circuit and Boojum components. We worked closely together to provide them with full access to the source code and documentation as they reviewed and tested the zkEVM circuit and Boojum related tools (using both automated and manual methods). Through this partnership, we were able to address many early issues.

(3) Boojum: From Review to Test

Now, we have entered the next step of our plan: Mainnet Shadow Mode! We are excited to now be able to run the new proof system alongside the existing proof system, even though Boojum is only in beta. We are already generating and validating “shadow proofs” of mainnet blocks.

The mainnet version of zkSync Era does not require shadow proofs - it will continue to be powered by the existing proof system. We are only validating these shadow proofs to further test and optimize the system, but using real production data from zkSync Era user activity.

We are also excited to be doing this test publicly, over the next few weeks you will see links to some information about these shadow proofs in the block explorer next to the existing proof information, we are open sourcing a CLI tool that anyone can use to verify new proofs.

We are now particularly focused on testing the new proof system, and do not plan to verify shadow proofs on Ethereum yet. During the testing phase, the verification of shadow proofs will be done off-chain, we look for edge cases and bugs, and continue to review the implementation further.

We are also open sourcing the Boojum codebase today. Please note: the codebase is still a work in progress! As testing progresses, you'll likely also see numerous tweaks, optimizations, fixes, and documentation improvements. We're also opening up several more interesting repositories in the coming weeks, including updated circuits and a GPU prover.

(4) Boojum: From testing to migration

Safety is a top priority in everything we do. We will only consider migrating when we are fully satisfied with our testing of the new system, and we will share more details in the coming weeks and months. We also plan to conduct further audits and security reviews, and this exciting upgrade is about to be fully implemented while the current attestation system is deprecated.

We believe that Boojum, coupled with our commitment to innovation and user-first design, is the next step towards a safer, more scalable, and more efficient zkEVM.