Plonky2

ざっくりまとめる

https://www.youtube.com/watch?v=kFGUcwT72_c

概要

SNARKの以下3点が改善された

Trusted Setup(Toxic waste)の必要性

Proof生成が遅い

gateの多さ

https://scrapbox.io/files/61b3369ff6642b001e13ce18.png

https://scrapbox.io/files/61b338e2d42ee5001f96131c.png

https://scrapbox.io/files/61b338f50f9ef9001dc33d48.png

STRAKsベースなのかな？どちらにせよこれはデカい

2~3分→15秒→0.17秒...かなり早い

https://scrapbox.io/files/61b33945097dc0002350eaab.png

https://scrapbox.io/files/61b3395380cf0c001ea88428.png

plygon Zero = plonky2ベースのzkEVM

技術詳細

https://scrapbox.io/files/61b33959157da50023477d35.png

https://scrapbox.io/files/61b33a1491d130001de45211.png

https://scrapbox.io/files/61b33a2e8f59cf001d2926d2.png

KZGはPlonkに使われてるやつ

Haloはペアリングなしで検証できるやつ

FRIはSTARKで使われるやつ

https://scrapbox.io/files/61b33bab0cf557001db4695a.png

FRIのパフォーマンスはblowup factorと呼ばれる値の影響を受ける

STARKの中で使われる一つの指標

blowup factorが小さければ、少量のデータをコミットし、速くproofできる

一方で、セキュリティターゲット(何ビット？)に到達させるために、何回もラウンドを重ねる必要があるので、結果的にproof sizeがでかくなっちゃう。

つまり、速度とproof sizeのトレードオフ

そこで、proofをより大きなblowup factorと一緒にラッピングし、再帰的にproofを収縮させることにした

blowup factorは十分に大きいのでラウンドを重ねる必要はないし、再帰的にproof sizeを小さくしているからトレードオフを解消できるよね！って理論かな

https://scrapbox.io/files/61b3425e8f68aa00233b2c2f.png

ついでにwitnessを256→64bitにして、高速化したらしい

ここまでが、プロトコルの全体像

Circuitの最適化

では、どうやって再帰的にproofを作るの？

A.多項式コミットメントを使った手法

https://scrapbox.io/files/61b3432e8f59cf001d295732.png

https://scrapbox.io/files/61b3440f1418fd001dd3a118.png

各gateごとにバカ長いテーブル(135列)を準備する

https://scrapbox.io/files/61b3449c2f0bf9001dd4acf6.png

ここはよくわかんない

https://scrapbox.io/files/61b344ca970afa001dbeb68f.png

poseidon hashを一つの列に対して行う

https://scrapbox.io/files/61b345273039bd002349e76b.png

これにより、マークル木の検証コストが削減できる

https://scrapbox.io/files/61b3457862bd4f001db7435f.png

これで、2^16→2^12 gateに削減できた🎉

チューニング

https://scrapbox.io/files/61b3471380e0940021d37472.png

https://scrapbox.io/files/61b3471c47b85f0020168291.png

https://scrapbox.io/files/61b347b80cf557001db4b25e.png

やっぱ線形代数屋しか勝たん