作者: David A. Harding
翻譯: 阿劍
默克爾化抽象語法樹（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（1、2），它提高了腳本語言的靈活性，使得編程者可以編寫腳本來驗證基于 MAST 的財產條件。如果用 Friedenbach 更喜歡的方式來實現，那會讓比特幣現在支持的三種腳本類型（裸露腳本、P2SH 和隔離見證腳本）都可以使用默克爾證據，
這幾種提議互有短長，但都提供了上文所說的 MAST 的好處（字節數可能有加有減），每一個都可以用軟分叉來激活，
結論：我們什么時候才能用上 MAST？
上文我們講解了 MAST 的好處，也簡要提及了兩種在比特幣上實現 MAST 的提案，你可能也好奇，什么時候我們能用上 MAST，遺憾的是，我也不知道，
從理念，到提案，到完整的實現，到提議軟分叉，到激活軟分叉，道阻且長。圍繞隔離見證升級，為期兩年的大戲已經很清楚地展現了這一點。
但從我的角度看，MAST 背后的基本理念已經在比特幣技術社區中獲得了廣泛的支持，而對 MAST 最感興趣的開發者也會繼續開發，除非有人能證明這種技術完全不靠譜，有朝一日這些開發者成功提出可供同行審議的軟分叉代碼，就輪到讀者你們和其他比特幣用戶，來決定 MAST 是否能成為比特幣協議的一部分了。
致謝
感謝 Mark Friedenbach、Jimmy Song 和 John Newbery 對本文草稿的評論。當然，文中出現的所有謬誤，都屬于我的責任。
腳注
- Russell O’Connor 被公認為是第一個描述了 MAST 雛形的人，有些來源則還會加上 Pieter Wuille，來源：Peter Todd、Gregory Maxwell（由 Jeremy Rubin 等人引用） 和 Mark Friedenbach（在私人通信中）。
感謝 John Newbery，
根據自由創作-分享協議 4.0，保留署名權，且在后續分享和改編中應維持同樣的要求，
