El lunes pasado publicamos un trabajo que presenta MuSig, un esquema multifirma basado en las firmas Schnorr. En este artículo, queremos explicar cómo fue construido y algunas de sus aplicaciones a Bitcoin.
MuSig es un esquema multifirma sencillo, cuyo carácter innovador consiste en que combina:
- recursos para la agregación de claves; y
- seguridad en el modelo de clave pública simple.
Existen dos versiones de MuSig, que varían según el número de rondas de comunicación. Las dos presentan seguridad comprobada, pero el MuSig de tres rondas solo depende del supuesto del logaritmo discreto (DL), del que también depende el algoritmo de firma digital de curva elíptica (ECDSA). En cambio, el MuSig de dos rondas depende del supuesto de un logaritmo discreto más uno (OMDL), que es ligeramente más fuerte.
Si bien este trabajo es producto de nuestra investigación de las firmas Schnorr para Bitcoin, MuSig es una construcción criptográfica que puede resultar útil para otras aplicaciones. Tanto el trabajo de investigación como este artículo se abocan principalmente a comentar las propiedades criptográficas de MuSig y no constituyen una propuesta directa para Bitcoin.
Un esquema multifirma es un algoritmo que combina firma y verificación, mediante el cual múltiples firmantes (cada uno con su propia clave pública/privada) firman juntos un solo mensaje y así generan una única firma. Acto seguido, dicha firma única puede ser verificada por cualquiera que conozca tanto el mensaje como las claves públicas de los firmantes. Cabe señalar que, en el contexto de Bitcoin, el término “multifirma” suele hacer referencia a una política de división de claves k-of-n, donde k puede no ser igual a n. En la bibliografía criptográfica, las multifirmas únicamente remiten a las políticas n-of-n, si bien es sencillo construir k-of-n sobre la base de n-of-n.
Vamos a emplear el término agregación de claves para referirnos a multifirmas que aparentan ser firmas individuales de una sola clave con relación a una clave pública combinada que existe únicamente en función de las claves públicas de los participantes. Esto implica que los verificadores ya no necesitan conocer las claves públicas de los participantes originales: en cambio, alcanza con otorgarles la clave combinada. En algunos usos, esto conlleva una optimización de la privacidad y el desempeño. En rigor, MuSig es un esquema de agregación de claves para firmas Schnorr.
Ya existen varios esquemas multifirma que efectivamente posibilitan la agregación de claves para las firmas Schnorr, pero acarrean ciertos condicionamientos, por ejemplo, la necesidad de verificar que los participantes realmente tengan la clave privada correspondiente a las claves públicas que afirman tener. La seguridad en el modelo de clave pública simple implica que desaparezcan dichos condicionamientos. Lo único que necesitamos de los participantes son sus claves públicas.
Aplicaciones de las multifirmas en Bitcoin
La aplicación más obvia de las multifirmas en el contexto de Bitcoin consiste en utilizarlas como alternativa más eficiente a los scripts multifirma n-of-n y a otras políticas que permiten una serie de combinaciones de claves (como k-of-n, el uso de árboles de claves, MAST y los esquemas “umbral” tradicionales). En estos casos, un esquema multifirma nativo implica que se genere una sola firma por cada entrada a la transacción. El esquema de agregación de claves también nos permite reducir el número de claves públicas por entrada a una sola, dado que los usuarios pueden enviar monedas al producto de la agregación de todas las claves involucradas, en lugar de incluirlas todas en el script. Así se logra disminuir la huella on-chain, acelerar la validación y optimizar la privacidad. Por ende, MuSig es una buena elección en este contexto.
No obstante, podemos avanzar todavía más. En lugar de limitarnos a una firma por entrada, podemos obtener una sola firma de la transacción entera. La agregación de claves no se puede utilizar en entradas múltiples, porque las claves públicas están atadas a las salidas, que se pueden gastar de manera independiente. En esta instancia se puede usar MuSig (si el verificador se encarga de la agregación de claves), pero el Bellare-Neven (BN), un reconocido esquema multifirma de clave pública simple no compatible con la agregación de firmas, funcionaría igual de bien. Cabe resaltar que es posible emplear multifirmas BN en casos donde las claves individuales son combinados MuSig.
Técnicamente, para combinar todas las firmas de las entradas a la transacción en una, lo que necesitamos no es un esquema multifirma, sino un esquema de agregación de firmas. En pocas palabras, la diferencia reside en que, en una firma combinada, cada firmante posee un mensaje propio, en lugar de compartir un mismo mensaje con todos los demás. Las firmas combinadas pueden clasificarse en interactivas o no interactivas: las firmas combinadas interactivas (IAS, por sus siglas en inglés) requieren la cooperación de los firmantes, mientras que los esquemas no interactivos permiten que cualquiera se encargue de la agregación. No se conocen esquemas de agregación no interactivos que dependan únicamente del supuesto de DL, pero construir los interactivos resulta trivial: se toma un esquema multifirma y se pide a todos los participantes que firmen la concatenación de todos los mensajes. Nuestro trabajo de investigación demuestra que dicha construcción no siempre es deseable y en cambio propone una variante IAS de BN con mejores propiedades.
Detalles
Notación:
● x, x1, x2,… son claves privadas y sus correspondientes claves públicas son X, X1, X2,… (Xi = xiG, donde G es el generador).
● El mensaje que se firma es m.
● H() es una función hash criptográfica.
Firmas Schnorr
A fin de refrescar conceptos, presentamos aquí las ecuaciones relevantes para las firmas Schnorr:
● Las firmas son (R,s) = (rG, r + H(X,R,m)x), donde r es un nonce aleatorio elegido por el firmante.
● La verificación requiere sG = R + H(X,R,m)X.
Multifirmas Schnorr naíf
Es posible realizar una generalización directa para respaldar las multifirmas:
● Llamar X a la suma de los puntos Xi.
● Cada firmante elige un nonce aleatorio ri, y comparte Ri = riG con los demás firmantes.
● Llamar R a la suma de los puntos Ri.
● Cada firmante computa si = ri + H(X,R,m)xi.
● La firma final es (R,s), donde s es la suma de los valores si.
● La verificación requiere sG = R + H(X,R,m)X, donde X es la suma de las claves públicas individuales.
Curiosamente, esto concuerda con la definición de esquema de agregación de claves expresada más arriba: múltiples partes pueden producir de manera conjunta una firma que constituye una firma de clave simple válida para la suma de todas las claves. Y si es tan simple, ¿por qué tanto alboroto?
El problema, claro, reside en que este esquema no es seguro. Considere el siguiente escenario. Alice y Bob quieren producir una multifirma de manera conjunta. Alice tiene un par de claves (xA,XA) y Bob tiene (xB,XB). No obstante, nada impide que Bob afirme que su clave pública es XB’ = XB - XA. Si efectivamente lo hace, los demás van a suponer que XA + XB’ es la clave combinada con la cual Alice y Bob van a firmar y por la cual deben cooperar. Por desgracia, esa suma equivale a XB, y claramente Bob puede ejecutar esa firma por sí solo. Esto se denomina ataque de clave maliciosa (rogue-key attack) y una manera de evitarlo consiste en exigir que, en primer lugar, Alice y Bob demuestren que realmente poseen las claves privadas correspondientes a sus supuestas claves públicas. No obstante, esta mitigación no siempre es posible e incluso cuando lo es resulta frágil en el mejor de los casos. Idealmente, deberíamos construir un esquema cuya seguridad no dependa de la verificación de las claves fuera de banda.
Bellare-Neven
Como se mencionó anteriormente, el esquema multifirma BN resulta seguro y no requiere tales supuestos. Así es como funciona:
● Llamar L = H(X1,X2,…).
● Cada firmante elige un nonce aleatorio ri, y comparte Ri = riG con los demás firmantes.
● Llamar R a la suma de los puntos Ri.
● Cada firmante computa si = ri + H(L,Xi,R,m)xi.
● La firma final es (R,s), donde s es la suma de los valores si.
● La verificación requiere sG = R + H(L,X1,R,m)X1 + H(L,X2,R,m)X2 + …
Técnicamente, BN conlleva una ronda de compromiso previo, donde los firmantes exponen H(Ri) ante los demás por primera vez, antes de revelar los puntos Ri en sí. Este paso es necesario para demostrar la seguridad de acuerdo con el supuesto de DL, pero podemos evitarlo si, en cambio, aceptamos el supuesto de OMDL. A la vez, este aspecto es lo que diferencia a los MuSig de dos y tres rondas.
Actualización del 19/02/2019: A la luz de este trabajo de investigación de Drijvers et al., nos percatamos de que el párrafo anterior es incorrecto. Saltearse la ronda de compromiso previo en MuSig resulta inseguro.
Por otro lado, cuando se desea obtener una IAS (donde cada firmante tiene su propio mensaje), el apéndice A de nuestro trabajo de investigación sugiere, en cambio, utilizar L = H((X1,m1),(X2,m2),…) y si = ri + H(L,R,i)xi para firmar (y un análogo para la verificación).
De cualquier modo, la firma resultante ya no cumple con la ecuación Schnorr normal, ni con ninguna otra ecuación que se pueda escribir como una función de una combinación de las claves públicas. En otras palabras, en el modelo de clave pública simple, sacrificamos la propiedad de agregación de claves a fin de garantizar la seguridad.
MuSig
Aquí es donde se aplica MuSig, que recupera la propiedad de agregación de claves sin perder la seguridad:
● Llamar L = H(X1,X2,…).
● Llamar X a la suma de todas las H(L,Xi)Xi.
● Cada firmante elige un nonce aleatorio ri, y comparte Ri = riG con los demás firmantes.
● Llamar R a la suma de los puntos Ri.
● Cada firmante computa si = ri + H(X,R,m)H(L,Xi)xi.
● La firma final es (R,s) donde s es la suma de los valores si.
● Una vez más, la verificación cumple con sG = R + H(X,R,m)X.
¡Eso es todo! Todo lo que tuvimos que hacer fue definir X no como una mera suma de las claves públicas individuales Xi, sino como la suma de los múltiplos de dichas claves, donde el factor de multiplicación depende de un hash de todas las claves participantes.
Agradecimientos
Le agradecemos mucho a Yannick Seurin por interesarse en revisar la seguridad de MuSig, escribir su prueba de seguridad e inventar el nombre.