ZKSNARK algorithm implementation

Introduction

The realization of the zero-knowledge proof project has been in an early stage since 2013, and there is still some way to go. However, with the rapid development of blockchain in recent years, more and more teams are setting their sights on this field, so zero-knowledge landing results are also developing rapidly.

1 Technical architecture

The current zero-knowledge proof architecture can be roughly divided into five layers:

The underlying foundation

The underlying algorithm library of zero-knowledge proof is the prerequisite for achieving zero-knowledge proof. The underlying algorithm contains a large number of finite field calculations, matrix operations, and elliptic curve operations.

Proof system

The proof system is also a zero-knowledge proof protocol, and the proof can only be completed by having the proof system. As mentioned above, Pinocchio and Plonk have their own independent proof systems. At present, the more widely used proof systems include Groth16 and Bulletproofs, etc.

Circuit constraints

As introduced in the previous article, every zero-knowledge proof needs to transform the actual problem to be tested into a proof protocol and a verifiable constraint relationship. Therefore, constructing circuit constraints is also a core part of zero-knowledge proof engineering, and it is the basis of zero-knowledge proof.
It is very difficult to construct the circuit. On the one hand, because different problems correspond to different constraints, the circuits are different; on the other hand, it is difficult to guarantee the correctness of the constructed circuit. Once the circuit is constructed incorrectly, the subsequent proof is difficult to guarantee. Therefore, efficient and reasonable construction of circuits is also an important subject in zero-knowledge proof.

Circuit gadget

In the actual complex constraint relationship, there are actually many simple constraint relationships that are reused, such as Boolean value proof, range proof, and hash proof. These constraints are often encapsulated in the open source library integrated by the gadget. Developers can directly call the interface to complete this part of the circuit components, which simplifies the developer's development volume and reduces the possibility of errors.

Upper application

Layer applications mainly include two categories:

Directly call the zero-knowledge proof library to complete the circuit construction and follow-up proof.
In order to simplify the process of zero-knowledge proof, developers aggregate the underlying construction toolkit of the blockchain into an open source tool for zero-knowledge proof, such as the SNARK toolbox ZoKrates on Ethereum.

Implementation language

According to incomplete statistics, there are currently dozens of open source libraries related to zero-knowledge proof, and there are close to 10 active github code bases. This article selects five representative zero-knowledge proof open source libraries to explain.

1. libsnark

Libsnark is the implementation of the zkSNARK solution developed by SCIPR Lab. The development language is C++. The theoretical basis behind the libsnark project implementation is to include mainstream protocols such as GGPR13, PGHR13, BCGTV13, BCIOP13, BCTV14, Groth16 and GM17. At the same time he realized a number of commonly used circuits.

github: https://github.com/scipr-lab/libsnark

bellman

bellman is a zk-SNARK software library developed by the Zcash team in Rust language, which implements the Groth16 algorithm. It provides a toolbox for building zk-snark circuits, circuit characteristics and basic structure.

github: https://github.com/zkcrypto/bellman

gnark

gnark is a zkSARNK implementation developed by ConsenSys, using Go language and using a DSL similar to GO to describe the circuit. Currently supports Pinocchio and groth16.

snarkjs

snarkjs is the javascript implementation library of the zkSARNK solution, supporting the original 8points protocol and the Groth protocol. With snarkjs you can make trusted settings, generate evidence and verify evidence.

github: https://github.com/iden3/snarkjs

pysnark

pysnark is an implementation of the zk-snark solution developed by Python. It supports the Pinocchio protocol and supports the generation of smart contracts for Ethereum to verify zero-knowledge evidence.