An welchen stellen gibt es Probleme bei gleichen Hashes in der Blockchain?

Diskussionen
,
1

Huhu Liebe Bitcoiner,

ich hab einmal eine Frage bezüglich Eindeutigkeit von Hashes.
Hashes sind bekannt dafür, aus einem Eingangsfolge deterministisch eine zufällig aussehenden Ausgangsfolge zu generieren. Dabei kann man mithilfe des Hashalgorithmus (da deterministisch) und einer Eignagnssequenz leicht den Ausgangswert bestimmen, andersherrum aber nicht. Damit liefert dieser Algorithmus ein asynchrone Schwierigkeit (Wie das Primzahlenproblem, die Multiplikation zweier Primzahlen geht einfache aber nur aus der Information dieser Zahl wieder die Priemzahlen zu bestimmen ist extrem aufwändig.)
Die Ausgangssequenz ist festgelegt auf eine feste Anzahl von Bits währen die Eingangssequenz beliebig lang sein darf.
Allein aus der letzten Eigenschaft lässt sich schnell herleiten, dass es mehrere Eingangssequenzen geben muss die die gleichen Ausgangwerte haben.

In der Blockchaintechnologie (Ich rede hier von der Konvention wie sie in Bitcoin verwendet wird) werden an vielen Stellen Hashes verwendet. Auch wenn es sehr unwahrscheinlich ist, an welchen Stellen im Bitcoin-Konzept kann es Probleme bei zwei Hashes geben, die exakt gleich sind?

Generell (ohne die genaue Implementierung zu kennen) würde ich sagen, dass es nur Probleme bei Hashes gibt, die den selben Use-Case haben. Der Merkletree-Hash sollte in meinen Augen also unabhängig vom Mining-Hash sein. Eine Gleichheit würde hier also nie problematisch werden da diese Hashes nie im gleichen Kontext auftreten. (Analysetools könnten Probleme bekommen aber ich würde mich mit den Überlegungen erstmal nur auf Bitcoin selber beschränken.)

Mining Hashes

Gibt es Probleme, wenn zwei Blockheader gehasht den gleichen wert ergeben? Intuitiv würde ich sagen nein, da dieser Hash lediglich beweisen soll, dass er unterhalb der Difficulty liegt. Die Blöcke sind auf ihren jeweiligen Vorgänger gelinkt und nehmen unabhängig ihres Hashes immer ihren festen Platz in der Blockchain ein.

Merkletree Hash

Hier kenne ich mich nicht mehr so gut aus. Ich würde sagen, dass wenn zwei Blöcke den selbem Merkletree Hash teilen, dann kann nicht mehr ganz klar zwischen den Payloads der beiden Blöcke unterschieden werden. Wenn ich vom Header ausgehe und den Merkletree suche, dann finde ich zwei Versionen mit jeweils unterschiedlichem Inhalt. Könnte das dazu führen einen Block aus der Vergangenheit zu überschreiben, nur weil ein neu geminter Block einen Merkletree Hash hat, der irgendwann schoneinmal benutzt wurde? Die Chance dafür steigt ja mit jedem Block an.

weitere Hashes
Innerhalb des Merkletrees gibt es ja auch jede Menge Hashes, aber ich würde sagen hier gibt es weniger Probleme. Alleine wenn man sich vorstellt, dass in zwei Bäumen exakt die gleichen Informationen gespeichert sind, dann gleichen sich deren Hashes natürlicher weise. Und Hashes unterschiedlicher Merkletrees werden nicht miteinander in Bezeihung gesetzt, da sie nichts miteinander zu tun haben.

Gibt es noch weitere Anwendungen der Hashes in Bitcoin? Speziell mit Wallets hab ich mich noch nicht so auseinander gesetzt.

2

Das ist in der Theorie natürlich absolut richtig. Das ist das Pigeonhole principle. Wenn du unendlich viele Tauben auf 2256 Höhlen verteilen willst wird es Kollisionen geben.

Bei unterschiedlichen Block Headern meinst du. Das kann nicht funktionieren, jeder Block muss einen einzigartigen Header haben. Du könntest die beiden Blöcke ansonsten beliebig austauschen.

Ich weiß aber nicht ob das in den Regeln verankert ist…

Es ist aber auch ein Problem für den Algorithmus. SHA-256 wäre dann nicht mehr Kollisionsresistent und es ist evtl. möglich das ganze Verfahren zu brechen oder zumindest soweit zu verstehen dass man manipulieren kann.

In der Praxix ist eine solche Kollission durch Zufall, was du ja hier beschreibst, extrem unrealistisch. Wer sich über sowas ernsthafte Sorgen hat, der hat die Bedeutung dieser Zahl nicht verstanden. :slight_smile:

Guter Thread hier im Forum dazu:

Und kann man auch in diversen Threads auf Stackoverflow lesen:

Man muss hier auch zwischen Second pre-image resistance und Collision resistance unterscheiden. Bei letzterer finde ich eine Kollision für irgendwelche Inputs.

Nur aufs Bitcoin Mining bezogen ist die Second pre-image resistance die relevante Eigenschaft. Hier geht es darum zu einem gegebenen Input (ein existierender Block) eine Kollision zu finden. Das ist nochmal unwahrscheinlicher und deshalb auch die „schwächere“ Eigenschaft einer kryptographischen Hashfunktion.

Ja, jede Bitcoin Adresse ist z.B. durch RIPEMD-160 (und SHA-256) gelaufen (und wird anschließend codiert).

Das steckt auch im Namen der Adresstypen drin. P2PKH (Legacy Adressen) ist eine Abkürzung für Pay to Public Key Hash, P2SH ist die Abkürzung für Pay to Script Hash, und so weiter.

Auch beim Derivieren des Seeds und der Schlüssel kommen HMACs und damit auch Hashfunktionen wie SHA-512 und SHA-256 zum Einsatz.

Ja, auch das wäre ein Problem.

4 „Gefällt mir“
3

Ok, es ist sehr unwahrscheinlich, dass es Hashkollisionen gibt aber nicht ausgeschlossen. Und im Gegensatz zu doppelten Wallets, wo dann lediglich zwei Personen den gleichen Privaten Schlüssel hätten kann eine Kollision in dem Header (Merkletree) die Blockchain zerstören.

Ich werde mir morgen mal genauer die Wahrscheinlichkeiten für sha256 herleiten. Vielen Dank für deine Links.

4

Das habe ich nicht gesagt! :smiley:

Sollte SHA-256 gebrochen werden ist das nicht der Tod für das Bitcoin Netzwerk. Es wäre zwar sehr ungemütlich für die Miner, aber vereinfacht gesagt könnte man SHA-256 einfach „raus forken“ und z.B. durch SHA-512 ersetzen. Nach dem Motto: „In 100 Blöcken geht’s mit SHA-512 weiter, bitte bleiben sie angeschnallt“.

Es ist nicht möglich vergangene Blöcke bei gebrochenem SHA-256 zu verändern!

Und davon abgesehen: Wenn SHA-256 gebrochen wird haben wir ganz andere Probleme. Die ganze Welt verwendet diesen Algorithmus, nicht nur das Bitcoin Netzwerk.

Und zum Thema doppelter Block:

  • Ein Block mit gleichem Block Hash würde das Netzwerk ignorieren. Außerdem kämen auch nur relativ junge Blöcke für eine Kollision in Frage, da ansonsten die Difficulty sowieso nicht stimmen würde. Und wie gesagt: Das ist unfassbar unwahrscheinlich.

  • Die Sache mit der Kollision im Merkletree der Transaktionen. Ich muss korrigieren von oben: Das wäre kein Problem! Die Transaktionen aus dem neuen Block wären im alten Block nicht gültig und damit wäre der Block (an alter Blockhöhe) auch ungültig und könnte nicht einfach ausgetauscht werden.

Ich sehe Bitcoin als Netzwerk jedenfalls in keinem dieser Szenarien nachhaltig gefährdet.

1 „Gefällt mir“
5

Interessiert mich auch. Wäre interessant die Wahrscheinlichkeit für einen solchen Zufall in den nächsten 100 Jahren zu kennen.

6

Was definierst du als gebrochenen Sha256?
Mir geht es nicht um irgendein Angriff sondern nur wass passiert, wenn zufälligerweise auf zwei unterschiedliche Eingaben des Sha256 die gleiche Ausgabe erfolgt. So wie ich das sehe ist der Hash damit nicht gebrochen weil das durchaus vorkommen kann, mit höherer Länge nur eben unwahrscheinlicher aber nicht unmöglich. Einfaches Beispiel: Der hash spuckt nur 2 Ziffern aus (Vorstellbar indem man vom sha-algorithmus nur die ersten beiden hexzeichen nimmt. Dann hätten wir einen Wertebereich von 256 Zahlen) Bit diesem Beispiel ist man schon in Bereiche des Geburtstagsparadoxon angekommen, wo es eine signifikannte Chance gibt, dass in einer zufällig ausgewählten Gruppe zwei Leute am gleiche Tag Geburtstag haben. Um das zu verhindern nimmt man längere ausgaben aber Kollisionen sind immer mathematisch möglich.

Ansonsten geb ich dir natürlich Recht, vergangene Blöcke sind fest und durch ihre Hashes gegen Veränderungen geschützt. Fürs Mining und der Difficulty sehe ich wie gesagt auch keine Probleme, da der Hash nur beweisen muss unter einer Schranke zu liegen. Ob da der Blockheader 3957 und der Blockheader 295760 den gleichen Hashwert besitzen ist relativ unwichtig.

Nur was passiert wenn zwei Merkle-Trees existieren, die den gleichen Root-Hash haben, welcher ja als Verweis auf dem jeweiligen Payload im Header steht? Dann kann es sein, das es zwei unterschiedliche Blöcke gibt, die jeweils den gleichen Merkle-Tree-Root-Hash im Header stehen haben.

Ja angesichts des hohen Grades an Unwarscheinlichkeit ist das wohl eine ehr theoretische Frage aber auch Grenzfälle können eintreten und sollten vom guten Code abgefangen werden können.

1 „Gefällt mir“
7

Mathematisch kann man das untersuchen der Kollisionen von Hashes als ein Zufallsexperiment ansehen. Wenn man davon ausgeht, dass jeder Hash mit der gleichen Wahrscheinlichkeit auftreten kann, dann ist dies ein als ob man eine zufällige Kugel, die alle unterschiedlich sind (zB. durchnummeriert), aus einer Urne zieht, nachschaut und sich merkt was man gezogen hat und diese Kugel wieder zurück legt.

Der Einfachheit sag ich einfach mal: Jedesmal wenn wir eine Kugel aus der Urne ziehen, dann malen wir die weiße Kugel rot an und packen sie wieder in die Urne. Es wird immer so gut gemischt dass auch wirklich zufällig eine Kugel gewählt wird.

Wenn man nun weiß, dass N Kugeln in der Urne liegen, dann kann man beim ersten ziehen davon ausgehen, dass man keine Kugel schonmal gezogen hat. Jede Kugel ist weiß. Beim zweiten ziehen kann man alle Kugeln ziehen außer die eine Rote, also N-1 Möglichkeiten. Beim dritten Zug sind schon 2 rote Kugeln und N-2 Weiße usw.

Da wir davon ausgehen dass jede Kugel mit der gleichen Wahrscheinlichkeit 1/N gezogen werden kann haben wir beim ersten ziehen die Wahrscheinlichkeit von 0/N=0 eine Rote kugel zu ziehen. Beim zweiten Zug genau 1/N und beim dritten Zug 2/N,… Wir können in diesen Einzelexperimenten (Zügen) die Wahrscheinlichkeiten des Ziehens einzelner Kugeln aufaddieren und weil sie alle gleichwahrscheinlich sind macht dies das Zählen sehr viel einfacher.

Für die Kollisionsberechnung führen wir diese Züge also solange hintereinander aus bis wir mal eine rote Kugel ziehen, welche wir ja schonmal irgendwann gezogen haben. Wir haben also solange „Pech“ und ziehen eine Weiße bis wir nach wenigstens N Zügen zwangsweise eine Rote ziehen müssen, da alle Kugeln Rot sind.

Die Wahrscheinlichkeit eine weiße Kugel zu ziehen ist also (1-0/N) * (1-1/N) * (1-2/N) * (1-3/N) * … bis wir eine Rote Kugel ziehen. Hier müssen wir die Wahrscheinlichkeiten multiplizieren weil wir mehrere Experimente hintereinander ausführen die sich jeweils Bedingen. Unter der Annahme, dass wir beim vorhergegangenen Ziehen eine Weiße Kugel hatten ziehen wir im nächsten eine Kugel mit geänderten Wahrscheinlichkeiten. Außerdem benutzen wir hier das Gegenereignis, also die Chance eine Weiße zu ziehen ist genau 1-(Chance für Rote) und umgekehrt. (Chance für Rote + Chance für Weiße = 1 für jeden individuellen Zug)

Die Wahrscheinlichkeit einer Kollision ist also eine Multiplikationsreihe der Wahrscheinlichkeiten nach n Zügen aus der Grundgesamtheit N immernoch nur weiße Kugeln gezogen zu haben. Auch hier benutzen wir die Gegenwahrscheinlichkeit, da das Ereignis, dass wir nur weiße Kugeln haben wollen ja genau keiner Kollision entspricht. Das Gegenereignis ist: es gab eine Kollision.
P(kol) =1 - Π (1-i/N) = w(n,N)
Das Produkt läuft von i = 0 … n

Da mir auf die Schnelle nichts einfällt, wie man diesen Term für große N vereinfacht hab ich mir mal ein schnelles Javaproramm geschrieben, welches das mit BigDecimal durchrechnet.

Erste Zahl ist i, also wie oft gezogen wurde und die zweite Zahl ist die kumulative Wahrscheinlichkeit keine Rote Kugel gezogen zu haben.

1E0   8.6361E-78
1E1   4.7498E-76
1E2   4.3612E-74
1E3   4.3224E-72
1E4   4.3185E-70
1E5   4.3181E-68
1E6   4.3180E-66
1E7   4.3180E-64
1E8   4.3180E-62

...
    private boolean forcestop;//mit false wird die Zeitschleife unterbrochen
    private final int LOOPTIME;//wie lange wird nach einem Tick gewartet

    public final static MathContext MCTX = new MathContext(150);

    public kollisionscheck(int looptime){
        LOOPTIME = looptime;
    }
    public void run(){
        forcestop = true;
        BigDecimal P = BigDecimal.ONE; // die kummulative Wahrscheinlichkeit
        BigDecimal N = new BigDecimal("2").pow(256,MCTX);
        System.out.println(N);
        long i = 0; // die Laufzahl, welches Produkt wir gerade berechnnen
        BigDecimal p;
        while(forcestop) {
            p = BigDecimal.ONE.subtract(new BigDecimal(i).divide(N,MCTX),MCTX);
            P = P.multiply(p,MCTX);
            System.out.println(i + " "+ BigDecimal.ONE.subtract(P,MCTX));
            i++;
            try {
                Thread.sleep(LOOPTIME);
            } catch (InterruptedException e) {
                return;
            }
        }
    }

Man erkennt, dass die Kollisionschance exponentiell zunimmt. Mit jeder Zehnerpotenz der Versuchsanzahl nimmt die Chance zwei Zehnerpotenzen zu. Extrapoliert man diese Rechnung so weiter, dann kommt es nach 1E38 Versuchen zu einer signifikanten Wahrscheinlichkeit, dass es eine Kollision gibt.

Für die Frage, wie es in 100 Jahren aussehen wird:
Bezogen auf unsere Blockanzahl sind wir gerade beim Versuch 7,3E5 wir haben also noch genug Zehnerpotenzen vor uns. Wenn alle 10 Minuten ein neuer Block dazukommt, dann sind das 6 pro Stunde oder 144 pro Tag oder 5,2E4 pro Jahr. in 100 Jahren währen wir also ungefähr bei Block Nr. 5,2E6. Schaut man in der Tabelle oben nach, dann hat man immernoch eine Kollisionswahrscheinlichkeit von 4E-67 also eine Zahl mit 67 führenden Nullen. Das ist sehr unwahrscheinlich.

1 „Gefällt mir“
8

Sorry, habe von gefundener Kollision direkt übergeleitet dass der ganze Algorithmus kaputt ist. In der Realität wäre eine Kollision nicht sofort der Weltuntergang.

Das Bitcoin Netzwerk würde wahrscheinlich so oder so relativ schnell auf SHA-512 oder SHA-384 umsteigen. Kollisionen im Mining Prozess würden zwar nichts kaputt machen, sind aber dennoch ein Störfaktor.

Habe ich ja geschrieben oben, wieso sollte das ein Problem sein? :slight_smile:

Angenommen ich finde einen gültigen Block A der zufälligerweise die gleiche Merkle root wie Block B hat. Du siehst jetzt die Gefahr dass man den Inhalt, also die Transaktionen, aus Block A nehmen, und in den alten Block B mit der gleichen Merkle root einpflanzen könnte. Damit wären die Transaktionen der beiden Blöcke nicht mehr klar zuzuordnen.

Transaktionen werden aber sowieso einzeln verifiziert. Die Transaktionen aus Block A wären auf Blockhöhe B nicht gültig bzw. bei 3000 Transaktionen steht die Wahrscheinlichtkeit extrem hoch dass es irgendeine Kollision mit dem UTXO Set der jeweiligen Blockhöhe gibt.

Treiben wir es auf die Spitze:

Wenn Block B sehr jung ist und zufälligerweise sind alle Transaktionen aus Block A auf Höhe B gültig und zufälligerweise findet man genau zu diesem Block eine Kollision in der Merkle root. Selbst dann ist es kein Problem, denn jede Transaktion führt den Timestamp des eigenen Blockes mit sich. Eine Transaktion mit Timestamp die nicht mit dem Block übereinstimmt ist ungültig.

Also selbst dieses unfassbar unwahrscheinliche Ereignis wird abgefangen.

Der Block Hash wäre in diesem Szenario sowieso ein anderer, aber nochmal: Eine Kollision im Block Hash wird vom Netzwerk ignoriert. Eine Node würde diesen Block nicht anfragen weil er bereits im inventory vector steht.

Hier nicht vergessen: Irgendwann haben wir keinen Speicher mehr und wissen nicht ob wir Kollisionen finden.

Beispiel: Wir suchen 2128 Hashwerte ab (das sind deine 1038). Würden wir diese Hashwerte einfach abspeichern wollen, bräuchten wir mehrere Exabyte an Speicher.

Für einen Kollisionsangriff gibt es natürlich effizientere Speichermöglichkeiten, aber im Kontext des Bitcoin Minings bei dem zufällig Kollisionen gefunden werden nicht. Aber da haben wir sowieso nur eine Handvoll Kollisionskandidaten…

Aber danke für die coole Rechnung!

Aus welcher Ecke kommst du dass du sowas freiwillig mit Java machst? :grin:

9

Danke für die Erklärung! Ja damit würde ich dir recht geben dass zufällige Kollisionen kein großen Problem für das Bitcoin-Netzwerk darstellen.

Ich habe Physik studiert. Allerdings habe ich schon so viele Programmiersprachen durch, dass ich mir nie die Syntax von einer merke. Ich denke den Algorithmus und google mir die Syntax zusammen :innocent:

Java ist es nur geworden weil ich weiß wie man damit beliebig große Dezimalzahlen darstellen kann. Einfache doubles helfen da nicht unbedingt weiter bzw können schnell eine grobe Fehlerquelle sein. Ich hatte hier noch Android studio rumliegen, wo ich letztes Jahr mal versucht habe den Sha-Algorithmus reverse zu engenieren.
Dabei hab ich den Sha256 so nachprogramiert, dass als inputbits 0, 1 oder a angegeben werden. Wenn nur 0 oder 1 eingegeben wurden gab es keine Probleme, und der Hash stimmte. gab es nur eine Bitvariable im Inputstring, dann hab ich ein Gleichungssystem erhalten, dass wenigstens 80 GB groß war :sweat_smile:

Das war trotsdem eine sehr lehrreiche Erfahrung. Zb. wie man alle möglichen Rechenoperationen auf Bitebene durchführt und dass es sich immer in ein Gleichungssystem umschreiben lässt, dessen Variablen nur 0 oder 1 sein können und die mit den Rechenoperationen UND, ODER, NOT usw verknüpft sind,…

1 „Gefällt mir“
10

:ok_hand: :kissing_heart:

11

Ich weiß nicht ob du meinen Beitrag angesehen hast, den @sutterseba dir oben verlinkt hat. Dort habe ich diese Rechnung bereits durchgeführt und auch eine Näherungsformel angegeben, die bei den von uns verwendeten Zahlen praktisch exakt ist.

Ein Weg diese herzuleiten ist folgender:

Du berechnest den natürlichen Logarithmus deines Produktterms, so dass dieser zu einer Summe wird. Anschließend entwickelst du die einzelnen ln-Summanden bis zur ersten Ordnung und fasst diese über dem gemeinsamen Nenner zusammen. Das Ergebnis ist dann Exponent der e-Funktion und du erhältst die von mir angegebene Formel:

P_{Kollision} \approx 1 - \text{e}^{-\frac{h^{2}}{2N}} = 1 - \text{e}^{-\frac{1}{2}(\frac{h}{\sqrt{N}})^{2}}

h : Anzahl der Hash-Versuche
N : Anzahl der Hash-Möglichkeiten

In dem verlinkten Beitrag sind auch Beispielwerte angegeben.

2 „Gefällt mir“
12

Ach der Logarithmus hat mir gefehlt, ja damit passt alles zusammen :rofl:

2 „Gefällt mir“
13

Aber würde man das überhaupt merken? Ich kann ja die anderen Transaktionen einfach einschleusen ohne dass man es merkt, der block hash bleibt ja der gleiche.

14

Wo willst du das denn einschleusen? Auf deiner Node? Auf „der“ Blockchain?

Geh mal nach draussen, ich glaube die Dezentralität hat bei dir an der Tür geklingelt… :smiley:

1 „Gefällt mir“
15

Oh man… da war ja was… :joy:

1 „Gefällt mir“
16

Du meinst im Fall, dass die neu eingeschleuste Transaktion per Zufall den gleichen Merkletree-Hash eines Blockes hat? Dann würde tatsächlich nicht auffallen dass die Transkation neu hinzugekommen ist. Du müsstest den neuen Block lediglich unter die Leute bringen.

Tatsächlich wäre das aber ein Angriff und somit noch unwahrscheinlicher als der hier diskutierte Zufall. Denn im Gegensatz zu irgendeiner Kollision müsstest du hier eine genaue Kollision realisieren. Die Chance dafür liegt bei 1/N * 1/N → 10E-80 . Zusätzlich gäbe es das Problem dass du nicht jede beliebige Kombination als Eingang nehmen kannst. Denn nur weil der Hash dann stimmt ist der Eingang nicht unbedingt eine gültige Transaktion. Das reduziert den möglichen Ergebnissraum noch einmal extrem.

Um das Beispiel von oben zu erweitern streichen wir alle Kugeln grün an, die eine valide Transaktion darstellen. Ohne genau nachzuschauen wie eine Valide Transaktion aussieht denke ich, dass nur ungefähr jede g=10E25 Eingabe auch eine valide Transaktion darstellt. Für das Experiment würde das bedeuten, dass du eine exakt vorgegebene grüne Kugel exakt zwei mal aus dem Topf fischen willst. Die Chance verringert sich dadurch nocheinmal beträchtlich.

17

Und genau das würde sowieso nicht funktionieren, von der Wahrscheinlichkeit mal abgesehen. Eine Node interessiert sich nicht für einen Block den sie schon kennt und verifiziert hat. Nodes fragen Blöcke von anderen Nodes an und bekommen sie nicht einfach aus dem nichts zugeschickt.

Ein direkter Angriff auf eine Node, also das brutale manipulieren der lokalen Chain ist flächendeckend nicht umsetzbar und wäre selbst wenn auch nicht effektiv, da der eingeschleuste Block ungültig ist.

Auch bei synchronisierenden Nodes spielt das keine Rolle. Eine Node braucht nur einen einzigen Peer um zu synchronisieren. Wenn dieser Peer fehlerhafte Blöcke bereit stellt wird die synchronisierende Node das sofort oder in unserem Kollisions-Sonderfall irgendwann* merken.

* Denn entweder ist die eingeschleuste Transaktion ungültig oder durch die eingeschleuste Transaktion sind spätere Transaktionen ungültig – Alle Transaktionen sind durch das UTXO Modell miteinander verknüpft!

Das ist also keine Frage von Wahrscheinlichkeit, sondern Umsetzbarkeit. Und die ist nicht gegeben.