Langue

Culture de Sapling : Nouvelles Fondations Crypto

Sean Bowe | Jul 26, 2017

La prochaine mise à niveau majeure du protocole de Zcash, dont le nom de code est Sapling, comportera un certain nombre d'améliorations concernant les performances, la sécurité et l’ergonomie de nos transactions blindées. Ceci est le premier d'une série de billets de blog qui exploreront les progrès réalisés dans le développement de Sapling.

BLS12-381 : une nouvelle courbe zk-SNARK

Les zk-SNARKs de Zcash reposent actuellement sur une construction de courbe elliptique Barreto-Naehrig, favorable au couplage, implémentée dans libsnark et conçue par nos scientifiques il y a de nombreuses années. Depuis lors, l'optimisation de Kim–Barbulescu de l'algorithme du crible de corps de nombre a réduit le niveau de sécurité présumé de cette courbe à environ 110 bits, bien que, selon les dernières recherches, la sécurité concrète de la courbe actuelle soit toujours d'environ 128 bits comme prévu initialement.

En guise de précaution supplémentaire, nous profitons de l'occasion pour mettre à jour notre courbe elliptique dans la mise à niveau de Sapling. Plus tôt cette année, j'ai présenté une nouvelle courbe appelée BLS12-381. Cette courbe cible la sécurité 128 bits en prenant en compte les recommandations de prudence suggérées par plusieurs articles récents.

Il existe à présent une implémentation de cette courbe en langage Rust. Elle comporte de solides garanties de sécurité mémoire car elle n'utilise pas d'optimisation d'assemblage ou de code non sûr{}. Malgré le fait qu’il s’agisse d’une courbe plus large, cette nouvelle implémentation est plus efficace que l’implémentation de BN254 que nous utilisons actuellement dans Zcash.

Pairing crate benchmarks

Les accélérations sont particulièrement prononcées lors du couplage et de l’arithmétique \(\mathbb{G}_2\) , qui augmente les performances des preuves et des vérification de zk-SNARK.

Nouvel algorithme multi-exponentiation

La partie la plus coûteuse de la création d'une preuve zk-SNARK est l'évaluation de grands polynômes sur les groupes \(\mathbb{G}_1\) et \(\mathbb{G}_2\) de la courbe elliptique. Cela se fait avec un algorithme « multi-exponentiation » qui calcule \(\prod_{i=0}^{n}{b_{i}^{s_i}}\) pour un grand nombre d'exposants \(\vec{s}\) qui résident en mémoire et un grand nombre de bases \(\vec{b}\) qui résident sur le disque à l'intérieur de la clé de preuve zk-SNARK.

Actuellement, nous utilisons l’implémentation de l'algorithme Bos-Coster de libsnark. Dans le pire des cas, cet algorithme utilise une mémoire équivalente au nombre de bases traitées, de sorte que la seule possibilité pour diminuer l'utilisation de la mémoire est de travailler avec des sous-ensembles de bases plus petits, chacun leur tour. À titre d'exemple, Ariel Gabizon a implémenté ce genre d'optimisation dans une modification de libsnark.

Libsnark a récemment implémenté une variante de l'algorithme de Pippenger qui divise la multi-exponentiation en plusieurs partie de l'exposant au niveau du bit, accumulant des bases dans des seaux et effectuant une somme par parties. Cet algorithme n'est pas seulement plus efficace que Bos-Coster, mais il est également très pratique dans le contexte de streaming de preuves. Grâce à cet algorithme, nous pouvons éviter de charger la clé de preuve en mémoire avant de construire une preuve, qui est une source principale d'utilisation de la mémoire dans notre système.

Nouveau système de preuve

Évidemment, l'exécution d’un nombre moins important de multi-exponentiations serait également un bon moyen d'améliorer les performances d'exécution. Nous envisageons sérieusement l'utilisation d'un nouveau système de preuve zk-SNARK, découvert par Jens Groth, pour remplacer PGHR (Pinnochio). Ce système de preuve est capable de faire de meilleures hypothèses cryptographiques, mais a des preuves plus petites et des temps de preuve/vérification plus rapide.

De plus, le nouveau système de preuve de Groth nous permet de concevoir des calculs multipartites moins coûteux et d'autres fonctionnalités très intéressantes dont nous parlerons plus en détails dans un futur billet de blog.

Étapes suivantes

Bien que les efforts ci-dessus combinés améliorent considérablement l'utilisation de la mémoire et les temps de preuve, la réduction de la taille de notre circuit zk-SNARK aura un effet beaucoup plus perceptible. Nous avons créé un certain nombre de nouvelles primitives crytographiques sur la construction BLS12-381, ce qui nous permet de réduire la taille de nos circuits arithmétiques, de réduire la taille des adresses Zcash et de simplifier le protocole.

Dans notre prochain billet de blog, nous nous pencherons davantage sur ces primitives et sur la manière dont toutes ces améliorations contribueront aux performances de nos zk-SNARKs.

Sapling, zkSNARKs, protocole | Afficher tous les mots-clés

Notice: Network Upgrade Overwinter will activate at block 347500, to be mined 2018-06-25 12:00 UTC-04:00 assuming 150 seconds/block