This article is written by DeGate evangelist Carlos Ramos. The views expressed herein are those of the author and do not necessarily represent the views of DeGate. The views expressed are not to be taken as financial advice. We thank Carlos Ramos for his analysis.
DeGate is a decentralized protocol built on Zero Knowledge (ZK) technology within the Ethereum ecosystem. As a ZK Rollup DEX, DeGate offers an experience similar to popular centralized exchanges (CEX), such as Binance or Bybit. The protocol supports several functions, including Spot Trading and Grid Trading, and more features are continually added to ensure a seamless trading experience. DeGate is designed to be fast and affordable, aiming to provide a more efficient and accessible means for users to gain exposure to various asset classes.
In this article, we will delve deeper into the architecture of DeGate and the technology behind Zero Knowledge and Groth16.
DeGate Architecture
The core of the DeGate is Zero Knowledge-Rollup (ZK-Rollup) technology which has some on-chain and off-chain components. Account and assets changes are processed off-chain and rolled up to the on-chain smart contract.
On-Chain component
The DeGate Smart Contract is the on-chain component. The smart contract is deployed on the Ethereum blockchain and is accessible to anyone who wants to interact with the exchange. This enables a trustless and transparent exchange of tokens, where users have full control over their funds and transactions are executed automatically without fully depending on DeGate ( see Exodus Mode ). Smart contracts that are deployed on the EVM network store assets, verify zero-knowledge proofs and provide the methods for deposit and withdrawal.
Off-Chain Components
DeGate also utilizes off-chain order matching and order book management to reduce transaction costs and increase the speed of trade execution. This is done thanks to the technology of zk-rollups, which allows for fast and efficient processing of large volumes of transactions without burdening the Ethereum network, but remaining secure and trustless.
The DeGate off-chain node mainly includes
- Trading System: Process users’ orders, perform order matching in the order book, process the events with account and asset state changes
- Operator: Periodically process account and asset off-chain transactions, generate zkBlock, call the zkp-worker, submit proofs (zkBlock data)
- Zkp-Worker: Describes the events that require zero-knowledge proof, and generates the zero-knowledge proofs
- Merkle Tree: Stores DeGate protocol’s accounts, assets, and orders in a tree structure
- Chain Sync: Observe and confirm all transactions that occur within the DeGate smart contracts
- Postman: Calls DeGate smart contract methods on the EVM network and submits zkBlock data to the smart contract
ZK-Rollup Technology
From the previous image, we can say that DeGate has a main component called as DeGate Node L2, and the rollup process can be summarized into the following three steps:
- The user signs a request, which can be done via DeGate using the asset Private key (PK) or using the user wallet PK ( transfers, deposits )
- The node verifies and processes the user requests, batches the off-chain transactions into blocks, and calls the circuit to generate the zero-knowledge proofs.
- The node sends the proof result to the on-chain contract for verification, completing the ZK-Rollup and enabling data availability.
Data Availability
The DeGate ZK-Rollup is secured by two key factors: proof generation and proof verification. In DeGate protocol, the proof generation is undertaken by the operator through an off-chain circuit program. The relayer collects a large number of transactions to generate a SNARK proof. The SNARK proof is a hash-like piece of content that represents the change set to the state of DeGate. For verification, to achieve and prove trustlessness in the blockchain system, we use immutable open-source smart contracts with a fixed verification key.
Circuit Program
About circuits : The circuit of Zero Knowledge Proof is a logical circuit that consists of several logic gates. Any calculation can be described as an arithmetic circuit. Based on this premise, complex logical operations can be disassembled and described in terms of simple addition and multiplication gates.
A ZKP ( Zero Knowledge proof ) is a protocol that enables one party, the prover, to convince another, the verifier, that a statement is true without revealing any information beyond the veracity of the statement. Non-Interactive ZKPs (NIZK) are a particular type of zero-knowledge proofs in which the prover can generate the proof without interaction with the verifier. NIZK protocols are very suitable for Ethereum applications, because they allow a smart contract to act as a verifier. This way, anyone can generate a proof and send it as part of a transaction to the smart contract, which can perform some action depending on whether the proof is valid or not. In this context, the most preferable NIZK are zk-SNARK (Zero-knowledge Succinct Non Interactive Argument of Knowledge), a set of non-interactive zero-knowledge protocols that have succinct proof size and sublinear verification time. The importance of these protocols is double: on the one hand, they help improve privacy guarantees, and on the other, they are a possible solution to scalability issues, and this is why it fits perfectly into DeGate’s Architecture.
Like most ZKPs, zk-SNARKs permit proving computational statements. For example, one can prove things like: the knowledge of a private key associated with a certain public key, the correct computation of a transaction, or the knowledge of the preimage of a particular hash. Importantly, one can do these things without leaking any information about the statements in question. In other words, without leaking any information about the private key, the transaction details, or the value of the preimage. More specifically, zk-SNARKs permit proving any computational statement that can be modelled with an arithmetic circuit, This type of circuits are often called zk-SNARK circuits. It is worth mentioning as well that the implementation of most zk-SNARK protocols (e.g. Pinnochio, GGPR13 and Groth16) makes use of elliptic curve cryptography.
Groth16 in detail
Groth16 is a zero-knowledge proof system that uses elliptic curves to enable efficient verification of computations involving arithmetic circuits. The construction is based on the following components:
- A bilinear pairing e: G1 x G2 → GT between two groups of points, G1 and G2, of prime order r, and a target group GT.
- A common reference string (CRS), which is a set of public parameters that are generated ahead of time and used in the proof generation and verification process.
- A circuit C(x) that describes the computation to be proved, where x is a vector of inputs to the circuit.
The Groth16 construction consists of three phases: key generation, proof generation, and verification.
The Groth16 construction involves several mathematical formulas and concepts, including elliptic curves, bilinear pairing functions, and zero-knowledge proofs.
Groth16 : Trusted setup
In Groth16, the trusted setup process involves generating a common reference string (CRS) that is used in the proof generation and verification process. The CRS is a set of public parameters that are generated ahead of time and distributed to all parties involved. The process involves generating random values that are used to create the public parameters of the CRS in a way that ensures they cannot be predicted or manipulated. The private values used to generate the public parameters are then destroyed to prevent them from being used to compromise the security of the system. The trusted setup process is critical for ensuring the security and integrity of the system.
Groth16 : QAP and FFT
In Groth16, the proof generation process involves creating a quadratic arithmetic program (QAP) that represents the computation being proved. The QAP is then transformed using fast Fourier transform (FFT) algorithms to create a succinct representation of the computation that can be used in the proof.
The QAP represents the computation being proved as a system of quadratic equations, where the variables are the inputs and intermediate values of the computation. The QAP is then transformed using FFT algorithms to create a polynomial commitment that represents the computation in a succinct form. This polynomial commitment is then used in the proof to verify the correctness of the computation.
The FFT algorithms used in Groth16 are based on the Cooley-Tukey algorithm, which is a widely-used algorithm for computing the discrete Fourier transform (DFT) of a sequence. The Cooley-Tukey algorithm is used to perform the FFT on the QAP, transforming it into a polynomial commitment that is much smaller than the original QAP.
The use of QAP and FFT in Groth16 allows for the efficient generation and verification of zero-knowledge proofs for computations involving arithmetic circuits. The use of FFT reduces the size of the proof, making it more efficient to compute and verify, while the use of QAP allows for a more natural representation of the computation being proved.
Groth16: ALT_BN128 curve
ALT_BN128 is a known elliptic curve. Pre-compiled contracts for this curve have been added to Ethereum in EIP196 and EIP197, which makes it possible to save more gas by using this curve for on-chain calculations.
The ALT_BN128 curve is a popular choice for pairing-based cryptography, and is used in the DeGate protocol for efficient verification of transactions. Here’s a comparison of the ALT_BN128 curve with some other commonly used curves in blockchain applications:
- secp256k1: The secp256k1 curve is widely used in blockchain applications, including Bitcoin. It has a prime order of 2²⁵⁶ — 2³² — 2⁹ — 2⁸ — 2⁷ — 2⁶ — 2⁴ — 1, and is defined by the equation y² = x³ + 7. The secp256k1 curve is faster than the ALT_BN128 curve for some operations, but is not pairing-friendly.
- BLS12–381: The BLS12–381 curve is another popular choice for pairing-based cryptography, and is used in several blockchain applications, including Zcash. It has a prime order of 2³⁸¹ — 3, and is defined by the equation y² = x³ + 4. The BLS12–381 curve is slower than the ALT_BN128 curve for some operations, but is more secure and has a larger security parameter.
Groth16 in DeGate
After much research and discussion, DeGate finally chose Groth16 for its zk-SNARK protocol. Groth16 is widely used and applied by many leading projects, and it has a rich library, making it friendly for developers. It also allows DeGate to achieve fast proof generation, lower ZK-Rollup cost within acceptable security limits.
Groth16 requires developers to implement the R1CS (Rank-1 Constraint System) circuit. It uses FFT (Fast Fourier Transformation) operations to optimize the efficiency of polynomial computation. The range of values of FFT is different for different curves, but all we need to find is two values on the prime domain of the curve that satisfy:
$$ 2^s * t = module -1 $$
where t is an odd number and 2^s is the range of values of the group for FFT.
Groth16 uses the ALT_BN128 curve. For the ALT_BN128 curve, s = 28, so the FFT takes the value range (0, 2²⁸), which is the range of the number of constraints of the R1CS circuit.
ZK Block Size & FFT:
To summarize, DeGate bundles off-chain transactions into zkBlocks and submits them to the blockchain. The number of transactions in a zkBlock is determined before deployment based on the number of constraints that can be supported by the ALT_BN128 curve and the difficulty of FFT calculations. The larger the number of transactions in a zkBlock, the more complex the problem becomes and the larger the volume of R1CS circuit constraints. To ensure efficient and secure processing of zkBlocks, DeGate has identified several zkBlock sizes with specific numbers of transactions. These sizes range from 5 to 355 transactions, with different sizes corresponding to different sets of PKs and VKs. The appropriate number of transactions in a zkBlock is determined by whether the total number of constraints in the zkBlock reaches the limit value of 2^s, where s is determined by the FFT range formula and determines the difficulty of FFT calculations in terms of CPU and memory usage.
According to the FFT range formula, different s values determine a different value range, and different value range determines the difficulty of FFT calculation, i.e. the amount of CPU and memory usage. So how to determine the appropriate number of transactions depends on whether the total number of constraints of zkBlock reaches the limit value of 2^s.
The FFT range formula is used to determine the appropriate FFT sizes for a given number of constraints, based on the degree of the polynomial being evaluated and the size of the field being used.
Currently, zkBlocks produced by DeGate have the following sizes: 355, 300, 250, 200, 150, 100, 50, 25, 10.
Trusted Setup
When the DeGate protocol is deployed to the Ethereum mainnet, both the circuit and smart contract was initialized. This process is also known as the trusted setup which involves random entropy. DeGate protocol’s trusted setup is divided into two phases
- References the Power of Tau configuration as the initial value.
- Based on the initial value, a future bitcoin block hash is first referenced, followed by getting 5 community members to provide random entropy, and another future bitcoin block hash is referenced. Finally, a Proving Key and a Verifying Key are computed and stored in the circuit and smart contract respectively.
Why Groth16 in DeGate ?
Groth16 is used in DeGate due to its efficiency and security properties. Compared to other zk-SNARK constructions, Groth16 has relatively small proof sizes and fast verification times, making it a good fit for DeGate’s requirements of efficient and secure transaction processing. Groth16 also has the advantage of being transparent and simple to understand, which helps with security audits and testing.
Groth16 vs other popular zk-SNARK constructions
Here is a comparison of Groth16 with some other popular and modern zk-SNARK constructions in terms of proof size and verification time:
ref : CTH
Groth16 is still unbeatable in terms of proof size and verification time is quite fast. The numbers in the table below, therefore, should be taken with a grain of salt. They’re based on benchmarks in the papers, or based on estimates provided by the inventors.
GROTH VS PLONK
Although Groth16 and PLONK are both efficient zk-SNARK constructions with comparable proof sizes and verification times, they have some key differences in their design and implementation.
- Proving system: Groth16 uses a quadratic arithmetic program (QAP) proving system, while PLONK uses a permutation argument system ( “grand product”). The QAP approach involves representing the input and output of a computation as polynomials, while the permutation approach involves representing the computation as a permutation of field elements. The choice of proving system affects the efficiency and security properties of the zk-SNARK construction.
- Security: Groth16 has been extensively studied and has been shown to have strong security properties, such as resistance to adaptive chosen message attacks. PLONK is a relatively new zk-SNARK construction that is still undergoing active research and development, and its security properties are still being analyzed.
- Transparency: Groth16 is considered to be more transparent than PLONK, as it involves fewer layers of abstraction and is easier to understand and audit. PLONK involves more complex mathematical operations, which can make it more difficult to verify the correctness of the implementation.
- Size of public parameters: Groth16 requires a larger size of public parameters than PLONK, which can be a disadvantage in some applications. However, the size of public parameters can be reduced through the use of trusted setups, which is a standard practice in zk-SNARK constructions.
- Support for more complex circuits: PLONK has been designed to support more complex sets of circuits than Groth16, such as circuits with up to a million constraints. Groth16 is better suited for smaller circuits with up to tens of thousands of constraints.
Overall, Groth16 is best suited when an application needs to generate many proofs for the same circuit (for instance a single logic computation) and performance is critical, while PlonK is best suited when it needs to handle many different circuits (for example different arbitrary business logics) with reasonably fast performance.
In DeGate Context : Why Groth16 over Plonk ?
While PLONK is also a strong zk-SNARK construction, it has some additional complexities in terms of the trusted setup and proof generation. In addition, Groth16 has been more extensively studied and has a longer track record of use in blockchain applications.
Therefore, Groth16 is the most suitable zk-SNARK construction for DeGate, as it provides the necessary efficiency, security, and simplicity for processing transactions on the Ethereum blockchain.
And finally, this is why Groth16 is the most suitable zkSnark for DeGate :
- Efficiency: According to the DeGate product overview, the protocol is designed to blocks of up to 355 transactions. Groth16 is well suited for this task because it has been shown to be very efficient for pairing-based cryptography, which is used extensively in zk-SNARKs.
- Security: As mentioned earlier, Groth16 is considered to be very secure and has a strong track record of use in blockchain applications. This is important for DeGate because it deals with the processing of financial transactions and requires a high level of security
- Numbers: The verification time for Groth16 is approximately 10 milliseconds on a typical CPU, which is much faster than other zk-SNARK constructions. In addition, the proof size for Groth16 is relatively small, which means that it requires less data to be transferred on the blockchain. This is important for DeGate because it helps to reduce the gas costs associated with processing transactions on the Ethereum blockchain.
CONCLUSION
This article provides an in-depth analysis of the DeGate protocol and its underlying Groth16 proof system, explains how DeGate leverages the Groth16 proof system to create a secure and efficient decentralized exchange platform. Various components of the DeGate architecture were highlighted, giving thus a more clear understanding of ZK in the context of DeGate.
