Try   HackMD

In this series of notes, we explore zkSNARKs in the context of PLONK and Halo2, two modern proof systems that find applications in the real world.

PLONK and Halo2 bear similarities and differences from each other, which provides us with the background to understand various elements of zkSNARKs and the computational and space complexities of these proof systems.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Along the way, we will discuss prevailing principles of PLONK and Halo2, such as, transforming computations into efficient arithmetic circuits, Lagrange interpolation of polynomials, accumulators, permutation arguments, lookup arguments, commitment schemes and elliptic curves, some directly in this series and some by referring to other notes where we discuss these topics in more depth.

We will begin by briefly introducing zkSNARKs, the theoretical principles that they embody, their uses as succinct knowledge arguments as well as their information theoretic hiding (zero-knowledge) properties. Afterwards, we will give an introduction to PLONK and its more recent variant Halo2.

In each chapter that follows, we will introduce and give a clear definition for a different element of these proof systems. In the final chapter, we will discuss how to bring together all the elements to construct a succinct zero-knowledge proof.

Chapters (private)

Remarks

This series reflects some of our views on zero-knowledge proof systems. Some of these views are possibly over-simplifications. Further, despite our efforts to minimize them, they may contain certain inaccuracies and we would be happy to remedy any such mistakes. Please feel free to contact petrichor.verdigris at gmail dot com if you would like to contribute to this series in any way, with due acknowledgement on our part. Thank you in advance.

References

  1. [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. https://eprint.iacr.org/2019/953.pdf, in IACR, 2019.
  2. [GW20] Ariel Gabizon, Zachary J. Williamson. plookup: A simplified polynomial protocol for lookup tables. https://eprint.iacr.org/2020/315.pdf, in IACR, 2020.
  3. [BGH19] Sean Bowe, Jack Grigg, and Daira Hopwood. Recursive Proof Composition without a Trusted. https://eprint.iacr.org/2019/1021.pdf, in IACR, 2019.
  4. [PFMM22] Luke Pearson, Joshua Fitzgerald, Héctor Masip, Marta Bellés-Muñoz, and Jose Luis Muñoz-Tapia. PlonKup: Reconciling PlonK with plookup. https://eprint.iacr.org/2022/086.pdf, in IACR, 2022.
  5. [GW20+] Ariel Gabizon, Zachary J. Williamson. The Turbo-PLONK program syntax for specifying SNARK programs. https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf, 2020.
  6. [G20] Ariel Gabizon. Multiset checks in PLONK and Plookup. https://hackmd.io/Iuu9P7S5Sca0TCoYJ-sFdA, 2020.
  7. [Z20] zcash. Halo2 book. https://zcash.github.io/halo2, 2020.
Last changed by 
 
kullervo
2
800

Read more

Vector Commitments

Vectors, w.r.t. commitment schemes, are simply arrays or ordered multi-sets, (sets with possible repetition of elements), unlike the regular definition of elements of linear spaces. For example, [2, 3, 1, 2, 5] will be a vector in this context (left to right order). Between sets and vectors, we could have also considered commitments to multi-sets without a specified order, but this is fairly uncommon in the literature.

Jul 27, 2023
Set Commitments

In this chapter, we discuss set commitments, which are the first in the hierarchy with a partial opening mechanism.

Jul 27, 2023
Single-element Commitments

In our view, the simplest family that is at the base of the hierarchy of commitment schemes consists of commitments to messages with no parts, which we call simple-element commitments. Paradoxically, all messages have some parts to them, perhaps outside of a single bit of information, i.e. a message that contains a single 0 or a 1.

Jul 27, 2023
Elements of Commitment Schemes

Commitment schemes are fundamental components of many cryptography protocols. A commitment scheme allows a committer to compute and publish a value d=C(m), called a commitment or a digest, which binds him/her to a message m (binding) without revealing it to the public (hiding/zero-knowledge).

Jul 27, 2023
Read more from kullervo
Published on HackMD