Bem vindo! Novo em Zcash?
A rede Zcash é jovem, mas está evoluindo rapidamente! Cadastre-se e estaremos em contato com mais informações sobre como você pode começar a usar Zcash!

Idioma

Bellman: zk-SNARKs em Rust

Sean Bowe | Apr 04, 2017

Bellman é uma biblioteca de linguagem Rust para a construção zk-SNARKs - pequena e barata para verificar provas de conhecimento-nulo de cálculos arbitrários. O objetivo do bellman é tornar mais fácil para o público em geral usar e experimentar com zk-SNARKs, e também como um passo à frente para melhorar a segurança e o desempenho da próximo grande lançamento da Zcash, o Sapling.

O Bellman contém uma implementação da construção de curva elíptica BLS12-381 que descrevemos algumas semanas atrás, que aparecerá em um próximo artigo dos nossos cientistas. Esta construção foi projetada especificamente para a construção eficiente de zk-SNARKs, mantendo uma alta margem de segurança.

Esta semana, eu adicionei uma implementação primitiva de um novo sistema de provas zk-SNARK projetado por Jens Groth. Seguro no modelo de grupo genérico, o novo design produz provas menores que podem ser construídas mais rapidamente e com menos memória.

Visão geral da zk-SNARKs

Se você está interessado em como as zk-SNARKs trabalham internamente, Ariel Gabizon tem escrito uma série de postagens no blog sobre a matemática subjacente que você precisa conferir! Por agora, podemos compreendê-los de maneira superficial.

As Zk-SNARKs são provas poderosas que, ao contrário de outros esquemas de prova de conhecimento-nulo, são muito pequenas (algumas centenas de bytes) e baratas para verificar (vários milissegundos), mesmo se a declaração posta em prova for grande e complicada. Sua propriedade de conhecimento-nulo permite a quem aplica a prova ocultar detalhes sobre a computação da contra-parte verificadora no processo e, portanto, elas são úteis tanto para privacidade quanto desempenho.

Os únicos esquemas conhecidos por serem eficientes são de pré-processamento. Em certo sentido, isso significa que um tipo de "ambiente" deve ser construído, que permita a quem está fazendo a prova avaliar a declaração e produzir uma prova. Não existe uma maneira conhecida de construir tal ambiente sem necessariamente estar temporariamente em posse de informação que permita construir falsas provas.

Zcash, que usa zk-SNARKs para suas transações blindadas, usa parâmetros que foram construídos em uma cerimônia sofisticada de computação multipartidária que você pode ler sobre aqui. Zk-SNARKs também são úteis no modelo designado de verificação, onde o próprio verificador constrói os parâmetros necessários e, portanto, nem o provador nem o verificador estão preocupados com sua integridade.

Em muitos esquemas da zk-SNARK, a declaração que está sendo comprovada é reduzida para o que é chamado de um sistema de restrição quadrática de grau -1, ou R1CS. Neste sistema, é dado ao provador um sistema de restrições aritméticas sobre um conjunto de variáveis ​​(elementos em um campo primo grande \(\mathbb{F}_r\)), e pediu para produzir uma atribuição às variáveis ​​que satisfaz as restrições.

Visão geral do Bellman

Bellman está atualmente em sua infância, mas já podemos usá-lo para construir esses tipos de provas. Atualmente, apenas uma API de nível muito baixo está disponível, sobre a qual podemos construir DSLs e várias abstrações para sintetizar circuitos. Se você quiser experimentar com ele, pegue o bellman crate from crates.io.

Todas as nossas abstrações de circuitos são escritas genericamente sobre um traço do Motor que manipula a curva elíptica e a aritmética de campos finitos. A síntese do circuito central é a característica do ConstraintSystem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pub trait ConstraintSystem<E: Engine> {
    /// Allocate a private variable in the constraint system, setting it to
    /// the provided value.
    fn alloc(&mut self, value: E::Fr) -> Variable;

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

Existem duas importantes decisões de desenho aqui:

  1. Toda a alocação, atribuição e restrição de variáveis ​​é executada sobre o mesmo caminho de código. Isso difere do design do libsnark's gadgetlib, para o qual era muito fácil esquecer uma restrição ou perceber erros em abstrações existentes por causa da separação. Essa abordagem facilita a gravação de abstrações e a realização de revisão de código.
  2. Todas as alocações e atribuições de variáveis ​​são feitas simultaneamente, e as atribuições existentes não podem ser consultadas ou modificadas. Isso encoraja um melhor design de gadgets e impede que os gadgets usem acidentalmente as atribuições para "comunicar" uns com os outros. Isso também tem um benefício de desempenho: já que todas as variáveis ​​já estão atribuídas, a imposição de restrições durante a prova é sintetizada diretamente nas testemunhas subjacentes para evitar ter que manter um sistema de restrição na memória.

Como exemplo de um tipo de implementação de gadget, veja como uma variável restrita boolean poderia ser implementada, juntamente com 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
    {
        // Allocate the variable
        let var = cs.alloc(
            if value { E::Fr::one(e) } else { E::Fr::zero() }
        );

        // Enforce (1 - var) * var = 0, which requires
        // var to be either 0 or 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,
                      other: &Bit) -> Bit
        where E: Engine, CS: ConstraintSystem<E>
    {
        let new_value = self.value ^ other.value;
        let new_var = cs.alloc(
            if new_value { E::Fr::one(e) } else { 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
        }
    }
}

Construir um circuito é uma questão de implementar os traços Circuit e Input:

 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);
}

Este projeto divide os circuitos em uma implementação Circuit, que os provadores instanciam para construir provas e uma implementação Input, que provadores e verificadores usam para realizar a alocação de entrada e síntese de circuitos relacionados. Isso difere do libsnark, onde esses caminhos de código são redundantes, usam funções de utilitário diferentes e exigem uma cuidadosa revisão de código para garantir a consistência.

Uma vez que realmente temos uma implementação de Circuit e` Input`, podemos usar as funções fornecidas no módulo groth16: criar um par de chaves (com algumas trapdoors selecionadas aleatoriamente), construir uma prova e realizar verificações:

 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
// Create a proving key and verifying key
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)
};

// Construct a proof
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()
};

// Prepare the verifying key
let pvk = groth16::prepare_verifying_key(e, &vk);

// Verify proof
assert!(groth16::verify(e, |cs| {
    DummyInput
}, &proof, &pvk));

Trabalho futuro

Esses fundamentos de nível inferior são tudo o que está disponível no Bellman agora. No futuro, estaremos escrevendo ferramentas que nos permitam construir coisas como funções de hash e cifras de fluxo.

Bellman ainda está em desenvolvimento e não deve ser usado em software de produção ainda. Na verdade, sua API deliberadamente não expõe nada que permita que você realmente o use! Atualmente serve como uma excelente oportunidade de aprendizado para a construção de zk-SNARKs de forma segura e eficiente, e as lições que aprendemos com a construção desse projeto irão moldar o futuro do Zcash.

Também estamos animados em escrever Bellman em Rust! Se você é um Rustacean e está interessado em zk-SNARKs ou Zcash, nós convidamos você a verificar o nosso projeto, junte-se ao nosso community chat ou veja algumas das várias coisas que escrevemos em Rust antes, como o nosso código de cerimônia de computação multipartidário.

Rust, cryptography, zkSNARKs | Veja todas as tags