# Maximizing Efficiency in Ethereum ZKPs: Comparing Groth16 and FFLONK Gas Costs and Implementing Best Practices
---

Author: Kiwi from [@OrbiterResearch](https://x.com/OrbiterResearch)

**TL; DR:**

1. **Gas Cost Analysis of Groth16 and FFLONK Proving Systems**

On Ethereum, the gas cost formulas for Groth16 and FFLONK verifiers can be expressed as:

- **Groth16 Gas Cost** $\approx 207k + 7.16k \times l$
- **FFLONK Gas Cost $\approx 200k + 0.9k \times l$**

Here, $l$ represents the length of the public signals. Both systems have similar cost structures but with different constants, resulting in varying overall gas costs.

2. **Best Practice for Minimizing Gas Costs in ZKP Verification:**

By integrating multiple public signals using Num2Bits and Bits2Num techniques, and applying SHA-256 hashing to use the hash result as the sole public signal, substantial reductions in gas costs are achieved while maintaining data integrity.

---

## **Introduction:**

The Ethereum ZKP ecosystem has evolved from the initial focus on "how to use ZKPs" to a more advanced stage of "how to optimize ZKPs for better efficiency." When implementing ZKPs on-chain, achieving the highest gas efficiency is crucial. Snarkjs supports multiple proving systems, including Groth16, PLONK, and FFLONK—with FFLONK being an optimization over PLONK specifically designed to enhance gas efficiency. This blog provides a detailed analysis of the verification gas costs for Groth16 and FFLONK based on the on-chain verifier generated by snarkjs. Additionally, it presents a best practice inspired by [Polygon's pil-stark](https://github.com/0xPolygonHermez/pil-stark/blob/main/circuits.bn128/stark_verifier.circom.ejs). For those interested in the practical aspects, the code used for gas testing and the implementation of the best practices can be found at [here](https://github.com/kiwi202202/circom-gas-test).

## Comparative Analysis of Groth16 and FFLONK Gas Costs

This section provides a detailed analysis of the gas costs associated with Groth16 verification steps. The analysis begins with a breakdown of Groth16's verification logic and its corresponding gas expenditures, validated through a testing framework. Subsequently, the gas costs for FFLONK are briefly compared.

### Initial Setup:

- **Scheme**: Groth16
- **Curve**: BN254
- **Proof $\pi$**: 2 G1 points ($A, C$), 1 G2 point ($B$)
- **pubSignals**: Length $l$, each being a scalar field element from $\mathbb{F}_p$, where $p$ is the prime characteristic of the scalar field used in the BN254 curve.

### Verification Steps and Gas Costs:

1. **Calldata Gas Consumption**:

    function verifyProof(
        uint[2] calldata _pA,
        uint[2][2] calldata _pB,
        uint[2] calldata _pC,
        uint[32] calldata _pubSignals
    )

- **Fixed Proof Size**: Total of 256 bytes (_pA: 64 bytes, _pB: 128 bytes, _pC: 64 bytes)
- **PubSignals**: Proportional to the number of public inputs, 32$l$ bytes
- **Gas Cost Calculation**:

$$
\text{Calldata Gas Cost} = (\text{Non-zero Bytes} \times 16) + (\text{Zero Bytes} \times 4)
$$

Assuming all bytes are non-zero:

$$
\text{Groth16 Calldata Gas Cost} = (256 + 32l) \times 16
$$

2. **Pre-allocate Memory Space**: $Fixed\ Gas\ Cost$

    let pMem := mload(0x40)
    mstore(0x40, add(pMem, pLastMem))

- Allocates 896 bytes but only moves the pointer.
- This memory space is used for Pairing Check later.
3. **Check pubSignals in $\mathbb{F}_p$ Range**:

    checkField(calldataload(add(_pubSignals, 0)))
    checkField(calldataload(add(_pubSignals, 32)))

- Gas cost for each `checkField`: 61 gas, based on empirical data.
- Total gas cost for $l$ pubSignals: $61 \times l$
4. **Check Pairing**: $Fixed\ Gas\ Cost + 6587 \times l$

This step is more complicated. We will analyze the gas cost of each small step directly in the below code comments. The main gas overhead is MSM and Pairing Check.

**MSM for $l$ public signals:** The gas cost of MSM is proportional to $l$. The measured coeffient is 6587 per pubSignal, which is similar to the estimated result through [EIP-1108](https://eips.ethereum.org/EIPS/eip-1108): 6150+, because a single operation is actually: one ECADD + one ECMUL + several times add, sub, mstore, mload and other operations.

The gas cost of ECADD and ECMUL of curve BN254 is shown in the table below in [EIP-1108](https://eips.ethereum.org/EIPS/eip-1108):


**Pairing Check:** In the verifyProof process of Groth16, the last step is Pairing Check, and the gas cost is the formula in the table above, $34000 \times k \ + 45000$. According to [EIP-197](https://eips.ethereum.org/EIPS/eip-197), k = bytes / 192 = 768 / 192 = 4 (in Groth16, the data amount of the input is always the same, 768 bytes)
Therefore, the gas cost of Pairing Check: 34000 * 4 + 45000 = 181000

function checkPairing(pA, pB, pC, pubSignals, pMem) -> isOk
{
    // Allocate memory, fixed gas
    let _pPairing := add(pMem, pPairing)
    let _pVk := add(pMem, pVk)

    // Load MSM initial point, fixed gas
    mstore(_pVk, IC0x)
    mstore(add(_pVk, 32), IC0y)

    // MSM Gas Cost: Proportional to N
    
    // g1_mulAccC performs scalar multiplication of multiple elliptic curve points 
    // (ICx, ICy)
    // and the pubSignals scalar array one by one, and accumulates them into _pVk
    // Essentially, it's an MSM operation of the elliptic curve point array 
    // [(ICx1, ICy1), (ICx2, ICy2) ...]
    // and the scalar array [pubSignal_0, pubSignal_1 ...]
    // Accumulated onto the initial point (ICx0, ICy0)

    g1_mulAccC(_pVk, IC1x, IC1y, calldataload(add(pubSignals, 0)))
    g1_mulAccC(_pVk, IC2x, IC2y, calldataload(add(pubSignals, 32)))

    ...

    // Load points for Pairing Check, fixed gas
    // -A
    mstore(_pPairing, calldataload(pA))
    mstore(add(_pPairing, 32), mod(sub(q, calldataload(add(pA, 32))), q))
    // B
    mstore(add(_pPairing, 64), calldataload(pB))
    mstore(add(_pPairing, 96), calldataload(add(pB, 32)))
    mstore(add(_pPairing, 128), calldataload(add(pB, 64)))
    mstore(add(_pPairing, 160), calldataload(add(pB, 96)))
    // alpha1
    mstore(add(_pPairing, 192), alphax)
    mstore(add(_pPairing, 224), alphay)
    // beta2
    mstore(add(_pPairing, 256), betax1)
    mstore(add(_pPairing, 288), betax2)
    mstore(add(_pPairing, 320), betay1)
    mstore(add(_pPairing, 352), betay2)

    // vk_x
    mstore(add(_pPairing, 384), mload(add(pMem, pVk)))
    mstore(add(_pPairing, 416), mload(add(pMem, add(pVk, 32))))
    // gamma2
    mstore(add(_pPairing, 448), gammax1)
    mstore(add(_pPairing, 480), gammax2)
    mstore(add(_pPairing, 512), gammay1)
    mstore(add(_pPairing, 544), gammay2)
    // C
    mstore(add(_pPairing, 576), calldataload(pC))
    mstore(add(_pPairing, 608), calldataload(add(pC, 32)))
    // delta2
    mstore(add(_pPairing, 640), deltax1)
    mstore(add(_pPairing, 672), deltax2)
    mstore(add(_pPairing, 704), deltay1)
    mstore(add(_pPairing, 736), deltay2)

    // Pairing Check: Gas cost is fixed due to constant input data size
    let success := staticcall(sub(gas(), 2000), 8, _pPairing, 768, _pPairing, 0x20)

    // Return result, fixed gas
    isOk := and(success, mload(_pPairing))
}

5. **Return Result**:

Finally, we return the verifyProof result , this step has fixed gas cost.

    mstore(0, isValid)
    return(0, 0x20)

### Gas Cost Summary:

The total gas cost for Groth16 verification is composed of two parts: a fixed cost (FIXED_GAS) and a variable cost proportional to the number of pubSignals (K * $l$).

- **Fixed Gas Cost (FIXED_GAS)**:
- Approximately 207700 gas, mainly due to the Pairing Check (181000 gas).
- **Proportional Gas Cost (K)**:
- The gas cost per pubSignal is approximately 7160 gas, broken down as follows:

$$
7160 = 32 \times 16 (\text{calldata cost}) + 61 (\text{bn128 checkField}) + 6587 (\text{scalar multiplication and accumulation})
$$

- Actual gas cost per pubSignal ranges from 6776 to 7160 gas due to varying calldata costs for zero and non-zero bytes.

The gas cost formula of Groth16's `verifyProof` function is:

$$
207700 + 7160 \times l
$$

where $l$ is the number of public signals.

If we do not consider calldata overhead (for example, when another contract calls the Groth16 verifier's `verifyProof` method), the formula becomes:

$$
203600 + 6792 \times l
$$

## Testing:

To validate these findings, a testing framework is used: [**circom-gas-test**](https://github.com/kiwi202202/circom-gas-test).

**Steps to Test a New Circuit:**

1. **Write the Circom File**: Create a `.circom` file within the `circuits` directory to define your circuit.
2. **Set Up Input**: Add a corresponding `input.json` file in the `inputs` directory to feed data into your circuit.
3. **Modify and Run Tests**: Update the `CIRCUIT_NAME` and `INPUT_PATH` in the `e2e` script to match your new circuit and input. Optionally, you can add a new `powersOfTau` file if required.

Run the test with the updated script settings, and analyze the gas consumption of your circuit.

### Testing Results for Groth16 Verification Gas Costs

This section presents the testing outcomes for Groth16 verification across diverse circuits and configurations. The tests are divided into two parts: comparing circuits with different scales but the same number of pubSignals, and comparing circuits with different numbers of pubSignals.

### Part 1: Sha256 Circuit Comparison

**Testing Setup:**

- **Environment**: Hardhat optimizer enabled, runs: 999999
- **Circuit**: Sha256
- **Public Signals**: 32

**Test Cases and Results:**

1. **Sha256_test**: Hashing 64 bytes, powersOfTau28_hez_final_16.ptau
- Gas Cost: 424660

1. **Sha256_test_in_1024**: Hashing 1024 bytes, powersOfTau28_hez_final_19.ptau
- Gas Cost: 424660

1. **Sha256_test_in_4096**: Hashing 4096 bytes, powersOfTau28_hez_final_21.ptau
- Gas Cost: 424636

Despite the significant differences in circuit scale and the powersOfTau files (16, 19, 21), the gas consumption remains consistent. This result aligns with the theoretical analysis of the verification code logic.

Based on the previously derived formula, the gas cost of SHA256 circuit:

$$
\text{SHA256 Gas Cost} = 207700 + 7160 \times 32 = 436820
$$

The observed results are slightly higher by about 10,000 gas. This discrepancy is due to the specific format of the pubSignals, where each pubSignal only has one effective byte, with the remaining 31 bytes being zero.

Adjusting for this:

$$
\text{Adjusted Gas Cost} = 207700 + 6788 \times 32 = 424916
$$

This adjusted result closely matches the observed gas cost, with only a 200 gas difference, likely due to the Hardhat optimizer. The code snippet below highlights the conversion of output bytes to bits, indicating the minimal effective bytes in each pubSignal:

component bits_to_bytes[32];
for (var i = 0; i < 32; i++) {
  bits_to_bytes[i] = Bits2Num(8);
  for (var j = 0; j < 8; j++) {
    bits_to_bytes[i].in[7-j] <== sha256.out[i*8+j];
  }
  out[i] <== bits_to_bytes[i].out;
}

### Part 2: Comparison with Different pubSignals

**Testing Setup:**

- **Environment**: Hardhat optimizer enabled, runs: 999999

**Test Cases and Results:**

1. **Sha256_test**: Hashing 64 bytes, 32 pubSignals
- Gas Cost: 424660

2. **Sha256_test_out_64**: Hashing 64 bytes, with 64 pubSignals (hash result duplicated)

- Gas Cost: 641844
- Difference due to additional 32 pubSignals: $641844 - 424660 = 217184 = 6787 \times 32$
- Gas per additional pubSignal calculated from the previous formula : $7160 - 31\times(16 - 4) = 6788$. This result is derived by subtracting the difference in gas costs between non-zero and zero bytes on Ethereum from the base coefficient of 7160, specifically, the cost reduction due to 31 zero bytes in each pubSignal, each saving 12 gas compared to a non-zero byte.
- Note that the calculated estimate of $6788$ per additional pubSignal closely aligns with the empirically tested result of $6787$.

**Base Fixed Gas Cost Calculation:**

Reversing the calculation to estimate the fixed gas cost:

$$
424660 - 6787 \times 32 = 207476 \approx 207700
$$

### Multiplier Circuit Tests

**Test Cases and Results:**

1. **Multiplier_1M**: Circuit with one pubSignal and 1M multiplication gate
- Gas Cost: $214635 \approx 207700 + 7160$

2. **Multiplier_10k**: Circuit with one pubSignal and 10k multiplication gate
- Gas Cost: $214659 \approx 207700 + 7160$

These results reinforce the theoretical analysis, confirming that the gas cost for Groth16 verification is largely determined by the number of pubSignals, with the fixed and proportional costs closely matching the calculated values.

## Comparative Analysis of FFLONK Gas Costs

FFLONK, like Groth16, has a fixed proof size but a variable length for public signals.

The increase in the number of public signals will also cause the gas cost of these steps to increase proportionally, including: calldata, computing challenges, performing inversions, evaluating the Lagrange polynomial, and calculating the public input polynomial evaluation. Similar to Groth16, we can approximate the gas cost with the following formula:

$$
\text{Fflonk Gas Cost} \approx 200k + 0.9k \times \text{len(public signals)}
$$

When ignoring calldata consumption:

$$
\text{Fflonk Gas Cost} \approx 188k + 0.6k \times \text{len(public signals)}
$$

The coefficients of these formulas are mainly obtained through testing and empirical data. The testing environment utilized Hardhat with the optimizer enabled and configured for `runs: 999999` to ensure accurate and optimized results.

The primary fixed gas cost arises from the pairing check, which costs around 113000 gas. Compared with Groth16, fflonk requires fewer pairings (k = 2) when calling the precompiled contract of Pairing check. Therefore, the gas cost of Pairing check is calculated as 113000 = 34000*2 + 45000

During testing of the FFLONK's gas expenses, it was observed that enabling Hardhat's optimizer with the setting `runs: 999999` led to a significant reduction of approximately 16,000 gas compared to the scenario where the optimizer was disabled. Notably, Groth16's gas cost is less affected by compiler optimizations. However, this optimization increases the bytecode size of the FFLONK contract, restricting it to a maximum of four public signals. This limitation on the number of public signals can be addressed in the 'Best Practice for Minimizing Gas Costs' section later in this article.

This breakdown highlights the linear relationship between gas cost and the number of public signals, with a fixed overhead, providing insight into optimizing gas costs in zero-knowledge proof applications on Ethereum.

## Best Practice for Minimizing Gas Costs

In the quest to optimize gas costs for zero-knowledge proofs (ZKPs) on Ethereum, one effective strategy involves reducing the number of public signals in the circuit. This section will detail how to implement this strategy using Num2Bits and Bits2Num templates to merge multiple pubSignals and leverage SHA-256 hashing to condense them into a single pubSignal, inspired by Polygon's [zkEVM](https://docs.polygon.technology/zkEVM/) contract.

### Merging Multiple pubSignals with Num2Bits and Bits2Num

Combining multiple public signals into a single signal can reduce the gas cost associated with ZKP verification. [Circomlib](https://github.com/iden3/circomlib) provides two useful templates, **`Num2Bits`** and **`Bit2Num`**, to facilitate this process. Both functions use little-endian order.

**Num2Bits Template**

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1 = 0;
    var e2 = 1;
    for (var i = 0; i < n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] - 1) === 0;
        lc1 += out[i] * e2;
        e2 = e2 + e2;
    }
    lc1 === in;
}

**Bits2Num Template**

template Bits2Num(n) {
    signal input in[n];
    signal output out;
    var lc1 = 0;
    var e2 = 1;
    for (var i = 0; i < n; i++) {
        lc1 += in[i] * e2;
        e2 = e2 + e2;
    }
    lc1 ==> out;
}

These templates are particularly useful because they help to reduce the number of individual signals that need to be managed, thus reducing gas costs.

### Hashing pubSignals

By hashing all original pubSignals and using the hash result as the sole pubSignal, we can minimize gas costs while maintaining data integrity. This approach is inspired by the [Polygon zkEVM contract](https://github.com/0xPolygonHermez/zkevm-contracts/blob/main/contracts/PolygonZkEVM.sol). The relevant Solidity code is as follows:

// Get snark bytes
bytes memory snarkHashBytes = getInputSnarkBytes(
    initNumBatch,
    finalNewBatch,
    newLocalExitRoot,
    oldStateRoot,
    newStateRoot
);

// Calculate the snark input
uint256 inputSnark = uint256(sha256(snarkHashBytes)) % _RFIELD;
// Verify proof
if (!rollupVerifier.verifyProof(proof, [inputSnark])) {
    revert InvalidProof();
}

This method adds only a single SHA256 hash computation onchain, which incurs a relatively low gas cost.

Specifically:

- keccak256: 30 gas + 6 gas for each word of input data
- sha256: 60 gas + 12 gas for each word of input data

It is important to evaluate the security implications of reducing the SHA256 hash output to fit the BN254 elliptic curve's scalar field. While SHA256 outputs a robust 256-bit hash, reducing this to 254 bits slightly decreases collision resistance from 128 to 127 bits, and pre-image and second pre-image resistances from 256 to 254 bits.


However, it's crucial to note that the inherent security level of the BN254 curve is about [100 bits](https://github.com/zcash/zcash/issues/714), which contextualizes the aforementioned security reduction as acceptable. This difference in security levels indicates that while the hash reduction slightly lessens SHA256's robustness, the overall security for applications using the BN254 curve is primarily governed by the curve's characteristics rather than the hash function's reduction.

This compromise in theoretical security is offset by gains in computational efficiency and gas cost savings in Ethereum ZKP applications, making it a reasonable trade-off in scenarios where cost and speed are prioritized.

### Implementing pubSignals hashing in Circom

To implement this in a Circom circuit, you can use an EJS template to wrap the required steps, making it easy to integrate with various circuits. Here's an example of such an implementation, you can check out the full code and examples at [Circom Gas Test](https://github.com/kiwi202202/circom-gas-test).:

<%
var circuitPaths = internalInfo.circuitPaths;
var internalCircuitName = internalInfo.circuitName;
var nPublics = internalInfo.nPublics;
var publicsBits = internalInfo.publicsBits;
var totalBits = publicsBits.reduce((sum, bits) => sum + bits, 0);
%>

pragma circom 2.0.3;

<% circuitPaths.forEach(function(path) { %>
include "<%- path %>";
<% }); %>

template Main() {
    signal input in[<%- internalInfo.inputSize %>];
    signal output out;

    component internalCircuit = <%- internalCircuitName %>();
    for (var i = 0; i < <%- internalInfo.inputSize %>; i++) {
        internalCircuit.in[i] <== in[i];
    }

    component hasher = Sha256(<%- totalBits %>);
    component bitsConverters[<%- nPublics %>];

    var offset = 0;

    <% for (var i = 0; i < nPublics; i++) { %>
        bitsConverters[<%= i %>] = Num2Bits(<%= publicsBits[i] %>);
        bitsConverters[<%= i %>].in <== internalCircuit.out[<%= i %>];

        <% for (var j = 0; j < publicsBits[i]; j++) { %>
            hasher.in[offset + <%= publicsBits[i] - 1 - j %>] <== bitsConverters[<%= i %>].out[<%= j %>];
        <% } %>
        offset += <%= publicsBits[i] %>;
    <% } %>

    component resultConverter = Bits2Num(256);
    for (var i = 0; i < 256; i++) {
        resultConverter.in[i] <== hasher.out[255 - i];
    }

    out <== resultConverter.out;
}

component main = Main();

By merging multiple public signals using Num2Bits and Bits2Num and applying SHA-256 hashing, significant gas cost reductions are achieved in on-chain ZKP verification. This method efficiently aligns circuit signals with smart contract requirements, optimizing gas usage and streamlining the verification process. An added benefit is that reducing the number of pubic signals helps avoid issues like the "transaction reverted: trying to deploy a contract whose code is too large" error, which can occur when using FFLONK.

## **Conclusion:**

In our exploration of gas costs for ZKP systems on the Ethereum, we've elucidated the distinctions between Groth16 and FFLONK proving systems. Although both systems follow a similar gas cost structure, their constants differ, which points to distinct implications for practical deployments, depending on the scenario and scale of use. Additionally, it's important to note that FFLONK has a much higher requirement for the size of the `powersOfTau` file compared to Groth16, which could influence the choice of system based on resource availability and specific application needs.

Our comparative analysis has established that although Groth16 is more widely used, FFLONK offers modifications that can lead to significant cost savings, especially in scenarios involving a high volume of public signals. This insight is vital for applications that rely heavily on frequent ZKP verifications, where optimizing gas efficiency is a critical concern.

Moreover, the best practice derived from the techniques employed by Polygon in their [pil-stark project](https://github.com/0xPolygonHermez/pil-stark/blob/main/circuits.bn128/stark_verifier.circom.ejs) offers a robust framework for significantly reducing gas costs. By leveraging methods such as Num2Bits and Bits2Num to consolidate multiple public signals and applying a SHA-256 hash to use a single signal, we achieve a dual benefit: lowering gas consumption and maintaining data integrity.

As the Ethereum ecosystem continues to mature and more developers look to implement ZKP-based applications, these insights and methodologies will play a crucial role in shaping efficient, scalable, and cost-effective solutions.

For practitioners and enthusiasts alike, the journey toward optimizing ZKPs is both challenging and rewarding. As we forge ahead, it is our collective experimentation, collaboration, and innovation that will drive the evolution of blockchain technology to new heights.