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  f(z) = q(z) * t(z)  f(x),q(x),t(x) sont bien égaux respectivement à f(z), q(z), t(z)  calculer Deep_composition = (q(x) - q(z)) / (x - z)  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

Target

Trace

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Cet audio est produit dans la langue originale de l'histoire !

Trop long; Pour lire

Oh juste une analyse technique Stark

Oh juste une analyse technique Stark

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Appuyez pour gagner : Telegram pourrait intégrer les 10 prochains milliards d'utilisateurs de crypto avant Solana

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Nomades numériques, écoutez : ce que vous devez savoir sur le nouveau visa DTV de la Thaïlande

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Appuyez pour gagner : Telegram pourrait intégrer les 10 prochains milliards d'utilisateurs de crypto avant Solana

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Nomades numériques, écoutez : ce que vous devez savoir sur le nouveau visa DTV de la Thaïlande

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps