Gültige Hashes bei steigender Difficulty

Fragen
1

Hallo Zusammen
Ich bin neu hier im Forum und beschäftige mich nun etwa seit erst einem Monat intensiv mit Bitcoin.
Ich mache wahrscheinlich einen Denkfehler da es nicht vorstellbar ist wieviele Hashes die 2^256 der Funktion wirklich sind. So wie ich das bisher verstanden habe wird die Difficulty ja jeweils an die durchschnittliche Hashrate angepasst. Und die Difficulty beschreibt welche Hashes gültig sind und welche nicht. Wenn ich mir die möglichen Hashes in einem Zahlenstrahl von 0 bis fast unendlich vorstelle beschreibt ja die Difficulty dass zB nur die Blöcke mit einem Hashwert von 0 bis x gültig sind. Wenn in Zukunft nun durch diverse Innovationen in der Hardware sowie Energiegewinnung und Energieeffizienz dazu kommen wird dadurch die Difficulty so stark erhöht das es immer weniger gültige Hashes gibt. Kann es dann nicht sein das irgendwann die Hashes aufgebraucht sind oder die wahrscheinlichkeit für eine Kollision (2 gleiche Hashes für Unterschiedliche Eingaben) auftreten kann?
Oder geht das einfach über meine Vorstellungskraft hinaus?
Und was würde bei einer möglichen Kollision bei Sha256 passieren und was würde das für Bitcoin bedeuten?

Danke euch allen für das tolle Forum!

Liebe Grüsse

2

Richtig, die Difficulty, bzw. das Target gibt einen Wert an der unterschritten werden muss. Ich verstehe deine Überlegung, allerdings vergisst du dabei zwei Punkte:

  1. 2^{256} ist unfassbar groß. Dazu dieses Video schauen:

  2. Die Schwierigkeit steigt exponentiell je kleiner man das Target setzt. Dazu hier eine passende Analogie:

    Uns geht früher die Hardware und Energie aus bevor uns gültige Hashwerte ausgehen. :slight_smile:

In der Theorie ist die Wahrscheinlichkeit bei steigender Hashrate natürlich größer. Aber auch hier unterschätzt du wie viel größer 2^{256} im Vergleich zur aktuellen oder zukünftig realistischen Hashrate ist.

170 \cdot 10^{18} ← Aktuelle Hashrate ca. 170 EH/s

\displaystyle\frac{\sqrt{2^{256}}}{170 \cdot 10^{18} \cdot 86000 \cdot 365} \approx 63767473140

… Jahre bis du sicher eine Kollision findest, mit der Hilfe des gesamten Bitcoin Netzwerks.

2 „Gefällt mir“
3

Dieser Thread ist sehr ähnlich, einfach mal reinschauen:

…

Für das Mining wäre das relativ egal. Bei den Bitcoin Transaktionen ist es nicht ganz egal.

Für das Finden einer Kollision braucht man nur in der Größenordnung von Wurzel(2²⁵⁶) Schritte. Also ja, ich denke, dass man hier dann mit 2¹²⁸ rechnen müsste.

2 „Gefällt mir“
4

Hat mir jetzt keine Ruhe gelassen, deshalb habe ich es gerade nochmal überschlagen. Die Frage war ja, wie viele Hashes man benötigt um relativ sicher eine Kollision zu bekommen. Für das Mining ist das denke ich nicht relevant, aber interessant ist es trotzdem (z.B. Skript-Hashes).

Mit der exakten Formel kommt man nicht weit. Deshalb habe ich mal ein bisschen genähert und bin auf folgende Näherungsformel für die Kollisionswahrscheinlichkeit gekommen:

P = 1 - \frac{N!}{(N-h)!\,N^{h}} \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

P ist im Prinzip die Wahrscheinlichkeit, dass man h Mal aus einer Urne mit N verschiedenen Kugeln zieht, jedes Mal zurücklegt, und am Ende mindestens eine Kugel zwei Mal oder öfter gezogen hat.
Dabei wird angenommen, dass alle Kugeln (Hashes) gleichwahrscheinlich sind. Außerdem muss N groß sein und h/N klein sein. Bei SHA-256 nehme ich an, dass tatsächlich N = 2²⁵⁶ Hashwerte möglich sind.

Bei unseren großen Zahlen ist die Formel praktisch exakt. Selbst beim üblichen Geburtstagsparadoxon mit relativ kleinen Zahlen ist sie nicht so schlecht.
Die Wahrscheinlichkeit beträgt ca. 50,7%, dass von 23 Leuten mindestens zwei am gleichen Tag Geburtstag haben. Nach der Näherungsformel sind es 51,6% (h=23, N=365).

Den zweiten Term in der Formel oben habe ich deshalb nochmal umgeformt, damit man die Abhängigkeit der Kollisionswahrscheinlichkeit von \frac{h}{\sqrt{N}} besser erkennen kann.

Nur wenn h in der Größenordnung von √N liegt, nimmt die Wahrscheinlichkeit greifbare Werte an. Liegt h eine Größenordnung darunter, ist P ≈ 0. Liegt h eine Größenordnung darüber, ist P ≈ 100 %.

Beispiele für N = 2²⁵⁶:

P (h = 2¹²²) ≈ 0,01 %
P (h = 2¹²⁵) ≈ 0,78 %
P (h = 2¹²⁸) ≈ 39 %
P (h = 2¹³¹) ≈ 100 %

Man kann also guten Gewissens sagen, dass man 2¹²⁸ Hashes benötigt, um eine Kollision zu finden.

3 „Gefällt mir“
5

Danke, jetzt verstehe ich das auch besser!

Da wir von collision resistance sprechen müsste man außerdem alle Hashwerte speichern um eine Kollision überhaupt zu bemerken, oder?

Hast du zufällig \approx 10^{22} Exabyte rum liegen? :slight_smile:

Und bei second-preimage resistance fällt das Geburtstagsparadoxon weg und damit auch die Wahrscheinlichkeit.

Ich korrigiere oben mal meine Jahresrechnung damit hier kein Blödsinn rum steht.

1 „Gefällt mir“
6

Gerne! Ich habe jetzt noch einen Satz ergänzt um klar zu machen, welche Wahrscheinlichkeit überhaupt berechnet wird.

Stimmt. :slightly_smiling_face:

Edit:
Wenn man wie beim Mining nicht systematisch nach Kollisionen sucht ist das so. Wenn man allerdings nur nach Kollisionen suchen möchte, gibt es auch sehr speichereffiziente Möglichkeiten.

Genau.

Gerade habe ich auch noch gedacht, dass ich nicht weiß, wie unterschiedlich überhaupt gehasht wird. Falls alle Miner den gleichen Algorithmus mit den gleichen Startwerten und der gleichen Transaktionsauswahl bzw. -reihenfolge verwenden würden, wäre die Wahrscheinlichkeit einer Kollision natürlich wesentlich höher.

Allerdings ist mindestens die Coinbase-Transaktion und dadurch auch die Blockhashes bei allen Minern unterschiedlich. Deshalb ist der Gedanke Unsinn.

2 „Gefällt mir“
7

Echt?

Dann wäre sie doch eher geringer, weil alle bei den gleichen Hashwerten landen (es werden insgesamt weniger N überprüft weil es Überschneidungen gibt - unter der Annahme dass alle Miner exakt gleich vorgehen). Oder wo hab ich da den Denkfehler?

Die Coinbase Transaktion wird sogar als zusätzliche Nonce verwendet, da die Nonce im Blockheader bei einer Hashrate > 4 GH/s innerhalb einer Sekunde bereits ausgereizt ist (neuer Timestamp setzt die Nonce im Blockheader zurück - aber eben nur im Sekundentakt).

Ich denke dass die Miner hier alle ähnlich vorgehen. Eine Änderung im Blockinhalt kostet mehr, da man die Merkle Root neu ausrechnen muss, deshalb wird die „extraNonce“ im Coinbase Script auch nur angepasst wenn es zwingend notwendig ist d.h. wenn die Nonce im Header nicht ausreicht.

Aber wie du schon sagst hat man alleine durch den Poolnamen schon einen eindeutigen Unterschied.

1 „Gefällt mir“
8

Du hast keinen Denkfehler. Ich glaube wir haben gerade etwas Unterschiedliches gemeint.

Ich meinte die „Wahrscheinlichkeit“, das zwei gleiche Hashes auftreten. Das würde wie du sagst sofort passieren, hätte aber nichts mehr mit Zufall zu tun. Deshalb ist es natürlich Quatsch da von Wahrscheinlichkeit zu sprechen.

Du meintest die Wahrscheinlichkeit, eine echte SHA256 Kollision zu finden. Die würde natürlich geringer, da man weniger Versuche hätte, h also kleiner wäre.

Sehr interessant! Ich dachte immer nur an Nonce, Timestamp und Transaktionsreihenfolge.

Gleich nach „extra nonce“ gegoogelt und was finde ich? → Mastering Bitcoin :smiley:

1 „Gefällt mir“
9

Ich denk mir das ja nicht aus! :grin:

1 „Gefällt mir“