How to Generate a Groth16 Proof for Forgery

We explore how an attacker can generate a new and valid proof based on an existing Groth16 proof without having to obtain the witness of the prover.

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 sha256packed
def 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.

• verifier contract: 0x46d6b34c…
• proof.json: 0x728ddfc2…
• proof2.json: 0x91f65d9d…

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