比特幣的工作量證明（hashcash）屬於什麼複雜度等級？
為了準確地表述這個問題，我將定義一個理想化的假設“完美”散列函式 H(n)，它具有很好的可擴展性屬性，並將據此制定一個問題 PERFECT HASHCASH，理解實際考慮可能最終只產生一個近似值這個理想。
為簡單起見，我們將說我們的散列函式 H(n) 將單個自然數 n 作為輸入。然後我們說 H(n) 是一個完美的散列函式當且僅當：
- H(n) 將每個自然數映射到一個無限二進制序列，其中計算任何初始段 s 的時間複雜度是 n 和 s 大小的多項式，（使其成為海綿函式）。
- 對於長度為 d 的任何初始段，所有自然數 n 的集合使得 H(n) 共享該初始段的自然密度= 1/(2^d)。
第一件事形式化了我們函式的可擴展性，第二件事形式化了我們希望所有散列大致“同樣頻繁地”作為輸出出現的想法。除此之外，我們完美的散列函式是一個黑盒子，我們並不關心它究竟是如何工作的，只要它滿足上述屬性，以及適用於散列函式的通常要求（易於計算，難以反轉，難以發現碰撞等）。
基於存在完美散列函式的假設，我們現在可以將問題PERFECT HASHCASH定義如下： PERFECT HASHCASH 將完美散列函式 H、自然數 n 和長度為 d 的全零向量 0^d 作為輸入，可以認為是 d 的一元表示。PERFECT HASHCASH 的解決方案由 n 和 d 組成，使得 H(n) 從 0^d 開始。
鑑於這些輸入，很明顯 PERFECT HASHCASH 屬於復雜性類TFNP，因為這是一個函式問題，並且保證存在解決方案。
我們也可以將 PERFECT HashCASH 辨識為比 TFNP 更精細的任何復雜性類別的成員嗎？
有關背景，請參閱Wikipedia 上的Complexity 類。
編輯：上述問題已經過徹底檢查，就像我最初制定它的方式一樣，我假設 SHA256 是我現在所說的完美雜湊函式。許多人在評論中指出這可能不是真的，因此我沒有將重點放在 SHA256 是否特別具有我們想要的良好縮放屬性上，而是定義了一個理想化的雜湊函式，我們希望 SHA256 至少可以很好地近似出於現實世界的目的，並據此重新表述了這個問題。
作為消除任何潛在混淆的最後一點，為了使 PERFECT HASHCASH 類似於真正的 Hashcash，我們必須再做一個假設：存在某種方法可以從數據塊（電子郵件、比特幣塊等）開始) 並以某種方式從中推導出一個特徵完美的散列函式，也許是通過“加鹽”一個不同的完美散列函式，結果也是另一個完美的散列函式。因此，在“完美比特幣”的情況下，比特幣網路上的所有礦工都將使用他們自己獨特的完美雜湊函式 H’(n) 以某種方式與他們正在處理的區塊相關聯，並且每個礦工將簡單地嘗試 H’(0), H’(1), H’(2), … 直到他們找到以足夠的 0 開頭的東西。每個 H’ 將是 PERFECT HASHCASH 的不同輸入。
加密散列函式，例如用於比特幣工作量證明的雙 SHA256，通常不使用這些對漸近行為進行分類的複雜性類來描述，這是有原因的。事實上，有幾個。
- 一個技術原因是雜湊函式通常無法擴展。例如，沒有定義如何擴展工作量證明以在 512 位上執行。一個自然的選擇是使用 SHA512，但是從 SHA256 到 SHA512 需要很多基本上任意的選擇，比如將輪數從 64 更改為 80，這是標準化的，但不是以自然縮放的方式，也不適用於任意大的雜湊尺寸。
- 它與密碼學家無關。即使是 NP 完全散列函式，這將是您列出的用於建構強散列的複雜情況中最強的，也不能保證我們從加密散列或工作證明函式中得到的所有東西。符合 NP 完全性的條件僅僅是一種強烈的啟發式方法，即問題不能通過漸近小於指數的算法來解決。但是對於一個好的散列函式，我們希望它在我們選擇使用它的非常有限的比特數下，最大指數，因為解決它實際上與嘗試散列函式中的所有可能性一樣困難。對於其相應的工作量證明函式，其難度如此之大，以至於只有輸出範圍的一小部分 x 是可以接受的，這意味著我們應該期望需要進行 x/2 倍於整個輸出範圍大小的嘗試才能找到工作量證明。任何比這更好的東西都會促使學者稱相關的雜湊函式被破壞，即使它只是將嘗試次數減少了一半，這仍然會將其置於指數複雜度類中，並且即使使用 NP 完全函式也很容易實現.
一個令人印象深刻（但只是表面相關）的例子是背包密碼學是如何挑選看似 NP 完全的東西不足以獲得密碼學上的東西。當然，問題在於通過選擇特殊情況可以降低問題的複雜性。關鍵是，即使是一個 NP 完全問題也可能比實際上必須嘗試每個解決方案更容易，儘管有時會這樣描述它！對於密碼學級的質量，必須嘗試每個輸入是字面意思；對於復雜性分析，如果漸近縮放在位數上保持指數級就足夠了。因此，如果您可以將問題簡化為另一個僅將每 1000 位作為輸入的 NP 完全函式， 3. 它很難！而且我認為這個困難已經讓你誤入歧途：即使你將這個問題放在 TFNP 中的論點，雖然非常接近事實，但在數學意義上並不正確。例如，如果我指定 x=0，則沒有 y 可以產生 hash(y) < x，這與您的斷言相矛盾。如果所有其他 x 都很好，或者 x 是否有所需的最小值，可能取決於您如何定義希望 hashcash 操作的“字元串”y。對於進入雙 SHA256 的比特數有限的比特幣，如果 x=1 也沒有解決方案，我不會感到驚訝，即如果沒有塊雜湊可以完全為零。當然，我們可能永遠不會知道。在實踐中，散列函式應該以您描述的方式產生完全的工作量證明函式是可取的，但我不認為這是一種經過驗證的質量。免責聲明：老實說，我不知道。你真的應該問密碼學家。
在找到散列函式如何縮放並驗證它對於任意大尺寸仍然是多項式之後，要回答您的問題，還需要做些什麼來證明相應的工作量證明函式是完全的。如果這個證明可以使用鴿子洞原理完成，你已經證明它是在 PPP 等中。
那麼難點在哪裡呢？例如，如果 y 的位數至少與 x 一樣多，並且如果我們將您的 hashcash 更改為小於或等於而不是小於，並且如果我們願意將其進一步乘以到以下點找到工作量證明或雜湊衝突的存在足以使“hashcash”為真，那麼您連結到的維基百科文章中解釋的鴿子洞原理顯然將適用。
但就我所見，任何低於此的東西都不足以應用鴿子洞原則，因此不會回答 hashcash 是否在 PPP 中的問題。再次參考您連結的維基百科文章：只有極少數問題的答案是已知的，即使是 PPP。對於 PPP、PPA 和 PPAD 的特殊情況，顯然變得更加困難。如果您找到解決方案，請將其發佈到學術期刊，而不僅僅是在這裡！