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.

Two problems of zk-SNARK

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

But only few people remember the second, equally important problem. It also appears due to the need to generate trusted parameters, but has a different nature and consequences. It is the problem of “masking” the initial task. In this article I will shed some light on this unfairly unnoticed problem of SNARK protocols.

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.

The second danger is that it is possible to create a backdoor in the formulation of the problem. Specifically, it is possible get the initial parameters from the equation:

(x^2–6x+5)(x-13) = 0

In this case, all honest participants will play by the rules: they will solve the equation (x^2–6x + 5) = 0. The attacker, on the other hand, will use a backdoor — the root of the polynomial (x – 13), and no one will even know about it. The reason for this is that after the ceremony the system operates only with public (trusted) parameters, which are obtained by an irreversible multiplication operation on an elliptic curve. Therefore, without the publication of toxic parameters it is impossible to verify the authenticity of the problem for which the proof is generated.

This kind of backdoor opens up countless possibilities for the participants of the ceremony to manipulate systems that use zk-SNARK protocols. For example, let’s consider a system that operates accounts of users with different rights (in cryptocurrencies, an account is a public key, and only the owner of the corresponding private key can manage funds on this account). Let the system be private and the fact of ownership of the account (possession of a private key in the case of cryptocurrency) be proved using zk-SNARK protocol. Then the problem should be formulated as follows:

“Account Y can be accessed by anyone who provides the corresponding private key X”.

However, if during the generation of trusted parameters it is formulated as follows:

“Account Y can be accessed by anyone who provides the corresponding private key X or number 13”.

then the participants of the ceremony who know the secret number 13 will be able to access the account of any user (access funds if this is a cryptocurrency).

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 authenticity of the initial problem and the destruction of toxic parameters is needed for all systems using SNARK protocols.

This article was performed bySmartDec, 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, andfollow us on Medium. We are also available for smart contract development and auditing work .