The Dark Side of Zero Knowledge: Undetectable Backdoor in zk-SNARK
When using a zero-knowledge proof protocol from the SNARK family, you never know the rules of the game. The rules are set by the participants of the procedure of system trusted parameters generation (“ceremony”), but after its completion it is impossible to check these rules. You can believe in correctness of the generation, but if you have not participated in it, you don’t have hundred percent guarantee.
In recent years, various zero knowledge protocols are increasingly mentioned in the blockchain community (to get a general understanding I recommend this article): first of all in the context of privacy, more rarely in the context of scalability and others.
One of the most studied, and most importantly — implemented is zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) protocol family. In particular, such protocol is used in Zcash cryptocurrency. SNARK popularity is justified: the protocol allows to prove zero-knowledge facts, proof is relatively small, and security is guaranteed by modern elliptic-curve cryptography.
However, there are some tradeoffs. The main disadvantage of this family of zk-protocols is the need to generate initial (trusted) system parameters. This process is also called ceremony. There are secret parameters that are used for ceremony and after that must be destroyed — they are called toxic. The problem is that in case toxic parameters are not destroyed the owner will be able to prove false facts (in the case of Zcash — to generate cryptocurrency out of thin air).
Trusted setup generation
Further, the mathematics underlying SNARK protocols will be only superficially considered. If you want to understand it, I recommend a series of articles by Vitalik Buterin.
Let’s take a look at the process of trusted parameters generation. We have a statement of the problem, the fact of the solution of which we want to prove with zero disclosure. For example, we want to check the knowledge of the root of a square equation:
x^2–6x+5 = 0
According to the protocol, we should convert this equation to the QAP (Quadratic Arithmetic Programs) form. Further for proof generation and verification it is necessary to obtain the trusted parameters. Let’s leave out the brackets how QAP produces trusted parameters, what these parameters are, and how they can be used to check the proof, so as not to delve into complicated mathematics. Note only that the parameters are represented as points on an elliptic curve:
They are obtained from the problem formulation in the QAP form by means of an irreversible operation of multiplication on an elliptic curve using toxic parameters.
Now that the trusted parameters are created, we can work with the proofs. In our case, we can generate and check the proof that the root of the equation is known (for example, x = 1). Moreover, the proof will not reveal the value of the secret (the root of the equation) and will consist of several points on the elliptic curve.
However, by virtue of the mathematics underlying the protocol, if someone has retained toxic parameters after the ceremony, that person will be able to prove false facts. Going back to our example, we will be able to prove that 2 is the root of the equation, although this is obviously not true.
Ceremony
Major projects that use SNARK protocols are perfectly aware of the existence of the toxic parameters problem and take the correctness of initial parameters generation seriously. The most famous example is Zcash ceremony.
The first ceremony happened in October 2016. It was attended by 6 well-known developers from the cryptocurrency community. The protocol of the ceremony provides sufficient security guarantees. Namely, if at least one participant of the ceremony is honest (i.e. correctly destroys their part of the toxic parameters) and will not be hacked, the ceremony will be safe.
Second, a more perfect ceremony for generating the trusted parameters happened in 2017–2018. It consisted of two stages, the first part (Powers of Tau) was attended by 87 people, and the final part (Sapling MPC) was attended by more than 90 people. As in the case of the original ceremony, with the honesty of at least one participant the ceremony can be considered safe. An important feature of the second ceremony was that anyone could become a participant. Thus, anyone had a chance to receive solid guarantees of the protocol correctness.
In conclusion it is important to notice that the criticality of the ceremony and the resulting threats should be considered separately for each system. At the same time, a reliable procedure for generating trusted parameters with guarantees of the destruction of toxic parameters is needed for all systems using SNARK protocols.
This article was performed by SmartDec, a security team specialized in static code analysis, decompilation and secure development.
Feel free to use SmartCheck, our smart contract security tool for Solidity language, and follow us on Medium. We are also available for smart contract development and auditing work.
