# Proving System: Plonky3

[Plonky3](https://github.com/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](https://docs.rs/rayon/latest/rayon/). This is located in the `maybe-rayon` subdirectory.
3. A [field](https://en.wikipedia.org/wiki/Field_\(mathematics\)) 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](https://en.wikipedia.org/wiki/Matrix_\(mathematics\)) abstraction with various implementations and associated algorithms. This is located in the `matrix` subdirectory.
6. A collection of [AIR](https://aszepieniec.github.io/stark-anatomy/overview.html#arithmetization-and-arithmetic-constraint-system)-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](https://en.wikipedia.org/wiki/One-way_compression_function) related traits and implementations, a padding-free, overwrite-mode [sponge function](https://en.wikipedia.org/wiki/Sponge_function), a hasher trait, a serializing hasher, and cryptographic [permutation](https://en.wikipedia.org/wiki/Permutation) related traits. This is located in the `symmetric` subdirectory.
8. An implementation of the Baby bear field (i.e., the [finite field](https://en.wikipedia.org/wiki/Finite_field) of size 2^31 - 2^27 + 1) and its quartic and quintic [extension fields](https://en.wikipedia.org/wiki/Field_extension). 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](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) implementations for Mersenne-31. This is located in the `mersenne-31` subdirectory.
11. A [Keccak](https://keccak.team/keccak_specs_summary.html) permutation and hash function implementation. This is located in the `keccak` subdirectory.
12. A [Blake3](https://github.com/BLAKE3-team/BLAKE3/) hash function implementation. This is located in the `blake3` subdirectory.
13. A library of [DFT](https://en.wikipedia.org/wiki/Discrete_Fourier_transform)-related traits and implementations. This is located in the `dft` subdirectory.
14. A collection of [coding theoretic](https://en.wikipedia.org/wiki/Coding_theory) 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](https://brilliant.org/wiki/primitive-roots-of-unity/), and compute the evaluations of the polynomial over a multiplicative-group [coset](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction). This is located in the `reed-solomon` subdirectory.
17. A collection of traits and implementations for generating [Fiat-Shamir](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) challenges based on an [interactive proof](https://en.wikipedia.org/wiki/Proof_of_knowledge)’s transcript. This is located in the `challenger` subdirectory.
18. A collection of [commitment scheme](https://en.wikipedia.org/wiki/Commitment_scheme) traits. This is located in the `commit` subdirectory.
19. A collection of [maximum distance separable](https://en.wikipedia.org/wiki/Singleton_bound) (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](https://eprint.iacr.org/2019/458.pdf) permutation implementation. This is located in the `poseidon` subdirectory.
21. A [Poseidon2](https://medium.com/@horizenlabs-tech/introducing-poseidon2-559c1b33b102) permutation implementation and related traits and implementations. This is located in the `poseidon2` subdirectory.
22. A [Rescue-XLIX](https://www.esat.kuleuven.be/cosic/sites/rescue/) permutation implementation. This is located in the `rescue` subdirectory.
23. A binary [Merkle tree](https://brilliant.org/wiki/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](https://eprint.iacr.org/2021/1043). This is located in the `brakedown` subdirectory.
25. A couple of functions to help with [Lagrange interpolation](https://en.wikipedia.org/wiki/Lagrange_polynomial), specifically [Barycentric interpolation](https://depts.washington.edu/ph506/BarycentricLagrange.pdf). This is located in the `interpolation` subdirectory.
26. A polynomial commitment scheme using degree 2 tensor codes, based on [BCG20](https://eprint.iacr.org/2020/1426). This is located in the `tensor-pcs` subdirectory.
27. An implementation of the [Monolith](https://eprint.iacr.org/2023/1025)-31 permutation. This is located in the `monolith` subdirectory.
28. An implementation of [FRI](https://eprint.iacr.org/2022/1216). This is located in the `fri` subdirectory.
29. A minimal univariate [STARK](https://aszepieniec.github.io/stark-anatomy/) 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.