C(x) = yのアウトプットをsumcheck等式として記述するというアイデア

Protocol

Libra

https://eprint.iacr.org/2019/317.pdf

Libraの分散prover algorithm: https://eprint.iacr.org/2024/143.pdf

実装: https://github.com/sunblaze-ucb/Libra

Complexity

• Prover time: O(N)
• Proof size / Verifier time: O(DlogN)
  • worst case: O(N)
  • structured circuit (e.g. matmul, data parallel circuit): O(DlogN)

実装の流れ

1. pcs::commit: 入力レイヤーの値をMLE形式でコミット
   1. transcriptにコミットメントを追加
2. grind: 証明の難易度を高めるための追加のハッシュ計算
   1. transcriptを強化する
3. c.fill_rnd_coefs: 回路のランダム係数を設定
4. c.evaluate: 回路評価を実行
5. gkr_prove: 証明
   1. (claimed_v, rx, ry, rsimd, rmpi)
6. prove_input_layer_claim: PCSのOpeningを実行
7. transcript.finalize_and_get_proof