The creation of blockchain technology was a paradigm-shifting event that created a system of trust without the reliance of a third-party authority. But the implementation of this revolutionary technology continues to pose a significant challenge related to efficiency: transactions per second (TPS) are not high enough to compete against preexisting systems. Take Bitcoin which only supports 7 transactions per second or Ethereum with 15 per second, and then contrast that with a payment provider like Visa which can process 65,000 per second. For blockchain to support large-scale applications, new technology is needed — which is exactly what a number of labs, scientists, and developers are working on. At present, there are two major layer expansions that address this issue:

Layer 1 Scaling: Directly increase the transaction processing capacity on the chain; also known as on-chain scaling. Common technical solutions are sharding and DAG.

Layer 2 Scaling: A considerable part of the workload is performed off-chain before being transferred on-chain once complete. Common technologies include State Channel, Plasma, Truebit, and the recently popular ZK Rollup.

Principle

The essence of a ZK Rollup is to compress and store the user state on-chain in a Merkle tree, and transfer the state transition of the user states to the off-chain. At the same time, a zkSNARK proof is used to ensure the correctness of the off-chain state transition. The cost of changing the user state directly on the chain is relatively high, whereas the cost of using a smart contract on the chain to verify whether a zero-knowledge proof’s proof is correct is relatively low. In addition, the necessary transfer information is submitted to the contract together to facilitate the user to check the account. Here is how it works.

Two Types of Roles

Transactor: A normal user. This role corresponds to an external account on Ethereum. The user builds the transfer transaction and signs it with the private key before sending the transaction to the relayer.

Relayer: Responsible for collecting and verifying the user’s transaction, then packaging the transaction in batches, and generating the proof of zkSNARK. The relayer finally submits the core data of the user’s transaction, the proof of zkSNARK, and the Merkle root of the new user states to the smart contract on the chain.

Of course, the relayer will not provide services for the transactor free of charge. After all, the relayer needs to consume gas to submit the zkSNARK proof and the transaction data to the chain. Therefore, the transaction sent by the transactor to the relayer must also include the corresponding handling fee.

State Transition Function

When the relayer receives the transaction, it must “execute” it. The execution of a transaction essentially changes the status of the related account. The state transition function (STF) is the function to change the status of those accounts.

The state is for the state machine, and each state machine has a state at some point. We can assume that the initial state of a state machine is S[0]. When an Action T[1] is applied to the state machine, the state of the state machine migrates. We can use the following formula to represent the migration process.

S[1] = STF(S[0], T[1])

Here, S[0] is the initial state, and S[1] is the state after the state machine executes Action T[1].

Then there are several new actions T[2], T[3], …, T[n]that continue to act on the state machine, and the state of the state machine will migrate in turn.

S[2] = STF(S[1], T[2])

S[3] = STF(S[2], T[3])

S[n] = STF[S[n-1], T[n]]

Simply put, we can also T[1], T[2], …, T[n]. As a whole, the state migration process can be simplified to:

S[n] = STF(S[0], T[1], T[2], …, T[n])

More generally, assuming that the state of the current state machine is PRE_STATE, then there are n number of actions T[1], T[2], …, T[n] acting in turn on the state machine, after which the state of the state machine enters POST_STATE. This can be expressed as:

POST_STATE = STF(PRE_STATE, T[1], T[2], …, T[n])

If the above action is replaced by a transfer transaction, and the account set in the system is regarded as a state machine, then the whole process is merely the process of transaction execution on the chain. The execution of this transaction changes the global state of the whole chain. The global state on the chain is also the state collection of each account. The state of all accounts is composed into a Merkle tree. The leaf nodes of the tree are the account states, and the root of the tree can be used to represent the state collection. Therefore, PRE_STATE and POST_STATE are also the roots of the global account status tree.

Account Status Model

The account states of the whole system in the chain can be managed by a Merkle tree. The leaf node of Merkle tree is the users’ status information. Similarly, ZK Rollup can also use a similar Merkle tree to organize its account status.

The simplest account state can include the public key, nonce, and balance of the account. The leaf node has a unique location in the Merkle tree, so the index of the location can indirectly reference this account information.

If we use three bytes to represent the index information, this Merkle tree can support a total of 2²⁴ = 16777216 accounts. This is enough for a general system. Therefore, for example, the account address of Ethereum can be changed from an address with 20 bytes to just 3 bytes of the leaf node index of the Merkle tree. In this way, the account address becomes “compressed”.

In addition to compressing the account address, we can also compress the transfer amount data. For example, for Ethereum the amount is represented by a 256 bit large integer, but there is actually little need to use a super large or super small amount here. If we assume that the minimum unit of transfer in the system is 0.001 ETH, and the transfer amount is represented by 4 bytes, we can support the transfer of 0.001–4,294,967.295 ETH, which is enough for the general system. If there is a situation where it is not enough, you can add more bytes to represent the amount, or introduce floating-point representation.

The handling fee is similar to the transfer amount, and the actual handling fee will fluctuate within a certain range, so we can also set a minimum unit for the handling fee, e.g. 0.001 ETH. Then 1 byte is used to represent the handling fee of 0.001–0.255 ETH. In this case the handling fee is paid by the transactor to the relayer.

Similarly, we can assume that the number of transfers of an account based on normal usage will not number in the tens of thousands, so it is almost enough to use two bytes to represent the nonce of an account because two bytes can represent a range of 0–65535.

Finally, the signature field cannot be compressed. Taking Ethereum as an example, the signature (r, s, v) requires a total of 65 bytes. In fact, EdDSA signatures are widely used in the ZK Rollup system.

Therefore, the format of a transaction is roughly as follows:

The length of each field in the above transaction is only for reference. When implementing the specific system, it is necessary to adjust the length of the field according to the actual situation to prevent the occurrence of field overflow. However, in principle it can be saved. With less data for transactions, then more transactions can be accommodated while using the same storage capacity.

Proof and Verification

After understanding the state transition function and the account state model, let’s take a look at what happens after the relayer collects the transaction.

We just mentioned that in the ZK Rollup system, the account information of all users is managed by a Merkle tree. The root of the Merkle tree is recorded in the smart contract on the chain, and the value of this root also represents the current state of all accounts in the whole system. When a user initiates a transaction, the state will change. But changes must be made in accordance with the following rules.

  • First, you must ensure the legitimacy of the transaction:
  • Is there enough money to pay the transfer amount and handling fee?
  • Is the nonce of the transferred account correct?
  • Is the signature of the transaction correct?
  • Next, the relayer performs the transfer, modifies the outgoing account in the Merkle tree and the leaf node of the transferred account, and recalculates the root of the new Merkle tree.
  • Repeating the second step, the relayer will process multiple transactions at once in a sequential order, and then submit the root of the final calculated Merkle tree as a new state to the smart contract on the chain.

However, there are problems in the above process: if only the root of the state tree is submitted to the contract, how can users believe that the new state root is truthfully calculated according to the above logic? Or what if the relayer does something intentionally harmful, like increasing the handling fee of the transaction?

One way to solve this problem is to ask the relayer to commit the root of the state tree to the contract, and also submit all transactions to the contract, so that anyone can verify whether the relayer has cheated when calculating the new state tree according to these transactions. However, this is equivalent to moving all the data under the chain back to the chain, and does not achieve the purpose of layer 2 scaling.

This problem can be solved by using zero-knowledge proof. The ZK in ZK Rollup is actually the abbreviation of zero-knowledge. After collecting a series of transactions, the relayer needs to generate a PROOF with predefined ZK circuits:

  1. Make sure that the nonce, value, and fees in each transaction T[1], T[2], …, T[n] are correct and the signature is correct.
  2. Ensure that there is no problem with the state migration process, i.e. STF(PRE_STATE, T[1], T[2], …, T[n]) = POST_STATE

Then, the PROOF is submitted to the chain contract together with POST_STATE, t[1], t[2], …, t[n]. Where t[1], t[2], …, t[n] is the simplified information of transaction, excluding nonce and signature. So t[i] is smaller than T[i].

Then the smart contract only needs to verify whether the PROOF is correct. If the PROOF is correct and the state saved in the contract is equal to the PRE_STATE, then the new state POST_STATE will be recorded in the contract and the original state will be replaced.

Since the relayer must generate the PROOF of zkSNARK before it can be submitted to the contract, the PROOF will not be validated if the relayer wrongly modifies the user’s transaction.

In addition, because the transaction t[1], t[2], …, t[n] submitted to the chain does not contain the nonce or signature, the data on the chain will become smaller (in the above example, only 11 bytes for each transaction will be on the chain).

At this time, the relayer cannot modify the user’s transaction due to the limitation of the zkSNARK proof. However, a malicious relayer can still refuse to serve a transactor without collecting the transactor’s transaction. In order to prevent this kind of behavior, the contract must support on-chain withdrawal; in other words, any transactor can take its token away from the chain.

Current Application

At present, a typical ZK Rollup application scenario is a decentralized exchange, represented by Loopring DEX Protocol (v3).

In addition, the open-source ZK rollup framework includes:

Summary

ZK Rollup is a new type of layer 2 scaling scheme. The core idea of this technology is:

  1. Take the main chain as the storage medium instead of the consensus engine
  2. Compress the transaction and reach a state consensus off-chain;
  3. Prove the security of the state consensus under the chain with zero knowledge proof.

At present, the most typical application scenario with ZK Rollup is a decentralized exchange. PPIO is also actively exploring ZK Rollup technology and are trying to apply it to the field of decentralized bandwidth and storage.

References