traces:
\(a: [a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7]\)
\(b: [b_0,b_1,b_2,b_3,b_4,b_5,b_6,b_7]\)
goal:
prove logup relation:
\(\sum\limits_{i=0}^{i=7}\frac{1}{a_i+\alpha}=\sum\limits_{i=0}^{i=7}\frac{1}{b_i+\alpha}\)
what are available:
- commitments to the traces via FIR:
\(\text{commit}[a(x)]\)
\(\text{commit}[b(x)]\)
note: \(a(x),b(x)\) denote the polynomials’ evaluation in trace domain, \(x\) comes from cyclic group.
- GKR circuit: give a proof for the accumulation of fractions, reduced the problem to proving evaluations of MLEs, these MLEs are from the fractions.
- STARK prover: prove a MLE’s evaluation is correct
STARK Prover:
inputs: a MLE: its evaluation on hypercube is committed
evaluation points
claim_evaluation
Protocol description:
GKR circuit:
Offloading logup accumulation to GKR has these component:
- a uni-variate PCS, commit to traces that are the denominator of logup fractions
- logup-GKR circuit transform the problem to proving evaluations of MLEs
- these MLEs need to be committed before, using the uni-variate PCS