Security Considerations of zk-SNARK Parameter Multi-Party Computation

Security Considerations of zk-SNARK Parameter Multi-Party Computation
2020-06-24 21:00:22 Author: research.nccgroup.com(查看原文) 阅读量:634 收藏

Zero-knowledge proofs are cryptographic constructions allowing users to demonstrate the knowledge of some value, without disclosing the value itself. Even though they have been studied for many years, zero-knowledge proofs are seeing renewed interest in blockchain applications, mostly through the usage of Zero-Knowledge Succinct Non-Interactive Argument of Knowledge, or zk-SNARKs for short. In order to issue and verify zk-SNARKs, users need a set of public parameters, taking the form of random numbers, that have to be generated prior to execution of the protocol.

The honest computation of parameters for zk-SNARKs plays a critical role in the security of the resulting proof system. Corruption of these parameters, be it as a result of a malicious adversary or due to an implementation error, completely invalidates the security guarantee of the scheme. This blog post describes the state-of-the-art Multi-Party Computation (MPC) ceremony for the secure computation of these parameters, and then presents some important security considerations to keep in mind when auditing such implementations.

A Short Refresher on zk-SNARKS

Zk-SNARKs are arguments issued by a prover, convincing a verifier about a statement, without revealing any additional information about the statement. In addition, it has some attractive properties, such as being short and non-interactive, in the sense that there is no back and forth exchange of messages between prover and verifier. This has some very advantageous benefits; statements are proven once at a small cost and verification can be performed very efficiently. Although the applications of zk-SNARKs are (practically) limitless, they are primarily used in blockchain technologies, such as Zcash or Ethereum. To provide a concrete example of the applicability of zk-SNARKs, consider a proof of a transaction on a blockchain, where the proof describes the transfer of some funds from one address to another, without revealing the addresses themselves.

This blog post will not dive into the inner workings of zk-SNARKs. For references on the topic, the following series of articles are very good introductory sources:

In order to use zk-SNARKs, a public set of parameters, called Common Reference String (CRS), is required. But the creation of these parameters also generates some private parameters, sometimes referred to as “toxic waste”. The toxic waste has to be destroyed for the whole scheme to be secure. Indeed, if any party were to obtain possession of these private parameters, they could forge proofs. In a blockchain setting, the ability to forge proofs could result in the ability to counterfeit money, and to do so unnoticed. It is thus crucial to ensure the deletion of these secret elements.

Trusted Setup Ceremony

A straightforward way to generate the CRS is to assume the existence of a trusted third-party, which samples the necessary random numbers, computes the public parameters and then destroys the toxic waste. Assuming the existence of such an honest third-party is common in the academic literature, but more controversial in real-world deployments. Since the ability to forge proofs can be used to counterfeit significant amounts of money, it might be sufficient reason for many a third-party to no longer behave honestly.

One method to eliminate the need for a trusted third-party is to use Multi-Party Computation (MPC), where several participants contribute to the parameter generation process. With MPC, if at least one single participant generates their contribution honestly and deletes their secret counterpart of the contribution, then the resulting CRS is honest.

The state of the art in terms of multi-party computation of zk-SNARK parameters was proposed in a 2017 paper by Sean Bowe, Ariel Gabizon and Ian Miers [BGM17]. Their approach introduced a few interesting new ideas. The most notable being probably the notion of player exchangeability, where the protocol can scale to a large number of participants, which can join and exit the ceremony without hindering the parameter computation or affecting the security of the resulting CRS. Opening the ceremony to a large number of participants also reduces the probability that the resulting CRS is dishonest. Indeed, each additional contributor effectively increases the probability that at least one of them is honest (or at least has not been subverted) and will destroy their secret contribution. To achieve these goals, the ceremony is split into two distinct phases.

We describe the approach presented in the paper by following a toy example and will provide some intuitions regarding how this process is scaled up in real-world deployments. This construction has been used in practice, such as for Zcash’s Powers of Tau and Sapling multi-party computation ceremonies. As an aside, NCC Group performed a security audit of parts of the Sapling ceremony and documented it in a public report.

The zk-SNARK construction used in the MPC paper is Groth’s zk-SNARK [Groth16]. Informally, these zk-SNARKs are represented by arithmetic circuit over a large prime field, and thus the statements in the proof system can be described by polynomials, through a series of clever encoding tricks. For the curious reader, this is explained in more detail in the introductory material provided above.

Consider a group $\mathbb{G}$ of prime order $p$ (in which the discrete logarithm problem is believed to be hard) and let $g$ be a generator of that group. Now, let $P$ be the following Polynomial defined over $\mathbb{F}_p$ :

$P(x) = 3x + 1$ .

The CRS consists of the elements:

$s \cdot g \text{ and } \alpha P(s) \cdot g,$

where $s$ and $\alpha$ are random elements uniformly distributed in $\mathbb{F}_p^*$ . They are the toxic waste we described earlier and should not be known to any party.

The following section will describe how the two elements of the CRS are computed during the Trusted Setup Ceremony. The first element will be obtained at the end of Phase 1 and the second element at the end of Phase 2.

Phase 1

In this first phase, the participants are working together to compute the value $s\cdot g$ .

The first participant, Alice, generates a uniformly random element $s_1 \in \mathbb{F}_p^*$ . She then computes

$A = s_1\cdot g$

and sends it to the second participant, Bob. Using Alice’s contribution, Bob now generates a random field element $s_2$ and computes

$B = s_2\cdot A$

and sends it to the protocol coordinator, who issues that quantity as the first part of the CRS to be used by all system participants.

Assuming the secret elements were generated honestly and subsequently destroyed, the protocol described above generates an honest CRS, where no single participant (including the coordinator) knows the value of the toxic waste. This is pictured in Figure 1. below.

Figure 1. Phase 1 – 2-party honest ceremony

But what happens in our toy example if the second participant turns out to be malicious? Bob could adaptively select a contribution value based on Alice’s such that the resulting CRS is no longer honest, or even worse, completely discard Alice’s contribution. In that case, no one would be able to tell that the resulting parameters are dishonest (see Figure 2.) and Bob, knowing the toxic waste, would be able to forge proofs.

Figure 2. Phase 1 – 2-party malicious ceremony

The solution proposed in the [BGM17] paper is to introduce a random beacon, a particular source of randomness that will also contribute to the generation of the parameters, see Figure 3.

Figure 3. Phase 1 – 2-party ceremony with Random Beacon

Random beacons differ from the more commonly-known random oracles in a crucial way; the random value produced by the beacon is not available before a certain time. Several instantiations have been proposed [BGB17], such as computing repeated iterations of a hash function on data that will be publicly available at a given time. Examples include the closing stock market value at a certain date in the future, or the value of a blockchain block at a given height, not yet mined.

At the end of Phase 1, the protocol coordinator thus obtains the random value from the random beacon and finalizes the first element of the CRS. Then, the coordinator computes

$\begin{aligned} P(s) \cdot g &= (3s + 1)\cdot g\\ &= 3(s\cdot g) + g, \end{aligned}$

where the quantity $s\cdot g$ is the value just computed as a result of Phase 1. Note that this quantity can be computed without the knowledge of the toxic waste $s$ .

To finalize Phase 1, the protocol coordinator now published the value $P(s)\cdot g$ for participants to be used in Phase 2.

Note that the protocol coordinator does not perform any secret operation, all it does is multiply the resulting contribution from the participants with the random element generated by the beacon. The computation it performs are public and can be verified by all participants. The coordinator merely serves as a central point of computation and distribution of the parameters. In a real-world deployment, one can also imagine that all participants publish their contributions to a public location, accessible to all, diverging from the “pass the baton” approach pictured in the figures. As a practical example, participants in the Zcash Powers of Tau ceremony uploaded their contributions to publicly accessible servers and used GitHub to record the links to access them.

Intermission: developing intuition

Now, what if the statement in our proof system was more complex; namely, what if the polynomial for which we created the parameters was not linear but quadratic. For instance, consider the degree 2 polynomial defined as $P(x) = 5x^2 + 3x + 1$ ? In that case, at the end of the first phase, the protocol coordinator would have to compute

$\begin{aligned} P(s) \cdot g &= (5s^2 + 3s + 1)\cdot g \\ &= 5(s^2\cdot g) + 3(s\cdot g) + g. \end{aligned}$

In order to do so, the quantities $(s\cdot g, s^2\cdot g)$ are now required by the protocol coordinator.

Thus, in the first phase of the protocol, instead of only computing and sending $s_1\cdot g$ , Alice also computes $s_1^2\cdot g$ and sends the two following quantities as her contribution:

$(s_1\cdot g, s_1^2\cdot g) = (A_1, A_2).$

In its turn, Bob now samples the random field element, computes

$(s_2\cdot A_1, s_2^2\cdot A_2) = (B_1, B_2)$ ,

and forwards these values to the coordinator, who will follow the same procedure with the random beacon’s contribution.

Note that this introduces some potential attacks, in which a malicious Bob could send a contribution value for $B_2$ that is not the square of the random number he sampled. This would go unnoticed, since the value of $s_2$ is not disclosed. While such an attack cannot be prevented, it can be detected using cryptographic pairings, which constitute an important aspect of the whole trusted setup ceremony protocol.

From this simple enhancement of our example, we can see how increasing the degree of the polynomial requires the computation of additional values. More specifically, we see that for a degree d polynomial, we would need d such quantities. Typical ceremonies use much higher degree polynomials.

We also see how the ceremony can scale up to more than two participants; each additional participant simply taking a turn in the ceremony, sampling a random secret element and contributing to the set of parameters.

This is one of the reasons why Phase 1 is computationally expensive and requires large amounts of data to be sent among the different participants. In practice, round computations can take several hours on modern machines and require to download and subsequently upload dozens of gigabytes of data. However, the same reasoning also explains why Phase 1 is statement-agnostic, it does not depend on the polynomial itself. Once all the required $s^i\cdot g$ quantities are securely generated, any polynomial can be evaluated and Phase 2 can thus be repeated for any new statement required for the zk-SNARK.

Phase 2

In this second phase, the participants work together to compute the value $\alpha P(s)\cdot g.$ Conceptually, Phase 2 follows exactly the same procedure as Phase 1; Alice generates a random contribution and computes $A = \alpha_1P(s)\cdot g$ , sends this value to Bob, who generates his random contribution $B = \alpha_2\cdot A$ . The result is then sent to the protocol coordinator who incorporates the value from the random beacon and then broadcasts the resulting second component of the CRS:

$\alpha P(s)\cdot g.$

Figure 4. Phase 2 – trusted setup ceremony

At this stage, the CRS has been successfully computed and it can be used by all participants for issuing and verifying sk-SNARKs.

In a real-world scenario, the CRS has many more components, as alluded to in the intermission above. Additionally, several steps are taken to validate the correctness of the different contributions. In the next section, we discuss some important security considerations of real-world implementations.

Security Considerations

In addition to the common security pitfalls one might look for in any cryptographic protocol, several areas require particular attention when auditing implementations of trusted setup ceremonies. In the following section, we discuss some of these security considerations.

1. Secure deletion of the parameters

The security of the multi-party computation ceremony relies entirely on the fact that at least one participant needs to securely delete their contribution for the resulting parameters to be generated honestly. Therefore, secure deletion of the secret contributions is a critical operation in any MPC implementation. An often-overlooked fact is that when functions go out of scope, the variables used within that function are not explicitly deleted and remain in the process memory, which is then returned to the memory pool. Thus, an attacker might be able to extract sensitive information directly from the memory.

However, erasing the secret parameters (sometimes referred to as memory zeroization) is a non-trivial task in software. In some instances, compilers have been known to optimize out explicit calls to erase the memory content, after seeing that the corresponding variables were not used in the remaining of the program. Some languages provide explicit constructions to zeroize the memory, such as the crate zeroize for the Rust programming language.

2. Adequate randomness

Generating good random numbers is paramount to the security of most cryptographic protocols. This is especially true for the CRS generation, where, even if all participants were behaving honestly, a flaw in the random number generation would render the whole computation worthless. A standard cryptographically secure pseudorandom number generator (CSPRNG) should be used, and it should be seeded with enough entropy to support the security needs of the parameters. It is also strongly recommended to aggressively detect errors and warnings that might be triggered as results of calls to the random number generator, such as when not enough entropy is available on the system.

An additional consideration related to randomness concerns the instantiation of the random beacon. The proof of security of the system relies on it as a source of randomness, with certain specific properties. Namely, that it should not be available before a certain time in the future, and that the random contribution it generates should be publicly available and verifiable. This significantly reduces the chance of a malicious adversary being able to compute the random beacon contribution ahead of time. Several constructions have been proposed in the academic literature [BGB17], for example using repeated calls to a hash function using high entropy public data as input, such as the value of the stock market on a set date in the future, or the result of several national lotteries around the world. As an example, during the Zcash Sapling trusted setup ceremony, a Bitcoin block height was selected in advance, and 2⁴² iterations of SHA256 over the block hash of that block were performed to obtain the random beacon contribution.

3. Well-defined process

Multi-party computation is a complex use-case where the lines between the different participating entities and their respective responsibilities might be blurry. It is thus important to have a well-defined process and established roles. For example, in the case of the trusted setup ceremony described above, every participating entity should know who will perform the roles of the coordinator, and how the random beacon contribution will be computed. Additionally, participants should be strongly encouraged, if not enforced, to verify all the transactions and validate all the parameters generated thus far. A separate entity, the protocol verifier, could also be identified, whose sole role would be to verify the integrity of the operations performed during the whole trusted setup ceremony. In real-world systems, a third-party auditing firm is sometimes mandated to verify and maintain records of trusted setup ceremonies.

4. Secure implementation

Lastly, an important consideration is the security and correctness of the source code implementing the trusted setup ceremony. The operations performed are complex and involve a wide variety of mathematical and cryptographic primitives. The source code should be implemented, scrutinized and tested carefully. Special emphasis should be placed on the security assumptions stated in the literature and how they are enforced in practice. Additionally, standard best programming practices should be followed, including proper error handling and usage of up-to-date underlying libraries. In a setting where participants compute on data generated by potentially malicious actors, the validation of all inputs is also critical.

A good practice to mitigate the risk of bugs in one specific implementation and to increase the trust in the parameters generated is to encourage participants to use alternative implementations and environments to perform the ceremony. This includes running independent implementations of the MPC ceremony, written in different programming languages for example. Alternatively, running the same code but on different architectures also provides additional assurance with respect to the final parameters. Some interesting real-world examples are detailed in a blog post released after the completion of the Zcash ceremony.

Example Implementation

After the success of the Zcash trusted ceremony, several implementations have sprouted as forks from the original Zcash code (Powers of Tau and Phase 2). A worthwhile example is the Trusted Setup Ceremony by Computer Systems Worldwide (CSW) publicly available at https://github.com/kobigurk/phase2-bn254. In a recent engagement, NCC Group Cryptography Services reviewed this implementation for the security considerations discussed above. As of the review completed in May 2020, the implementation followed the cryptography best practices described earlier. This implementation provides some interesting additions to the original Zcash code, including WebAssembly bindings, allowing participants to run parts of the ceremony in browser-based applications. This makes it easier for less tech-oriented participants to take part in the ceremony and will certainly help in broadening adoption and increase the number of potential participants in MPC ceremonies. As a concrete example, the tornado.cash project used those WebAssembly bindings for their MPC ceremony and got a record-breaking amount of contributions, significantly more than similar ceremonies in the past.

Conclusion

The secure generation of parameters for zk-SNARKs is a crucial step in the trustworthiness of the resulting proof system. By highlighting some potential pitfalls and important security considerations of these implementations, NCC Group hopes to provide helpful pointers to all implementers and avoid the introduction of vulnerabilities detrimental to the confidence users have in the different applications of these systems.

References

[BGM17] Sean Bowe and Ariel Gabizon and Ian Miers. 2017. “Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model” https://eprint.iacr.org/2017/1050

[Groth16] Jens Groth. 2016. “On the Size of Pairing-based Non-interactive Arguments” https://eprint.iacr.org/2016/260

[BGB17] Benedikt Bunz, Steven Goldfeder, and Joseph Bonneau. 2017. “Proofs-of-delay and randomness beacons in Ethereum”.

文章来源: https://research.nccgroup.com/2020/06/24/security-considerations-of-zk-snark-parameter-multi-party-computation/
如有侵权请联系:admin#unsafe.sh