BoojumMatter Labs

Description

Boojum is a proving system operating on EraVM ISAInstruction Set Architecture of a virutal machine describes its computational model, including the available instructions, registers, data types, etc. and supporting zk stack chains. It includes recursive STARKShort for "scalable transparent argument of knowledge", a STARK is a type of zero-knowledge proof that resolves one of the primary weaknesses of ZK-SNARKs, its reliance on a "trusted setup”. STARKs also come with much simpler cryptographic assumptions, avoiding the need for elliptic curves, pairings, and the knowledge-of-exponent assumption and instead relying purely on hashes and information theory. This means that they are secure even against attackers with quantum computers. proving of zkVMA special type of zk proving system that proves the correctness of state transitions of a virtual machine. Computation is represented by a program in a specific instruction language, it can have private and public inputs and public outputs. Most of zkVMs are STARKs. execution, as well as the final wrap with Plonk or Fflonk SNARKShort for "succinct non-interactive argument of knowledge", a SNARK is a widely used type of zero-knowledge proof that is short and fast to verify. Different kinds of SNARKs are usually systematized by proof size, verification time, and type of setup. The most famous SNARKs are Groth16, PLONK/Marlin, Bulletproofs, and STARKs. proving system. Boojum targets 100 bits of security.

Proof systemThe infrastructure that allows projects to verify their state transitions. It is composed by onchain verifiers and offchain provers. The main two flavors are optimistic and ZK proof systems, but they can be combined in a hybrid model. In general though, if a system is able to accept state roots optimistically, even if it has a ZK component, it is considered an optimistic proof system.

zkVM component

Boojum’s core is an implementation of the Redshift protocol which uses the PlonkA zk-SNARK proving system introduced by Gabizon, Williamson and Ciobotaru in 2019 that allows proving custom circuits. Plonk is based on KZG polynomial commitments and thus requires a universal trusted setup. IOP with a polynomial commitmentA commitment scheme that commits to a polynomial and allows generating the proof of opening the polynomial at a given point against the commitment. scheme based on List Polynomial Commitments (LPCs), which is in turn based on FRIA proximity test method that is used to determine whether a set of points is mostly on a polynomial with a degree less than a specified value. It resembles the FFT but the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic., making the scheme transparent. The scheme makes use of the Goldilocks field, which is much smaller than BN254’s field. This part of boojum implements a zkVM for EraVM, which is closely aligned with EVM but has essential differences like 16 registers.

Recursion circuits

The protocol makes use of several layers of recursive proof aggregation for 15 types of circuits. In particular, nodeA software client that participates in the network. and scheduler circuits aggregate zk proofs and compressor and wrapper circuits reduce the final proof size. Further information about the aggregation architecture can be found here.

Final wrap

The final proof could either be wrapped into a Plonk+KZGA polynomial commitment scheme that allows a prover to compute a commitment to a polynomial, with the properties that this commitment can later be opened at any position: the prover shows that the value of the polynomial at a certain position is equal to a claimed value. KZG is widely used as it’s applicable both for univariate and k-variate polynomials, is efficient for batch proofs, and is able to generate many proofs at once relatively fast. It is also proof generation time efficient: the time for prover to commit to a polynomial is linear on the degree of the polynomial. proof, or into Fflonk+KZG for cheap verification. The KZG commitment is done over BN254 curve and it uses Aztec Ignition trusted setupGeneration of a piece of data that must then be used for some cryptographic protocol to run. Generating this data requires some secret information. The "trust" comes from the fact the secret must be destroyed after the ceremony, otherwise cryptographic properties of the protocol could be broken. Once the data is generated, and the secrets are forgotten, no further participation from the creators of the ceremony is required. There are two types of trusted setups for SNARKs: (i) trusted setup per circuit where it is generated from scratch for each circuit, (ii) trusted universal setup per proving system where it can be used for several circuits. ceremony, see below for more details.