Veröffentlicht am 12-09-2019

Der Da Vinci Zero Knowledge Proof

Zero Knowledge Proofs sind ein heißes Thema in der Blockchain-Welt. Die folgende Kurzgeschichte zeigt eine Technik, die häufig in Zero Knowledge Proofs verwendet wird, nämlich das mehrmalige Wiederholen eines Protokolls, um den „Fehler bei der Zuverlässigkeit“ zu reduzieren.

Welche Mona Lisa ist welche? Bild: https://commons.wikimedia.org/wiki/Category:Mona_Lisa

Geschichte

Peggy Pegg-Whistle trank Tee in ihrem Cottage in Nether Bumpstead, Suffolk, Großbritannien, als der Anruf von Interpol kam. Sie wurde sofort im Louvre gebraucht. Ein Hubschrauber war unterwegs.

Peggy war die beste Kunsthistorikerin der Welt und der Ansprechpartner, wenn es um Da Vinci ging. Sie hatte das Gefühl, welches Gemälde diesen Anruf betraf.

Paris

Einige Stunden später erreichte sie den Louvre. Sie wurde in einem Nebenraum von einem Mann namens Victor begrüßt.

Es war sofort klar, dass Victor keine Lust auf Smalltalk hatte. Er verschwendete keine Zeit, um zu erklären, was los war.

„Danke, dass Sie nach Paris gekommen sind, Frau Pegg-Whistle. Wir befinden uns hier in einer seltsamen Situation. Nun, das ist streng geheim, aber die Mona Lisa wurde letzte Nacht gestohlen. Die Polizei bewegte sich schnell. Es gab eine Verfolgungsjagd auf den Champs Élysées um den Arc du Triomphe in Richtung Bois du Boulogne und zurück über die Seine. Endlich haben wir den Kunstdieb unter dem Eiffelturm gefangen.

„Als wir jedoch in den Fluchtwagen schauten, standen zwei identische Mona Lisas vor uns! Wir hatten keine andere Wahl, als beide Bilder zu nehmen und hierher zurückzubringen.

„Und hier befinden wir uns. Hinter diesen beiden schwarzen Blättern befinden sich die beiden Gemälde von Mona Lisa, und wir wissen nicht, welches das Original ist.

"Wir konnten keine Unterschiede zwischen ihnen feststellen und wussten nicht, wen wir sonst anrufen sollten. Ich höre, sie nennen dich Peggy die Prüferin, da du nie eine Fälschung übersehen hast.

"Heute Abend gibt es eine Ausstellung für einige der größten Namen in Paris. Ich muss in den nächsten 5 Minuten wissen, welches dieser Bilder das echte ist, damit es rechtzeitig wieder in die Galerie gehängt werden kann. Könnten Sie mir bitte sagen, Frau Pegg-Whistle, welches Gemälde die wahre Mona Lisa ist? “

Er sagte die letzte Zeile, als er die schwarzen Laken von den beiden Gemälden, die nebeneinander an der Wand standen, abwarf.

Peggy sah sich eine Weile die beiden Bilder an. Sie waren in der Tat sehr ähnlich. Auf den ersten Blick sahen sie absolut identisch aus. Sie war erstaunt über die Genauigkeit der Fälschung.

Sie trat näher und inspizierte beide für einige Minuten. Sie betrachtete beide Bilder nur einen Zentimeter von den Leinwänden entfernt.

Schließlich wich sie von den Gemälden zurück ... sie hatte einen Unterschied entdeckt. Sie wusste, welches der Betrug war.

Sie wollte genau erzählen, was sie verraten hatte, aber irgendetwas ließ sie innehalten.

Wie konnte sie diesem Mann Victor vertrauen?

Sie hatte keinen Beweis dafür gesehen, dass er ein Beamter im Louvre oder ein Mitglied der französischen Polizei war. Sie hatte keine Beweise dafür gesehen, dass er oder irgendetwas, was er gesagt hatte, authentisch war.

Die Frist von 5 Minuten schien extrem kurz zu sein und plötzlich dachte sie ... was wäre, wenn Victor tatsächlich der Verbrecher hier wäre?

Und jetzt dachte sie darüber nach, es war etwas Ungewöhnliches, Unangenehmes, Unappetitliches und Ungewöhnliches an Victor und Peggys Intuitionen waren normalerweise genau richtig.

Vielleicht hatte Victor die falsche Mona Lisa erfunden und war dabei, die echte durch seine Fälschung zu ersetzen. Seine letzte Überprüfung der Richtigkeit bestand darin, Peggy the Prover, die weltbeste Kunsthistorikerin, mit den beiden Gemälden nebeneinander zu testen.

Sie versuchte, solche sensationellen Ideen beiseite zu schieben, aber es gab etwas an ihm, das sie einfach nicht mochte. Die ganze Situation fühlte sich seltsam an.

Was sollte sie tun?

Vielleicht sollte sie einfach sagen, dass die beiden Bilder identisch waren… aber dann würde er die Fälschung wieder aufhängen (denn er wusste sicherlich, welches die Fälschung war, wenn er sie geschaffen hatte, vielleicht hatte er die Rückseite des Rahmens markiert oder so) und er würde den wirklichen stehlen und denken, dass niemand es jemals erfahren würde. Sie würde dann die Polizei alarmieren müssen, dass die echte Mona Lisa gestohlen worden war.

Oder ... sie sollte ihm den Unterschied zwischen den Gemälden zeigen. Aber dann würde er vom weltbesten Kunsthistoriker lernen, wo die Fälschung verbessert werden könnte. Und wenn er eine so gute Fälschung gemacht hätte und dann über den winzigen Unterschied informiert worden wäre, den sie entdeckt hatte, wäre er sofort der beste Fälscher der Welt!

Sie brauchte einen Weg, um zu beweisen, dass sie die Bilder unterscheiden konnte, damit er nicht mit dem echten Gemälde davonlief. Aber sie musste es tun, ohne etwas über den Unterschied zu erfahren, den sie entdeckt hatte, damit er nichts von dem besten Kunsthistoriker der Welt lernte ... zumindest bis sie jemanden in den Raum bringen konnte, dem sie vertraute.

Sie musste in null Wissen beweisen, dass sie den Unterschied zwischen den Gemälden kannte.

Sie begann…

„Ich werde dir beweisen, dass diese beiden Bilder unterschiedlich sind, und so weiß ich, welches die echte Mona Lisa ist. Aber ich werde nicht verraten, wo der Unterschied liegt. “

Victor zeigte sofort, dass seine Hand nicht so vertrauenswürdig war, wie er zu erkennen versuchte.

„Wie um alles in der Welt kannst du das machen ?! Es tut mir leid, Peggy, aber wir sind hier in Eile. Kannst du mir bitte sagen, was der Unterschied ist? “, Erwiderte er.

Das Protokoll

"Das werden wir tun", begann sie gelassen. „Ich werde auf eines der Bilder zeigen, und Sie müssen sich daran erinnern, auf welches ich gezeigt habe. Dann wirst du mir die Augen verbinden. Anschließend können Sie die Bilder entweder tauschen oder an ihrer aktuellen Position belassen. Wenn Sie fertig sind, können Sie meine Augenbinde entfernen und ich werde noch einmal auf das Gemälde zeigen, auf das ich ursprünglich gezeigt habe. “

Warf Victor ein, "aber das ist nur ein 50-50, woher weiß ich, dass Sie nicht nur raten?"

"Das tust du nicht", antwortete sie, "aber dann werden wir diesen Test 10 Mal wiederholen. Und jedes Mal, wenn wir dies tun, werden Sie das Gemälde, auf das ich ursprünglich gezeigt habe, im Auge behalten, und ich werde erneut getestet, ob ich auf dasselbe Gemälde zeigen kann. Wenn ich tatsächlich einen Unterschied zwischen den Gemälden kenne, kann ich jedes Mal auf dasselbe Gemälde verweisen.

„Wenn ich jedoch den Unterschied zwischen ihnen nicht erkennen kann, habe ich in den 10 Runden zusammen weniger als 1 von 1000 Chancen, nur richtig zu raten. Um genau zu sein, die Wahrscheinlichkeit, richtig zu raten, ist 1/2 hoch 10 oder 1 von 1024. “

Victor dachte über seine Möglichkeiten nach, hatte aber wirklich keine andere Wahl, als das von Peggy vorgegebene Protokoll durchzuarbeiten. Während der 10 Runden des Protokolls zeigte sie tatsächlich, indem sie jedes Mal auf dasselbe Gemälde zeigte, dass sie mit sehr hoher Wahrscheinlichkeit (1023/1024 oder 99,9%) den Unterschied zwischen den Gemälden erkennen konnte, ohne irgendwelche Informationen preiszugeben über den Unterschied, den sie entdeckt hatte.

Was danach geschah?

Außerdem waren Peggys Intuitionen richtig! Victor wusste bereits vor ihrer Ankunft, welche die echte Mona Lisa war. Er war ein Fälscher und plante, das echte Gemälde zu stehlen. Er hatte Peggy als letzte Kontrolle kontaktiert, um sicherzugehen, dass er damit durchkommen würde.

Er sah jedoch amüsiert zu, wie sie Runde für Runde auf dasselbe Gemälde zeigte, was seine Fälschung als minderwertig anzeigte, aber nicht enthüllte, was genau das Spiel verraten hatte.

Nach den 10 Runden des Protokolls verließ Peggy den Raum und rief sofort ihre Freundin an, die im Louvre arbeitete, dem sie vertraute.

5 Minuten später kehrte sie mit ihrer Freundin in das Zimmer zurück und stellte fest, dass Victor und die echte Mona Lisa gegangen waren! Er hatte die Fälschung eindeutig aufgegeben und war ungeduldig mit dem echten Gemälde davongelaufen.

Peggy alarmierte sofort die Polizei und die Jagd war auf der Suche nach Victor!

Mit wissensfreien Beweisen können Sie nachweisen, dass Sie etwas wissen, ohne Informationen preiszugeben, die Sie nicht preisgeben möchten.

In der akademischen Literatur zu wissensfreien Beweisen wird ein Protokoll als vollkommen „gesund“ bezeichnet, wenn der Prüfer zu 100% sicher sein kann, dass der Prüfer das Geheimnis tatsächlich kennt. Häufig wird die Eigenschaft des Nullwissens eines Protokolls auf Kosten der Soliditätseigenschaft des Protokolls erhalten.

In dem obigen Protokoll hat jede Runde des Protokolls einen "Tonigkeitsfehler" von 1/2, d. H. Der Prüfer ist nur zu 50% sicher, dass der Prüfer das Geheimnis in jeder Runde kennt.

Viele wissensfreie Protokolle wiederholen den gleichen Test mehrmals, wobei jede Runde einen festen Fehler aufweist. Diese Wiederholung erzeugt einen viel kleineren Klangfehler.

Schauen Sie sich bitte meine früheren Blog-Hash-Funktionen an, die mit Emojis erklärt wurden, und schauen Sie sich auch meine Firma Pilcro an, eine App für den sofortigen Zugriff auf Ihre bevorzugten Markenassets, wenn Sie Markeninhalte erstellen.

Diese Geschichte wurde in The Startup veröffentlicht, der größten Veröffentlichung zu Unternehmertum von Medium, gefolgt von mehr als 303.461 Personen.

Abonnieren Sie hier unsere Top Stories.

Siehe auch

Drängt die politische Kunst andere Kunstformen an die Peripherie?Wie trägt man eine weite Hose28 Days of the Web: Ein Interview mit Elton Leonard, Art Director der Honey River Design GroupHör auf zu rennen, vielleicht versucht der Frieden dich zu finden“Loving Vincent” - Wie die Ignorati ein Meisterwerk in Öl töteten…Wie ich eine verwirrende, aber erstaunliche Botschaft von Gott lernte