Spartan is a sum-check-based zkSNARK with an extremely efficient prover. It also features several unique properties that are particularly relevant for client-side proving in applications such as identity and other use cases where zero-knowledge is essential. Here are some highlights: Spartan can be instantiated with any multilinear polynomial commitment scheme (e.g., Binius, HyperKZG, Samaritan, WHIR, Mercury, BaseFold, PST13, Dory, Hyrax). Depending on the polynomial commitment scheme used, one can achieve different properties (e.g., small fields or big fields, post-quantum or pre-quantum security, transparent or universal setup, hash-based or curve-based, binary fields or prime fields). Spartan is flexible with respect to arithmetization: it can support R1CS, Plonkish, AIR, and their generalization CCS. Spartan protocol itself internally uses lookup arguments, so one can additionally prove lookup constraints with Spartan. The prover's work naturally splits into a witness-dependent part and a witness-independent part (a significant chunk, up to 90%, of the prover's work is incurred in the witness-independent part). The latter part can be offloaded to any untrusted entity without violating zero-knowledge. Note that such a clean decomposition between witness-dependent part and witness-independent part is not featured by other popular zkSNARKs (e.g., Groth16, Plonk, HyperPlonk, Honk). The witness-dependent work of the Spartan prover is shown to be MPC-friendly by more recent works, allowing the whole Spartan prover to be delegated. For uniform constraint systems, Spartan's prover can be optimized further by eliminating the witness-indepdent work of the prover, which constitutes about 90% of the prover's work. Despite several papers describing Spartan and follow-up works, there is a lack of understanding of the Spartan protocol--even among experts. The primary goal of this document is to provide a gentle introduction to the Spartan protocol. While we aim for precision, we may occasionally abuse notation for the sake of clarity and accessibility.

In this multi-part series, we aim to make folding schemes less mysterious. In the first part, we focus on answering simple question. We also examine why some projects experience poor performance despite using folding. TLDR: it is because of sub-optimal choices and things built around folding schemes (e.g., circuits fed to folding schemes) rather than folding schemes themselves. In future parts, we will provide a gentle introduction to NeutronNova's and Neo's folding schemes. Among all folding schemes, NeutronNova has the best asymptotics and concrete efficiency. NeutronNova also shows how to handle non-uniformity efficiently that arises when dealing with zkVMs. In particular, NeutronNova provides an approach to build folding schemes for complex statements including VM executions. After NeutronNova, we will dive into Neo, which combines the best of all existing schemes:incurs tiny recursion overheads (like Nova) leverages small fields (like STARKs) incurs pay-per-bit commitment costs (like Binius) leverages the sum-check protocol (like Spartan and Jolt) Now, let's begin. We start with the most important question.