Curve Trees, Helios y Selene

Un árbol de Merkle con puntos en lugar de hashes, donde demostrar un camino ocupa kilobytes

Repaso del árbol de Merkle

Un árbol de Merkle calcula el hash de los datos por parejas (o grupos), después el hash de los hashes, y así hasta una única raíz. Para demostrar que un elemento está en el árbol se muestra el camino: los hermanos en cada nivel. El camino tiene longitud log n.

Pero necesitamos demostrar el camino con conocimiento cero, sin mostrar ni la hoja ni los hermanos. Eso significa codificar «calcular un hash» en un circuito aritmético y demostrar el circuito. Los hashes normales (Keccak, SHA) son muy caros en estos circuitos: decenas de miles de restricciones por hash.

La idea de Curve Trees

Usar un compromiso de Pedersen vectorial como «hash»:

Es un buen hash para nuestro propósito (encontrar una colisión es tan difícil como el logaritmo discreto), y en un circuito aritmético sale casi gratis, siempre que los números xᵢ sean escalares de la curva en la que viven los Gᵢ.

El problema: los hijos son puntos de la curva E₁, así que sus coordenadas son elementos del cuerpo base de E₁. Para usarlas como escalares necesitamos una curva E₂ cuyo cuerpo de escalares sea igual al cuerpo base de E₁. En el siguiente nivel, al revés. Un par así se llama ciclo de curvas.

Helios y Selene

Para Monero se eligió un ciclo especial «anclado» a Ed25519: las coordenadas de los puntos de Ed25519 viven en el cuerpo F_p, p = 2²⁵⁵ − 19, y una de las curvas del ciclo (Selene) tiene exactamente este F_p como cuerpo de escalares. Así, las hojas (coordenadas de O, I, C en Ed25519) se pueden «hashear» directamente sobre Selene, luego las coordenadas de los puntos de Selene sobre Helios, y así sucesivamente, alternando.

Los nombres vienen de los dioses griegos del Sol (Helios) y de la Luna (Selene): dos curvas que «orbitan» la una alrededor de la otra.

Cómo se demuestra el camino

Para cada nivel, el probador no muestra el punto padre en sí, sino su rerandomización (el punto más un múltiplo aleatorio de otro generador), y demuestra en un circuito sobre la curva correspondiente:

1. «conozco los hijos, uno de los cuales es el punto rerandomizado del nivel anterior»;
2. «estos hijos, combinados con los generadores, dan el padre (rerandomizado)».

Para comprobar de forma eficiente las operaciones de curva dentro del circuito se usan divisores (la técnica de Liam Eagen): en lugar de una multiplicación escalar paso a paso, se demuestra una propiedad de una función racional sobre la curva, lo cual es mucho más barato. Ver Generalized Bulletproofs y divisores.

Todos los niveles sobre una curva se demuestran con un Generalized Bulletproof, y los de la otra, con un segundo. El resultado son dos pruebas cuyo tamaño crece con la profundidad del árbol, es decir, de forma logarítmica con el número de salidas.

Actualizar el árbol

Cuando una salida supera el bloqueo de 10 bloques, el nodo la añade al árbol y recalcula el camino hasta la raíz. Un compromiso vectorial se actualiza de forma incremental: añadir un hijo significa sumar x·Gᵢ al padre, sin recalcular los demás. Si hay una reorganización de la cadena, los cambios se deshacen.