ZKP(ゼロ知識証明)の情報と高速計算需要のメモ
syoyo事前知識
zk-SNARKs、zk-STARKsとは？
STARKの原理
Hardware Acceleration for Zero Knowledge Proofs
syoyoStarkNet も稼働しはじめており,
PoW のようにスケール(ZKP の計算を競う)のかは不明だが, 少なくとも, たとえば Solana validator のように ZKP Validators/Proovers が pipeline で ZKP 計算を特定の時間以内で行い, それに対して報酬をもらうという形態は出てくるであろう(2024/02 時点でもう出ているかもであるが)
syoyoSNARK の ASIC
syoyoZK Hardware Acceleration: The Past, the Present and the Future
syoyoAccelerating zk-SNARKs - MSM and NTT algorithms on FPGAs with Hardcaml
syoyo一般情報
syoyoGPU 実装
icircle. 現状(2024/02)最も?よくできている GPU(CUDA) 実装と思われる.
Metal support も予定されているようだが, 既存の実装 risc0 ではレジスタ数不足で Metal やめるみたいな雰囲気もあり, ナカナカ一筋縄ではいかないようだ
syoyowebgpu?
icircle は CUDA べったりなので...
とりあえずは cpp 実装をベースに GPU 移植していくのがいいだろうか...
syoyo乱数
PC であれば /dev/urandom 使うことができるが...
webgpu で zk の場合, ブラウザの cryptographically secure RNG API を使うことになるであろう.
syoyomcl is a library for pairing-based cryptography, which supports the optimal Ate pairing over BN curves and BLS12-381 curves.
syoyoCircle STARKs
syoyoReed-Solomon Codes over the Circle Group
syoyoビットコインをきっかけに学ぶ暗号技術入門
syoyoBaby Bear prime(素数)
p = 2^31 - 2^27 + 1
Risc Zero で使われている
(2^32 程度のフィールドで, より小さいフィールド. 計算効率がよい)
Baby Bear の命名の由来は不明.
syoyoMersenne field M31(p = 2^31 - 1)は, 32bit コンピュータでの計算において非常に効率がよい. Circle STARKs ではこれが使われている.
syoyo数学用語
irreducible. イレデューシブル. 既約.
reducible の対語(?)なので, 「減らす」ができない, 約分できない, という意味合い.
reducible は数学では「可約」と訳されているので, 「既約」はちょっとわかりずらいですね.
syoyoBinius
Circle STARK のように 64bit の有限体を使うが, 計算を 2 値(XOR)にして効率化を図る.
ingonyama が実装をだしている(FPGA)