密碼貨幣的密碼學(xué)有什么問(wèn)題存在

2014 年，我曾在一篇文章和一場(chǎng)演講中列出了一系列我認(rèn)為對(duì)密碼學(xué)貨幣領(lǐng)域的成熟有重大意義的數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)難題。五年過(guò)去，滄海桑田，但在這些我們認(rèn)定重要的事項(xiàng)上，到底取得了多少進(jìn)展？在哪些挑戰(zhàn)上我們成功了，哪些事情上我們失敗了、又或者我們轉(zhuǎn)變了看法？本文中我會(huì)歷數(shù)2014年列舉出的16大問(wèn)題，并檢視我們的進(jìn)展。最后，我會(huì)給出2019年版的新難題。

我把難題分成了三類：（i）密碼學(xué)難題，如果可解，應(yīng)有純數(shù)學(xué)形式的解決辦法；（ii）共識(shí)理論，基本上就是要求對(duì)工作量證明和權(quán)益證明做改進(jìn)；（iii）經(jīng)濟(jì)學(xué)問(wèn)題，要求創(chuàng)造一種為不同參與方賦予經(jīng)濟(jì)激勵(lì)的結(jié)構(gòu)，并且一般都在協(xié)議層以外包含了應(yīng)用層。雖然進(jìn)度不一，但我們?cè)谒蓄悇e中都看到了重大進(jìn)展。

密碼學(xué)問(wèn)題

1. 區(qū)塊鏈可擴(kuò)展性

當(dāng)前密碼學(xué)貨幣領(lǐng)域面臨的最大挑戰(zhàn)之一就是可擴(kuò)展性問(wèn)題……對(duì) “區(qū)塊鏈數(shù)據(jù)量過(guò)大” 的擔(dān)心是有道理的：如果只有小一部分人才有能力運(yùn)行全節(jié)點(diǎn)，那么這些實(shí)體就可以秘密勾結(jié)并給自己分配額外的比特幣，而其它用戶則無(wú)力為自己伸張正義，因?yàn)橹挥凶约候?yàn)證區(qū)塊才能發(fā)現(xiàn)非法區(qū)塊。

問(wèn)題定義：創(chuàng)造一種區(qū)塊鏈結(jié)構(gòu)，既能擁有比特幣級(jí)別的安全保障，同時(shí)用于保證網(wǎng)絡(luò)功能存續(xù)的最強(qiáng)大節(jié)點(diǎn)的規(guī)模上限會(huì)隨著交易數(shù)量的增加而呈次線性增長(zhǎng)。

現(xiàn)狀：有大量的理論進(jìn)步，但有待生產(chǎn)環(huán)境檢驗(yàn)。

在可擴(kuò)展性問(wèn)題上，我們已經(jīng)在理論上取得了大量進(jìn)展。五年前，幾乎還沒(méi)有人思考過(guò)分片的可能性；現(xiàn)在，分片設(shè)計(jì)是大家司空見(jiàn)慣的東西了。除了以太坊 2.0，還有 OmniLedger、LazyLedger、Zilliqa，而且新論文幾乎每個(gè)月都會(huì)冒出幾篇來(lái)。我個(gè)人的觀點(diǎn)是，在這個(gè)點(diǎn)上出現(xiàn)的進(jìn)展會(huì)越來(lái)越多。最基本來(lái)說(shuō)，我們已經(jīng)有多項(xiàng)技術(shù)可以讓驗(yàn)證者群體對(duì)超過(guò)單個(gè)驗(yàn)證者所能處理的數(shù)據(jù)安全地達(dá)成共識(shí)，同時(shí)技術(shù)還讓客戶端能夠間接地驗(yàn)證區(qū)塊的完全有效性和可得性，即便是在 51% 攻擊的條件下。

下面列舉出的可能是這些技術(shù)中最重要的一部分：

隨機(jī)采樣：可以隨機(jī)選出一些驗(yàn)證者組成委員會(huì)，使其在統(tǒng)計(jì)意義上代表整個(gè)驗(yàn)證者群體：

https://github.com/ethereum/wiki/wiki/Sharding-FAQ#how-can-we-solve-the-single-shard-takeover-attack-in-an-uncoordinated-majority-model

錯(cuò)誤性證明：讓監(jiān)測(cè)到錯(cuò)誤的節(jié)點(diǎn)向其它節(jié)點(diǎn)廣播自己發(fā)現(xiàn)的錯(cuò)誤：https://bitcoin.stackexchange.com/questions/49647/what-is-a-fraud-proof

數(shù)據(jù)托管證明：讓驗(yàn)證者可以概率性地證明自己下載并驗(yàn)證了一些數(shù)據(jù)：https://ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236

數(shù)據(jù)可用性證明：當(dāng)客戶端具備區(qū)塊頭的區(qū)塊體不可用時(shí)，讓客戶端可以探測(cè)到錯(cuò)誤：https://arxiv.org/abs/1809.09044。也可以看看更新的編碼化默克爾樹提案。

還有一些更小的進(jìn)展，比如用收據(jù)實(shí)現(xiàn)跨分片通信，還有 “常量因子” 強(qiáng)化技術(shù)如 BLS 簽名聚合技術(shù)。雖說(shuō)如此，完全分片的區(qū)塊還是沒(méi)能在現(xiàn)實(shí)中出現(xiàn)（盡管部分分片的區(qū)塊鏈 Zilliqa 已經(jīng)開始運(yùn)行了）。理論上來(lái)說(shuō)，剩下的爭(zhēng)議都是細(xì)節(jié)上的，圍繞著與分片組網(wǎng)穩(wěn)定性、開發(fā)者體驗(yàn)和緩解中心化風(fēng)險(xiǎn)的各項(xiàng)挑戰(zhàn)；基本的技術(shù)可行性看起來(lái)不再有疑問(wèn)。但剩下的挑戰(zhàn)都是不可能僅靠理論來(lái)解決的問(wèn)題；只有開發(fā)出這樣的系統(tǒng)、看到以太坊 2.0 或類似的鏈實(shí)際運(yùn)行才能解決這些問(wèn)題。

2. 時(shí)間戳

問(wèn)題：創(chuàng)建一種分布式的激勵(lì)兼容系統(tǒng)，無(wú)論它是區(qū)塊鏈上的覆蓋層還是區(qū)塊鏈本身，能夠以高準(zhǔn)確度維護(hù)一個(gè)實(shí)時(shí)的時(shí)鐘。所有合法用戶的時(shí)鐘圍繞某個(gè) “真實(shí)時(shí)間” 以 20 秒的標(biāo)準(zhǔn)差呈正態(tài)分布……沒(méi)有任何兩個(gè)節(jié)點(diǎn)的時(shí)間差會(huì)超過(guò) 20 秒。解決方案可以依賴現(xiàn)有的 “N 個(gè)節(jié)點(diǎn)” 概念；可以通過(guò)權(quán)益證明或者 non-sybil token 來(lái)組織節(jié)點(diǎn)（可聯(lián)系下文的 9 號(hào)難題）。這個(gè)系統(tǒng)應(yīng)能不斷地提供時(shí)間，并且時(shí)間在超過(guò) 99% 的誠(chéng)實(shí)參與者節(jié)點(diǎn)內(nèi)部時(shí)間的 120 秒范圍內(nèi)。外部系統(tǒng)可能最終會(huì)依賴這個(gè)系統(tǒng)；因此，它應(yīng)該能在攻擊者無(wú)視激勵(lì)措施且控制 25% 的節(jié)點(diǎn)條件下保持安全性。

現(xiàn)狀：有一些進(jìn)展。

以太坊在 13 秒的出塊時(shí)間、無(wú)特殊高級(jí)時(shí)間戳技術(shù)的條件下運(yùn)作得非常好；這個(gè)網(wǎng)絡(luò)只是要求客戶端不要接受所引時(shí)間戳比本地時(shí)間更新的區(qū)塊。也就是說(shuō)，這一技術(shù)還沒(méi)有在高強(qiáng)度攻擊下接受過(guò)檢驗(yàn)。最新的網(wǎng)絡(luò)調(diào)整時(shí)間戳提案嘗試改變現(xiàn)狀，它讓客戶端本地可以在并不知道高精確度的當(dāng)前時(shí)間時(shí)對(duì)時(shí)間達(dá)成共識(shí)；不過(guò)這也還沒(méi)有被檢驗(yàn)過(guò)?？偟膩?lái)說(shuō)，時(shí)間戳技術(shù)已從研究挑戰(zhàn)的前沿退了下來(lái)；也許這一點(diǎn)會(huì)在眾多權(quán)益證明區(qū)塊鏈（包括以太坊 2.0 等）上線之后改變，到時(shí)候我們就能更具體地定位問(wèn)題了。

3. 通用的計(jì)算過(guò)程證明

問(wèn)題：創(chuàng)建程序 POC_PROVE（P，I） -》 （O， Q） 以及 POC_VERIFY（P，O，Q） -》 {0， 1} ，使得 POC_PROVE 以 I 為輸入運(yùn)行程序 P ，可以返回程序輸出 O 以及一段計(jì)算過(guò)程證明 Q ；當(dāng) POC_VERIFY 以 P 、O 、Q 為輸入時(shí)，可輸出結(jié)果，表明 Q 和 O 是不是 POC_PROVE 算法使用程序 P 生成出來(lái)的。

現(xiàn)狀：大量理論進(jìn)展和實(shí)際進(jìn)展。

這個(gè)基本上就是說(shuō)，要構(gòu)建一個(gè) SNARK（或者 STARK 或 SHARK，等等）。而且我們已經(jīng)做到了！SNARKs 越來(lái)越被充分理解了，甚至已經(jīng)被用在多條區(qū)塊鏈中（包括以太坊上的 tornado.cash 項(xiàng)目）。而且 SNARKs 是非常有用的，無(wú)論是作為隱私保護(hù)技術(shù)（Zcash 和 tornado.cash），還是作為可擴(kuò)展性技術(shù)（例如 ZK Rollup、STARKDEX 以及 STARK 化的糾刪編碼數(shù)據(jù)根）。 不過(guò)還是有些效率上的問(wèn)題，創(chuàng)造一種算術(shù)友好型的哈希函數(shù)是一個(gè)（看 此處 和 此處 了解那些突破性的候選方案）；高效證明隨機(jī)內(nèi)存存取是另一個(gè)。進(jìn)一步來(lái)說(shuō)，還有一個(gè)未解決的問(wèn)題是，是不是此類方案的證明時(shí)間都遵循 O（n * log（n）） 的限制，還是說(shuō)，有某種辦法可以構(gòu)建一個(gè)簡(jiǎn)潔的證明，開銷僅呈線性增長(zhǎng)，就像 bulletproofs 一樣（但它的驗(yàn)證時(shí)間也會(huì)呈線性增長(zhǎng)）。此外，這些現(xiàn)有方案有 bug 的風(fēng)險(xiǎn)也是一直存在的?？偠灾?，問(wèn)題都是細(xì)節(jié)上的，在問(wèn)題的基本層面已經(jīng)沒(méi)有疑問(wèn)了。

4. 代碼混淆

密碼學(xué)難題的圣杯是創(chuàng)造一個(gè)混淆器 O：對(duì)給定的任意程序 P，該混淆器能產(chǎn)生一個(gè)次級(jí)的程序 O（P） = Q，只要給出相同的輸入，P 與 Q 會(huì)返回相同的輸出，并且更重要的是，Q 不會(huì)暴露 P 的任何信息。這樣話，人們就可以在 Q 中隱藏口令、秘密的加密密鑰，或者僅僅是用 Q 來(lái)隱藏算法本身的工作方式。

現(xiàn)狀：進(jìn)展緩慢。

翻譯成大白話，這個(gè)問(wèn)題就是說(shuō)，我們想要一種方式來(lái) “加密” 一個(gè)程序，使得加密后的程序能對(duì)同樣的輸入給出相同的輸出，但原程序內(nèi)部的機(jī)理又是完全隱藏起來(lái)的。這種技術(shù)的一種用場(chǎng)是一段包含一把私鑰的程序，僅允許這把密鑰對(duì)特定消息簽名。

代碼混淆方案對(duì)區(qū)塊鏈協(xié)議來(lái)說(shuō)是非常有用的，雖然用起來(lái)會(huì)比較微妙，因?yàn)槲覀儽仨毭鎸?duì)這樣的可能性：一個(gè)在鏈上的混淆過(guò)的程序可能會(huì)被復(fù)制并用在一個(gè)完全不同的環(huán)境中，由此產(chǎn)生許多不同的結(jié)果。讓我很感興趣的點(diǎn)在這里：我們可以用包含一些工作量證明的、混淆后的程序來(lái)代替運(yùn)營(yíng)者，從而能在抗串謀工具中移除中心化的運(yùn)營(yíng)者，因?yàn)樵诖_定單個(gè)參與者的行動(dòng)時(shí)，使用多個(gè)輸入、運(yùn)行多次程序的開銷會(huì)非常大。

不幸的是，到目前為止，這還是一個(gè)難題。在這個(gè)問(wèn)題上不斷有人付出努力，一方面是創(chuàng)造一些建構(gòu)（例如這個(gè)），嘗試減少對(duì)那些我們不知道其實(shí)用性的數(shù)學(xué)對(duì)象（例如通用性密碼學(xué)多重線性映射）的假設(shè)，另一方面是嘗試做出有用數(shù)學(xué)對(duì)象的有用實(shí)現(xiàn)。不過(guò)，所有這些路徑距離我們的目的——?jiǎng)?chuàng)建出可行且在已知條件下安全的代碼混淆器——非常遙遠(yuǎn)。請(qǐng)看 https://eprint.iacr.org/2019/463.pdf 以了解對(duì)該問(wèn)題的更一般化的概述。

5. 基于哈希的密碼學(xué)

問(wèn)題：創(chuàng)造一種簽名算法，除了依靠哈希函數(shù)的隨機(jī)特性以外沒(méi)有別的安全假設(shè)；哈希函數(shù)對(duì)古典計(jì)算機(jī)保持 160 比特的安全性（即，根據(jù) Grover 算法，對(duì)量子計(jì)算機(jī)保持 80 比特的安全性），并且具有最優(yōu)大小及其他屬性。

現(xiàn)狀：有一些進(jìn)展。

自2014年以來(lái)，這個(gè)題目下出現(xiàn)了兩項(xiàng)進(jìn)展：（1）SPHINCS，一種 “無(wú)狀態(tài)” 的簽名方案（“無(wú)狀態(tài)” 的意思是，即使多次使用，也無(wú)需保存像 nonce 那樣的計(jì)數(shù)信息）。該方案在《難題》一文出版后不久就出現(xiàn)了，提供了一種僅基于哈希函數(shù)的簽名方案，簽名大小在 41 kB 左右；（2）STARKs 也已經(jīng)被開發(fā)出來(lái)了，所以人們可以基于 STARK 技術(shù)實(shí)現(xiàn)相近大小的簽名。不僅是簽名方案，連通用型零知識(shí)證明技術(shù)，都可以僅用哈希函數(shù)實(shí)現(xiàn)出來(lái)，這是我在 5 年前完全沒(méi)有料到的事，我很高興能見(jiàn)識(shí)到這一切。雖然說(shuō)，簽名的大小仍然是一個(gè)問(wèn)題，但人們也在不斷付出努力減少證明的大?。ɡ缱罱?DEEP FRI），而且看起來(lái)進(jìn)一步的進(jìn)展效果會(huì)越來(lái)越強(qiáng)。

基于哈希函數(shù)的密碼學(xué)中尚未解決的主要問(wèn)題是簽名聚合，就是類似于 BLS 簽名方案所提供的功能。已知的是我們可以對(duì)許多 Lamport 簽名方案生成 STARK，所以一個(gè)更有效率的簽名方案可能就快出來(lái)了。（如果你還在思考基于哈希函數(shù)的公鑰加密方案是否可能，答案是，不行，因?yàn)楣粽咧恍韪冻稣\(chéng)實(shí)用戶平方級(jí)的成本就可以攻破這樣的方案。）

責(zé)任編輯：ct