Bienvenue ! Vous découvrez 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!

Langue

Bellman: zk-SNARK dans Rust

Sean Bowe | Apr 04, 2017

Bellman est une bibliothèque en langage Rust permettant de créer des zk-SNARK (petites preuves à connaissance nulle simples à vérifier)_ de calculs arbitraires. L'objectif de Bellman est de simplifier l'utilisation et l'expérimentation des zk-SNARK pour le grand public, et constitue également un pas en avant en vue d'améliorer la sécurité et les performances de la prochaine version majeure de Zcash, Sapling.

Bellman contient une intégration de la construction de courbe elliptique BLS12-381 que nous avons décrit il y a quelques semaines, et qui sera publiée dans un document à venir rédigé par nos chercheurs. Cette construction a été spécifiquement conçue pour la création efficace de zk-SNARK, tout en conservant une importante marge de sécurité.

J'ai ajouté cette semaine une implémentation primitive d'un nouveau système de contrôle zk-SNARK conçu par Jens Groth. Sécurisée dans le modèle de groupe générique, la nouvelle conception produit des épreuves plus petites qui peuvent être fabriquées plus rapidement et nécessitent moins de mémoire.

Présentation des zk-SNARK

Si vous souhaitez découvrir le fonctionnement interne des zk-SNARK, Ariel Gabizon a publié une série de publications de blogs à propos des calculs sous-jacents que vous devriez vérifier ! Pour le moment, nous pouvons les comprendre au niveau superficiel.

Les zk-SNARK sont des épreuves puissantes qui, contrairement aux autres programmes d'épreuves à connaissance nulle, sont très petites (quelques centaines d'octets) et faciles à vérifier (plusieurs millisecondes), même si la déclaration vérifiée est longue et complexe. Leur propriété de connaissance nulle permet au contrôleur de masquer les détails relatifs au calcul pour le vérificateur pendant le processus. Ils sont donc utiles à la fois en termes de confidentialité et de performance.

Les seuls programmes de ce type connus pour leur efficacité sont des programmes de « pré-traitement ». Dans un sens, cela signifie qu'un type « d'environnement » doit être construit pour permettre au vérificateur d'évaluer la revendication et de produire une épreuve. Il n'existe aucun moyen connu d'élaborer un tel environnement sans disposer temporairement d'informations qui pourraient vous permettre de fabriquer de fausses épreuves.

Zcash, qui utilise des zk-SNARK pour ses transactions protégées, utilise des paramètres qui ont été élaborés au cours d'une cérémonie de calcul multi-parties très avancée décrite plus en détails ici. Les zk-SNARK sont également utiles dans le modèle du vérificateur désigné, où le vérificateur lui-même construit les paramètres requis. Par conséquent, ni le contrôleur ni le vérificateur ne sont concernés par son intégrité.

Dans de nombreux programmes zk-SNARK, la déclaration vérifiée est réduite à ce que l'on appelle un système de contraintes quadratiques de niveau 1, ou R1CS. Dans ce système, le contrôleur doit respecter un système de contraintes arithmétiques sur un ensemble de variables (éléments d'un grand champ principal \(\mathbb{F}_r\)) et est invité à produire une affectation des variables satisfaisant à ces contraintes.

Présentation de Bellman

Bellman n'en est encore qu'à ses balbutiements, mais nous pouvons déjà l'utiliser pour construire ces types d'épreuves. Actuellement, seule une API de très bas niveau est disponible. Nous pouvons utiliser cette dernière pour construire des DSL et différentes abstractions afin de synthétiser les circuits. Si vous souhaitez faire un essai, saisissez la caisse bellman crate de crates.io .

Toutes les abstractions de notre circuit sont rédigées de manière générique sur un trait du moteur qui gère la courbe elliptique et l'arithmétique à champ fini. Le trait ConstraintSystem se situe au cœur de la synthèse :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pub trait ConstraintSystem<E: Engine> {
    /// Allouer une variable privée dans le système de contrainte, en la définissant sur
    /// la valeur fournie.
    fn alloc(&mut self, valeur: E::Fr) -> Variable;

    /// Appliquer `A` * `B` = `C`.
    fn enforce(
        &mut self,
        a: LinearCombination<E>,
        b: LinearCombination<E>,
        c: LinearCombination<E>
    );
}

Deux décisions de conception majeures entrent en jeu ici :

  1. L'ensemble des attributions, affectations et contraintes de variables est réalisé sur le même chemin de code. Cela constitue une différence avec la conception de gadgetlib de libsnark, dans laquelle il était trop facile d'oublier une contrainte ou de ne pas remarquer des erreurs présentes dans les abstractions existantes en raison de cette séparation. Cette approche simplifie la rédaction d'abstractions et la révision du code.
  2. Toutes les attributions et affectations de variables peuvent s'effectuer simultanément et les affectations existantes ne peuvent pas être interrogées ni modifiées. Cela favorise une meilleure conception des gadgets et empêche les gadgets d'utiliser accidentellement les affectations pour « communiquer » entre eux. Cela présente également un avantage en termes de performance : dans la mesure où toutes les variables sont déjà affectées, l'application de contraintes pendant la vérification est directement synthétisée dans les témoins sous-jacents, afin d'éviter d'avoir à conserver un système de contraintes en mémoire.

Pour illustrer un type d'implémentation de gadget, voici comment une variable contrainte par des valeurs booléennes pourrait être implémentée, avec XOR :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#[derive(Clone)]
pub struct Bit {
    var: Variable,
    value: bool
}

impl Bit {
    pub fn alloc<E, CS>(e: &E,
                        cs: &mut CS,
                        value: bool) -> Bit
        where E: Engine, CS: ConstraintSystem<E> + ?Sized
    {
        // Allouer la variable
        let var = cs.alloc(
            si la valeur { E::Fr::one(e) } sinon { E::Fr::zero() }
        );

        // Appliquer (1 - var) * var = 0, qui requiert que
        // var soit 0 ou 1
        cs.enforce(
            LinearCombination::one(e) - var,
            LinearCombination::zero(e) + var,
            LinearCombination::zero(e)
        );

        Bit {
            var: var,
            value: value
        }
    }

    pub fn xor<E, CS>(&self,
                      e: &E,
                      cs: &mut CS,
                      sinon : &Bit) -> Bit
        où E: Engine, CS: ConstraintSystem<E>
    {
        let new_value = self.value ^ other.value;
        let new_var = cs.alloc(
            Si new_value { E::Fr::one(e) } sinon { E::Fr::zero() }
        );

        // 2a * b = a + b - c
        cs.enforce(
            LinearCombination::zero(e) + self.var + self.var,
            LinearCombination::zero(e) + other.var,
            LinearCombination::zero(e) + self.var + other.var - new_var
        );

        Bit {
            var: new_var,
            value: new_value
        }
    }
}

Créer un circuit consiste à implémenter les traits Circuit et Entrée :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub trait Circuit<E: Engine> {
    type InputMap: Input<E>;
    fn synthesize<CS: ConstraintSystem<E>>(self,
                                           engine: &E,
                                           cs: &mut CS)
                                           -> Self::InputMap;
}

pub trait Input<E: Engine> {
    fn synthesize<CS: PublicConstraintSystem<E>>(self, engine: &E, cs: &mut CS);
}

Cette conception divise les circuits en implémentation de Circuit, que les contrôleurs instancient pour construire des épreuves, et implémentation d'Entrée, que les contrôleurs et les vérificateurs utilisent pour procéder à l'affectation des entrées et à la synthèse des circuits connexes. Cela diffère de la méthode libsnark, dans laquelle ces chemins de code sont redondants, utilisent des fonctions utilitaires différentes et nécessitent une révision attentive du calcul pour garantir leur cohérence.

Dès que nous aurons réellement une implémentation de Circuit et d'Entrée, nous pourrons utiliser les fonctions fournies dans le module groth16 : créer une paire de clés (comprenant des trappes sélectionnées de manière aléatoire), construire une épreuve et procéder aux vérifications.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Créer une clé de contrôle et une clé de vérification
let (pk, vk) = {
    let tau = E::Fr::random(e, rng);
    let alpha = E::Fr::random(e, rng);
    let beta = E::Fr::random(e, rng);
    let gamma = E::Fr::random(e, rng);
    let delta = E::Fr::random(e, rng);
    let c = DummyCircuit;

    groth16::keypair(e, c, &tau, &alpha, &beta, &gamma, &delta)
};

// Construire une épreuve
let proof = {
    let r = E::Fr::random(e, rng);
    let s = E::Fr::random(e, rng);

    let c = DummyCircuit;

    groth16::prove(e, c, &r, &s, &pk).unwrap()
};

// Préparer la clé de vérification
let pvk = groth16::prepare_verifying_key(e, &vk);

// Vérifier l'épreuve
assert!(groth16::verify(e, |cs| {
    DummyInput
}, &proof, &pvk));

Travaux futurs

Ces fondations de niveau inférieur sont les seuls éléments disponibles actuellement dans Bellman. À l'avenir, nous rédigerons des outils qui nous permettront de construire des éléments tels que des fonctions de hachage et le cryptage de flux.

Bellman est encore en cours de développement et ne doit pas encore être utilisé dans les logiciels de production. En fait, son API n'expose délibérément aucun élément qui pourrait vous permettre de l'utiliser réellement ! Il sert actuellement d'excellente opportunité d'apprentissage pour créer des zk-SNARKs de manière sécurisée et efficace, et les enseignements que nous retiendrons de cette création façonneront l'avenir de Zcash.

Nous sommes également enthousiasmés par la rédaction de Bellman en Rust ! Si vous êtes rusticien et intéressé par les zk-SNARKs ou par Zcash, nous vous invitons à consulter notre projet, à rejoindre notre chat de la communauté ou à examiner les différents éléments que nous avons rédigés en Rust dans le passé, tel que notre code de cérémonie de calcul multi-parties.

Rust, cryptographie, zkSNARK | Afficher tous les mots-clés