基于一種特殊的有向圖Tangle介紹

為了了解tangle是什么東西，我們得先了解什么叫有向圖。

有向圖是點（下圖中有數(shù)字的方格）還有邊（下圖箭頭線）的集合

其中Tangle是IOTA的資料結(jié)構(gòu)（像以太和比特幣都是區(qū)塊鏈的資料結(jié)構(gòu)），Tangle是一種特殊的有向圖。Tangle上面保存了交易。每筆交易由一個點代表（vertex）。當(dāng)一個新的交易要加入Tangle。他必須驗證之前Tangle上的兩個交易，每個驗證會增加一個邊（edge），所以加入一筆交易，會在Tangle上增加兩個邊。

用同樣一個例子來解說

像在上面的Tangle中，交易5驗證了交易2交易3，然后交易5又被交易6驗證。在這篇文章暫時還不會討論驗證的詳細過程，目前只要當(dāng)作驗證是確認上一筆交易有沒有花超過該帳戶余額就好了。

我們稱呼還沒被驗證的交易叫做tips（畢竟他會在整個Tangle末端的地方）。像上圖交易6就是一個tip。每一個新產(chǎn)生的交易都需要驗證兩筆tips的交易（至少至少至少要一個）。選擇需要被驗證的tips的演算法是IOTA技術(shù)的特色。

但為了循序漸進，我們會從最簡單的方法開始： 我們隨機抽取任意兩個tips，并且每個tip 被抽到的機率都是相等的。

為了展示tangle在這種隨機抽取策略（講得比較專業(yè)一點叫“uniform random tip selection”）下tangle會長什么樣子，IOTA Foundation做了動畫模擬展示。這個模擬隨機產(chǎn)生了一個tangle，這個隨機的tangle會由一個創(chuàng)世區(qū)塊（genesis）開始。在這個展示中，最左邊是創(chuàng)世區(qū)塊，最右邊是最新的交易（tips）。tips會以灰色表示。當(dāng)滑鼠滑到任何一筆交易上面的時候，被當(dāng)下交易驗證的交易會以紅色表示，驗證當(dāng)下交易的交易會以藍色表示。

在上面的模擬中，你或許已經(jīng)注意到交易并不平均分散在各個時間，而是在某些時間會特別的「繁忙」。這個讓模型更加真實的隨機方式，是使用帕松過程去模擬交易抵達而完成的。而這個模型在分析多少客戶在指定的時間段之中走進商店，或者多少電話打進客服中心的這些例子中非常普遍。我們可以于下圖中看到這個行為如何用在糾纏。交易4、5、以及6幾乎同時抵達，而交易6之后有個長的中斷，暫時沒有新的交易發(fā)出來。

對我們的目標來說，我們只需要知道一件關(guān)于帕松分布事情：平均而言，進入的交易速度被設(shè)定為我們稱為λ的常數(shù)。例如，我們設(shè)定λ=2，交易量為100，則總模擬時間將會是50次每單位時間。試試看吧！

在開始之前，一件需要說明而更有趣的事情是；如果我們設(shè)定λ為非常小的數(shù)（例如0.1），則我們就可以得到「鏈」。一個交易不是認可（approve）兩個，而是只認可（approve）前一個交易長得像鏈的纏結(jié)，這是因為交易將變慢以至于任何給定的時間內(nèi)，只有一個端點（tip ）去認證。在另個極端狀況中，如果λ很大，所有的交易將抵達得很快，使得它們所見到的唯一的端點即是創(chuàng)始端點（創(chuàng)始交易所產(chǎn)生的端點）。這就是模擬的限制：以一個很大的λ和固定的交易量，我們將在相當(dāng)短的時間段中進行模擬。

非常小的 λ所生產(chǎn)的鏈

非常大的λ：只有創(chuàng)始端點是可見的

所以什么是交易看不「見」前一個端點呢？在模型中，我們讓每個交易它抵達后一定時段內(nèi)是不可見的（invisible）。我們使用字母h標示延遲的時間長度。這個延遲表示該交易被準備以及透過網(wǎng)路傳播的時間。在我們的模擬中，我們常常設(shè)定h=1。這代表我們只能在過去的每段單位時間內(nèi)，認可最少一次的交易。這個延遲不只是很務(wù)實的小細節(jié)，也是纏結(jié)最基本的性質(zhì)，如果沒有這個延遲的話，我們將得一個非常無聊的鏈。這個延遲是真實世界中，各個節(jié)點廣播通知彼此有新的交易出現(xiàn)所花費的時間。加上這個參數(shù)，也使得我們的糾纏和現(xiàn)實世界的狀況更加接近。

最后，來講更先進的節(jié)點選擇演算法─「無權(quán)重隨機漫步」。使用這個算法，我們在創(chuàng)始交易（genesis transaction）上放一個「隨機漫步者（walker）」，然后讓該隨機漫步者開始「走向」端點。每一步，它都跳往一個我們最近直接認可（directly approve）的交易。因為我們在選擇要移動去哪個交易時，移動到每個交易的機率是相同的，這就是「無權(quán)重」一詞的由來。下面我們做了一個模擬來表示它如何進行。

你們可以看到這個隨機漫步者所移動的路徑被標記為紅色，每個有著不同的可能路徑的連接點則被標記為藍色。對于那些剛發(fā)布的交易們，因為太新了，對于隨機漫步是「不可見」的，這些不可見的交易則被標記為透明的。

在學(xué)會無加權(quán)隨機漫步（ unweighted random walk）后，接下來要介紹他的進階進化版加權(quán)隨機漫步（ weighted random walk）。

為什么要舍去無加權(quán)隨機漫步轉(zhuǎn)而使用加權(quán)隨機漫步呢？ 因為我們必須避免懶惰端點（lazy tips）的存在。所謂懶惰端點是指這個端點（tips）完全不跟上tangle的最新狀態(tài)，在廣播（broadcast）自己的每一筆交易的時候只認可之前舊的交易。這樣的懶惰端點對于整個IOTA網(wǎng)路沒有任何幫助，新的端點永遠不會被認可到，整個IOTA網(wǎng)路會停滯不前。

在上面例子中，交易14就是一個懶惰端點，因為他認可的交易是非常久之前的交易1 和交易3 ，如果我們使用均等機率的隨機漫步，這樣的懶惰端點交易14 被認可到的機率跟其他一般的端點是一樣的，這樣就很大的程度的鼓勵了這種對于社群有害的行為。

要如何解決這種問題呢？ 如果我們強迫所有的人只能認可最新的交易，這樣的行為就跟去中心化的想法背道而馳。每個使用者、每筆交易都可以認可任何一筆他們想要的交易。我們沒有可信的辦法可以判斷交易時間上的先后順序，所以要去實踐認可最新交易的這個方法，是有困難的。我們的解決方法是開發(fā)出一個內(nèi)建的共識機制去避免這種狀況的發(fā)生，因此可以讓懶惰端點比較不可能被其他人認可到。

我們的解決辦法是要給隨機漫步一個偏置量（bias），借此讓我們比較難選到懶惰端點。我們用累積加權(quán)（cumulative weight）去表達一個交易的重要性。我們更容易走到（選到）一個加權(quán)值較大的交易而不是一個加權(quán)值較小的交易。累積加權(quán)的計算方法很簡單，就是

去計算這筆交易有多少交易給它直接或間接認可，再+1

以上圖為例，交易3 因為被交易5 直接認可，交易7、交易8、交易10 間接認可。因此這樣得到

· 累積加權(quán)值= 1（直接認可數(shù)） + 3（間接認可數(shù)） + 1（公式要求加的1）

為了要展示一下累積加權(quán)的效果，我們再透過另外一個懶惰端點的例子來進行說明。

在上圖，交易16 是一個懶惰端點。為了要選到交易16，我們的隨機漫步必須先到交易7 并且跳過交易9，才能選到交易16。然而這種狀況不太會發(fā)生，因為交易16 的累積加權(quán)只有1，然后交易9 的累積加權(quán)有7，相比之下交易9 的累積加權(quán)大得多。因此累積加權(quán)是一個有效遏止懶惰端點的方法。

但這樣可能會有另外一個疑惑冒出來： “我們真的需要這些隨機性嗎？ ”如果用一個超級加權(quán)的隨機漫步（ super-weighted random walk ）呢？透過這種方法，我們的隨機漫步在要選下一筆交易的分岔點時，可以永遠只選加權(quán)值最大的交易就好，不需要任何的隨機性及機率“，我們會得到的tangle會變成下面的圖示一樣。

在這個tangle 中，灰色方塊是沒有任何人認可過的tips，一個正常的tangle 應(yīng)該是希望每個tips 在右邊（時間比較后面）的地方有其他tips。但像這樣散落后面沒有接tips 就會有點問題。這些散落的tips 沒有任何交易去給他們做認可。這就是我們?nèi)绻麑﹄S機漫步給予偏置量太多時會產(chǎn)生的問題： ”如果我們堅持只選擇累積加權(quán)值最大的交易，這樣就會有很大比例的交易永遠不會被認可到“，這樣也就會產(chǎn)生像上圖一樣，中間是被認可成功的交易大道，兩旁散落著一些被遺棄的交易。

因此我們需要一個方法去明確定義，在分岔點時，選每個不同交易認可者的機率。這個過程使用的確切公式不是說十分重要，只要我們給予加權(quán)值比較大的交易一個偏置量，并且透過一些參數(shù)去控制這個偏置量多大這樣就好了。因此在此我們在這邊接紹一個新的參數(shù)α，α控制交易累積加權(quán)值的重要性。α的明確定義在白皮書里面有，如果有需要以后也會有專文件紹。

如果α=0這樣就會回歸無權(quán)重的隨機漫步。如果α非常大，這樣就會變成超級加權(quán)隨機漫步（ super-weighted random walk ）。所以在這兩極之間，可以找到一個平衡，這個平衡點可以充分的處罰懶惰端點，而且也不會造成太多的tips被遺落在外沒有被認可。如何找到這個理想的平衡點是一個IOTA很重要的研究項目。

決定每一步隨機漫步選取機率的方法叫做馬可夫鏈地卡羅 （Markov chain Monte Carlo）簡稱MCMC。馬可夫鏈的特性是每一個狀態(tài)的分布概率都跟之前的前一個狀態(tài)有關(guān)，之前的其他狀態(tài)都沒有關(guān)系（獨立的）。

如果有任何新點子都可以透過模擬去展示，我們很建議讀者在讀完之后玩玩不同α和λ ，可以看看不同的值下會產(chǎn)生怎樣不同的tangle。

到目前為止，我們已經(jīng)介紹過有向無環(huán)圖（DAG）、隨機漫步（random walk）、和各種不同交易端點的選擇法（tip selection mechanism）。在本篇文章，我們終于要來談?wù)動嘘P(guān)錢的事情。這次，我們要來介紹什么叫做”交易A 認可了交易B“。

就像本系列前面談到的，每一筆交易都包含著交易資訊像是”Alice給Bob 10 IOTAs“。交易認可者的工作第一步就是確認是不是Alice真的有10 IOTAs可以給Bob。

可能有些人會疑惑那這些IOTAs從哪里來的呢？ （好啦其實我覺得大家沒有疑惑） 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，他自己做了另一筆交易。在他跑了端點選擇的演算法（tip selection algorithm）后，判斷他需要認可Alice 的交易才行。為了完成認可，他需要確認Alice 真的有10i 可以供花費。而且Charlie 如果沒有認真驗證的話對自己也沒什么好處，如果他給一個余額不足的交易通過認可，這樣他自己的交易永遠都不會被驗證成功。

為了要認可Alice 的這筆交易，Charlie 必須列出所有Alice 這筆交易，直接和間接認可過的所有交易，一直列到創(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)里面帳戶余額都不能是負數(shù)，如果是負數(shù)的話，Charlie 的交易就會是無效的。

接下來我們看看另一個例子。如果Alice 想要給Bob 超過他戶頭余額的IOTA數(shù)會發(fā)生什么事情。

如果Alice 給Bob 100i，但是Alice 只有10i。這樣Alice 的交易，和接下來所有讓Alice 交易認可成功的交易，都會被整個IOTA 網(wǎng)路視為無效交易。

整個狀況會變得更有趣如果我們是認可了兩筆交易而不是一筆交易（實際上一般狀況下也需要認可兩筆啦）。

在右邊Bob 付錢的交易，成功認可了左邊兩筆Alice 付錢的交易，因為Alice 的帳戶余額是足以付那兩筆交易的錢。

那如果余額不足怎么辦？ 下面這張圖呈現(xiàn)了這個例子。在下面這個例子中Bob 不能讓Alice 的交易被認可成功，因為如果認可成功的話，這樣Alice 的帳戶余額就會是負數(shù)的，而負數(shù)的帳戶余額是不被允許的。如果Bob 讓Alice 的交易認可成功，他就打破了IOTA 協(xié)議，在IOTA 網(wǎng)路上的所有人都不會讓Bob 的交易被認可成功。

上面這個狀況叫做雙花（雙重花費double spend），因為Alice 把他的錢花了兩次。而且必須注意到，Alice 在他花費的當(dāng)下沒有破壞IOTA 協(xié)議，因為每一筆交易的當(dāng)下，Alice 的帳戶余額都足以支付當(dāng)下那筆個別的消費。也許Alice 也不是故意做雙花攻擊，她只是不小心就送出了兩筆交易的廣播。反正結(jié)果就是，Alice 創(chuàng)造了兩個分岔，這兩個分岔在tangle 上沒辦法被整合。這樣就造成一個大問題給所有的IOTA 誠實使用者： ”到底哪一筆交易才是能讓他們認可成功的呢？ “

這個問題的解決辦法就是之前所提到的加權(quán)隨機漫步（ weighted walk）。最后這兩個分支會有一個變成加權(quán)值比較大另一個比較小。之后的交易會接在加權(quán)值比較大的分支上（這個行為就像是交易被留下），加權(quán)值較小的會被放棄。這件事也暗示著，交易從被發(fā)出去到認可成功會有一段時間的延遲，即使有些交易成功認可了這筆剛發(fā)出去的交易，也不能保證這筆剛發(fā)出去的交易會不會是有沖突交易分岔上的一部份。為了確認這筆交易是不是被確認認可了（comfirmed）。我們必須等到這筆交易的確認信心（ confirmation confidence ）足夠高，關(guān)于這些我們下面會進行解釋。

在上面內(nèi)容我們有提到，當(dāng)Alice 多次花費或者多次廣播交易時會造成雙重花費的問題。我們下面來介紹在tangle 上會如何解決這個問題，還有如何片段哪一個交易歷史才適合的交易歷史。

為了闡明這個問題，我們將會檢視下面這個雙花的情境。

如你所見，Alice 在最一開始有5i。在接下來的交易，Alice 把這5i 同時給Bob 還有Charlie兩個人，也就是說他重復(fù)花費了這5i。這很明顯的是一個問題！ 即便這兩筆交易都是合法的，但是我們?nèi)绻寖晒P交易都合法的話就會讓Alice 多給了不存在的5i。用tangle 的術(shù)語來說，我們沒辦法讓未來的交易同時認可（approve）這兩筆交易，因為這樣會造成Alice 帳戶余額是負數(shù)。

前面的文章告訴我們，透過加權(quán)隨機漫步演算法，在上圖最終會有一個分支加權(quán)值會大得多。因此共識（consensus）就會形成，然后加權(quán)值比較大的交易就會成為合法交易。但是從Bob 和Charlie 的角度，他們怎么知道他們真的從Alice 那邊收到錢了呢？

想像一下Bob 和Charlie 都是恐龍販售商（dinosaur dealer，這例子真貼近生活……），Alice 是一個恐龍狂粉，他跟這兩個恐龍販售商都買了一只暴龍。假如這兩位販售商一看到交易出現(xiàn)在tangle 上就瞬間寄出暴龍的友好店家。但這樣的話，最終這兩個好心店家會有一個人發(fā)現(xiàn)他沒有收到錢。我們要如何不讓友好店家們不會白白送人一只爬蟲類動物呢？

這是一個非常嚴重的問，比特幣是第一個成功解決這種問題的技術(shù)。為了示范tangle是如何解決這種問題，我們要介紹一個新概念叫”確認信心（ confirmation confidence ）“。這個信心是測量tangle上對于一個交易的接受程度（level of acceptance）。

信心程度是透過下列過程進行計算。

1. 跑端點選擇演算法100 遍。

2. 記下有多少個交易認可我們這筆交易，并且記錄下來叫A。

3. 這個交易的確認信心（ confirmation confidence ）就是A percent

換句話說，確認信心（ confirmation confidence ）就是認可這筆交易的端點百分比。并非所有端點都是給予相同程度的重要性，如果某個端點他有更高的機率被選取的話，那他在計算確認信心（ confirmation confidence ）時的重要性就會更高。為了呈現(xiàn)這點，我們把確認信心（ confirmation confidence ）加到模擬里面。在下圖，擁有超過95%確認信心（ confirmation confidence ）的交易，我們以粗框方格表示。

在上圖，交易9 被4 個中的2 端點認可（交易12、交易13認可，交易11、交易7 不認可）。如果我們用機率一致的端點選取演算法，交易9 會有50% 的確認信心。然而，認可交易9 的端點們明顯的比沒有認可交易9 的端點們有更高一點的可能性，因此這提升了一點交易9 的確認信心。

現(xiàn)在要讓Bob 和Charlie 判斷何時出貨Alice 訂的暴龍變得明確許多。只要Alice 的交易超過某個非常高的信心水平，比如說95%，這樣這筆交易被推離共識，認為是非法交易的可能性就會變得很低。但是我們必須說”可能性變得很低“，而不是說”不可能“。如果Alice 是壞蛋，而且他擁有足夠的算力，他還是能夠成功的執(zhí)行雙花攻擊。

為了執(zhí)行雙花攻擊，Alice 會新發(fā)布一個付錢給Charlie 而非給Bob 的交易。Alice 必須用這個給Charlie 的交易認可兩個舊的交易，而這兩個舊的交易不可以參考到給Bob 的那個交易（原文寫給Charlie 的交易，但是我覺得怪怪的感覺是給Bob 的交易才能雙花）。接下來他會一直送出超級大量新的交易，去讓這個給Charlie 錢的交易（分支）有更高的累積加權(quán)值。如果Alice 擁有足夠巨大的算力，就可以讓整個IOTA 網(wǎng)路相信Alice，并且把之后自己的交易接在這個新的分支后面。因此Alice 成功的翻轉(zhuǎn)了歷史紀錄，成功實行了雙花攻擊。在這個時候，如果我們?nèi)タ唇oBob 錢的交易的確認信心，我們會發(fā)現(xiàn)，給Bob 錢交易的確認信心從95% 掉到趨近于0，甚至是0。

攻擊如下圖所示，越往下時間越后面。

這種情境只會在Alice 擁有超過，或者接近整個IOTA 網(wǎng)路算力時才會發(fā)生，也就是說Alice 能夠發(fā)送超過或接近整個IOTA 網(wǎng)路其他人送出的交易數(shù)總和。因此對于一個成熟而且足夠活躍的網(wǎng)路來說，這是不用擔(dān)心的。但是對于現(xiàn)在的IOTA 網(wǎng)路而言，這會是一個很大的問題?，F(xiàn)在IOTA 網(wǎng)路的交易量還不足以抵抗雙花攻擊。

因為IOTA 本身的設(shè)計就有可擴充性，所以IOTA Foundation 設(shè)計了一個暫時的志愿性質(zhì)的共識機制。這個機制就是協(xié)調(diào)員（coordinator）。每兩分鐘（印象中這數(shù)字現(xiàn)在有改變）就會有一個里程碑交易（mileston transaction）被IOTA Foundation 發(fā)布出來。所有被里程碑交易認可的交易的確認信心都會直接被提升到100%。透過協(xié)調(diào)員，Alice 的交易就永遠不會被認可。我們采用這個方式去保護現(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ù)量級的加速。