In-depth Explanation of Boojum Upgrade Why zkSync Era Chooses the STARK Proof System

Boojum Upgrade Why zkSync Era Chooses STARK Proof System

Author: zkSync; Translator: LianGuaixiaozou

Main points of this article:

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

Performance: Boojum demonstrates world-class proof performance, improving the performance of the zkSync Era sorter, and is capable of handling over 100 TPS.

• What is the next step for Ethereum after The Merge?
• Exploring the StarkNet ecosystem AGLD soaring, whole-chain gaming brewing
• MKR Drives DeFi Recovery Are RWA and Endgame Sustainable Narratives?

Decentralization: The Boojum prover only requires 16 GB RAM, supporting future large-scale prover decentralization.

Ready: Shadow proving is now live on the mainnet!

As stated in our ZK Credo manifesto, zkSync’s mission is to promote personal freedom for everyone by establishing a trustless, secure, permissionless, cost-effective, user-friendly, flexible, and infinitely scalable blockchain network that makes digital self-ownership universally accessible.

To achieve this mission, the alpha version of zkSync Era has been open to the public for over three months and has received amazing feedback. During this time, we have seen a lot of activity on the network.

Highlights of the network:

· Total locked value of $577 million (source: L2Beat).

· Processed 23.75 million transactions in the past 30 days – the highest transaction volume on an L2 (source: L2Beat).

· 9,735 smart contracts verified source code.

In March 2023, we launched zkSync Era, which uses a SNARK-based system to support our zkEVM and has provided support for zkSync Lite on the mainnet for nearly three years using a proven circuit framework. However, we know that this is not the end of the zkSync Era proof system, and we designed it to be capable of fundamental changes without the need for regenesis. This means that we can perform important cryptographic upgrades without disrupting developers and users.

We have long been committed to cryptographic upgrades. Today, we are pleased to announce our first cryptographic upgrade: zkSync Era is transitioning to a new STARK-based proof system called “Boojum”.

1. Introduction to Boojum

Boojum is the name of our Rust-based algorithm and constraint library that we use to implement upgraded versions of the ZK circuits for zkSync Era and ZK Stack. The name Boojum is inspired by Lewis Carroll’s poem “The Hunting of The Snark”, where Boojum represents the most fearsome type of Snark.

(1) What is Boojum?

Boojum has many exciting features in its design:

· PLONK-type algorithm: For zero-knowledge protocols, the algorithm (arithmetization) is the process of converting general computations into mathematical form. For the upgraded system, we continue to use a PLONK-type algorithm. Using this approach, ZK circuits are easier to write compared to other optional solutions, making the system easier to develop, audit, maintain, and upgrade.

· Powerful commitment scheme: The core of Boojum is the FRI commitment scheme, which allows us to commit to a bounded polynomial and then efficiently prove that the claimed opening of the polynomial indeed belongs to a low-degree polynomial.

· Efficiency of the “boring” part in the system: Although the efficiency of the prover is sometimes overlooked when people talk about prover performance, in the current version of the proof system, the optimized GPU prover is very efficient and the witness generation time is comparable to the proof generation time. Through Boojum, we provide automated parallel witness generation (if the dependency graph allows), while still allowing for easy definition of witness generation functions like |(a, b)| a + b.

· Easy to scale: The underlying constraint system abstraction is very shallow, but it allows users to add their custom gate constraint types in various ways, such as adding specialized polynomials or reusing general-purpose columns. Once users define a simple geometry for their circuit, the extension interface allows them to automatically generate provers, verifiers, and recursive verifiers. This enables a very efficient development process; if users change the circuit structure and choose to use different types of gates, they can simply call the interface again, which will regenerate the keys and ensure they use the correct prover and verifier programs.

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

Boojum defaults to operating in the prime field of size 2^64 – 2^32 + 1 (known as the “Goldilocks field,” originally proposed by Mike Hamburg with specific parameters suggested by Hamish Ivey-Law), and provides implementations of corresponding field binding primitives, such as the Poseidon2 hash function, as well as more conventional 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, pair-based SNARK—a micro-upgrade of the current proof system, essentially—to wrap the STARK proof, and this SNARK will be verified on Ethereum. This proof is much smaller and has much lower verification costs; this step reduces the cost of the proof system and thus reduces the cost of the transaction itself.

Boojum benefits from contributions from many people in the community and we are grateful for the various ideas we have received. We have drawn inspiration from the foundational documents of STARK, FRI, and DEEP-FRI, the advancements in hash functions proposed in Poseidon and Poseidon2, and the development of the PLONK algorithm proposed by Gabizon, Williamson, and Ciobotaru. Additionally, we have been shaped by the innovative approaches of the Plonky2 project (Farmer, Lubarov, Borgeaud, etc.), including the choice of Poseidon MDS and the use of round constants, as well as the novel insights presented by Eagen, Fiore, Gabizon, and Haböck in cached quotients and multivariate lookup research. It is these valuable contributions that have collectively shaped the design of Boojum.

2. Why choose Boojum?

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

(1) World-class performance

Although our current SNARK-based system is running effectively, it cannot scale to the large capacity and near real-time transactions that the ZK Stack plans to support in the coming years. We envision the future of these systems to be one where proofs can be generated and verified at low cost and high speed, enabling fast finality and interoperability between chains.

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

In order to measure the proof generation time of the network (as well as other key performance-related metrics), we have partnered with Celer, a team with rich experience in benchmarking and analyzing multi-proof systems. As you can see from the chart below, Boojum’s performance is significantly better than most systems. The results speak for themselves: our deployment demonstrates world-class proof performance, and to our knowledge, it is the fastest proof system deployed for applications.

For comparative purposes, Celer conducted these benchmarks on a CPU-based prover, but our mainnet system uses a faster GPU-based prover.

Transitioning to a STARK-based proof system will bring significant performance improvements and help ensure low-latency finality, supporting increased activity on zkSync Era and other ZK Stack-based systems.

(2) Reducing the decentralized hardware requirements

Given that this is not our only optimization target, these performance results are particularly impressive – we want to reduce the hardware requirements of running the system while improving its performance.

Popular proof systems today, including our existing proof system, clearly have high hardware requirements. Our current verification system runs on an A100 GPU cluster, with each GPU having 80 GB of RAM. This demand for expensive and powerful machines poses a significant barrier to our goal of achieving a user-driven, decentralized proof generation future. To achieve this goal, it is not enough to make proof generation permissionless; users should also be able to do so without expensive machines and hundreds of GBs of RAM.

This is another area where we have made significant progress! The GPU prover used in Boojum only requires 16GB of RAM, which is an important step towards our future vision. CPU-based verification is also possible with as low as 64 GB of RAM (we hope to lower it to 32 GB) and can make maximum use of modern multi-core processors. Once we fully transition to the new proof system, we will release more information about its decentralized plans.

Lastly, the zkSync Era sorter based on Rust can process 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 boost for the sorter. The improved performance of Boojum also means that transactions can be proven faster, and the reduced hardware requirements allow the network to access lower-cost machines, thereby improving horizontal scalability.

3. The Road to Boojum Mainnet

The team has been working continuously for several months to upgrade the system, and we are excited to finally bring it to the mainnet. We also want to share some stories from the journey so far.

(1) Upgrading zkSync Era

First, let’s briefly introduce how we executed this upgrade. 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 the Merkle tree data structure to store information about the network state. This information is necessary for the proof system as we are proving statements about the system’s state. One key design decision of this Merkle tree (and how it interacts with the proof system) is the use of non-algebraic hash functions, specifically Blake2s. If we were optimizing purely for proof generation simplicity, we would use algebraic hash functions like Poseidon2. However, this choice would couple the observable state with the proof system parameters, such as the choice of prime fields. Any upgrade to the proof system would require a full regenesis of the state, which would be a disruptive experience for zkSync Era users. All we need to do to upgrade our proof system is to redeploy Blake2s within the circuit.

(2) Boojum: From Design to Audit

About a month ago, we started focusing on the implementation of a complete end-to-end version of the new proof system. Given the complexity and importance of system correctness in this update, we conducted a series of internal and external audits.

The zkEVM circuit and the Boojum algorithm library were still actively under development at that time, but we collaborated with external security auditors who focused on early identification of potential issues related to the reliability of the main circuit and Boojum components. We worked closely with them, providing them with full access to source code and documentation as they audited 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 Audit to Testing

Now, we are moving to the next planned step: Mainnet Shadow Mode! We are excited to be able to run the new proof system alongside the existing proof system now, even though Boojum is still in the testing phase. We have been generating and validating “shadow proofs” for mainnet blocks.

The mainnet version of zkSync Era does not require shadow proofs – it will continue to be supported by the existing proof system. We are simply verifying these shadow proofs to further test and optimize the system using real production data from zkSync Era user activity.

We are also excited to conduct this testing publicly, and in the coming weeks, you will see links to information about these shadow proofs alongside existing proof information in the block explorer. We are open-sourcing a CLI tool that anyone can use to verify the new proofs.

Currently, our focus is on testing the new proof system, and we do not plan to verify shadow proofs on Ethereum. During the testing phase, shadow proof verification will be done off-chain as we look for edge cases and bugs and continue further review of the implementation.

We have now opened the source code of the Boojum codebase. Please note: the codebase is still a work in progress! As testing progresses, you may also see a lot of adjustments, optimizations, fixes, and documentation improvements. We will also be opening several more interesting codebases in the coming weeks, including updated circuits and GPU prover.

(4) Boojum: From Testing to Migration

Security is our top priority in everything we do. We will only consider migration when we are completely satisfied with the 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 as we approach this exciting upgrade, while the current proof system will be deprecated.

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

We will continue to update Blocking; if you have any questions or suggestions, please contact us!