Proving System: Plonky3

Plonky3 is a batteries-included framework for building succinct proof systems. It is a collection of Rust crates providing a very small set of core traits around which various cryptographic primitives and examples are built.

Plonky3 consists of the following functional components, listed in a linearization of their dependency ordering:

1. A collection of simple utility functions. This is located in the util subdirectory.

2. A feature-gated wrapper around parts of rayon. This is located in the maybe-rayon subdirectory.

3. A field abstraction with various implementations and associated algorithms. This is located in the field subdirectory.

4. A collection of utilities for testing field implementations. This is located in the field-testing subdirectory.

5. A matrix abstraction with various implementations and associated algorithms. This is located in the matrix subdirectory.

6. A collection of AIR-related traits and implementations, including a two-row matrix view and affine functions over columns in a pair (“virtual columns”). This is located in the air subdirectory.

7. A framework for symmetric crypto primitives, including compression function related traits and implementations, a padding-free, overwrite-mode sponge function, a hasher trait, a serializing hasher, and cryptographic permutation related traits. This is located in the symmetric subdirectory.

8. An implementation of the Baby bear field (i.e., the finite field of size 2^31 - 2^27 + 1) and its quartic and quintic extension fields. This is located in the baby-bear subdirectory.

9. An implementation of the Goldilocks field (i.e., the finite field of size 2^64 - 2^32 + 1) and its quadratic extension field. This is located in the goldilocks subdirectory.

10. An implementation of the Mersenne-31 field (i.e., the finite field of size 2^31 - 1) and some of its field extensions, as well as DFT implementations for Mersenne-31. This is located in the mersenne-31 subdirectory.

11. A Keccak permutation and hash function implementation. This is located in the keccak subdirectory.

12. A Blake3 hash function implementation. This is located in the blake3 subdirectory.

13. A library of DFT-related traits and implementations. This is located in the dft subdirectory.

14. A collection of coding theoretic traits. This is located in the code subdirectory.

15. A collection of coset low degree extension related traits and implementations. These are used to take a polynomial, represented as its 2^k evaluations over the multiplicative subgroup of a finite field generated by a primitive 2^k-th root of unity, and compute the evaluations of the polynomial over a multiplicative-group coset of a primitive 2^(k+added_bits)-th root of unity. This is located in the lde subdirectory.

16. An implementation of Reed-Solomon codes. This is located in the reed-solomon subdirectory.

17. A collection of traits and implementations for generating Fiat-Shamir challenges based on an interactive proof’s transcript. This is located in the challenger subdirectory.

18. A collection of commitment scheme traits. This is located in the commit subdirectory.

19. A collection of maximum distance separable (MDS) permutation related traits and implementations. (An MDS permutation is an MDS code which is also a permutation.) This is located in the mds subdirectory.

20. A Poseidon permutation implementation. This is located in the poseidon subdirectory.

21. A Poseidon2 permutation implementation and related traits and implementations. This is located in the poseidon2 subdirectory.

22. A Rescue-XLIX permutation implementation. This is located in the rescue subdirectory.

23. A binary Merkle tree implementation and a vector commitment scheme backed by binary Merkle trees. This is located in the merkle-tree subdirectory.

24. An implementation of the Spielman-based code described in the Brakedown paper. This is located in the brakedown subdirectory.

25. A couple of functions to help with Lagrange interpolation, specifically Barycentric interpolation. This is located in the interpolation subdirectory.

26. A polynomial commitment scheme using degree 2 tensor codes, based on BCG20. This is located in the tensor-pcs subdirectory.

27. An implementation of the Monolith-31 permutation. This is located in the monolith subdirectory.

28. An implementation of FRI. This is located in the fri subdirectory.

29. A minimal univariate STARK framework. This is located in the uni-stark subdirectory.

30. A minimal multivariate STARK framework. This is located in the multi-stark subdirectory.

31. An AIR for the Keccak-f permutation. This is located in the keccak-air subdirectory. This is provided as an example.

A common misconception about Plonky3 is that Plonky3 provides a reusable STARK framework. This is not really the case, because the univariate STARK framework isn't general enough to work for a wide enough variety of commercially relevant use cases. Making it general enough for that is a hard problem, due in part to the limitations of abstraction capabilities in Rust. This is the reason why Valida, for example, doesn't leverage the univariate STARK framework in Plonky3, but instead contains its own implementation of univariate STARKs.

Valida leverages Plonky3 for some core bits of Valida's proving system, including key abstractions such as Plonky3's AIR builder, and Plonky3's FRI polynomial commitment scheme.