Schlüssel-Aggregation für Schnorr-Signaturen
Blockstream Research

Schlüssel-Aggregation für Schnorr-Signaturen

Pieter Wuille

Am vergangenen Montag haben wir einen Aufsatz veröffentlicht, in dem MuSig, ein Multisignatur-Konzept aufgrund von Schnorr-Signaturen vorgestellt wird. In diesem Beitrag gehen wir auf seinen Aufbau und einige Anwendungen für Bitcoin ein.

MuSig ist ein einfaches Multisignatur-Konzept, das neuartig ist insofern als es zwei Aspekte kombiniert:

  1. Unterstützung für die Schlüssel-Aggregation
  2. Sicherheit im Plain Public-Key-Modell

Es gibt zwei Versionen von MuSig, die je nach der Anzahl der Kommunikationsrunden variieren. Beide sind nachweisbar sicher, aber Dreirunden-MuSig baut nur auf der Diskreten Logarithmus-Annahme, auf die auch ECDSA aufbaut. Zweirunden-MuSig beruht dagegen auf der geringfügig stärkeren One More Discrete Logarithm (OMDL)-Annahme.

Diese Arbeit ist das Ergebnis unserer Forschung im Bereich der Schnorr-Signaturen für Bitcoin, aber MuSig ist ein kryptographisches Konzept, das für andere Anwendungen nützlich sein kann. Der Aufsatz und dieser Blog-Beitrag gehen primär auf die kryptographischen Eigenschaften von MuSig ein und sind kein direkter Vorschlag für Bitcoin.

Ein Multisignatur-Schema ist eine Kombination aus einem Unterzeichnungs- und Verifizierungsalgorithmus, wobei mehrere Unterzeichner (jeder mit einem eigenen privaten/öffentlichen Schlüssel) gemeinsam eine einzelne Nachricht unterzeichnen, was eine einzelne Signatur erzeugt. Diese einzelne Signatur kann daraufhin von jeder beliebigen Person verifiziert werden, die auch die Nachricht und die öffentlichen Schlüssel der Unterzeichner kennt. Hinweis: Im Zusammenhang mit Bitcoin bezieht sich der Begriff „Multisig“ gewöhnlich auf eine k-of-n Policy, wobei k sich von n unterscheiden kann. In der Kryptographie-Literatur beziehen sich Multisignaturen eigentlich nur auf n-of-n Policies, obwohl wir einfach k-of-n über n-of-n konstruieren können.

Wir verwenden den Begriff Schlüssel-Aggregation für Multisignaturen, die wie eine Single-Key-Signatur aussehen, aber in Bezug auf einen aggregierten öffentlichen Schlüssel, der eine Funktion der öffentlichen Schlüssel der Teilnehmer ist. Dies bedeutet, dass Verifizierer die ursprünglichen öffentlichen Schlüssel der Teilnehmer gar nicht kennen müssen –

man kann ihnen stattdessen den aggregierten Schlüssel geben. In einigen Anwendungsfällen führt dies zu besserem Datenschutz und besserer Leistung. MuSig ist effektiv ein Schlüssel-Aggregations-Schema für Schnorr-Signaturen.

Es gibt bereits mehrere Multisignatur-Konzepte, die effektiv eine Schlüssel-Aggregation für Schnorr-Signaturen darstellen, aber es besteht die Einschränkung, dass verifiziert werden muss, dass die Teilnehmer auch wirklich über den privaten Schlüssel verfügen, der mit den öffentlichen Schlüsseln übereinstimmt, die sie angeblich haben. Sicherheit im Plain Public-Key-Modell bedeutet, dass es keine solche Einschränkung gibt. Wir brauchen von den Teilnehmern lediglich ihre öffentlichen Schlüssel.

Anwendungen für Multisignaturen in Bitcoin

Der offensichtlichste Anwendungsfall für Multisignaturen im Zusammenhang mit Bitcoin ist als wirksamer Ersatz für n-of-n Multisig-Scripts und andere Policies, die eine Reihe möglicher Schlüsselkombinationen erlauben (einschließlich k-of-n, mithilfe von Schlüsselbäumen, MAST oder traditionellen Schwellenschemata). Hierfür bedeutet ein natives Multisignatur-Schema, dass wir letztlich eine Signatur pro Transaktionseingabe haben. Ein Schlüssel-Aggregationsschema ermöglicht es zudem, die Anzahl der öffentlichen Schlüssel pro Eingabe auf einen zu reduzieren, da ein Nutzer Coins an das Aggregat aller beteiligten Schlüssel senden kann, anstatt sie alle in das Script einzubeziehen. Dies resultiert in einer kürzeren Kette, schnellerer Validierung und besserem Datenschutz. Infolgedessen ist MuSig hier eine gute Wahl.

Wir können allerdings noch weiter gehen. Statt uns auf eine Signatur pro Eingabe zu beschränken, können wir effektiv eine Signatur für die gesamte Transaktion nutzen. Die Schlüssel-Aggregation kann nicht für mehrere Eingaben benutzt werden, da die öffentlichen Schlüssel an die Ausgaben gebunden sind und diese unabhängig ausgegeben werden können. MuSig kann hier eingesetzt werden (wobei die Schlüssel-Aggregation vom Verifizierer ausgeführt wird), aber Bellare-Neven(BN), ein bekannteres Multisignatur-Schema nach dem Plain Public-Key-Modell, das die Schlüssel-Aggregation nicht unterstützt, würde genauso gut funktionieren. Interessanterweise ist es möglich, BN Multisignaturen zu verwenden, wobei die einzelnen Schlüssel MuSig-Aggregate sind.

Um die Signaturen aller Transaktionseingaben in eine zu kombinieren, brauchen wir technisch gesehen kein Multisignatur-Schema, sondern ein Aggregat-Signaturschema. Der Unterschied liegt einfach darin, dass jeder Unterzeichner bei einer Aggregat-Signatur seine eigene Nachricht hat, nicht eine allen gemeinsame Nachricht. Aggregat-Signaturen können als interaktiv oder nicht-interaktiv klassifiziert werden: interaktive Aggregat-Signaturen (IAS) erfordern die Zusammenarbeit der Unterzeichner, während nicht-interaktive Schemata es ermöglichen, dass eine beliebige Person die Aggregation vornehmen kann. Es sind keine nicht-interaktiven Aggregationsschemata bekannt, die nur auf der DL-Annahme beruhen, aber interaktive sind einfach zu konstruieren: Man nimmt ein Multisignatur-Schema und sorgt dafür, dass jeder Teilnehmer die Verkettung aller Nachrichten unterzeichnet. Unser Aufsatz zeigt, dass dies nicht immer eine wünschenswerte Konstruktion ist, und bietet stattdessen eine IAS-Variante von BN mit besseren Eigenschaften an.

Details

Notation:

  • x, x1, x2, … sind private Schlüssel mit den entsprechenden öffentlichen Schlüsseln X, X1, X2, … (Xi = xiG, wobei G der Generator ist)
  • Die zu unterzeichnende Nachricht ist m
  • H() ist eine kryptographische Hash-Funktion

Schnorr-Signaturen

Zur Erinnerung: Dies sind die für Schnorr-Signaturen relevanten Gleichungen:

  • Signaturen sind (R,s) = (rG, r + H(X,R,m)x) wobei r eine vom Unterzeichner beliebig gewählte Nonce ist
  • Die Verifizierung erfordert sG = R + H(X,R,m)X

Naive Schnorr-Multisignaturen

Zur Unterstützung von Multisignaturen ist eine einfache Generalisierung möglich:

  • X sei die Summe der Xi Punkte
  • Jeder Unterzeichner wählt beliebig eine Nonce ri aus und teilt Ri = riG mit den anderen Unterzeichnern
  • R sei die Summe der Ri Punkte
  • Jeder Unterzeichner berechnet si = ri + H(X,R,m)xi
  • Die endgültige Signatur ist (R,s), wobei s die Summe der si Werte ist
  • Die Verifizierung erfordert sG = R + H(X,R,m)X, wobei X die Summe der einzelnen öffentlichen Schlüssel ist

Interessanterweise entspricht dies der obigen Definition für ein Schlüssel-Aggregationsschema: Mehrere Parteien können gemeinsam eine Signatur erzeugen, die eine gültige Einzelschlüsselsignatur für die Summe der Schlüssel ist. Wenn es so einfach ist, warum all die Aufregung?

Das Problem besteht selbstverständlich darin, dass dieses Schema nicht sicher ist. Man betrachte folgendes Szenario. Alice und Bob wollen zusammen eine Multisignatur erzeugen. Alice hat ein Schlüsselpaar (xA,XA) und Bob hat (xB,XB). Nichts hindert jedoch Bob daran zu behaupten, sein öffentlicher Schlüssel sei XB’ = XB - XA. Wenn er das tut, nehmen andere an, dass XA + XB’ der aggregierte Schlüssel sei, den Alice und Bob brauchen, um zusammen zu unterzeichnen. Leider ist diese Summe gleich XB und Bob kann offensichtlich alleine unterzeichnen. Dies nennt man einen Rogue-Key-Angriff. Eine Möglichkeit zur Vermeidung eines solchen Angriffs besteht darin, von Alice und Bob zu verlangen, dass sie erst beweisen, dass sie auch wirklich über die privaten Schlüssel verfügen, die ihren beanspruchten öffentlichen Schlüsseln entsprechen. Diese Maßnahme ist jedoch nicht immer möglich und selbst wenn sie möglich ist, gilt sie bestenfalls als anfällig. Im Idealfall entwickeln wir ein Schema, dessen Sicherheit nicht von der externen Verifizierung der Schlüssel abhängt.

Bellare-Neven

Wie oben erwähnt, ist das BN Multisignatur-Schema auch ohne derartige Annahmen sicher. So funktioniert es:

  • L = H(X1,X2,…)
  • Jeder Unterzeichner wählt beliebig eine Nonce ri und teilt Ri = riG mit den anderen Unterzeichnern
  • R sei die Summe der Ri Punkte
  • Jeder Unterzeichner berechnet si = ri + H(L,Xi,R,m)xi
  • Die endgültige Signatur ist (R,s) wobei s die Summe der si Werte ist
  • Die Verifizierung erfordert sG = R + H(L,X1,R,m)X1 + H(L,X2,R,m)X2 + …

Technisch gesehen gibt es bei BN eine Pre-Commit-Runde, in der die Unterzeichner zuerst gegenseitig H(Ri) offenlegen, bevor sie die Ri Punkte selbst enthüllen. Dieser Schritt ist notwendig, um die Sicherheit unter der DL-Annahme nachzuweisen, kann aber vermieden werden, wenn wir stattdessen die OMDL-Annahme akzeptieren. Dies ist auch der Unterschied zwischen dem Zweirunden- und dem Dreirunden-MuSig.

Berichtigung vom 19.02.2019: Nach der Lektüre des Papiers von Drijvers et al. haben wir erkannt, dass der obige Absatz falsch ist. Es ist nicht sicher, die Pre-Commit-Runde in MuSig einfach zu überspringen.

Wenn ein IAS erwünscht ist (bei dem jeder Unterzeichner eine eigene Nachricht hat), schlägt Anhang A unserer Abhandlung vor, stattdessen L = H((X1,m1),(X2,m2),…) und si = ri + H(L,R,i)xi zum Unterzeichnen (und analog dazu für die Verifizierung) zu verwenden.

In jedem Fall erfüllt die resultierende Signatur die normale Schnorr-Gleichung nicht mehr, noch jegliche andere Gleichung, die als Funktion einer Kombination der öffentlichen Schlüssel geschrieben werden kann. Mit anderen Worten, wir haben die Schlüssel-Aggregationseigenschaft verloren, um Sicherheit im Plain Public-Key-Modell zu gewinnen.

MuSig

Genau hier setzt MuSig an. Es stellt die Schlüssel-Aggregationseigenschaft wieder her, ohne die Sicherheit zu opfern:

  • L = H(X1,X2,…)
  • X sei die Summe aller H(L,Xi)Xi
  • Jeder Unterzeichner wählt beliebig eine Nonce ri und teilt Ri = riG mit den anderen Unterzeichnern
  • R sei die Summe der Ri Punkte
  • Jeder Unterzeichner berechnet si = ri + H(X,R,m)H(L,Xi)xi
  • Die endgültige Signatur ist (R,s), wobei s die Summe der si-Werte ist
  • Die Verifizierung entspricht wieder sG = R + H(X,R,m)X

Das war’s! Wir mussten nur X nicht als einfache Summe der einzelnen öffentlichen Schlüssel Xi, sondern als Summe der Vielfachen jener Schlüssel definieren, wobei der Multiplikationsfaktor von einem Hash aller teilnehmenden Schlüssel abhängt.

Danksagung

Wir sind Yannick Seurin äußerst dankbar für sein Interesse an der Prüfung der Sicherheit von MuSig, das Abfassen seines Sicherheitsnachweises und das Ausdenken eines Namens.

If you have specific preferences, please, mark the topic(s) you would like to read: