Anatomy of a STARK

Chapter 0: STARK Overview

Interactive Oracle Proofs

1. Think of STARK like a special case of SNARKs, where:

   • hash functions are the only cryptographic ingredient

   • arithmetization is AIR based (rather than the R1CS stuff we studied in Groth16)

     • and reduces the claim about computational integrity to one about the low degree of certain polynomials

   • the low degree of polynomials is proven by using FRI as a subprotocol

   • Zero Knowledge is optional. (STARKs are not ZK-STARKs by default)

2. The claims (which are to be proven) is NOT about a mathematical conjecture but concerns the integrity of a particular computation. The proof system is said to establish computational integrity.

3. Interactive proof systems are made non-interactive via the Fiat-Shamir Transform. Non-interactive proof systems consist of a single message from the prover to the verifier.

4. The difference between an argument system and a proof system is that an argument system provides protection against a prover whose computational power in bounded, so there is a nonzero but negligibly small false positive/false negative rate.

5. If verifying the computation is (much) faster than re-running the computation, then that proof system is said to be succint.

   • If the verifier has no access to the secret information that is available to the prover, AND when the proof system protects the confidentiality of this secret, the proof system satisfies Zero-Knowledge.

6. Interesting: Especially in context of zero-knowledge proof systems, the computational integrity claim may need a subtle amendement. In some contexts it is not enough to prove the correctness of a claim, but the prover must additionally prove that he knows the secret additional input, and could as well have outputted the secret directly instead of producing the proof. Proof systems that achieve this stronger notion of soundness called knowledge-soundness are called proofs (or arguments) of knowledge.

Chapter 1: STARK Overview

1. Scalable

   • Prover should have a running time that is atmost quasilinear in the size of the computation (in contrast to SNARKs where the prover is allowed to have a prohibitively expensive complexity)

   • Verification time is poly-logarithmic in the size of the computation.

2. Transparent

   • All verifier messages to the prover are just publicly sampled random coins (random values)

   • So, no trusted setup procedure is needed to instantiate the system and there is no toxic waste

3. Argument of Knowledge

   • It's an argument system and not a proof system

4. The compilation pipeline of STARKs can be divided into the following four stages (and three transformations):

   • 

Compilation Pipeline Overview

1. Computation

   • The input to the entire pipeline is a computation, which can be thought of as (a program, an input and an output). This is most probably the witness

   • The goal is to transform the computation into a format that enables resource-constrained verifier to verify it's integrity.

2. Arithmetization and Arithmetic Constraint System

   • In this transformation, the sequence of elementry logical and arithmetical operations on strings of bits (witness) is transformed into a sequence of native finite field operations on finite field elements, such that the two represent the same computation.

   • The output is the arithmetic constraint system which is essentially a bunch of equations with coefficients and variables taking values from the finite field. The computation is integral iff the constraint system has a satisfying solution.

   • The arithmetic constraint system defines atleast two types of constraints on the algebraic execution trace:

     • Boundary constraints: at the start or at the end of the computation an indicated register has a given value

     • Transition Constraints: Any two consecutive state tuples evolved in accordance with the state transition function.

   • Collectively these constraints are called algebraic intermediate representation or AIR. Advanced STARKs may define more constraint types to deal with memory or consistency of registers within 1 cycle.

3. Interpolation and RS IOPs

   • In context of STARKs, interpolation means finding a representation of the arithmetic constraint system in terms of polynomials. This set of resulting polynomials is an abstract protocol not an arithmetic constraint system.

   • If the messages (in a typical proving system) from the prover is replaced by oracles (which the verifier can query in any point of their chosing), it becomes an interactive oracle proof (IOP)

     • If the oracle corresponds to a polynomial of low degree, then it is called a Polynomial IOP.

   • The intuition is that the prover arrives at a polynomial constraint system, whose equations hold and the malicious prover will have a constraint system with atleast one equation false.

     • Since unequal polynomials are unequal almost everywhere... the verifier has a high probability of sniffing out these malicious provers.

   • This interpolation step (in STARKs, we literally create polynomials by interpolating the execution trace and then these polynomials are sent as oracles to the verifier) essentially reduces the satisfiability of an arithmetic constraint system to a claim about the low degree of certain polynomials (FRI step).

4. FRI

   • Polynomial oracles do not exist in reality. It's closest apporximation is to get the prover to commit to a polynomial and open the polynomial at the points of verifier's choosing. This is enabled by FRI.

   • The Reed-Solomon codeword associated with a polynomial are the set of values of the polynomial over domain D. If we put these values in a Merkle Tree, then the root of this tree would represent a commitment to the polynomial.

   • FRI is the protocol where the prover will send a series of such Merkle roots, where the length of the codeword halves in every iteration (ergo, the domain halves).

   • The verifier checks each Merkle root commitment to see if a simple linear relation holds or not.

     • WHAT IS THIS SIMPLE LINEAR RELATION?

   • For honest provers, the degree of the represented polynomial halves everytime until eventually at the last round we are left with a constant polynomial. However for the dishonest prover, after every iteration, the only reasonable assumption about the degree of the polynomial is that it is 1 less than the length of the codeword.

   • How does FRI play out? Well, if the verifier asks for the evaluation of a polynomial f(x) at z, and then if the prover responds with y... then that would mean that f(x) - y / x - z divides each other. So, if the prover was lying about the value of f(z) being y, then they would not be able to prove the low degree of the polynomial f(x) - y / x - z.

   • One last step of cryptographic compilation is to replace the verifier's random coins with something pseudorandom - but deterministic and that is what the Fiat-Shamir transform does and the result is the non-interactive proof known as the STARK.

---

Chapter 2: Basic Tools

1. Figure out how basic finite fields, with given operations work. For example, Fp with + and X.

   • Subtraction of a - b would be equivalent to a + (additive inverse of b)

   • Division of a / b would be equivalent to a * $b^(-1)$ (multiplicative inverse of b)

   • 0 does not have a multiplicative inverse, but every other element has it and they also have additive inverses.

2. For purpose of building STARKs we need finite fields with a particular structure: it needs to contain a substructure of order 2k for some sufficiently large k.

   • Defining modulus p = f.$2^k$ + 1

   • f is some cofactor that makes the number prime

   • For all intents and purposes, one can identify this subgroup with 2k evenly spaced points on the complex unit circle.

   • 

     • The complex unit circle is the set of all complex numbers with magnitude 1, representing points that lie on a circle of radius 1, centered at (0,0). Each point can be written as e^(i$\theta$) where where 𝜃 goes from 0 to $/pi$$2 \pi$

     • While we're working in a finite field Fp, these points behave similarly to evenly spaced points on this circle because:

       • They form a cyclic group under multiplication

       • When you multiply by the generator ω, it's like rotating around the circle

       • After 2^k multiplications, you get back to where you started (just like going all the way around the circle)

3. Univariate polynomials are polynomials with a non-negative degree with one unknown, x.

   • Their extremely useful property that is leveraged in proof systems is that relations that apply to their coefficient vectors, extend to their values on a potentially much larger domain.

   • This essentially means that univariate polynomials reduce claims about large vectors to claims about the values of their corresponding polynomials in a small selection of sufficiently random points. This is because equal polynomials are equal everywhere (in the domain) and unequal polynomials are almost unequal everywhere in the domain.

4. Multivariate polynomials generalise univariate polynomials to many indeterminates, such as x, y, z, ...

   • Multivariate polynomials are useful for articulating the arithmetic constraints that an integral computation satisfies.

   • Basically a set of multivariate polynomials that capture the constraint of the correct application of a single iteration of a given operation is expected to capture the computation. So, the polynomial evaluates to 0 if the computation is integral.

5. The fiat-shamir transform converts an interactive proof system protocol to a non-interactive one.

   • This is achieved because it turns out that keeping the verifier queries completely random is an overkill. If we can make the verifier's message difficult to predict by the prover, then that is good enough security for our Fiat-Shamir transform.

   • Precisely speaking, FS replaces the verifier's random messages by the hash of the transcript of the protocol up until those points.

   • It is necessary to restrict the prover's control over what input goes into the hash function (that generates a psuedorandom output) otherwise he can grind until he finds a favorable input.

   • 
6. Merkle Trees.

   • Everyone knows how they work. Move the fuck on.

---

Chapter 3: FRI

1. The Fast Reed Solomon Interactive Oracle Proof of Proximity is a protocol that establishes a committed polynomial has a bounded degree.

   • The codewords in this protocol refer to Reed-Solomon codewords, meaning that their values correspond to the evaluation of some low-degree polynomial over the points in domain D.

2. The domain D is larger than the number of possibly non-zero coefficients in the polynomial by a factor called the blowup factor (which is the reciprocal of code's rate $\phi$)

   • This is possibly because a large vector of numbers can be molded into polynomials and the equality of polynomials (via SZL) can help reason about the equality of these polynomials.

3. The brilliant idea behind split-and-fold technique is to reduce a claim to two claims of half the size.

   • Then both claims are merged into one using random weights supplied by the verifier.

   • After logarithmic number of steps, the claim has been reduced to one of a trivial size which is true if and only if the original claim was true.

   • In the case of FRI, this computational claim asserts that the given codeword corresponds to a polynomial of low degree.

4. The key step in FRI is to derive a codeword for the f*(x) = $$ f_{E}(x) $$ + $\alpha.f_O{}(x)$ from the codeword for f(x), where $\alpha$ is the random scalar supplied by the verifier.

5. Another thing that we should know is that even though the domain gets halved when you split f(x) into $f_{E}(x)$ and $f_{O}$(x) in the form of $f^{*}(x) = f_{E}(x) + \alpha.f_{O}(x)$, all the points of the domain are involved in the derivation of the codeword of the new polynomial (even if it has half the degree and half the domain)

   • The great thing that this ensures is that a malicious prover can't reliably trim down the points of evaluation after every iteration.

   • These images represent the mathematical backing behind this statement

   • 

   • 

     1. Let's consider a single round of FRI:

        • The prover commits to f(x) by sending the Merkle root of its codeword to the verifier

        • The verifier responds with the random challenge $\alpha$

        • The prover computes f*(x) and commits to it by sending the Merkle root of $f^{*}(\omega^{2i})_{i=0}^{N/2 - 1}$ to the verifier

     2. The verifier now has 2 commitments to polynomials and his task is to verify that their correct relation holds.

        • The verifier rejects the proof if:

          • $f^{*}(x^{2}) != 2^{-1}.((1 + \alpha x^{-1}.f(x) + (1 - \alpha x^{-1}).f(-x)$

        • To do this, the verifier randomly picks a point from {0,..., N/2 - 1}, which will define 3 points:

          • A: ($\omega^{i}$, $f(\omega^{i})$)

          • B: ($\omega^{N/2 + i}$, $f(\omega^{N/2 + i}))$

          • C: ($\alpha, f^{*}(\omega^{2i}))$

        • Now, the verifier does a colinearity check, ie, verifying whether A, B and C fall on a straight line. Now, why would that happen?

          • Well because x-cordinates of both A and B are the square roots of $\omega^{2i}$ and given that the points of this subgroup can be represented on a circle... then A and B are in a straight line.

          • Now, if we next find the line that passes through A and B, we find C :P

          • 
     3. Now, post this first round of FRI... the prover and verifier can set $f = f^{*} and D = D^{*}$ and begin the process again.

        • After $log_{2}(d+1) - 1$ rounds of FRI, where d is the degree of the polynomial... we are left with a constant polynomial and a constant codeword.

          • At this point the prover send this constant instead of codeword's Merkle Root, making it abundantly clear that is corresponds to a polynomial of degree 0.

     4. IMPORTANT: This requires FURTHER RESEARCH from my end.

        • In production systems, the length of the codeword is often reduced not by a factor of 2 but by a small power of 2.

        • This optimises the proof size and runtime.

        • Study the implications on the theoretical security because by this tradeoff.

     3.1 Index Folding

     1. The random indices ($\alpha$, i) are not independent between rounds. The same index is re-used across rounds, with reductions modulo the codeword length when necessary.

     2. Random indices are less likely to catch hybrid codewords (codewords where a malicious prover tries to mix valid and invalid codewords)

     3. By re-using and folding the same indices, if there's an inconsistency, it will be either caught in the current round or in the subsequent round.

     3.2 Security Level

     The following are the recommendations from the EthSTARK documentation for conjectural security for a target security level of $\lambda$ bits:

     1. Merkle tree hash functions need to have 2 $\lambda$ bits

     2. The field used for FRI needs to have 2$\lambda$ elements, if not use field extensions

     3. Every co-linearity check provides log$_{2} \rho^{-1}$ bits of security. So the number of co-linearity checks required is $\lambda$ divided by the security of each colinearity check. 4. $\rho$ is the code's rate, inverse of the blowup factor.

     3.3 Productionising FRI

     1. Can FRI be used as a polynomial commitment scheme? Absolutely. All you need to do is the following:

        • If the prover claims that f(z) = y, then it can be verified via the following method:

          • (f(x) - y) / x - z is the rational function that MUST be a polynomial if the claim is true!!

        • This has been touched upon in greater detail in STARKs 101 (ironic, ik)

     2. Next we optimize how FRI handles multiple polynomial constraints efficiently.

        • Instead of running FRI separately for multiple polynomials that need degree bounds verified, we:

          • Take all polynomial constraints

          • Combine them into one big check using random weights from the verifier

          • g(X) = Σ (αᵢ⋅fᵢ(X) + βᵢ⋅X^(2ᵏ⁻ᵈⁱ⁻¹)⋅fᵢ(X))

          • αᵢ and βᵢ are random weights

          • fᵢ(X) are the different polynomials

          • dᵢ are their degree bounds

        • Then proves the degree bound just once on this combined polynomial