為了了解tangle是什么東西,我們得先了解什么叫有向圖。
有向圖是點(diǎn)(下圖中有數(shù)字的方格)還有邊(下圖箭頭線)的集合
其中Tangle是IOTA的資料結(jié)構(gòu)(像以太和比特幣都是區(qū)塊鏈的資料結(jié)構(gòu)),Tangle是一種特殊的有向圖。Tangle上面保存了交易。每筆交易由一個點(diǎn)代表(vertex)。當(dāng)一個新的交易要加入Tangle。他必須驗(yàn)證之前Tangle上的兩個交易,每個驗(yàn)證會增加一個邊(edge),所以加入一筆交易,會在Tangle上增加兩個邊。
用同樣一個例子來解說
像在上面的Tangle中,交易5驗(yàn)證了交易2交易3,然后交易5又被交易6驗(yàn)證。在這篇文章暫時還不會討論驗(yàn)證的詳細(xì)過程,目前只要當(dāng)作驗(yàn)證是確認(rèn)上一筆交易有沒有花超過該帳戶余額就好了。
我們稱呼還沒被驗(yàn)證的交易叫做tips(畢竟他會在整個Tangle末端的地方)。像上圖交易6就是一個tip。每一個新產(chǎn)生的交易都需要驗(yàn)證兩筆tips的交易(至少至少至少要一個)。選擇需要被驗(yàn)證的tips的演算法是IOTA技術(shù)的特色。
但為了循序漸進(jìn),我們會從最簡單的方法開始: 我們隨機(jī)抽取任意兩個tips,并且每個tip 被抽到的機(jī)率都是相等的。
為了展示tangle在這種隨機(jī)抽取策略(講得比較專業(yè)一點(diǎn)叫“uniform random tip selection”)下tangle會長什么樣子,IOTA Foundation做了動畫模擬展示。這個模擬隨機(jī)產(chǎn)生了一個tangle,這個隨機(jī)的tangle會由一個創(chuàng)世區(qū)塊(genesis)開始。在這個展示中,最左邊是創(chuàng)世區(qū)塊,最右邊是最新的交易(tips)。tips會以灰色表示。當(dāng)滑鼠滑到任何一筆交易上面的時候,被當(dāng)下交易驗(yàn)證的交易會以紅色表示,驗(yàn)證當(dāng)下交易的交易會以藍(lán)色表示。
在上面的模擬中,你或許已經(jīng)注意到交易并不平均分散在各個時間,而是在某些時間會特別的「繁忙」。這個讓模型更加真實(shí)的隨機(jī)方式,是使用帕松過程去模擬交易抵達(dá)而完成的。而這個模型在分析多少客戶在指定的時間段之中走進(jìn)商店,或者多少電話打進(jìn)客服中心的這些例子中非常普遍。我們可以于下圖中看到這個行為如何用在糾纏。交易4、5、以及6幾乎同時抵達(dá),而交易6之后有個長的中斷,暫時沒有新的交易發(fā)出來。
對我們的目標(biāo)來說,我們只需要知道一件關(guān)于帕松分布事情:平均而言,進(jìn)入的交易速度被設(shè)定為我們稱為λ的常數(shù)。例如,我們設(shè)定λ=2,交易量為100,則總模擬時間將會是50次每單位時間。試試看吧!
在開始之前,一件需要說明而更有趣的事情是;如果我們設(shè)定λ為非常小的數(shù)(例如0.1),則我們就可以得到「鏈」。一個交易不是認(rèn)可(approve)兩個,而是只認(rèn)可(approve)前一個交易長得像鏈的纏結(jié),這是因?yàn)榻灰讓⒆兟灾劣谌魏谓o定的時間內(nèi),只有一個端點(diǎn)(tip )去認(rèn)證。在另個極端狀況中,如果λ很大,所有的交易將抵達(dá)得很快,使得它們所見到的唯一的端點(diǎn)即是創(chuàng)始端點(diǎn)(創(chuàng)始交易所產(chǎn)生的端點(diǎn))。這就是模擬的限制:以一個很大的λ和固定的交易量,我們將在相當(dāng)短的時間段中進(jìn)行模擬。
非常小的 λ所生產(chǎn)的鏈
非常大的λ:只有創(chuàng)始端點(diǎn)是可見的
所以什么是交易看不「見」前一個端點(diǎn)呢?在模型中,我們讓每個交易它抵達(dá)后一定時段內(nèi)是不可見的(invisible)。我們使用字母h標(biāo)示延遲的時間長度。這個延遲表示該交易被準(zhǔn)備以及透過網(wǎng)路傳播的時間。在我們的模擬中,我們常常設(shè)定h=1。這代表我們只能在過去的每段單位時間內(nèi),認(rèn)可最少一次的交易。這個延遲不只是很務(wù)實(shí)的小細(xì)節(jié),也是纏結(jié)最基本的性質(zhì),如果沒有這個延遲的話,我們將得一個非常無聊的鏈。這個延遲是真實(shí)世界中,各個節(jié)點(diǎn)廣播通知彼此有新的交易出現(xiàn)所花費(fèi)的時間。加上這個參數(shù),也使得我們的糾纏和現(xiàn)實(shí)世界的狀況更加接近。
最后,來講更先進(jìn)的節(jié)點(diǎn)選擇演算法─「無權(quán)重隨機(jī)漫步」。使用這個算法,我們在創(chuàng)始交易(genesis transaction)上放一個「隨機(jī)漫步者(walker)」,然后讓該隨機(jī)漫步者開始「走向」端點(diǎn)。每一步,它都跳往一個我們最近直接認(rèn)可(directly approve)的交易。因?yàn)槲覀冊谶x擇要移動去哪個交易時,移動到每個交易的機(jī)率是相同的,這就是「無權(quán)重」一詞的由來。下面我們做了一個模擬來表示它如何進(jìn)行。
你們可以看到這個隨機(jī)漫步者所移動的路徑被標(biāo)記為紅色,每個有著不同的可能路徑的連接點(diǎn)則被標(biāo)記為藍(lán)色。對于那些剛發(fā)布的交易們,因?yàn)樘铝耍瑢τ陔S機(jī)漫步是「不可見」的,這些不可見的交易則被標(biāo)記為透明的。
在學(xué)會無加權(quán)隨機(jī)漫步( unweighted random walk)后,接下來要介紹他的進(jìn)階進(jìn)化版加權(quán)隨機(jī)漫步( weighted random walk)。
為什么要舍去無加權(quán)隨機(jī)漫步轉(zhuǎn)而使用加權(quán)隨機(jī)漫步呢? 因?yàn)槲覀儽仨毐苊鈶卸瓒它c(diǎn)(lazy tips)的存在。所謂懶惰端點(diǎn)是指這個端點(diǎn)(tips)完全不跟上tangle的最新狀態(tài),在廣播(broadcast)自己的每一筆交易的時候只認(rèn)可之前舊的交易。這樣的懶惰端點(diǎn)對于整個IOTA網(wǎng)路沒有任何幫助,新的端點(diǎn)永遠(yuǎn)不會被認(rèn)可到,整個IOTA網(wǎng)路會停滯不前。
在上面例子中,交易14就是一個懶惰端點(diǎn),因?yàn)樗J(rèn)可的交易是非常久之前的交易1 和交易3 ,如果我們使用均等機(jī)率的隨機(jī)漫步,這樣的懶惰端點(diǎn)交易14 被認(rèn)可到的機(jī)率跟其他一般的端點(diǎn)是一樣的,這樣就很大的程度的鼓勵了這種對于社群有害的行為。
要如何解決這種問題呢? 如果我們強(qiáng)迫所有的人只能認(rèn)可最新的交易,這樣的行為就跟去中心化的想法背道而馳。每個使用者、每筆交易都可以認(rèn)可任何一筆他們想要的交易。我們沒有可信的辦法可以判斷交易時間上的先后順序,所以要去實(shí)踐認(rèn)可最新交易的這個方法,是有困難的。我們的解決方法是開發(fā)出一個內(nèi)建的共識機(jī)制去避免這種狀況的發(fā)生,因此可以讓懶惰端點(diǎn)比較不可能被其他人認(rèn)可到。
我們的解決辦法是要給隨機(jī)漫步一個偏置量(bias),借此讓我們比較難選到懶惰端點(diǎn)。我們用累積加權(quán)(cumulative weight)去表達(dá)一個交易的重要性。我們更容易走到(選到)一個加權(quán)值較大的交易而不是一個加權(quán)值較小的交易。累積加權(quán)的計(jì)算方法很簡單,就是
去計(jì)算這筆交易有多少交易給它直接或間接認(rèn)可,再+1
以上圖為例,交易3 因?yàn)楸唤灰? 直接認(rèn)可,交易7、交易8、交易10 間接認(rèn)可。因此這樣得到
· 累積加權(quán)值= 1(直接認(rèn)可數(shù)) + 3(間接認(rèn)可數(shù)) + 1(公式要求加的1)
為了要展示一下累積加權(quán)的效果,我們再透過另外一個懶惰端點(diǎn)的例子來進(jìn)行說明。
在上圖,交易16 是一個懶惰端點(diǎn)。為了要選到交易16,我們的隨機(jī)漫步必須先到交易7 并且跳過交易9,才能選到交易16。然而這種狀況不太會發(fā)生,因?yàn)榻灰?6 的累積加權(quán)只有1,然后交易9 的累積加權(quán)有7,相比之下交易9 的累積加權(quán)大得多。因此累積加權(quán)是一個有效遏止懶惰端點(diǎn)的方法。
但這樣可能會有另外一個疑惑冒出來: “我們真的需要這些隨機(jī)性嗎? ”如果用一個超級加權(quán)的隨機(jī)漫步( super-weighted random walk )呢?透過這種方法,我們的隨機(jī)漫步在要選下一筆交易的分岔點(diǎn)時,可以永遠(yuǎn)只選加權(quán)值最大的交易就好,不需要任何的隨機(jī)性及機(jī)率“,我們會得到的tangle會變成下面的圖示一樣。
在這個tangle 中,灰色方塊是沒有任何人認(rèn)可過的tips,一個正常的tangle 應(yīng)該是希望每個tips 在右邊(時間比較后面)的地方有其他tips。但像這樣散落后面沒有接tips 就會有點(diǎn)問題。這些散落的tips 沒有任何交易去給他們做認(rèn)可。這就是我們?nèi)绻麑﹄S機(jī)漫步給予偏置量太多時會產(chǎn)生的問題: ”如果我們堅(jiān)持只選擇累積加權(quán)值最大的交易,這樣就會有很大比例的交易永遠(yuǎn)不會被認(rèn)可到“,這樣也就會產(chǎn)生像上圖一樣,中間是被認(rèn)可成功的交易大道,兩旁散落著一些被遺棄的交易。
因此我們需要一個方法去明確定義,在分岔點(diǎn)時,選每個不同交易認(rèn)可者的機(jī)率。這個過程使用的確切公式不是說十分重要,只要我們給予加權(quán)值比較大的交易一個偏置量,并且透過一些參數(shù)去控制這個偏置量多大這樣就好了。因此在此我們在這邊接紹一個新的參數(shù)α,α控制交易累積加權(quán)值的重要性。α的明確定義在白皮書里面有,如果有需要以后也會有專文件紹。
如果α=0這樣就會回歸無權(quán)重的隨機(jī)漫步。如果α非常大,這樣就會變成超級加權(quán)隨機(jī)漫步( super-weighted random walk )。所以在這兩極之間,可以找到一個平衡,這個平衡點(diǎn)可以充分的處罰懶惰端點(diǎn),而且也不會造成太多的tips被遺落在外沒有被認(rèn)可。如何找到這個理想的平衡點(diǎn)是一個IOTA很重要的研究項(xiàng)目。
決定每一步隨機(jī)漫步選取機(jī)率的方法叫做馬可夫鏈地卡羅 (Markov chain Monte Carlo)簡稱MCMC。馬可夫鏈的特性是每一個狀態(tài)的分布概率都跟之前的前一個狀態(tài)有關(guān),之前的其他狀態(tài)都沒有關(guān)系(獨(dú)立的)。
如果有任何新點(diǎn)子都可以透過模擬去展示,我們很建議讀者在讀完之后玩玩不同α和λ ,可以看看不同的值下會產(chǎn)生怎樣不同的tangle。
到目前為止,我們已經(jīng)介紹過有向無環(huán)圖(DAG)、隨機(jī)漫步(random walk)、和各種不同交易端點(diǎn)的選擇法(tip selection mechanism)。在本篇文章,我們終于要來談?wù)動嘘P(guān)錢的事情。這次,我們要來介紹什么叫做”交易A 認(rèn)可了交易B“。
就像本系列前面談到的,每一筆交易都包含著交易資訊像是”Alice給Bob 10 IOTAs“。交易認(rèn)可者的工作第一步就是確認(rèn)是不是Alice真的有10 IOTAs可以給Bob。
可能有些人會疑惑那這些IOTAs從哪里來的呢? (好啦其實(shí)我覺得大家沒有疑惑) IOTA跟其他知名的幣像是以太幣還有比特幣不同的地方是,IOTA不需要挖礦, IOTA在創(chuàng)世交易( genesis transaction )時就產(chǎn)生出了所有的IOTAs,從此之后不會有任何新的IOTA被產(chǎn)生,IOTA的數(shù)量也就維持定值。在創(chuàng)世交易時,就將IOTAs傳給一開始的投資者(ICO投資者)。在這之后,這些使用者互相交易,就構(gòu)成了現(xiàn)在的交易網(wǎng)路。
好的讓我們回過來看看Alice 和Bob,用他們來做個很簡單的范例。下面的小框框代表了一個交易,為了方便起見,我們把他們兩個人交易前和交易后的帳戶余額都寫上來。我們可以看到,在一開始Alice 有10i,在給了Bob 10i后Alice 什么都沒有了。
過了一陣子,有一個人叫Charlie,他自己做了另一筆交易。在他跑了端點(diǎn)選擇的演算法(tip selection algorithm)后,判斷他需要認(rèn)可Alice 的交易才行。為了完成認(rèn)可,他需要確認(rèn)Alice 真的有10i 可以供花費(fèi)。而且Charlie 如果沒有認(rèn)真驗(yàn)證的話對自己也沒什么好處,如果他給一個余額不足的交易通過認(rèn)可,這樣他自己的交易永遠(yuǎn)都不會被驗(yàn)證成功。
為了要認(rèn)可Alice 的這筆交易,Charlie 必須列出所有Alice 這筆交易,直接和間接認(rèn)可過的所有交易,一直列到創(chuàng)世交易。然后就出現(xiàn)了下面這一個很長的列表
1. 創(chuàng)世交易創(chuàng)造了15i
2. 創(chuàng)世交易給Bob 2i
3. 創(chuàng)世交易給Alice 8i
4. 創(chuàng)世交易給Charlie 5i
5. Charlie 給Donna 3i
6. Bob 給Alice 2i
任何的過程只要結(jié)果是讓Alice 有10i 而且Bob 有0i 都是可以接受的結(jié)果。而且Charlie 必須注意到所有其他帳號在這個系統(tǒng)里面帳戶余額都不能是負(fù)數(shù),如果是負(fù)數(shù)的話,Charlie 的交易就會是無效的。
接下來我們看看另一個例子。如果Alice 想要給Bob 超過他戶頭余額的IOTA數(shù)會發(fā)生什么事情。
如果Alice 給Bob 100i,但是Alice 只有10i。這樣Alice 的交易,和接下來所有讓Alice 交易認(rèn)可成功的交易,都會被整個IOTA 網(wǎng)路視為無效交易。
整個狀況會變得更有趣如果我們是認(rèn)可了兩筆交易而不是一筆交易(實(shí)際上一般狀況下也需要認(rèn)可兩筆啦)。
在右邊Bob 付錢的交易,成功認(rèn)可了左邊兩筆Alice 付錢的交易,因?yàn)锳lice 的帳戶余額是足以付那兩筆交易的錢。
那如果余額不足怎么辦? 下面這張圖呈現(xiàn)了這個例子。在下面這個例子中Bob 不能讓Alice 的交易被認(rèn)可成功,因?yàn)槿绻J(rèn)可成功的話,這樣Alice 的帳戶余額就會是負(fù)數(shù)的,而負(fù)數(shù)的帳戶余額是不被允許的。如果Bob 讓Alice 的交易認(rèn)可成功,他就打破了IOTA 協(xié)議,在IOTA 網(wǎng)路上的所有人都不會讓Bob 的交易被認(rèn)可成功。
上面這個狀況叫做雙花(雙重花費(fèi)double spend),因?yàn)锳lice 把他的錢花了兩次。而且必須注意到,Alice 在他花費(fèi)的當(dāng)下沒有破壞IOTA 協(xié)議,因?yàn)槊恳还P交易的當(dāng)下,Alice 的帳戶余額都足以支付當(dāng)下那筆個別的消費(fèi)。也許Alice 也不是故意做雙花攻擊,她只是不小心就送出了兩筆交易的廣播。反正結(jié)果就是,Alice 創(chuàng)造了兩個分岔,這兩個分岔在tangle 上沒辦法被整合。這樣就造成一個大問題給所有的IOTA 誠實(shí)使用者: ”到底哪一筆交易才是能讓他們認(rèn)可成功的呢? “
這個問題的解決辦法就是之前所提到的加權(quán)隨機(jī)漫步( weighted walk)。最后這兩個分支會有一個變成加權(quán)值比較大另一個比較小。之后的交易會接在加權(quán)值比較大的分支上(這個行為就像是交易被留下),加權(quán)值較小的會被放棄。這件事也暗示著,交易從被發(fā)出去到認(rèn)可成功會有一段時間的延遲,即使有些交易成功認(rèn)可了這筆剛發(fā)出去的交易,也不能保證這筆剛發(fā)出去的交易會不會是有沖突交易分岔上的一部份。為了確認(rèn)這筆交易是不是被確認(rèn)認(rèn)可了(comfirmed)。我們必須等到這筆交易的確認(rèn)信心( confirmation confidence )足夠高,關(guān)于這些我們下面會進(jìn)行解釋。
在上面內(nèi)容我們有提到,當(dāng)Alice 多次花費(fèi)或者多次廣播交易時會造成雙重花費(fèi)的問題。我們下面來介紹在tangle 上會如何解決這個問題,還有如何片段哪一個交易歷史才適合的交易歷史。
為了闡明這個問題,我們將會檢視下面這個雙花的情境。
如你所見,Alice 在最一開始有5i。在接下來的交易,Alice 把這5i 同時給Bob 還有Charlie兩個人,也就是說他重復(fù)花費(fèi)了這5i。這很明顯的是一個問題! 即便這兩筆交易都是合法的,但是我們?nèi)绻寖晒P交易都合法的話就會讓Alice 多給了不存在的5i。用tangle 的術(shù)語來說,我們沒辦法讓未來的交易同時認(rèn)可(approve)這兩筆交易,因?yàn)檫@樣會造成Alice 帳戶余額是負(fù)數(shù)。
前面的文章告訴我們,透過加權(quán)隨機(jī)漫步演算法,在上圖最終會有一個分支加權(quán)值會大得多。因此共識(consensus)就會形成,然后加權(quán)值比較大的交易就會成為合法交易。但是從Bob 和Charlie 的角度,他們怎么知道他們真的從Alice 那邊收到錢了呢?
想像一下Bob 和Charlie 都是恐龍販?zhǔn)凵蹋╠inosaur dealer,這例子真貼近生活……),Alice 是一個恐龍狂粉,他跟這兩個恐龍販?zhǔn)凵潭假I了一只暴龍。假如這兩位販?zhǔn)凵桃豢吹浇灰壮霈F(xiàn)在tangle 上就瞬間寄出暴龍的友好店家。但這樣的話,最終這兩個好心店家會有一個人發(fā)現(xiàn)他沒有收到錢。我們要如何不讓友好店家們不會白白送人一只爬蟲類動物呢?
這是一個非常嚴(yán)重的問,比特幣是第一個成功解決這種問題的技術(shù)。為了示范tangle是如何解決這種問題,我們要介紹一個新概念叫”確認(rèn)信心( confirmation confidence )“。這個信心是測量tangle上對于一個交易的接受程度(level of acceptance)。
信心程度是透過下列過程進(jìn)行計(jì)算。
1. 跑端點(diǎn)選擇演算法100 遍。
2. 記下有多少個交易認(rèn)可我們這筆交易,并且記錄下來叫A。
3. 這個交易的確認(rèn)信心( confirmation confidence )就是A percent
換句話說,確認(rèn)信心( confirmation confidence )就是認(rèn)可這筆交易的端點(diǎn)百分比。并非所有端點(diǎn)都是給予相同程度的重要性,如果某個端點(diǎn)他有更高的機(jī)率被選取的話,那他在計(jì)算確認(rèn)信心( confirmation confidence )時的重要性就會更高。為了呈現(xiàn)這點(diǎn),我們把確認(rèn)信心( confirmation confidence )加到模擬里面。在下圖,擁有超過95%確認(rèn)信心( confirmation confidence )的交易,我們以粗框方格表示。
在上圖,交易9 被4 個中的2 端點(diǎn)認(rèn)可(交易12、交易13認(rèn)可,交易11、交易7 不認(rèn)可)。如果我們用機(jī)率一致的端點(diǎn)選取演算法,交易9 會有50% 的確認(rèn)信心。然而,認(rèn)可交易9 的端點(diǎn)們明顯的比沒有認(rèn)可交易9 的端點(diǎn)們有更高一點(diǎn)的可能性,因此這提升了一點(diǎn)交易9 的確認(rèn)信心。
現(xiàn)在要讓Bob 和Charlie 判斷何時出貨Alice 訂的暴龍變得明確許多。只要Alice 的交易超過某個非常高的信心水平,比如說95%,這樣這筆交易被推離共識,認(rèn)為是非法交易的可能性就會變得很低。但是我們必須說”可能性變得很低“,而不是說”不可能“。如果Alice 是壞蛋,而且他擁有足夠的算力,他還是能夠成功的執(zhí)行雙花攻擊。
為了執(zhí)行雙花攻擊,Alice 會新發(fā)布一個付錢給Charlie 而非給Bob 的交易。Alice 必須用這個給Charlie 的交易認(rèn)可兩個舊的交易,而這兩個舊的交易不可以參考到給Bob 的那個交易(原文寫給Charlie 的交易,但是我覺得怪怪的感覺是給Bob 的交易才能雙花)。接下來他會一直送出超級大量新的交易,去讓這個給Charlie 錢的交易(分支)有更高的累積加權(quán)值。如果Alice 擁有足夠巨大的算力,就可以讓整個IOTA 網(wǎng)路相信Alice,并且把之后自己的交易接在這個新的分支后面。因此Alice 成功的翻轉(zhuǎn)了歷史紀(jì)錄,成功實(shí)行了雙花攻擊。在這個時候,如果我們?nèi)タ唇oBob 錢的交易的確認(rèn)信心,我們會發(fā)現(xiàn),給Bob 錢交易的確認(rèn)信心從95% 掉到趨近于0,甚至是0。
攻擊如下圖所示,越往下時間越后面。
這種情境只會在Alice 擁有超過,或者接近整個IOTA 網(wǎng)路算力時才會發(fā)生,也就是說Alice 能夠發(fā)送超過或接近整個IOTA 網(wǎng)路其他人送出的交易數(shù)總和。因此對于一個成熟而且足夠活躍的網(wǎng)路來說,這是不用擔(dān)心的。但是對于現(xiàn)在的IOTA 網(wǎng)路而言,這會是一個很大的問題。現(xiàn)在IOTA 網(wǎng)路的交易量還不足以抵抗雙花攻擊。
因?yàn)镮OTA 本身的設(shè)計(jì)就有可擴(kuò)充性,所以IOTA Foundation 設(shè)計(jì)了一個暫時的志愿性質(zhì)的共識機(jī)制。這個機(jī)制就是協(xié)調(diào)員(coordinator)。每兩分鐘(印象中這數(shù)字現(xiàn)在有改變)就會有一個里程碑交易(mileston transaction)被IOTA Foundation 發(fā)布出來。所有被里程碑交易認(rèn)可的交易的確認(rèn)信心都會直接被提升到100%。透過協(xié)調(diào)員,Alice 的交易就永遠(yuǎn)不會被認(rèn)可。我們采用這個方式去保護(hù)現(xiàn)在還不成熟的IOTA 網(wǎng)路,直到IOTA 網(wǎng)路足夠活躍到能夠轉(zhuǎn)移到100% 去中心化,應(yīng)用整個完整的IOTA 分散式共識演算法。在這個時候IOTA Foundation 就會關(guān)掉協(xié)調(diào)員,讓tangle 自己成長。到那個時候,移掉協(xié)調(diào)員也可以讓整個網(wǎng)路有幾個數(shù)量級的加速。
評論
查看更多