Starky

Currently, a zero-knowledge proof system consists of modules such as arithmetic, constraint systems, and polynomial commitment patterns. This proof system uses the same finite fields and hash functions as Plonky2, but without computationally heavy arithmetic. Arithmetic and constraint systems in Starky use air. That is to say, the calculation process of the program is represented by several strict tables, and there are predefined constraints between the rows and columns of each table, which are the same as the constraints between different tables. The polynomial commitment scheme in Starky is DEEP-FRI, a non-interactive protocol proving that a commitment polynomial has bounded degree.

STARK table generation

Programs in ZK World will generate multiple original tables after execution. Currently there are several tables, such as CPU, memory, bit, range check, CMP, etc.

Different tables define different numbers of columns for storing data such as raw data, fixed data, auxiliary data. The values of some columns will be determined when the program is executed, and the values of the remaining columns need to be calculated using the program execution results. When all cells of the strict table have values, We get the full star tables, then we can use FFT to interpolate each column in each table to a polynomial.

The operation process of each table is as follows:

1. Iterate each row in the table and calculate the values of all columns related to the instruction;

2. Calculate the value of the column related to the permutation parameter;

3. Calculate the value of the column related to the lookup;

4. Use FFT to interpolate all columns to the polynomial;

5. Return the column polynomial array and common input.

Starky proof generation

Once we have the polynomial arrays and public inputs for each table as shown, we can start the proof process. Each table in the beginning must generate a ZK-STARK proof separately. The proof process for each table is as follows

1. Calculate polynomials and commitments.

(a) generate a Merkle commitment from a purely tabular polynomial;

(b) Divide instances of permutation parameters into batches, each batch generating a polynomial Z(X);

(c) Compute the Z(X) polynomial for the crosstab lookup:

(d) Generate Merkle commitments from all Z(X) polynomials above.

1. Use the tracking polynomial and the Z(X) generator polynomial:

3 Divide the quotient polynomial into small polynomials whose degree is the quotient subfactor;

4. Generate a Merkle commitment from the quotient polynomial;

5. Calculate the three points that challenge ζ, g·ζ and the last point gn −1 are in group H;

6. Open the challenge points on the polynomial respectively to get the opening; (a) point ζ is opened

Subarge tracking polynomial Permutation and Lookup Polynomials Across Tables sand scab quotient polynomial (b) Point g·ζ is opened Subarge tracking polynomial Permutation and Lookup Polynomials Across Tables (c) Point gn −1 is only open on Crosstab Lookup Polynomial

1. Generate the final polynomial;

(a) compress the polynomial opened at each point into a polynomial

Fi(X) =工αj· fij,i ∈ [3]

(b) Compute the Fi(X) quotient above, where z ∈ {ζ, g ζ, gn −1}

(c) Compress all points to Qi(X) to get the final FRI polynomial

Final (X)=work αkQi(X)

1. Generate the FRI proof of the final polynomial fri_proof;

2. Finally, a single distinct proof is obtained, consisting of the following parts

Sand Scab Microcaps

• permutation_ctl_zs_cap

Shabab Quotient Cap

Shagui Garden opens

• fri_proof

1. Rigorous proofs of all distinct tables and public inputs are converted into final proofs of the program, called star proofs.

There are now a total of 3 Merkel pledges

1. Merkle commitment to track polynomials;

2. A Merkle commitment of the permutation_ctl_zs polynomial;

3. Merck commitment for quotient polynomials.

strict validation

Proving the correct execution of the ZK World program requires verifying the rigorous proof generated in Figure 6.1.2. Validation mainly includes that each table proves to be valid and the cross-tab constraints between different tables are correct. The technological process of this project is as follows:

1. Obtain all challenges that produce a distinctive proof;

2. Obtain the number of Z polynomials in the permutation parameter;

3. Generate the data needed to validate the Z polynomial for the crosstab lookup;

(a) the values of the Z polynomial for ζ and the Z polynomial for g ζ on each table generated; (b) Generate the β, V required to generate the Z polynomial; (c) Columns and selectors for crosstab lookups.

1. Verify each distinct piece of evidence separately.

(a) Check that the number of polynomials and the strictly proven cap_height are valid; (b) Get the values of 3 points (ζ, g ζ and gn −1) open to column polynomials; (c) calculate the constraint value on the above-mentioned three points, arrange the parameter and the value of cross table lookup polynomial; (d) Check quotient (ζ) · Z_H(ζ) = disappearance (ζ); (e) Check whether the FRI proof is valid.

FRI

FRI is a protocol that proves a commitment polynomial with bounded degree, using Deep-FRI as its polynomial commitment model Figure 72 simply expresses the calculation process of FRI, anyone can read Deep-FRI [8] for more details.

benchmark

Many optimizations have not been applied yet, and we expect to see more performance improvements as we invest more time in optimizing. The benchmarks below should only be used as rough guides for expected future performance.

In the benchmark below, a VM executes the same Fibonacci calculator program for 20 loops at a target security level of 100 bits on an advanced 64-core CPU.