following previous post Input Layer Encoding (witness encoding) trace columns are interpreted as functions, the inputs of the function are bits, enough number of bits that can present \(n\) number of witness in this column. for trace \(i\), with \(n\) number of rows (trace degree, trace length) \(f_i(b_0,b_1,b_2,…,b_n)=a_{b_n,…,b_2,b_1,b_0} \) at the last layer (input layer) of GKR, the numerators and denominators of the fractions are all from the STARK trace, we need to defined the constraint to wind these values with STARK trace, and prove this winding. The question can be described in different ways: how to simulate a Multi-linear Polynomial Commitment scheme from a uni-variate polynomial commitment scheme how to implement the final oracle query by the verifier at the random point resulting from the GKR protocol interaction. or from this blog Multi-linear Polynomial Commitment scheme from a uni-variate polynomial commitment scheme The essential question is at the end …

following this post Witness encoding: trace columns are interpreted as functions, the inputs of the function are bits, enough number of bits that can present \(n\) number of witness in this column. for trace \(i\), with \(n\) number of rows (trace degree, trace length) \(f_i(b_0,b_1,b_2,…,b_n)=a_{b_n,…,b_2,b_1,b_0} \) Circuit for computing the sum of the fractions the sum of logup is about the sum of many fractions, the strategy here is adding the numerators together (at the end I suppose the denominator will be divided, but now, only consider adding the numerators ) adding two fractions: \(\frac{a}{b}+\frac{c}{d}=\frac{a\cdot d + c \cdot b}{b\cdot d}\) let a fraction to be represented by two element: \(numerator, denominator\) in this way of represent, the addition of two fractions is expressed as \((a,b)+(c,d)=(a\cdot d + c \cdot b, b\cdot d)\) for the Logup equation to be proved in the note is: Then the circuit is something like: …

Equation function Turn a function in binary field to its multilinear extension. let \(\mathcal{G}\) be a function in binary field, its multi-linear extension can be presented as: $$\mathcal{G}(r_1,…,r_m)=\sum\limits_{x\in\{0,1\}^m}\mathcal{G}(x)\prod\limits^{m}_{i=1}\underbrace{(r_i\cdot x_i + (1-r_i)(1-x_i))}_{x_i=0 \rightarrow 1-r_i, x=1 \rightarrow r_i }$$ emphasize: \(r_i \in \mathbb{F}\) \(x \in \{0,1\}^m\) \(x_i \) is 0 or 1 …

How to define high degree constraint in Plonky3 and Stwo as a user Plonky3: A user must verify the following equation when determining the degree of the constraint (further explanation is provided in the next section): let \(d\) be the degree of the constraint: \(d-1\leq 2^{\text{log_blow_up_factor}}\) If this condition is not met, an error will occur: lde.height() >= domain.size() Stwo The user must first define the maximum degree bound. If the constraints exceed this bound, there will be no explicit error indicating that the failure is due to a high-degree constraint. Instead, the error will appear as “constraint not satisfied” because the out-of-domain sample evaluation does not match. set the maximum degree bound to be self.log_degree()+1 is equivalent to getting maximum 2 degree constraint in plonky3 Why the constraint degree affects the other parameters? In both Plonky3 and Stwo, quotient polynomial evaluations are computed using an evaluate function. This function …

I am using a simplified circuit for case demonstration purpose: The bus statement to be proved is: \([x_0,x_1]\) in [0] with \(bus_{id}\)=a, this case has only one valid witness [0,0], with multiplicity to be 2 Original protocol: The above statement essentially proves: \(\frac{1}{\alpha -x_0}+\frac{1}{\alpha -x_1}=\frac{2}{\alpha}\) where \(\alpha\) is a random value, obtained by the hash result of the witness \((x_0,x_1)\), this is the application of Fiat-Shamir transform. Modified protocol The above statement essentially proves: \(\frac{1}{\alpha +a -\beta x_0}+\frac{1}{\alpha +a-\beta x_1}=\frac{2}{\alpha+a}\) where \(\alpha, \beta\) are random values, obtained by the hash result of the witness \((x_1,y_1)\), \(bus_{id}=a\) is a hash of some circuit information, which can be consider as part of a statement to be proved. attack of the modified protocol: Since the \(bus_{id}=a\) is independent of the witness, it can be crafted in a way that let the verifier accepts a proof from an invalid witness, as shown below: attacker …

continue from this blog Another thought: proving everying thing together and logup by stwo as extra. Building LogUp trace basic steps: logup trace generator, size is determined. let mut logup_gen = LogupTraceGenerator::new(log_size); generate columns that is associated with this logup trace generator let mut col_gen = logup_gen.new_col(); write fraction, building accumulator column for vec_row in 0..(1 << (log_size_payload – LOG_N_LANES)) { let p = bitreverse_multiplicity_col.data[vec_row]; let left_values: Vec<PackedM31> = left_cols .iter() .map(|col| col.data[vec_row]) // Extract data at vec_row .collect(); let q: PackedSecureField = lookup_elements.combine(&left_values); col_gen.write_frac(vec_row, p.into(), q); } finalized col logup_gen.finalize_last(); Notes on Logup trace generation the columns that are associated to a Logup trace generator is the columns that in one logup proof, namely, they belongs to the same relation to give a logup proof, in powdr setting, this means the columns should include all the payloads in the same bus id. logup_gen.finalize_last() outputs (trace, sum), trace is of …