❗️TL;DR

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

• Performance: Boojum demonstrates world-class proving performance, complementing the zkSync Era sequencer which can already process over 100 TPS.

• Decentralization: Boojum provers only require 16 GB of RAM, enabling massive future prover decentralization.

• Readiness: Shadow proving has already been live on Mainnet!

The mission of zkSync is to advance personal freedom for all — making digital self-ownership universally accessible by building a blockchain network that is trustless, secure, permissionless, affordable, easy to use, resilient and limitlessly scalable, as we articulated in the ZK Credo.

In line with this mission, the Alpha version of zkSync Era was open to the public a little over three months ago, and the reception has been nothing short of amazing. During that period we’ve seen significant activity on the network.

Network highlights:

• $577M Total Value Locked (source: L2Beat)

• 23,750,000 transactions over the past 30 days — most of any L2 (source: L2Beat)

• 9,735 source-code-verified smart contracts

In March 2023, we launched zkSync Era with a SNARK-based system underpinning our zkEVM, leveraging the battle-tested circuit framework that has been powering zkSync Lite on Mainnet for almost three years. However, we knew this wasn’t going to be the final word when it came to zkSync Era’s proof system, and designed the system in such a way that we can make radical changes to it without having to perform a regenesis. This means we can deploy major cryptographic upgrades without disrupting developers and users.

Behind the scenes, we’ve been working on a cryptographic upgrade for a long time, and our paper on a system called RedShift fully describes the approach. Today, we're excited to announce the first cryptographic upgrade: zkSync Era is transitioning to a new STARK-based proof system called ‘Boojum.’

Meet Boojum

Boojum is the name of our Rust-based arithmetization & constraint library, which we use to implement the upgraded version of the ZK circuits for zkSync Era and the ZK Stack. The name Boojum was inspired by Lewis Carroll's poem "The Hunting of the Snark," where the Boojum represents the most feared type of Snark.

What is Boojum?

We designed Boojum to have a number of compelling properties:

• PLONK-style arithmetization: In the context of zero-knowledge protocols, arithmetization is the process that transforms a general computation into mathematical form. As with the current proof system, our upgraded system continues to employ a PLONK-style arithmetization. With this approach, the ZK circuits are simpler to write relative to some alternative formalisms, making the system easier to develop, audit, maintain, and upgrade.

• Powerful commitment scheme: At the heart of Boojum lies the FRI commitment scheme, a key component that enables us to commit to a polynomial of bounded degree, and later efficiently prove that claimed opening (of the polynomial) indeed belongs to the low-degree polynomial.

• Efficiency of “boring” parts of the system: Even though witness generation is sometimes neglected when people talk about prover performance, in the current version of the proof system we have reached the point where the optimized GPU prover is so efficient that the witness generation time is comparable to the proof generation time. With Boojum, we provide automated parallelized (if the dependency graph allows it) witness generation, while keeping it easy to define a witness generation function like |(a, b)| a + b.

• Ease of extension: The base constraint system abstraction is very thin, but it allows users to add their custom gate types in various fashions, e.g. adding a few specialized polynomials for them, or reusing what’s called “general purpose columns”. After a user has defined a simple geometry for their circuit the extension interface provides the ability for them to automatically generate a prover, verifier, and recursive verifier. This allows for a very efficient development process; if the user changes the circuit structure and picks different types of gates to use, they can just call the interface again it will regenerate the keys and ensure that they’re using the correct prover and verifier.

• Single stack: With Boojum, everything listed above can be expressed with only standard, idiomatic Rust, using 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 composition.

Boojum by default operates over the prime field of size 2^64 - 2^32 + 1 (dubbed a “Goldilocks field”, originally presented by Mike Hamburg, and with specific parameters suggested by Hamish Ivey-Law) and provides implementations of the corresponding field-bound primitives like the Poseidon2 hash function, as well as lookup-table based implementations of more standard cryptographic primitives, such as SHA256, Keccak256 and Blake2s.

Importantly, in the final step of our implementation, we will wrap the STARK proofs with a non-transparent pairing-based SNARK — essentially a slightly upgraded version of the current proof system — and it will be this SNARK that is verified on Ethereum. This proof is much smaller and cheaper to verify; this step drives down the cost of the proof system, and therefore the transactions themselves.

Boojum has benefited from the work of a number of different people in the community, and we’d like to extend our thanks for these ideas. We’ve drawn inspiration for this approach from the foundational papers on STARK, FRI, and DEEP-FRI (Ben-Sasson et al.), the advancements in hash functions presented in Poseidon and Poseidon2 (Grassi et al.), and the development of PLONK arithmetization from Gabizon, Williamson, and Ciobotaru. Additionally, the innovative approaches – including the choices for Poseidon MDS and round constants used in Boojum – of the the Plonky2 project (Farmer, Lubarov, Borgeaud et al.) and novel insights presented in the cached quotients and multivariate lookups research from Eagen, Fiore, Gabizon, and Haböck. Together, these invaluable contributions have helped shape Boojum's design. A complete list of references can be found below, and inside Boojum’s code we’ve attempted to give credit where appropriate.

Why Boojum?

When designing Boojum there were two key factors behind our decision-making: (1) world-class proving performance, and (2) reducing hardware requirements for decentralization.

World-class Performance

Our current SNARK-based system, while effective for today, won’t scale to the high-volume, near real-time transactions the ZK Stack, where zkSync Era operates as a Hyperchain, aims to support in the coming years. The future we imagine for these systems is one in which proofs are generated and verified cheaply and quickly, allowing for fast finality and interoperability between Hyperchains.

The performance of the proof system directly contributes to the price a user will pay for their transactions, and over time these costs need to trend toward zero. The current version of the proof system was performant enough for the zkEVM to be built, and process millions of transactions in just a few months, but with Boojum we can do even better!

To measure the proof generation time (and other key metrics related to performance) of the network we partnered with Celer, a team with deep experience in benchmarking and profiling multiple proving systems. In the image below you can see that Boojum significantly outperforms the majority of the systems profiled. The results speak for themselves: our implementation demonstrates world-class proving performance, and to the best of our knowledge this is the fastest proof system used in production.

To allow for an apples-to-apples comparison, Celer performs these benchmarking exercises on CPU-based provers, but our Mainnet system is using our GPU-based provers which are even faster.

You can read more about the results of Celer’s benchmarking, including detailed comparisons of the trade-offs between each framework here.

The move to a STARK-based proof system represents a dramatic improvement in performance, and will help ensure a low latency for finality and support for increased levels of activity on zkSync Era and other ZK Stack based systems.

Reduced Hardware Requirements for Decentralization

These performance results are particularly impressive when one considers that this wasn’t the only metric we were optimizing for — we wanted to increase the system performance while simultaneously reducing the hardware requirements for running it.

Today's prevalent proof systems, including our existing one, are notably hardware-intensive. Our current proof system runs on a cluster of A100 GPUs each with 80 GBs of RAM. This demand for expensive, powerful machines poses a significant barrier to our goal: a future of user-powered, decentralized proof generation. To achieve this goal, it isn’t enough to make proof generation permissionless; users should also NOT need an expensive machine with hundreds of GBs of RAM to participate.

This is another area in which we’ve made extremely compelling progress! The GPU provers we’re using for Boojum require just 16 GB of RAM, and this low barrier to entry is a significant step toward the future we envision. CPU-based proving is also possible with as low as 64 GB of RAM, which we hope to get as low as 32 GBs, and utilizes modern multicore processors to their limit. After we complete the migration to the new proof system, we will publish more information about our plans for its decentralization.

Lastly, the zkSync Era Rust-based sequencer can already process over 100 transactions per second (TPS). The introduction of the new proof system not only enhances performance but also reduces hardware requirements, making it an ideal complement to the sequencer. The increased performance from Boojum also means the system can prove transactions faster, and the reduced hardware requirements improve the network’s access to cheaper machines for increased horizontal scalability.

Boojum’s Journey to Mainnet

The team has been working on the development of this upgrade for months now, and we are excited to be at the point where we are now putting the system through its paces on Mainnet. We also want to share a little bit of the story so far.

Upgrading zkSync Era

First, a quick aside on how we can even perform an upgrade like this. To begin with, zkSync Era was designed in such a way that we are able to upgrade every component over time, and the proof system is no exception.

Similar to Ethereum, we use Merkle tree data structures to be able to store information about the state of the network. This information is required by the proof system, given that we’re proving statements about the state of the system. A key design decision made for this Merkle tree (and how the proof system interacts with it) was to use a non-algebraic hash function, specifically Blake2s. If we’d been optimizing purely for ease of proof generation, we’d have used an algebraic hash function (e.g. Poseidon2), but this choice would have coupled the observable state to the proof system parameters — such as the choice of prime field. Any upgrade to the proof system would have then required a full regenesis of the state, which would have been a massively disruptive experience for users of zkSync Era. All that is required for us to upgrade our proof system is for us to reimplement Blake2s in-circuit.

Boojum: From Design to Review

Around a month ago we started to converge on a complete end-to-end version of the implementation of our new proof system and, given the complexity of this change and how critical the correctness of the system is, we began to conduct a series of internal and external audits.

The zkEVM circuits and Boojum arithmetization library were still being actively developed at the time, but we partnered with external security auditors who focused on early identification of potential issues related to soundness for our primary circuits and Boojum components. We worked closely together, providing them with full access to source code and documentation as they reviewed and tested the zkEVM circuits and Boojum gadgets, using both automated and manual testing.

We were able to address a lot of early findings through this partnership, and we’ll be sharing a lot more details about this process in the next blog post.

Boojum: From Review to Testing

This brings us to today, and the next step in our phased rollout: mainnet shadow mode! We are excited to now be running the new proof system alongside our existing one, albeit with Boojum purely in a testing phase. We are already generating and verifying “shadow proofs” for Mainnet blocks.

The shadow proofs aren’t required for the mainnet version of zkSync Era – this will continue to be powered by the existing proof system. We are just verifying these shadow proofs to further test and optimize the system, but with real production data from zkSync Era’s user activity.

We are also glad to be doing this testing out in the open, and in the coming weeks, you’ll see a link to some information about these shadow proofs alongside the existing proof information inside the block explorer, and we are open sourcing a CLI tool that anyone can use to verify any of the new proofs.

We’re really focused on testing the new proof system right now, and don’t plan to verify the shadow proofs on Ethereum just yet. During the testing phase this will be done off-chain as we look for edge cases and bugs, and continue to further review the implementation.

We’re also open sourcing the Boojum codebase today. You can find a link to the Boojum repo here. Fair warning: the codebase is still a work in progress! You’ll likely see lots of tweaks, optimizations, fixes, and documentation improvements as we get further through our testing. We'll be also opening a few more interesting repos in the coming weeks, including the updated circuits and GPU prover.

Boojum: From Testing to Prime Time

As with everything we do - security comes first. Only when we are completely satisfied with the testing of the new system we will consider migration, and we’ll share more details about this in the coming weeks and months. We have further audits and security reviews planned too, as we get this exciting upgrade closer to being fully deployed and the current proof system deprecated.

We are confident that Boojum, coupled with our commitment to innovation and user-first design, is the next step forward for a more secure, scalable, and efficient zkEVM. Of course, this work will also be available for anyone building with the ZK Stack!

Stay tuned for more details.

References

Hamburg, M. (2015). Ed448-Goldilocks, a new elliptic curve. Cryptology ePrint Archive, Paper 2015/625.

Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2017). Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In International Colloquium on Automata, Languages, and Programming, ICALP.

Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Paper 2018/046.

Ben-Sasson, E., Goldberg, L., Kopparty, S., & Saraf, S. (2019). DEEP-FRI: Sampling Outside the Box Improves Soundness. Cryptology ePrint Archive, Paper 2019/336.

Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019) Plonk: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Report 2019/953.

Grassi, L., Kales, D., Khovratovich, D., Roy, A., & Rechberger, C. (2019). POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems. Cryptology ePrint Archive, Paper 2019/458.

Eagen, L., Fiore, D., & Gabizon, A. (2022) cq: Cached quotients for fast lookups. Cryptology ePrint Archive, Report 2022/1763.

Haböck, U. (2022) Multivariate lookups based on logarithmic derivatives. Cryptology ePrint Archive, Paper 2022/1530.

Kattis, Assimakis A., Konstantin Panarin, and Alexander Vlasov. ‘RedShift: Transparent SNARKs from List Polynomial Commitments’. (2022) In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security

Grassi, L., Khovratovich, D., & Schofnegger, M. (2023). Poseidon2: A Faster Version of the Poseidon Hash Function. Cryptology ePrint Archive, Paper 2023/323.

plonky2. (2023) GitHub. https://github.com/mir-protocol/plonky2