Logup GKR in an example

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

Leave a Reply

Your email address will not be published. Required fields are marked *