Sumcheck is all you need論文を読む part1

この記事は何？

Justin Thaler先生が以下の論文を最近投稿したようなので、これを雑にまとめていく記事を書きます。タイトルの通り、sumcheckプロトコルの魅力が語られていく論文(Opinionated Survey)です。

https://eprint.iacr.org/2025/2041.pdf

• 本記事（part1）は、論文１章に関してつらつら書いていきます
• sumcheckプロトコルとかコミットメントとかに関しては別途記事を書く予定です、多分

TL;DR

Sumcheckプロトコルを上手に使うと、高速なSNARK証明を実現できる

The prover’s work is dominated by two tasks: (i) committing to data and (ii)
proving that the committed data is well-formed. The central thesis of this survey is that fast SNARKs minimize both costs by using the sum-check protocol.

• コミットメントするデータ量を以下に減らすかが高速なSNARK証明生成のカギ
• sumcheckプロトコルを使うことでそれが可能

But not all uses of sum-check are equally effective. The fastest SNARKs invoke sum-check in highly sophisticated ways, exploiting repeated structure in computation to aggressively minimize commitment costs and prover work.

• ただし、とりあえずsumcheckプロトコルを呼び出せばよいわけではなく、sumcheckプロトコルをいかに上手に適用してあげられるかがポイント

概要和訳
SNARKsは、証明者がwitnessをコミットし、そのコミットされたwitnessが有効であることを証明することで機能する。証明者の作業は主に2つのタスクに支配される:(i)データへのコミット、(ii)コミットされたデータが適切に形成されていることの証明。本サーベイの中心的な主張は、高速なSNARKsはsum-checkプロトコルを使用することで両方のコストを最小化するということである。しかし、sum-checkのすべての使用法が等しく効果的というわけではない。最速のSNARKsは、計算における繰り返し構造を活用してコミットメントコストと証明者の作業を積極的に最小化する、高度に洗練された方法でsum-checkを呼び出す。本サーベイでは、これを可能にする重要なアイデアを調査する:batch evaluation arguments、read/write memory checking、virtual polynomials、sparse sum-checks、small-value preservation。これらの技術は、高速なSNARK証明の基盤としてのsum-checkプロトコルの潜在能力を最大限に引き出す。

イントロ（第1章）

SNARKとは何か

A SNARK (succinct non-interactive argument of knowledge) allows an untrusted prover to convince a verifier that it correctly executed some computation on a witness, or equivalently that it knows data satisfying a certain property.

• 信頼できない証明者(prover)が、検証者(verifier)に対して以下を証明する
  • witness wに対して計算f(w)を正しく実行したこと
  • または、特定の性質(y = f(w)となるような)を満たすデータを知っていること

The naive way to do this is for the prover to send the full witness, and for the verifier to directly run the checker.

素朴には、証明者がwitnessを検証者に全部渡して、検証者が計算f(w)を行えば良いですが、このやり方は簡潔(succinct)ではないですね（succinctってなんだ？）

（この論文での）Succinctness(簡潔性)の意味

Succinctness means the proof should be shorter than the trivial proof and faster to verify than re-running the checker on the full witness

• 素朴なやり方での証明より短い
• 計算fを再実行するより高速に検証できる

モダンなSNARKの効率性

the key bottleneck for applying SNARKs in practice is prover time, not proof size or verifier cost.

• SNARKにおいて、検証者側の性能はすでに非常に効率的である
  • 証明サイズ: 1キロバイト未満〜数百キロバイト
  • 検証時間: 通常ミリ秒オーダー
• SNARKsを実用的に適用する際の鍵となるボトルネックは証明時間(prover time)
  ¹

SNARK証明のメカニズム

SNARK proving in a nutshell. Modern SNARKs operate in two stages:
• The prover commits to a large dataset (e.g., a witness).
• Then it proves that this committed data is well-formed, i.e., that the witness checker would accept the committed witness.

モダンなSNARKsは以下の2段階で動作:

1. データへのコミット
   • 証明者が大規模データセット(例:witness)にコミット
2. データの正当性証明
   • コミットされたデータが適切に形成されていることを証明
   • つまり、コミットされたwitnessで計算f(w)を行うとyになることを証明

SNARKの責務:
データへのコミットだけでなくその主張が正しいことの証明も必要

"Commit-then-prove-well-formed"構造がもたらす2つのコスト

1. 暗号技術は高コスト

コミットメントに含まれる操作:

• ハッシュ化
• 誤り訂正符号化
• 暗号群演算

これらは大規模ベクトルに適用すると非常に時間がかかる

2. コミットするデータが多いほど、チェックも増える

• 証明者がコミットするすべてのデータは、後で適切に形成されていることを証明する必要がある
• これにより証明負担がさらに増加

この章の教訓

Hence the high-level lesson: commit to as little data as possible.

可能な限り少ないデータをコミットしよう

だから、Sum-checkプロトコルが重要だ

コミットメントコストを最小化する最良の方法は?

One of the key design principles in this survey is to treat interaction as a resource: use it to minimize commitments and prover work, and remove it just once, via Fiat-Shamir, at the very end.1 Section 1.1 elaborates on this viewpoint and why popular SNARKs for years failed to fully embrace this principle.

• このサーベイにおける重要な設計原則の1つは、対話をリソースとして扱うこと
• つまり、コミットメントと証明者の作業を最小化するために対話を使用し、最後の最後にFiat-Shamirを介して一度だけ対話を除去する

With this principle in mind, the sum-check protocol is a remarkably effective tool for offloading　work onto an untrusted prover while keeping the proof succinct. The sum-check protocol as a standalone object is information-theoretically secure, i.e., it uses no cryptography at all. In place of cryptography, it uses interaction and randomness. Fiat-Shamir can then be used to remove the interaction with minimal overhead.

• この原則を念頭に置くと、sum-checkプロトコルは、証明を簡潔に保ちながら、信頼できない証明者に作業をオフロードするための非常に効果的なツール
• sum-checkプロトコルは、単独のオブジェクトとしては情報理論的に安全
  • つまり、暗号技術を一切使用しない
  • 暗号技術の代わりに、対話とランダム性を使用する
• Fiat-Shamirを使用して最小限のオーバーヘッドで対話を除去できる

SNARKの証明生成のパフォーマンス階層

The performance of SNARK provers follows a clear hierarchy:
• Slowest: SNARKs that do not use the sum-check protocol at all.
• Faster: SNARKs that invoke sum-check, but fail to fully exploit repeated structure in the computation.
• Fastest: SNARKs that combine sum-check with techniques that aggressively exploit repeated structure to minimize commitment costs and overall prover overhead. As we will see, these techniques include batch evaluation arguments, polynomial virtualization, small-value preservation, and more.

SNARKの証明生成のパフォーマンスは、明確な階層構造に従う:

• 最も遅い: sum-checkプロトコルを全く使用しないSNARK
• より高速: sum-checkプロトコルを呼び出すが、計算における繰り返し構造を完全に活用できていないSNARK
• 最速: sum-checkプロトコルと、コミットメントコストと証明者の全体的なオーバーヘッドを最小化するために繰り返し構造を積極的に活用するテクニックを組み合わせたSNARK
  • これらのテクニック（Batch Evaluation, Virtual Polynomialsなど）は主に論文の５章で紹介

Happily, the fastest SNARKs also turn out to be the simplest.

嬉しいことに、最速のSNARKは最もシンプルである

Opinionated Surveyということで、あくまでもJustin Thaler先生がそう考えている、っていう理解で良いんですかね？

SNARKの歴史を軽く追う（論文1.1）

1980-1990年代:Interactive Proofsの誕生

• Goldwasser, Micali, and Rackoff (GMR)論文でInteractive Proofsが導入
• 1990年:LFKN論文でsum-checkプロトコルが登場
  • #SAT問題(充足解の数え上げ)に効率的な検証者を持つ証明が可能に
  • IP = PSPACEという画期的な結果につながる (いまだにこれなに？ってなるけど、誰か教えてください)

1990-2010年代

• 研究の焦点が特にProbabilistically Checkable Proofs(PCPs)へシフト
• • Univariate polynomials(一変数多項式)とquotienting技術が基盤に（論文３章で紹介）
• Kilianによる最初のSNARKs構築(PCP + Merkleコミットメント)

2017~

• vSQLとHyrax(2017):Sum-checkベースのSNARKsの実現可能性を実証
  • GKRプロトコルをSNARKsにコンパイル
• SpartanとClover:任意の回路のサポートを実現

Still, the dominant approach in both theory and practice remained based on univariate encodings and quotienting. This was partly due to the appeal of very short proofs (e.g., Groth16), and partly due to limited awareness of sum-check-based systems and their performance.

それでも、理論と実践の両方において支配的なアプローチは、univariate encodingsとquotientingに基づくものであり続けた。これは、非常に短いproof(例えば、Groth16 [Gro16])の魅力と、sum-check-based systemsとそのパフォーマンスに対する認識の限界が一因であった。

2023年あたりからのブレークスルー

• LassoやJoltの登場
• Sum-checkと以下を組み合わせることで劇的な性能向上
  • Batch evaluation arguments
  • Memory checking
  • Small-value preservation

Univariate polynomialsベースのシステムよりシンプルかつ高速、と言っている

The modern perspective, developed in this survey, is not that sum-check solves all performance issues when applied naively. Rather, there is a spectrum of sophistication in how the protocol is used. By exploiting repeated structure in real computations, sum-check enables SNARKs that can scale to the needs of real-world infrastructure

• Sum-checkを単純に適用するだけでは不十分
• 使用方法の洗練度に大きな幅がある
• 実際の計算における繰り返し構造を活用することが鍵
• 実世界のインフラのニーズに対応可能なスケーラビリティを実現

１章まとめ

久々にzkSNARK周りを知りたかったので読んでいますが、最近の流行りはsumcheck × 〇〇ってことなんでしょうかね？（あくまでもOpinionated Surveyですが）

例えば、Anonymous Credentials from ECDSAでも、GKRベースのプロトコルの各メッセージmを乱数padで暗号化(m + pad)して実行してトランスクリプトを作成後、「それを復号してGKRベースのプロトコルの検証作業を行う回路」をLigeroで証明するアプローチが取られているようです。

次の記事（part 2）では、論文２章を読んで、数式のNotationや基礎知識についてまとめます。

1. デジタルウォレットへのzkSNARKの応用が色々議論されてますが、ウォレットがスマホ、検証者はサーバーと仮定すれば、焦点をあてたいのは検証時間よりもスマホでの証明生成時間、ですね ↩