Stwo: Under the Hood
This section provides an overview of the core components and protocols that make up Stwo. It is intended for readers who want to understand the technical details and inner workings of the system implementation. Throughout this section, we describe the implementation as available in this commit.
The following topics are covered:
- Mersenne Primes: Introduction to the Mersenne31 prime field used in Stwo for efficient arithmetic.
- Circle Group: Explains the algebraic structure underlying FFT and polynomial operations.
- Circle Polynomials: Details the representation and evaluation of polynomials in the circle group.
- Circle FFT: Describes the fast Fourier transform algorithm adapted for the circle group.
- Vector Commitment Scheme (VCS): Covers the use of Merkle trees for committing to vectors and enabling efficient proofs of inclusion.
- AIR to Composition Polynomial: Shows how algebraic constraints are encoded as polynomials for proof generation.
- Circle FRI: Explains the FRI protocol for low-degree testing of polynomials over the circle group.
- Polynomial Commitment Scheme (PCS): Describes the protocol for committing to and opening polynomials with soundness guarantees.
- Proof Generation and Verification: Walks through the process of generating and verifying a STARK proof in Stwo.
- Lookups: Discusses lookup arguments and their implementation in Stwo for efficient constraint checking.