🐙

ZK ゼロ知識証明で計算効率のよい binius のメモ

2024/06/03に公開

ZKP(ゼロ知識証明 Protocol)が今後のトレンド(主にブロックチェーンや認証)になりそ?

既存で稼働実績(e.g. ZCash や Polygon zkEVM など)がある, zk-SNARK ベースなのあるけど, 楕円曲線暗号ベースで計算量が多いのがネック...

circle-STARKs や Binus で, 効率計算できるのが出てきた!

https://zenn.dev/syoyo/scraps/94bfebd9860245

Binus に注目してみます.

概要

ヴィタリック先生(豚琳先生)の blog がとりあえずはわかやすいでしょうか.

https://vitalik.eth.limo/general/2024/04/29/binius.html

  • 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
https://eprint.iacr.org/2023/1784.pdf

実装

Irreducible の rust 実装

https://gitlab.com/IrreducibleOSS/binius/

Igonyama(ライオンという意味(「ライオン・キング」由来?). こちらも ZK アクセラレーションの会社)の FPGA 実装

https://github.com/ingonyama-zk/open-binius

Vitis HLS で C/C++ で記述されているので, そのままでは AMD(Xilinx) の FPGA でしか動きません...
(Verilog 版ほしいね)

Discussion