Scroll and its zkEVM: make Ethereum great again!

The race for scalability d’Ethereum goes through solutions known as « of secondary layer  » (layer 2). These infrastructures lighten the load on the main blockchain (layer 1). Among the techniques used, the ZKP (zero-knowledge disclosure proofs) are reputed to be efficient and secure.

We present to you Scrolla brand-new scalability solution based on these famous proofs. It embeds a virtual machine integrating these famous proofs, offering a native compatibility for all existing Ethereum smart contracts. To understand how Scroll works, from its zkRollups and his zkEVMfollow the guide.

Scroll is a project co-founded by 3 entrepreneurs and scientists: Sandy Peng (Cambridge University), Haichen Shen (Tsinghua and Washington universities) and Ye Zhang (Peking and New York universities).

The team endorses original values of Ethereum: an accessible platform, both in terms of user experience and costs. It has therefore chosen to work on improving its scalability through these famous secondary layers (L2).

There are different ways ofaggregate transactions on a secondary layer. Scroll is based on zkRollups. The development team is convinced that this is the most effective solution to date. It has therefore designed a virtual machine for Ethereum based on these proofs: a zkEVM.

Ethereum for everyone

The ultimate goal of Ethereum’s developers is to make the network accessible to a very large number of people. To achieve this, we need to greatly improve scalability of the system. It is a matter of enabling the main network (L1) to always execute more operationsbut also to offer fresh minimal.

To unleash Ethereum’s potential, the decentralized applications Today’s decentralized applications (dApps) need to be able to operate at optimum cost and speed. L2s meet this objective – especially those based on ZKP, such as StarkNet or Kakarot. But the design of dApps on these L2s still needs to be affordable for developers. This is the aim of zkEVM by Scroll: to enable any Ethereum developer to portabilize its code on the L2 – Scroll.

Open-source development

The Scroll team is particularly committed to the ideals of development and open source. open-source. It is thus attentive to other L2 solutions, and collaborates with other members of the community.

The code from Scroll is public and auditable This is a guarantee of security – anyone can reread it or help improve it.

Decentralization and resistance to censorship

These are two fundamental pillars of Ethereum. The search for a better scalability must not be at the expense of decentralization and the resilience of the network. Since Ethereum’s L1 manages both consensus and data availability, the level of security Scroll is the same.

The resistance to censorship of a zkRollup is more difficult to achieve. It is the subject of active research, in particular using hardware acceleration to enable users to deploy their own proof algorithms.

>> Prefer to keep your cryptos safe? Choose a Ledger wallet (commercial link) <<

Scroll is designed around four technical principles fundamental principles for the project development team: security, EVM equivalence, efficiency and decentralization.

User security

For all users of a second-layer solution, the security of its fonds (and its data personal) is essential. Scroll therefore uses the consensus the base layer ofEthereum to ensure the transaction finalization. Thus, there is no need to trust L2 nodes to ensure the integrity of user funds.

EVM-equivalence

The idea is to offer the same development experience on an L2 as on Ethereum. To enable programmers to effortlessly migrate their decentralized applications from L1 to L2, Scroll is committed to maintaining an EVM-equivalent development environment.

EVM-compatible L2 approaches based on the transpilation pose security challenges. With its full EVM equivalence, Scroll eliminates the need for developers to modify and audit their code.

Transpilation: compile code from one language to another source-to-source.

Efficiency

The effectiveness of an L2 can be evaluated in terms of flow and transaction costs :

• The expenses must be considerably reduced compared to L1 ;
• The preconfirmation of L2 transactions must be quasi-immediateand their finalized on L1 reasonably fast.

The challenge is therefore to obtain good metrics for these two variables, without sacrificing the security of the system. Although it is much easier to achieve an efficient L2 by operating in a centralizedThis is not ideal in terms of security. Scroll therefore aims to offer a fully decentralized environmentin order to benefit from the most high degree of safety possible, that of the Ethereum consensus.

Decentralization

The Scroll team considers decentralization protocol as a essential property. Indeed, a decentralized system will be robust and resistant to attack (especially coordinated attacks and censorship).

So it’s at every level that the developers want to decentralize Scroll:

• Node operators;
• Provers ;
• Community (users and developers).

This goal of decentralization is one of the reasons for Scroll’s open source development.

The above-mentioned technical principles have many implications for the design by Scroll.

zkRollups and zkEVM

Requirements in terms of safety andEVM-equivalence thus lead to the design of an adapted type of zkRollup. The proofs are succinct and are verified on Ethereum’s L1. All transactions carried out on the L2 therefore have the same degree of security. security than L1.

As for EVM equivalence, the ideal was of course to create a zkEVMwhich is part of the technical feat. Fortunately, recent advances by researchers in the field of zero-disclosure proofs of knowledge offer this possibility.

The proof network

It is with the objective of decentralization Scroll, but also to obtain a short time to finalize transactions, came up with the idea of creating a prover network dedicated. This decentralized and permission-free is used to generate proofs of validity for zkRollups.

This infrastructure is scalable Proof nodes can be simply added to improve proof computation capacity. Similarly, the operations performed by these nodes are highly parallelizable.

Scroll’s team will first provide GPU provers in open-source, but relies on its community to create better hardware solutions (based on FPGA and ASICfor example).

With time and competition in the field, the latency and the cost of generating proofs should be greatly reduced. The Scroll team also intends to decentralize the Sequencerto further improve the robustness and resistance to censorship protocol.

Research and innovation

Thanks to its development open-source and transparent, the Scroll team was able to benefit from the latest innovations in the field of ZKP, such as :

• Improving proof systems;
• New methods for aggregating proofs;
• Hardware acceleration for ZKPs.

Scroll works with PSE (Privacy and Scaling Explorations), the Ethereum Foundation. This open mode of research and development should enable us to find the best solutions in the field. Scroll is currently exploring several areas for improvement:

• Post-danksharding data blobs;
• Optimizing zkEVM, with new hardware-friendly ZK algorithms;
• The way ZK primitives are presented to application developers on Layer 2.

Scroll is therefore perfectly aligned with technical principles but also philosophical of the Ethereum community. The scalability of the « universal computer » will depend on secondary layer solutions.

>> Security is the basis! To keep your cryptos close to you, trust Ledger (commercial link) <<

The Ethereum virtual machine or EVM is theexecution environment of the network, enabling smart contracts to be deployed. Its main programming language is Solidity. Once the contract code has been compiled (translated into bytecode), the EVM interprets it, so each operation has a cost in gas.

The secondary layers or L2 are used to improve Ethereum’s throughput and lower its user fees. There are several schools of thought: sidechainschains Plasma or rollups. Each one offers a compromise in terms of efficiency, scalability, decentralization and security.

A rollup represents the new state of the blockchain after a set of transactions has taken place on the L2 (a batch). This state is therefore made up of balances user accounts and code of the relevant smart conctracts on the L2. More specifically, the smart contract on L1 maintains a state root the root of the rollup’s Merkle tree. This enables aggregate transactions on the L2and to carry out state transitions on the L1.

Scroll uses a particular type of rollup, based on ZKPs, hence its name: zkRollup. ZKP, for zero-knowledge proofsare evidence that attest to the validity of all transactions sent from L2 to L1.

What is a zkRollup?

Visit zkRollups are considered to be the most relevant L2 solution in terms of safety and completion date. The generated proof is succinctThis means that L1 can verify it quickly and easily. This makes it possible to aggregate a large number of transactions from the L2. There is no need to re-execute these transactions to update the state of the blockchain: this is what keeps costs to a minimum.

However, zkRollups do have disadvantages :

• They must be coded in a specific language (R1CS), with its heavy syntax requiring a certain expertise;
• They are not composablei.e. it is not possible for different decentralized applications to interact with each other on an L2 of this type.

Scroll’s objective is to provide the best user experience to develop with zkRollups on Ethereum. The idea is to make proof checking native within the EVM: L1 dApps can then be ported as is, using zkRollups. This means creating an EVM that can integrate ZKP operations.

What is a zkEVM?

A zkEVM is a virtual machine for Ethereum integrating computations related to zero-knowledge disclosure proofs (ZKP).

zkRollups are inexpensive and secured. They can, however, present problems of compatibility. The Scroll team has therefore created a zkEVM to make dApps compatible with their secondary layer solution.

There are two ways of using Scroll: firstly, theASIC (Application-Specific Circuit). Contracts are coded in such a way that specific for each application using the R1CS. This code is called low level the basic circuit rollup. However, there are problems of composability and poor developer experience.

Conversely, the whole point of the zkEVM is to benefit from the same experience of development as on the primary layer of Ethereum. All EVM languages are accepted, starting with Solidity.

Such a virtual machine runs on a CPU, so all you have to do is program a universal CPU circuit to check low-level operations. Once this universal circuit has been created, we can verify execution of any type of program. However, this approach has been rejected in the past: the smallest operand in the basic circuit generates a multitude of steps within the EVM.

A arithmetic circuit is the standard model for performing complex operations on data in computer calculations. polynomials. In cryptography, and particularly in the field of ZKP, polynomials are ubiquitous. We’ll come back to this later!

However, encoding the smart contract in a language verifiable by the EVM is an approach costly. Each operation requires high costs on the L1 side.

Scroll bases the compromise solution on a zkEVMoffering a very simple development experience, while optimizing execution costs via its specific EVM circuit.

Create a zkEVM native for the time being feat. Technically, many challenges had to be solved, both in terms of design and pure mathematics.

Elliptic curves

EVM does not support elliptic curve graphs (cyclic elliptic curves), which are necessary for ZKPs. This makes it difficult to create recursive proofs or specialized ZK protocols. The verification is adjusted to be EVM-compatible.

EVM word size

It is currently 256 bits. The ZKP use arithmetic operations in the prime fields. This incompatibility considerably encumbers the circuit size in the EVM, by about orders of magnitude. We speak of mismatched field arithmetic.

EVM special opcodes

The operative codes EVM’s original operating codes require new design models. When designing the ZK circuit, you need to take into account, for example, the gas and call functions.

The EVM is a stack machine

The EVM does not use a register to store its data, but a stack. It always executes the first operands of the stack. This is not the case with SyncVM from zkSync or the architecture of StarkNetwhich work with a registry.

Ethereum’s storage layer

The EVM storage layer is based on Keccak and the MPT (Merkle Patricia Tries). These specifications are not suitable for ZKP and cause costs to soar.

So we have to find solutions to these many problems. Fortunately, the research in the field of ZKP is prolific, and new techniques are appearing, greatly reducing the cost of generating proofs.

Scroll gathers different mathematical tools to optimize the creation of proofs.

Polynomial pledging

Behind this barbaric name lies a new cryptographic techniquewhich allows good flexibility in building ZKPs. This is an improvement over R1CS. Indeed, the low-level language leaves little room for optimization, as constraints must be of degree 2 (due to elliptic curve pairings). Polynomial commitment schemes make it possible to raise the degree of constraints.

In mathematics, a constraint is a condition that must be satisfied by the solution of an optimization problem.

An efficient search table

The use of a search table (lookup table), designed in Arya and optimized in Plookup, delivers substantial savings. Its arguments feature a pleasantly flexible syntax, thanks to TurboPlonk and UltraPlonk. This greatly reduces EVM circuit overheads.

Affordable recursive proofs

Composing recursive proofs was once very expensive. Once again, this is due to operations on elliptic curves. A new technique, Halo, is now available to amortize costs. As for evidence aggregationAztec improves circuit scalability.

GPU verification of proofs

Scroll’s team designed the fastest proving algorithm for GPU and ASIC/FPGA. To give an order of magnitude, it is at least 5 times faster than Filecoin. L’hardware acceleration makes ZK proof generation much faster.

The main idea is as follows to optimize architecture to reduce the size of the arithmetic circuit. This specific architecture reduces proof production costs.

In practice, the zkEVM from Scroll allows any developer to compile and deploy their code, written in an EVM languagelike Solidity. The corresponding bytecode is then deployed on L2. The user experience will be the same as on L1, with one difference: fees are considerably reduced, as is the transaction pre-confirmation time.

Flow within the zkEVM

Within the L2the execution of a set of transactions requires the proof of validity of the corresponding zkRollup circuit. In return, the L1 (Ethereum) re-executes transactions to check their validity and update the state of the chain.

On the L1on bytecode smart contracts is stored on the corresponding Ethereum layer, and transactions are broadcast peer-to-peer. Each node must therefore execute the bytecode before updating the EVM.

On the L2the bytecode is also stored on the dedicated L1 layer. The transactions are distributed off-channel to a zkEVM node. The zkEVM does not execute the code: it generates a proof stipulating that the state resulting from the transactions is valid. It is at the L1 level that the contract verifier updates the state of the blockchain, if the proof is correct, without rerunning the transactions.

At theEVM from L1 (native execution), the bytecode is loaded onto the stack, then all the opcodes are executed one by one. Each opcode follows these three steps:

• Read elements of the stack, memory or storage area ;
• Execution calculations ;
• Writing results in stack, memory or storage area.

zkEVM proofs must therefore ensure that the execution process meets the following conditions:

• The bytecode is correctly loaded from the persistent storage layer;
• Opcodes are executed one by one, sequentially, without forgetting ;
• Each opcode is executed correctly (it respects the 3 steps mentioned above).

Scroll’s zkEVM is designed around these three fundamental points.

In this chapter, we’ll take a deeper dive into the concepts that bring zkEVM to life. They allow us to deal with the three aspects mentioned above one by one.

The cryptographic accumulator

A accumulator is a cryptographic primitive used to justify membership of a set. It is one-way, i.e. it does not reveal the other members of the set.

On Scroll, an accumulator is used to prove that the persistent storage area is being read correctly. In practice, bytecode deployed on the L2 is stored as the leaf of a Merkle tree. The verifier can then ensure that the bytecode is correctly loaded from a given address. In fact, all it has to do is check the corresponding path in the Merkle tree: this is a succinct proof.

Tracing opcode execution

The sequence of operations must be fully verifiable, as the verifier does not know the destination of conditional loops or jumps in the code.

The trace (follow-up) of the execution of the opcodes can be seen as the « unpacked » version of the bytecode. You therefore need to know all the inputs (inputs) relating to the code executed.

In this way, the prover provides all the entries of the circuit, as well as the instruction execution follow-up. This follow-up table is also known as thecontrol« of the circuit.

Prove that opcode execution is correct

We create zkRollup circuits for each opcode in the set. The next step is to prove that reading, writing and operations are correct.

To keep costs down, Scroll uses two optimization techniques. Firstly, two different proofs are used for the read/write and the calculations :

• The elements required for the opcodes are grouped together in a « bus » or « State proof« (state proof). This proof ensures that state, memory and worst-case operations are correct, but does not verify that the read/write operation is performed in the right place.

• The second proof, or « EVM Proof« This ensures that the calculations performed on the « bus » elements are correct.

This separation makes it possible to generate the proof of calculations without taking into account the entire Ehtereum storage area.

Then, each opcode is fragmentedThis is done in a specific way, using polynomials, according to need. This avoids overloading the EVM circuit at every stage.

This architecture was first formalized by the Ethereum Foundation. The Scroll team is actively developing it, and has implemented several opcodes. All the work can be seen on GitHub.

>> Not your keys not your coins ! Choose Ledger (commercial link) as your hardware wallet of choice <<

Scroll consists of two main components: the zkEVM and Layer 2 infrastructure itself. The network of proof nodes is decentralizedwhile for the time being Sequencer is centralized.

Scroll L2 infrastructure

The infrastructure consists of three main components:

• The Scroll nodeswhich create L2 blocks from user transactions. They also ensure communication with Ethereum’s L1.

• The Roller network which creates validity proofs for zkEVM.

• Smart-contracts Rollup and Bridgewhich ensure data availability for ZK transactions. They also act as verifiers for proofs, and enable users to transfer assets between Ethereum and L2.

Let’s go into the details of each system component.

Scroll Nodes

These nodes allow users and to decentralized applications to interact with Scroll. They consist of 3 modules.

Firstly, the Sequencer This is a JSON-RPC interface that accepts L2 transactions. The Sequencer draws transactions from the mempool at regular intervals (a few seconds) to form blocks. A state root is associated with each block. The sequencer is implemented via Geth.

Secondly, the Coordinator It receives the code execution tracking once a new block is generated. This « cryptographic witness » is then sent to a randomly selected Roller.

Thirdly, the Relay He has access to the contracts deployed on Ethereum and Scroll (Bridge and Rollup). It monitors the Rollup contract and therefore the status of L2 blocks (data availability and proofs). In addition, the Relayer ensures the transmission of transaction messages between Ethereum and Scroll, via the Bridge.

Rollers

Rollers generate proofs of validity for zkRollups: they therefore have the role of proofers. These nodes rely on hardware acceleration (GPU, ASIC, FPGA) to reduce proof creation time and costs.

Validity proof generation

The diagram below summarizes the various stages of the process:

1. The Roller starts by converting the execution tracking coming from the Coordinator and creates the witness circuit.
2. It then generates ZKP proofs for each circuit.
3. In the final step, it aggregates all the proofs for the various circuits in the block into a single proof.

We’ll go into the details of proof generation later in the article.

Rollup and Bridge contracts

These are the two contracts responsible for insuring data availability and communication between the two layersEthereum and Scroll.

The Rollup

This contract receives the state roots and the L2 blocks from the Sequencer.

The state roots are stored on Ethereum, while the L2 block data are calldata. This ensures data availability for these blocks, while taking advantage of Ethereum’s security. The Relayer can always rebuild the blocks.

Once the Rollup contract has verified the proof of validity of a Scroll block, it is considered finalized.

The Bridge

For its part, this contract allows users to exchange messages between L1 and Scroll. In addition, it allows users to bridge their ERC-20 between Ethereum and Scroll, in both directions. Sending messages or ERC-20s from Ethereum involves a transaction sendMessage on the Bridge. The Relayer then indexes the transaction on L1, and sends it to the Sequencer for inclusion in a block on L2. The same system is used in reverse.

The diagram below summarizes the construction of zkRollups and L2 blocks with Scroll. The finalization of L2 blocks on Ethereum’s main layer only occurs after several steps.

Building blocks on Scroll

First of all, the Sequencer will generate a sequence of blocks. Each block i also features a follow-up performance T. The blocks are then sent to the Coordinator. At the same time, the Sequencer will submit the transaction data D to contract Rollup on Ethereum, as well as the resulting state roots.

Next, the Coordinator randomly selects a Roller to generate a proof of validity for each block’s execution tracking. It is possible to generate proofs for different blocks in parallel, which improves system throughput.

After generating the proof P for the block ithe Roller refers her to Coordinator. Every k blocks, the Coordinator will select a new Roller, in order to aggregate k block proofs in one global proof A.

Finally, the Coordinator submits the aggregate evidence A to contract Rollup for finalize L2 blocks (i + 1 to i + k). Proofs are verified using state roots and transaction datawhich are subject to the contract.

Block finalization

The block finalization on Ethereum also involves several stages. Each block passes through three states:

• Precommited The block is not yet finalized on the L2 chain, but users who trust the sequencer can act on it in advance.
• Committed The Rollup contract has received the transaction data for the block. At the moment, there is no proof that the execution is correct.
• Finalized The block is finalized when the proof of validity of the execution of its transactions is verified. on-chain on Ethereum. It is now part of Scroll’s canonical L2 chain.

Proof checking via Ethereum’s L1 therefore confers the same level of security for Scroll’s zkEVM. We’ll now look at how Scroll’s proofs of validity are constructed.

Knowledge non-disclosure proofs (ZKP) are a formidable tool opening up new technological possibilities. They are therefore particularly useful in the field of confidentiality (privacy) and the scalability of blockchains. However, generating ZKPs is no mean feat: it’s slow and costly.

So this is the main argument against ZKPs: in order to prove the correct execution of a program, many more calculations have to be performed than the program itself. The increase in calculation size is several orders of magnitude.

In this chapter, we will decompose proof generation and give an idea of the costs for each stage.

Plonk

There are several proof systems (zk-SNARK) based on Plonk. Proposed in 2019, Plonk is based on permutations in Lagrange bases. Since then, this system has been widely adopted in the ZKP field, and several improvements to Plonk have seen the light of day.

Scroll uses a modified version ofHalo 2the Plonk-based proof system designed by the scientific team at ZCash. Scroll’s implementation incorporates the KZG polynomial commitment scheme, which we’ll describe below.

Polynomials

The polynomials are very useful in cryptography, as they can be used to represent large objectsin a simple and efficient way. In the case of ZKPs, the idea is to represent an n-dimensional vector (of elements belonging to a finite field).

This procedure is called polynomial interpolation :

A polynomial can be represented in two different ways:

• as a tuple of its n coefficients : [p₀​, p₁​, …, p_n−1​] ;
• In the form of the tuple of its ratings distinct : [P(x₀​), P(x₁​), …, P(x_n−1​)] where the values {x₀, x₁, …, x_n-1} form the evaluation area.

The transition from the first representation to the second is called Fourier transformationwhile its inverse is called… the inverse Fourier transformation.

The calculation of these transformations can be performed simply. In the first case, simply calculate the polynomial for each x_i of the evaluation domain. In the second case, Lagrange interpolation is used.

Thus, these transformations can be obtained with O(n²) calculations. However, the polynomials of the zkRollups are of high degree, so it is preferable to find a more efficient method: this is the aim of the fast Fourier transformation.

In algorithms, the notation O() represents the upper limit of the number of iterations of the algorithm, given n elements at entry.

Fast Fourier transformation

This transformation enhancement comes from the fact that ZKPs manipulate polynomials in finite fields (also known as Galois fields). This restricts the coefficients and evaluation points in this spectrum. What’s more, the evaluation domain is also reduced (it becomes a multiplicative subgroup of the finite field).

This additional structure makes the transformation more efficient, thanks to the mathematical symmetries it generates. Thus, we go from O(n²) operations at O(n log n) for the fast Fourier transform and its inverse.

The tracking table

The trace table trace table is a two-dimensional matrix representing the witness as well as other useful data to prove that it is correct. Each cell in the table below is an element belonging to a finite body.

The columns A, B and C represent the « control data« also say »private entries« . Each line is a sequential list of numbers in the Square-Fibonnacci sequence.

The i-th line is therefore the witness for the (i + 2)-th Square-Fibonacci number, since the latter uses the two previous values to calculate it.

The sequence of Square-Fibonacci is a variation of the classic Fibonacci sequence:

– Let f₀ = 0, f1 = 1 ;

– Then for i ≥ 2, let f_i = (f_i-2)²+(f_i-1)² mod q, where q is a (very large) prime integer; the modulo limits the size of each element, so that it can be represented in a fixed number of bits.

The S column is called the Selector This indicates that a particular mathematical relationship links the elements of the line. A « 1 » indicates that the first three elements of the line (a, b and c) must satisfy c = a² + b² mod q. Conversely, a « 0 » indicates that this relationship need not be satisfied. The empty line at the bottom of the table (with only a 0 for column S) is added for ease of calculation.

The column P corresponds to the « public entries« . It contains publicly known inputs to the arithmetic circuit.

Control generation

This process consists of filling in the tracking table. It is therefore necessary to iterate over each cell of the array, and find the appropriate value. The corresponding arithmetic (in finite fields) is heavier than for native types (integers and long integers). Indeed, these elements require around 256 bits to be represented, which is larger than the word size of a CPU. Fragmenting the elements adds a additional computational load to the calculation of mod q values.

In the example given by Scroll through the Square-Fibonacci sequence, the computational load is more or less the same as for the original calculation. However, for more complex operations, the size of the array and the number of arithmetic operations required to fill it increases considerably.

Additional processes

Once the private data have been filled in, the tracking table undergoes further processing. The auxiliary columns, also known asvirtual columnsThese « virtual columns » are used to help check the validity of the table. They depend on certain constraints imposed by the algorithm:

• The wiring constraints (wiring constraints): some cells must have the same value. In the case of the Square-Fibonacci sequence, this means: a_i+1 = b_i and b_i+1 = c_i.
• The search tables of the Plonk model.

Interpretation of the polynomial tracking table

The Z column corresponds to the polynomial accumulator, calculated from the control data. It reduces the computational load for the constraints imposed on the other columns.

This column is therefore an n-dimensional vector of finite elements. It represents the « evaluation form » of the polynomial of degree n – 1: the i-th element of column A corresponds to the value of the polynomial A(wⁱ).

Calculation of KZG commitments

Once the columns have been interpreted as polynomials, we can proceed to pledging. The pledging scheme used is as follows KZG (Kate-Zaverucha-Goldberg Polynomial Commitment Scheme).

First of all, this makes it possible to compressr each column into a shorter representation: the size of the table is therefore greatly reduced.

In addition, the use of a polynomial commitment scheme makes it possible to generate evaluation proofs. They are used to prove that a polynomial passes through a particular point without having to reveal the point.

Without going into the mathematical details of calculating KZG commitments (see the « Resources and bibliography » section for further explanations), here are a few remarks:

• The diagram requires a trusted setup (a secret number) ;
• We use the polynomials in Lagrange basis to simplify the calculation of KZG commitments from the evaluation form of polynomials.

The calculations require multiplying a vector of scalars by a vector of group elements. This is called « multiscalar multiplication« .

This is a complex operation (group arithmetic). Thus, this second phase of proof generation is more computationally intensive than filling in the tracking table. A simple addition within a group of elliptic curves requires a large number of arithmetic operations in finite fields.

Costs of the KZG phase A multiscalar multiplication of size n for each column of length n.

Prove that the tracking table is correct

Once the tracking table has been filled in, and each column pledged via the KZG scheme, the third phase begins: the verification.

In order to be valid, the original tracking table must respect a combination of constraints. In Scroll’s example, there are 3 constraints:

• Square-Fibonacci relationship
• The wiring constraints
• Constraints due to public entries: the first row must begin with the first two Square-Fibonacci numbers, while the cells corresponding to the nth Square-Fibonacci number must match the advanced result (entered in the third row of column P, the public entries).

All these constraints are expressed as relations between the polynomials in the table. The individual constraints can then be linearly combined to form a single polynomial constraint (meta-constraint). This is because the individual polynomial constraints must all be equal to zero in the evaluation domain.

However, rather than evaluating each polynomial for all points in the domain, Scroll employs a better technique.

The quotient polynomial

This involves deriving the proposition that the polynomial constraint is valid for every row in the tracking table. This is equivalent to proving that there exists a quotient polynomial respecting the following property:

There exists a quotient polynomial Q(x) such that ϕ(x)=Q(x)⋅(x_n-1) where ϕ(x) is the meta-stress.

The calculation of the quotient polynomial is the most costly:

• Each one-column polynomial must be converted from its evaluation form to its coefficient form: O (n log n) using the Fast Fourier Transform.
• Each polynomial then requires 2n evaluations: 0 (2n log 2n) = 0 (n log n)
• Then, using the 2n valuations, calculate the 2n valuations of the quotient polynomial (simple arithmetic).

The pledging the quotient polynomial is pledged in the same way as the column polynomials. However, the degree of the quotient polynomial is much higher. This would imply the use of a specific Lagrange basis, and therefore a trusted setup different (it must be larger than the degree of the quotient polynomial).

Scroll bypasses these calculations, transforming the quotient polynomial into two polynomials of degree less than n. It can thus be engaged using multi-scalar multiplication of size n. This operation therefore requires :

• An inverse fast Fourier transform of size 2n ;
• 2 multiscalar multiplications of size n.

Proving the existence of the quotient polynomial

For prove the existence of the quotient polynomialthe verifier has the following elements:

• KZG commitments for each column and for the quotient polynomial ;
• Evaluation proofs for each column and for the quotient polynomial at point α.

There are therefore two conditions to check:

• The validity of each evaluation evidence ;
• The correct value for quotient polynomial at the point of evaluation α.

Each evaluation proof requires a elliptic curve matchingwhile verification of the quotient polynomial requires arithmetic in finite fields. All in all, the calculations required for verification proofs are much more light than those necessary for their generation.

Improve Scroll speed

There are several areas for improvement speed up proof generation.

Hardware acceleration

The complex operations such as multiscalar multiplication or fast Fourier transform, account for a significant proportion of the calculations. CPUs are not very fast when it comes to executing the associated algorithms. The idea is therefore to use GPU, ASIC or FPGA The search for suitable algorithms is on.

Reducing the number of columns in a table

This involves finding new calculation techniques, so as to lighten the tracking table. This is also an area of research that can greatly improve system efficiency.

Parallelization

Some of the tasks required to generate proofs are parallelizablesuch as polynomial column commitment schemes. In addition, the commitment scheme (based on multiscalar multiplication) for each control column can be computed at the same time as its generation. This substantially increases the overall speed of the validity proof generation scheme.

Alternative proof systems

The research theoretical research in the field of ZKP is very active. There are many proof systems each with a certain computational cost. In the future, scientists may be able to design more efficient systems.

If Ethereum and its secondary layer piqued your curiosity, don’t hesitate to test Scroll ! The testnet is already available in alpha version.

The pre-alpha testnet was launched in August 2022. It’s a success story, with more than 100,000 users. Over 15,400,000 transactions have been carried out on this testnet and 1,800,000 blocks have been proven. Over 641,000 batches were submitted as proofs of validity, and finalized by Scroll’s Rollup contract on L1.

The alpha of the Scroll testnet is available on Goerli (one of Ethereum’s test networks). To take part, just follow the few steps outlined on the dedicated portal:

Of course, you’ll need a wallet (like MetaMask) correctly configured. First, import the chain ID and RPC URLs for the Testnet by clicking on the « Add to wallet » buttons on the page. The Goerli testnet is set to MetaMask by default.

To use other walletsand manually configure the chain ID and RPC, all information is available in the dedicated documentation.

Join the development team

To take part in the development of this ambitious project, you can contact the Core Team on Discord, for example (all the useful links are at the end of the article). Of course, you’ll need a technical background consequently. Here are the profiles we’re looking for:

• ZKP researchers;
• ZKP, Golang or Solidity developers;
• GPU engineers ;
• Community animators.

Resources and bibliography

Here are all the links that might be useful for using Scroll or deepening your knowledge of Ethereum, EVM, ZKP and the underlying mathematics.

Scroll

Ethereum and ZKP

zkRollups and Mathematics

• An Incomplete Guide to Rollups – Vitalik Buterin
• Rank-1 Constraint System with Application to Bulletproofs – TariLabs (R1CS specifications, arithmetic circuits)
• Scalable Zero Knowledge via Cycles of Elliptic Curves – Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
• SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge – Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza (including TinyRAM)
• Optimizing Halo and Constructing Graphs of Elliptic Curves – Daira Hopwood
• POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems – Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, Markus Schofnegger
• Cairo: a Turing-complete STARK-friendly CPU architecture – Lior Goldberg, Shahar Papini, and Michael Riabzev
• Aztec emulated field and group operations – Ariel Gabizon (understand Aztec)
• KZG polynomial commitments – Dankrad Feist
• Understanding PLONK – Vitalik Buterin (introduction to Plonk)
• PlonK: Permutations over Lagrange-bases for Ecumenical Noninteractive arguments of Knowledge – Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru (the complete Plonk white paper)
• Explaining Halo 2 – Sean Bowe
• Inner Product Arguments – Dankrad Feist (the model used on the basic version of Halo 2 via Pedersen’s involvement)
• The source code Halo 2
• The modified version including KZG engagement diagram
• PCS multiproofs using random evaluation – Dankrad Feist (Understanding KZG commitment calculations)
• STARK 101 – Starkware’s excellent tutorial on ZKPs with the Square-Fibonacci sequence example
• From AIRs to RAPs – how PLONK-style arithmetization works – Ariel Gabizon (understanding arithmetization)
• Multiset checks in PLONK and Plookup – Ariel Gabizon (Understanding Plonk’s constraint checking)
• Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments – Alin Tomescu (understanding the generation of KZG evaluation proofs)

Keeping your cryptos safe, nothing beats a Ledger wallet. The Nano S and Nano X offer security and ease of use. In fact, they are compatible with the vast majority of cryptos and networks. They are an absolutely essential alternative to all the exchanges that offer to hold your assets for you. Remember, « Not your keys, not your coins »!