摘要：稀疏梅克爾樹在上文中我們已經了解到一個交易的成功的前提是需要發送方提供關于一個的完整交易歷史。因此，中使用了一種稱為稀疏梅克爾樹，的數據結構存儲交易數據，能夠在的時間復雜度驗證一個交易不存在。

本文首發于深入淺出區塊鏈社區
原文鏈接:深入理解Plasma（四）Plasma Cash原文已更新，請讀者前往原文閱讀

這一系列文章將圍繞以太坊的二層擴容框架 Plasma，介紹其基本運行原理，具體操作細節，安全性討論以及未來研究方向等。本篇文章主要介紹在 Plasma 框架下的項目 Plasma Cash。

在上一篇文章中我們已經理解了 Plasma 的最小實現 Plasma MVP 如何使用 UTXO 模型實現 Plasma 鏈下擴容的核心思想。但由于 Plasma MVP 本身過于簡單，并不能用于實際的生產環境中。2018 年 3 月，在巴黎舉行的以太坊開發者大會上，Vitalik 發布了 Plasma Cash 模型[[1]](https://ethresear.ch/t/plasma...，可以視為對 Plasma MVP 的改進。Plasma Cash 與 Plasma MVP 的主要區別是每次存款操作都會產生一個唯一的 coin ID 對應轉移到側鏈上的資產，并使用一種稱為稀疏梅克爾樹（Sparse Merkle Tree）的數據結構存儲交易歷史。由此帶來的好處是用戶不需要關注子鏈上的每個動態，只需要關注跟自己的 token 有關的動態。在下文中將介紹具體細節。

Plasma Cash 中的每次存款操作都會對應產生一個 NFT（non-fungible token）[[2]](https://en.wikipedia.org/wiki...。NFT 可以簡單理解為“不可互換的 token”，即每個 token 都是獨一無二的，由唯一的 ID 標記。以太坊官方為 NFT 提供了 ERC721 標準[[3]](http://erc721.org/)，在之前火爆到阻塞以太坊的 CryptoKitties 就是由 ERC721 合約實現的。

在 Plasma Cash 中，當用戶向 Plasma 合約發送存款交易時，合約會生成一個與存款等值的 token，并給這個 token 分配一個唯一的 ID。如果一個用戶分別執行兩次存款操作，且每次存款都是 5 ETH，那么他將得到相等價值的兩個完全不同的 token。和 Plasma MVP 一樣，每次存款操作都會使得 Plasma 合約產生一個只包含這個存款交易的區塊。

Plasma Cash 中的每個 token 都被分配唯一的 ID，因此可以按 ID 的順序存儲每個 token 的交易歷史。Plasma Cash 的區塊按 token ID 的順序給每個 token 分配了一個插槽（slot），每個插槽會記錄這個 token 是否被交易的信息。例如在下圖（來源[[4]](https://github.com/ethsociety...）的區塊中，包含 4 個 token，id 分別是 #1，#2，#3，#4。其中 #1，#2，#3 被標記為沒有被花費，而 #4 由用戶 A 發送給用戶 B。

從上面這個例子中我們可以看到，每個插槽記錄了其所對應的 token 在當前區塊中的交易狀態，所有存儲了某個 token 的交易狀態的區塊按時間順序連在一起就構成了這個 token 的全部交易歷史。每當一個 token 被分配了一個 id，之后的所有交易狀態都會被保存在每個區塊相同的插槽中，也不會被其它 token 取代。因此，用戶只需要關注每個區塊中存儲屬于自己的 token 的狀態，完全不用關心別的插槽存儲的內容。

由于 Plasma Cash 中的節點只追蹤屬于自己的 token 的交易歷史，因此當有交易發生時，token 的發送者要向接收者提供關于這個 token 所有的交易歷史（從存款交易開始）以便接收者驗證。從下圖（來源[[4]](https://github.com/ethsociety...）的例子中可以看到 4 個區塊中所記錄的 4 個 token 的交易歷史。

截止到區塊 #4，可以看到token #1 和 token #3 始終沒有被交易。token #2 在區塊 #2 被 E 發送給了 F，在區塊 #4 被 F 發送給了 G，在其它區塊沒有發生交易，token #2 的最終所有權歸 G。token #4 在區塊 #1 被 A 發送給了 B，在區塊 #3 被 B 發送給了 C，在其它區塊沒有發生交易，token #4 的最終所有權歸 C。F 為了向 G 證明 token #2 的合法性，需要向 G 提供 token #2 在前 4 個區塊中的所有交易歷史，也就是說不僅需要包括區塊 #2 中 E => F 的交易證明、區塊 #4中 F => G 的交易證明，還要包括在區塊 #1 和 #3 中沒有被交易的證明。到這里可能感覺有點奇怪，為什么還要包括沒有被交易的證明？這是為了防止雙花，因為 G 并不知道在區塊 #1 和 #3 中 token #2 是否被交易給了其它人。假如 F 在區塊 #3 中將 token #2 發送給了 H，并且對 G 隱瞞了這個交易，那么發生在區塊 #4 中的 F => G 就是非法（雙花）的。因此，在 Plasma Cash 中，完整且合法的交易歷史是一個 token 被安全交易的前提。

在上文中我們已經了解到一個交易的成功的前提是需要發送方提供關于一個 token 的完整交易歷史。完整的交易歷史既包括這個 token 在哪些區塊被交易的信息，也包括這個 token 在哪些區塊沒有被交易的信息。我們都知道，在區塊鏈中，使用梅克爾樹（Merkle Tree，MT）構造梅克爾證明（Merkel Proof, MP）可以在 O(logN)的時間復雜度驗證一個交易是否存在一個區塊中。但想要證明一個交易沒有存在一個區塊中，使用標準的梅克爾樹卻沒那么容易。因此，Plasma Cash 中使用了一種稱為稀疏梅克爾樹（Sparse Merkle Tree，SMT）的數據結構存儲交易數據，能夠在O(logN)的時間復雜度驗證一個交易不存在。

SMT 實際上一點都不復雜，它的葉子節點是按數據集中的元素序號順序排列的。如果某個葉子節點對應的元素為空，那么該葉子節點將存儲一個特定的值（例如 0 的哈希值）。一個簡單的 SMT 示例如下圖（來源[[5]](https://medium.com/@kelvinfic...）所示。

擴展到 Plasma Cash 中，SMT 的葉子節點對應了區塊中給每個 token 分配的插槽，按照每個 token 的 ID 排序。每個葉子節點存儲對應的 token 的交易信息，如果 token 在這個區塊中沒有被交易，則相應的葉子節點存儲的值為 null。

以上圖為例，如果需要證明交易 A 存在，就像在標準的 MT 中一樣，需要構造 MP：H(null) 和 H(H(null) + H(D))。如果需要證明 B 不存在，同樣很簡單，我們已經知道 B 的位置是第二個葉子節點，如果 B 不存在，那么該節點存儲的值應該為 null。因此就像在標準的 MT 中證明存在的 MP 一樣，只不過需要加上 H(null) 作為 MP 的一部分，即 MP：H(null)、H(A)和 H(H(null)+H(D))。

Plasma Cash 中的取款操作在流程上跟 Plasma MVP 大體相同，都要從提交取款申請開始，經歷爭議期之后才能完成。由于 Plasma Cash 中采用的數據結構不同，在取款時需要提交的 token 所有權證明不同，因此當爭議發生時需要提交的爭議證明也不同。

在向 Plasma 合約提交關于某個 token 的取款申請時，需要提供關于這個 token 最近的兩次交易證明。例如，在上圖中，假如 G 想要取走 token #2 到主鏈，那么他需要提交關于 F => G 以及 E => F 的 Merkle Proof。

取款者在提交了取款申請之后同樣需要支付一定的保證金，并等待一段時間的爭議期。在這期間如果有其它節點提交了有效的爭議證明，那么取款者不但無法完成取款操作，也會損失全部或部分的保證金。

目前 Plasma Cash 支持三種爭議證明，分別應對三種不同的攻擊場景（具體會在后文分析）：

已花費證明。如果能證明正在取款的 token 已經被花費，那么取款立即被取消；

雙花證明。如果能證明取款申請中提供的兩次交易證明中間還有別的交易，即發生了雙花，那么取款立即被取消；

非法交易歷史證明。用戶還可以對正在取款的 token 的其它交易歷史提出爭議。這種爭議不會立刻阻斷取款，而是強制取款者提交其它交易證明來反駁爭議，如果沒有在規定時間內反駁，則取款被取消。

在這一節將討論已有的 3 種攻擊場景以及如何構造爭議分別應對這些攻擊[[6]](https://karl.tech/plasma-cash...。在這里假設 Plasma Cash 中存在不可信的 operator 接收所有的交易并構造區塊。

如下圖（來源[[7]](https://github.com/loomnetwor...）所示，假設攻擊者 Alice 向 Bob 發送了一個 token A，且 Bob 已經驗證了 A 的交易歷史沒有問題，交易在區塊 N+X 得到確認。在這之后，Alice 立即提交取款申請，企圖將 token A 取回主鏈，并提交 A 在區塊 N 以及之前的交易證明。為了應對這種情況，Bob 必須及時發現 Alice 的取款行為，并且在爭議期結束前提交在區塊 N+X 中 token A 被 Alice 發送給 Bob 的證明。這里需要注意的是，如果 Bob 在區塊 N+Y 將 token A 發送給 Charlie 的交易是不能被當做爭議證明的，只有最接近被爭議的交易的下一個交易證明有效。

雙花攻擊需要 operator 配合，將含有已經被花費的 token 的交易打包入下一個區塊中。如下圖所示（來源[[7]](https://github.com/loomnetwor...），攻擊者 Alice 和 Charlie 是同謀，Alice 向 Bob 發送一個 token A 在區塊 N+X 被確認，之后 Alice 又將 token A 發送給 Charlie，并在區塊 N+Y 被確認。這時在主鏈看來，Bob 和 Charlie 都是 token A 的合法擁有者。接下來，Charlie 立即提交取款申請，企圖取走 token A。Bob 為了防止自己的 token 被盜，可以在爭議期內提交在區塊 N+X 被確認的交易，表明自己在 Charlie 之前已經擁有了 token A。

這種攻擊需要聯合比較多的同謀者。如下圖所示，Alice 在區塊 N 擁有 token A。Bob 聯合 operator、Charlie 以及 Dylan 企圖盜走 Alice 的 token。首先，operator 偽造 Alice 將 token A 發送給 Bob 的交易，并在區塊 N+X 得到確認，之后 Bob 將 token 發送給 Charlie，在區塊 N+Y 確認。同樣地，Charlie 接著將 token 發送給 Dylan，在區塊 N+Z 確認。這是，Dylan 提出取款申請，企圖取走 token A。Dylan 用于取款申請的兩個交易證明 Charlie => Dylan 和 Bob => Charlie 都是合法的，但 token A 的交易歷史中有一部分是偽造的。Alice 為了證明自己是 token A 的最新合法擁有者，可以提出爭議，要求 Dylan 提供 Alice => Bob 的交易證明，同時 Alice 需要提交一部分保證金（否則任何人都可以隨便提出爭議）。Dylan 必須在一定的時間內提供合法的交易證明，否則取款失效。

Talk is cheap, show me your code.

目前已經有許多機構和公司已經實現了 Plasma Cash，但實現的語言和細節有所不同：

Loom Network [[8]](https://github.com/loomnetwor...

Omisego [[9]](https://github.com/omisego/pl...

Wolk [[10]](https://github.com/wolkdb/dee...

Lucidity [[11]](https://github.com/lucidityte...

本篇介紹了 Plasma 框架下的基于 NFT 的項目 Plasma Cash。Plasma Cash 給每個新轉移的 token 分配一個唯一的 token ID，并且用稀疏梅克爾樹存儲交易，使得用戶可以只關注跟自己的 token 有關的動態，而不需要關注其它 token。Plasma Cash 可以被看作 Plasma 逐漸邁向成熟的一步，已經有很多公司使用 Plasma Cash 搭建自己的平臺和應用，例如 Loomnetwork 公司搭建了自己的 Plasma Cash 子鏈并且編寫了 SDK 支撐開發者在上面開發新的應用。然而 Plasma Cash 本身仍然存在較多的問題，例如 token 無法被分隔合并、需要提交的證明過長等。在接下來的文章中還會繼續跟進 Plasma 最新的進展。

https://ethresear.ch/t/plasma-cash-plasma-with-much-less-per-user-data-checking/1298

https://en.wikipedia.org/wiki/Non-fungible_token

http://erc721.org/

https://github.com/ethsociety/learn-plasma

https://medium.com/@kelvinfichter/whats-a-sparse-merkle-tree-acda70aeb837

https://karl.tech/plasma-cash-simple-spec/

https://github.com/loomnetwork/plasma-paper/blob/master/plasma_cash.pdf

https://github.com/loomnetwork/plasma-cash

https://github.com/omisego/plasma-cash

https://github.com/wolkdb/deepblockchains/tree/master/Plasmacash

https://github.com/luciditytech/lucidity-plasma-cash

本文的作者是蓋蓋，他的微信公眾號: chainlab

深入淺出區塊鏈 - 系統學習區塊鏈，打造最好的區塊鏈技術博客。