# Sin7Y Tech Review (25): STARK - An Indepth Technical Analysis ![](https://i.imgur.com/3u2vXKD.png) ## Step1 - Build trace （fib2-example） | <span style="color:red">1</span>| <span style="color:red">1</span> | | -------- | -------- | | 2 | 3 | |5 |8 | | 13 | 21 | | 34 |55 | | 89 | 144 | | 233 |377 | |610 | <span style="color:red">987</span> | The numbers marked in <span style="color:red">red</span> are public info ``` Some assertion: Form: [register, step, value] examples: [0,0,1], [1,0,1],[1,7,987] ``` ## Step2 - Prover for Trace Selection of the protocol parameter: ``` pub struct ProofOptions { num_queries: u8, // number of queries to increase reliability blowup_factor: u8, // domain extension factor grinding_factor: u8, // ？nonce security parameter, for the security selection of query position hash_fn: HashFunction, // Hash Function blake3-259/192, sha3-256 field_extension: FieldExtension, // Whether the field extension is conducted fri_folding_factor: u8, // The folding factor of Fri protocol 4-8-16 fri_max_remainder_size: u8, // The max remainder of Fri protocol } ``` ### 1. AIR Instantiation ``` FibAir { context: AirContext::new(trace_info, degrees, options), result: pub_inputs, } AirContext { options, // protocol parameters trace_info, // trace parameters: row number and col number transition_constraint_degrees, // transition the constraint degree, and if the multiplication of two registers is involved, then degree = 2; similarly, if the multiplication of three registers is involved, then degree = 3; if periodic column exists, then degree = base + period.length – 1 ce_blowup_factor, // constraint computational domain extension factor trace_domain < ce_domain < lde_domain trace_domain_generator: B::get_root_of_unity(log2(trace_length)), lde_domain_generator: B::get_root_of_unity(log2(lde_domain_size)), } ``` #### 2. Verify the consistency of AIR and Trace (Debug module) #### 2.1 Verify basic parameters ``` Trace.width = air.trace_width ``` #### 2.2 Verify the validity of assertion (boundary cs) ``` Trace[assertion_i.register][assertion_i.step] = assertion_i.value ``` #### 2.3 Verify if Trace holds transition cs（Debug module） ``` Loop: For every two adjacent rows: pub struct EvaluationFrame<E: FieldElement> { current: Vec<E>, next: Vec<E>, } Holds: next[0] == cur[0] + cur[1] next[1] == next[0] + cur[1] The number of times of Loop: Trace.length - 1 ``` #### Transcript ``` write.into(air, public info) ``` ### 3. Commit for trace Domain parameter selection: ``` StarkDomain { trace_twiddles, /ntt twiddle factor ce_domain_size: air.ce_domain_size(), //constraint computational domain ce_to_lde_blowup: air.lde_domain_size() / air.ce_domain_size(), // LDE domain domain_offset: air.domain_offset(), //domain offset } ``` #### 3.1 Interpolate -> LDE -> evaluate over LDE-domain ![](https://i.imgur.com/yTogPgb.png) #### 3.2 Commitment ![](https://i.imgur.com/LDJhVo5.png) #### Transcript ``` write.into(cm_to_trace) ``` ### 4.Evaluate CS #### 4.1 Obtain Linear Composition Coefficients ``` Ok(ConstraintCompositionCoefficients { transition: t_coefficients, boundary: b_coefficients, }) ``` The number of coefficients is consistent with that of constraints In this example (fib2-example), there are 2 transition cs and 3 boundary cs. #### 4.2 Establish the evaluator for t-cs and b-cs ##### 4.2.1 t-cs ``` 1. Obtain the degree of t-cs (In this example, the degree is [1,1], refer to Chapter 2.3) 2. Establish the t-cs group (record the parameters needed for reaching the object of degree -> compose degree（ce_domain_size - 1） Loop: Calculate the evaluate-degree = base * （trace.length - 1） + tracce.length / period.cycle *(period.length - 1) of every t-cs Establish the t-cs group according to the degree: TransitionConstraintGroup { degree, // the degree of t-cs degree_adjustment, // The space to reach the object degree, target_degree = composition_degree + trace_poly_degree(vanish poly-degree), degree_adjustment = (target_degree - evaluation_degree) indexes: vec![], coefficients: vec![], } Record index and distribution coefficient “coef” Cycle each t-cs (In fib2-example, cycle twice) 3. Establish the period value table 4. Set the divisor for t-cs, with all t-cs having the same form z(x) = x^n-1 / x - g^{n-1} // The last value does not satisfy the condition ``` ##### 4.2.2 b-cs ``` 1. The divisor of each b-cs is not necessarily the same 2. Judge that if the number of assertions is the same as the number of coefficients to be distributed assertion.len() == coefficients.len() 3. Establish the b-cs group Loop: Obtain the type and initial step of the assertion Establish the b-cs group BoundaryConstraintGroup { constraints: Vec::new(), divisor, // The divisor corresponding to the boundary degree_adjustment, target//The space to reach the object degree, target_degree = composition_degree + divisor.degree()，degree_adjustment = (target_degree - trace_poly_degree) } Add b-cs forms air::BoundaryConstraint { register: assertion.register, // Corresponding register index poly, // assertion value polynomial, interpolation is required for multiple values; otherwise, it is a single value poly_offset, //offset information. If the assert is in the first step, it is [0,1], otherwise it is [1, T] cc, // Coefficient distributed to this b-cs } prover::BoundaryConstraintGroup { degree_adjustment: group.degree_adjustment(), single_value_constraints: Vec::new(),// corresponding Sigle value assertion small_poly_constraints: Vec::new(),//assertion whose assertion value num is smaller than 63 large_poly_constraints: Vec::new(),//assertion whose assertion value num is larger than 63, the values in ce_domain are needed to conduct Pre_compute }; ``` #### 4.3 Evaluate t/s-cs over ce_domain ##### 4.3.1 Define evaluator table ``` ConstraintEvaluationTable<B: StarkField, E: FieldElement<BaseField = B>> { evaluations: Vec<Vec<E>>, //[ce_domain_size][t_cs_merge_value (0): b_cs_values(1...)] divisors: Vec<ConstraintDivisor<B>>, // [t-cs divisor, b-cs divisor] domain_offset: B, trace_length: usize, #[cfg(debug_assertions)] t_evaluations: Vec<Vec<B>>, #[cfg(debug_assertions)] t_expected_degrees: Vec<usize>, } evaluations[step_i][0] += sum_{j}(evaluation[j] * (coefficients.0 + coefficients.1 * xp) // The divisor is identical. evaluations[step_i][j] += (evframe.cur().state[register] - value) * (coefficients.0 + coefficients.1 * xp) // for single assertion evaluations[step_i][j] += (evframe.cur().state[register] - polynom::eval(&self.poly, x * self.x_offset)) * (coefficients.0 + coefficients.1 * xp) // for multiassertion // for multi-assertion evaluations[step_i][j] += (evframe.cur().state[register] - self.values[values_index]) * (coefficients.0 + coefficients.1 * xp) // for multiassertion // for multi-assertion large poly ``` ### 5. Commitment to Evaluate CS #### 5.1 Establish constraints composition polynomial ![](https://i.imgur.com/4LQ5jqP.png) #### 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) and (b *x^2 +d) correspond to two columns, respectively. ![](https://i.imgur.com/UFMx9gj.png) ### 6. Establish DEEP composition polynomial 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 | <span style="color:red">1</span>| <span style="color:red">1</span> | | -------- | -------- | | 2 | 3 | |5 |8 | | 13 | 21 | | 34 |55 | | 89 | 144 | | 233 |377 | |610 | <span style="color:red">987</span> | | trace_poly_0 |trace_poly_1 | ``` ood_frame = {cur: [trace_poly_0(z), trace_poly_1(z)], next: [trace_poly_0(z * g), trace_poly_1(z * g)]} ``` ##### 6.2.2 composition poly at z ``` iter!(self.columns).map(|p| polynom::eval(p, z^m)).collect() // m is the column num of the composition poly ``` #### 6.3 Establish Deep composition polynomial ##### 6.3.1 Generate random numbers ``` pub struct DeepCompositionCoefficients<E: FieldElement> { /// Trace polynomial composition coefficients $\alpha_i$, $\beta_i$, and $\gamma_i$. pub trace: Vec<(E, E, E)>, /// Constraint column polynomial composition coefficients $\delta_j$. pub constraints: Vec<E>, /// Degree adjustment composition coefficients $\lambda$ and $\mu$. pub degree: (E, E), } ``` ##### 6.3.2 cal quotient poly ``` => for trace polynomial T`(x) = alpha * (T(x) - T(z)) // degree = trace.length - 1 T``(x) = beta * (T(x) - T(z * g)) T```(x) = gamma * (T(x) - T(z_conjugate)) merge_trace_composition_poly = T(x) / (x - z) + T``(x) / (x - z * g) + T```(x) / (x - z_conjugate) Degree = trace.lengh - 2 => for composition polynomial compute H'_i(x) = (H_i(x) - H_i(z^m)) / (x - z^m) sum(H`_i(x) * cc_i) Deep_composition_polynomial = merge_trace_composition_poly + sum(H`_i(x) * cc_i) Degree = trace.length - 2 => Deep_composition_polynomial degree adjustment Deep_composition_polynomial = Deep_composition_polynomial * (cc_0 + x * cc_1) Degree = trace.length – 1 ``` #### 6.4 Evaluate Deep over LDE ``` deep_evaluations<lde_domain_size> = deep_composition_poly.evaluate(&domain); ``` ### 7. Calculate the FRI Layer num of Deep ``` trace.length() = fold_factor ^ Layer_num + remainder_size; fold_factor = {4, 8, 16} remainder_size < remainder_max_size == 256 ``` ![](https://i.imgur.com/k3m21If.png) ### 8. Determine positions of the query Select multiple positions of the query from lde_domain. ``` fold_position = source_position % (fold_domain) fold_domain = source_domain / fold_factor ``` ### 9. Establish proof objects #### 9.1 Generate FRI proof ``` pub struct FriProof { layers: Vec<FriProofLayer>, remainder: Vec<u8>, // last poly <all coefficients> num_partitions: u8, // stored as power of 2 } pub struct FriProofLayer { values: Vec<u8>, paths: Vec<u8>, } ``` ![](https://i.imgur.com/rnksZVM.png) #### 9.2 Query trace poly at above positions Similar to the above ``` Queries::new(trace_proof, trace_states) ``` #### 9.3 Query constraint poly at above positions Similar to the above ``` Queries::new(merkle_proof, evaluations) ``` #### 9.4 Establish the STARK Proof ``` StarkProof { context: self.context, commitments: self.commitments, ood_frame: self.ood_frame, trace_queries, constraint_queries, fri_proof, pow_nonce: self.pow_nonce, } ``` ## Step3 - Verify the proof Read pub-info from the transcript to obtain relevant data, and then to execute the verification process. ### 1.Ood consistency check Verify the consistency of the mathematical relationship described in Chapter 5.2 ``` => for Boundary b(z) = q_b(x) * b_divisor(z) => for composition poly t(z) = q_z(x) * t_divisor(z) ``` ### 2. Instantiate the FRI-verifier object ``` pub struct FriVerifier<B, E, C, H> where B: StarkField, E: FieldElement<BaseField = B>, C: VerifierChannel<E, Hasher = H>, H: ElementHasher<BaseField = B>, { max_poly_degree: usize, domain_size: usize, domain_generator: B, layer_commitments: Vec<H::Digest>, //flod_poly commitment layer_alphas: Vec<E>, // random numbers options: FriOptions, num_partitions: usize, _channel: PhantomData<C>, } ``` ### 3. Calculate Deep poly on query positions The calculating method is the same as that in Chapter 6.4 ### 4. Execute the FRI VERIFY process ![](https://i.imgur.com/rIXsHSe.png) ![](https://i.imgur.com/rglOJ2R.png)
Last changed by  
 
Sin7Y
Exploring #Layer 2, #Crosschain, #ZK, and #Privacy Computing.
1179

Read more

The Poseidon2 in Plonky3

Abstract:This document provides a simple introduction to the current state of development of polynomial commitments and the application of hash functions in zero-knowledge proofs (zk). We conduct a detailed study and comparison of the two generations of Poseidon hash functions used in Plonky2 and Plonky3, and present benchmark results to verify the computational performance of Poseidon2.

4/26/2024
Balancing Privacy between Decentralization and Regulation: Insights from DevConnect Istanbul

During DevConnect Istanbul, I had the privilege of engaging with various project teams and researchers dedicated to privacy-oriented initiatives. We discussed a range of privacy-related topics. To my surprise, I found that the concept of ‘privacy’ is interpreted quite differently by different people, generally falling into two distinct categories:

11/29/2023
Programmable Privacy Could Be More Compliance-Friendly

At Ola, we strongly agree with a16z’s statement in their article “Achieving Crypto Privacy and Regulatory Compliance” about web3:

11/29/2023
Sin7y Tech Review (35) Hybrid Rollup - The Next-Generation Infrastructure

A comparative study of Aztec, Miden, and Ola In this article, we delve into the concept of "Hybrid Rollup," examining how projects Aztec, Miden, and Ola approach this technology. We investigate their unique smart contract languages, explore state tree designs, and consider the trade-offs in privacy designs. Our objective is to provide a comprehensive overview of Hybrid Rollup technologies, helping you understand their key components and envision their future trajectory. What is Hybrid Rollup? We are delighted to see that our recent initiatives have been garnering an increasing amount of attention in the market. "Hybrid Rollup" is the most accurate summary of what we at Ola have been working on: Rollup: a. It operates at Layer 2, but it also has the flexibility to function at Layer 3, depending on the platform utilized for the verification contract deployment.b. It's a scalability solution.c. It has programmability - "Rollup" doesn't specifically indicate this feature; "Programmable Rollup" is more accurate. Hybrid: a. It supports public, private, and hybrid contract types.b. Developers can freely choose the contract type based on their needs.c. Users can freely choose the transaction type in hybrid contracts.

6/13/2023
Read more from Sin7Y
Published on HackMD