Batch-Validierung von Schnorr

Im aktuellen BIP über die Standardisierung von Schnorr stellt Pieter Wuille einen Algorithmus zur Batch-Validierung vor. Nach meinem Verständnis ist die Multiplikation mit einem Skalar die schwerste Operation: Um die Batch-Validierung sicher zu machen, müssen wir jede öffentliche Nonce mit einem zufälligen Faktor multiplizieren, sodass wir wieder auf zwei Multiplikationen pro Signatur (plus eins) zurückkommen. Ich verstehe nicht, warum es die Beschleunigung gibt, die in der Abbildung zu Beginn des BIP dargestellt wird. Könnte jemand helfen?

Danke im Voraus für eure Antworten!

Antworten (1)

Sie haben Recht, dass die Multiplikation der elliptischen Kurve tatsächlich die teuerste Operation im Validierungsalgorithmus ist. Und da sowohl die Einzelsignaturvalidierung als auch die Batchvalidierung zwei EC-Multiplikationen pro Signatur erfordern, scheint es, dass durch Batching keine Beschleunigung erzielt werden kann.

Es sind jedoch mehrere Algorithmen bekannt, um die Summe mehrerer EC-Multiplikationen schneller zu berechnen als die einzelnen Multiplikationen zu summieren. Der Algorithmus von Straus (auch als Shamir-Trick bekannt), der Algorithmus von Bos-Coster und der Algorithmus von Pippenger bieten alle Beschleunigungen und sind in verschiedenen Szenarien anwendbar. In der Grafik in unserem BIP-Entwurf werden Straus und Pippenger verwendet (abhängig von der Größe der Charge; Pippenger gewinnt nur für Chargen über ~100 Schlüssel). Für ausreichend große Chargen sind Bos-Coster und Pippenger O(log n) -mal schneller als einzelne Multiplikationen.

Um Ihnen eine Vorstellung davon zu geben, wie dies möglich ist, ist hier eine Zusammenfassung des Bos-Coster-Algorithmus (obwohl er in der Praxis nicht der schnellste ist, ist er am einfachsten zu erklären):

  • Beginnen Sie mit einer Liste von Paaren (a 1 , P 1 ), (a 2 , P 2 ), ..., (a n , P n ) .
  • Sortieren Sie diese Liste von groß nach klein a i (und nummerieren Sie sie neu, sodass eine 1 jetzt die größte Zahl ist, ...).
  • Während die Liste eine Länge größer als 1 hat:
    • Ersetzen Sie die beiden oberen Elemente (a 1 , P 1 ) und (a 2 , P 2 ) durch die beiden Elemente (a 1 – a 2 , P 1 ) , (a 2 , P 1 + P 2 ) . Beachten Sie, dass a 1 P 1 + a 2 P 2 = (a 1 – a 2 )P 1 + a 2 (P 1 + P 2 ) .
    • Wenn dies zu einem Element mit dem Koeffizienten 0 führt, entfernen Sie es (dies passiert, wenn a 1 = a 2 ).
    • Sortieren Sie die Liste erneut.
  • Wenn nur ein Element übrig bleibt, hat es die Form (a, P) , wobei a der ggT aller Eingaben ist. Für ein ausreichend großes n wird dieser ggT mit ziemlicher Sicherheit 1 sein , in diesem Fall ist die Lösung einfach P . Andernfalls ist a eine kleine Zahl, und die Lösung ist nur aP .

Die Intuition hier ist, dass, wenn Sie sagen wir 100 Multiplikationen durchführen müssen, eine 1 - eine 2 im Durchschnitt 100 Mal kleiner ist als die Zahl, die sie ersetzt ( eine 1 ), also teilen wir in jedem Schritt einen der Koeffizienten durch 100 , während nur eine einzige EC-Addition durchgeführt wird. Dies steht im Gegensatz zur naiven EC-Multiplikation, bei der Sie im Allgemeinen eine Addition für jedes Bit in der Eingabe durchführen müssen.

Es sollte erwähnt werden, dass der Endwert (a, P), a der ggT der Eingaben ist, weshalb er normalerweise 1 oder klein ist. Es ist auch so, dass Sie ein Sicherheitsargument für Randomizer-Werte anführen können, die viel kleiner als der volle Bereich sind – obwohl diese Tatsache nicht notwendig ist, um eine Beschleunigung zu erzielen, würde sie möglicherweise vom Verständnis ablenken.
Batch-Validierung von Schnorr
AntwortenHierDatenschutz-Bestimmungen1y, 0v