摘要：稀疏梅克爾樹在上文中我們已經(jīng)了解到一個(gè)交易的成功的前提是需要發(fā)送方提供關(guān)于一個(gè)的完整交易歷史。因此，中使用了一種稱為稀疏梅克爾樹，的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)交易數(shù)據(jù)，能夠在的時(shí)間復(fù)雜度驗(yàn)證一個(gè)交易不存在。

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

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

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

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

在 Plasma Cash 中，當(dāng)用戶向 Plasma 合約發(fā)送存款交易時(shí)，合約會(huì)生成一個(gè)與存款等值的 token，并給這個(gè) token 分配一個(gè)唯一的 ID。如果一個(gè)用戶分別執(zhí)行兩次存款操作，且每次存款都是 5 ETH，那么他將得到相等價(jià)值的兩個(gè)完全不同的 token。和 Plasma MVP 一樣，每次存款操作都會(huì)使得 Plasma 合約產(chǎn)生一個(gè)只包含這個(gè)存款交易的區(qū)塊。

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

從上面這個(gè)例子中我們可以看到，每個(gè)插槽記錄了其所對(duì)應(yīng)的 token 在當(dāng)前區(qū)塊中的交易狀態(tài)，所有存儲(chǔ)了某個(gè) token 的交易狀態(tài)的區(qū)塊按時(shí)間順序連在一起就構(gòu)成了這個(gè) token 的全部交易歷史。每當(dāng)一個(gè) token 被分配了一個(gè) id，之后的所有交易狀態(tài)都會(huì)被保存在每個(gè)區(qū)塊相同的插槽中，也不會(huì)被其它 token 取代。因此，用戶只需要關(guān)注每個(gè)區(qū)塊中存儲(chǔ)屬于自己的 token 的狀態(tài)，完全不用關(guān)心別的插槽存儲(chǔ)的內(nèi)容。

由于 Plasma Cash 中的節(jié)點(diǎn)只追蹤屬于自己的 token 的交易歷史，因此當(dāng)有交易發(fā)生時(shí)，token 的發(fā)送者要向接收者提供關(guān)于這個(gè) token 所有的交易歷史（從存款交易開始）以便接收者驗(yàn)證。從下圖（來源[[4]](https://github.com/ethsociety...）的例子中可以看到 4 個(gè)區(qū)塊中所記錄的 4 個(gè) token 的交易歷史。

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

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

SMT 實(shí)際上一點(diǎn)都不復(fù)雜，它的葉子節(jié)點(diǎn)是按數(shù)據(jù)集中的元素序號(hào)順序排列的。如果某個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的元素為空，那么該葉子節(jié)點(diǎn)將存儲(chǔ)一個(gè)特定的值（例如 0 的哈希值）。一個(gè)簡單的 SMT 示例如下圖（來源[[5]](https://medium.com/@kelvinfic...）所示。

擴(kuò)展到 Plasma Cash 中，SMT 的葉子節(jié)點(diǎn)對(duì)應(yīng)了區(qū)塊中給每個(gè) token 分配的插槽，按照每個(gè) token 的 ID 排序。每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)對(duì)應(yīng)的 token 的交易信息，如果 token 在這個(gè)區(qū)塊中沒有被交易，則相應(yīng)的葉子節(jié)點(diǎn)存儲(chǔ)的值為 null。

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

Plasma Cash 中的取款操作在流程上跟 Plasma MVP 大體相同，都要從提交取款申請開始，經(jīng)歷爭議期之后才能完成。由于 Plasma Cash 中采用的數(shù)據(jù)結(jié)構(gòu)不同，在取款時(shí)需要提交的 token 所有權(quán)證明不同，因此當(dāng)爭議發(fā)生時(shí)需要提交的爭議證明也不同。

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

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

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

已花費(fèi)證明。如果能證明正在取款的 token 已經(jīng)被花費(fèi)，那么取款立即被取消；

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

非法交易歷史證明。用戶還可以對(duì)正在取款的 token 的其它交易歷史提出爭議。這種爭議不會(huì)立刻阻斷取款，而是強(qiáng)制取款者提交其它交易證明來反駁爭議，如果沒有在規(guī)定時(shí)間內(nèi)反駁，則取款被取消。

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

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

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

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

Talk is cheap, show me your code.

目前已經(jīng)有許多機(jī)構(gòu)和公司已經(jīng)實(shí)現(xiàn)了 Plasma Cash，但實(shí)現(xiàn)的語言和細(xì)節(jié)有所不同：

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 的項(xiàng)目 Plasma Cash。Plasma Cash 給每個(gè)新轉(zhuǎn)移的 token 分配一個(gè)唯一的 token ID，并且用稀疏梅克爾樹存儲(chǔ)交易，使得用戶可以只關(guān)注跟自己的 token 有關(guān)的動(dòng)態(tài)，而不需要關(guān)注其它 token。Plasma Cash 可以被看作 Plasma 逐漸邁向成熟的一步，已經(jīng)有很多公司使用 Plasma Cash 搭建自己的平臺(tái)和應(yīng)用，例如 Loomnetwork 公司搭建了自己的 Plasma Cash 子鏈并且編寫了 SDK 支撐開發(fā)者在上面開發(fā)新的應(yīng)用。然而 Plasma Cash 本身仍然存在較多的問題，例如 token 無法被分隔合并、需要提交的證明過長等。在接下來的文章中還會(huì)繼續(xù)跟進(jìn) Plasma 最新的進(jìn)展。

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

本文的作者是蓋蓋，他的微信公眾號(hào): chainlab

深入淺出區(qū)塊鏈 - 系統(tǒng)學(xué)習(xí)區(qū)塊鏈，打造最好的區(qū)塊鏈技術(shù)博客。