是否可以保證對於每個可能的雜湊 y 都存在一個數字 x，使得雜湊函式 H，H(x) = y？
在這裡專門討論 SHA-256 及其對比特幣的參與，這是有人問我的一個問題，我不知道答案。是的，我知道 SHA-256 只能從 $ 0 $ 至 $ 2^{256} -1 $ ，所以這可以作為我們 y 的範圍。我問的是在這個範圍內，是否保證每個可能的 y 都有一個 x。
我問這個主要是因為我想知道是否有任何東西可以保證一個新的比特幣塊總是可以用低於其目標的雜湊值創建。
TL;DR：沒有數學上的確定性，即常見加密雜湊函式的每個輸出值都是可以達到的，但對於大多數人來說，這是極有可能的。一個值得注意的例外是比特幣挖礦中使用的雙 SHA-256 (SHA256d)，其中極有可能存在一些無法訪問的輸出。
對於理想化的 256 位散列，很可能每個可能的散列值 $ y $ 通過散列一些 $ x $ 當有大約 $ 2^{264} $ 的可能值 $ x $ , 包括所有 33 字節 $ x $ ; 然後很可能有些 $ y $ 不被覆蓋變得非常小：不到一英寸 $ 2^{b-264} $ 如果有 $ 2^b $ 的可能值 $ x $ ; 因此，雖然從來沒有保證，但實際上可以肯定的是，所有 $ y $ 當我們允許說 40 字節時被覆蓋 $ x $ ：相反的機率小於 $ 2^{-56} $ .
參數：雜湊可以理想化為隨機函式。隨機函式是否覆蓋其所有圖像集的問題是優惠券收集者的問題。如果目標集有 $ n $ 元素，源集中完全覆蓋圖像集的預期元素數量為 $ E(n)=n\log n+\gamma,n+{1\over2}+O({1\over n}) $ 在哪裡 $ \gamma\approx0.577 $ 是歐拉-馬斯切羅尼常數；以及散列後不覆蓋輸入集的機率 $ E(n)/\epsilon $ 元素小於 $ \epsilon $ . 改變 $ n $ 至 $ 2^b $ 為一個 $ b $ -位雜湊，我們得到 $ E(2^b)\approx2^b(b\log(2)+\gamma) $ 和 $ \begin{align}\log_2(E(2^b)) &\approx b+\log_2\left(b+{\gamma\over\log(2)}\right)+\log_2(\log(2))\ &\approx b+\log_2(b+0.833)-0.528766\end{align} $
SHA-256 是Merkle-Damgård 散列，使用根據Davies-Meyer 構造建構的壓縮函式。如果全部的問題 $ y=\operatorname{SHA-256}(x) $ 達到減少，最多 55 個字節散列，如果全部 $ \operatorname{Enc}_x(IV) $ 達到某個常數 $ IV $ 和某個分組密碼 $ \operatorname{Enc} $ 在哪裡 $ x $ 是鍵，鍵調度包含塊填充。對於理想化的分組密碼，與理想化散列的分析相同，因此我們會以壓倒性的優勢覆蓋所有值。SHA-256 使用ARX 分組密碼，我看不出它與理想化密碼有顯著差異的原因，但這是一個弱論點。
當我們允許兩輪（例如，100 字節雜湊）時，我們可以更積極地獲得全面覆蓋，因為現在的問題是，如果所有 $ \operatorname{Enc’}_{x_1}(y_0)\boxplus y_0 $ 到達哪裡 $ x_1 $ 是 36 字節的第二個塊，並且 $ y_0 $ 允許在第一輪可達的幾乎完整的 32 字節值集之間變化 ( $ \boxplus $ 是 256 位加法，沒有跨越 32 位邊界的進位）。儘管如此，還是沒有數學上的保證。
在比特幣挖礦中，計算的是 $ y=\operatorname{SHA-256}(\operatorname{SHA-256}(x)) $ . 對於外部散列，我們遠低於優惠券收集者的界限，並且絕大多數高於生日界限，因此極有可能存在一些值 $ y $ 還沒到。
我在下面附上 Dave Thomson 的評論。