# On the weak simulation extractability of Groth16 arguments

###### tags: `weak simulation extractability, weak-SE, proof non-malleability, transaction non-malleability, UC security, OpenZeppelin`

> This note summarises the main results from https://eprint.iacr.org/2020/811 while adding some more background.

### Introduction
It is a known fact that Groth16 arguments that pass verification can be re-randomised, and hence they are malleable. It was however not explored before how malleable Groth16 arguments are.

### Background
In order to understand why non-malleability may be of interest, we need to see the bigger picture. Why do we care about non-malleability and what are some types of non-malleability that we would be interested in relation to the security of a blockchain? We give some intuition and examples below. If intuition regarding such notions is clear, one can safely skip this section and move on to the next one.

To start with, ***the non-malleability of a blockchain transaction*** is a necessary security notion that needs to be fulfilled by the underlying blockchain aiming to implement decentralized anonymous payment schemes. The necessity of transaction non-malleability and various ways to achieve it for transactions that also contain (zk)SNARK arguments are discussed, for example, in [Zerocash](https://eprint.iacr.org/2014/349), [ZETH](https://arxiv.org/abs/1904.00905) and [Zcash](https://github.com/zcash/zips/blob/master/protocol/protocol.pdf) as follows. 

* In [Zerocash](https://eprint.iacr.org/2014/349), the intuition for the necessity of transaction non-malleability is motivated in section 1.3, step 6 (the entire section 1.3 is worth reading by anyone looking to understand why transactions are designed the way they are in Zcash and Zerocash); the details of how this is designed using cryptographic primitives such as signatures are given in section 4.2 and Figure 2, and the more in depth definitions and related security proofs are given in appendix C and appndix D.

* In [ZETH](https://arxiv.org/abs/1904.00905) (this is a relative of Zerocash/Zcash optimised for use on Ethereum), section 3.4, page 14, there is the list of components of a transaction tx_Mix; notice the lack of signatures! Appendix B.2 gives the definition of transaction non-malleability and a security proof that transaction non-malleability is ensured if the skSNARKs arguments are non-malleable (a property that follows from simulation extractability of zkSNARKs such as GM17) and one also uses strong encryption schemes (IND-CCA2 secure). Related explanations, even though technical, are easy to follow.   

* In [Zcash](https://github.com/zcash/zips/blob/master/protocol/protocol.pdf), malleability attacks are prevented using details described in sections 4.10, 4.12 and 4.13; the details are however technical/more involved. 

(ZK) ***argument non-malleability*** is an important and related security notion to transaction non-malleability. Indeed, one way to ensure that a blockchain transaction is non-malleable, given that the transaction has to contain a (zk) SNARK is by using simulation extractable arguments (which, in turn, implies, non-malleable arguments). As we are going to clarify in the rest of this note, weak simulation extractabilible arguments as defined in [this paper](https://eprint.iacr.org/2020/811.pdf) are not sufficient for our purpose. For more details, see also the example above for the use of simulation extractable SNARKs in [ZETH](https://arxiv.org/abs/1904.00905). 

### Main results of [the paper](https://eprint.iacr.org/2020/811.pdf)

[The paper we are analysing](https://eprint.iacr.org/2020/811.pdf)  presents in theorem 3.2 sufficient and, as far as I can tell, also necessary conditions for a QAP circuit ensuring that all arguments that pass its respective verification have the following properties:
- Case 1: they are arguments of statements (i.e., public inputs) for which the prover have not seen arguments before, and in that case even a malicious prover could not have created those arguments without knowing the correct witness for the fresh statements OR 
- Case 2: they are re-redomised arguments for a statement for which the prover has seen at least an argument before; note that in this case the prover may have seen an honestly generated argument so a witness exists even though the prover may not know it; or, the prover may have seen a simulated argument that was created with a trapdoor, and, in that case, there is no guarantee that a witness even exists.

All in all, only in Case 1, when there was no argument so far for a given statement there is a guarantee the prover knows a witness for the argument he just generated; while in case 2 of a statement for which an argument was produced before (by another party, for example), all we can say with certainty (due to theorem 3.2 and corollary 3.2.2) is that the new argument is a randomisation of the old argument but the prover may not know the witness or a witness may not even exist! 

An interesting fact is that given the conditions described in theorem 3.2, one cannot combine two or more different previously seen arguments even if they are for the same statement/public input, to create a new argument (even for the same statement). Only at most one old argument can be randomised to obtain a new argument (for the same statement, of course). In fact, under the conditions mentioned in theorem 3.2, the most general transformation (of any kind) that a prover can do using old arguments that pass verification to create new arguments that pass verification is to randomize them with the general randomisation procedure described in equation 2, page 6. And due to the fact that this general transformation is in fact just a randomisation, the statement/public input of the old and new arguments are the same. Moreover, the randomisation procedure described in equation 2, page 6 can be used for randomising both honestly generated arguments and simulated arguments. 

The Cases 1 and 2 above cover the intuition behind the notion of weak-SE (or weak simulation extractable) as defined by the authors. In terms of malleability, this means that any plain Groth16 argument can be malleable (since any old argument that passes verification, whether it is the result of a simulation or an honest argument generation process, can be randomised), but a statement cannot be malleable (a malicious prover cannot modify old arguments into new arguments for statements/public inputs for which he has not seen an argument before). 

### Final notes
- The authors of [the paper we are analysing](https://eprint.iacr.org/2020/811.pdf) talk about transforming Groth16 into an UC secure building block for use in other protocols. My understanding is that the aim for such a transformantion is to obtain UC security in the most efficient way possible, not necessarily to eliminate the intrinsic malleability issues of Groth16. They propose a two step approach for achieving UC security: first step, lift the non-blackbox weak simulation extractable NIZK to a blackbox weak simulation extractable NIZK using a technique detailed [here](https://eprint.iacr.org/2019/480.pdf) and, second step, they support the claim (which was made before, but without proof [here](https://eprint.iacr.org/2015/1093.pdf) and [here](https://eprint.iacr.org/2015/1093/20151111:062221) that a blackbox weak simulation extractable NIZK implies UC security. The authors claim the weak simulation extractability definition is inspired from [here](https://eprint.iacr.org/2015/1093/20151111:062221).

- Regarding the two conditions necessary for theorem 3.2 to hold, the notation can be confusing. When the authors mention $w_i(x)$, they do not mean the evaluation of those polynomials at the trapdoor $x$ but rather the actual polynomials $w_i(X)$ with indeterminate $X$. Note that the linear independence and $0$ span intersection restrictions should apply only to the polynomials related to the output wires of the QAP circuit. Moreover, a similar condition has been demonstrated to be necessary and sufficient in a different zkSNARK related context: [the updated version of the BCTV14 protocol](https://eprint.iacr.org/2019/119.pdf) (for which, its previous version, without the condition had a major security issue related to knowledge soundness).