On the Malleability of Groth16 Proofs

Move on Sui lets users efficiently verify any non-deterministic polynomial time (NP) statement using Groth16, an efficient and widely used Zero-Knowledge Succinct Non-interactive Argument of Knowledge (Zk-SNARKs), a useful kind of zero-knowledge proof system.

Zero-knowledge proofs are a key cryptographic method for enhancing privacy and security on a blockchain. They allow one party (the “prover”) to prove that a statement is true to another party (the “verifier”) without revealing any confidential details. For example, a prover can prove they know the solution to a puzzle without revealing the solution.

Groth16 satisfies the classical non-interactive zero knowledge (NIZK) properties of correctness, soundness, and zero-knowledge. In addition, it satisfies the stronger property of knowledge-soundness, which roughly says that a party producing a verifying proof actually knows a valid solution. However, when using Groth16 to instantiate a NIZK as part of a bigger application, developers need to make sure the properties required of that NIZK are provided by the original Groth16 system. There are several additional properties of NIZKs that applications may require, including simulation-soundness, true-simulation-soundness, subversion resistance, and simulation-extractability. It is well documented in the literature that Groth16, by itself, does not satisfy many of these properties. But when Groth16 is used as a ZK argument of membership, the absence of these properties does not interfere with the intended security or privacy properties of the system.

Groth16 proofs are re-randomizable, enabling the public generation of a fresh proof of a statement. In other words, the proof sent by the prover can be scrambled to look completely different although it remains a valid proof of the same statement. In fact, re-randomizability has been used as a feature in some applications. However, application developers need to carefully understand this property in order to prevent double-spending attacks in certain scenarios. In particular, it should be recognized in the application layer to regard two different proofs on the same statement to correspond to the same spending action.

As an analogy for this property, suppose Alice and Bob share a codebook named Caesar Codebook where A is K, B is D, C is M, and so on to communicate secret messages. Alice encrypts the message “Hello” to become IFOOR. Eve, who is observing the secret transmission, can further scramble the message, for example by shifting all the letters by 5. The new message becomes (NKTTW, 5). Bob can still decrypt this message by first reverse shifting by 5 and then applying the codebook in reverse. The key observation is that Alice and Bob’s communication still remained confidential to them, but at the same time, Eve is able to scramble the message to appear completely different. The same analogy applies to Groth16 NIZKs, where we have proof instead of encryption, secret witness instead of secret plaintext, and verifiability instead of decryption.

In many applications, Groth16 is used to provide Zero Knowledge Proof of Knowledge (ZKPoK) of signatures. In such applications, it is important to be aware that Groth16 doesn’t provide a property called Simulation Extractability. The intuition behind this property is as follows: let’s say there are two Sudoku Puzzles, designated SP1 and a related puzzle SP2, both of which have solutions. An honest party posts a proof, pi, that they know solves SP1. Can an attacker, without knowing a complete solution to SP2, produce a proof, pi’, claiming to solve SP2? Notice that, as both puzzles do have solutions, such an attacker will not be violating the classic soundness property of the NIZK.

It turns out that it is enough to satisfy a weaker simulation-extractability property for securely instantiating most of these applications. Fortunately, Groth16 satisfies this weaker notion provided some technical notions are met. Andrija Novakovic and Kobi Gurkan describe a simple way to modify the prover so that the proofs satisfy all these technical conditions. The snarkjs and arkworks libraries already incorporate these modifications, making deployments using these libraries immune from these specific attacks.

In particular, these technical conditions are imposed on representations of the program that is only used by the prover, namely the Quadratic Arithmetic Program (QAP) and Rank-1 Constraint System (R1CS). The Groth16 verifier does not need those as inputs, so these requirements are likely better discharged at the prover side than the verifier. In addition, not all applications require these extra properties. As such there is unlikely to be any modification on the Move side to accommodate the assurance of these stronger properties, and instead encourage developers to incorporate application appropriate safeguards.