¡Bienvenido! ¿Eres nuevo en 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: Nueva Construcción de la Curva Elíptica de zk-SNARK

Sean Bowe | Mar 11, 2017

Nuestro equipo está continuamente trabajando para mejorar la seguridad, el rendimiento y la usabilidad de nuestras transacciones blindadas que preservan la privacidad. Como mencionamos en nuestro artículo de blog sobre el futuro próximo de Zcash, estamos trabajando en una colección de mejoras criptográficas para la próxima versión de Zcash, llamada Sapling. Uno de nuestros objetivos es hacer que los pagos blindados sean más eficientes y menos intensivos en memoria. También pretendemos mejorar el nivel de seguridad concreto de la construcción de la curva elíptica que usamos para nuestras pruebas de zk-SNARK.

La curva BLS12-381.

Pasé algún tiempo el mes pasado diseñando e implementando una nueva construcción de curva elíptica compatible con el emparejamiento que sea óptima para zk-SNARKs en el nivel de seguridad de 128 bits. La construcción minimiza los costos de rendimiento y usabilidad al tiempo que aumenta nuestros márgenes de seguridad.

La construcción aparecerá en un próximo paper de nuestros científicos, donde será acompañada por una descripción más detallada de la construcción y de cómo fue seleccionada.

Curvas de Barreto-Naehrig

Las curvas de Barreto-Naehrig (BN) son una clase de construcciones de curvas elípticas compatibles con el emparejamiento construidas sobre un campo base \(\mathbb{F}_q\) de orden \(r\), donde \(r \approx q\). Nuestra construcción de curva actual tiene \(q \approx 2^{254}\). El año pasado, Kim y Barbulescu presentaron una variante del algoritmo de Matiz de Campo Numérico que redujo una estimación conservadora [1] del nivel de seguridad a alrededor de 110 bits, basados en un paper reciente.

Es posible construir una nueva curva BN que apunte a la seguridad de 128 bits, incluso de acuerdo con esta estimación conservadora, seleccionando una curva más cercana a \(q \approx 2^{384}\). Sin embargo, el mayor orden de grupo \(r\) perjudica el rendimiento de la multiexponenciación, las transformaciones rápidas de fourier y otras operaciones criptográficas que necesitamos realizar de manera eficiente en los esquemas de zk-SNARK y las computaciones multi-pares. Además, el campo escalar más grande \(\mathbb{F}_r\) hace que el material de las claves sea innecesariamente grande.

Curvas de Barreto-Lynn-Scott

Las curvas de Barreto-Lynn-Scott (BLS) son una clase ligeramente más antigua de curvas compatibles con el emparejamiento que ahora parecen ser más útiles para apuntar a este nivel de seguridad. Investigaciones actuales sugieren que con \(q \approx 2^{384}\), y con un grado de incrustación igual a 12, estas curvas funcionan para un nivel de seguridad de 128 bits. Convenientemente, el orden de grupo para estas curvas es \(r \approx 2^{256}\), lo que nos permite evitar los inconvenientes de rendimiento y usabilidad que acompañan a un campo escalar más grande.

BLS12-381

En los esquemas de zk-SNARK, necesitamos manipular polinomios muy grandes sobre el campo escalar \(\mathbb{F}_r\). Podemos realizar una evaluación/interpolación multi-punto eficiente con transformaciones fourier rápidas, siempre y cuando nos aseguremos de que \(\mathbb{F}_r\) está equipado con una gran raíz de unidad \(2^s\).

Como se hace normalmente, apuntamos a una subfamilia de estas curvas que tenga torres de campo de extensión óptimas e isomorfismos de torsión simple. Con el fin de asegurar que las reducciones de Montgomery y otros algoritmos de aproximación sean eficientes en términos de espacio, apuntamos a un \(r \approx 2^{255}\) tal que el bit más significativo de \(r\) (y de \(q\)) es desmontado con miembros de 64 bits.

Como de costumbre, con el fin de optimizar el rendimiento de emparejamiento, nos aseguramos de que la parametrización de la curva BLS tenga un peso Hamming ligero. La curva que hemos elegido en última instancia se llama BLS12-381 con \(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)

Implementación en el lenguaje Rust

He comenzado a trabajar en una implementación de la construcción en Rust como parte de mi proyecto de zk-SNARK bellman. La biblioteca tiene el objetivo de ser portable, ajustada a las normas, y de alto rendimiento. Debido a la naturaleza de los esquemas de zk-SNARK, es difícil construir pruebas de manera eficiente en tiempo constante, por lo que la biblioteca no se centra actualmente en la resistencia de canal lateral.

Futuras publicaciones del blog describirán una serie de técnicas y herramientas que nuestros científicos han ideado para usar esta construcción de curvas con el fin de optimizar Zcash.

[1]Menzes, Sarkar y Singh (http://eprint.iacr.org/2016/1102.pdf) muestran que 2^110 es una estimación conservadora para el tamaño del espacio de polinomios que necesita ser escaneado para polinomios continuamente diferenciables. Sin embargo, para el caso q=p^12 relevante para las curvas BN no existe un método eficiente actualmente publicado para escanear este espacio. (Verificar la diferenciabilidad continua de cada polinomio por separado daría como resultado un tiempo de ejecución total superior a 2^128). Por tanto, hasta donde sabemos, el algoritmo más eficiente actualmente conocido y completamente descrito para romper la curva que Zcash utiliza actualmente es el rho de Pollard, que correría en un tiempo sqrt(q)~2^127. (Gracias a Palash Sankar y Shashank Singh por ayudar a entender su resultado.)

cryptography, zkSNARKs | Ver todos los tags