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.