什麼是比特幣默克爾化抽象語法樹？

以太坊爱好者｜2021-09-02 10:51

默克爾化抽象語法樹（Merklized Abstract Syntax Trees, MAST）是一項為比特幣提議的升級，可以實現更小的交易體積、更好的隱私性，以及更大的智能合約。在本文中，我們會解釋MAST 的基本原理，講解其潛在好處，並總結目前一些包含這項技術的提案。問題：沒用到的腳本數據

默克爾化抽象語法樹（Merklized Abstract Syntax Trees, MAST）是一項為比特幣提議的升級，可以實現更小的交易體積、更好的隱私性，以及更大的智能合約。在本文中，我們會解釋MAST 的基本原理，講解其潛在好處，並總結目前一些包含這項技術的提案。

問題：沒用到的腳本數據

中本聰給了比特幣一個有趣的特性，是他沒有寫在比特幣白皮書裡的。除了可以通過公鑰來接收比特幣、用私鑰數字簽名來花費比特幣，用戶還可以編寫程序（叫做“script”，腳本），當成動態的公鑰和簽名來用。

當你指定一個腳本後—— 這在每一種比特幣錢包裡都是基本操作—— 由比特幣網絡強制執行的比特幣協議就不會讓任何人花費這個腳本所控制的比特幣，除非腳本返回True。這讓你可以指定資金的花費條件，稱為“encumbrances”（財產條件），比如要求花費的交易一定要得到你的私鑰簽名。

更加複雜的財產條件也是有可能實現的，比如下面這個例子，我們會用它貫穿整篇文章：Alice 希望能夠隨時花費她的比特幣，但如果她連續三個月沒有花費自己的比特幣（可能因為身故或者喪失行為能力），她希望自己的兄弟姐妹Bob 和Charlie 擁有自己的比特幣，在任何兩人能達成一致的地方使用這些財產。

下面這個條件腳本就實現了上文所說的目標，它不僅納入了Alice 的公鑰（需要驗證一個來自她私鑰的簽名），但也加入了以下條件性邏輯：一個超時條件，以及Bob 和Charlie 的公鑰。

在當前的比特幣協議中，上述所有的數據都必須添加到區塊鏈中，在Alice 的比特幣花費的時候，也包括在特定的花費行為中完全無關的腳本部分，也要曝光。就比如在Alice 花費自己的比特幣時Bob 和Charlie 的公鑰也要曝光。

未使用的條件數據增大了交易的體積，也使用戶在必要之外曝光了更多的隱私，同時，也使體積而非驗證代價成為智能合約大小的主要限制因素。 MAST 旨在改善這些情況，辦法就是移除在區塊鏈上直接包含未使用的腳本部分的需要。

MAST 初始構想

MAST 1 背後的觀念來自於兩種久已存在的概念，抽象語義樹和默克爾樹。抽象語義樹（AST）是一種通過將一個程序分割成獨立的小塊來描述程序的方法，這樣會讓程序變得更容易分析和優化。為了生成一個AST，你需要把所有的方程與其前提用箭頭連接起來，直至所有的前提都被找出。下圖即是上文示例腳本的AST。

另一方面，默克爾樹則可用來驗證某個元素是否是屬於某個集合，且無需知曉整個集合的全貌。舉個例子，比特幣的簡易支付驗證錢包（SPV wallet）就使用默克爾樹來驗證某筆交易是否存在於某個區塊中，這樣無需下載完整的區塊，可以節省帶寬。

要生成一棵默克爾樹，先要把每個元素都各自哈希一次，生成各自唯一的標識符；然後這些標識符配對之後再次哈希，生成這一對標識符的標識符；如此不斷重複，直至只剩下一個標識符，稱為“默克爾根”，它就是一個短小精悍、但是標記了整個集合的標識符了。

在驗證某個元素屬不屬於某個集合時，擁有整個集合的人可以向你提供從那個元素到默克爾根路徑上的所有標識符。這樣就能證明，這個元素確實在這個集合內。

簡而言之，AST 背後的技術讓你可以把一個程序分成多個小塊，而默克爾樹讓我們可以驗證這些小塊確實是一個完整程序的一部分，且不必暴露整個程序。這就是MAST 的基本原理，可以讓花費者用一個默克爾證明來替換在單次交易中沒有用到的條件—— 減少交易體積、提高隱私性，並支持更大的合約。

MAST 的一個例子

我們以上文的財產條件為例，為我們希望的兩種可能場景分割為兩個子腳本：

Alice 可以隨時花費自己的比特幣（左邊的子腳本）或者，如果連續三個月使用Alice 的簽名來花費，則需要Bob 和Charlie 的簽名來花費此中的比特幣（下圖右邊的子腳本）

基於這兩個獨立的子腳本，創建一棵默克爾樹：

這棵默克爾樹的樹根最終標識了Alice 的完整財產條件，而且只有32 字節的體積。此後，Alice 可以使用一個替代性的條件腳本，聲明：一筆花費交易，只有提供其中一個子腳本連接到默克爾根的證據、並且子程序返回True 的時候，才是有效的。

子腳本的默克爾證據，形像地畫出來會像下圖這樣，就看用的是哪個子腳本了：

好處#1 —— 更小的交易

我們先來看看MAST 如何能讓複雜財產條件的用戶創建更小的交易。這是MAST 給我們帶來的第一個好處。

在上文的例子中，我們使用了一個具備兩個子腳本的財產條：要么Alice 自己花自己的錢，要么Bob 和Charlie 在等待三個月之後一起花她的錢。我們來設想一個無限延伸的版本：其第三個子腳本指明，三個月零一天后，Dan 和Edith 可以花費此中的資金；第四個子腳本指明，三個月零二天后，Fred 和George 可以使用這筆資金；等等等等

這個思維實驗可以使我們得到下面的這張圖，它顯示了，子腳本的數量與需要加入區塊的條件數據量，在有和沒有MAST 時候的關係。

下面是一個對數圖，意思是一樣的：

雖然一開始MAST 交易的體積會比沒有MAST 的同條件交易更大，比如我們的兩個子腳本的條件，但非MAST 的交易體積會（隨子腳本的數量）線性增大，而MAST 交易的體積則只會

對數增大

。

如果節省數據量是主要目標，我們還可以進一步優化。對於許多財產條件來說，花費者可能更高頻地使用其中某個條件。比如，Alice 希望自己高壽，所以她建構的默克爾樹把自己花費的條件放在離頂端更近的地方，而所有其它條件都放在樹的底部：

這樣設計的話，不同情況下的MAST 默克爾證據的體積是不一樣的，在最理想的情況下，Alice 活著，自己花自己的錢；而另一種情況下，Alice 身故，她的受益人來花這些錢。我們把這些因素呈現到圖上。

可以看出，Alice 使用時，其交易的數據量一直是最優的情形，無論她的財產條件中的受益人有多少個；而在她的受益人使用這筆資金時，交易的數據量也只比前述標準構造的默克爾樹多用幾個字節。

無論Alice 選擇什麼安排，可以看出MAST 可以讓多子腳本的財產條件交易體積更小，因此用戶可以少付一些手續費，而區塊裡可以裝入更多的高級交易。

好處#2 —— 更強的隱私性

我們在上文的講解中，把Alice 的財產腳本全部曝光了出來，但你可以設想，如果在Alice 花費自己的比特幣時，你在區塊鏈上僅僅看到了下圖左邊的數據：

只有這些信息，你是沒法知道Alice 以外是否還有人能花費這裡的資金、以及他們花費是需要面對什麼約束條件的。你可以從MAST 中猜測可能有一些別的條件，但也僅限於猜測而已—— Alice 可能只是假裝她的默克爾樹還有其它可以花費的部分。

對應地，如果你看到的是另一個分支（也就是上圖的右邊的子腳本），你不會知道這筆資金在超時之前是否能花費，也不知道是不是只需一把私鑰就能花費它。你同樣可以猜測存在其它的花費條件，但你沒法在區塊鏈上確證這一點。

保證未使用的財產條件不曝光在某些時候非常有用，比如某些商人可能希望自己的智能合約盡可能保密，不要被潛在的競爭對手看到。這一點與某些標榜自己是專為智能合約設計、但實際上又不能為這些合約提供隱私性的山寨幣恰好相反。

隱私性也可以為所有的比特幣用戶提供額外的好處，即使某些用戶根本不在乎財產條件的隱私性。假設從本文一開始，Alice 就是唯一一個使用非MAST 條件模板的人。因為所有條件都是公開的，那麼任何人都可以跟踪Alice 的花費行為，只需在區塊鏈上觀察這個模板被使用的情形即可，這樣Alice 的隱私就蕩然無存。

任何讓識別特定用戶更容易的設計，也會讓人們可以更容易地區別對待他們的比特幣和別人的比特幣，這叫做“同質性的缺失”。如果某些人知道了Alice 的財產條件長什麼樣，他們就可以賄賂或者強迫礦工不要打包這些人的交易，以此阻止Alice 使用自己的比特幣。

MAST 不能完全解決這個問題，因為Alice（或者Bob 和Charlie）仍然需要揭示部分的產權負擔，但是許多別的複雜財產條件可以解析成少量的簡單MAST 類型條件。

舉個例子，Alice 的默認花費行為看起來就像其它只需提供單簽名的普通支付行為，所以Alice 的基於MAST 的交易跟其它基於MAST 的單簽名交易就沒有任何分別。這反過來提高了Alice 的隱私性，也提高了她的資金的同質性，以及所有使用基於MAST 的單簽名條件的用戶的貨幣同質性。

MAST 的這一好處還很有可能與其他提高比特幣隱私性和同質性的提議結合在一起。有些提議是讓某些複雜的財產條件可以用單簽名來使用，比如Pieter Wuille 和Gregory Maxwell 的“

通用門限樹

”、Andrew Poelstra 的

“無腳本式腳本”

，還用Thaddeus Dryja 的

“離散對數合約”

；MAST 就可以和這些方案相結合。

但即使這些方案都不能在比特幣上實現，MAST 自身也能為複雜財產條件的用戶提供更多的隱私性和可互換性，不論是與當前相比，還是與支持用戶自定義智能合約的山寨幣相比。

好處#3 —— 更大的智能合約

比特幣現在為單個腳本設置了三種不同的體積限制：裸露腳本大小不能超過1 萬字節，在2010 年7 月引入；P2SH 腳本不能超過520 字節；segwit 腳本不能超過1 萬字節。我們把這幾個大小在上面的圖中展示出來：

可以看出來，即使是極端的無限延長的例子，MAST 也比當前所有的機制支持更多的條件分支。實際上，MAST 的擴展性非常之好，以至於即使你擁有現在可觀測的宇宙中所有的能量，若是只用來創建一棵標準（平衡）的默克爾樹，其默克爾證據也只有8448 字節。即使是這麼大的默克爾證據，任何現在的筆記本電腦，都能在1 毫秒之內完成驗證。

因為免去了全節點處理未使用的子腳本的任務，MAST 還能幫比特幣腳本繞過別的一些硬性限制。在這一方面，MAST 很好地保存和延伸了比特幣智能合約長期的設計目標，也就是合約的負擔應盡可能由合約的參與者承擔，而節點付出了帶寬、內存和處理能力，卻無法得到補償，因此應盡可能少承擔。

所以，MAST 的真正成就不是讓比特幣用戶可以創建（比以往）更加高級的合約，而是它打開了這種可能性，還不會給比特幣的節點增加新的負擔。

實現MAST：現有的多種提議

迄今為止，bitcoin-dev 郵件組裡提出了兩種方法在比特幣協議中啟用MAST，兩種方法都仍在草案階段，可能會有所變更。

第一種提議是Johnson Lau（化名“jl2012”）提出的

BIP114

，使用了一個基於隔離見證的延伸特性，使得原生的隔離見證地址（

bech32

）可以成為對MAST 財產條件的默克爾根的承諾。花費交易因此可以從樹上選擇一個子腳本。

第二種提議是Mark Friedenbach（化名“maaku”）提出的兩個未命名的BIP（

、

），它提高了腳本語言的靈活性，使得編程者可以編寫腳本來驗證基於MAST 的財產條件。如果用Friedenbach 更喜歡的方式來實現，那會讓比特幣現在支持的三種腳本類型（裸露腳本、P2SH 和隔離見證腳本）都可以使用默克爾證據。