Validación por lotes de Schnorr

En el reciente BIP sobre la estandarización de Schnorr, Pieter Wuille presenta un algoritmo para la validación por lotes. Según tengo entendido, la operación más pesada es la multiplicación por un escalar: para que la validación por lotes sea segura, necesitamos multiplicar cada nonce público por un factor aleatorio, por lo que volvemos a dos multiplicaciones por firma (más uno). No entiendo por qué existe la aceleración presentada en la figura al comienzo del BIP. ¿Alguien podría ayudar?

¡Gracias de antemano por sus respuestas!

Respuestas (1)

Tiene razón en que la multiplicación de la curva elíptica es de hecho la operación más costosa en el algoritmo de validación. Y como tanto la validación de una sola firma como la validación por lotes requieren dos multiplicaciones de EC por firma, parecería que no se puede obtener una aceleración del procesamiento por lotes.

Sin embargo, se conocen varios algoritmos para calcular la suma de múltiples multiplicaciones EC más rápido que sumar las multiplicaciones individuales. El algoritmo de Straus (también conocido como el truco de Shamir), el algoritmo de Bos-Coster y el algoritmo de Pippenger proporcionan aceleraciones y son aplicables en diferentes escenarios. En el gráfico de nuestro borrador BIP, se utilizan Straus y Pippenger (dependiendo del tamaño del lote; Pippenger solo gana para lotes de más de ~ 100 llaves). Para lotes suficientemente grandes, Bos-Coster y Pippenger son O(log n) veces más rápido que las multiplicaciones individuales.

Para darle una idea de cómo es esto posible, aquí hay un resumen del algoritmo de Bos-Coster (aunque en la práctica no es el más rápido, es el más fácil de explicar):

  • Comience con una lista de pares (a 1 , P 1 ), (a 2 , P 2 ), ..., (a n , P n ) .
  • Ordene esta lista de mayor a menor a i (y vuelva a numerarla para que 1 sea ahora el número más grande, ...).
  • Mientras que la lista tiene una longitud mayor que 1:
    • Reemplace los dos elementos superiores (a 1 , P 1 ) y (a 2 , P 2 ) con los dos elementos (a 1 - a 2 , P 1 ) , (a 2 , P 1 + P 2 ) . Tenga en cuenta que a 1 P 1 + a 2 P 2 = (a 1 - a 2 )P 1 + a 2 (P 1 + P 2 ) .
    • Si esto da como resultado un elemento con coeficiente 0, elimínelo (esto sucede cuando a 1 = a 2 ).
    • Ordena la lista de nuevo.
  • Cuando solo quede un elemento, será de la forma (a, P) , donde a es el MCD de todas las entradas. Para un n lo suficientemente grande , ese GCD será casi con seguridad 1 , en cuyo caso la solución es simplemente P. De lo contrario , a será un número pequeño y la solución es simplemente aP .

La intuición aquí es que cuando tiene que realizar, digamos, 100 multiplicaciones, un 1 - un 2 será en promedio 100 veces más pequeño que el número que reemplaza ( un 1 ), por lo que en cada paso estamos dividiendo uno de los coeficientes por 100 , mientras que solo hace una sola adición de EC. Esto contrasta con la multiplicación EC ingenua en la que generalmente necesita realizar una suma para cada bit en la entrada.

Vale la pena mencionar que el valor final (a, P), a es el GCD de las entradas, por lo que suele ser 1 o pequeño. También es el caso de que puede presentar un argumento a favor de la seguridad de los valores del aleatorizador que son mucho más pequeños que el rango completo, aunque este hecho no es necesario para que haya una aceleración, por lo que tal vez distraiga la comprensión.
Validación por lotes de Schnorr
RespuestasAquíPolítica de privacidad1y, 0v