Técnico › FCMP++

Rerandomización de entradas

Cómo gastar una salida del árbol sin mostrar cuál

En resumen

En FCMP++ una entrada de transacción no es una referencia a una salida, sino una copia «repintada» de ella: a cada punto de la salida se le suma un múltiplo aleatorio de un generador aparte. Los puntos resultantes son indistinguibles de puntos aleatorios, pero quien gasta conoce la «pintura» y puede demostrar: (1) que al quitarla se obtiene alguna hoja del árbol y (2) que conoce la clave de esa hoja.

Por qué rerandomizar

Una prueba de pertenencia demuestra la afirmación «el punto X es una hoja del árbol». Si publicamos la propia salida O, ya no queda nada que ocultar: todo el mundo ve qué salida se gasta. Si no publicamos nada, no hay nada a lo que vincular la key image ni el compromiso del importe. Necesitamos un término medio: publicar algo vinculado matemáticamente a la salida, de forma que solo quien gasta pueda ver ese vínculo.

Ese truco es la rerandomización. En RingCT, un truco parecido era la pseudo-salida C̃: el mismo compromiso del importe, pero con una máscara nueva. FCMP++ aplica la misma idea a cada parte de la salida.

De qué se compone una hoja

leaf = ( O.x, I.x, C.x ) coordenadas x de tres puntos de Ed25519: la clave de la salida O, el generador de la key image I = Hp(O) y el compromiso C

O y C salen directamente de la salida en la cadena; I la calcula el nodo al añadir la salida al árbol. En el árbol solo entran coordenadas (números), no los puntos en sí: así es más fácil «hashearlas» en el siguiente nivel (ver Curve Trees).

Las fórmulas de rerandomización

Quien gasta elige cuatro escalares aleatorios r_o, r_i, r_r_i, r_c y publica:

Se publicaFórmulaQué oculta
ÕO + r_o·Tqué clave de salida se gasta
ĨI + r_i·Uel generador de la key image de esa salida
Rr_i·V + r_r_i·Tun compromiso con r_i, necesario para vincular Ĩ con la key image
C̃C + r_c·Gqué compromiso de importe se gasta (como la pseudo-salida de RingCT)

T, U, V son generadores fijos obtenidos mediante hash a punto; nadie conoce sus logaritmos respecto a G ni entre sí. Eso es crucial: si alguien conociera T = t·G, podría «repintar» una componente como si fuera otra.

hoja del árbol (pública) O I = Hp(O) C + r_o·T + r_i·U + r_c·G entrada de la transacción Õ Ĩ (+ R) C̃ sin r, el vínculo entre la columna izquierda y la derecha es invisible

Qué se demuestra sobre estos puntos

La transacción lleva dos pruebas que se reparten el trabajo:

  1. La prueba de pertenencia (dentro de un circuito aritmético sobre Helios/Selene) demuestra: existe una hoja (O, I, C) en el árbol con raíz ρ, y existen r_o, r_i, r_r_i, r_c tales que los Õ, Ĩ, R, C̃ publicados cumplen las fórmulas de arriba.
  2. SA+L (fuera del circuito, sobre Ed25519) demuestra: quien gasta conoce x, y con Õ = x·G + (y + r_o)·T, y la key image es L = x·I, usando solo los Õ, Ĩ, R publicados.

Fíjate en que la prueba de pertenencia no sabe nada de las claves de gasto, y SA+L no sabe nada del árbol. Esta separación permite, por ejemplo, delegar la prueba de pertenencia en otro dispositivo sin darle derecho a gastar.

Por qué es seguro

  • Ocultación: r_o·T es un punto aleatorio del subgrupo, así que Õ está distribuido uniformemente, sea cual sea O. Comparar Õ con las salidas no sirve de nada; la herramienta lo muestra.
  • No hay hojas falsas: para «quitar la pintura» de un punto inventado y caer en una hoja real habría que resolver un logaritmo discreto entre generadores.
  • No se puede cambiar el importe: el balance se comprueba sobre C̃, y la prueba de pertenencia garantiza que C̃ solo difiere del C real de la hoja en un múltiplo de G, así que el importe es el mismo.
  • No hay doble gasto: L = x·I depende solo de la salida, no de r; un segundo gasto produce la misma L.