Step1. Build trace （fib2-example）

The red part is Public info

Step2. Prover for Trace

Protocol parameter selection:

1. AIR instantiation

secondary title

2. Verify the consistency of AIR and Trace (Debug mode)

2.1 Verify basic parameters

2.3 Verify that Trace meets transition cs (Debug module)

Transcript

3.Commit for trace

Domain parameter selection:

3.1 Interpolate -> LDE -> evaluate over LDE-domain

3.2 Commitment

Tracescript

4.Evaluate CS

secondary title

4.1 Get linear combination coefficient

The number of coefficients is the same as the number of constraints

In this example (fib2-example), transition cs 2; boundary cs 3

4.2.1 t-cs

4.2.2 b-cs

4.3 Evaluate t/s-cs over ce_domain

4.3.1 Define evaluator table

5 Commitment to Evaluate CS

secondary title

5.2 commitment to composition poly

Example:

Compose_poly = a * x^3 + b * x^2 + c * x + d = (a * x^2 + c) * x^ + (b * x^2 + d)

(a * x^2 + c),(b *x^2 +d) corresponds to two columns respectively

secondary title

The general formal: f(x) = q(x)* t(x)

Need check at random z

1. f(z) = q(z) * t(z)

2. f(x),q(x),t(x) indeed equal respectively f(z), q(z), t(z)

3. calculate Deep_composition = (q(x) - q(z)) / (x - z)

4. Check LDT for q_q(x)

6.1 select z which out of domain(ood)

draw an out-of-domain point z. Depending on the type of E, the point is drawn either from the base field or from an extension field defined by E.

The purpose of sampling from the extension field here (instead of the base field) is to increase security.

6.2 evaluate trace and constraint polynomials at the OOD point z

6.2.1 trace_poly at z & z * g

6.2.2 composition poly at z

6. Establish DEEP composition polynomial

6.3.1 Generating random numbers

6.3.2 cal quotient poly

6.4 evaluate Deep over LDE

7. Calculate Deep's FRI Layer num

secondary title

Select multiple query locations from lde_domain.

secondary title

9. Build the proof object

9.2 query trace poly at above positions

9.1 Generate FRI proof

9.3 query constraint poly at above positions

similar to above

9.4 Building STARK PROOF

Step3. Verify for proof

Read pub-info from transcript to obtain related data to perform verification process.

1. Ood consistency check

Verify the consistency of the mathematical relationships described in Section 5.2.

2. Instantiate the FRI-verifier object

secondary title

The calculation method is the same as in Chapter 6.4

Sin7y was established in 2021 and is composed of top blockchain developers. We are both a project incubator and a blockchain technology research team, exploring the most important and cutting-edge technologies such as EVM, Layer2, cross-chain, privacy computing, and autonomous payment solutions.

about Us

Sin7y was established in 2021 and is composed of top blockchain developers. We are both a project incubator and a blockchain technology research team, exploring the most important and cutting-edge technologies such as EVM, Layer2, cross-chain, privacy computing, and autonomous payment solutions.

WeChat public account: Sin7Y

GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon