Revealing The All Mysterious zk-STARKs

Published in

Coinmonks

9 min readDec 23, 2019

“In this post, will try to minimize the mathematical formulas and make it as easy to understand as possible.”

People say STARKs is a new generation of SNARKs. Not only because it’s faster, the most important due to these 2 qualities:
1. Trusted setup is not required with STARKs, and
2. They are Quantum-resistant

However, STARKs are not perfect and come at a cost: the size of proof. The proof size of a STARK is about 40–50KB compared to SNARKs, which are only 288 bytes in size. Additionally, STARKs are relatively new — it’s only been around two years since the original concept was published. We may still need some more time to verify their voracity.

In STARKs, S stands for ‘Scalable’. With the T standing for Transparency, STARKs resolves one of the major weaknesses of SNARKs, “trusted setup”.

STARKs don’t rely on Elliptic-curve cryptography and pairings and they use simpler cryptographic assumptions like hashes. This means STARKs don’t need a trusted setup and are resistant to attackers with quantum computers.

SNARKs and STARKs are both based on polynomial verification. The difference is how to hide secrets, how to verify succinctly, and how to achieve non-interaction.

Let’s have a quick review on how SNARKs works.

Alice has a polynomial P(x), Bob has secret s.
The goal is,
Alice doesn’t know s, Bob doesn’t know P(x) but Bob could verify P(s). Hiding the secret, s, by ‘Homomorphic Hindins’ , s → H(s), succinct verification by QAP/Pinocchio and put H(s) in CRS (Common Reference String) to achieve non-interaction. Read my previous post for more details (sorry… it’s Chinese).

Conversion

The first step in zero knowledge proof is to turn the posited “question” into a polynomial. This section will only explain how to turn the questions into polynomials. As for the details of how to convert, I won’t be explaining too much here.

Questions → Constraints → Polynomials

Both SNRAK and STARK are based on high-dimensional polynomials. If the polynomial is: x³ + 3x² + 3 = 0, the solution of the polynomial can be easily guessed. If the polynomial is x ^ 2000000 + x ^ 1999999 +…, the difficulty will be much higher.

The first step is to convert the question into a polynomial.
I will be using a Collatz Conjecture as an example here. What is a Collatz Conjecture?
1. If the number is even, divide by 2
2. If the number is odd, multiple by 3 and plus 1.(3n+1)

Any positive integer, followed by the two rules above, will end up with 1. Take 52 as an example,
52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

Recording the results of each operation. This is called the execution trace, as 52-> 26->…-> 1 above. Then we convert the execution trace into a polynomial as follows (the conversion from the execution trace to a polynomial is not the focus here. For details, refer to this article by StarkWare)

https://medium.com/starkware/arithmetization-i-15c046390862

Composition Polynomial

Then the above four polynomials with the limiting conditions are combined into one, and the final one is called “composition polynomial,” and this polynomial is the polynomial to be verified later.

As mentioned at the beginning, both SNARKs and STARKs use high-dimensional polynomials. Then, we will introduce the ways in which STARK achieves zero-knowledge information exchange, transparency, and scalability.

Degree Adjustment

This step is prepared for later verification. We adjust the highest degree of constraint polynomial to 2^n. If the highest degree isn’t a power of 2, up to the nearest power of 2 greater than the highest degree.

Assume that each constraint polynomial (not the composition polynomial) is Cj (x), the degree is Dj, D >= Dj and D is equal to 2 ^ n. In order to reach the D degree, multiply these polynomials by degree (D-Dj) ,

The result of composition polynomial would be

aj、βj are provided by the verifier. So, the composition polynomial is made by the prover and the verifier.

*Point of this section is to adjust the polynomial to the D (power of 2) degree. You can skip the process if you don’t understand…

FRI

FRI is a short name for ”Fast RS IOPP”（RS = “Reed-Solomon”, IOPP = “Interactive Oracle Proofs of Proximity”）. FRI enables verification to be succinct. Before introducing FRI, let’s first discuss how to prove that you know the polynomial f(x)?

RS Erasure Code：

The erasure coding is to extend the original data so that it makes data fault-tolerant. The way to achieve this is to encode all the data as a polynomial, and verifying the polynomial. For example, if you have two points, you can make a line, then pick out 3 points on the line. Any 2 of these 3 points can reconstruct the original one. Assuming that there are d points that we can construct a d-1 degree polynomial y = f (x). Verify that z1 is the correct data by verifying f (z1)? = Y.

Back to the question above, how do you prove that you know the polynomial? The most direct way is to calculate all the roots. By erasure coding, assuming d + 1 points, according to Lagrange interpolation, a d-degree polynomial h (x) can be constructed. If two polynomials are the same at any point d (within a range) (f (z) = h (z), z = z1, z2 … zd), then means I know f (x). But we are faced with a high-dimensional polynomial, d is 1–2 million, such tests are inefficient and not feasible. FRI solves this problem, taking the number of verifications from few millions to dozens.

Decrease Complexity

Assume that the composition polynomial is f (x), and reduce the degree of the polynomial by finding a bivariate polynomial to represent the original one. Suppose f (x) = 1744 * x ^ {185423}, and we find y, so that y = x ^ {1000}. The polynomial can be rewritten as g (x, y) = 1744 * x ^ {423} * y ^ {185}. In this way, the degree from 100,000 has been reduced to 1,000, and the degree of the polynomial has been greatly reduced by this way. The current implementation in StarkWare is power of 2, so y = x² (f (x) = g (x, x²)).

Another tactic we use here is to split a polynomial into two smaller degree polynomials. We split into odd and even coefficients of polynomial,

f(x)= g(x²) + xh(x²)

For example,

f(x) = a0 + a1x + a2x² + a3x³ + a4x⁴ + a5x⁵
g(x²) = a0 + a2x² + a4x⁴, （g(x) = a0 + a2x + a4x²）
h(x²) = a1x + a3x² + a5x⁴, （h(x) = a1 + a3x + a5x² ）

With these two skills, the complexity goes down by a factor of 2 each time. The FRI protocol consists of two phases, commit phase and query phase.

Commit Phase：
The commit phase is the same as the aforementioned description. Every time the polynomial is disassembled, a random number is provided by the verifier and then form a new polynomial. Repeat the process again and again.

f(x) = f0(x) = g0(x²) + x*h0(x²)
==> f1(x) = g0(x) + α0*h0(x), ← α0（provided by verifier）
==> f2(x) = g1(x) + α1*h1(x), ← α1（provided by verifier）
==> . . .

Query Phase：
This phase is to verify the polynomials, f0(x), f1(x), f2(x), … , provided by the prover. The verifier sample z and query f(z) and f(-z) (The domain need to satisfy L²= {x²：x ∊ L}. Not explain here.). So, we can have,

f0(z) = g0(z²) + z*h0(z²)
f0(-z) = g0(z²) -z*h0(z²)

The verifier can know g0(z²)、h0(z²) by solving the equations, and the calculate f1(z²), then f1(x) and so on.

With FRI (RS Erasure Codes, IOPs), the number of verifications has been reduced from millions to 20–30 times (log2 (d)), which makes verification succinct. We solved the complexity problem, but we still have interaction issue!

* Compared to SNARKs： QAP and Pinocchio are used for verification in SNARKs.

Non-Interaction

We use Micali construction to explain how to achieve non-interactive verification. Micali construction consists of two parts, PCPs (Probabilistically checkable proof) and hash function. PCPs is a type of a proof system with a random local check. In other words, the prover produces a long proof (which is a large amount of data), and the verifier checks by random sampling. The process looks like this: the prover produces the proof 𝚿, and the verifier randomly check n points.

Our goal here is to have :
1. a small proof,
2. non-interaction.

Random sampling help achieve a small proof but what about the interaction? The idea is very simple, that is, pre-sampling. We pre-sample a short proof from 𝚿, and the short one is on behalf of the original proof, 𝚿, sent to the verifier. The prover is of course not the candidate to pre-sample obviously. To solve this problem, we use Fiat-Shamir Heuristic to pre-sample.

First, constructing a merkle tree by the proof 𝚿, and then hashing the merkle root to get a random number 𝛒, where 𝛒 is the index for pre-sampling. Put the small chunk chosen by 𝛒 and the merkle path of the chunk and the merkle root together and we call this combination is 𝛑 which is a STARK proof.

Until now, only hash algorithms, a cryptographic lightweight algorithm, have been used. The selection of the hash function is the only global parameter of this proof system (everyone needs to know), unlike SNARK, which has global secret parameters such as (α, β, 𝛾) used by KCA, using HH(Homomorphic Hidings) to hide these secrets and then generate the CRS. Because this proof system is based on a public hash function, it does not require a pre-generated secret. Therefore, STARK can achieve transparency and without the need of a trusted setup.

Then, using PCPs and Fiat-Shamir Heuristic to replace the interactive part of FRI (value α provided by verifier). We can achieve non-interaction.

*Compared to SNARKs: The non-interaction of SANRK is to put the global parameters into the CRS. Because values in the CRS are public, HH is required to hide the secrets.

MIMC

No matter SNRAKs or STARKs, the need to convert the polynomial to arithmetic circuits remains. So, the complexity of the circuit is crucial — it’s relative to the time of proof generation and verification. MiMC is used as the hash function in STARKs, its circuit complexity is simpler. This is how it works,

https://vitalik.ca/general/2018/07/21/starks_part_3.html

MiMC has some very useful characteristics: difficult to compute, easy to verify, and non-parallelizable to compute. Those fulfill the primary goals of VDFs (Verifiable Delay Functions). Here is a proposal to use MiMC to be a VDF candidate by Vitalik.

Final Thoughts:

Computing the MiMC circuit backwards takes about 100 times longer to compute than the forward direction.

From the explanation above, we can understand why STARK does not need a trusted setup, but why it is quantum-resistant? HH is used in SNARK to hide secrets, and HH relies on the elliptic curve, but the elliptic curves are not quantum-resistant (which means private keys can be derived from public keys).

STARKs only use hash functions in their entire process, and currently there are no effective algorithms to crack hash functions — so as a result, STARKs are understood to resist quantum attacks.

Any feedback or mistakes that need correcting are welcomed.

References：
StarkDEX Deep Dive: the STARK Core Engine
Starkware’s series：
- STARK Math: The Journey Begins
- Arithmetization I
- Arithmetization II
- Low Degree Testing
- A Framework for Efficient STARKs
Vitalik’s series：
- STARKs, Part I: Proofs with Polynomials
- STARKs, Part II: Thank Goodness It’s FRI-day
- STARKs, Part 3: Into the Weeds
ZK-STARKs — Create Verifiable Trust, even against Quantum Computers
https://ethereum.stackexchange.com/questions/59145/zk-snarks-vs-zk-starks-vs-bulletproofs-updated

Join Coinmonks Telegram Channel and Youtube Channel learn about crypto trading and investing