Threshold-ECDSA: Signieren durch mehrere Parteien

ECDSA-Signaturen erfordern die Berechnung einer zufälligen Nonce k, des Kurvenpunkts R = k*G und der Signatur s = k^{-1}(h + r*x) mod n, wobei x der private Schlüssel und r die x-Koordinate von R ist. Die Invertierung von k und die Multiplikation mit dem privaten Schlüssel machen ECDSA inhärent nichtlinear, anders als Schnorr-Signaturen, bei denen die Antwort eine einfache lineare Kombination ist. Diese Nichtlinearität macht es äußerst schwierig, die Berechnung auf mehrere Parteien zu verteilen.

Das von Gennaro und Goldfeder entwickelte GG18-Protokoll (2018) war die erste praktisch einsetzbare Zwei-Parteien- und Threshold-ECDSA-Konstruktion, die ohne einen vertrauenswürdigen Dealer sicher ist. Die zentrale Idee besteht darin, homomorphe Paillier-Verschlüsselung für die erforderliche multiplikativ-zu-additive (MtA)-Umwandlung der nichtlinearen ECDSA-Berechnung zu verwenden. GG18 bietet simulationsbasierte Sicherheit gegenüber statischen, ehrlich-aber-neugierigen Angreifern.

GG20 (Gennaro und Goldfeder 2020) verbesserte GG18, indem es die Sicherheit gegenüber bösartigen Angreifern ohne Trusted Setup nachwies. GG20 ergänzte Zero-Knowledge-Beweise, um sicherzustellen, dass jede Partei das Protokoll korrekt befolgt. Diese Beweise verhindern, dass eine bösartige Partei die Nonce oder die Signatur manipuliert, um Informationen über die Schlüsselanteile anderer Parteien zu gewinnen. GG20 wurde zur Grundlage vieler produktiver MPC-Wallet-Implementierungen.

CGGMP21 (Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021) ist derzeit das fortschrittlichste Threshold-ECDSA-Protokoll. Es ermöglicht einen identifizierbaren Abbruch. Das bedeutet: Wenn das Signaturprotokoll aufgrund bösartigen Verhaltens fehlschlägt, kann das Protokoll die verantwortliche Partei identifizieren. Dies ist für den Einsatz in Unternehmen entscheidend, bei dem Verantwortlichkeit eine wichtige Rolle spielt. CGGMP21 ist in beliebten MPC-Bibliotheken wie tss-lib und multi-party-sig implementiert.

Die zentrale Herausforderung bei Threshold-ECDSA besteht darin, ein Produkt aus Geheimnisanteilen zu berechnen, ohne diese offenzulegen. Die MtA-Umwandlung (multiplikativ zu additiv) wandelt das Produkt a*b aus den Anteilen zweier Parteien in additive Anteile um: Partei 1 erhält alpha und Partei 2 erhält beta, sodass alpha + beta = a*b gilt. Dies wird mithilfe der Paillier-Verschlüsselung erreicht: Partei 1 verschlüsselt a, Partei 2 multipliziert den Chiffretext homomorph mit b und addiert Zufallswerte. Das Ergebnis wird von Partei 1 entschlüsselt, um additive Anteile zu erhalten.

Die Paillier-Verschlüsselung ist ein partiell homomorphes Verschlüsselungsverfahren, das sowohl Addition als auch Multiplikation mit einem Klartext unterstützt. Ausgehend von einer Verschlüsselung Enc(a) kann jeder für ein bekanntes b Enc(a*b) berechnen, ohne zu entschlüsseln. Diese Eigenschaft ermöglicht das MtA-Protokoll: Partei 1 erzeugt ein Paillier-Schlüsselpaar und sendet Enc(k1) sowie Enc(x1), also die Anteile an Nonce und privatem Schlüssel. Partei 2 verwendet homomorphe Operationen, um ihren Beitrag zu berechnen, ohne k1 oder x1 zu erfahren.

Eine Threshold-ECDSA-Signatur umfasst typischerweise mehrere Kommunikationsrunden. Bei GG20 gibt es eine Vorverarbeitungsphase mit zwei Runden, in der Commitments für die Nonce und zufällige Blinding-Werte berechnet werden, sowie eine Online-Signaturphase mit einer Runde, in der Teilsignaturen kombiniert werden. Die Vorverarbeitung kann erfolgen, bevor die Nachricht bekannt ist, wodurch sich die Online-Latenz auf eine einzige Runde reduziert. CGGMP21 optimiert diesen Ablauf weiter.

Ein identifizierbarer Abbruch bedeutet: Wenn das Threshold-Signaturprotokoll fehlschlägt, weil eine Partei eine fehlerhafte Nachricht gesendet oder das Protokoll nicht befolgt hat, können die ehrlichen Parteien kryptografisch feststellen, welche Partei sich regelwidrig verhalten hat. Dazu sind in jedem Schritt Zero-Knowledge-Beweise für die korrekte Berechnung erforderlich. Ohne identifizierbaren Abbruch könnte eine bösartige Partei einen Denial-of-Service-Angriff verursachen, indem sie die Durchführung des Protokolls verweigert, ohne identifiziert zu werden.

EdDSA (Schnorr-basierte Signaturen über Ed25519) lässt sich wesentlich einfacher als ECDSA auf mehrere Parteien verteilen, da Schnorr-Signaturen linear sind: Die Antwort z = r + c*x ist eine Summe additiver Anteile. FROST (Flexible Round-Optimized Schnorr Threshold) von Komlo und Goldberg (2020) ermöglicht zweirundige Threshold-Schnorr-Signaturen ohne vertrauenswürdige Einrichtung. FROST wird derzeit von der IETF (RFC-Entwurf) für den Einsatz in datenschutzfreundlichen Protokollen und Kryptowährungs-Wallets standardisiert.

Threshold-ECDSA ist aufgrund des MtA-Protokolls und der Zero-Knowledge-Beweise rechenintensiver als ECDSA mit einer einzelnen Partei. Eine GG20-Signatur mit zwei Parteien dauert auf moderner Hardware ungefähr 1–2 Sekunden. Bei einem Threshold-Schema mit größerem n dauert sie aufgrund der zusätzlichen paarweisen MtA-Ausführungen länger. Die Optimierungen von CGGMP21 reduzieren die Dauer auf einige hundert Millisekunden. Für Kryptowährungstransaktionen, bei denen die Signaturlatenz wichtig ist, ist diese Leistung akzeptabel, aber dennoch erheblich.

Threshold-ECDSA wird im institutionellen Finanzwesen in großem Maßstab eingesetzt. Fireblocks verwendet Threshold-ECDSA auf Basis von GG20 und sichert damit ein Transaktionsvolumen von über 4 Billionen US-Dollar. Coinbase Prime verwendet eine MPC-Verwahrung auf Grundlage von Threshold-Signaturen. Qredo und Copper.co bieten Threshold-ECDSA für die institutionelle Verwaltung von Vermögenswerten an. Die Go-Bibliothek tss-lib (von Binance verwendet) und multi-party-sig (von Coinbase verwendet) sind wichtige Open-Source-Implementierungen.

Threshold-ECDSA ermöglicht es t Parteien zu signieren, ohne dass eine Partei den vollständigen Schlüssel kennt. Die nichtlineare Struktur von ECDSA erfordert eine MtA-Umwandlung mithilfe der homomorphen Paillier-Verschlüsselung. GG18 legte den Grundstein für diesen Ansatz, GG20 ergänzte die Sicherheit gegen bösartige Parteien und CGGMP21 fügte den identifizierbaren Abbruch hinzu. EdDSA/Schnorr lässt sich mithilfe von FROST einfacher auf mehrere Parteien verteilen (zwei Runden, keine vertrauenswürdige Einrichtung). Produktive Einsätze bei Fireblocks und Coinbase sichern Vermögenswerte im Wert von Billionen.