Por José Felip Darás

Efectivamente, Bitcoin podría haber sido mejor desde un principio, pero una patente, pendiente de caducar, obligó a Satoshi a elegir otra metodología en la firma de transacciones: Elliptic Curve Digital Signature Algorithm (ECDSA).

El whitepaper de Bitcoin, publicado el 1 de noviembre de 2008, no se realiza en una tarde, ni en un mes, y más si su contenido tiene que definir, contemplar y asumir factores tan importantes como «el doble gasto, que el efectivo electrónico permita que los pagos en línea se envíen directamente de una parte a otra sin la carga de pasar por una institución financiera, con marcas de tiempo, en una cadena continua de hash supervisada por una prueba de trabajo (blockchain, PoW), anónimo y distribuido entre nodos no controlados». Puede que se empezara a escribir a principios de 2008 e incluso más atrás en el tiempo, por lo que, para crear una herramienta casi tan perfecta de transmisión de valor, que sería destinada a un uso mundial, no se podían cometer errores: había que tener en cuenta las patentes.

«El método para identificar suscriptores y para generar y verificar firmas electrónicas en un sistema de intercambio de datos», más conocido como el algoritmo de identificación de Schnorr, fue presentado a patente por el Prof. Dr. Claus Peter Schnorr en EE UU el 24 de febrero de 1989. La vigencia de las patentes en EE UU es de veinte años, pero a la patente se le otorgó en un derecho de aplicación el 29 de agosto de 1990 (EP0383985A1), por lo que «la prisa» por sacar el whitepaper y desarrollar la red Bitcoin descartó su implementación (aunque también podemos suponer que el whitepaper se hizo muy anteriormente a estas fechas y directamente se descartó).

¿Se puede implementar Schnorr ahora?

Sí. Es una tarea de programación complicada, en la que debería interferir el consenso de la red Bitcoin.

¿Para qué Schnorr si ya tenemos SegWit?

«SegWit no resuelve realmente el problema de escalabilidad de Bitcoin ni tampoco el spam sobre la mempool de los nodos».

Una firma Schnorr es un procedimiento criptográfico que permite sustituir un conjunto de firmas por una sola en la red de transacciones de Bitcoin, cuando todas provienen de un mismo input. Puede aumentar en un 25% la eficiencia de la red, y sus ventajas van más allá de reducir el espacio de bloque que emplea cada transacción.

Además, si se hace necesaria solo una firma por transacción, un spammer tendría que enviar muchas más transacciones y por tanto gastar más dinero para ocupar el espacio de transacción, evitando así la situación vivida durante mayo y finales del año 2017, donde supuestamente ciertos actores estaban ralentizando deliberadamente la red, producto de múltiples transacciones con «muchas fuentes», incrementando las tasas y provocando retrasos en el mempool de los nodos.

Las firmas Schnorr pueden eliminar el tamaño extra causado por las transacciones multifirma, ahorrando espacio y, por tanto, dinero. El efecto de la firma Schnorr también queda oculto, de modo que las transacciones multifirma se ven idénticas a las de una sola firma. Además, la verificación de las firmas Schnorr es ligeramente más rápida que la de ECDSA.

Ejemplo de un bloque lleno con muchas transacciones desde un mismo input:

https://blockchain.info/block/00000000000000000182aabc399d2daec86b50d510701a5fd098793a4eadead4

El algoritmo de Schnorr no se ha estandarizado desde su invención, probablemente debido a la patente original impuesta en él (que ya expiró). Si bien los contornos generales del sistema son matemáticamente correctos, la falta de documentación y especificaciones dificulta su implementación. Específicamente, su aplicación al diseño de pares de claves efímeras de Bitcoin implica consideraciones de seguridad que requieren mayor optimización.

Sobre las firmas de Schnorr existía el problema de «cancelación». La posibilidad de que un grupo de usuarios cree una firma válida para la suma de sus claves abre la puerta para que un participante adversario pueda restar la clave de otro usuario. Ya hay disponible una solución que implica multiplicar todas las claves utilizadas durante la configuración con un hash basado en sí mismo y todas las demás claves implicadas antes de la firma. Este proceso se llama «delinearización» (delinearization), sobre el cual se está trabajando actualmente.

A corto plazo, las firmas de Schnorr se consideran un reemplazo viable para dos funciones importantes del protocolo Bitcoin: OP_CHECKSIG y OP_CHECKMULTI- SIG.

El primero se usa actualmente para verificar firmas ECDSA contra su clave pública respectiva de acuerdo con el mensaje en una transacción. Al cambiar a un equivalente que verifica las firmas de Schnorr en lugar de ECDSA, el código de operación se puede usar para autorizar un gasto que requiere múltiples firmas y que normalmente requeriría llamar a OP_CHECK- MULTISIG. Utilizando una interacción a priori no observable por la red, la colección de firmantes calcula una clave pública combinada junto con una firma común que se verifica mediante el nuevo OP_CHECKSIG con los beneficios de una mayor privacidad y costos reducidos. Este último implica escenarios de umbral donde solo se necesitan firmas de n-m para autorizar una transacción.

La implementación actual de OP_CHECKMULTISIG valida todas las claves públicas y firmas asociadas requeridas por la política de umbral. Debido a que el cálculo se escala linealmente con el número de participantes, Schnorr propone un esquema mucho más eficiente que reemplaza la lista de firmas por una combinación única junto con un subconjunto de las pubkeys requeridas.

Hasta que se realice una mayor evaluación del esquema de delineación que asegura a los firmantes de actores malintencionados, las aplicaciones adicionales de las firmas de Schnorr pueden ser prematuras, pero la implementación de las características anteriores puede allanar el camino para una mejor comprensión del esquema en producción.

Agregación de firmas

Las propiedades de Schnorr que permiten la combinación de múltiples firmas en una sola entrada también son aplicables a la agregación de múltiples entradas para todas las transacciones. El desarrollador de Bitcoin, Gregory Maxwell, fue el primero en introducir la idea utilizando ideas de una propuesta anterior basada en firmas BLS, CoinJoin, que permite a diferentes usuarios combinar todas sus transacciones en una sola transacción. Esa transacción incluirá múltiples entradas provenientes de diferentes pagadores, que envían dinero a múltiples salidas, pertenecientes a diferentes beneficiarios (aumentando así la privacidad).

Diferencias fundamentales

Para entender correctamente la diferencia entre esta aplicación y las descritas anteriormente, es necesario considerar cómo se agregan las firmas en cada caso respectivo. En la configuración multigrado nativa, los firmantes colaboran entre ellos para calcular una clave pública común y su firma asociada. Esta interacción ocurre fuera del protocolo y solo concierne a las partes involucradas. La idea detrás de la agregación de firmas es habilitar validadores del sistema, es decir, nodos de Bitcoin para calcular una sola clave y firma para cada entrada de todas las transacciones en el nivel de protocolo.

Debido a que este esquema amplía el alcance de la agregación fuera del conjunto determinista de participantes, introduce un nuevo vector de ataque para que los actores malintencionados aprovechen el error de «cancelación». Por esta razón, la corrección de delineación resaltada en la sección anterior es crítica para la solidez de este método.

En términos de implementación, la propuesta es bastante sencilla: OP_CHECKSIG y OP_CHECKMULTISIG se modifican para que puedan apilar claves públicas, delinearlas y, una vez validadas todas las entradas asociadas, producir una firma combinada para sus respectivas transacciones.

Es bastante sencillo evaluar el tipo de ahorro de recursos que habría sido posible si se hubiera implementado la agregación de firmas desde el bloque génesis. Suponiendo que cada firma histórica se redujera a 1 byte, excepto una por transacción, el análisis sugiere que el método daría como resultado una reducción de al menos 25% en términos de almacenamiento y ancho de banda. El aumento en el uso de umbrales n-n-n es probable que se traduzca en más ahorros.

Otras soluciones

Blockstream, por ejemplo, ha publicado este año su «Key Aggregation for Schnorr Signatures», MuSig: hay dos versiones de MuSig, que varían según el número de rondas de comunicación. Ambas son probablemente seguras, pero MuSig de tres rondas solo se basa en el supuesto del Logaritmo Discreto (DL), del que ECDSA también depende. En cambio, MuSig de dos rondas se basa en el supuesto de un Logaritmo Discreto Más Uno (OMDL) un poco más fuerte.

Cramer–Shoup, cryptosystem, DH, DSA, ECDH, EdDSA, EKE, ElGamal, signature scheme, MQV, SPEKE, SRP, STS, AE, CEILIDH, EPOC, HFE, IES, Lamport, McEliece, Merkle–Hellman, Naccache–Stern, Naccache–Stern, knapsack, NTRUEncrypt, NTRUSign, Three-pass o protocol XTR son algunas soluciones criptográficas conocidas, algunas ya en desuso por no cumplir con su funcionalidad en este campo, otras por haber sido «rotas» (cracked) o simplemente «patentadas», estarán ahí para su estudio, combinación o modificación, esperando algún día poder recibir el honor de implementarse en el código principal de Bitcoin.

 

Technology roadmap – Schnorr signatures and signature aggregation: https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/

Schnorr-SHA256 module: https://github.com/sipa/secp256k1/blob/968e2f415a5e764d159ee03e95815ea11460854e/src/modules/schnorr/schnorr.md

Elliptic Curve Digital Signature Algorithm: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Schnorr signature: https://en.wikipedia.org/wiki/Schnorr_signature

Patente US4995082A, «Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system»: https://patents.google.com/patent/US4995082

Mempool Transaction Count: https://blockchain.info/en/charts/mempool-count?timespan=all

MuSig, a multi-signature scheme based on Schnorr signatures: https://eprint.iacr.org/2018/068