nonnative
v0.3.0
Die nonnative Bibliothek stellt R1CS-Einschränkungen zum Überprüfen von Berechnungen über ein nicht-natives Feld in einem Beweissystem bereit.
Die Bibliothek basiert auf dem Constraint-Writing-Framework arkworks-rs und wird unter der MIT-Lizenz und der Apache v2-Lizenz veröffentlicht (siehe Lizenz).
WARNUNG: Dies ist ein akademischer Proof-of-Concept-Prototyp. Insbesondere wurde der Code nicht sorgfältig überprüft. Diese Implementierung ist NICHT für den Produktionseinsatz bereit.
Diese Bibliothek implementiert ein Feld-Gadget für ein Primfeld Fp über einem anderen Primfeld Fq wobei p != q .
Beim Schreiben von Beschränkungssystemen für viele kryptografische Beweise sind wir auf ein natives Feld beschränkt (z. B. das Skalarfeld der paarungsfreundlichen Kurve). Dies kann unpraktisch sein; Beispielsweise erfordert die rekursive Zusammensetzung von Beweisen über Kurvenzyklen, dass der Verifizierer Berechnungen über ein nicht-natives Feld durchführt.
Die Bibliothek ermöglicht es, Berechnungen über ein nicht-natives Feld auf die gleiche Weise zu schreiben, wie man Berechnungen über das native Feld schreiben würde. Dies führt natürlich zu einem zusätzlichen Overhead, den wir durch verschiedene Optimierungen minimieren.
Da das nicht-native Feld das FieldVar Merkmal in Arkworks implementiert, können wir es wie eine native Feldvariable ( FpVar ) behandeln.
Wir können die Standardfeldoperationen wie + , - und * ausführen. Sehen Sie sich das folgende Beispiel an:
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 ) ? ; Nach jeder Multiplikation führt unsere Bibliothek intern eine Reduzierungsoperation durch, die einen Zwischentyp NonNativeFieldMulResultVar auf den normalisierten Typ NonNativeFieldVar reduziert. Dadurch kann ein Benutzer eine Abfolge von Vorgängen nahtlos ausführen, ohne sich um die zugrunde liegenden Details kümmern zu müssen.
Diese Operation ist jedoch teuer und manchmal vermeidbar. Wir können die Anzahl der Einschränkungen reduzieren, indem wir diesen Zwischentyp verwenden, der nur Additionen unterstützt. Zur Multiplikation muss es wieder auf NonNativeFieldVar reduziert werden. Unten finden Sie ein Skelettbeispiel.
Um a * b + c * d zu berechnen, lautet die einfache (aber teurere) Implementierung wie folgt:
let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;
Dadurch werden insgesamt zwei Reduktionsoperationen durchgeführt, eine für jede Multiplikation.
Wir können eine Reduzierung einsparen, indem wir das NonNativeFieldMulResultGadget wie folgt verwenden:
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()?;
Es führt nur einen Reduzierungsvorgang durch und ist etwa doppelt so schnell wie die erste Implementierung.
Die Bibliothek verwendet die Standardidee, mehrere Gliedmaßen zu verwenden, um ein Element des Zielfelds darzustellen. Beispielsweise kann ein Element im TargetField durch drei BaseField-Elemente (dh die Gliedmaßen) dargestellt werden.
TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)
Nach einigen Berechnungen werden die Gliedmaßen überfordert und müssen reduziert werden, um weitere Berechnungen durchführen zu können.
Wir nutzen intensiv die Optimierungstechniken in [KPS18] und [OWWB20]. Beide Werke verfügen über eigene Open-Source-Bibliotheken: xJsnark und bellman-bignat. Im Vergleich dazu arbeitet diese Bibliothek mit der Arkworks-Umgebung und ist außerdem für die Dichte statt für die Anzahl der Einschränkungen optimiert, was für holografische Zero-Knowledge-Beweise wie Marlin nützlich ist.
Die Bibliothek wird nach Ihrem Ermessen unter einer der folgenden Lizenzen lizenziert.
Sofern Sie nicht ausdrücklich etwas anderes angeben, unterliegt jeder von Ihnen zur Aufnahme in diese Bibliothek eingereichte Beitrag einer Doppellizenz wie oben (wie in der Apache v2-Lizenz definiert), ohne zusätzliche Bedingungen oder Konditionen.
[KPS18]: AE Kosba, C. Papamanthou und E. Shi. „xJsnark: ein Framework für effiziente überprüfbare Berechnungen“, in Proceedings of the 39th Symposium on Security and Privacy , ser. S&P '18, 2018, S. 944–961.
[OWWB20]: A. Ozdemir, RS Wahby, B. Whitehat und D. Boneh. „Skalierung überprüfbarer Berechnungen mithilfe effizienter Satzakkumulatoren“, in Proceedings of the 29th USENIX Security Symposium , ser. Sicherheit '20, 2020.
