雜湊探勘/簽名的複雜性
在閱讀有關加密貨幣挖礦的資訊時，我發現它需要雜湊函式輸出的一些前導位為 0。這歸結為雜湊函式的原像抗性，因此通過窮舉搜尋完成。
我的問題是，假設我有一個理想的散列函式，它提供 128 位輸出，我希望前導 4 位為 0。我必須執行它（隨機選擇的消息）的預期時間是多少，這樣我才能得到想要的結果？
更具體地說，我正在尋找一種功能，它會給出複雜性，用於設置 $ m $ 返回的理想雜湊函式的位 $ n $ 位作為輸出。
對於隨機輸入。每個位都有機率 $ \frac{1}{2} $ 為零。然後因為我們假設獨立性（理想的散列函式暗示了這個假設）。對於每個輸入的機率 $ 4 $ 前導位中的零是 $ \frac{1}{2^4}=\frac{1}{16} $ .
然後 $ k $ 計算，因為我們認為每個輸出都是獨立的（仍然是因為它是一個理想的散列函式）。準確等待的機率 $ i $ 步驟是一個很好的輸出是 $ \frac{1}{16}\left(15/16\right)^{i-1} $ . （因為你有一個錯誤的輸出 $ (i-1) $ 雜湊，然後是一個傻瓜）。
計算時間的期望是 $ \sum^{\infty}{i=1} i\frac{1}{16}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}{j=1} \sum^{\infty}{i=j}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}{j=1} \sum^{\infty}_{i=0}\left(15/16\right)^{j+i-1} $
$$ =\frac{1}{16}\sum^{\infty}{j=1} \left(15/16\right)^{j-1}\sum^{\infty}{i=0}\left(15/16\right)^{i} $$ $$ = \frac{1}{16}\sum^{\infty}{j=1} \left(15/16\right)^{j-1}\frac{1}{1/16} $$ $$ =\sum^{\infty}{j=0} \left(15/16\right)^{j} =16 $$.
然後平均而言，您必須計算 $ 16 $ 雜湊找到一個好的。
您可以通過替換輕鬆概括此證明 $ 16 $ 經過 $ 2^m $ , 你會推斷出你平均需要計算 $ 2^m $ 雜湊。
請注意，因為我們提前選擇了我們想要為零的座標，所以如果我們查看我們應該計算的雜湊數，雜湊函式的總輸出並不重要（但如果我們查看計算時間，它可以做到的 $ H $ ).