In welcher Komplexitätsklasse befindet sich der Proof-of-Work (Hashcash) von Bitcoin?

Es gibt einen Grund, warum kryptografische Hash-Funktionen, wie der doppelte SHA256, der für den Arbeitsnachweis in Bitcoin verwendet wird, normalerweise nicht mit diesen Komplexitätsklassen beschrieben werden, die asymptotisches Verhalten klassifizieren. Tatsächlich gibt es mehrere.

1. Ein technischer Grund ist, dass Hash-Funktionen oft nicht skalieren. Beispielsweise ist nicht definiert, wie man den Proof-of-Work erweitern würde, um mit 512 Bit zu arbeiten. Eine natürliche Wahl wäre dann, SHA512 zu verwenden, aber der Wechsel von SHA256 zu SHA512 erfordert viele im Wesentlichen willkürliche Entscheidungen, wie das Ändern der Anzahl der Runden von 64 auf 80, die standardisiert sind, aber nicht auf natürliche Weise skalieren und nicht für beliebig großen Hash Größen.

2. Für den Kryptographen ist es nicht relevant. Selbst eine NP-vollständige Hash-Funktion, die der stärkste unter den Komplexitätsfällen wäre, die Sie zum Erstellen eines starken Hashs aufgelistet haben, garantiert nicht alles, was wir von einem kryptografischen Hash oder einer Proof-of-Work-Funktion erwarten. Sich für NP-Vollständigkeit zu qualifizieren, ist lediglich eine starke Heuristik, dass das Problem nicht durch einen Algorithmus gelöst werden kann, der asymptotisch weniger als exponentiell ist. Aber für eine gute Hash-Funktion möchten wir, dass sie bei der sehr begrenzten Bitanzahl, mit der wir sie verwenden, maximal exponentiell ist, in dem Sinne, dass das Lösen wirklich so schwierig ist wie das Ausprobieren aller Möglichkeiten in einer Hash-Funktion. Für seine entsprechende Proof-of-Work-Funktion so schwierig, dass nur ein Bruchteil x des Ausgangsbereichs akzeptabel ist, Dies würde bedeuten, dass wir damit rechnen sollten, dass eine Anzahl von Versuchen erforderlich ist, die dem x/2-fachen des gesamten Ausgabebereichs entspricht, um einen Proof-of-Work zu finden. Alles Bessere würde einen Akademiker veranlassen, die zugehörige Hash-Funktion kaputt zu nennen, selbst wenn es nur die Anzahl der Versuche halbiert, was sie immer noch in eine exponentielle Komplexitätsklasse bringen würde und sogar mit einer NP-vollständigen Funktion leicht möglich wäre .

   Ein beeindruckendes (aber nur oberflächlich verwandtes) Beispiel dafür, wie es nicht ausreicht, etwas scheinbar NP-vollständiges auszuwählen, um etwas kryptografisch Schwieriges zu erhalten, ist die Rucksackkryptographie. Das Problem war natürlich, dass durch die Auswahl von Spezialfällen die Komplexität des Problems reduziert wurde. Der Punkt ist, dass sogar ein NP-vollständiges Problem weniger schwierig sein kann, als tatsächlich jede Lösung ausprobieren zu müssen, obwohl es manchmal so beschrieben wird! Für kryptografische Qualität ist es wörtlich gemeint, jede Eingabe ausprobieren zu müssen; für die Komplexitätsanalyse ist es gut genug, wenn die asymptotische Skalierung exponentiell in der Anzahl der Bits bleibt. Wenn Sie also das Problem auf eine andere NP-vollständige Funktion reduzieren könnten, die nur jedes 1000. Bit als Eingabe verwendet,

3. Es ist schwierig! Und ich denke, diese Schwierigkeit hat Sie bereits in die Irre geführt: Auch Ihre Argumente für die Platzierung dieses Problems in TFNP sind zwar sehr nah an der Wahrheit, aber im mathematischen Sinne nicht wahr. Wenn ich beispielsweise x=0 spezifiziere, kann kein y hash(y) < x erzeugen, was Ihrer Behauptung widerspricht. Ob alle anderen x in Ordnung sind oder ob es einen erforderlichen Mindestwert für x gibt, hängt wahrscheinlich davon ab, wie Sie die "Strings" y definieren, mit denen Hashcash arbeiten soll. Für Bitcoin mit einer begrenzten Anzahl von Bits, die in den Doppel-SHA256 eingehen, würde ich mich nicht wundern, wenn x = 1 auch keine Lösung hat, dh wenn kein Block-Hash genau Null werden kann. Natürlich werden wir es wahrscheinlich nie erfahren. In der Praxis ist es wünschenswert, dass eine Hash-Funktion vollständige Proof-of-Work-Funktionen auf die von Ihnen beschriebene Weise erzeugt, aber ich denke nicht, dass dies eine bewährte Qualität ist. Haftungsausschluss: Ich weiß es ehrlich gesagt nicht. Sie sollten wirklich einen Kryptografen fragen.

   Was noch zu tun ist, um Ihre Frage zu beantworten, nachdem Sie herausgefunden haben, wie die Hash-Funktion skaliert, und überprüft haben, ob sie für beliebig große Größen polynomial bleibt, ist nur dieser Beweis, dass die entsprechende Proof-of-Work-Funktion vollständig ist. Wenn dieser Nachweis nach dem Schubladenprinzip geführt werden kann, haben Sie gezeigt, dass es sich um PPP handelt usw.

   Wo ist also die Schwierigkeit? Zum Beispiel, wenn y mindestens so viele Bits wie x hat und wenn wir Ihr Hashcash so ändern, dass es weniger als oder gleich ist, sondern nur weniger als, und wenn wir bereit sind, es bis zu dem Punkt weiter zu multiplizieren, dass entweder Das Finden eines Arbeitsnachweises oder das Vorhandensein einer Hash-Kollision ist gut genug, um "Hashcash" wahr zu machen, dann würde offensichtlich das Schubladenprinzip gelten, wie es in dem von Ihnen verlinkten Wikipedia-Artikel erläutert wird.

   Aber alles andere würde meines Erachtens nicht ausreichen, um das Schubladenprinzip anzuwenden, und würde daher nicht die Frage beantworten, ob Hashcash in PPP enthalten ist oder nicht. Um noch einmal auf Ihren verlinkten Wikipedia-Artikel zu verweisen: Nur für sehr wenige Probleme ist die Antwort bekannt, selbst für PPP. Für die Sonderfälle PPP, PPA und PPAD wird es natürlich noch schwieriger. Wenn Sie eine Lösung finden, veröffentlichen Sie sie in einer wissenschaftlichen Zeitschrift, nicht nur hier!