# 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.

** G**roth

**is a zero-knowledge proof protocol proposed by Daniel Jens**

**16****roth in the paper βOn the Size of Pairing-based Non-interactive Argumentsβ published in 20**

**G****.**

**16**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

**ennaro, Craig**

**G****entry, Bryan**

**G****arno, Mariana**

**P****aykova in 2013 in the paper βQuadratic Span Programs and Succinct NIZKs without PCPsβ.**

**R**# 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** *

which satisfies the following equation with public *(aβββ, aβββ, β¦, aβ)*

and *statement (aβ, aβ, β¦, aβ)**aβ = 1**.*

in the above equation is related to the specific problem to be proved and is not related to the secret *uα΅’(X),vα΅’(X),wα΅’(X),h(X),t(X)*

held by the prover and the public *witness *

.*statement*

## 2.1 Setup Phase

In the setup phase, pick

, define *Ξ±, Ξ², Ξ³, Ξ΄, x β β€β**

, and compute *Ο = (Ξ±, Ξ², Ξ³, Ξ΄, x)**Ο=([Οβ]β, [Οβ]β)** ,* 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

and uses * r, s* β β€β

`witness `*(aβββ, aβββ, β¦, aβ)*

, `statement `*(aβ, aβ, β¦, aβ)*

and *aβ = 1*

to compute proof *Ο = ([A]β, [C]β, [B]β)*

.## 2.3 Verification Phase

Substitute `statement `

and *(aβ, aβ, β¦, aβ)*

to verify that the following equation is equal.*aβ = 1*

If equal, proof

is correct; otherwise, proof *Ο = ([A]β, [C]β, [B]β)*

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

, constructYou can then make the verification equation

Of course, there are other construction methods. For example, ** Yuguang Hu** of

**proposed a better construction method: Select a random number**

**Secbit***x* β β€β

, and *x* β {0, 1}

, to makeThis 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

**tutorial.**

**Zokrates**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

*and pk to*

*verification.key**. For the verification.key, we will use the delta (*

*proving.key**Ξ΄*

).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

*. This smart contract can be deployed directly to Ethererum.*

*verifier.sol*## 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

*in the above proof.json file with*

*c**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

**. 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.**

**alt_bn128**Next, write a simple program (gen-g16-proof) to calculate

, *[Bβ]β = [B + Ξ·Ξ΄]β*

according to *[Cβ]β = [C + Ξ·A]β**[A]β**, **[C]β**, **[B]β**, *

:*[Ξ΄]β*

** Note**:

*[Ξ΄]β*

in the above procedure comes from the verification.key, whereas *[A]β*

*,**[B]β*

*,**[C]β*

from *. Integrate them into*

*proof.json**(reference format here).*

*input.json*Execute command:

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

After that, new

and *[Bβ]β*

values can be obtained in *[Cβ]β** output.json* (reference format here).

Note: The reader needs to replace *delta**, **a**, **b**, *

in the above *c** 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 *with*

*output.json**b*

and *c*

in the original *and save as*

*proof.json**. See below:*

*proof2.json*`{`

βproofβ: {

βaβ: [β0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035β, β0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1β],

βbβ: [[β0x302d34ff018f8abeea4b0ea206048a8c69c8cc8d4f7ddcc1bd613dcb539de567β, β0x0927c6aac8cf8b3cf7534f06d80b791f07725ad1ee3a5246c6a6bd5533335ff4β], [β0x29140540827fad8c7f4b55877678ffa1c52d4a72a49f25c83495d18e9aa1b358β, β0x23533b6d3c4df0aa49924cc9462aa1e278b4c58d3037a9bc9ab4026a18fbeefbβ]],

βcβ: [β0x1de4d89b61640eead90df97fe4fcf7c76509941094657406caf0ec71c83bf537β, β0x26c6778ea34fb888c44ba3a4c0e53fb6b83c90c0759201efe23886a85670018cβ]

},

βinputsβ: [β0x0000000000000000000000000000000000000000000000000000000000000001β]

}

Next, according to * proof.json* and

*, the parameters of calling the smart contract are generated respectively. Here,*

*proof2.json**is constructed by the attacker based on*

*proof2.json**.*

*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

*method with the parameters of the above call contract.*

*verifier.verifyTx()*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

*or try other ways*

*input.json**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.

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