Bem vindo! Novo em 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!

Idioma

BLS12-381: Nova construção de curva elíptica do zk-SNARK

Sean Bowe | Mar 11, 2017

Nossa equipe está continuamente trabalhando para melhorar a segurança, o desempenho e a usabilidade de nossas transações blindadas que preservam a privacidade. Como mencionamos em nossas próximas prioridades no blog, estamos trabalhando em uma coleção de melhorias criptográficas para a próxima versão do Zcash chamada Sapling. Um de nossos objetivos é tornar os pagamentos blindados mais eficientes e menos intensivos em memória. Pretendemos também melhorar o nível de segurança concreto da construção da curva elíptica que usamos para as nossas provas zk-SNARK.

A curva BLS12-381.

Passei algum tempo no mês passado projetando e implementando uma nova construção de curva elíptica compatível com o emparelhamento que é ideal para zk-SNARKs no nível de segurança de 128 bits. A construção minimiza os custos de desempenho e usabilidade, aumentando nossas margens de segurança.

A construção aparecerá em um próximo artigo de nossos cientistas, onde será acompanhada por uma descrição mais completa da construção e como foi selecionada.

Curvas de Barreto-Naehrig

As curvas de Barreto-Naehrig (BN) são uma classe de construções de curvas elípticas "compatíveis com o emparelhamento" construídas sobre um campo de base \(\mathbb{F}_q\) de ordem \(r\), onde \(r \approx q\). Nossa construção atual da curva tem \(q \approx 2^{254}\). No ano passado, Kim e Barbulescu apresentaram uma variante do algoritmo Number Field Sieve, que reduziu uma estimativa conservadora [1] do nível de segurança para cerca de 110 bits com base em um 'artigo recente'.

É possível construir uma nova curva BN que tenha como alvo a segurança de 128 bits, mesmo de acordo com essa estimativa conservadora, selecionando uma curva mais próxima de \(q \approx 2^{384}\). No entanto, a ordem de grupo maior \(r\) prejudica o desempenho de multi-exponenciação, fast fourier transforma e outras operações criptográficas que precisamos para executar com eficiência em zk-SNARK esquemas e multi-partido computações. Além disso, o maior campo escalar \(\mathbb{F}_r\) torna o material chave desnecessariamente grande.

Curvas de Barreto-Lynn-Scott

As curvas de Barreto-Lynn-Scott (BLS) são uma classe ligeiramente mais antiga de curvas de emparelhamento que agora parecem ser mais úteis para segmentar esse nível de segurança. Pesquisas atuais sugerem que com \(q \approx 2^{384}\) e com um grau de incorporação de 12, essas curvas têm como alvo o nível de segurança de 128 bits. Convenientemente, a ordem do grupo para essas curvas é \(r \approx 2^{256}\), o que nos permite evitar os inconvenientes de desempenho e usabilidade que acompanham um campo escalar maior.

BLS12-381

Em esquemas de zk-SNARK, precisamos manipular polinômios muito grandes sobre o campo escalar \(\mathbb{F}_r\). Podemos realizar eficiente multi-ponto de avaliação / interpolação com fast fourier transforma, contanto que garantamos que \(\mathbb{F}_r\) rstá equipado com um grande \(2^s\) raiz da unidade.

Como é comum, nós almejamos uma subfamília dessas curvas que tem torres de campo de extensão ótimas e isomorfismos de torção simples. Para garantir que as reduções de Montgomery e outros algoritmos de aproximação sejam eficientes em termos de espaço. Nós miramos em \(r \approx 2^{255}\) de modo que o bit mais significativo de \(r\) (e \(q\)) são unset com membros de 64 bits.

Como de costume, para otimizar o desempenho do emparelhamento, asseguramos que a parametrização da curva BLS tenha baixo peso Hamming. A curva que finalmente escolhemos é denominada BLS12-381 como \(q \approx 2^{381}\).

u = -0xd201000000010000
k = 12
q = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687 629129015664037894272559787
r = 52435875175126190479447740508185965837690552500527637822603658699938581184513
E(Fq) := y^2 = x^3 + 4
Fq2 := Fq[i]/(x^2 + 1)
E'(Fq2) := y^2 = x^3 + 4(i + 1)

Implementação de linguagem Rust

Comecei a trabalhar em uma implementação da construção em Rust como parte do meu projeto bellman projeto zk-SNARK. A biblioteca tem o objetivo de ser portátil, compatível com padrões e de alto desempenho. Devido à natureza dos esquemas de zk-SNARK, é difícil construir eficientemente provas em tempo constante, e assim a biblioteca não foca atualmente na resistência do canal lateral.

Postagens futuras no blog irão descrever uma série de técnicas e ferramentas que os nossos cientistas têm concebido para usar esta construção de curva para otimizar Zcash.

[1]Menzes, Sarkar e Singh (http://eprint.iacr.org/2016/1102.pdf) mostram 2^110 é uma estimativa conservadora para o tamanho do espaço de polinômios que precisa ser verificado para suavizar polinômios. No entanto, para o caso q=p^12 relevante para as curvas BN, não há nenhum método eficiente atualmente publicado para escanear este espaço. (Verificando cada polinômio separadamente para a suavidade resultaria em tempo de execução total maior do que 2^128). Assim, ao melhor de nosso conhecimento o algoritmo mais eficiente atualmente conhecido totalmente descrito para quebrar a curva Zcash está atualmente usando rho de Pollard, o que seria executado no tempo sqrt(q)~2^127. (Os nossos agradecimentos a Palash Sankar e Shashank Singh por ajudarem a compreender o seu resultado.)

cryptography, zkSNARKs | Veja todas as tags