🐙
ZK ゼロ知識証明で計算効率のよい binius のメモ
ZKP(ゼロ知識証明 Protocol)が今後のトレンド(主にブロックチェーンや認証)になりそ?
既存で稼働実績(e.g. ZCash や Polygon zkEVM など)がある, zk-SNARK ベースなのあるけど, 楕円曲線暗号ベースで計算量が多いのがネック...
circle-STARKs や Binus で, 効率計算できるのが出てきた!
Binus に注目してみます.
概要
ヴィタリック先生(豚琳先生)の blog がとりあえずはわかやすいでしょうか.
- M31 などの, ビット数少なく(主に 64bit)て, かつ 32bit アーキテクチャで効率よく計算(ビットシフトと carry だけで演算ができる)できる有限体を使う
- ここまでは Circle STARKs と同じ
- 多項式を Hypercube(2^n) で表現
- そのままでは Merkle tree で探索が困難なので, hypercube を square(X^2) に展開
- さらに, ビット演算(XOR のみ)でできるようにごにょごにょ
- リード・ソロモン符号とか...
という感じでしょうか.
論文
Irreducible(「既約」ではなく, ZK アクセラレーションの会社) が出してます(旧 Ulvetanna)
Succinct Arguments over Towers of Binary Fields
実装
Irreducible の rust 実装
Igonyama(ライオンという意味(「ライオン・キング」由来?). こちらも ZK アクセラレーションの会社)の FPGA 実装
Vitis HLS で C/C++ で記述されているので, そのままでは AMD(Xilinx) の FPGA でしか動きません...
(Verilog 版ほしいね)
Discussion