Eine kurze Geschichte der Entwicklung von Proof-of-Work in Kryptowährungen. Teil 2

Ursprünglicher Autor: Ray Patterson
  • Übersetzung
Ich mache Sie auf eine Übersetzung des Artikels „ The Proof-of-Work in Cryptocurrencies: Brief History. Teil 2 »Ray Patterson von Bytecoin.org .

„Eine kurze Geschichte der Entwicklung von Proof-of-Work in Kryptowährungen. Teil 1 “ist da .


Kreuzung


Bis Mitte Sommer 2013 waren bereits mehr als hundert Altmünzen in Betrieb, von denen fast die Hälfte in den letzten Monaten aufgetaucht ist. Unnötig zu erwähnen, dass fast alle "Neulinge" Litecoin-Gabeln waren und Scrypt verwendeten? Ein weiterer Trend der Saison war PPcoin's neuer Proof-of-Stake, weshalb die Kombination aus Scrypt + PoS als "Standardsatz für Anfänger" bezeichnet werden kann.

Diese (quantitative) Popularität der Verschlüsselung und der Beginn des exponentiellen Wachstums der Bitcoin-Komplexität führten zu einem einfachen Gedanken: Scrypt-ASICs erscheinen in der Sekunde, in der sie rentabel werden. Und obwohl sich die gigantische Novemberblase - als Bitcoin 1200 Dollar erreichte - noch nicht einmal aufgeblasen hatte, begann die Suche nach einer neuen PoW-Funktion erneut.

Wie kann ich die Standard-Hash-Funktion diversifizieren? Zum Beispiel ... eine andere Standard-Hash-Funktion!Sifcoin war der erste, der die Idee vorschlug, nacheinander mehrere populäre Funktionen zu übernehmen, deren Rolle die Finalisten des SHA3-Wettbewerbs übernahmen: Blake, BMW, Groestl, JH, Keccak, Skein. Die Idee ist ganz einfach: Sechs grundlegend verschiedene Algorithmen sind sechs verschiedene ASIC-Chips, das ist (auf den ersten Blick) viel und teuer. Wenn einige Algorithmen eine Hintertür finden (sie brechen nicht notwendigerweise das Ganze, sondern lernen, wie man das Problem mit den „vielen Nullen am Anfang“ schneller löst), bleibt das gesamte Schema mehr oder weniger erhalten.

Pioniere kriegen nicht immer alle Lorbeeren: Am Ende gewann dieser Sechs-Hash-Algorithmus an Popularität (und Namen) in der ersten Verzweigung von Sifcoin - der Quark-Währung. Fazit: Geben Sie Ihren Produkten nicht das Präfix "sif". Im Laufe der Zeit spalteten sich ein oder zwei Dutzend Altmünzen von Quark ab, von denen eine die Popularität des „Vaters“ bei weitem übertraf: Darkcoin (heute DASH ). Die neue PoW hieß X11 und unterschied sich, wie Sie sich vorstellen können, in der Anzahl der verwendeten Hash-Funktionen. Er gab nichts grundlegend Neues (außer der Reihenfolge der Runden), und daher sollte die Prävalenz von X11 (ungefähr auf dem zweiten Platz nach der Verschlüsselung) eher mit dem Erfolg von DarkCoin selbst in Verbindung gebracht werden, bei dem es viele andere Änderungen gab (etwas vernünftig, etwas) nicht sehr).

X11 erschien Anfang 2014 und funktionierte zunächst ausschließlich auf der CPU, was alle sehr freute. Im April verdoppelte sich die Komplexität von DarkCoin, was zu begründeten Vermutungen im Erscheinungsbild des GPU-Miners führte. Da niemand erkannte, wurde ein Wettbewerb für die offene Implementierung solcher Software ausgeschrieben, Geld gesammelt - und bereits einen Monat später war die Hashrate auf dem neuen GPU-Miner um eine Größenordnung gewachsen. Es stellte sich heraus, dass es ungefähr 5-mal effizienter als die CPU ist (10-maliges Verschlüsseln).

Bis heute gibt es viele Variationen des Themas X11 und Quark. Einige haben sogar ihre eigenen eindeutigen Namen: X14, X15 ... Gleichzeitig ist jedem klar, dass der Algorithmus im wahrsten Sinne des Wortes überhaupt nicht ASIC-resistent ist. 11 verschiedene Hashes anstelle von einem zu berechnen, bedeutet grob gesagt, die Pipeline um das 11-fache zu verlängern. Mit anderen Worten, die Preisschwelle für die Amortisation der Entwicklung eines Stück Eisens hat sich nur mehrmals verschoben.

Dank verschiedener Marketingtechniken wurden einzelne SHA-3-Finalisten in der Solo-Version populär. Zum Beispiel Keccak selbst, auch bekannt als SHA-3. Nun, hier ist alles klar: "Wie SHA-2, nur besser!". Das heißt, es gab keine spezielle Idee, ASICs zu konfrontieren, außer der Tatsache, dass die Entwicklung und der Start der Produktion mindestens ein Jahr dauert. Aber andererseits: Wir haben einen wirklich frischen, modernen Standard! Außerdem erschien sogar eine spezielle Skeincon-Münze, die anscheinend den Skein-Algorithmus verwendete (wahrscheinlich Fans von Bruce Schneier).

Artenvielfalt


Die Evolution machte eine Runde, und die Gedanken an Kryptowährungen kehrten wieder zu speichergebundenen Algorithmen zurück. Nehmen wir zum Beispiel die Verschlüsselung: Der Algorithmus ist gut, nur die schlechten Parameter!

Höchstwahrscheinlich wurden Überlegungen angestellt, da keine Kryptowährungen mit nur anderen statischen Verschlüsselungsparametern auftraten. Die Idee mit dynamischem Speicher wurde aber gleich in zwei Versionen umgesetzt:

  1. Scrypt-n. Erinnern Sie sich an die drei Verschlüsselungsparameter, die in Tenebrix und anderen Litecoin ausgewählt wurden: N = 1024, r = 1, p = 1. Letzterer ist für die Möglichkeit der Parallelisierung verantwortlich, wir brauchen dies nicht. N und r erhöhen die erforderliche Speichergröße und r erhöht auch die Anzahl der Aufrufe der Salsa20-Mischfunktion, d.h. In dieser Hinsicht wurde beschlossen, N periodisch zweimal zu erhöhen, wodurch der Algorithmus gezwungen wurde, nur mehr Speicher zu verwenden. Zum Start benötigt Vertcoin [9] 512 KB (N = 4096), nach einem Jahr steigt der Appetit auf 1024 KB usw. Den GPU-Miner neu zu schreiben, ist laut den Machern nichts, aber niemand wird jedes Jahr einen neuen ASIC erstellen.
  2. Scrypt-Jane. Die Idee, N zu erhöhen, ist immer noch dieselbe, aber der Prozess verläuft nicht nach einem bestimmten Zeitplan, sondern wird durch eine Pseudozufallsformel geregelt, die nicht linear von der aktuellen Zeit abhängt. Und obwohl N monoton zunimmt (in Ordnung, „nimmt nicht ab“), sind die Perioden zwischen den Nachzählungen eher divergierende Reihen (6,3, 3,9,3,24,12,36 ...). Darüber hinaus verwendet Scrypt-Jane mehrere Mischfunktionen (Salsa20 / 8, ChaCha20 / 8 und Salsa6420 / 8) und Hash-Funktionen (SHA2, BLAKE, Skein, Keccak) im Inneren.

Eine andere, grundlegend andere speichergebundene PoW-Funktion war die in BitShares implementierte Momentum- Funktion . Es ist sehr einfach:

  1. Angenommen, wir möchten Daten D signieren. Zuerst erhalten wir H = Hash (D), wobei Hash () eine kryptografische Hash-Funktion ist
  2. Finden Sie so unterschiedliche Werte von A und B, dass BirthdayHash (A + H) = BirthdayHash (B + H) ist, wobei BirthdayHash () eine speichergebundene Funktion wie scrypt ist.
  3. Wenn nun Hash (H + A + B) <Zielschwierigkeit (lesen - es beginnt mit n Nullen), dann ist es das, Sieg. Ansonsten kehren wir zu Schritt 2 zurück.

Wie Sie sehen, besteht die Hauptarbeit darin, in Schritt 2 nach Kollisionen von zwei Hashes zu suchen. Natürlich müssen Sie dort nicht 256 passende Bits, sondern weniger finden, aber dies ist auch eine schwierige Aufgabe. Wenn Sie also eine Übereinstimmung der ersten 64 Bits finden müssen, sind 2 ^ 64-Hash-Operationen erforderlich ... Oder nicht?

Ein Superheld hilft uns: das Paradoxon der Geburtstage . Sein Wesen ist, dass die Wahrscheinlichkeit, eine Kollision unter einer bestimmten Menge zu finden, quadratisch mit der Anzahl der Elemente zunimmt (weil die Anzahl der eindeutigen Paare unter der Menge ebenfalls so zunimmt). In der Praxis ergibt sich daraus die folgende Einschätzung: Um eine 64-Bit-Kollision mit einer Wahrscheinlichkeit von 50% zu finden, müssen etwa 2 ^ 32 Hashes generiert werden (4 Milliarden statt 18 Billionen - das ist eine solche Einsparung).

Warum funktioniert es nicht mit "normalem" PoW, weil auch dort im Wesentlichen nach Kollisionen gesucht wird? Das Schlüsselwort hier ist "jeder" Konflikt. In Bitcoin müssen Sie eine Übereinstimmung mit einem bestimmten Muster finden: N Nullen am Anfang und in Momentum N müssen alle ersten Bits übereinstimmen.

Es gibt einen offensichtlichen Kompromiss zwischen Zeit und Gedächtnis. Nach Angaben des Erstellers sollte der Algorithmus etwa 2 GB Speicher pro Thread verwenden, d. H. Ein gewöhnlicher Computer kann sogar mehrere parallele Suchvorgänge durchführen. Gleichzeitig bleibt das Schicksal von ASICs, an dessen Stärke man sich nicht erinnern kann, nur zu schauen und zu beneiden (oder schneller zu sein).

Dieser Ansatz hat einen Nachteil. Alle bisherigen Proof-of-Work-Algorithmen arbeiteten "sofort". in dem Sinne, dass sie tatsächlich pleite gingen und jeder Versuch eine festgelegte Zeit in Anspruch nahm und sie alle die gleichen Erfolgschancen hatten. Jeder verifizierte Hash ist wie das Werfen eines Würfels mit 2ˆ256 Gesichtern. Sie können jederzeit einen weiteren Würfel nehmen (mit der Arbeit an einem anderen Block beginnen), und die Chancen ändern sich nicht. Was bedeutet das für den Bergmann? Dies bedeutet, dass er, wenn er eine neue Transaktion erhält, die er in den Block aufnehmen möchte, die Hash-Struktur aktualisieren muss ("take another cube"). Dies dauert einen Bruchteil einer Sekunde, so dass gesagt werden kann, dass die Verluste vernachlässigbar sind. Bei Momentum ist alles nicht so einfach. Die nächste Iteration des Hashens und das Hinzufügen eines neuen Hashs zur globalen 2-GB-Tabelle hat bessere Erfolgschancen als die vorherige! Es ist klar Das anschließende Aktualisieren des Block-Headers und der Beginn des Neuaufbaus der Tabelle ist sehr nachteilig. Wenn sich mit jedem Würfelwurf die Chancen erhöhen, eine Lösung zu finden, ist es rentabler, KEINEN neuen Würfel zu nehmen. Das heißt, dass es für den Momentum Miner nicht rentabel ist, neue Transaktionen anzunehmen und ihren Fortschritt zu "sichern". Letztendlich fallen die Transaktionen, die gesendet wurden, bevor Sie mit diesem Block arbeiten, in den Block. Für Bitokin würde dies bedeuten, dass sich die durchschnittliche Transaktionsbestätigungszeit von 10 Minuten auf 20 Minuten erhöht. die gesendet wurden, BEVOR Sie mit diesem Gerät arbeiten. Für Bitokin würde dies bedeuten, dass sich die durchschnittliche Transaktionsbestätigungszeit von 10 Minuten auf 20 Minuten erhöht. die gesendet wurden, BEVOR Sie mit diesem Gerät arbeiten. Für Bitokin würde dies bedeuten, dass sich die durchschnittliche Transaktionsbestätigungszeit von 10 Minuten auf 20 Minuten erhöht.

Mineralien


Apart ist die einzige PoW-Funktion, die im Sommer 2013 aufgetaucht ist. Bevor wir fortfahren, wollen wir ein allgemeines Problem mit dem Proof-of-Work erkennen. Ich werde sofort reservieren, dass dies für niemanden ein Problem darstellt (oder sogar umgekehrt), d. H. Es geht darum, was viele Leute für ein Problem halten.

All diese Arbeit ist nutzlos! Außer in der Kryptowährung benötigt niemand diese Hashes. Sie können natürlich den kleinsten der gefundenen Hashes drucken und an die Wand hängen , aber sie haben keinen praktischen Nutzen. Wir werden keine philosophischen Diskussionen darüber führen, ob diese Arbeit nützlich sein sollte oder nicht, sondern nur die Tatsache, dass es keine triviale Aufgabe ist, eine nützliche PoW-Funktion zu entwickeln.

Es wurde jedoch einer gefunden. Der Entwickler von SunnyKing (er hat das Proof-of-Stake-Schema erfunden (oder zumindest als erster implementiert)) stellte der Öffentlichkeit das folgende Schema vor: Der Beweis für die geleistete Arbeit ist die gefundene Kette von Primzahlen, die einige Eigenschaften erfüllen. Genauer gesagt sollte es sich um eine Cunningham-Sequenz der ersten oder zweiten Art oder eine Kombination davon handeln (die sogenannten Bi-Twin-Primzahlen ).

Der erste Grund ist, warum dies nützlich ist. Diese Primzahlen sind natürlich nicht klein (sonst wäre es ziemlich einfach, sie zu finden): in der Größenordnung von Hunderten von Ziffern in Dezimalschreibweise. Für die RSA-Verschlüsselung reicht dies jedoch noch nicht aus, Sie müssen dort jedoch Zufallszahlen verwenden. Cunningham-Ketten sind eher eine merkwürdige mathematische Struktur, die (theoretisch) den nächsten Vorhang in der Zahlentheorie öffnen kann. Letztendlich galt dieser gesamte Bereich bis zum Aufkommen der Kryptografie mit öffentlichen Schlüsseln nur als „schöne, nutzlose Wissenschaft“, sodass jegliche Bemühungen, auch wenn sie eine solche „Olympiade“ darstellen, als wertlos gelten.

Nun erfahren Sie, wie genau Sie Primzahlen mit Kryptowährungsblöcken verknüpfen können. Angenommen, unsere Kette beginnt mit einer Zahl P. Der Hash des Blockheaders (in dem das Nonce-Feld aufgezählt ist) wird als Ganzzahl interpretiert. Und diese Zahl sollte ein Teiler von P-1 oder P + 1 sein. Die Komplexität des Netzwerks ist die Länge der erforderlichen Kette von Primzahlen (sie reicht von 7 bis 11). Das ist im Allgemeinen die ganze Idee. Daher ist es unmöglich (d. H. Sehr schwierig), eine zufällig gefundene Kette (oder sogar die einer anderen Person aus einem anderen Block) zu verwenden, um die Arbeit an Ihrem eigenen Header zu beweisen.

Es gibt zwei Nachteile: Erstens wissen wir nicht, ob es einen einfacheren Weg gibt, das Primecoin-Problem zu lösen (diese Kryptowährung wird genannt). Mit Hashes ist alles mehr oder weniger klar: Ein Angriff, um den Prototyp einer kryptografischen Hash-Funktion zu finden, ist nahezu hoffnungslos (zumindest basieren alle kryptografischen Säulen auf dieser Annahme - und Gott bewahre, dass sie zusammenbrechen!). Dasselbe über den Primecoin-Block zu sagen (wo alle P-1- oder P + 1-Faktoren für uns geeignet sind), ist bereits schwierig.

Zweitens die Komplexität des Bergbaus. Wie bereits erwähnt, ist es proportional zur Länge der Kette. Die Länge ist jedoch eine ganze Zahl und berücksichtigt nicht die Änderung des Bruchteils. Eine Änderung der Komplexität von 9.0 auf 9.99 ist somit völlig unsichtbar, wirkt sich jedoch von 9.99 auf 10 bereits drastisch auf die Gesamt-Hash-Rate und die Geschwindigkeit des Auftretens neuer Blöcke aus.

Darüber hinaus verwendet diese Funktion offensichtlich nur die CPU-Leistung des Computers, keinen Speicher. Lange Zeit hatte sie keinen GPU-Bergmann, aber als er auftauchte, wurde klar, dass Primecoin kein Anti-ASIC-Gral ist. Vielleicht blieb er deshalb mit ein paar Gabeln in seiner Nische, und seine PoW-Funktion wurde nicht populär.

Power Sapience


Und schließlich betrachten wir einen völlig anderen Zweig des phylogenetischen PoW-Baums für Kryptowährungen: CryptoNight und CuckooCycle , die sich unmittelbar nach dem Versagen der Verschlüsselung parallel zu den anderen zu entwickeln begannen, als reinen CPU-Algorithmus.


CryptoNight ist der Name der Hash-Funktion im CryptoNote-Code (nicht verwechseln!), Der viele andere Unterschiede zu Bitcoin enthält (ausgehend von der Tatsache, dass dies überhaupt keine Verzweigung ist - obwohl Sie jetzt niemanden damit überraschen werden). Es gibt keine CryptoNote-Kryptowährung als solche, aber es gibt einige, die auf dieser Technologie aufbauen: Bytecoin, Monero, DigitalNote usw. ... Jeder, wenn er seine eigenen Unterschiede hat, aber die PoW-Funktion ist für alle gleich.

CryptoNight verwendet die allgemeine Idee der Verschlüsselung "einer großen Datentabelle, in der zufällige Abfragen vorgenommen werden". Die Erfinder stellten jedoch einen Nachteil fest, der mit dem linearen Kompromiss "Zeit" - "Gedächtnis" verbunden ist. Bei der Verschlüsselung erstellt die Hauptschicht (zweite Schicht) jeden neuen Datenblock auf der Grundlage des vorherigen Datenblocks. Wenn wir beispielsweise nur jeden zweiten Block von N speichern, müssen wir ihn in 50% der Fälle erneut zählen. Es gibt N solche zufälligen Zugriffe auf das Array, so dass sich herausstellt, dass wir, nachdem wir die Hälfte des Speichers eingespart haben, N + 1 / 2N = 150% der Blöcke berechnen, dh nur das Eineinhalbfache. Wenn wir nur jeden dritten Block behalten, werden wir dies in 33% der Fälle nicht bemerken, in 33% - wir werden einen zusätzlichen Block neu berechnen, in 33% - zwei zusätzliche. Das heißt, die gesamte Arbeit: N + 1 / 3N + 1/3 * 2N = 2N = 200%. Gesamt, wie berechnetWenn Sie nur 1 / s aller Daten speichern, erhöht sich der Arbeitsaufwand nur (s-1) / 2-mal (möglicherweise ist dies übrigens genau das, was Scrypt-ASICs tun).

In dieser Hinsicht weist CryptoNight drei grundlegende Unterschiede auf:

  1. Der nächste Block wird basierend auf ALLEN vorherigen berechnet. Das Auswerfen von beispielsweise jedem zweiten Block führt dazu, dass zum Wiederherstellen des Durchlaufs nicht ein Block, sondern alle vorherigen Blöcke gleichzeitig neu gezählt werden müssen.
  2. Zugriffe auf das Datenarray werden nicht nur gelesen, sondern auch geschrieben. Es stellt sich also heraus, dass für jedes Element eine „zweite Dimension“ erscheint - die Zeit; und das Nachzählen wird noch zeitaufwändiger.
  3. Schließlich ist die Gesamtzahl der Aufrufe des Arrays viel größer als die Anzahl der Elemente im Array (2 ^ 20 gegenüber 2 ^ 15), dh das resultierende Array wird am Ende des Zyklus bis zur Unkenntlichkeit transformiert.

Zusätzlich werden intern 64-Bit-Operationen (Multiplikation, Addition) und AES-Verschlüsselung als Mischfunktion verwendet. Dies ist ein Knicks in Richtung moderner Prozessoren mit eingebauten relevanten Anweisungen (und einem Stein im GPU-Garten). Der von CryptoNight benötigte Gesamtspeicher beträgt 2 MB, d. H. ungefähr so ​​groß wie der L3-Cache pro Kern. Um nicht zu sagen, dass dies eine unerreichbare Höhe für den ASIC ist, aber dennoch ist die Kostengrenze ziemlich hoch.

Im Allgemeinen kann CryptoNight als sehr effektiver praktischer Algorithmus charakterisiert werden: Es gibt natürlich einen GPU-Miner dafür, aber er hat nur im Vergleich zu alten Prozessoren (32 Bit oder kleiner Cache) einen ernsthaften Vorteil. Soweit man beurteilen kann, zielen alle Details genau auf die praktische Wirksamkeit herkömmlicher Computer (von denen es Milliarden gibt).

CuckooCycle ist genau das Gegenteil. Erstens hat es eine theoretische Informationsbasis. Nicht in dem Sinne, dass es nur theoretisch entwickelt wurde (im Moment gibt es keine solchen Kryptowährungen), sondern in der Tatsache, dass seine Zuverlässigkeit auf der Komplexität der Lösung des informationstheoretischen Problems beruht: der Suche nach Zyklen in einem zweigliedrigen Graphen. Grundsätzlich ist jede moderne Kryptographie mit öffentlichen Schlüsseln gleich aufgebaut.
Die Hauptidee (wenn Sie nicht auf die Graphentheorie selbst eingehen) ist dieselbe wie in Momentum - durch die Verwendung einer bestimmten Menge an Speicher erhalten wir den optimalen Algorithmus zur Lösung dieses Problems. Rechenoperationen werden minimiert, daher dauert der Zugriff auf diesen Speicher die Hauptzeit. Darüber hinaus ist die Überprüfung der Lösung natürlich viel schneller.

Hauptfrage, was sich fragen lässt: Ist der beschriebene Algorithmus wirklich optimal? Gibt es morgen einen kniffligen CS-Artikel mit einer anderen, effizienteren Lösung, die nicht viel Speicher benötigt? Grundsätzlich ist dies die Hauptsache, die CuckooCycle und CryptoNight unterscheidet.

Jetzt auch beliebt: