Author: shuangcrypto.com

Stark can be described in 5 steps in a high level:

1. Computation program
2. generate an execution trace and a set of polynomial constraints, AIR (Algebraic Intermediate Representation) (no circuit)
3. Transfer the execution trace to be a polynomial, extend it to a larger domain
4. compute the composition polynomial, which is the

…

1. prover commit to \(f(x)\)

$$f(X)=f_E(X^2)+X\cdot f_O(X^2)$$

if we take an intermediate variant \(Y\) to replace the \(X^2\)

With a fixed \(Y\), then \(f(x)\) can be considered as one degree polynomial for \(X\), as

$$f(X)=f_E(Y)+X\cdot f_O(Y)$$

and for a given \(y\), it determineds a unique line (one degree polynomial)

and the …

Building blocks

Vector Commitment on elliptic curve, useful for its additive homomorphic

Statement

$$\{(\textbf{g,h}\in \mathbb{G}^n, P \in \mathbb{G}, c \in \mathbb{Z}_p; \textbf{a,b}\in \mathbb{Z}_p^n): P=\textbf{g}^{\textbf{a}}\textbf{h}^{\textbf{b}} \wedge c=<\textbf{a},\textbf{b}>\}$$

Proving

the strategy is recursive proof. For every recursive step, keep the public statement in the same format, but the vector length, together with …

Plonk argument of knowledge can be described in 5 steps in a high level:

1. Computation
2. Arithmetic circuit
3. Constrain System
4. Transfer the constrain system to polynomial
5. Prove gate constraints are satisfied.
6. Prove permutation constraints are satisfied.

Constrain System in Plonk (Plonkish constrain system)

The constraint system in Plonk is

$$(\textbf{q}_{\textbf{L}_i} )\cdot …

Question 1:

There are two list \((a_1, a_2, a_3,…a_n)\) and \((b_1,b_2,b_3,…,b_n)\)

how can we prove they contain the same element? (now we only consider to have the same elements, permutation comes in next question) This question would help you to understand why the permutation construction in Plonk is constructed in …