DeepHash 專欄 ｜如何用理論電腦科學來優化比特幣費率市場？
關於 DeepHash 專欄
“區塊鏈技術非常複雜，而且有很多誤解。更可怕的是，很多人自認為了解區塊鏈技術，但表現出的卻是無知。學術機構有著巨大的責任去培養下一代的創新者。”這是在杜克大學商學院開設區塊鏈課程的美國金融協會前主席 Campbell Harvey 曾經有感而發地說過的話。
每項新興技術發展都有它的週期，愈是可能帶來重大變革的技術，這個週期往往也愈明顯。就在區塊鏈技術步入所謂“幻滅的低谷”之時，DeepTech 深科技認為，下一個產業風口，如今正在每個頂尖高校的實驗室、在各國央行與監管機構的研究室，在行業組織的研討會中醞釀著。
DeepTech 深科技認為，此時才是關鍵時刻，身為一家堅持深入報道科學科技產業的專業媒體與科技服務提供者，我們有責任也有必要，在這個時點上有帶領讀者去撥開迷霧、釐清誤解，培養對區塊鏈技術的更深刻認知。
因此我們於每週二固定推出 DeepHash 專欄，由 DeepTech 資深編輯林佳誼，邀集千人學者兼天德鏈創始人蔡維德、中國工信部電子工業標準化研究院區塊鏈研究室主任李鳴等專家學者共同維護，每週一次，帶領讀者在技術研發、在法規政策、在行業標準，在國際趨勢，方方面面深入挖掘未來 3-5 年真正具有產業化潛力區塊鏈知識。
本週我們要帶您回到區塊鏈的源頭——比特幣。近來幣價暴跌，讓整個行業瀰漫悲觀氛圍，更有人認為距今誕生 10 年比特幣會就此化為泡影。但事實上，學界仍積極投入不斷完善這一目前為止仍是最成功執行的加密貨幣。包含著名計算機學家、圖靈獎唯一華人得主姚期智也注意到了這個問題，並發表一篇最新論文，希望能通過理論電腦科學來強化比特幣交易費機制的理論架構。以下我們將帶您深入讀懂這篇論文：
解讀圖靈獎得主姚期智最新論文，如何用理論電腦科學來優化比特幣費率市場
挪威科技大學資訊與通訊技術與自然科學系副教授王皓亦對本文提供了專業意見
前段時間，一筆在比特幣網路上的交易，在區塊鏈行業引發了大量關注。一名使用者僅花費 0.1 美元，就完成了一筆價值 1.94 億美元的比特幣轉帳交易。這在傳統金融行業的標準來看，簡直是天方夜譚。
這筆交易在 10 月 15 日被新增到區塊 545911 中，價值高達約 1.94 億美元（當時幣價約 6466 美元）的 3 萬枚比特幣，分別被轉到兩個地址，而手續費僅 0.00001464 BTC，約 0.1 美元。相較之下，一般傳統銀行假設是跨境匯款，需要按匯款金額約 0.10% 收取手續費，還不計其它電報費與中轉行手續費。
比特幣轉帳的低成本固然誘人，但卻反映出了整個費率市場其實並不健全，缺乏誘因吸引礦工加入，投入裝置、電力等資源來協助維持整個比特幣系統的運作。在當前幣價低迷，區塊獎勵跌破挖礦成本，導致礦工大量退出之際，更凸顯出建立交易手續費機制，對維繫整個比特幣生態健全有多重要。
著名計算機學家、圖靈獎唯一華人得主姚期智也注意到了這個問題。他的最新發表論文《比特幣費率設計的激勵分析》（An Incentive Analysis of some Bitcoin Fee Designs），就以比特幣交易費機制為主題，從數學的角度為近期學界提出的創新機制，提供了支援與佐證。
他更指出，這是一個令人興奮的研究領域，有著許多吸引人的問題等待解決，對於理論科學家與系統設計者都是如此。
(來源：arXiv)
姚期智的研究方向包括計算理論及其在密碼學和量子計算中的應用。他是研究量子計算與通訊的國際前驅，於 1993 年最先提出量子通訊複雜性，基本上完成了量子計算機的理論基礎。1995 年提出分散式量子計算模式，後來成為分散式量子演算法和量子通訊協議安全性的基礎。
尤其是在現代密碼學領域，他的研究在基於複雜性的密碼學和安全形式化方法方面有根本性貢獻。
正如日前他曾在公開演講中指出的，電腦科學正在迎來一個前所未有的黃金時代，正在打破邊界，帶來新的變革。姚期智也將自己的研究觸角延伸到了加密貨幣與區塊鏈的領域。
根據姚期智個人頁面來看，《比特幣費率設計的激勵分析》這篇論文，應是他首度以個人獨立掛名的加密貨幣或區塊鏈主題論文。過去他所發表的這類主題論文，多半是與團隊或研究夥伴合作，如 2018 年 5 月曾與團隊共同發表《將中本聰共識擴容至每秒數千計次交易》（Scaling Nakamoto Consensus to Thousands of Transactions per Second）一文，提出快速、高效能且去中心化的區塊鏈系統 Conflux。
而姚期智在這篇論文中，主要是為 Ron Lavi、Or Sattath、Aviv Zohar 等 3 位以色列學者，在 2017 年所提出的“壟斷價格機制”（Monopolistic Price Mechanism）和“隨機取樣最優價格機制”（Random Sampling Optimal Price Mechanism, RSOP），提供了更多數學上的佐證和支援。
比特幣系統的現況與問題
在比特幣的世界裡，礦工如何通過挖礦得到獎勵，驅動起整個分散式帳本的交易驗證執行，是這個去中心化體系賴以運轉的最根本基礎。
而當今比特幣系統中的兩個主要問題就是：
（i）隨著區塊獎勵逐漸減少，礦工要如何獲得足夠的收入；
（ii）區塊容量上限而導致的吞吐量限制。
更具體的說，目前礦工挖礦的主要動機仍是取得區塊獎勵，也就是比特幣。
這真正暴露出的問題是，截至目前為止，比特幣仍然遠未實現其成為世界貨幣的使命，在這一公開帳本上，真正的經濟交易活動少之又少，無法產生足夠的手續費來獎勵礦工。所有礦工挖礦的目的都只是為了獲取區塊獎勵，因此當幣價下跌，整個系統就隨之崩潰。
但區塊獎勵機制是每 4 年會減少一半。因此，長遠來說，交易費機制才是礦工收入的主要來源，並是整個比特幣世界是否穩定安全的決定性因素。
(來源：arXiv)
重構比特幣的費率市場：MP 和 RSOP 制
也就是說，比特幣的未來要走下去，一定要發展出手續費取代挖礦獎勵的穩定機制。
為此，Ron Lavi 等人在 2017 年《重構比特幣的費率市場》（Redesigning Bitcoin’s fee market）一文中，提出了兩項創新的比特幣費率機制設計構想，希望能夠改善礦工的收益。
(來源：arXiv)
首先，我們需要了解的是，在比特幣交易市場中有兩種參與者：
（1）需要在比特幣系統中進行認證和註冊交易記錄的使用者；
（2）建立新區塊以打包交易並進行認證的礦工。
每個使用者會提出其交易願意所支付的最大金額，而礦工則使用一種機制來決定要打包哪些交易並向每個使用者收取多少費用。
比特幣系統的安全性來自於大批誠實礦工所提供的算力。Ron Lavi 等人認為，現有的比特幣費率機制是採用“競價”（pay your bid）拍賣制，以此現有的交易手續費市場來看，除非區塊堵塞，否則礦工並不能得到很好的收益。
而這一點與區塊鏈擴充套件性（scalability）的議題也有關聯，因為如果區塊容量變大，可能導致交易費收入進一步下降，這限制了區塊鏈系統設計者在區塊容量上可以調整的空間。
因此，Ron Lavi 等人提出了兩個替代性的拍賣制：“壟斷價格機制”（Monopolistic Price Mechanism）和“隨機取樣最優價格機制”（Random Sampling Optimal Price Mechanism, RSOP）。
壟斷價格機制（Monopolistic Price Mechanism）根據以下規則運作：
- 每項交易明確定出願意支付的最高手續費金額
- 礦工可以選擇在其區塊中打包進哪些交易
- 區塊中的所有交易都支付相同費率，此費率按區塊內的最低出價金額而定
- 礦工理應選擇可以將其收益極大化的交易，也就是交易數量與最低出價金額相乘後的最大數字。
以壟斷價格機制來說，礦工選擇區塊中被接受交易的數量。而在這些被納入區塊中的交易中，哪一筆交易所提出的手續費金額最低，那麼所有交易都一律支付這一金額。這個機制讓區塊的容量可以動態調整。
壟斷價格（MP）機制是一種自然而實用的機制，儘管並非嚴格意義上的激勵相容。他們的廣泛模擬結果顯示，這個機制在多數獨立同分布的情況下，都不會太過偏離激勵相容。也對某種有限大小下離散分佈的特殊情況進行了分析。
Ron Lavi 等人認為，MP 制可能是“競價”（pay your bid）拍賣制以外的一個很好選擇，因為後者有著出價低與收益低的問題。他們也推測，MP 制在一般獨立同分布的情況下，應該是接近激勵相容的。
“隨機取樣最優價格機制”（Random Sampling Optimal Price Mechanism, RSOP）根據以下規則運作：
- 將每個區塊中的交易隨機分派為兩組
- 運算出每一組的壟斷價格
- 將每一組算出的價格用於相對的另一組（亦即，只有在對應組中出價高於壟斷價格的交易才會被接受，並一律支付相同價格）
這一做法的訴求仍然是要取得某個接近壟斷價格的金額，但主要區別在於這（通過設計）消除了單一交易對手續費支付價格的影響，因為使用者需支付多少手續費都是由對應組來決定的。儘管這仍然無法完全避免任何價格操縱的可能性，但推測情況應該並不嚴重。
Ron Lavi 等人的貢獻是，他們在這篇論文中提出了一個概念架構，用拍賣理論去決定哪個交易可以被打包進各個區塊。其主要貢獻是提案與分析這兩種以拍賣為基礎的手續費市場機制。這兩種機制從根本上將手續費與區塊容量的問題脫鉤開來，讓我們可以更自由地根據其它安全性考量來決定區塊大小。
這兩種機制同時有以下三個好處：
（1）從系統使用者手中收取到高收益（這也意味著這一協定擁有高安全性）；
（2）激勵礦工扮演賣家的角色，遵循協定；
（3）簡化交易發行。
同時，兩種機制都鼓勵參與者直接地表達出他們真實意願——在這個情況下來說，就是直接表明他們願意為交易支付多少手續費。今日的比特幣錢包，其費率估算機制必須衡量當下的堵塞程度來採用不同的交易手續費。而若是根據 Ron Lavi 等人提出的機制，則錢包程式可以不受外在情況或其他人行為因素的影響獨立運作。
運用理論電腦科學證明 MP 制接近激勵相容
不過，Ron Lavi 等人所提出的只是一個概念架構，儘管 3 人在研究中進行了模擬和分析，仍不足以展現出其所提出的創新機制是確實可用的。
事實上，他們 3 人繼 2017 年 9 月發表這篇論文、11 月並在美國斯坦福大學舉行的 Scaling Bitcoin 第四屆研討會上發表研究成果後，似乎仍未引起太多關注。學術界並沒有太多後續討論該如何進一步完善並應用這兩種創新機制。根據 arXiv.org1 線上預印本資料庫網站顯示，至今僅有 2 筆引用紀錄。
然而，在《部分比特幣費率設計的激勵分析》一文中，姚期智卻特地對上述兩個機制進行研究，並通過理論電腦科學的分析，為期提供了數學上的支援與佐證。
(來源：arXiv)
姚期智首先指出，儘管 MP 不是嚴格的激勵相容，但 Ron Lavi 等人研究了這個機制在獨立同分布（Independent and identically distributed, IID）的情況下能夠多接近激勵相容。而他們基於廣泛模擬和一些分析工作，猜測這一機制是接近激勵相容的。
激勵相容（incentive compatible, IC）在比特幣費率機制中是一個很重要的概念。在機制設計理論中，激勵相容係指若所有的參與者都能依機制誠實揭示任何被要求的私有資訊時，那麼就會得到最好的成果。
因此，如何設計出一個比特幣的費率機制，讓礦工可以從系統使用者身上更好地獲得收益，且是接近激勵相容的，而使用者也可以誠實地將每筆交易手續費價格設定在自己願意支付的金額。這就是讓手續費可以逐步取代區塊獎勵，推動比特幣（乃至於所有加密貨幣）提升流通性的極大關鍵。
(來源：arXiv)
姚期智及其研究團隊通過數學分析，進一步證明了 MP 制確實是接近激勵相容，並且在任何隨著使用者數量增長下的獨立同分布情況下都是如此。
典型的激勵相容標準只能處理一種攻擊，也就是不誠實的競價。但比特幣使用者還可能進行“多重策略競價”（multiple strategic bids）等其它型別攻擊。也就是一名使用者可能會將他的交易拆分成幾個不同交易，分開競價。這個方式甚至可以讓一個原本失敗的交易被納入區塊。
而這篇論文中也證明了 MP 制即使是在面臨多重策略競價等其它攻擊出現的情況下，依然是激勵相容的。
同時，姚期智也探討了 RSOP 制。他與研究團隊證明了，正如 Ron Lavi 等人所推測的，RSOP 收益必然會依照 MP 收益而定。
這些結果，為 MP 製作為比特幣交易費制度的一個方案，提供了佐證與支援。
姚期智：理論電腦科學可以成為區塊鏈系統設計的有用工具
姚期智一文的貢獻可以分為兩個層面。第一，這篇論文證明了壟斷價格機制是接近激勵相容的。且在多重策略競價（MSB）攻擊下依然如此。同時，該文結果也顯示出，壟斷價格可以決定隨機取樣最優價格式拍賣的收益價格。這些結果為壟斷價格作為比特幣費率設計的一種方案，提供了支援。
第二，姚期智研究團隊在證明中所採用的研究方法，運用了精密的數學分析。他特別強調，這展現出理論電腦科學（theoretical computer science）可以成為區塊鏈系統設計的一個有用工具。
最後，姚期智研究團隊也認為，激勵相容區塊鏈設計這個新興領域，是一個令人興奮的研究領域，有著許多吸引人的問題等待解決，對於理論科學家，對於系統設計者來說都是如此。
參考：
[1] Andrew Chi-Chih Yao,“An Incentive Analysis of some Bitcoin Fee Designs”, Nov 11, 2018, ofollow,noindex"> https:// arxiv.org/abs/1811.0235 1
[2] Ron Lavi, Or Sattath, Aviv Zohar,“Redesigning Bitcoin's fee market”Sep 26, 2017, https:// arxiv.org/abs/1709.0888 1