1. Introduction and Background

Groth16 is one of the most famous zkSNARK proving schemes. There are also other proving schemes, such as PGHR13, GM17. Compared with early proving schemes, Groth16 has a smaller proof size (only two 𝔾₁ elements and one 𝔾₂ element) and a faster proving & verification speed (only one equation needs to be verified). Groth16 has been widely used in many projects, such as Zcash, Filecoin, etc.

Groth16 is a zero-knowledge proof protocol proposed by Daniel Jens Groth in the paper β€œOn the Size of Pairing-based Non-interactive Arguments” published in 2016.

Please note that the name of the general algorithm is composed of the first letter of the author’s surname and the year. Similar ways of naming algorithms include GGPR13 β€” an algorithm proposed by Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova in 2013 in the paper β€œQuadratic Span Programs and Succinct NIZKs without PCPs”.

2. An Overview of the Groth16 Algorithm

Like other QAP-based algorithms, in a Groth16 scheme, a prover needs to prove that he knows a secret called witness (aβ‚—β‚Šβ‚, aβ‚—β‚Šβ‚‚, …, aβ‚˜) which satisfies the following equation with public statement (a₁, aβ‚‚, …, aβ‚—) and aβ‚€ = 1.

uα΅’(X),vα΅’(X),wα΅’(X),h(X),t(X) in the above equation is related to the specific problem to be proved and is not related to the secret witness held by the prover and the public statement.

2.1 Setup Phase

In the setup phase, pick Ξ±, Ξ², Ξ³, Ξ΄, x ← β„€β‚š*, define Ο„ = (Ξ±, Ξ², Ξ³, Ξ΄, x), and compute Οƒ=([σ₁]₁, [Οƒβ‚‚]β‚‚), where

Here [σ₁]₁ are elements on the elliptic curve 𝔾₁. Also [Οƒβ‚‚]β‚‚ are elements on the elliptic curve 𝔾₂.

Please note: After the calculation of [σ₁]₁, [Οƒβ‚‚]β‚‚ is completed, the original random parameter sets σ₁ and Οƒβ‚‚ need to be discarded. They are also known as β€œtoxic waste”. If they are not discarded, the entire system will be considered unsafe, because a person who knows σ₁ and Οƒβ‚‚ can generate false proof without the witness.

2.2 Proving Stage

The prover randomly picks r, s ← β„€β‚š and uses witness (aβ‚—β‚Šβ‚, aβ‚—β‚Šβ‚‚, …, aβ‚˜), statement (a₁, aβ‚‚, …, aβ‚—) and aβ‚€ = 1 to compute proof Ο€ = ([A]₁, [C]₁, [B]β‚‚).

2.3 Verification Phase

Substitute statement (a₁, aβ‚‚, …, aβ‚—) and aβ‚€ = 1 to verify that the following equation is equal.

If equal, proof Ο€ = ([A]₁, [C]₁, [B]β‚‚) is correct; otherwise, proof Ο€ is invalid.

3. The Security of Groth16

Groth16 has a qualitative leap in efficiency compared to previous proof algorithms, however, attention should be paid to security when employing it. If you are not careful, you can make vulnerabilities. The famous open source project Zokrates in its tutorial states:

The core point of this description is that an attacker can generate a new and valid proof based on an existing Groth16 proof without having to obtain the witness of the prover. But the methods to generate such a proof are not mentioned in the paper. This aroused great interest. In response, I carefully read the Groth16 thesis hoping to find some clues.

Note: Groth16 has a malleability problem, and no vulnerabilities have been found on the algorithm so far. However, when designing a system with Groth16, if you do not pay attention to the malleability problem, the system may cause a vulnerability.

4. Attack Idea

As described in the Zokrates tutorial, we can see that the proof generated by the attacker must be generated based on an existing and correct proof.

First, we can observe and verify the equation:

It seems we can come to the idea that if the attacker can construct a new proof π’ = ([A’]₁, [C’]₁, [B’]β‚‚) based on the existing proof Ο€ = ([A]₁, [C]₁, [B]β‚‚), and satisfy the following equation with π’ = ([A’]₁, [C’]₁, [B’]β‚‚)

then the attacker achieves.

From here:

Then:

Then obtain evidence. More generally, pick a random number Ξ· ← β„€β‚š, and Ξ· β‰  0, construct

You can then make the verification equation

Of course, there are other construction methods. For example, Yuguang Hu of Secbit proposed a better construction method: Select a random number x ← β„€β‚š, and x βˆ‰ {0, 1}, to make

This way is simpler, smarter and easier to understand.

Of course, you can also use there two ways together.

5. Attack Practice

It is clear in theory, but it needs to be verified by practice. To test it, we can experiment with the β€œsha256” example in the Zokrates tutorial.

In this example, the prover generates zkSNARK proof to prove that he knows the pre-image 5 of sha256 0xc6481ee2c5ff4164af680b8cfaa5e8ed3120eeff89c4f307c4a6faaae059ce10. It is suggested to try this example first, and then read on.

Note that the default proving scheme for Zokrates is Groth16 and the elliptic curve based on it is alt_bn128 (also known as bn256).

5.1 Compiler Circuit

First, use the circuit in the example directly:

import β€œhashes/sha256/512bitPacked” as sha256packeddef main(private field a, private field b, private field c, private field d) -> (field):
h = sha256packed([a, b, c, d])
h[0] == 263561599766550617289250058199814760685
h[1] == 65303172752238645975888084098459749904
return 1

Save it as hashexample.zok and compile

./zokrates compile -i hashexample.zok

The compiled circuit will be saved in the out file by default.

5.2 Setup

Next initialize the circuit,

./zokrates setup

By default, this command reads the circuit in the out file, initializes it, and writes vk to verification.key and pk to proving.key. For the verification.key, we will use the delta (Ξ΄).

The delta (Ξ΄) in verification.key generated by this initialization is:

…
vk.delta = [0x08d8de30e1b96070599f473822831a5c84675e1ae26d38df88065be710c1ae51, 0x16d8e6761d0e470349897bb92b9a29f50934f76b8208226baef2f107a1914ec4], [0x141806f6a7fc82fbb2b73b544fe06902d2fb0c0ef68531801d92c2937a6d39a3, 0x2587d44143e5ef58550d5691ae14f73ed529cc756b619e4bb10bc7ed02c993a3]
…

Note: this delta (Ξ΄) represents a point on alt_bn128 (𝔾₂). The abscissa x and ordinate y of each point on alt_bn128 (𝔾₂) are complex numbers, and each complex number has an imaginary part and a real part. Therefore, four values are required to represent such a point.

Then we can directly generate the smart contract code to verify the proof

./zokrates export-verifier

The command generates a smart contract code based on the verification.key and saves it in verifier.sol. This smart contract can be deployed directly to Ethererum.

5.3 Generating Proof

Next, we calculate the witness according to the private input

./zokrates compute-witness -a 0 0 0 5

Then, according to the witness, we generate proof

./zokrates generate-proof

The proof will be saved in the proof.json file

{
β€œproof”: {
β€œa”: [β€œ0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”, β€œ0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1”],
β€œb”: [[β€œ0x04567073d4db9932c4e6fec8c5c715bbc7d981bbd2771aba57988bedaf2654f7”, β€œ0x1fcbe2f4653402e614d7a5aee078180a6063869c139b352450184015387d0d4f”], [β€œ0x0b6f1e65d68b60e377194800473d1f06498ee37ac14d814732fd9858b1ffa102”, β€œ0x03faefb041fee3b4c82eaa96c278c55c09d5937a7101d66bd1dc9e30366e1fba”]],
β€œc”: [β€œ0x000f6a3ba957a10e387494b36da172de81e71db3fbb3cf131122439c10c3c35e”, β€œ0x1ed51ff80897f736c03ac95176e48272c3bb4573262d271aeceaaed89707c428”]
},
β€œinputs”: [β€œ0x0000000000000000000000000000000000000000000000000000000000000001”]
}

5.4 Implementation of Attack

The attack process involves replacing b and c in the above proof.json file with b + Ξ·Ξ΄ and c + Ξ·a respectively. To keep it simple, let’s set Ξ· = 1.

Note that β€œ+” here is the addition of two points on the elliptic curve, not the simple addition of numbers.

We need to write some code to complete this process.

Note: as mentioned earlier, Zokrates uses the curve of alt_bn128. We need to find the corresponding library of alt_bn128 to help us to calculate the points on the elliptic curve. The good news is that it’s in Ethereum and it’s used out of the box.

Next, write a simple program (gen-g16-proof) to calculate [B’]β‚‚ = [B + Ξ·Ξ΄]β‚‚, [C’]₁ = [C + Ξ·A]₁ according to [A]₁, [C]₁, [B]β‚‚, [Ξ΄]β‚‚:

Note: [Ξ΄]β‚‚ in the above procedure comes from the verification.key, whereas [A]₁, [B]β‚‚, [C]₁ from proof.json. Integrate them into input.json (reference format here).

Execute command:

gen-g16-proof -i input.json -o output.json

After that, new [B’]β‚‚ and [C’]₁ values can be obtained in output.json (reference format here).

Note: The reader needs to replace delta, a, b, c in the above input.json according to the value generated by his own runtime. And get the newly calculated b and c from output.json.

Replace the values of b and c in output.json with b and c in the original proof.json and save as proof2.json. See below:

{
β€œproof”: {
β€œa”: [β€œ0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”, β€œ0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1”],
β€œb”: [[β€œ0x302d34ff018f8abeea4b0ea206048a8c69c8cc8d4f7ddcc1bd613dcb539de567”, β€œ0x0927c6aac8cf8b3cf7534f06d80b791f07725ad1ee3a5246c6a6bd5533335ff4”], [β€œ0x29140540827fad8c7f4b55877678ffa1c52d4a72a49f25c83495d18e9aa1b358”, β€œ0x23533b6d3c4df0aa49924cc9462aa1e278b4c58d3037a9bc9ab4026a18fbeefb”]],
β€œc”: [β€œ0x1de4d89b61640eead90df97fe4fcf7c76509941094657406caf0ec71c83bf537”, β€œ0x26c6778ea34fb888c44ba3a4c0e53fb6b83c90c0759201efe23886a85670018c”]
},
β€œinputs”: [β€œ0x0000000000000000000000000000000000000000000000000000000000000001”]
}

Next, according to proof.json and proof2.json, the parameters of calling the smart contract are generated respectively. Here, proof2.json is constructed by the attacker based on proof.json.

$ ./zokrates print-proof -f remix -j proof.json[β€œ0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”,”0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1"],[[β€œ0x04567073d4db9932c4e6fec8c5c715bbc7d981bbd2771aba57988bedaf2654f7”,”0x1fcbe2f4653402e614d7a5aee078180a6063869c139b352450184015387d0d4f”],[β€œ0x0b6f1e65d68b60e377194800473d1f06498ee37ac14d814732fd9858b1ffa102”,”0x03faefb041fee3b4c82eaa96c278c55c09d5937a7101d66bd1dc9e30366e1fba”]],[β€œ0x000f6a3ba957a10e387494b36da172de81e71db3fbb3cf131122439c10c3c35e”,”0x1ed51ff80897f736c03ac95176e48272c3bb4573262d271aeceaaed89707c428"],[β€œ0x0000000000000000000000000000000000000000000000000000000000000001”]

$ zokrates print-proof -f remix -j proof2.json[β€œ0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”,”0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1"],[[β€œ0x302d34ff018f8abeea4b0ea206048a8c69c8cc8d4f7ddcc1bd613dcb539de567”,”0x0927c6aac8cf8b3cf7534f06d80b791f07725ad1ee3a5246c6a6bd5533335ff4"],[β€œ0x29140540827fad8c7f4b55877678ffa1c52d4a72a49f25c83495d18e9aa1b358”,”0x23533b6d3c4df0aa49924cc9462aa1e278b4c58d3037a9bc9ab4026a18fbeefb”]],[β€œ0x1de4d89b61640eead90df97fe4fcf7c76509941094657406caf0ec71c83bf537”,”0x26c6778ea34fb888c44ba3a4c0e53fb6b83c90c0759201efe23886a85670018c”],[β€œ0x0000000000000000000000000000000000000000000000000000000000000001”]

Finally, deploy the verifier.sol generated in the setup phase to the Ethereum network, and call the verifier.verifyTx() method with the parameters of the above call contract.

In the research of this article, the following results were obtained on the rinkeby network.

You can also try to modify eta (Ξ·) in the input.json or try other ways to construct a more effective proof.

6. How To Defend

There are four suggested ways to defend. We will use Zokrates once again as a reference:

  • Signed proofs

A requirement is to submit the zkSNARK proof and the prover’s signature together. In this way, even if an attacker forges a proof, the prover’s signature cannot be forged.

  • Nullifiers

Consider some or all of the public input in the proof as a nullifier. Since the above attack method cannot change the public input, the nullifier can only be used once, which can effectively prevent such attacks.

  • Usage of an Ethereum address as a public input to the program

Consider making the address (msg.sender) that submits the proof as part of the public input. However, this requires the circuit to be taken into account when designing.

  • Usage of non-malleable schemes such as GM17

The last method is to change to other proving schemes. This is obvious, but it loses the advantage of the efficiency of Groth16.

7. Summary

Groth16 is an excellent zkSNARK proving scheme as the size of the proof is smaller, and the speed of generating and verifying the proof is faster. Groth16 is a technically mature proof and has been widely used in various types of projects including Zcash and Filecoin, among others.

When a new system is designed with Groth16, it’s important to consider the possibility that an attacker may generate a new proof with a disclosed proof. Therefore the system designer should not use Groth16 straight away; instead, consideration towards specific business scenarios and potential attack models are needed before implementation. From there, appropriate measures can be taken to avoid defects and loopholes.

  1. G16 Paper On the Size of Pairing-based Non-interactive Arguments, Jens Groth.
  2. Zokrates g16 malleability
  3. Zokrates sha256 example
  4. Ethereum bn256 library
  5. gen-g16-proof