nonnativeダウンロード - nonnativeソースコードのダウンロード

nonnative

その他のソースコード

v0.3.0

ダウンロード

非ネイティブフィールドガジェット

nonnativeライブラリは、証明システム内の非ネイティブフィールド上の計算をチェックするための R1CS 制約を提供します。

このライブラリは、制約記述フレームワーク arkworks-rs に基づいており、MIT ライセンスおよび Apache v2 ライセンスに基づいてリリースされています (ライセンスを参照)。

警告:これは学術的な概念実証のプロトタイプです。特に、注意深くコードレビューを受けていません。この実装は実稼働環境で使用する準備ができていません。

概要

このライブラリは、別の素数フィールドFq ( p != q ) 上に素数フィールドFpのフィールドガジェットを実装します。

多くの暗号証明用の制約システムを作成する場合、ネイティブフィールド (ペアリングに適した曲線のスカラーフィールドなど) に制限されます。これは不便な場合があります。たとえば、曲線のサイクルによる証明の再帰的合成では、検証者が非ネイティブフィールドを計算する必要があります。

このライブラリを使用すると、ネイティブフィールドに対して計算を記述するのと同じ方法で、非ネイティブフィールドに対して計算を記述することができます。これにより当然追加のオーバーヘッドが発生しますが、さまざまな最適化を使用してオーバーヘッドを最小限に抑えます。

使用法

非ネイティブフィールドは arkworks のFieldVarトレイトを実装しているため、ネイティブフィールド変数 ( FpVar ) のように扱うことができます。

+ 、 - 、 *などの標準的なフィールド操作を実行できます。次の例を参照してください。

 let a = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "a" ) , || Ok ( a_value ) ) ? ;
let b = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "b" ) , || Ok ( b_value ) ) ? ;

// add
let a_plus_b = & a + & b ;

// sub
let a_minus_b = & a - & b ;

// multiply
let a_times_b = & a * $b ;

// enforce equality
a . enforce_equal ( & b ) ? ;

高度な最適化

各乗算の後、ライブラリは内部でreduce演算を実行し、中間型NonNativeFieldMulResultVar正規化型NonNativeFieldVarに還元します。これにより、ユーザーは基礎的な詳細を気にすることなく、一連の操作をシームレスに実行できます。

ただし、この操作はコストがかかるため、回避可能な場合もあります。加算のみをサポートするこの中間型を使用することで、制約の数を減らすことができます。乗算するには、 NonNativeFieldVarに戻す必要があります。スケルトンの例については、以下を参照してください。

a * b + c * dを計算するための簡単な (しかしより高価な) 実装は次のとおりです。

 let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;

これにより、乗算ごとに 1 つずつ、合計 2 つのreduce演算が実行されます。

次のようにNonNativeFieldMulResultGadget使用すると、1 つの削減を保存できます。

 let a_times_b = a.mul_without_reduce(&b)?;
let c_times_d = c.mul_without_reduce(&d)?;
let res = (&a_times_b + &c_times_d)?.reduce()?;

これは、 reduce操作を 1 つだけ実行し、最初の実装よりも約 2 倍高速になります。

インスピレーションと基本デザイン

このライブラリでは、複数のリムを使用してターゲットフィールドの要素を表すという標準的な考え方が採用されています。たとえば、TargetField 内の要素は 3 つの BaseField 要素 (つまり、四肢) で表すことができます。

 TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)

いくつかの計算の後、手足は圧倒され、より多くの計算を行うために縮小する必要があります。

私たちは [KPS18] と [OWWB20] の最適化手法を多用しています。どちらの作品にも、xJsnark と bellman-bignat という独自のオープンソースライブラリがあります。それらと比較すると、このライブラリは arkworks 環境で動作し、制約の数ではなく密度についても最適化されているため、Marlin のようなホログラフィックのゼロ知識証明に役立ちます。