Abaixo estão algumas etapas que examinam os processos detalhados do STARK.   Step1 - Construir Trace（fib2-example)  Os números marcados em 'vermelho' são informações públicas.   Some assertion: Form: [register, step, value] examples: [0,0,1], [1,0,1], [1,7,987]   Step2 - Provedor para Trace  Seleção do parâmetro do 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. Instanciação 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. Verifique a consistência do AIR e Trace (módulo Debug)   2.1 Verificar Parâmetros Básicos   Trace.width = air.trace_width   2.2 Verificar a validade da afirmação (limite cs)   Trace[assertion_i.register][assertion_i.step] = assertion_i.value   2.2 Verifique se 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   Transcrição   write.into(air, public info)   3. Confirmar para rastreamento  Seleção de parâmetro de domínio:   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 -> avaliar sobre o domínio LDE  3.2 Compromisso    Transcrição   write.into(cm_to_trace)   4. Avaliar CS   4.1 Obter coeficientes de composição linear   Ok(ConstraintCompositionCoefficients { transition: t_coefficients, boundary: b_coefficients, })  O número de coeficientes é consistente com o de restrições  Neste exemplo (fib2-example), existem 2 cs de transição e 3 cs de limite.   4.2 Estabelecer o Avaliador para t-cs e 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 Avalie t/s-cs sobre ce_domain   4.3.1 Definir Tabela de Avaliadores   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. Compromisso para avaliar CS     5.1 Estabelecer Polinômios de Composição de Restrições   5.2 Compromisso com o Poli de Composição  Exemplo:  Compose_poly = a * x^3 + b * x^2 + c * x + d = (a * x^2 + c) * x^ + (b * x^2 + d) (a * x^2 + c ) e (b *x^2 +d) correspondem a duas colunas, respectivamente.    6. Estabeleça o Polinômio de Composição DEEP  O formal geral: f(x) = q(x)* t(x)  Precisa verificar aleatoriamente z  f(z) = q(z) * t(z)  f(x),q(x),t(x) de fato iguais respectivamente f(z), q(z), t(z)  calcular Deep_composition = (q(x) - q(z)) / (x - z)  Verifique o LDT para q_q(x)   6.1 Selecione z qual fora de Domain(ood)  Desenhe um ponto z fora do domínio. Dependendo do tipo de E, o ponto é desenhado a partir do campo base ou de um campo de extensão definido por E.  O objetivo da amostragem do campo de extensão aqui (em vez do campo base) é aumentar a segurança   6.2 Avaliar polinômios de traço e restrição no ponto OOD z   6.2.1 trace_poly em 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 Composição Poli em z   iter!(self.columns).map(|p| polynom::eval(p, z^m)).collect() // m is the column num of the composition poly   6.3 Estabelecer polinômio de composição profunda   6.3.1 Gerar Números Aleatórios   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 Quociente Cal 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 Avalie profundamente sobre LDE   deep_evaluations<lde_domain_size> = deep_composition_poly.evaluate(&domain);   7. Calcule o número da camada FRI de Deep     trace.length() = fold_factor ^ Layer_num + remainder_size; fold_factor = {4, 8, 16} remainder_size < remainder_max_size == 256   8. Determine as posições da consulta  Selecione várias posições da consulta de lde_domain.   fold_position = source_position % (fold_domain) fold_domain = source_domain / fold_factor   9. Estabelecer Objetos de Prova   9.1 Gerar prova 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 Polígono de Rastreamento de Consulta nas Posições Acima  Semelhante ao acima   Queries::new(trace_proof, trace_states)   9.3 Poli de Restrição de Consulta nas Posições Acima  Semelhante ao acima   Queries::new(merkle_proof, evaluations)   9.4 Estabelecer a Prova STARK   StarkProof { context: self.context, commitments: self.commitments, ood_frame: self.ood_frame, trace_queries, constraint_queries, fri_proof, pow_nonce: self.pow_nonce, }   Passo 3 - Verifique a prova  Leia pub-info da transcrição para obter dados relevantes e, em seguida, para executar o processo de verificação.   1. Verificação de boa consistência  Verifique a consistência da relação matemática descrita no 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. Instancie o 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 em posições de consulta  O método de cálculo é o mesmo do Capítulo 6.4     4. Execute o processo 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 áudio é produzido no idioma original da história!

Muito longo; Para ler

Oh, apenas uma análise técnica rígida

Oh, apenas uma análise técnica rígida

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Toque para ganhar: Telegram pode integrar os próximos 10 bilhões de usuários criptográficos antes de Solana

De fóruns a feeds: como os algoritmos de mídia social moldam a interação digital

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Toque para ganhar: Telegram pode integrar os próximos 10 bilhões de usuários criptográficos antes de Solana

De fóruns a feeds: como os algoritmos de mídia social moldam a interação digital

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps