Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

言語

BLS12-381: 新しいzk-SNARK楕円曲線の構築

Sean Bowe | Mar 11, 2017

チームでは、プライバシーを保護する シールドされたトランザクション のセキュリティ、性能、使いやすさを改善するために継続的に取り組んでいます。 ブログ記事、将来的な優先順位 で述べたように、現在はSaplingという次のバージョンのZcashのための暗号改良に取り組んでいます。Zcashの目標の1つに、シールドされた支払いをより効率的に少ないメモリデ行うことがあります。また、zk-SNARKプルーフに使用する楕円曲線構築の具体的なセキュリティレベルを向上させる予定です。

BLS12-381曲線。

先月は、128ビットのセキュリティレベルでzk-SNARKsに適した、ペアリング親和性のある新しい楕円曲線構造を設計し実装していました。この構築は、セキュリティマージンを増やしながらパフォーマンスとユーザビリティコストを最小限にします。

構築は弊社所属の研究者が上梓する次の研究論文に掲載されます。構築の説明とどのようにしてこれが選択されたかについてより詳しくご紹介します。

Barreto-Naehrig曲線

Barreto-Naehrig(BN)曲線は、オーダー \(r\)\(r \approx q\))のベースフィールド \(\mathbb{F}_q\) 上に構築される ペアリングフレンドリー 楕円曲線構造のクラスです。現在の曲線構造は、\(q \approx 2^{254}\) です。昨年、KimとBarbulescu は、数対ふるい法のバリアントを発表しました。最近の論文 に基づくと、これにより保守的な [1] セキュリティレベルの見積もりが約110ビットまで減少しました。

この控えめな概算に従っても、\(q \approx 2^{384}\) により近い曲線を選択して、128ビットのセキュリティを目標とする新しいBN曲線を構築することができます。ただし、より大きなグループのオーダー|r|によって、zk-SNARKスキーマおよびマルチパーティコンピュテーションで効率的に実行する必要があるマルチ累乗、高速フーリエ変換、およびその他の暗号化動作のパフォーマンスが低下します。さらに、より大きなスカラーフィールド|Fr|により、鍵材料が不必要に大きくなります。

Barreto-Lynn-Scott曲線

Barreto-Lynn-Scott(BLS)曲線は、ペアリングに適した曲線のわずかに古いクラスに属し、このセキュリティレベルを目標にするのにさらに役立ちます。最新の調査では、\(q \approx 2^{384}\) および埋め込み次数12を使用して、この曲線では128ビットのセキュリティレベルをターゲットにすることが推奨されています。好都合なことに、この曲線のグループオーダーは \(r \approx 2^{256}\) であるため、スカラーフィールドの大きさにともないパフォーマンスやユーザビリティが損なわれないようにすることができます。

BLS12-381

zk-SNARK方式では、スカラーフィールド \(\mathbb{F}_r\) で非常に長い多項式を扱う必要があります。\(\mathbb{F}_r\) に大きな \(2^s\) の累乗根を確保している限り、高速フーリエ変換による効率的なマルチポイント評価/補間を行うことができます。

一般的に行われる ように、Zcashではこの曲線の中で、最適な拡大体の塔と、単純なねじり同型をターゲットにしています。モンゴメリ減算などの近似アルゴリズムのスペース効率を確保するため、最有意の \(r\) (および \(q\) )のビットが64ビットリムによってゼロに設定されるように|r reduce|をターゲットにします。

通常どおり、ペアリングのパフォーマンスを高める最適化を行うため、BLS曲線のパラメトリゼーションのハミング加重を低く抑えます。最終的に選択したのは、BLS12-381 という \(q \approx 2^{381}\) としての曲線です。

u = -0xd201000000010000
k = 12
q = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687 629129015664037894272559787
r = 52435875175126190479447740508185965837690552500527637822603658699938581184513
E(Fq) := y^2 = x^3 + 4
Fq2 := Fq[i]/(x^2 + 1)
E'(Fq2) := y^2 = x^3 + 4(i + 1)

Rust言語の実装

bellman zk-SNARKプロジェクトの一環として、Rust内の実装例の構築に取り掛かり始めました。ポータブルで、標準規格に準拠した高パフォーマンスのライブラリが目標です。zk-SNARKの特性により、定数時間内に効果的にプルーフを構築するのは難しいため、ライブラリは現在サイドチャネルへの抵抗には焦点をあてていません。

今後のブログでは、弊社の研究員がZcash最適化を目指し、この楕円曲線構築に使うために考案した数多くのテクニックやツールについてご紹介します。

[1]Menzes、Sarkar、Singh(http://eprint.iacr.org/2016/1102.pdf)は、2^110が多項式のスペースサイズとしては控えめな推定であり、スムーズな多項式のために調べる必要があるとしています。しかしBN曲線に関連したq=p^12の場合は、現在このスペースを効果的に調べる方法は公表されていません(多項式がスムーズかどうか一つずつチェックすると全実行時間は2^128よりも長くなります)。従って、知られている限りではZcashが現在使用している曲線を破るために、完全に解説された最も効果的でよく知られているアルゴリズムは、私たちの知る限りPollardのrhoであり、その実行時間はsqrt(q)~2^127です(研究結果の理解に手助けをしてくださったPalash SankarとShashank Singhに感謝します)。

cryptography, zkSNARKs | 全てのタグを見る