Graphene - 新的區塊傳遞協議
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
好专业,感觉像学术论文一样。
是直接從發表會的內容截取出來的,所以performance視覺化等等看起來特別正式吧哈哈哈
很暈很暈.....我不知道能明白多少....但也感謝分享!!!
好像看文字比較無聊...建議你去聽聽他原本的介紹,有教授講課的感覺說不定比較好懂xD
听起来真的好神。
可以直接去看他的演講視頻,應該可以學到更多!
Great post! You've earned a 18.18% upvote from @dolphinbot
Join the DolphinBot Team for Daily Payouts in Steem! Click here: http://bit.ly/dolphinbot
You got a 10.09% upvote from @emperorofnaps courtesy of @antonsteemit!
Want to promote your posts too? Send 0.05+ SBD or STEEM to @emperorofnaps to receive a share of a full upvote every 2.4 hours...Then go relax and take a nap!
You got a 5.54% upvote from @redlambo courtesy of @antonsteemit! Make sure to use tag #redlambo to be considered for the curation post!
你好cn区点赞机器人 @cnbuddy 谢谢你对cn区的贡献。如果不想再收到我的留言,请回复“取消”。
Congratulations,
you just received a 54.26% upvote from @steemhq - Community Bot!
Wanna join and receive free upvotes yourself?
Vote for
steemhq.witness
on Steemit or directly on SteemConnect and join the Community Witness.This service was brought to you by SteemHQ.com