0 Daumen
639 Aufrufe

Aufgabe:

Bei der Suche nach der Bestätigungszahl für einen Bitcoin-Block müssen Hashwerte berechnet werden, die eine bestimmte Anzahl n an Nullbits am Anfang des Hashwerts aufweisen. Die Hashwerte selbst sind 160 Bit lang.

Wie groß ist die Wahrscheinlichkeit, dass der Hashwert für die erste Bestätigungszahl bereits n Nullbits am Anfang aufweist?


Ansatz/Problem:

Mir einfällt nur dies ein: n/(160-n)^2

Avatar von

Bitte etwas konkreter werden. Geht es um zusammenhängende Nullbits? Beziehen sich diese auf die 160 Bits (= 160 Stellen)?

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Wahrscheinlichkeit der Nullbits am Anfang eines Hashwerts

Zur Berechnung der Wahrscheinlichkeit, dass der Hashwert für die erste Bestätigungszahl \(n\) Nullbits am Anfang aufweist, müssen wir verstehen, wie Hashwerte funktionieren. Hashfunktionen im Kontext der Kryptographie, wie sie etwa bei Bitcoin verwendet werden, sind darauf ausgelegt, nahezu zufällige Ausgaben zu erzeugen. Das bedeutet, dass jedes Bit eines Hashs unabhängig von den anderen Bits mit einer Wahrscheinlichkeit von 50% eine 0 oder eine 1 ist.

Wenn wir einen Hashwert betrachten, der \(n\) Nullbits am Anfang aufweisen soll, können wir dies als eine Sequenz von \(n\) unabhängigen Versuchen betrachten, bei denen jedes Mal mit einer Wahrscheinlichkeit von \(0,5\) (oder \(1/2\)) eine Null gefordert wird, da jedes Bit mit einer Wahrscheinlichkeit von 50% entweder 0 oder 1 sein kann.

Berechnung der Wahrscheinlichkeit

Um die Wahrscheinlichkeit zu berechnen, dass die ersten \(n\) Bits alle Null sind, multiplizieren wir die Wahrscheinlichkeiten für jedes dieser \(n\) Bits. Da die Wahrscheinlichkeit, eine Null zu erhalten, \(1/2\) ist und diese Wahrscheinlichkeit für jedes der \(n\) Bits gleich ist, ergibt sich die Wahrscheinlichkeit wie folgt:

\( P(n \text{ Nullbits am Anfang}) = \left(\frac{1}{2}\right)^n \)

Dies bedeutet, dass die Wahrscheinlichkeit, \(n\) Nullbits am Anfang des Hashwerts zu haben, exponentiell mit der Anzahl der geforderten Nullbits abnimmt.

Beispiel

Für \(n=3\), also wenn die ersten 3 Bits Null sein sollen, wäre die Wahrscheinlichkeit:

\( P(3 \text{ Nullbits}) = \left(\frac{1}{2}\right)^3 = \frac{1}{8} \)

Zusammenfassung

Der ursprünglich vorgeschlagene Ansatz \(n/(160-n)^2\) ist nicht korrekt für dieses Problem. Der Schlüssel zur Lösung liegt in der Tatsache, dass jeder Hashwertbit unabhängig und zufällig mit einer Gleichwahrscheinlichkeit von \(1/2\) entweder eine Null oder eine Eins sein kann. Die Wahrscheinlichkeit, dass die ersten \(n\) Bits eines Hashwertes Null sind, folgt daher einer einfachen Berechnung, die auf der Wahrscheinlichkeit für das Auftreten eines einzelnen Bits basiert, und nicht auf der Gesamtlänge des Hashes oder einer anderen Funktion dieser Länge.
Avatar von 4,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community