# Safu ZK
## Safu ZK: A concise resource on Zero Knowledge Proofs
### whoami
I am Rahul Saxena and currently, I am a security engineer at ZkSync which is an Ethereum L2 scaling solution. The scaling that ZkSync does is enabled via something called Zero-Knowledge Proofs in the sense that anything that is done on the rollup is provable.\
\
That means that the EVM execution can be cryptographically proven to be correct eliminating the need for optimistic solutions and introducing the complex challenge period. This makes the EVM that ZkSync uses a ZkEVM.\
\
I make sure that the \*circuits\* that generate these proofs of execution do not have any bugs and work as they are supposed to.
### What would this resource contain?
This resource would contain all my notes that I'll take down while I dive deep into the world of Zero Knowledge cryptography to secure ZkSync's systems and quench my intellectual thirst.
# SafuZK Roadmap
The step-by-step plan to gaining and organising information about different aspects of ZK and cryptography useful for ZkVM security
This is the broad outline of all the resources I would consult and make notes on to gain a deeper understanding of every aspect related to ZK security, especially ZkVM security.\
\
Obviously, the exact resources and/or the order of studying them could change, but this is still a pretty good rough estimate of the roadmap.
1. The main resource for the resource would be the [Awesome ZkVM](https://github.com/rkdud007/awesome-zkvm) repository.
2. Since many of the upcoming ZkVMs are based on STARKs, I would focus on learning their workings deeply. So, the resources I have in mind would focus more or less on STARKs and ZkVMs.
1. [STARKs 101](https://starkware.co/stark-101/) ✅
2. [Anatomy of a STARK](https://aszepieniec.github.io/stark-anatomy/) 🏗️
3. [FRI from scratch](https://blog.lambdaclass.com/how-to-code-fri-from-scratch/)
4. [A zero-knowledge paradigm](https://www.lita.foundation/blog/zero-knowledge-paradigm-zkvm) series by Lita Foundation
# Fiat Shamir Vulnerabilities
## Fiat Shamir Transform
The Fiat Shamir transform is something that we often come across when studying how different ZK protocols work and it seems like everyone just assumes that you already know what FS transform is, lol.
Here is an explanation of what the Fiat Shamir transform means.
1. Any proving system typically consists of some back and forth messaging between the prover and the verifier to judge whether the proof presented by the prover is true or not. Since that is not ideal in different protocols, Fiat Shamir proposes a mechanism to convert interactive protocols into non-interactive protocols.
2. When you want to assess whether the Fiat Shamir transform is mathematically (crpytographically) secure or not, you ensure the three following properties hold:
* Completeness
* All correct proofs are always accepted
* Soundness
* All incorrect proofs are always rejected (a very small probability of false claims being accepted is fine, also known as *negligible soundess*)
* Preserving ZK (over n rounds)
* Even after getting the answers from the prover for different challenges for `n` rounds, the verifier does not gain computational power. That is, **What the verifier can compute after the interaction == What the verifier could have computed before the interaction**
3. Long form Resource: Watch this [presentation by @ronrothblum](https://youtube.com/watch?v=9cagVtYstyY)
4. This presentation will help you understand why FS is secure for an ideal hash function, ie, the ROM (Random Oracle Model).
5. And most importantly, why people make mistakes while implementing FS, because FS does not have such strong guarentees over real, concrete hash families. And, if you can internalise why, I reckon that would be a good spot to go bug-hunting.
#### FS Security B1: Last Challenge Attack
1. Example of a bug due to incorrect implementation of Fiat Shamir over the PLONK proving system: [Last Challenge Attack by OZ](https://www.youtube.com/watch?v=Sk-S8-n6Jo4)
* Quick Recap of the how the hack is carried out
* 
* PIOP -> Polynomial Interactive Oracle Protocol
* What changes to the above diagram when we implement the FS transform?
* Well, first the prover commits to the polynomial as expected
* Then, he *hashes the commitment to the polynomial to create the challenge* (the challenge would have originated from the Verifier in an interactive setting)
* Then using the generated challenge, prover evaluates the polynomial and sends the evaluation to the verifier together with the proof.
* On the verifier side the verifier also hashes the commitment to understand the challenge and then uses that knowledge to verify prover's claims.
* The PLONK prover goes in 5 rounds (of back and forth) and I'll shortly present the table of what happens in all those rounds. Let's first understand what each column is:
* Transcript: answers given by the prover + initial Poly commitment
* Out FS Challenge: Challenge given to the prover
* FS Challenge: I/P to the current round from the previous rounds
* 
* Now, the final proof π is generated from the transcript that were produced upto this point. It looks something like this:
* 
* Important point to note is that `u` (or the last challenge) is not being used anywhere in the calculation of the proof. Therefore, *it makes sense to replace hashing all the transcripts to obtain `u` with a random value.*
2. Now onto the last step of the PLONK verifier. If the following equation holds, then the proof is accepted.
* 
3. Now these are the steps that the attacker would take to forge a false proof that would be accepted by the verifier.
* **Bootstrapping**: Prover produces `A` and `B` from any circuit of its choice. By virtue of it being a legitimate proof, the equation highlighted in 7 holds.
* The prover can change any values in the proof π highlighted in green (including the public inputs) apart from the polynomial commitments, red blocks:
* 
* Prover computes `F` and `E` from the fixed components in π using steps 9-11 of the verifier
* Now, the Prover goes onto calculate these two red variables by exploiting the independence of `u` on the two red elements.
* 
* Prover adds the missing X and Y to complete the false proof π
* Verifier accepts the false proof π as valid, because we started off with a valid proof. What we did is simply retrofitted the two values.
4. That's it. That was the exploit. Key Takeaways:
* FS challenges must depend on the entire transcripts
* PLEASE follow the protocol
#### FS Security B2: Weak Fiat Shamir Attacks
1. As mentioned in the Fiat Shamir description earlier, whether a FS implementation is secure or not is dependent on whether *soundness* and *completeness* is preserved or not (ZK too, but that's not the focus right now).
2. It is shown in the academic papers that the Fiat Shamir transform preserves these security properties. But that is true for **non-adaptive** settings, ie, settings where the malicious prover P\* may not choose the statements.
3. In adaptive settings, P\* can compute both `π` and `x` simultaneously.
* `π` -> Proof
* `x` -> Public Statement
4. These notions of adaptive and non-adaptive settings give rise to the notion of **WEAK FIAT SHAMIR** and **STRONG FIAT SHAMIR** implementation.
* Since calculating both `π` and `x` is only possible if we omit the public statement in the calculation of the challenges and hence the proof `π`, that is referred to as the *weak* implementation of Fiat Shamir.
* On the other hand, if we want to stop the prover P (malicious or not) from calculating both `π` and `x` simultaneously we have to make sure that these values cannot be calculated independently. Hence, using the public statement `x` to generate the challenges and hence the proof `π` is called the *strong* implementation of Fiat Shamir.
5. The above points can be summarised by this picture:
1. 
6. Now to understand how weak FS implemetations affect PLONK proofs, we first go over the very basics of PLONK on a high level:
* PLONK has a constraint system that deals with addition, multiplication (and custom) gates
* This looks something like this:
* 
* We need two types of constraints for this system:
* Gate Constraints for Gate correctness
* Consistency Constraints for wiring correctness
* Now, the ultimate **verification equation** that must be satisfied for it to be a valid proof looks something like this:
* 
* Please take a note of the equation as well description of the various parts of it from the above photo
7. With an understanding of PLONK and weak FS, let's see how a typical attack would be carried out in this scenario:
* As a reminder in the weak FS implementation, the public inputs are NOT used to derive challenges
* We may then very well compute the proof first. This can be done because the challenges can be determined by the prover itself. Now the only thing that would remain is to set the *public input* in such a way that it makes the proof acceptable.
* Basically, we can arbitrarily choose any polynomial for the highlighted part of the equation:
* 
* All that is left to do now is solve for the public values PI = PI1, PI2, .... , PIk such that the equation is satisfied.
* Even this *calculation* is very easy to carry out because you have a high degree of freedom, ie, you can set ALL BUT 1 PIi to be arbitrary (from the list of public values).
* So essentially, if there are 500 public values or PIis available, you just have to choose one correct from them that satisfies the equation and the rest can be any random values that you like.
8. Did this look like a theoretical exercise? Well, it was not. Here's a real-life exploit that could have helped the attacker mint unlimited money:
* [Dusk critical PLONK security vulnerability](https://dusk.network/news/plonk-vulnerability-remediated)
* [Video Inspiration for the section](https://www.youtube.com/watch?v=RTSdkWZrEn4)
# Glossary
This page will be a quick lookup to clarify the jargon used in the industry. In my experience, I have often noticed that people already know a concept but they do not have the right word to encapsulate that or they use an alternative term and are therefore clueless as to what this \*new\* term means.\
\
This is the reason for this page to exist.
### B
1. Base Field
For the `secp256k1` curve, the base field `p` is
```
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
```
The base field of an elliptic curve is the field over which the curve is defined. The base field size thereby defines the number of elements of the finite field.
### S
1. Scalar Field
For the `secp256k1` curve, the scalar field `n` is:
```
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
```
The scalar field is the field of scalars used in the operations performed on the curve, such as point addition, scalar multiplication and pairings
Refer to the explanation of `Base field` for initial context.
# All About STARKs
This section contains notes, resources and research on the internal workings of a STARK proof.
# STARKs 101
A short walkthrough of how STARK proofs work
## STARK 101
### Ch1. Statement, LDE and Commitment
* Statement: There exists an *x* such that the 1023th ($$a\_{1022}$$) value of the *fibonacci square* sequence is 2338775057. The whole sequence is under prime $$P = 3221225473$$
* As the prover we know that the value of *x* is 3141592. However this value should not be leaked to the STARK verifier.
* LDE (Low Degree Extension): Helps encode our sequence/data. Done in 3 steps:
* Generate Input:
* This is what our data looks like: $$a\_0, a\_1, a\_2,...., a\_{1022}$$
* The above are the values of the first 1023 values in the fibonacci square sequence with the $$a\_0$$ and $$a\_1$$ set according to us (0 and 3141592)
* This is also called **the trace**. Because this is like the trace of the computation.
* Now we *choose* another sequence of numbers, say $$y\_0, y\_1, y\_2,...., y\_{1022}$$
* For our case we choose: $$1, g^1, g^2, g^3,..., g^{1022}$$ as the *y-values for the trace values to be plotted on a graph*
* 
* Interpolate Polynomial
* Interpolate a polynomial such that for each $$i$$, $$f(g^i) = a\_i$$
* This is what it looks like:
* 
* Extend
* Now, all you need to do is just evaluate the polynomial over a much larger domain as well.
* In our case, it would be 8 times the original domain
* In our case, the extended domain would look something like this: $${x\_i'} = w, w\.h, w\.h^2,...., w\.h^{8191}$$
* This is format of **Reed-Solomon encoding/codeword**.
* Just as a reminder, this photo is for intuition only as this graph is drawn over a real field and has a smooth curve. In reality since this plotting is being done over a prime field, it would NOT look like this.
* 
* Commitment: Now, we need to commit to our LDE.
* To do this simply send the Merkle Tree root of the tree generated by hashing together all the values of the polynomial evaluation in the extended domain. That would look something like this:
* 
### Ch2. Polynomial Constraints
1. These are the few things that we will use in this chapter from the last chapter:
* Trace - $$a$$
* Generator of G - $$g$$
* Trace Polynomial - $$f(x)$$
* The polynomial formed by the interpolation of the trace values.
2. Constraints on $${a\_n}$$ that needs to be satisfied in order to convince the verifier of our statement
* $$a\_0 = 1$$
* $$a\_{1022} = 2338775057$$
* $$a\_{n+2} = a\_{n+1}^2 + a\_n^2$$
3. So the thing that we are going for is doing a bunch of reductions of these constraints so that we get *another statement* which if we prove to be true, then goes on to imply that these 3 initial constraints are also true.
#### 2.1 Reduction 1
1. The first reduction is to convert the constraints on $${a\_n}$$ to constraints on the trace polynomial $$f(x)$$.
2. $$a\_0 = 1$$ is the same as saying $$f(x) = 1$$, where $$x$$ is $$g^0$$.
3. Similarly, $$a\_{1022} = 2338775057$$ can be thought of as $$f(x) = 2338775057$$ where $$x = g^{1022}$$
4. Lastly, the constraint $$a\_{n+2} = a\_{n+1}^2 + a\_n^2$$ can be converted to:
* $$f(g^2x) = f(gx)^2 + f(x)^2$$ for $$x = g^i$$, $$0 \leq i \leq 1020$$
5. This is all possible because of the way the trace polynomial was created. Just to jog thy memory, here's a photo:
* 
6. Finally, at the end of *Reduction 1*, this is the state of affairs:
* 
#### 2.2 Reduction 2
1. So, instead of saying $$f(x) = 1$$ for $$x = g^0$$, we could also reframe that as:
* $$f(x) - 1 = 0$$, for $$x = g^0$$
2. Similarly, $$f(x) - 2338775057 = 0$$, for $$x = g^{1022}$$
3. And lastly, $$f(g^2x) - f(gx)^2 - f(x)^2 = 0$$, for $$x = g^i$$, $$0 \leq i \leq 1020$$
4. So this basically means for the first constraint polynomial in this reduction, $$g^0$$ is a root
5. For the second constraint polynomial in this reduction, $$g^{1022}$$ is a root
6. For the last constraint polynomial in this reduction, $$g^i$$, $$0 \leq i \leq 1020$$ are the roots
7. Therefore, at the end of the second reduction this is the state of affairs:
* 
#### 2.3 Reduction 3
1. Given the theorem that if $$(x-z)$$ divides $$p(x)$$ then $$z$$ is a root of $$p(x)$$, the above reduction can be boiled down to the following:
2. $$g^0$$ is a root of $$f(x) - 1$$ can be written as:
* $$(f(x) - 1) / (x - g^0)$$ is a polynomial
3. $$g^{1022}$$ is a root of $$f(x) - 2338775057$$ can be written as:
* $$(f(x) - 2338775057) / (x - g^{1022})$$ is a polynomial
4. And finally the last constraint can be re-written as:
* $$(f(g^2x) - f(gx)^2 - f(x)^2) / \prod\_{i=0}^{1020}(x - g^i)$$
5. Regarding point 4, the denominator is extremely inefficient and it has like 1021 roots and it's multiplication would be very hard for a computer. So, we do a couple of heavy optimizations.
6. $$\prod\_{i=0}^{1023}(x-g^i)$$ can be written as $$x^{1024} - 1$$
7. ^^This polynomial is much easier to compute.
8. Now notice there is a difference in the $$i$$ values of pi. So to make it equivalent to $$p\_2x$$ we divide the polynomial in 6 by the added $$i$$ value polynomials.
9. Then the final state of affairs after reduction 3 is the following:
* 
#### A few more adjustments
1. Now we have established that we do not need to care about the initial constraints and all we need to do to prove our statement is to show that:
* $$p\_0(x)$$,$$p\_1(x)$$,$$p\_2(x)$$ are polynomials
2.
```
```
3. Now instead of showing 3 different rational functions to be polynomial, we can do the process once and for all.
4. Let's take a random linear combination of these three rational functions. That looks something like this:
* $$CP = \alpha\_0.p\_0(x) + \alpha\_1.p\_1(x) + \alpha\_2.p\_2(x)$$
* Where all the $$\alpha$$ are random field elements
* We call it the composition polynomial
* Luckily we have another theorem which states with very high probability that:
* $$CP$$ is a polynomial $$\iff$$ all $$p\_i$$'s are polynomials
#### Lastly
1. **Commit to the CP using the Merkle Tree**
### Ch3. FRI Commitments
1. The goal here is to show that $$CP$$ is a polynomial which in turn will prove that all the constraints are satisfied and our initial statement was true.
2. And ofc, we won't prove what we want to prove.
* We won't prove that $$CP$$ is a polynomial
* We will prove that $$CP$$ is **close** to a **polynomial** of **low degree**.
3. Now, let us define what *close* and *low degree* mean.
4. **Low degree** is some agreement between the prover aand the verifier on some bounded degree that the polynomial is bounded by.
5. To understand **Close**, let us first understand distance.
* The distance between function $$f$$ and polynomial $$P$$ is the number of points where $$f(x) \neq p(x)$$
* For example, here the $$f(x)$$ and $$p(x)$$ disagree on 5 points, so the distance between them is 5.
* 
* So, a function $$f$$ is close to a polynomial $$p$$ if $$D(f,p)$$ is small.
6. Our goal is to prove that the $$CP$$ is close to a polynomial of low degree. AND WE ACHIEVE THAT VIA **FRI** PROTOCOL.
* FRI stands for Fast Reed-Solomon Interactive Oracles Proof of Proximity
#### 3.1 FRI - The Protocol
* Receive random $$\beta$$
* Apply the FRI operator
* Commit (the resulting polynomial)
Repeat the above steps again and again until
* lastly the prover sends the result
* at the stage where the degree has been reduced to the *low* degree agreed upon by the prover and verifier
* The FRI operator functions (broadly) on the following principle:
* 
#### 3.2 FRI Steps Overview
* 
* As you can see above, $$CP(x)$$ keeps on getting halved until we have to prove $$deg(CP\_{10}) < 1$$ and Domain is also less (8).
* The verifier stops sending random $$\beta$$ values now since a polynomial that is bounded by degree 1 is actually a constant.
#### 3.3 Deep dive into the FRI operator
1. Each polynomial $$P(x)$$ can be split into an even and odd part like this:
* $$P(x) = g(x^2) + xh(x^2)$$
2. Here's an example of the split $$P\_0(x) = 5x^5 + 3x^4 + 7x^3 + 2x^2 + x + 3$$
3. It will be split into $$g$$ and $$xh$$ in the following fashion:
* $$g(x^2) = 3x^4 + 2x^2 + 3$$
* $$xh(x^2) = 5x^5 + 7x^3 + x$$
4. Now we receive the random $$\beta$$. This is what convinces the verifier that the prover didn't cheat, bc this can convince the verifier that the prover did not calculate the values in advance.
5. Now the new function will be:
* $$P\_1(y) = g(y) + \beta h(y)$$
* Now $$g(y) = 3y\_2 + 2y + 3$$
* And $$h(y) = 5y\_2 + 7y + 1$$
* So, $$P\_1(y) = (3 + 5\beta)y^2 + (2 + 7\beta)y + 3 + \beta$$
6.
```
```
7. As you can see in point 6, the bounded degree decreased from 6 to 3. We will keep on going like this until we reach an upper degree bound of 1.
8. Therefore, $$deg(P\_1) \leq deg(P\_0)/2$$
### Ch4. The Proof
1. Up until now, we created a trace polynomial and commited to the trace root (Ch1)
2. Then we did some reductions on the original requirements on the trace and created the Composition Polynomial. We then committed to the CP root.
3. Then in Ch3 we applied the FRI protocol to prove that CP was close to a polynomial of a low-degree and we committed each layer of FRI, ie, $$CP\_1$$ Root, $$CP\_2$$ Root, ...., $$CP\_{10}$$ Root.
4. This is what we have sent so far to the verifier from the prover's side. This is called the **Commitment Phase**.
5. The *second part of the proof* is called **Decommitment** or actually trying to convince the verifier that every calculation and commitment made so far was truthful and not false.
6. Now how this would work out is, that the *verifier* will send $$q$$ random elements and the prover will provide a *validation data* for each.
7. So, the first thing that needs to be proven by the prover to the verifier is the correct transition from **trace polynomial** to **Composition Polynomial**.
* For that, the prover will send $$f(x)$$, $$f(gx)$$, $$f(g^2x)$$ for a given $$x$$.
* This is enough information for the verifier to themselves calculate $$CP\_0(x)$$, based on the formula below
* 
8. Now the next thing that needs to be proven to the verifier is the transition between each FRI layer. That is done via the following approach:
* $$CP\_{i+1}(x^2) = g(x^2) + \beta h(x^2)$$
* And both $$g(x^2)$$ and $$h(x^2)$$ can be calculated only via $$CP\_i(x)$$ and $$CP\_i(-x)$$ like this:
* 
* Therefore, the verifier can computer $$CP\_{i+1}(x^2)$$ by only getting $$CP\_i(x)$$ and $$CP\_i(-x)$$ from the prover
9. Assuming that step 8 is clear, then the prover will send the value of $$CP\_1(-x^2)$$ and from that value and from the $$CP\_1(x^2)$$ calculated in step 8, the verifier will be able to check the value of $$CP\_2(x^4)$$ and on and on until $$CP\_{10}$$.
10. The prover is sending out these elements such as $$f(x)$$, $$f(gx)$$, $$f(g^2)$$, but remember we did not commit these individual elements but rather the hash of the merkle tree root, so how do we convince the verifier that we did indeed commit these elements into the Merkle tree?
* So, the prover sends the verification path from the element to the Merkle tree to convince the verifier. This is called decommitment and looks something like this:
* 
11. Now, the question is How Much data does the prover send to the verifier to convince him?
* 
* So, if you look at the left side (commitment), we are sending order of $$log(n)$$ elements in the commitment phase and then for a single query $$q$$, we are sending order of $$log(n)$$ path (from Merkle leaf to root). So, overall complexity is $$O(log^2n)$$
* Now, for $$q$$ different queries, we need to send data in order of: $$q \* O(log^2n)$$. But since $$q$$ is constant, the data remains of order $$O(log^2n)$$.
**NOW AFTER ALL THIS SHENANIGANS, the VERIFIER IS CONVINCED THAT THE PROVER'S INITIAL STATEMENT ABOUT THE 1023rd VALUE OF THE SEQUENCE IS TRUE**.
# 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 *quasi*linear 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
*
```
```
*
```
```
```
6. 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
7. 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
*
8. 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.
9. **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
```