Graphene: A New Protocol for Block Propagation

今天來為大家介紹這個名為Graphene - 的新區塊廣播協議。這個協議是在去年十一月份的比特幣擴容大會上，由UMASS的教授Brian Levine所發表的，在他發表之後也在Reddit等論壇上引起廣大的迴響和討論。今天我在這裡簡單整理他的報告內容，讓大家理解這個十分突破性的想法提案。

_{Image Source}

Problem Definition

在探討這個新的Protocal之前，我們要先搞清楚他要解決（優化）的內容是什麼。
我們知道，在比特幣「共識層」的運作過程中，當一個礦工節點成功的解開了PoW問題之後，它便有權力打包並且廣播一個區塊給所有其他的節點。若是大家都同意這個新的區塊，就會以它為最新區塊開始重新找下一個區塊。在這個過程中，一個新的區塊如何被廣播到所有的節點手中，就是所謂的傳播協議(Propagation Protocal)。

目前比特幣所使用的Protocal就是最直觀的方式：當節點Alice收到一個新的Block而準備要傳遞給Bob時，他傳送一整個完整的區塊，包含了所有的交易細目，如下圖所示：
_{(Source of all Images: Brian Levine's Presentation @ Scaling Bitcoin)}

這個方法乍看之下很合理，但如果仔細想想，是非常浪費頻寬的。為什麼呢？因為比特幣的網路中，所有節點之間其實有著某種「默契」：每個節點都會自己有一個mempool，存放了所有尚未被打包的交易，並且隨時與全網路同步。也就是說，絕大多數的節點的mempool都是相同的，每一筆交易細目大家也都知道，真正Block Propagation的過程中我們要傳遞的訊息只有「哪筆交易已被打包入這個新區塊中」而已。那麼如果Alice還在傳遞是告訴Bob每一筆交易的細目，是不是太多嘴了一點呢？

（注意：Block Propagation主旨在優化節點接溝通效率，並非減少最終區塊大小。）

這就是為什麼Block Propagation會是一個討論議題的原因。在區塊鏈世界中所有節點99%有著相同的資訊，因此在溝通上可以用很多方式簡化過程。接下來我們就一步一步介紹各種協議，以及Graphene是如何誕生。

Protocal 1: Compact Blocks

Compact Blocks 這個協議很早就被提出了，應該是所有人看到這個問題最直接的想法：我們只傳送新區塊中所有的Transaction ID （TxID），而不要傳送整筆交易。甚至，我們不需要傳送完整的TxID，只要傳送Hash ID的前幾個Bytes 就可以了（只傳送前六個Bytes就可以將碰撞機率降至一兆分之一）

只要實踐Compact Block就可以大量減少傳輸壓力，因此接下來的優化中也會以Compact Blocks的表現當作一個基準：

Proposal 2: Bloom Filter

Bloom Filter是一個簡單的檢測概念，他就是好像一個過濾器一樣，能夠幫助我們驗證一個大集合S中，我們想要選取哪個子集合。它的運作過程可以用一個簡單的二元陣列來描述：

• 首先，想要傳遞訊息的Alice，要把我們要的選擇的交易一筆一筆「放入」這個過濾器中：
  假如現在我們想要放入tx1，我們就讓tx1的值通過定義好的兩個函數，各輸出一個整數，如下圖中產出1,4，我們就將這個陣列（也就是過濾器）中的1, 4項由0變成1。
  
  接著假設我們還要放入tx2，所以我們透過一樣的方法，產生兩個值：0、4，並且一樣把Filter中的0跟4換成1。
  
  等我們重複這個過程放入所有交易之後，我們便可以把這個過濾器傳送給我們的朋友Bob，由於我們只需要傳送一個Binary Array，因此大小可以大幅度減少。

• 當Bob收到這個Filter之後，他便將他手中(mempool裡)的全部交易一一通過這個過濾器，看看哪些交易會「通過」這個過濾器，就帶表是Alice所想要傳達的交易了：例如當Bob也將tx1通過兩個函數後，他也會得到1、4，因為Filter中的1、4都是1，因此Bob可以「大概」確定tx1是被選重的交易之一。

為什麼是「大概」確定呢？看完上圖你應該會發現，最右邊的框框寫了一個False Positive，也就是「被誤認為合法交易」的情況。上圖中假設有一個tx4，產出0、1，由於Filter中0、1的位子都是1，所以他會被「誤認」為選中的交易之一。

這個情況其實不會太難解決，我們只要增長我們的Filter，就可以有效的降低False Positive的機率(FPR)。假設m是mempool大小（上圖情境中），傳遞者Alice設定過濾器的FPR(錯誤機率) = 1/m的話，這個Filter傳給Bob之後發生的錯誤期望值是

E(error) = m(筆交易) * 1/m(錯誤機率) = 1

也就是每次會有一筆交易被誤認。這個期望值是很高的，代表我們每次傳送都會出錯，因此實際上非常不可行。但如果我們把FPR設為1/(100m)的時候，也就是錯誤率變成每一百次傳遞出錯一次，似乎還算可以接受，不過這樣也代表著我們把我們的過濾器大小放大了一百倍，在減少傳輸資料量上，就不再有明顯的價值了。

Performance Compared to Compact Blocks

Protocal 3: Invertible Bloom Loopup Tables (IBLT)

上一個Bloom Filter如何再優化呢？IBLT是個更進階的資料結構，透過一樣的概念，把資料「壓縮」到一個比較小的資料結構當中來傳輸。對於IBLT的實行細節有點複雜這裡也不適合太深入，總之不是0、1這麼簡單，可以想像成多了一些計數器等等的表格架構。我們只要知道IBLT有一些相當不錯的優點：

• 兩個IBLT表格可以相減並得出差異：
  
• IBLT的大小與mempool無關，只跟我們「預計」mempool與block之間的大小差異有關。也就是只跟我們預計兩個要比較的集合大小差異有關。
  

在上圖中我們可以看到這樣一個協議的傳輸過程，但是這種模式在傳送IBLT時，如果mempool很大很大，充滿了等待被打包的交易，我們的IBLT就必須要變得更大，而在實際情況下這可能是個大到不可掌控。下圖中我們可以看到如果mempool size是10000，根本就變成個垃圾方法了！

Finally: Graphene Protocol

如果看到這裡，你已經想到如何結合Bloom Filter與IBLT的話，那就真的是天才，該受我一跪。記得剛剛說的，Bloom Filter會有我們可以預測的錯誤機率，而IBLT的大小由兩個集合的差異大小決定，Graphene就是利用這兩個特性做一個神奇的配合：

首先，我們先利用一個設定FPR = 1/m 的Bloom Filter來當作傳遞ID的主體。就如剛剛所說的，設定FPR=1/m代表我們可以估計在m個交易裡面會有一個被「誤會為選擇」的交易。因此Alice想傳達的交易，將會跟Bob解出的交易，差1。

也就是說，如果我們將Alice要傳達的交易也經過IBLT儲存，一併傳給Bob的話，那麼Bob在解開Filter的交易之後，如果也把這些交易做成一個IBLT，再兩者相減，就可以知道誰是那個「被誤會的交易(False Positive)」了！

由於我們可以預測兩個IBLT的原始陣列大小差距僅僅是1，所以這個IBLT也會非常小，讓我們總體傳遞訊息的大小壓的非常低。在Python模擬下，可以來到Compact Blocks的十分之一！

小結

這個協議到目前為止都還沒有被實踐，比特幣開發團隊也沒有表示會在未來生集中採用此種廣播協議，但是它所帶來的新的想法我覺得確實有造成幣圈轟動的力度。有些人提到Grapheme所忽的「排序」問題，我個人是認為不是一個太大的障礙，可以透過一些新的規則先把兩筆前後相關的交易綁在一起，或是用其他的方式定義交易順序，不會影響整體Graphene帶來的好處。

Block Propagation Protocal為什麼如此重要，是因為它決定了整個比特幣網路的溝通「效率」。越少的Data Flow必定帶來越低的延遲，而Graphene這種新的溝通協議在不會增加CPU負擔(太多)、不需要更多儲存空間、不需要增加來回溝通次數的情況下，能夠成功減少流量的消耗，我覺得是個十分成功也驚人的突破。

希望Graphene在未來幾個月內，能夠被新的區塊鏈採用或是納入更新。即便不是如此，我相信Graphene的提出也給了人們更多對於傳播協議升級的想像！

Reference

Paper : Graphene: A New Protocol for Block Propagation Using Set Reconciliation
YouTube: Brian Levine's Presentation at Scaling Bitcoin 2017