nonnative
v0.3.0
La bibliothèque nonnative fournit des contraintes R1CS pour vérifier les calculs sur un champ non natif dans un système de preuve.
La bibliothèque est basée sur le framework d'écriture de contraintes arkworks-rs et est publiée sous la licence MIT et la licence Apache v2 (voir Licence).
AVERTISSEMENT : Il s'agit d'un prototype académique de validation de principe ; en particulier, son code n'a pas fait l'objet d'une révision minutieuse. Cette implémentation n'est PAS prête pour une utilisation en production.
Cette bibliothèque implémente un gadget de champ pour un champ premier Fp sur un autre champ premier Fq où p != q .
Lors de l'écriture de systèmes de contraintes pour de nombreuses preuves cryptographiques, nous sommes limités à un champ natif (par exemple, le champ scalaire de la courbe d'appariement). Cela peut être gênant ; par exemple, la composition récursive de preuves via des cycles de courbes nécessite que le vérificateur calcule sur un champ non natif.
La bibliothèque permet d'écrire des calculs sur un champ non natif de la même manière que l'on écrirait des calculs sur le champ natif. Cela introduit naturellement une surcharge supplémentaire, que nous minimisons grâce à diverses optimisations.
Étant donné que le champ non natif implémente le trait FieldVar dans arkworks, nous pouvons le traiter comme une variable de champ native ( FpVar ).
Nous pouvons effectuer les opérations de champ standard, telles que + , - et * . Voir l'exemple suivant :
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 ) ? ; Après chaque multiplication, notre bibliothèque effectue en interne une opération de réduction , qui réduit un type intermédiaire NonNativeFieldMulResultVar au type normalisé NonNativeFieldVar . Cela permet à un utilisateur d'effectuer de manière transparente une séquence d'opérations sans se soucier des détails sous-jacents.
Cependant, cette opération est coûteuse et est parfois évitable. Nous pouvons réduire le nombre de contraintes en utilisant ce type intermédiaire, qui ne supporte que les ajouts. Pour multiplier, il doit être réduit à NonNativeFieldVar . Voir ci-dessous pour un exemple de squelette.
Pour calculer a * b + c * d , l'implémentation simple (mais plus coûteuse) est la suivante :
let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;
Cela effectue deux opérations de réduction au total, une pour chaque multiplication.
Nous pouvons économiser une réduction en utilisant NonNativeFieldMulResultGadget , comme suit :
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()?;
Il effectue une seule opération de réduction et est environ 2 fois plus rapide que la première implémentation.
La bibliothèque utilise l'idée standard consistant à utiliser plusieurs membres pour représenter un élément du champ cible. Par exemple, un élément de TargetField peut être représenté par trois éléments BaseField (c'est-à-dire les membres).
TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)
Après quelques calculs, les membres deviennent submergés et doivent être réduits afin de pouvoir effectuer davantage de calculs.
Nous utilisons largement les techniques d'optimisation de [KPS18] et [OWWB20]. Les deux œuvres ont leurs propres bibliothèques open source : xJsnark et bellman-bignat. Par rapport à eux, cette bibliothèque fonctionne avec l'environnement arkworks et est également optimisée pour la densité plutôt que pour le nombre de contraintes, ce qui est utile pour les preuves holographiques à connaissance nulle comme Marlin.
La bibliothèque est sous licence sous l'une des licences suivantes, à votre discrétion.
Sauf indication contraire explicite de votre part, toute contribution que vous soumettez pour inclusion dans cette bibliothèque sera sous double licence comme ci-dessus (telle que définie dans la licence Apache v2), sans aucun terme ou condition supplémentaire.
[KPS18] : AE Kosba, C. Papamanthou et E. Shi. "xJsnark : un cadre pour un calcul vérifiable efficace", dans Actes du 39e Symposium sur la sécurité et la confidentialité , ser. S&P '18, 2018, pages 944 à 961.
[OWWB20] : A. Ozdemir, RS Wahby, B. Whitehat et D. Boneh. "Mise à l'échelle du calcul vérifiable à l'aide d'accumulateurs d'ensembles efficaces", dans Actes du 29e USENIX Security Symposium , ser. Sécurité '20, 2020.
