#43 // Block 955000 // Aufdeckung von Doppelausgaben [Übersetzung]

Im Original erschienen am 15. Oktober 1993 als Detecting Double Spending von Hal Finney

Hier ist ein Versuch, Chaums digitales Bargeld aus seiner Arbeit, Untraceable Electronic Cash, von Chaum, Fiat, and Naor, aus den ‘Crypto 88 Proceedings’ zu beschreiben. Dieses Bargeld hat die Eigenschaft, dass der Benutzer des Bargelds anonym bleiben kann, solange er es nicht mehr als einmal ausgibt, aber wenn er es doppelt ausgibt, wird seine Identität aufgedeckt.

So funktioniert es im Allgemeinen: Alice eröffnet ein nicht anonymes Konto bei einer Bank. Sie weist sich aus, so dass die Bank weiß, wer sie ist; sowohl sie als auch die Bank kennen ihre Kontonummer. Wenn sie Bargeld abheben will, geht sie zur Bank oder kontaktiert sie elektronisch und legt einen Nachweis darüber vor, wer sie ist und wie ihre Kontonummer lautet, und die Bank gibt ihr etwas digitales Bargeld. Bei dem digitalen Bargeld handelt es sich um ein Informationsmuster, das vielleicht in einer Computerdatei, auf einer Chipkarte oder einem magnetischen Speichermedium gespeichert ist. Später gibt sie das digitale Bargeld aus, indem sie es an Bob, einen Händler, schickt oder übergibt. Bob kann überprüfen, ob das Bargeld von der Bank stammt. Er nimmt das Bargeld an, wenn es gültig ist, und gibt Alice die Ware. Später schickt er das Geld an die Bank, um es seinem eigenen Konto gutzuschreiben.

Beachten Sie, dass dies alles im Grunde mit einer einfachen RSA-Signatur möglich ist. Die Bank könnte Alice eine Erklärung geben, auf der steht: „Dies ist 1 Dollar wert“, signiert mit dem geheimen Schlüssel der Bank. Bob könnte überprüfen, ob die Erklärung tatsächlich von der Bank unterzeichnet wurde, und wüsste daher, dass niemand außer der Bank diese Erklärung erstellt haben kann. Er akzeptiert sie und schickt sie zurück an die Bank, die sie anerkennt, da sie ihre eigene Unterschrift erkennt.

Ein Problem bei diesem einfachen Geld ist, dass Doppelausgaben nicht aufgedeckt oder verhindert werden können, da das Bargeld immer gleich aussieht. Abhilfe kann man schaffen, indem man das Bargeld mit einer eindeutigen Seriennummer versieht. Wenn Bob nun das Bargeld von Alice entgegennimmt, kann er die Bank anrufen und fragen, ob noch jemand die Seriennummer 123456 eingezahlt hat. Wenn nicht, nimmt er das Geld an und zahlt es ein. Dies wird als elektronisches “Online-Geld” bezeichnet; der Händler muss bei jeder Transaktion bei der Bank nachfragen.

Dieses verbesserte, einfache System verdient es jedoch nicht, Bargeld genannt zu werden, denn es fehlt das charakteristische Merkmal von digitalem Bargeld: Es ist nicht anonym. Wenn die Bank sieht, dass Geld mit der Seriennummer 123456 eingezahlt wird, erkennt sie, dass es sich um denselben Schein handelt, den Alice abgehoben hat. Die Bank kann also ableiten, dass Alice das Geld bei Bob ausgegeben hat, und aus dieser Art von Information könnte eine Akte mit allen möglichen Informationen über sie erstellt werden, die ihre Privatsphäre zerstören.

Um Anonymität zu ermöglichen, müssen wir uns mit der Mathematik befassen. Was wir wollen, ist, dass Alice und die Bank gemeinsam eine RSA-Signatur von der Bank erstellen, die nicht gefälscht werden kann, die aber von der Bank nicht als von Alice stammend erkannt wird. Dies ist der erste Punkt, der in Chaums Arbeit erörtert wird.

Das Geld in diesem System hat die Form (x,f(x)1/3)mod⁡ n, wobei n der öffentliche Modulus der Bank ist. f() (und im Folgenden auch g()) ist eine Einwegfunktion, eine Funktion, die sich leicht berechnen lässt, für die aber die Umkehrung zu berechnen nicht durchführbar ist. Es sollte außerdem nicht durchführbar sein, zwei verschiedene y, z zu finden, sodass f(y)=f(z). Heute gibt es mehrere geeignete Auswahlmöglichkeiten für Einwegfunktionen, wobei die häufigsten der MD5-Algorithmus von RSA und der Secure Hash Algorithm (SHA) der US-Regierung sind.

Dass der obige Ausdruck als Geld akzeptiert wird, hat zwei Gründe. Erstens, nur die Bank kann irgendetwas ^ (1/3) mod n berechnen. Das ist im Wesentlichen die RSA-Signieroperation für den Exponenten 3. Niemand sonst kann Kubikwurzeln finden. Der Grund, warum f(x) verwendet wird, ist der folgende. Angenommen, wir schlagen vor, dass (x, x^(1/3)) das Geld sein soll, für ein zufälliges x, mit der Begründung, dass nur die Bank die Kubikwurzel aus x finden könnte. Siehst du, wie man auf diese Weise Geld fälscht? (Nimm dir einen Moment Zeit und überlege, wie ein solches Paar konstruiert werden könnte, selbst wenn man keine Kubikwurzeln ziehen kann.)

Die Antwort ist, dass es leicht ist, dies zu fälschen, indem man zunächst ein zufälliges y wählt und das Paar (y^3, y) vorlegt. Nun haben wir eine Zahl und dazu ihre Kubikwurzel. Und doch mussten wir keine Kubikwurzeln ziehen, um sie zu finden. Deshalb wäre diese Art von Geld nutzlos.

Chaums System vermeidet dies, indem es die Kubikwurzel einer Einwegfunktion von x zieht. Um es zu fälschen, ohne eine Kubikwurzel zu ziehen, müsste man (finv(y^3), y) erzeugen, was dem obigen Muster entsprechen würde, aber man kann die Einwegfunktion auf diese Weise nicht invertieren. Also kann nur die Bank Geld in der richtigen Form erzeugen. Dies kann als die formale, mathematische Form meines obigen informellen “Geldes” betrachtet werden, das ein digital signierter Zettel mit einer Seriennummer war. Hier ist x die Seriennummer, und sie wird auf diese spezielle Weise digital signiert. Mehr wird nicht benötigt.

Das Schöne an diesem Geld ist, dass es eine Blinding-Vorgehensweise (Blinding) ermöglicht, ein Verfahren, bei dem die Bank den Wert signiert, ohne zu wissen, welchen Wert sie signiert. Es funktioniert wie folgt. Alice wählt x, welches das x im Geld sein wird. Sie berechnet f(x), aber anstatt es an die Bank zur Signierung (Erhebung in die dritte Potenz als Wurzel) zu senden, wählt sie zunächst eine zufällige Zahl r und sendet f(x)_r^3 an die Bank. Die Bank erhebt diese Zahl in die 1/3-te Potenz (zieht also die Kubikwurzel) und erhält r _ f(x)^(1/3). Beachte jedoch, dass die Bank r und f(x) nicht getrennt sieht, sondern nur deren Produkt. Sie weiß nicht, was r oder f(x) ist. Tatsächlich könnten sie jeweils beliebig sein.

Die Bank sendet dieses r * f(x)^(1/3) an Alice zurück, und sie dividiert es durch r, das sie kennt. Das liefert ihr f(x)^(1/3), und sie legt das mit x zusammen, um ihr digitales Geld zu erhalten: (x, f(x)^(1/3)). Sie hat ein Stück Geld, das nur von der Bank signiert worden sein könnte, und doch wird die Bank es nicht wiedererkennen, wenn es eingezahlt wird.

Während dieser Abhebung geschehen weitere, nicht mathematische Dinge. Alice muss sich, wie oben erwähnt, bei der Bank ausweisen. Und die Bank wird ihr Konto mit dem Wert des Bargeldes belasten. In diesem System gehen wir der Einfachheit halber davon aus, dass alles Bargeld denselben Wert hat. In einem realen System könnten unterschiedliche Werte durch andere Exponenten als 3 kodiert werden.

Als Alice das Geld einzahlt, muss Bob bei der Bank anrufen, um sich zu vergewissern, dass es nicht schon vorher eingezahlt wurde, da es sich um ein „Online“-System handelt. Obwohl die Bank x nicht erkennt (sie hat noch nie davon gehört), erinnert sie sich an alle x, die eingezahlt wurden, und kann Bob warnen, wenn das Geld schon einmal ausgegeben wurde. Sowohl Bob als auch die Bank können die digitale Unterschrift auf dem Geld verifizieren und werden es daher anerkennen.

Das gesamte oben genannte Material nimmt weniger als eine Seite von Chaums neunseitiger Arbeit ein. Für Chaum ist das alles trivial. Nun kommen wir zum interessanten Teil. Jetzt schauen wir uns das System an, das Doppelausgebern (Double spender) ermöglicht, ihre Anonymität zu verlieren. Dies ermöglicht ein elektronisches “Offline-Geld”; Bob muss nicht mehr bei der Bank nachfragen, ob das Geld bereits ausgegeben wurde. Er nimmt es von Alice an, weil er weiß, dass die Bank das Geld einlösen und Alice verklagen wird, um den Verlust auszugleichen, falls sie betrügt.

(Um diese Erklärung leichter nachvollziehbar zu machen, beschreibe ich eine leicht vereinfachte Version von Chaums Offline-Bargeld. Die von mir beschriebene Version erfordert die Verwendung einer nicht invertierbaren Einwegfunktion wie das oben verwendete f(). Chaums Version erfordert keine so starke Annahme und bietet „bedingungslose“ Rückverfolgbarkeit, selbst wenn die Einwegfunktion gebrochen ist).

Beginnen wir mit der Form des Geldes selbst. Es ist das Produkt aus k/2 Zahlen, wobei k ein “Sicherheitsparameter” ist, der die Chance beeinflusst, dass ein Betrüger erfolgreich ist. Jede Zahl hat die Form g(xi,yi)^(1/3), wobei g eine zweistellige Einwegfunktion ist, ähnlich dem f von oben. (Die “xi”, “yi”, “ai”, usw. sind separate Werte für jedes i von 0 bis k/2.)

xi und yi verhalten sich wie folgt: xi=f(ai), wobei ai eine Zufallszahl und f eine weitere Einwegfunktion ist. yi ist etwas komplizierter. Es ist f(ai xor ), wobei , der Schlüssel zu dieser gesamten Operation, identifizierende Informationen über Alices Konto ist! Es ist ihre Kontonummer, verkettet mit einer Seriennummer für das Bargeld.

Nun, warum all diese Mühe? Hier ist der Grund. Wenn man sowohl ai als auch (ai xor ) für ein bestimmtes i herausfinden könnte, würde man Alices Identität kennen. (Die XOR-Verknüpfung der beiden würde ergeben.) Wenn Alice doppelt ausgibt, werden sowohl ai als auch ai xor offengelegt.

Was geschieht, wenn Alice die Münze ausgibt, ist Folgendes. Für jedes i von 0 bis k/2 wählt Bob zufällig 0 oder 1. Wenn er 1 wählt, erhält er ai und yi. Wenn er 0 wählt, erhält er (ai xor ) und xi. Dies ermöglicht es ihm, die Signatur auf dem Geld zu überprüfen, wie unten ausführlicher beschrieben wird.

Beachte, dass Bob, wenn er diese Informationen erhält, eine Reihe von ai kennenlernt und eine Reihe von (ai xor ) kennenlernt, diese aber für unterschiedliche i gelten. Er kennt weder ai als auch (ai xor ) für ein und dasselbe i. Also kann er Alices Anonymität nicht brechen.

Wenn Bob das Geld bei der Bank einzahlt, gibt er die Informationen weiter, die er von Alice über ai und so weiter erhalten hat.

Nehmen wir nun an, Alice betrügt. Sie gibt das Geld woanders wieder aus, bei Charlie. Charlie geht genauso vor wie Bob und wählt für jeden Wert von i zufällig 0 oder 1. Hier ist der Haken. Da er nach dem Zufallsprinzip wählt, ist es sehr unwahrscheinlich, dass er genau dieselben 0en und 1en wählt, die Bob gewählt hat. (Hier spielt die Größe von k eine Rolle - je größer sie ist, desto unwahrscheinlicher ist es, dass Charlie und Bob das gleiche Muster von 0 und 1 wählen. Allerdings dauern die Berechnungen dann auch länger.) Das bedeutet, dass Charlie für einen oder mehrere Werte von i wahrscheinlich eine 0 wählt, während Bob eine 1 wählt, oder umgekehrt.

Aus diesem Grund, wenn Bob ai für dieses i erhält, wird Charlie ai xor erhalten. Oder wenn Bob ai xor erhält, wird Charlie ai erhalten. In jedem Fall, wenn Charlie seinen Datensatz über diese Informationen an die Bank sendet, wird die Bank Bobs und Charlies Informationen zusammenführen und sowohl ai als auch xor erhalten. Die XOR-Verknüpfung dieser beiden ergibt , und Alice wird überführt! Das ist die Grundidee.

(Chaum schlägt vor, sich nicht nur auf den Zufall zu verlassen, um sicherzustellen, dass Bob und Charlie unterschiedliche Folgen aus 1 und 0 verwenden. Zumindest einige der Bits könnten von der Bank an Bob und Charlie so zugewiesen werden, dass jeder eine unterschiedliche Nummer erhält. Auf diese Weise wäre garantiert, dass Bob und Charlie für ein bestimmtes i entgegengesetzte Werte wählen.)

Der Grund, warum das Geld die Form hat, die es hat, liegt darin, dass Bob überprüfen kann, ob es von der Bank signiert ist. Für jeden Wert von i muss Alice ihm ausreichend Informationen geben, um xi und yi zu berechnen. Wenn Bob eine 1 wählt, gibt sie ihm ai und yi. Mit ai kann Bob xi (=f(ai)) berechnen, und damit sowie mit yi kann er g(xi,yi) berechnen. Wenn Bob eine 0 wählt, gibt sie ihm (ai xor ), wie zuvor beschrieben, und auch xi. Mit (ai xor ) berechnet Bob yi (=f(ai xor )), und damit sowie mit xi kann er g(xi,yi) berechnen.

Für jedes i erhält Bob also, unabhängig davon, ob er eine 0 oder eine 1 wählt, ausreichend Informationen, um g(xi,yi) zu berechnen. Er multipliziert diese alle miteinander und bestätigt, dass sie gleich dem ursprünglichen “Geld”-Wert von Alice sind, wenn dieser in die 3. Potenz erhoben wird (erinnere dich daran, dass das Geld das Produkt aus g(xi,yi)^(1/3) für alle i war). Nur die Bank konnte eine Signatur über diese Einwegfunktion f erzeugen, deren Argumente diese spezielle Form annehmen.

Es gibt noch eine weitere Komplikation. (Nun ja, tatsächlich existiert eine nahezu unendliche Anzahl von Komplikationen, wenn man genau genug hinsieht. Aber wir werden uns nur auf eine weitere konzentrieren.) Alice muss diese spezielle Form von Geld von der Bank auf eine solche Weise erhalten, dass die Bank es nicht wiedererkennt. Das bedeutet, dass sie es verblenden (blind) muss. Aber in diesem Fall möchte die Bank sicherstellen, dass das Geld die richtige Form hat, wenn sie es signiert; insbesondere möchte sie sich verdammt sicher sein, dass Alices , das tief in all diesen f’s von g’s vergraben ist, tatsächlich die richtige für sie ist. Aber da die Bank nicht sehen kann, was sie signiert, ist dies schwer umzusetzen.

Chaum verwendet dafür Cut-and-Choose. Er lässt Alice all diese f’s und g’s gemäß der obigen Form vorbereiten, wobei sie sorgfältig ihr eigenes belastendes in jedes einzelne einbettet. Dann multipliziert sie jedes g(xi,yi) mit einem Blinding-Faktor ri^3, genau wie beim ersten Bargeld. Diese sendet Sie an die Bank zur Signierung.

Der Trick ist jedoch, dass sie doppelt so viele sendet, wie verwendet werden. Sie sendet k davon, aber nur k/2 werden verwendet. (Deshalb verwendete die obige Schleife k/2 als Grenze.) Die Bank wählt zufällig k/2 aus den k aus, die sie gesendet hat, als diejenigen, die tatsächlich verwendet werden. Alice muss dann die Blinding-Werte ri für diejenigen senden, die die Bank nicht ausgewählt hat.

Die Idee dahinter ist, dass Alice, wenn sie zu betrügen versucht und “Bozo” statt “Alice” in dieses -Feld einbettet, ein Risiko eingeht. Erstens, damit es nützlich ist, wird sie es in viele -Felder für verschiedene Werte von i einbetten müssen. Wenn Bob und Charlie nach ihrer Doppelausgabe ihre Aufzeichnungen vergleichen, wird jeder Wert von i, für den sie unterschiedliche 0 und 1 gewählt haben, was durchschnittlich die Hälfte sein wird, ein -Feld enthüllen. Wenn sie nur wenige fälscht, stehen die Chancen gut, dass ihre wahre Identität dennoch enthüllt wird.

Wenn sie aber eine große Menge davon fälscht, dann stehen die Chancen gut, dass, wenn die Bank die Hälfte auswählt, zumindest einige der Fälschungen in der Menge sein werden, die die Bank nicht ausgewählt hat. Dann, wenn Alice ihre Blinding-r-Faktoren offenlegen muss, ist das Spiel vorbei. Die Bank wird all diejenigen g(xi,yi)’s, die nicht verwendet werden, ent-blinden und die gefälschten -Felder sehen.

Diese Cut-and-Choose-Methode hat den Nachteil, dass Alice bei der Vorbereitung des Geldes doppelt so viel Arbeit leisten muss, von der die Hälfte lediglich verworfen wird. Aber sie ist ein einfaches, “brachiales” Verfahren, um sicherzustellen, dass Blinding-Signaturen tatsächlich auf ordnungsgemäß geformten Daten durchgeführt werden.

So sieht’s aus. Anonymität, solange man nicht betrügt, und Doppelausgeber (Double spender) werden überführt. Es ist ein wenig kompliziert, aber dafür gibt es Computer; Bob und Alice würden das alles nicht von Hand machen. Alice würde die Taste “Geldkandidat generieren” drücken und etwas erhalten, das an die Bank gesendet wird (viele der neuen PDA’s verfügen über Infrarot-Funkkommunikation, die ideal für direkte, von Angesicht zu Angesicht durchgeführte Transaktionen wäre). Bob würde die Taste “Geld prüfen” drücken, wenn Alice es ausgibt, und es würde rot oder grün aufleuchten. Solange die Berechnungen nicht tatsächlich zu viel Zeit in Anspruch nehmen, was in diesem Fall trotz dieser weitschweifigen Erklärung wirklich nicht der Fall ist, können die Beteiligten die Details ignorieren.