A continuación hay una serie de pasos que examinan los procesos en profundidad de STARK. Paso 1 - Seguimiento de compilación (ejemplo fib2) Los números marcados en 'rojo' son información pública. Some assertion: Form: [register, step, value] examples: [0,0,1], [1,0,1], [1,7,987] Paso 2 - Probador para Trace Selección del parámetro de protocolo: 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. Instanciación de AIRE 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. Verificar la coherencia de AIR y Trace (módulo de depuración) 2.1 Verificar parámetros básicos Trace.width = air.trace_width 2.2 Verificar la Validez de la Afirmación (Límite cs) Trace[assertion_i.register][assertion_i.step] = assertion_i.value 2.2 Verificar si Trace retiene la transición cs (módulo de depuración) 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 Transcripción write.into(air, public info) 3. Confirmar para Trace Selección de parámetros de dominio: 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 Interpolar -> LDE -> evaluar sobre dominio LDE 3.2 Compromiso Transcripción write.into(cm_to_trace) 4.Evaluar CS 4.1 Obtención de coeficientes de composición lineal Ok(ConstraintCompositionCoefficients { transition: t_coefficients, boundary: b_coefficients, }) El número de coeficientes es consistente con el de restricciones En este ejemplo (ejemplo fib2), hay 2 cs de transición y 3 cs de límite. 4.2 Establecer el Evaluador para t-cs y 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 Evaluar t/s-cs sobre ce_domain 4.3.1 Definir tabla de evaluadores 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. Compromiso de Evaluar SC 5.1 Establecer Restricciones Polinomio de Composición 5.2 Compromiso con la Composición Poli Ejemplo: Componer_poli = a * x^3 + b * x^2 + c * x + d = (a * x^2 + c) * x^ + (b * x^2 + d) (a * x^2 + c ) y (b *x^2 +d) corresponden a dos columnas, respectivamente. 6. Establecer el polinomio de composición DEEP El formal general: f(x) = q(x)* t(x) Necesita comprobar al azar z f(z) = q(z) * t(z) f(x),q(x),t(x) de hecho iguales respectivamente f(z), q(z), t(z) calcular Composición_profunda = (q(x) - q(z)) / (x - z) Comprobar LDT para q_q(x) 6.1 Seleccione z que fuera del Dominio (bueno) Dibuje un punto fuera del dominio z. Según el tipo de E, el punto se dibuja desde el campo base o desde un campo de extensión definido por E. El propósito de tomar muestras del campo de extensión aquí (en lugar del campo base) es aumentar la seguridad 6.2 Evaluar polinomios de traza y restricción en el punto OOD z 6.2.1 trace_poly en 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 Composición Poli en z iter!(self.columns).map(|p| polynom::eval(p, z^m)).collect() // m is the column num of the composition poly 6.3 Establecer polinomio de composición profunda 6.3.1 Generar números aleatorios 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 Cociente Poli => 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 Evaluar Profundo sobre LDE deep_evaluations<lde_domain_size> = deep_composition_poly.evaluate(&domain); 7. Calcule el número de capa FRI de profundidad trace.length() = fold_factor ^ Layer_num + remainder_size; fold_factor = {4, 8, 16} remainder_size < remainder_max_size == 256 8. Determinar posiciones de la consulta Seleccione varias posiciones de la consulta de lde_domain. fold_position = source_position % (fold_domain) fold_domain = source_domain / fold_factor 9. Establecer objetos de prueba 9.1 Generar prueba 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 Consulta de seguimiento de poli en las posiciones anteriores Similar al anterior Queries::new(trace_proof, trace_states) 9.3 Consulta polivinílica de restricción en las posiciones anteriores Similar al anterior Queries::new(merkle_proof, evaluations) 9.4 Establecer la Prueba STARK StarkProof { context: self.context, commitments: self.commitments, ood_frame: self.ood_frame, trace_queries, constraint_queries, fri_proof, pow_nonce: self.pow_nonce, } Paso 3 - Verificar la prueba Lea pub-info de la transcripción para obtener datos relevantes y luego ejecute el proceso de verificación. 1. Comprobación de consistencia alta Verificar la consistencia de la relación matemática descrita en el Capítulo 5.2 => for Boundary b(z) = q_b(x) * b_divisor(z) => for composition poly t(z) = q_z(x) * t_divisor(z) 2. Crear una instancia del objeto 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. Calcule Deep Poly en posiciones de consulta El método de cálculo es el mismo que en el Capítulo 6.4 4. Ejecute el proceso 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

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Making security fun one episode at a time

Oh, solo un análisis técnico rígido

Oh, solo un análisis técnico rígido

Demasiado Largo; Para Leer

Companies Mentioned

Sin7Y

About Author

ETIQUETAS

Languages

ESTE ARTÍCULO FUE PRESENTADO EN...

Oh, solo un análisis técnico rígido

Demasiado Largo; Para Leer

Companies Mentioned

Sin7Y

About Author

ETIQUETAS

Languages

ESTE ARTÍCULO FUE PRESENTADO EN...

HISTORIAS RELACIONADAS