Oh juste une analyse technique Stark

Vous trouverez ci-dessous un certain nombre d'étapes examinant les processus approfondis de STARK.

Étape 1 - Construire Trace (exemple fib2)

Les chiffres marqués en 'rouge' sont des informations publiques.

 Some assertion: Form: [register, step, value] examples: [0,0,1], [1,0,1], [1,7,987]

Step2 - Prouveur pour Trace

Sélection du paramètre de protocole :

 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. Instanciation AIR

 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. Vérifier la cohérence d'AIR et de Trace (module de débogage)

2.1 Vérifier les paramètres de base

 Trace.width = air.trace_width

2.2 Vérifier la validité de l'assertion (Boundary cs)

 Trace[assertion_i.register][assertion_i.step] = assertion_i.value

2.2 Vérifier si la trace maintient la transition cs (module de débogage)

 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

Transcription

 write.into(air, public info)

3. S'engager pour Trace

Sélection des paramètres de domaine :

 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 Interpoler -> LDE -> évaluer sur le domaine LDE

3.2 Engagement

Transcription

 write.into(cm_to_trace)

4.Évaluer CS

4.1 Obtenir des coefficients de composition linéaire

 Ok(ConstraintCompositionCoefficients { transition: t_coefficients, boundary: b_coefficients, })

Le nombre de coefficients est cohérent avec celui des contraintes
Dans cet exemple (fib2-example), il y a 2 cs de transition et 3 cs de frontière.

4.2 Établir l'évaluateur pour les t-cs et 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 Évaluer t/s-cs sur ce_domain

4.3.1 Définir le tableau des évaluateurs

 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. Engagement à évaluer CS

5.1 Établir le polynôme de composition des contraintes

5.2 Engagement envers Composition Poly

Exemple:
Compose_poly = a * x^3 + b * x^2 + c * x + d = (a * x^2 + c) * x^ + (b * x^2 + d) (a * x^2 + c ) et (b *x^2 +d) correspondent respectivement à deux colonnes.

6. Établir le polynôme de composition DEEP

Le formel général : f(x) = q(x)* t(x)
Besoin de vérifier au hasard z

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

   
   

2. f(x),q(x),t(x) sont bien égaux respectivement à f(z), q(z), t(z)

   
   

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

   
   

4. Vérifier LDT pour q_q(x)

6.1 Sélectionnez z qui hors du domaine (ood)

Dessinez un point z hors domaine. Selon le type de E, le point est tiré soit du champ de base, soit d'un champ d'extension défini par E.
Le but de l'échantillonnage à partir du champ d'extension ici (au lieu du champ de base) est d'augmenter la sécurité

6.2 Évaluer les polynômes de trace et de contrainte au point OOD z

6.2.1 trace_poly à z & z * g

 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 en z

 iter!(self.columns).map(|p| polynom::eval(p, z^m)).collect() // m is the column num of the composition poly

6.3 Établir un polynôme de composition profond

6.3.1 Générer des nombres aléatoires

 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 Évaluer en profondeur sur LDE

 deep_evaluations<lde_domain_size> = deep_composition_poly.evaluate(&domain);

7. Calculez le numéro de couche FRI de Deep

 trace.length() = fold_factor ^ Layer_num + remainder_size; fold_factor = {4, 8, 16} remainder_size < remainder_max_size == 256 

8. Déterminer les positions de la requête

Sélectionnez plusieurs positions de la requête à partir de lde_domain.

 fold_position = source_position % (fold_domain) fold_domain = source_domain / fold_factor

9. Établir des objets de preuve

9.1 Générer une preuve FRI

 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>, } 

9.2 Requête Trace Poly aux positions ci-dessus

Semblable à ce qui précède

 Queries::new(trace_proof, trace_states)

9.3 Interroger le poly de contrainte aux positions ci-dessus

Semblable à ce qui précède

 Queries::new(merkle_proof, evaluations)

9.4 Établir la preuve STARK

 StarkProof { context: self.context, commitments: self.commitments, ood_frame: self.ood_frame, trace_queries, constraint_queries, fri_proof, pow_nonce: self.pow_nonce, }

Étape 3 - Vérifiez la preuve

Lisez les informations de pub de la transcription pour obtenir les données pertinentes, puis pour exécuter le processus de vérification.

1. Bonne vérification de la cohérence

Vérifier la cohérence de la relation mathématique décrite au chapitre 5.2

 => for Boundary b(z) = q_b(x) * b_divisor(z) => for composition poly t(z) = q_z(x) * t_divisor(z)

2. Instanciez l'objet FRI-Verifier

 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. Calculer Deep Poly sur les positions de requête

La méthode de calcul est la même que celle du chapitre 6.4

4. Exécutez le processus FRI VERIFY