Cuando las firmas de Schnorr sean parte de Bitcoin, ¿será posible validar cada bloque con una sola validación de firma?

En una charla reciente, Pieter Wuille habló sobre acelerar la verificación cuando se utilizan firmas Schnorr y varios algoritmos para verificar múltiples firmas.

¿Sería realmente posible verificar un solo bloque agregando las claves y firmas de todas las transacciones? (En teoría, incluso más transacciones en varios bloques)

Supongo que esto implica que el antiguo esquema ECDSA ya no se usaría. Si fuéramos compatibles con versiones anteriores, probablemente solo podríamos hacer esto para transacciones que usaran firmas Schorr, mientras que las otras tendrían que verificarse una por una.

(Dejando de lado la política de cambios drásticos de protocolo) ¿No podríamos incluso ahorrar más espacio si adoptamos el encabezado del bloque para incluir una firma Schnorre agregada para el bloque y dejar de lado todas las firmas Schnorr de las transacciones individuales dentro de ese bloque?

¿Yo me perdí algo? La charla no dio muchos detalles pero solo mencionó la idea.

Respuestas (1)

Sí, una validación por bloque, pero no una firma por bloque.

Para aclarar la confusión, hay 3 tecnologías distintas involucradas aquí:

  • (1) la agregación no interactiva es la capacidad de un tercero (que no posee ninguna clave privada) de combinar varias firmas, cada una con su propio mensaje y clave pública, en una sola firma que puede verificar alguien que sabe todo mensajes y claves públicas.
  • (2) la agregación interactiva es lo mismo, pero cuando los firmantes deben ser conscientes de la agregación y comunicarse entre sí para producir conjuntamente una sola firma.
  • (3) la validación por lotes es la capacidad de un verificador para verificar si varias tuplas (clave pública, mensaje, firma) son válidas o no, más rápido que verificar las firmas individuales. Si una o más de las tuplas no son válidas, el verificador no sabrá cuáles, en este caso.

Las firmas de Schnorr (y cualquier otro esquema de firma conocido basado en logaritmos discretos) admiten (2) y (3), pero no (1).

La falta de (1) significa que no puede haber una sola firma para un bloque completo (*), ya que el minero que construye el bloque es un tercero que no participa en la creación de la firma.

Debido a (2), lo mejor que podemos esperar (siempre que estemos restringidos a firmas basadas en DL) es una firma por transacción. Incluso eso requiere la agregación de entradas cruzadas, que tiene complejidades más allá de la implementación de las firmas Schnorr en cadena (consulte esta publicación , por ejemplo).

Sin embargo, debido a (3) es correcto que puede haber una sola validación por bloque, pero no una sola firma por bloque. De hecho, la aceleración que es posible a través de la validación por lotes se vuelve no trivial. Cada una de las 4 líneas es una técnica de optimización que se implementa actualmente en libsecp256k1, que elegirá la mejor según el tamaño del problema y las limitaciones de memoria.

Aceleración de la validación de lotes

(*) Existe una forma de "media agregación" no interactiva para firmas basadas en DL, donde N firmas se pueden combinar de forma no interactiva en una única firma de tamaño (1+N)/2 firmas originales. Esto podría usarse para bloques, aunque las ganancias no son tan grandes y existen complejidades en torno a la agregación de todo el bloque que lo hacen menos interesante.

Supongo que tengo que leer los detalles nuevamente, pero ¿no era la idea del modelo de clave pública simple y la construcción de musig exactamente que la agregación no interactiva sería posible? ¿O debería haber pedido firmas de música? Pensé que musig es el esquema exacto que actualmente se usa cuando la gente habla de schnorr. No marque como correcto todavía ya que todavía tengo preguntas abiertas (que probablemente sean mi culpa)
MuSig permite una configuración no interactiva : la firma sigue siendo interactiva.
Y MuSig es solo una de las cosas que la billetera puede elegir usar cuando existe la validación de Schnorr en cadena (porque las firmas que salen de la firma de MuSig son compatibles con un verificador de Schnorr). Hay construcciones (configuración interactiva) que le permiten construir k-of-n con una sola tecla, por ejemplo, o incluso combinaciones arbitrarias y/o de participantes.
"Existe una forma de "media agregación" no interactiva para firmas basadas en DL, donde N firmas se pueden combinar de forma no interactiva en una única firma de tamaño (1+N)/2 firmas originales". -- ¿No se podría iterar esto para las iteraciones O(log(N))?
@Martin Schwarz ¿Qué quieres decir con iterado? La construcción (para Schnorr) es que combinas (R1,s1), ..., (Rn,sn) en (R1,...,Rn,s) donde s = H(L,1)*s1 + . .. + H(L,n)*sn y L = H(R1,...Rn,P1,...,Pn,m1,...,mn), y Pi son las claves públicas y mi son los mensajes .
Ah, claro. Está bien, eso no funciona.
Acabo de ver esto hoy: muy buena figura, ¿por qué no incluirla en el bip-schnorr?
Cuando las firmas de Schnorr sean parte de Bitcoin, ¿será posible validar cada bloque con una sola validación de firma?
RespuestasAquíPolítica de privacidad1y, 0v