具有一個且只有一個正確答案的工作證明方案
我需要一個只有一個解決方案的問題，這樣解決方案很難找到但很容易驗證。我需要能夠從隨機種子中確定性地生成問題。
所以本質上，我希望能夠做到這一點：
- 產生一個隨機值。
- 然後可以搜尋隨機值的“正確答案”。
- 只有一個“正確答案”。
- 可以很容易地驗證特定答案是否正確。
理想情況下，所需的工作量是可調的。大多數工作量證明系統的問題在於，它們要麼不能確保只有一個正確答案，要麼需要某個實體來生成問題並保留解決方案。
例如，我可以要求某人生成具有隨機值的 HMAC 的東西，結果非常低。但是這樣就不會有一個且只有一個正確答案了。我可以將兩個素數相乘，最小的因子可能是正確的答案。但是我沒有可以做這種乘法的代理。第一步和第二步是一成不變的，儘管我可以調整隨機數的大小。
更新：在生成隨機數之前不可能完成所有工作。理想情況下，任何預計算都不會帶來顯著的好處。顯示的隨機數必須使您能夠完成這項工作。
一種明顯的方法是查看離散對數問題。也就是說，你選擇一個合適的訂單組 $ n $ （在哪裡 $ n $ 是素數）和發電機 $ G $ ; 對於一個挑戰，你選擇一個隨機元素 $ H $ ，並且您要求該值 $ 0 \le k < n $ 這樣 $ H = kG $ .
這符合您的要求（1）產生的值是有效隨機的，要求（2）可以在 $ O(\sqrt n) $ 時間，（3）如果 $ G $ 是一個生成器，那麼只有一個這樣的值，並且 (4) 答案可以在 $ O(\log n) $ 時間。此外，工作量是可調的（通過選擇不同大小的組）。
為此，我們需要選擇一個找不到離散日誌的組。 $ O(\sqrt n) $ 時間; 我相信一個適當大小的隨機橢圓曲線可以滿足這個要求。
然而，這個建議的主要困難是找到一個合適大小的橢圓曲線組。這是不平凡的，我知道的所有預先計算的橢圓曲線組都被縮放以使離散對數問題“不可行”，而不是“困難”。
另一個看起來合適的組是一個更大的乘法組的一個小子組。也就是說，我們選擇一個大素數 $ p $ 和一個小素數 $ q $ 在哪裡 $ q | p-1 $ . 然後我們將在大小的乘法子組中工作 $ q $ 該組的 $ \mathbb{Z}^*_p $ . 為了創建這個子組的隨機元素，我們選擇一個隨機數 $ 1 < x < p $ , 併計算 $ H = x^{(p-1)/q} $ . 子群的順序當然是 $ q $ ，所以如果工作目標大約是 $ 2^{32} $ 操作，我們可以選擇一個1024位 $ p $ 和一個 64 位 $ q $ . 與橢圓曲線思想相比，該提議的主要優點是更容易設計一個 $ p $ 和 $ q $ 合適的尺寸，而不是試圖定義橢圓曲線。