The reverse side of zero knowledge: backdoor in zk-SNARK, which can not be detected
Using the proof protocol with zero disclosure from the SNARK family, you never know the rules of the game. These rules are set by participants in the procedure for generating trusted system parameters, but after it is completed, it is not possible to verify these rules. You can believe in the correctness of the generation, but if you did not participate in it, you do not have one hundred percent guarantee.
Recently, various zero knowledge protocols have been increasingly mentioned in the blockchain community (to get a general idea of them, I recommend this article ): primarily in the context of privacy, less often in the context of scalability and others.
One of the most studied, and what is more important - implemented is the family of protocols zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge). This protocol is used, in particular, in Zcash cryptocurrency. The popularity of SNARK is justified: the protocol allows us to prove the facts with zero disclosure, the evidence is relatively small, and all this with the security guarantees that modern cryptography on elliptic curves gives us.
')
However, as usual, it was not without drawbacks: the main disadvantage of this family of zk-protocols is the need to generate initial (trusted) system parameters — this process is also called a ceremony. After all, to generate used to be destroyed secret parameters - they are called toxic. The main problem lies in the fact that in the case of preservation of toxic parameters, owning them will be able to prove false facts (in the case of Zcash - to generate cryptocurrency from the air).
Further, the mathematics underlying the SNARK protocols will be only superficially affected. If you are interested in understanding it, I advise you a series of articles from Vitalik Buterin on this topic.
Let's look at the process of generating trusted parameters. So, we have a problem statement, the solution of which we want to prove with zero disclosure. For example, we want to test knowledge of the root of a quadratic equation:
According to the protocol, we must bring this equation to the QAP (Quadratic Arithmetic Programs) form. Further, to generate and verify evidence, it is necessary to obtain the initial parameters. Let's leave out of brackets the way trusted parameters are obtained from QAP, what these parameters are and how exactly they can be used to verify evidence in order not to go deep into hard mathematics. We only note that the parameters are represented as points on an elliptic curve:
They are obtained from the formulation of the problem in the form of QAP using an irreversible multiplication operation on an elliptic curve using toxic parameters.
Now that the initial parameters have been created, we can start working with the evidence. In our case, we can generate and check the proof that the root of the equation is known (for example, ). At the same time, the evidence will not reveal the secret value (the root of the equation) and will consist of several points of the elliptic curve.
However, by virtue of the mathematics underlying the protocol, if toxic parameters were preserved by someone after the ceremony, that person would be able to prove false facts. Returning to our example, we can prove that 2 is the root of the equation, although this is obviously not the case.
Serious projects that use the SNARK protocols are well aware of the existence of the problem of toxic parameters and are very serious about the correctness of the procedure for generating initial parameters. The most famous example is the Zcash ceremony .
The first ceremony was held in October 2016, it was attended by 6 famous developers from the cryptocurrency community. The ceremony protocol provides sufficient security guarantees. Namely, if at least one of the participants of the ceremony will be honest - correctly destroy their part of the toxic parameters - and will not be hacked, then the ceremony will be safe.
The second , more perfect ceremony of generating trusted parameters took place in 2017-2018. It already consisted of two stages, in the first part (Powers of Tau) 87 people took part, and in the final part (Sapling MPC) more than 90 people. As in the case of the original ceremony, with 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, everyone had a chance to get one hundred percent guarantee of the protocol's correctness.
In conclusion, it is worth noting that the criticality of the ceremony and the threats arising from it should be considered separately for each particular system. And at the same time, for all systems using SNARK protocols, a reliable procedure for generating initial parameters with guarantees for the destruction of toxic parameters is necessary.
Recently, various zero knowledge protocols have been increasingly mentioned in the blockchain community (to get a general idea of them, I recommend this article ): primarily in the context of privacy, less often in the context of scalability and others.
One of the most studied, and what is more important - implemented is the family of protocols zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge). This protocol is used, in particular, in Zcash cryptocurrency. The popularity of SNARK is justified: the protocol allows us to prove the facts with zero disclosure, the evidence is relatively small, and all this with the security guarantees that modern cryptography on elliptic curves gives us.
')
However, as usual, it was not without drawbacks: the main disadvantage of this family of zk-protocols is the need to generate initial (trusted) system parameters — this process is also called a ceremony. After all, to generate used to be destroyed secret parameters - they are called toxic. The main problem lies in the fact that in the case of preservation of toxic parameters, owning them will be able to prove false facts (in the case of Zcash - to generate cryptocurrency from the air).
Initial parameter generation
Further, the mathematics underlying the SNARK protocols will be only superficially affected. If you are interested in understanding it, I advise you a series of articles from Vitalik Buterin on this topic.
Let's look at the process of generating trusted parameters. So, we have a problem statement, the solution of which we want to prove with zero disclosure. For example, we want to test knowledge of the root of a quadratic equation:
According to the protocol, we must bring this equation to the QAP (Quadratic Arithmetic Programs) form. Further, to generate and verify evidence, it is necessary to obtain the initial parameters. Let's leave out of brackets the way trusted parameters are obtained from QAP, what these parameters are and how exactly they can be used to verify evidence in order not to go deep into hard mathematics. We only note that the parameters are represented as points on an elliptic curve:
They are obtained from the formulation of the problem in the form of QAP using an irreversible multiplication operation on an elliptic curve using toxic parameters.
Now that the initial parameters have been created, we can start working with the evidence. In our case, we can generate and check the proof that the root of the equation is known (for example, ). At the same time, the evidence will not reveal the secret value (the root of the equation) and will consist of several points of the elliptic curve.
However, by virtue of the mathematics underlying the protocol, if toxic parameters were preserved by someone after the ceremony, that person would be able to prove false facts. Returning to our example, we can prove that 2 is the root of the equation, although this is obviously not the case.
Ceremony
Serious projects that use the SNARK protocols are well aware of the existence of the problem of toxic parameters and are very serious about the correctness of the procedure for generating initial parameters. The most famous example is the Zcash ceremony .
The first ceremony was held in October 2016, it was attended by 6 famous developers from the cryptocurrency community. The ceremony protocol provides sufficient security guarantees. Namely, if at least one of the participants of the ceremony will be honest - correctly destroy their part of the toxic parameters - and will not be hacked, then the ceremony will be safe.
The second , more perfect ceremony of generating trusted parameters took place in 2017-2018. It already consisted of two stages, in the first part (Powers of Tau) 87 people took part, and in the final part (Sapling MPC) more than 90 people. As in the case of the original ceremony, with 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, everyone had a chance to get one hundred percent guarantee of the protocol's correctness.
In conclusion, it is worth noting that the criticality of the ceremony and the threats arising from it should be considered separately for each particular system. And at the same time, for all systems using SNARK protocols, a reliable procedure for generating initial parameters with guarantees for the destruction of toxic parameters is necessary.
Source: https://habr.com/ru/post/434720/
All Articles