Gibt es ein Proof-of-Work-System, das wesentlich mehr Speicher zum Generieren als zum Verifizieren benötigt?

Litecoin widersteht der GPU-Beschleunigung, indem es eine Verschlüsselungs-basierte Hash-Funktion verwendet, deren Generierung und Überprüfung etwas Speicher benötigt. Das Problem dabei ist, dass der rParameter hoch genug eingestellt werden muss, dass es schwierig ist, eine GPU zu verwenden, aber niedrig genug, dass Clients mit wenig Speicher (z. B. Smartphones) immer noch effizient Blöcke verifizieren können.

Gibt es einen Arbeitsnachweis, der erheblich mehr Speicher benötigt, um einen Arbeitsnachweis für einen Block zu generieren, als um zu überprüfen, ob ein Block einen ausreichenden Arbeitsnachweis enthält?

Ich habe von zwei möglichen Ansätzen gehört: Zeit-Speicher-Kompromiss mit Scrypt und einem Hash-Algorithmus der Graphentheorie, der viel Speicher benötigt, um Lösungen zu finden.

Was meinst du mit Hash-Funktion "überprüfen"? Neu generieren und vergleichen?
@amaclin So ungefähr? Ich habe meine Frage eingegrenzt. Ist es klarer?
Es gibt keine "Hash-Funktion überprüfen". PoW überprüft, ob das Ergebnis kleiner als das Ziel ist. Aber um es zu überprüfen, sollten wir den Wert berechnen
@amaclin There is no such thing as "verify hash function" Sicher gibt es das. But to verify it we should calculate the valueIch habe den Zeit-Speicher-Kompromiss mit scrypt als Beispiel gegeben, also ist es eindeutig möglich.
Litecoin „widersteht“ der GPU nicht. Nicht einmal ASICs. "Versucht, Widerstand zu leisten ..." vielleicht, aber es gibt Gerüchte, dass der Schöpfer bereits bei der Einführung eine GPU verwendet hat. Außerdem: Das Finden und Verifizieren eines Hashs ist dasselbe, der einzige Unterschied besteht darin, dass Sie die Berechnung beim Verifizieren nur einmal anstelle von Milliarden von Malen durchführen müssen.
@Jannes Litecoin doesn't 'resist' GPU. Not even ASICs.Es ist zumindest besser als Bitcoin. Wenn Sie eine alternative Formulierung haben, können Sie meine Frage gerne bearbeiten. Also: finding and verifying a hash are the same thing, only difference is that when verifying you only need to do the calculation once instead of billions of times.Mir ist bewusst, dass SHA256 so ist. Könnte es ein Nicht-SHA256- oder Nicht-Hashcash-basiertes Proof-of-Work-System geben, das die von mir festgelegten Anforderungen erfüllt?
@NickODell Es gibt absolut nichts "Besseres" daran ... der ganze Sinn des Arbeitsnachweises besteht darin, so einfach wie möglich zu sein, da dies die Eintrittsbarriere für neue Spieler (ASIC-Hersteller) senkt. Das bedeutet, dass weniger Menschen in einer privilegierten Position sind, einen unfairen Vorteil gegenüber anderen zu haben (wie zum Beispiel die Schöpfer der Münze selbst). Es macht keinen Sinn, PoW künstlich schwerer zu machen. Natürlich versuchen Scamcoin-Ersteller, es wie einen Vorteil klingen zu lassen, aber es ist wirklich das Gegenteil.
@Jannes Die Eintrittsbarriere für das ASIC-Mining wird nicht gesenkt, da die chinesischen Mining-Farmen ihre Hardware nicht preisgeben (und unter Berücksichtigung der Versorgungsprobleme mit BFL), neige ich zu der Annahme, dass es eine äußerst unterschiedliche Eintrittsbarriere gibt zum Asic-Mining
@Jannes Sie betreten das Reich der Spekulation über die Motive von Altcoin-Schöpfern, was unglaublich offtopic ist.
@WizardOfOzzie WENN es eine unterschiedliche Eintrittsbarriere gibt, wird es nur noch schlimmer, wenn Sie die Designs und Chips komplexer machen. Wenn Sie das tun, brauchen Sie klügere Leute, um sie zu entwerfen, teurere Maschinen, um sie herzustellen usw.
Verwandte: listen.randombit.net/pipermail/cryptography/2013-January/… aber wahrscheinlich nicht geeignet für Altcoin-Nutzung.

Antworten (3)

Ich denke, ein Mining-Prozess, der stochastische Stichproben aus einem großen Datensatz verwendet, würde die von Ihnen festgelegten Anforderungen erfüllen. Dafür liefert die Blockchain sogar einen tollen Datensatz. Nehmen wir zum Beispiel an, jede Nonce erfordert, dass Sie die Blockchain zufällig abtasten, um ein paar Bytes herauszusuchen. Da Sie beim Mining viele Nonces verwenden und nicht vorhersagen konnten, welche Daten Sie aus der Blockchain benötigen würden, müssten Sie im Grunde die gesamte Blockchain (jeden öffentlich vereinbarten Datensatz, wirklich) während des Minings verfügbar haben. Die Lösung kann dann mit einer kleinen Stichprobe dieses Datensatzes und einem Beweis dafür, dass die Daten in dem Datensatz enthalten sind, verifiziert werden. Wenn Sie das Blockchain-Beispiel verwenden, benötigen Sie wahrscheinlich eine Kette von Block-Headern und einen Merkle-Zweig für die ausgewählten Transaktionsdaten.

Eine andere Möglichkeit, dies zu tun, wäre die Verwendung eines großen zufälligen Merkle-Baums . Nehmen wir an, jemand hat einen Merkle-Baum mit 2^31 zufälligen 32-Byte-Werten erstellt. Wenn man bedenkt, dass auch die Merkle-Zweige gespeichert werden müssen, sind das (1 + 2 + 2^2 + 2^3 + ... + 2^31) * 32 bytes, oder (2^32-1)*32 ~= 137.4 GBvon Daten insgesamt. Diese Daten sind sehr öffentlich für jeden verfügbar, der sie wirklich herunterladen und den Merkle-Root überprüfen wollte. Die Merkle-Wurzel würde als Mining-Merkle-Wurzel bekannt gemacht, und sie ist eine bekannte und vereinbarte Konstante. Beim Mining wird dieser zufällige Merkle-Baum abgetastet und gehasht, und mit dem Finden einer erfolgreichen Lösung wird der Merkle-Baum-Zweig bereitgestellt, der beweist, dass sich die abgetasteten Daten tatsächlich im öffentlich vereinbarten Merkle-Baum befinden.

In diesem Schema werden ~137,4 GB Speicher zum Schürfen benötigt, aber nur ~1 kB an Daten, um eine Lösung gegen die öffentlich vereinbarte Mining-Merkle-Root zu verifizieren.

Und die Zahlen könnten hier offensichtlich angepasst werden, damit die Leute schürfen können, ohne 137,4 GB ihrer Festplatte aufzugeben. Es müsste ein Ausgleich erreicht werden.

Das gefällt mir eigentlich viel besser, wenn ich darüber nachdenke, weil es nicht den Nebeneffekt hat, dass das Mining länger dauern kann, wenn die Blockchain wächst. Sie könnten wahrscheinlich sogar einen Snapshot der Bitcoin-Blockchain erstellen und diesen als öffentlich überprüfbaren Datensatz verwenden. Aber die Blockchain-Methode zwingt Knoten im Wesentlichen dazu, auch vollständige Knoten zu sein, was interessant ist, also ist es ein Kompromiss.

Bearbeiten: Bei einer schnellen Suche bin ich auf dieses Papier gestoßen, das im Wesentlichen dasselbe Problem mit einer anderen stochastischen Stichprobenmethode löst, die das Geburtstagsparadoxon beinhaltet. Ihre Lösung ist interessant, weil sie jedes Mal den Aufbau eines eigenen großen Datensatzes beinhaltet. Dies ist jedoch möglicherweise keine gute Sache, da es den Wiederaufbau von Blöcken verhindert, wenn neue Transaktionen eingehen.

http://www.hashcash.org/papers/momentum.pdf

Eine relevante Bitcointalk-Diskussion zum Momentum-Algorithmus:

https://bitcointalk.org/index.php?topic=313479.0

Ich finde es lustig, wie der „Momentum“-Aspekt (Merkle nicht aktualisieren zu können, nachdem er zum ersten Mal erstellt wurde) als das definierende Merkmal des Algorithmus angepriesen wird, obwohl es eigentlich ein ziemlich bedeutender Nachteil ist, der die Bestätigung aller Transaktionen um 1 Block verzögert . Es kann auch das Problem verschärfen, dass Bergleute keine großen Blöcke abbauen wollen, weil sie lange brauchen, um sich zu verbreiten. Das heißt, es kann rentabler sein, mit Ihrem winzigen Block weiter zu schürfen, auch nachdem Sie von einem neuen Block im Netzwerk gehört haben, da die Dynamik, die Sie bereits haben, es einfacher macht. Ich denke, die Tatsache, dass der PoW-Algorithmus von Bitcoin keine Dynamik hat, ist eigentlich eine großartige Funktion, die es ermöglicht, Transaktionen schnell zu bestätigen.

Die Verwendung eines unveränderlichen Datensatzes, wie in der oben bereitgestellten Lösung, bietet die gewünschten asymmetrischen Speicheranforderungen beim Arbeiten/Verifizieren der Arbeit und vermeidet gleichzeitig das Problem der Dynamik.

Wenn das Mining auf Daten in der Blockchain basierte, könnte jemand Daten einfügen, die zufällig erscheinen, aber tatsächlich stark komprimierbar sind, wenn Sie einen geheimen Schlüssel kennen. Der zweite Ansatz scheint jedoch vernünftig zu sein.
@ NickODell, danke. Ich habe meinen Beitrag bearbeitet, vielleicht interessiert Sie auch der Momentum-Algorithmus.
Die Verwendung der Blockchain für Daten zwingt Miner zumindest dazu, ein vollständiger Knoten zu sein, das ist zumindest ein Vorteil, denke ich. Die Verwendung von 137 GB zufälliger Daten bedeutet, dass Sie nur darauf warten, dass jemand einen ASIC mit 137 GB RAM baut, und alle anderen sind am Arsch (so viel zum Widerstand ...).
@Jannes Wenn Sie einen ASIC mit 137 GB RAM bauen, warum machen Sie den RAM nicht extern, damit Sie ihn für weniger bekommen? Und wenn der Algorithmus weitgehend vom RAM abhängt, warum nicht den ASIC durch eine CPU ersetzen?
@NickODell, weil lokaler RAM immer schneller als externer RAM und ASIC immer schneller als CPU ist? Das ist der springende Punkt. Es macht keinen Sinn, PoW CPU/GPU-resistent zu machen, denn wenn es sich lohnt, wird jemand einen ASIC dafür machen. Weil ein ASIC im Grunde nur eine CPU + RAM ist, aus der alle unnötigen (allgemeinen) Dinge herausgeschnitten wurden. Um es schneller zu machen. Am Ende verbrennen Sie Watt ... das ist der springende Punkt. Die absolute Geschwindigkeit spielt keine Rolle (gleiche Watt), aber die Geschwindigkeit im Verhältnis zu anderen ist wichtig! Wenn Sie reich sein müssen, um in eine ASIC-Anlage zu investieren, erhalten Sie einen unfairen Vorteil -> Zentralisierung.
@NickODell, der ziftrCOIN-Algorithmus verwendet auch einen Algorithmus, der mehr Speicher zum Berechnen als zum Verifizieren benötigt, indem der Merkle-Baum direkt im Block als Merkle-Baum verwendet wird, den ich in meiner Antwort beschrieben habe. Der Vorteil besteht darin, dass Sie das Wissen über alle von Ihnen geschürften Daten nachweisen können, während nur eine der Transaktionen erforderlich ist, um zu beweisen, dass ein Header für einen SPV-Knoten gültig ist.
@NickODell, meine Antwort hat 3 verschiedene Möglichkeiten gezeigt, dies zu tun, erfüllen diese nicht Ihre Anforderungen?
@ StephenM347 Alle drei haben unterschiedliche Probleme 1) Jemand könnte zufällig aussehende Daten einfügen 2) Jemand könnte mehrere Miner parallel auf demselben Datensatz ausführen, 3) Hat die von Ihnen festgestellten Probleme. Sie alle sind gute Versuche, das Problem anzugehen, aber sie scheitern aus dem einen oder anderen Grund.
Würde eine einfache Zyklusfindung oder eine ausgezeichnete punktbasierte Kollisionssuche die Speicherkosten des Impulses nicht stark reduzieren, während die Rechenkosten nur um einen kleinen Faktor erhöht würden?

Dagger soll viel Speicher zum Erstellen, aber wenig zum Verifizieren benötigen.

Mein "Cuckoo Cycle" https://github.com/tromp/cuckoo ist ein speichergebundener graphentheoretischer Proof-of-Work, der trivial zu verifizieren ist und AFAIK der einzige ist, dessen Laufzeit von Speicherlatenz dominiert wird.

Ich dachte, dass dieser Algorithmus veraltet ist? github.com/tromp/cuckoo/issues/2
Nein; nur der ursprüngliche Mining-Algorithmus ist veraltet. Der neue, der die von Dave Andersen vorgeschlagene Kantenbeschneidung verwendet, hat sich bisher Angriffen widersetzt. Bitte lesen Sie die README und das Whitepaper für alle Details, einschließlich eines Vergleichs mit Momentum.
Gibt es ein Proof-of-Work-System, das wesentlich mehr Speicher zum Generieren als zum Verifizieren benötigt?
AntwortenHierDatenschutz-Bestimmungen1y, 0v