Zero-knowledge proof

Zero-knowledge simple non-interactive argument (zk-snark), usually called zero- knowledge proof, is another effective technology to provide transaction privacy. Specifically, zk-snark allows the prover to provide a short proof to prove that he knows a secret without revealing the fact of the secret. The cryptocurrency Zcash, which is considered to provide a very high level of privacy protection, is the first successful application of zk-snark.

However, the current zk-snarks technology still has many limitations. Therefore, zcash using zk-snark has the following problems. Although zk-snark is efficient in terms of The New Standard of Value, Helicon Foundation 2018 is inefficient in terms of prover's computation and parameter size. Specifically, the public parameter in Zcash is about 1 GB, even a powerful computer, it still takes a few minutes to generate a proof. The high requirements for computing power and memory make it very difficult for Zcash to implement a secure independent mobile wallet.

As mobile devices have become prevalent and mobile payment is widely accepted, there is a pressing need to address the above issues if zk-snark is to be used in cryptocurrency. We are making encouraging progress in this regard. We estimated that the efficiency improvements should be sufficient to realize mobile payments based on zk-snarks' cryptocurrency. Below we briefly introduce our findings, the details of which can be found in [10]. The increase in efficiency is based on the following improvements. First of all, zk-snark requires the statement that needs to be proved to be expressed in the form of arithmetic gate. At a high level, these statements are related to the building blocks of the token, including hash functions, commitment schemes, and pseudo-random functions. In Zcash, the choice of this building block is the hash function SHA256. However, the circuit of this building block consists of nearly a million Boolean gates, which also causes the parameters and the prover's result to consist of millions of elements and steps.

First, we recommend choosing building blocks that can be represented by fewer arithmetic gates. In this way, the calculation and parameter size of the prover are much smaller than the current system.

In the second improvement, we optimized the architecture in two ways. One is to use a ternary search tree instead of a binary search tree; the second is to use a window-based modular exponentiation operation with window size=3. Although the binary search tree is usually simpler, in a group equipped with bilinear mapping, fewer arithmetic gates can be used to represent operations involving 3 elements. Therefore, the entire architecture can be represented by smaller arithmetic gates, thereby further improving efficiency.

Combining these two technologies, our zk-snarks-based cryptocurrency parameter size will be reduced by about 90%, providing the necessary foundation for the realization of the wallet on the mobile client.