Dispositivos señuelo (honeypots)
Combinación con firmas Schnorr
Introducción
Cuando comenzamos a determinar qué mejoras del consenso íbamos a incorporar a nuestra sidechain Alpha, teníamos una lista de ideas relativamente larga. Sin embargo, hubo una serie de elementos que quedaron descartados debido a presiones en cuanto a los plazos o por otros motivos.
Uno de los cambios que sí se incluyó fue la incorporación de algunos opcódigos[1] simples que solían formar parte de Bitcoin. Uno de ellos es OP_CAT, que concatena dos variables de la pila.
Uno de los que no se incluyó fue el uso de árboles de sintaxis abstracta de Merkle (MAST, por sus siglas en inglés) en el scripting. Esta idea viene circulando desde hace varios años, pero nunca se implementó en Bitcoin. Su premisa básica consiste en disponer las condiciones del script en forma de árbol y revelar únicamente la parte que ejecutan los usuarios al efectuar gastos. Si bien habilitaría numerosos scripts complejos a gran escala, exige rediseñar en profundidad el lenguaje de script. Estuvimos pensando en esto durante un tiempo, pero no va a estar listo pronto.
No obstante, poco después del lanzamiento de Alpha nos dimos cuenta de que su lenguaje de script, gracias a la incorporación de OP_CAT, posibilita una forma sencilla de verificación con árboles de Merkle. Por ende, ahora podemos emular un subconjunto de MAST sin alterar en absoluto las reglas de consenso. Todo lo que tenemos que hacer es emplear el lenguaje de script de una manera que no habíamos anticipado. Como verá en las próximas secciones, esto posibilita algunas construcciones multifirma[2] muy grandes a muy bajo costo (en términos de los opcódigos ejecutados y el tamaño on-chain).
El resto del artículo está dedicado a los detalles técnicos, los usos posibles y algunas ideas sobre implementaciones. Puede saltearse la parte técnica si no es lo suyo.
Detalles técnicos
Imagine que desea crear una multifirma 1-de-11 (con 11 claves públicas conocidas). Primero va a computar los hashes SHA256 de las claves públicas en cuestión y los insertará en un árbol de Merkle. En el siguiente gráfico, todos los nombres de los símbolos, excepto el 1, representan hashes de 32 bytes. Utilizamos el 1 como constante simple en lugar de una rama hacia la derecha donde no hay ninguna.
R
/ \
/ \
/ \
Z1 Z2
/ \ / \
Y1 Y2 Y3 1
/ \ / \ / \
X1 X2 X3 X4 X5 X6
/ \ / \ / \ / \ / \ / \
K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 1
Si utilizamos el script en nuestra sidechain Alpha, podemos construir un script que tome como entrada una clave pública, una firma y un trayecto Merkle. En la etapa de verificación, el script utilizaría el trayecto Merkle para probar que la clave pública pertenece a un árbol cuya raíz es R y que la firma se corresponde con dicha clave pública.
8 PICK SHA256 (SWAP IF SWAP ENDIF CAT SHA256)*4 <R> EQUALVERIFY CHECKSIG
Cabe señalar que las 6 operaciones internas se repiten 4 veces, una por cada nivel del árbol.
Para ver por qué funciona así, siga los pasos de ejecución con la siguiente entrada, que representa una firma que emplea la décima clave (cuyo hash es K10). Las últimas 8 filas constituyen el trayecto Merkle. Para cada uno de los niveles, de abajo hacia arriba, contienen la entrada con la que se combina el hash que se viene ejecutando, sumada a un 0 o un 1 que indica si se trata de un nodo a la izquierda o a la derecha, respectivamente.
Ampliación de la escala
En la sección anterior, se proporciona un ejemplo que muestra cómo implementar una multifirma 1-de-11 en el script de Alpha. Ahora bien, el script de Bitcoin ya es perfectamente capaz de ejecutar la multifirma 1-de-11.
La ventaja de este otro enfoque es que es posible incrementar su escala de manera logarítmica. Duplicar la cantidad de claves públicas válidas solo añade 40 bytes a las transacciones en cuestión y tanto esta cifra como la cantidad de (costosas) validaciones de firmas se mantienen constantes. Comparémoslo con Bitcoin, donde añadir una sola clave pública implica sumar 34 bytes.
Debido a las limitaciones del script en cuanto al cómputo de operaciones, este enfoque en teoría funciona hasta una multifirma 1-de-4 294 967 296, si bien llegados a este punto, la construcción del árbol se vuelve demasiado engorrosa debido a su enormidad. Aun así, una construcción 1-de-1 000 000 tendría que ser factible.
Para construir 1-de-250 000 mediante este enfoque hacen falta 886 bytes del script de Alpha. Dicha cifra es más de 9000 veces menor de lo que sería su equivalente, si fuera posible, en el script de Bitcoin.
Dispositivos señuelo
Un uso posible de estas grandes construcciones multifirma son los dispositivos señuelo (honeypots). Supongamos que usted opera un consorcio de 10 000 servidores y quiere depositar en cada uno una pequeña cantidad de BTC, con el objetivo de tentar a cualquier posible atacante a robarse las monedas y así enterarse de su irrupción.
Si usted no puede permitirse perder más de 10 BTC para dicho fin y además necesita colocar una cartera Bitcoin autónoma en cada servidor, solo podrá dejar 1 mBTC en cada máquina, lo cual no constituye un monto particularmente atractivo.
En cambio, con una multifirma de 10 000 bytes de extensión, podría asignar los 10 BTC a un script multifirma de semejante tamaño y, al mismo tiempo, dejar una sola clave en cada máquina. Como todas las claves siguen estando separadas y la firma revela cuál fue utilizada, usted podrá detectar qué máquina fue vulnerada.
Combinación con firmas Schnorr
Existen otros usos posibles de las grandes construcciones multifirma, pero el enfoque que se describió hasta ahora solo es compatible con 1-of-n, no con m-of-n.
No obstante, es posible combinar este enfoque con una interesante propiedad de las firmas Schnorr[3] a fin de obtener algo más poderoso. Si usted cuenta con un conjunto de firmas para el mismo mensaje (transacción), es posible “sumar” las firmas en pos de obtener una firma correspondiente a la “suma” de sus claves públicas.
Esto quiere decir que, en lugar de emplear un scipt multifirma 3-de-3, podemos utilizar la suma de las 3 claves públicas involucradas como la clave pública “1-de-1” en una CHECKSIG normal. A continuación, todos los firmantes pueden firmar por su cuenta una transacción de gasto de fondos y luego sumar sus firmas a fin de generar una firma que resulte válida para la suma de las claves públicas. En otras palabras: mediante el uso de las firmas Schnorr, las multifirmas m-of-m donde M es un valor arbitrariamente alto quedan reducidas a un 1-de-1 sencillo, por lo menos en lo que respecta a la blockchain. La desventaja es que hacen falta dos rondas porque primero los participantes deben ponerse de acuerdo en un nonce de firma.
Quizás a esta altura ya entienda cómo se combinan. Los árboles de Merkle son compatibles con 1-of-n muy grandes. Las firmas Schnorr son compatibles con m-of-m muy grandes. Esto implica que si podemos escribir nuestras condiciones de gasto como 1-of-(n posible m-of-m), podemos construir un árbol de Merkle que consista en claves públicas combinadas por Schnorr. Así, cada hoja del árbol de Merkle se transforma en un conjunto de claves que todos deben firmar.
Por ejemplo: una multifirma 4-de-5 con las claves A, B, C, D, E se puede escribir como:
Esto se transforma en un árbol de Merkle de 5 hojas, cada una de las cuales consiste en la suma de 4 claves públicas. En Alpha, esto requeriría 286 bytes de script. En Bitcoin, una multifirma 4-de-5 precisa 490 bytes.
Y no olvidemos que, además, siempre exige una sola (costosa) operación CHECKSIG. En el script de Bitcoin, siempre hace falta una CHECKSIG por firmante requerido (m para una multifirma m-of-n).
Algunos ejemplos más:
Árboles con umbral generalizados
El enfoque que consiste en crear árboles de Merkle cuyas hojas representan combinaciones de claves ni siquiera se limita a condiciones m-of-n. Para cualquier elemento que se pueda expresar como un número relativamente pequeño de combinaciones de conjuntos de claves que todos tienen que firmar, este enfoque es óptimo.
Nosotros diseñamos un lenguaje sencillo que describe dichas condiciones para las combinaciones de claves. Una descripción puede ser:
Una clave pública en formato hexadecimal que requiere una firma con esa misma clave.
O (a, b, c,...) donde a, b, c... son otras descripciones, de las cuales deba cumplirse una.
Y (a, b, c,...) donde a, b, c… son otras descripciones, de las cuales deban cumplirse todas.
UMBRAL (n, a, b, c,...) donde n es un número y a, b, c… son otras descripciones, de las cuales se deben cumplir n.
Con este lenguaje, resulta sencillo expresar condiciones como “O bien firman A y B, o firman 2 de los firmantes C, D y E.”
Propiedades
Greg Maxwell elaboró una lista de cinco propiedades interesantes de los esquemas de firma en este contexto (resumidas en el acrónimo “ACEUP” por sus iniciales en inglés). [4]
Responsabilidad: Tanto OP_CHECKMULTISIG como estas firmas tipo árbol permiten que todos los participantes del esquema sepan quién firmó.
Componibilidad: Si hay dos participantes y ambos exigen firmar mediante una descripción compleja, ¿es posible construir una descripción que describa este tipo de firma y aun así contar con software que sepa cómo procesarla? Las firmas tipo árbol son muy buenas para esto.
Eficiencia: El tamaño de las transacciones y el desempeño de validación de las firmas tipo árbol siempre son iguales o mejores que los de OP_CHECKMULTISIG. No obstante, esto conlleva un tiempo de firma mayor.
Facilidad de uso: Las firmas tipo árbol precisan 2 rondas para todos los participantes porque, en primer lugar, necesitan un nonce de firma Schnorr.
Privacidad: La identidad y cantidad de los participantes de una firma tipo árbol son mucho más fáciles de ocultar, dado que el costo de agregar variables simuladas es muy bajo.
Implementación
Consulte https://github.com/ElementsProject/elements/pull/48 para ver un parche que incorpora compatibilidad con firmas tipo árbol a la billetera de Alpha. Las nuevas RPC addtreesigaddress y createtreesig generan direcciones de P2SH para scripts que implementen árboles de claves públicas, y signrawtransaction precisa un argumento extra para ingresar en el árbol de claves públicas (que se debe conocer al momento de firmar).
Conclusión
Es interesante ver cómo habilitar ventajas inesperadas con unos pocos cambios al lenguaje de scripting. Al fusionar árboles de Merkle de claves públicas con firmas Schnorr combinadas, posibilitamos algunas combinaciones de multifirmas m-of-n muy grandes de manera eficiente. Como parte de nuestro trabajo con el paquete Elements para sidechains, esto pronto estará disponible en el código base de Alpha, y en posibles sucesores vamos a mejorar la compatibilidad con esta característica.
[1] Véase https://github.com/ElementsProject/elementsproject.github.io#new-opcodes
[2] Una transacción que bloquea las monedas, de tal modo que exige múltiples firmas de múltiples firmantes. Una construcción multifirma m-of-n exige un mínimo de firmas, m, de una cantidad n de firmantes diferentes cuyas claves públicas se conocen.
[3] Véase el elemento “Validación de firmas Schnorr” en http://elementsproject.org/