Continued from the previous article. PlatON Privacy-Preserving Computation White Paper | Part 1. Overall Framework

We have know about the Overall Framework of PlatON Privacy-Preserving Computation White paper, LatticeX Foundation proposes a framework, as shown in Figure 1, to deal with privacy and storage issues in PlatON/Alaya. This solution or plan is based on the architecture of PlatON 2.0. The vision of PlatON 2.0 is to build a decentralized and collaborative AI network and global brain to drive the democratization of artificial general intelligence.

This chapter will cover the algorithm section in detail.

Part 2. Algorithms

This level contains cryptographic algorithms to support upper level solutions. It has four classes including primitives, ZK-SNARKs, recursive zero-knowledge proofs and accumulators. Note that most of these algorithms are based on elliptic-curve cryptography, which turns out to be non- quantum safe. Although we believe that the power of quantum computers now poses no substantial threat to cryptography in a decade, we continue to maintain an ongoing interest in post-quantum cryptography. The research of quantum-resilient alternatives is very active in the academic com- munity. We will migrate to the post-quantum era gradually when these algorithms are ready.

2.1 Primitives

Primitives are building blocks to construct advanced cryptographic algorithms and solutions.

Elliptic Curves.

Elliptic-curve cryptography enables smaller public key size and fast operations. Inheriting from Ethereum, the Secp256k1 curve is supported natively. Faster Curve25519 is also integrated to generate fast zero-knowledge proof, e.g., range proofs, based on discrete log problems. Another type of curves are pairing-friendly ones, including BN254 and BLS12–381. These two curves are widely used in ZK-SNARKs algorithm and related pairing-based constructions such as BLS signature and verifiable function. Due to its versatility, pairing-friendly curves will be unified with BLS12–381 in the near future.

Hash Functions.

Standard hash function used in blockchain is SHA256. Although the com- putation of SHA256 is extremely fast, it is not compatible with zero-knowledge proof algorithms. This is because SHA256 consists of well-designed Boolean circuits, but almost zero-knowledge proof algorithms are designed for arithmetic circuits. In theory, one could transfer SHA256 circuit into arithmetic in a field, but the performance of proof generation of the underlying ZKP algorithm is not satisfactory.

Zero-knowledge friendly hash functions play an important role to improve the performance of proof generation time. These functions are directly defined on arithmetic circuits, which naturally compatible with most ZKP algorithms. Poseidon and Rescue are two of the candidates. However, it is worth pointing out that these hash functions are newborn ones, which lack of sophis- ticated cryptographic analysis and test of time. We keep a constant eye on the progress of these algorithms, and cautious approach to the use of these algorithms is recommended.

Polynomial Commitment.

A polynomial commitment scheme allows a committer to commit a polynomial with a short string that can be used by a verifier to confirm claimed evaluations of the committed polynomial. Polynomial commitment has a wide range of applications. It is a core building block of ZK-SNARKs, vector commitment and verkle tree et al. We recommend the efficient construction proposed in, which is also named as the KZG polynomial commitment. The KZG polynomial commitment has constant size (one single element), the overhead of opening one and multiple evaluations requires only a constant amount of communication, which is desirable in most applications.

However, the advantages of KZG polynomial commitment come at a price. It needs a trusted setup procedure, which is not acceptable in a decentralized network and applications. An ongoing activity named as Lumino is a MPC ceremony to generate all the parameters in a distributed manner, and the resulting parameter is trustless as long as at least one participant is honest.

2.2 ZK-SNARKs

ZK-SNARKs are core components of the algorithm level. Essentially, ZK-SNARKs are non- interactive proof systems that could prove any NP problems in zero-knowledge. The proof size and verification time are very small, but the proving time is relatively large. These properties are very suitable for blockchain systems. Small proof size and verification time are beneficial to broadcast and verify the proof on-chain, and the proving procedure could be done off-chain.

Plonk and Marlin are preferable in our systems. Besides of the short proof and ver- ification time, these two systems have another attractive property. Both of them only require a universal structured reference string to setup the system. This string plays a vital role to enjoy short proof size and verification time, and could be generated in a distributed way by running a very simple and efficient MPC protocol. Further, this string is independent of the applications (not like Groth16 ), and could be updated at any time by any participant. The very recent activity Lumino is an MPC ceremony to generate this string for Plonk. We note that there exists ZK- SNARKs or other types of proof systems that do not need trusted setup. However, the concrete performance of most these algorithms seems not satisfactory for most complicated applications.

GKR-based algorithms are another type of ZK-SNARKs. Although the concrete proof size and verification time are not as good as Plonk and Marlin, the proving time is attractive in other off-chain applications. Recent progresses show their huge potentials. This type of algorithm could even prove complicated statements such as deep learning models, which is the state-of-the-art ZK-SNARK scheme in this direction.

In order to reduce the bar of developing with ZK-SNARKs, gadgets libraries under different algorithms are provided. In addition to facilitating development, these basic components allow for targeted optimization of them.

2.3 Recursive ZKPs

Recursive ZKPs are proofs of proofs. They essentially prove that another zero-knowledge proof is valid. These proof systems are very powerful in solving the scalability and storage issues in blockchain. However, the performance of all existing schemes is not satisfactory. We are very optimistic about the research in this area and have great confidence in the subsequent performance improvement.

ZKP Composition.

Zero-knowledge proofs are usually used to protect the anonymity and confi- dentiality of transactions. However the introduction of ZKP will inherently reduce the performance of blockchain, this is because the verification procedure will take tens of milliseconds and is much larger than a single signature verification. Using ZKP composition, one could batch many (say 100) transactions protected by ZKP, and prove that “the zero-knowledge proof of these 100 transactions are valid”, then the resulting proof actually convince participants all the 100 transactions in a single verification. This again improves the amount of transaction per second (TPS) of the blockchain system.

Incrementally-Verifiable Computation.

IVC proposed by Valiant is a general case of ZKP composition. IVC splits a long sequential computation between different parties such that every party performs a small part of the computation and passes it on to the next party. Together with the current state of their computation, parties should include a proof that the computation was performed correctly, not only in the last step, but in its entirety.

A simple example is depicted in Figure 2. The computation is split into F0,F1,F2 in sequence and distributed to 3 parties. IVC enables anyone to verify the final result and the intermediate computations are correct, without computing the functions again. The basic idea of IVC is as follows. The first party computes F0 on the input and provides a proof to convince the second party that the computation is correct. The second party computes F1 on x1 and provides a proof which says “I have a valid proof that x1 = F0(x0)”. The third party acts similarly, and provides a proof says “I have a valid proof that x2 = F1(x1)”. Therefore, one could verify the validity of π2 to believe that all the computations are correct.

IVC has plenty of applications, and it is very powerful to construct succinct blockchain systems. One could keep a very small proof on-chain, all the participants could verify the validity of the proof to make sure all the historical transactions are valid. The research of IVC is also very active in the academic community.

Proof-Carrying Data.

PCD is a generalization of IVC, where the computation is represented with a DAG, not just in a path. The research is very active, but the overall performance is still not satisfactory for real applications.

2.4 Accumulators

An accumulator is a one-way membership hash function. It allows users to certify that potential candidates are a member of a certain set with a short and easy-to-verify witness. In some cases, it is also required to conceal the individual members of the set.

One trivial accumulator is Merkle tree, which accumulates all the transactions into the root of the tree. A witness of the membership is the path of its siblings to the root. One could easily re- compute the root according to the path and compare the results. Vector commitment does the same as Merkle trees by using a totally different way, it could heavily rely on polynomial commitment. The recent pointproofs system is a new and efficient candidate for vector commitment.

A verkle tree is essentially a combination of vector commitment and Merkle tree, which is first proposed by John Kuszmaul. In a Merkle tree a parent is the hash result of its two children. While in a verkle tree, a parent is the vector commitment of its multiple children. Verkle trees are more space-efficient than Merkle trees, and the witness of membership contains multiple opening proofs of vector commitments, which could be aggregated into single one proof. Due to the efficiency in proof size, Ethereum 2.0 plans to build stateless clients using verkle tree.