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