Tangle 白皮書

v1.4.3 / April 30, 2018
本文由 成功大學分散式帳本實驗室 翻譯

摘要

在本論文中我們分析了 IOTA（一種用於物聯網 [IoT] 行業的加密貨幣）中所使用的主要技術。這個新穎的加密貨幣最主要的特點就是 tangle，以一個有向無環圖 (DAG) 存放交易資訊。tangle 不僅成功的讓區塊鏈往前邁進一步，其特性更是符合 M2M 小額支付系統的需求。

本篇論文的一個關鍵貢獻是馬可夫鏈蒙地卡羅 (Markov Chain Monte Carlo, MCMC) 演算法。這些演算法會為新的交易選擇要接在哪些既有交易之後。

1. 關於系統的一般介紹

在過去的六年中，比特幣的興起和成功證明了區塊鏈技術的價值所在。然而，這種技術也有許多缺點，阻礙了它成為全球範圍內加密貨幣的唯一平臺。在這些缺點中，特別值得提及的就是無法進行小額支付，而小額支付在迅速發展的物聯網行業中的重要性不斷增加。在現今的系統中，使用者須支付手續費才能產生交易；因此，為了支付極少的金費而須再付好幾倍的手續費並不合理。且因手續費為產生區塊的人之動機，因此想完全屏除掉並不容易。另外亦須關注的是現存的加密貨幣都是清楚區分不同角色（如交易發起者，交易驗證者）的異質 (heterogeneous) 系統。這種明顯區分參與者的設計，容易造成資源搶奪與浪費的現象。 這就需要尋找一些完全不同於「基於比特幣和其他加密貨幣的區塊鏈技術」的解決方案。

在本論文中，我們提出了一個無區塊鏈 (blockchainless) 的加密貨幣系統，稱之為 IOTA [1]，可用於建立全球範圍內基於現有硬體的物聯網系統中的一種貨幣。

在一般情況下，IOTA 按如下方式運行。如前所述，不存在全域的區塊鏈，取而代之的是一個 DAG（有向無環圖），我們稱之為 Tangle。通過節點發出的所有交易構成了這個 Tangle（存所有交易的帳本）的集合。這個圖的邊是這樣形成的：當一個新的交易產生，它必須驗證之前的兩個交易，這些驗證關係就通過有向的邊來表示，如圖 1 所示（在圖中，時間走向總是從左到右）。如果從交易 A 到交易 B 之間沒有直接連接的有向邊，而有長度至少大於二的有向邊路徑存在，我們就說交易 A 間接地驗證了交易 B。另外，有一個創世交易 (genesis transaction)，被所有交易直接或間接驗證，如圖 2。創世交易有以下描述:在最一開始有一個地址 (address) 擁有全部的 token，接著創世交易會把金錢轉給其他 founder 的地址。我們強調所有的 token 皆是創世交易所產生的（不會再產生新的 token），而且不會再有「挖礦」就可以收到金錢獎勵的概念了。

術語:

site

在 Tangle 圖上的交易

節點 (node)

• 整個網路是由節點組成
• 也是發起交易者

整個架構的宗旨如下:使用者必須驗證其他交易才能發起交易，為整個網路的安全性盡一份力。我們假定節點檢查認證的交易是否存在衝突，同時節點不會直接或者間接地認證具有衝突的交易。其想法是隨著交易被越來越多的直接或者間接的交易所驗證，這個交易就愈會被系統所接受；換句話說，要接受一個雙重支付 (double-spending) 交易是極為困難的 (或者至少在實作上是幾乎不可能的)。很重要的是我們不會強制規定怎麼選擇要驗證的交易；更確切的說，我們認為如果很大量的節點依循「參考」的規則（這是比較合理的假設，特別是在 IoT，節點是裝載各式韌體的晶片），各節點就分別遵守其類別的規則

要發起一個交易，節點需做以下步驟：

• 選擇兩個交易驗證（這兩筆交易可能會一樣）
• 檢查這兩筆交易有無衝突，且有無驗證到衝突的交易
• 要讓一筆交易合法 (valid)，節點必須解出一道加密的問題（耗費計算力），與比特幣挖礦相似（如: 需要找出一個 nonce 讓其與其他驗證交易的資料的 hash 值為特定格式，像是這個 hash 值的前面需有幾個 0）

通常，我們是一個非同步的網路，因此節點並不會看到一樣的交易集合。值得注意的是 tangle 可能存在衝突的交易。節點間並不需要達成共識，因為合法的交易有權繼續在 tangle 中; 但要是出現衝突的交易，便需要決定哪筆交易要被孤立 (orphaned)，也就是這筆交易不會再被新進的交易間接驗證。決定哪筆交易是要被孤立的主要準則如下：一個節點進行多次的 tip 選擇演算法，接著觀察哪筆交易較可能被選到的 tip（間接）驗證。舉例來說：假設跑了 100 次 tip 選擇演算法，有一筆交易被選到 97 次，我們便說它有 97% 的信心被驗證到。

我們也一併說明接下來的問題 (cf. [4])： 是甚麼動機促使節點們產生、傳播 (propagate) 交易? 事實上，我們佈署的節點並沒有理由不產生及傳播交易。每個節點會計算一些數據，其中之一是計算會從鄰居接收多少新的交易。如果某個特定節點「太懶惰」，便會被它的鄰居捨棄。所以即使節點並沒有發布任何的交易（也因此沒有分享新的交易來驗證自己交易的動力），他仍然有動機努力工作。

在隨後的章節中，我們要討論選擇兩筆交易予以接受納入系統的演算法，用於衡量整體交易的驗證演算法（第 3 節，尤其是 3.1 節），以及可能會受到的攻擊情況（第 4 節）。

此外，應該指出的是，有關有向無環圖在加密貨幣領域中的想法已經有一些時日了，比如文獻 [3],[6], [7], [9], [12]。尤其需要指出的是，文獻 [7] 中提出的是被稱為 GHOST 的協議，修改了比特幣協議，把主要帳本的結構從區塊鏈改為一棵樹 (tree); 這樣的作法顯示，可以降低驗證時間並提高整體網路的安全性。在文獻 [9]中，作者們提出了基於 DAG 的加密貨幣模型; 和我們所提出的模型不同的是，組成 DAG 的是區塊 (block)，而非獨立的交易。且礦工會競爭手續費，新的金錢也會被創造（如同比特幣）。再來，文獻[6]中提出了一種類似於我們的解決方案，雖然他並沒有討論任何驗證 tip 的方法。我們也提及了另一種 [2] [10] 針對基於 P2P 的比特幣小額支付的解決方案。

2. 權重及相關概念

這裡我們定義一個交易的自身權重及其相關概念。交易的權重與發送這筆交易的節點所投入的工作量成正比；在實踐中，權重可以假定為 $3^n$ 的一些數值，其中 $n$ 屬於有限區間內的正整數。事實上，這與權重是如何增加的並不相干; 重要的是，每一筆交易都有一個正整數的權重。總之，權重愈高該筆交易在 tangle 中也就愈「重要」。我們假設，為了避免各式攻擊，沒有任何角色 (entity) 可以在短時間內產生大量的「可接受」權重的交易。

圖 1 權重的（重新）計算

我們所需要的一個重要概念就是一個交易的累積權重：它被定義為這個交易的自身權重與其他直接以及間接驗證這個交易的所有交易的自身權重之和。累積權重的計算方法如圖 1 所示。其中方框代表交易，方框右下角較小的數位表示這個交易的自身權重，而字體較大且加粗的數字是這筆交易的累積權重。例如，交易 F 經交易 A, B, C, E 直接或者間接被驗證。交易 F 的累積權重就是交易 F 自身權重及交易 A, B, C 和 E 的各自自身權重之和，即 9= 3 + 1 + 3 + 1 + 1。

在圖 1 中沒有被驗證的交易（即 “tips”）只有交易 A 和交易 C。若一個新的交易 X 進入系統並且驗證交易 A 和 C，那麼交易 X 就是系統中唯一的 tip 了，同時系統中其他所有的交易的權重增加 3（即交易 X 的自身權重）。為討論驗證演算法，我們需要引入一些其他的變數。首先，對於 tangle 中的一個點（比如，一筆交易），我們引入它的：

• 高度 (height): 定義為自創世交易 (genesis) 至當前這個交易的所有路徑中最長的長度；
• 深度 (depth): 定義為自這個交易到某個 tip 的最長路徑；
  
  圖 2. 關於交易的積分計算（帶圓圈的數字）

例如，在圖 2 中，交易 G 的高度為 1，深度為 3（因為反向路徑 F, B, A）； 而交易 D 的高度為 3，深度為 2。接下來，我們引入積分(score)的概念。一筆交易的積分定義為它的自身權重與所有它驗證的那些交易的自身權重之和，如圖 2 所示。同樣的，僅有的 tips 有交易 A 和 C。交易 A 直接或者間接地驗證了交易 B, D, F, G，因此交易 A 的積分為 1+3+1+3+1 = 9。同樣地，交易 C 的積分為 1+1+1+3+1 = 7。

事實上，想要了解本論文的證明過程，你可以假設所有交易的權重都為 1。因此，從現在開始，我們會依循這個假設。而現在累積權重就是 1 再加上所有直接或間接驗證此筆交易的數量; 積分 (score) 就是此筆交易所直接或間接驗證過的交易數量。

接著注意到，所有的代數中 (目前!) 最重要的就是累積權重(雖然高度、深度以及分數待會也會列入討論)。

3. 系統的穩定性和截斷集合

記 $L(t)$ 為 $t$ 時刻系統中 tips 的總數。當然，大家預期隨機過程 (stochastic process) $L(t)$ 保持穩定。更精確地說，是正遞迴 (positive recurrent) 的; 參照第 4.4 節以及 [11] 的 6.5 截處，有更正式的定義; 正遞迴指的是當 $t\to \mathrm{\infty }$，$\mathbb{P}[L(t)=k]$ 的極限應存在且為正值 $\mathrm{\forall }k\ge 1$。直觀上， $L(t)$ 應當圍繞一個恒定的常數波動，而不是趨於無窮大（這樣的話系統中會存在大量未經驗證的交易）。

為了分析 $L(t)$ 的穩定性，我們需要一些前提假設。其中一個就是，當有一個獨立的節點它產生了一個大權重的交易，因此新進交易的整個過程可以以帕松分佈為模型(比照 [11] 的 5.3 節)。假設 $\lambda$ 為交易輸入流的速率（帕松過程）；為簡單起見，我們假定交易輸入流的速率保持恒定。假設所有 的設備都具有近乎同等的計算能力；並假定系統總交易數為 $N$，其中 $L$ 個 tips 的情形下，一台設備要發送一筆交易所需要計算的平均時間為 $h$。我們假定所有節點都符合以下模式:

即在要發送一筆交易的時候，節點從tips 中隨機任意選擇兩個並驗證它們。須注意到的是，對「誠實的節點」而言，採用此方法並不是一個好主意。有幾個缺點，它並不能有效的抵制「懶惰的節點」和惡意的節點(參照第 4.1 節)。但我們仍把這個方法納入討論，因為其較簡單分析，而且讀者也接著會一窺較複雜的 tip 選擇演算法。

接下來我們做進一步的簡化，當一個節點發送，我們需要經過時間h之後才會發現它不是原本的狀態了。這代表一個交易在時間t接上tangle，直到時間t+h才會在tangle上看見。我們也假定tips的總數保持在幾乎靜值，數字大概落在$L_0$上下，在接下來我們會計算$L_0$由$\lambda$與$h$建立的函數。

我們發現，在一個給定的時間$t$，我們有約$\lambda h$的"隱藏的的tip"(這些tips是在在時段$[t-h,t)$接在tangle上，所以它們尚未能在tangle上被看到)；接著我們假設有$r$個"顯現的tips"(在t-h之前接上tangle的tips)，所以得出$L_0=r+\lambda h$。由於tips的總數是穩定的，我們或許可假定有$\lambda h$個交易，在t-h的時候為tips而在時間t時已不是了。現在考慮一個全新的交易被引進的情況；則這個交易會approve到tips的機率為$r/(r+\lambda h)$(因為這裡有r個tips，而這裡也有$\lambda h$已經不是tips但節點誤以為是)，所以選擇到tips的期望值是$2r/(r+\lambda h)$。我們可以發現一個重要的現象，在穩定的狀態中，選擇到tips的期望值為$1$，因為平均而言，一個新進的交易並不會改變tips的總數。解$2r/(r+\lambda h)$，可以得到$r=\lambda h$，以及

(1)$L_0=2\lambda h$

我們在這裡註記，如果今天規則改成一個交易會去驗證k個交易，而非兩個，則我們有類似的計算結果:

(2)$L_0^{(k)}={\displaystyle \frac{k\lambda h}{k-1}}$

理所當然的，$L_0^{(k)}$會趨近於$\lambda h$當$t$趨近無限大(基本上，剩下的tips會是那些網路上尚未可見到的)

我們回去考慮會有兩個交易會被approve的情況，一個交易第一次被approve期望的時間大約為$h+L_0/(2\lambda )=2h$。因為根據我們的假設，在第一個h時間之前，交易是不會被approved的。接下來驗證此交易的帕松過程的速率為$(2\lambda )/L_0$（可參考文獻[11]中的定理 5.3，說明了當我們以不同類別獨立分類每個帕松過程，那麼各個類別的帕松過程是相互獨立的）。

同時，注意到（至少在交易節點試圖驗證 tips 的情況下）對任意固定 $t$ 時刻， 在某一個階段 $s\in [t,t+h(L_0,N)]$ 內那些 tips 構成了一個截斷集合(cutset)，意味著在時間 $t^{\prime }>t$ 時發起的交易到創世交易的任何路徑都必須通過這個集合。至少在某些偶然的情況下這個截斷集合變得非常小，這是極為重要的。我們也許可以使用這個較小的截斷集合作為檢查點，作為 DAG 可能的剪枝或者其他用途。

上述「純隨機」策略實際上並不太好，因為這種策略不會鼓勵節點驗證交易：比如「懶惰」的用戶也許總是去驗證幾個較早的固定交易（因此也就沒有貢獻到最新交易的驗證），而這種行為也不會受到懲罰。為消除這類行為，我們需要採用一種策略，以便使得新進交易偏向於選擇驗證那些具有較高分數 (score) 的 tips。惡意的節點也可以人工的製造大量 tips(如產生大量交易只驗證幾組就交易)，讓新交易能有極高機率選擇 tips，且有效的捨棄「誠實」節點的 tips。為了避免這個行為，我們得採用另一種方法，讓新進交易偏向選擇「好」的 tips。在 4.1 節有一個此種策略的例子。

因此，在這種情況下，求解一筆交易第一次被驗證所需要的時間的期望值，就有一點複雜了。我們分兩個區間進行分析，如圖 3 所示。

• 低負載區：tips 的數量很少，常常只有 1 個。 當交易流足夠慢時會發生，不太可能發生不同的交易驗證同一個 tip 的情況。 而且若網路延遲很短且設備運算的速度很快，也不大可能會有大量 tips 出現的情況。 即使是在交易流的很快的情況下也是如此。此外，我們也應假設不會有攻擊者產生大量的交易以膨脹 tips 數量。
• 高負載區：tips 的數量很多。當交易流很大且計算力與網路的延遲很長時便可能會讓多筆不同交易驗證到同一個 tip。

圖 3. Tangle 及其在低負載和高負載情況下典型的 tip 集合（具有陰影的方框）。需要注意的是 在高負載情況下，一些交易也許需要等待較長時間從而得到
第一次驗證。

在低負載區域，這種情況就相對簡單：在 ${\lambda }^{-1}$ 的時間尺度上會發生第一次驗證， 因為第一個（或者第一批中的一個）進入的交易將會驗證我們的這些交易。

現在我們來考慮高負載區域的情況，也就是當 $L_0$ 很大的時候。如上面所提到的，我們可以假設驗證其他 tips 的帕松事件是相互獨立且其機率近似 $2\lambda /L_0$。因此，我們預期一筆交易被第一次驗證的時間約為 $L_0/(2\lambda )\approx 1.45h$ (1)。值得一提的是，更好的驗證策略(較偏袒「好」的 tips)，被動的花費大量時間等待交易被驗證並不是個好主意，這是因為「好」的 tips 會不斷的出現且也常被選擇驗證。甚至當交易在等待被驗證的時間太長時(如，花費比 $L_0/(2\lambda )$ 還長的時間)，一個好的辦法就是另外發起一個空交易，也就是發起一個新的空白交易並去驗證我們的交易與其他「好」的 tip(因此這個空白交易會有很大的機會被驗證)。

接下來，注意到基於高度和積分的驗證策略可能會受到特定類型的攻擊，見 4.1 節分析。我們將在那一節中討論更加詳細的策略來防止這樣的攻擊。無論如何，這種最簡單的 tip 選擇策略（「隨機驗證兩筆交易」）仍然是值得考慮的，因為這對於分析來說最簡單，從而也許會給出系統行為方面的一些定性和定量方面的理解。

結論：

1. 我們區分了兩個區間，低負載和高負載區間，如圖 3 所示。
2. 在低負載區，通常沒有多少 tips（比如說，一個或者兩個），一個 tip 在 $\mathrm{\Theta }({\lambda }^{-1})$ 時間尺度內得到第一次驗證，其中 $\lambda$ 是進入系統內的交易流速度。
3. 在高負載區，tips 的典型數量取決於驗證策略（比如，新的交易如何選擇其 他的兩個交易進行驗證）。
4. 對於 「隨機驗證兩個 tips」 策略，tips 的典型數量由公式（3）確定。可以看到這種策略在 tips 的典型數量上是理想的，但是在實際中不會選用這種策略， 因為這策略不會鼓勵新的交易去驗證 tips。
5. 然而，我們需要更多精細的策略，這類策略將在 4.1 節中進行討論。
6. 在高負載區，一個 tip 獲得驗證所需要的時間尺度為 $\mathrm{\Theta }(h)$，其中 $h$ 是一個節點的平均計算/傳播擴散時間。但是，如果在上述時間間隔內沒有獲得第一個驗證，那麼（對於交易產生者或者接收者）一個好的方法就是額外發送一筆空白交易來提高驗證速度。

3.1 累積權重的增長有多快？

很顯然的，在低負載區，交易被驗證幾次後，它的累積權重將以 $\lambda$ 的速度增加，因為本質上來說所有新的交易都將間接指向我們的交易。

而在高負載區，一個舊且具有較大的累積權重的交易，其累積權重會因為其他心交易會間接指向它而以 $\lambda$ 的速度增加。當然，我們看到剛開始的時候交易需要等待一定的時間被驗證，很顯然其累積權重在初始時會以較為無規的形式增長。為了弄明白一個交易在得到幾個驗證之後其累積權重的變化行為，我們記 $H(t)$ （為簡單起見，我們自發起交易開始計時）為 $t$ 時刻該交易的累積權重期望值，並用 $K(t)$ 表示在 $t$ 時刻驗證我們的這筆交易的 tips 數量的期望值。在此，我們簡記為 $h:=h(L_0,N)$。同時，我們做一個簡化假設，認為 tips 的總數大體保持恒定不變（等於 $L_0$ ）。這裡我們採用「隨機驗證兩個 tips」的策略；可期望其結果大體上與其他合理的策略所得到的一樣。

在 $t$ 時刻進入系統中的一筆交易通常是基於 $t-h$ 時刻時系統的狀態，來選擇兩筆交易進行驗證(因為節點在發起交易前必須進行運算/驗證)。不難得到至少驗證一個我們的 tip 的機率是 $1-(1-{\displaystyle \frac{K(t-h)}{L_0}}{)}^2=-{\displaystyle \frac{K(t-h)}{L_0}}(2-{\displaystyle \frac{K(t-h)}{L_0}})$ (等號左手邊的 1 減掉 2 個不是我們的 tips 被驗證的機率)，因此我們可以寫下如下的微分方程（類似於文獻 [11]中的例子 6.4）：

$H(t+\sigma )=H(t)+\lambda \sigma {\displaystyle \frac{K(t-h)}{L_0}}(2-{\displaystyle \frac{K(t-h)}{L_0}})+o(\sigma )$

我們可以化簡式子為︰
(3) ${\displaystyle \frac{dH(t)}{dt}}=\lambda {\displaystyle \frac{K(t-h)}{L_0}}(2-{\displaystyle \frac{K(t-h)}{L_0}})$

為了能夠使用方程(3)，我們首先需要計算 $K(t)$。如何立刻去計算 $K(t)$ 是很困難的，因為在 $t-h$ 時刻的一個 tip 也許在 $t$ 時刻已經不是一個 tip，並且，在新進入的交易驗證了這樣一個 tip 的情況下，那麼驗證原來交易的 tips 總量就會增加 1 個。現在，根據（1）和（3）可以觀察到關鍵的問題是在 $t-h$ 時刻的一個 tip 在 $t$ 時刻仍然保持為 tip 的機率為 $1/2$。因此，在 $t$ 時刻，有一半的 $K(t-h)$ 的「以前」的 tips 仍然保持為 tips，而另一半已經至少被一筆交易所驗證。讓我們用 A 表示（大概）$K(t-h)/2$ 的 tips 為在 $t-h$ 到 $t$ 時刻仍然保持為 tips 的這些交易的集合，而用 B 表示另外一半在 $t$ 時刻已經被驗證過的 tips。假定新進入的交易至少驗 證了集合 B 中一筆交易而沒有驗證集合 A 中任何交易的機率為 $p_1$；同時假設同時驗證了兩筆集合 A 中的交易的機率為 $p_2$ 。顯然， $p_1$ 和 $p_2$ 分別對應於在新交易到達時，目前「我們」的 tips 增加或者減少 1 的機率。因此，得到一些基本關係式：

$p_1=({\displaystyle \frac{K(t-h)}{2L_0}}{)}^2+2\times {\displaystyle \frac{K(t-h)}{2L_0}}(1-{\displaystyle \frac{K(t-h)}{L_0}})$

$p_2=({\displaystyle \frac{K(t-h)}{2L_0}}{)}^2$

(為了達到第一個敘述，觀察到 $p_1$ 等於都驗證 B 集合的機率與第一個驗證 B 集合且第二個不是 A 或 B 集合的機率之和) 類似方程式（4），關於 $K(t)$ 有如下微分方程：

(4) ${\displaystyle \frac{dK(t)}{dt}}=(p_1-p_2)\lambda =\lambda {\displaystyle \frac{K(t-h)}{L_0}}(1-{\displaystyle \frac{K(t-h)}{L_0}})$

仍然很難準確地求解方程（4），因此我們進一步進行簡化假設。首先，我們可以看到，對於任意固定 $ϵ>0$ , 在當 $K(t)$ 達到 $ϵL_0$ 水準之後，$K(t)$ 將會迅速增長到 $(1-ϵ)L_0$ 。現在，當 $K(t)$ 相對於 $L_0$ 非常小的時候，我們可以捨棄掉方程（4）右邊最後一項。同時，用 $K(t)-h{\displaystyle \frac{dK(t)}{dt}}$ 代替 $K(t-h)$ ，我們可以得到方程（4）的簡化版（記住 ${\displaystyle \frac{\lambda h}{L_0}}={\displaystyle \frac{1}{2}}$):

(5) ${\displaystyle \frac{dK(t)}{dt}}\approx {\displaystyle \frac{1}{2h}}K(t-h)$

其中邊界條件為 $K(0)=1$。我們打算尋$K(t)=exp(c{\displaystyle \frac{t}{h}})$形式的解；帶入(5)之後，我們得到:
${\displaystyle \frac{c}{h}}exp(c{\displaystyle \frac{t}{h}})\approx {\displaystyle \frac{1}{2h}}exp(c{\displaystyle \frac{t}{h}}-c)$

因此，
(6)$K(t)=exp(W({\displaystyle \frac{1}{2}}){\displaystyle \frac{t}{h}})\approx exp(0.352{\displaystyle \frac{t}{h}})$
這是一個近似解，這裡的W(。)是所謂的Lambert W-function。同時對式(6)左右兩邊取對數，我們可以得到K(t)2達到$ϵL_0$所需要的時間大約為:
(7) $t_0\approx {\displaystyle \frac{h}{W({\displaystyle \frac{1}{2}})}}\times (ln{L}_0-ln{ϵ}^{-1})\lesssim 2.84hln{L}_0$

再回到方程（3）（並且，如前面一樣，捨棄掉右邊最後一項），我們可以得到在 「調整階段」（例如，在 $t\le t_0$ 的時候， $t_0$ 為（7）式的結果）具有如下方程：

$$\begin{gathered} \frac{dH(t)}{dt}\approx \frac{2\lambda }{L_0}K(t-h)\approx \frac{1}{hexp(W(\frac{1}{2}))}exp(W(\frac{1}{2})\frac{t}{h}) \\ =\frac{2W(\frac{1}{2})}{h}exp(W(\frac{1}{2})\frac{t}{h}) \end{gathered}$$

因此，
(8) $H(t)\approx 2exp(W({\displaystyle \frac{1}{2}}))\approx 2exp(0.352{\displaystyle \frac{t}{h}})$

圖 4. 累積權重的增長

在此提醒讀者，如前述所討論的，在調整階段之後，累積權重 $H(t)$ 會隨著速度 $\lambda$ 線性增長。我們需要強調的是在（9）式中的「指數增長」並不意味著在調整階段累積權重增長「十分的迅速」，圖 4 中表示了其行為。

同時，我們認為這一節中的計算在可以輕易的套用在平均 $s>1$ 筆交易的情況下。在那樣的情況下，只需要在（2）中將 2 用 $s$ 代替（但是在（4）中不可以），並在（3）和（6）-（9）中把 $\ln 2$ 替換為 $\ln s$ 。

結論

1. 在低負載區，在我們的交易被驗證過幾次之後，其累積權重將以 $\lambda w$ 的速度增長，其中 $w$ 是一筆普通交易的平均權重。
2. 在高負載區，同樣的，在我們的交易被驗證過幾次之後，其累積權重在所謂的調整區間按照公式（8）不斷加速增長，而在調整階段完成之後，其增長速度為 $\lambda w$ ，如圖 4 所示。事實上，對於任何合理的策略，交易的累積權重經過調整階段之後，都將以上述速度增長，因為本質上來說，所有新進入系統的交易都將間接驗證我們的交易。
3. 可以想像調整階段就是直到大部分的 tips 都間接驗證我們的交易的時候。公式（7）中給出了典型的調整階段時間長度。

4. 可能的攻擊情況

讓我們在討論一個攻擊方案，當攻擊者試圖「趕上」整個網路：

1. 攻擊者付款給商家，在商家認為交易已經獲得了足夠大的累積權重之後，攻擊者拿到了商品；
2. 接下來攻擊者發佈了一筆雙重支付的交易；
3. 攻擊者同時發送大量較小的交易（非常多，使用它所有的計算能力），這些交易不直接或者間接驗證原始的付款交易，而是去驗證那筆雙重支付的交易；
4. 可以看到攻擊者也許就擁有大量的女巫攻擊身份，並且不對 tips 進行驗證；
5. 在第 3 步中，也可以採用另外的一種方案，攻擊者使用所有它的計算能力去發送一筆「大」的雙重支付交易（具有非常大的自身權重），並驗證在原始付款交易之前的交易；
6. 攻擊者期望他的 sub-DAG 超越主體 DAG，從而使得 DAG 持續從攻擊者的雙重支付交易進行增長，以便使得之前合法的支付交易被拋棄掉（如圖 5 所示）。

事實上，接下來我們可以看到這種大權重的雙重支付交易策略可以增加攻擊者成功的機率。而且，在這種數學模型的「理想」情況下，這種攻擊「總是」可以成功的。

假設 $W^{(n)}$ 為獲得權重為 $3^n$ 的雙重支付交易的 nonce 的時間。我們可以假設 $W^{(n)}$ 是一個以 $\mu 3^{-n}$ 為參數（比如，期望值為 ${\mu }^{-1}{3}^n$ ）的指數分佈的隨機變數，其中 $\mu$ 表示攻擊者的計算能力。

圖 5 「大權重」攻擊

假設商家在一筆合法交易的累積權重達到至少 $w_0$（這對應這筆原始交易經過 $t_0$ 個時間單位）之後才被接受，因此可以認為其累積權重將以線性速度 $\lambda w$ 增長，其中 $\lambda$ 是系統中交易（由誠實使用者發送的交易）的總體到達速率，而 $w$ 是一般交易的平均權重。記 $w_1=\lambda w{t}_0$ 為在商家接受交易時合法分支的總權重。

假設 $\lceil x\rceil$ 是大於或等於 $x$ 的最小整數，定義 $n_0=\lceil {\displaystyle \frac{\ln w_1}{\ln 3}}\rceil$ ，那麼 $3^{n_0}\ge w_1$ （事實上，如果 $w_1$ 較大，$3^{n_0}\approx w_1$ ）。如果在 $t_0$ 時間間隔內，攻擊者設法獲得了一個 nonce 以使得權重至少為 $3^{n_0}$，那麼攻擊就成功了。這種成功攻擊的概率是
$\mathbb{P}[W^{(n_0)}<t_0]=1-\exp (-3^{-n_0}{t}_0\mu )\approx 1-\exp (-t_0\mu w_1^{-1})\approx {\displaystyle \frac{t_0\mu }{w_1}}$

（至少在 ${\displaystyle \frac{t_0\mu }{w_1}}$ 很小的情況下，這是合理的假設）。然而，如果這種「即刻」攻擊沒有成功的話，攻擊者可以繼續尋找 nonce 以使得權重為 $3^n$ ，其中 $n>n_0$，並希望在找到 nonce 的時候，合法交易分支的總權重要小於 $3^n$。這種情況的概率是
$\mathbb{P}[\lambda w{W}^{(n_0)}<3^n]=1-\exp (-\mu 3^{-n_0}\times (3^{-n_0}/\lambda w))=1-\exp (-\mu /\lambda w)\approx {\displaystyle \frac{\mu }{\lambda w}}$

也就是說，儘管 ${\displaystyle \frac{\mu }{\lambda w}}$ 一般情況下應該是很小，在每一個 $n$ 值水準下，攻擊成功具有恒定的機率。因此，最終總是可以攻擊成功。事實上，攻擊成功的典型耗時大概是 $3^{\lambda w/\mu }$ 。儘管這個數量也許非常大，但是「第一次」（在時間 $t_0$ 內）成功攻擊的機率依然不會很小。因此我們得到如下的結論：我們需要對策（如前面第 3 節所提到的，後面的那種策略也許不是最好的方案，因為那樣不能為垃圾交易攻擊提供足夠的保護）。

那麼現在我們來討論當最大權重具有上限，比如說上限為 1 的時候，估算攻擊成功的概率。

假設給定的一筆交易在發送後經過 $t_0$ 時間單位後，獲得累積權重為 $w_0$ ，並假設這筆交易的調整階段已經結束，因此其累積權重以 $\lambda$ 的速度線性增長。現在，攻擊者試圖對這筆交易進行雙重支付攻擊；因為在第一筆交易發送的時候，他私下秘密準備了雙重支付交易，並且開始生成其他的交易來驗證這筆雙重支付交易。如果在一定的時候（在商家決定接受第一筆合法的交易之後），攻擊者的 Subtangle 的權重要大於合法交易 Subtangle 的權重的話，雙重支付攻擊就會成功。如果上述條件不成立的話，那麼 雙重交易就不會被其他交易驗證（因為合法的交易將獲得更多的累積權重並且所有新的 tips 都會間接驗證這筆交易），因此雙重支付也就成為了孤立交易了。

如前所述，假定 $\mu$ 為攻擊者的計算能力(交易的產生速度)，我們也假設交易是立即被傳播出去的。假定 $G_1,G_2,G_3...$ 是以 $\mu$ 為參數（期望值為 $1/\mu$）的獨立同分佈的指數分佈變數，並記 $V_k=\mu G_k$，$k\ge 1$。很顯然，$V_1,V_2,V_3...$ 是以 1 為參數的獨立同分佈的指數分佈的變數。

假設在 $t_0$ 時刻商家決定接受交易（記住這時這筆交易的累積權重為 $w_0$ ）。讓我們來估算一下攻擊者成功完成雙重支付攻擊的機率。記 $M(\theta )=(1-\theta {)}^{-1}$ 是以 1 為參數的指數分佈的隨機變數的生成函數的矩（參考文獻[14]中 7.7 節）。對於 $\alpha \in (0,1)$，
於是有如下公式成立:
(10) $\mathbb{P}[\sum _{k=1}^n{V}_k\le \alpha n]\approx \exp (-n\phi (\alpha ))$

其中 $\phi (\alpha )=-\ln \alpha +\alpha -1$ 是對 $\ln M(-\theta )$ 的拉格朗日變換。請注意，作為一個一般事實，對於任意 $\alpha \in (0,1)$，$\phi (\alpha )>0$ 是成立的（想像指數隨機變數 Exp(1)的期望值等於 1）。

假定 ${\displaystyle \frac{\mu t_0}{w_0}}<1$（否則，攻擊者的 Subtangle 最終超過合法的機率就接近於 1）。現在，為了在 $t_0$ 時刻超過 $w_0$ ，攻擊者需要在 $t_0$ 時間單位內至少發送具有 $w_0$ 筆權重為 $m$ 的交易。因此，通過公式（10），我們可以得到雙重支付交易在 $t_0$ 時刻有更大累積權重的機率大概是
(11) $P[\sum _{k=0}^{w_0/m}{G}_k<t_0]=P[\sum _{k=1}^{w_0}{V}_k<\mu t_0]=P[\sum _{k=1}^{w_0}{V}_k<w_0\times {\displaystyle \frac{\mu t_0}{w_0}}]\approx \exp (-w_0\phi ({\displaystyle \frac{\mu t_0}{w_0}}))$

也就是說，上述機率非常小，我們通常需要的 ${\displaystyle \frac{w_0}{m}}$ 是相當大，並且 $\phi ({\displaystyle \frac{\mu t_0}{w_0}})$ 不能很小。

類似地，雙重交易在 $t\ge t_0$ 時具有更大的累積權重的概率大概是

(12) $\exp (-(w_0+\lambda (t-t_0))\phi ({\displaystyle \frac{\mu t}{w_0+\lambda (t-t_0)}}))$

注意到，通常我們有 ${\displaystyle \frac{\mu t_0}{w_0}}\ge {\displaystyle \frac{\mu }{\lambda }}$（因為在調整階段，累積權重增長的速度小於 $\lambda$ ）。

無論如何，可以得到成功進行雙重支付的機率大概為

(13) $\exp (-w_0\phi (max({\displaystyle \frac{\mu t_0}{w_0}},{\displaystyle \frac{\mu }{\lambda }})))$

比如，假設 $\mu =2$, $\lambda =3$（因此攻擊者的計算能力只是比網路中其他算力稍微小一點點）。假設在時間 12 的時候，交易獲得累積權重為 32。那麼， $max({\displaystyle \frac{\mu t_0}{w_0}},{\displaystyle \frac{\mu }{\lambda }})={\displaystyle \frac{3}{4}}$, $\phi ({\displaystyle \frac{3}{4}})\approx 0.03768$ ，公式（13）給出的上限大概是 0.29. 然而， 我們假設 $\mu =1$（並保持其他參數不變 ）， 那麼 $max({\displaystyle \frac{\mu t_0}{w_0}},{\displaystyle \frac{\mu }{\lambda }})={\displaystyle \frac{3}{8}}$, $\phi ({\displaystyle \frac{3}{8}})\approx 0.3558$，公式（13）得到大約是 0.00001135，確實有很大的變化。

通過上述討論，我們觀察到很重要的一點就是，為了系統的安全，必須確保 $\lambda >\mu$（否則，公式（13）的估算就沒有什麼用）；比如，系統中誠實交易的輸入相對於攻擊者的計算能力要足夠的大。這也意味著在 IOTA 的早期，需要額外 的安全措施（比如檢查點的方式）。

同時，對於如何決定兩個相互衝突的交易中哪一筆是合理的交易的策略來說， 僅依靠累積權重判斷的我們必須十分小心謹慎。這是因為可能受制於在 4.1 節中所描述的類似的攻擊（攻擊者也許會提前准備好雙重交易，構建一個 Subchain/Subtangle 來指向驗證這筆雙重支付交易，然後在商家接受交易之後將這個 Subtangle 廣播出去）。然而，在下一節中我們將提出一個更好的方法來處理兩筆相互衝突的交易：運行 tip 選擇演算法，然後看這兩筆交易中哪一筆交易（間接）被選取的 tip 所驗證。

4.1 寄生鏈攻擊

考慮圖 6 中的如下攻擊：攻擊者秘密打造一個 Subtangle，並偶爾指向驗證主網路，從而獲得更多的積分（注意好的 tips 的積分大概是主網路中所有自身權重之和，而攻擊者的 tips 還包含寄生鏈中所有的自身權重）。同時，對於單獨打造這個鏈的攻擊者來說，他有足夠強大的電腦，網路延遲不是問題，因此攻擊者能夠獲得到寄生 tips 具有更高高度的寄生鏈。最後，只要誠實節點所使用的選擇策略是在已有的 tips 中進行一些簡單選擇的話，攻擊者的 tips 數量在攻擊的時候可以任意增加。

為防禦這種攻擊，我們基於主 tangle 中具有更多活躍的雜湊算力的事實，因此相對於攻擊者來說，可以使得更多的交易獲得更多的累積權重。演算法的核心思想是使用 MCMC（馬可夫鏈蒙地卡羅）演算法來選擇兩個 tips。
假設某一筆交易目前的累積權重為 $H_x$ (如一筆在 Tangle 上的交易)，再次提醒，我們假設所以交易的自身權重等於 1；因此 tip 的累積權重總是 1，而其他交易的累積權重至少是 2。

這樣做是為了在 Tangle 的節點上佈下一些點(隨機漫步者 (random walker))，讓他們朝著 tips 隨機行走。而被隨機漫步者挑中的 tips 就是待被驗證的候選交易。

具體演算法描述如下：

1. 考慮累積權重在 $W$ 和（假定） $2W$ 之間的所有交易（其中 $W$ 是很大的一個數，數值待定）；
2. 獨立選擇放置 $N$ 個隨機漫步者（$N$ 不是很大，比如說為 10）；
3. 那些隨機漫步者將進行離散時間隨機行走到 tips（比如，當且僅當 $y$ 能夠驗證 $x$，就可以從 $x$ 轉到 $y$）；
4. 兩步行走能到達開始設定的 tip 的話，這就意味著這是我們要進行驗證的兩個tips(然而，更好的做法是依照著個原則修改規定: 捨棄那些「太快」走到 tips 的隨機漫步者: 他們可能走到「懶惰的 tips」)；
5. 隨機行走轉移機率按如下方式進行定義：如果 $y$ 驗證 $x$（我們記做 $y\to x$ ）， 那麼轉移概率 $P_{xy}$ 是正比於 $\exp (-\alpha (H_x-H_y))$，也就是

(14) $P_{xy}=\exp (-\alpha (H_x-H_y))(\sum _{z:z\to x}^{}\exp (-\alpha (H_x-H_z)){)}^{-1}$

其中 $\alpha >0$ 是一個待選取的參數（可以從 $\alpha =1$ 開始）。需要注意的是這個演算法是局域性 (local) 的，我們不需要遍歷到創始交易來計算所有的東西。
為了說明這個演算法如我們所想像的那樣工作，首先考慮那些「懶惰的 tips」（那些故意認證一些較早的交易以避免進行交易的驗證），如圖 6 所示。注意到，即使某個交易被這樣的一個 tip 所驗證，也不太可能使得懶惰的 tip 被選中，因為從公式（14）可見累積權重差異非常大。

接下來，考慮如下的攻擊：攻擊者秘密地構建一條鏈（「寄生鏈」），其中包含一筆交易用來從他的一個帳戶清空轉移到他控制的另一個帳戶中（如圖 6 中左邊的紅色圓圈）。在某一個時刻，攻擊者在主 tangle 中發起另一筆交易（如圖 6 中另一個紅色圓圈），並等待直到商家接受它。寄生鏈偶爾驗證指向主 tangle（因此得名），從而使得寄生鏈具有很好的高度和積分（甚至比主 tangle 還要好），儘管其累積權重並不是特別大。同時注意到寄生鏈在商家的交易之後不能夠再驗證指向主 tangle 了。而且，攻擊者也可以試圖在他攻擊的時候人為地任意增加他的 tips，如圖 6 所示。攻擊者的想法和目標是要使得其他交易來驗證和指向寄生鏈，從而使得「好的」tangle 被孤立。

圖 6 tip 選擇演算法。兩個紅色圓圈所代表的是試圖進行雙重攻擊的交易。

現在可以很容易地看到為什麼 MCMC 選擇演算法具有很高的機率不去選擇攻擊者的 tips 中的任何一個。這個演算法也同樣不會去選擇那些「懶惰」的 tips，其原因基本上是一樣的：寄生鏈上的交易相比於那些他們指向的主 tangle 上的交易的累積權重要小得多。因此，隨機行走不太可能會跳到寄生鏈（除非從寄生鏈開始，但是這也不太可能，因為主 tangle 包含更多的交易）。

這裡提供一個附帶的保護措施，我們可以先用較大的$\alpha$值跑出一個「理想的 tip」(幾乎是決定性的)，再用較小的 $\alpha$ 執行真正的 tip 的選擇。然後比對我們驗證的交易是否跟「理想的 tip」一樣

我們也可以發現，直接使用遞迴，便可以簡單快速地計算出口的機率分布;這是我們不希望節點做的事。然而或許可以用以下的手法，改變我們的方法:每一步的隨機漫步中，有 ${\displaystyle \frac{1}{3}}$ 的機率會往回走(遠離 tips 一步)。這種漫步最後會快速地到達 tips (因為它會漂移的前往 tips)，但是難以計算這種替代措施的效能(?)

接著讓我們說明為什麼節點要遵循這個演算法(至少很相像)。回顧我們在第 1 節所觀察到的，假設至少一定「好的」比例的節點會遵循參考的演算法是非常合理的。而且因為計算力及網路延遲，tip 選擇演算法會傾向針對過去 tangle 的狀態計算(在發起交易的當下狀態)。現在，故意採用更久以前的狀態可能是個好主意，如我們一直以來的解釋。想像一個「自私的」節點只想增加他的交易被驗證的機會。這節提到的 MCMC 演算法定義了一個機率分佈的 tips 集合，更明確的說，對於節點而言，第一首選的 tip 會是機率最大的。然而，若其他節點也很「自私」而且用相同方法的話，那他們全部都會失敗：許多新交易會在同一時間驗證相同的兩個 tips，因此在接下來的驗證過程會有太多競爭(因為節點都用過去的狀態，他們不會察覺在大量的驗證下，這兩個 tips 的累積權重的增加)。因此，即使是自私的節點也會採用隨機的 tip 驗證演算法，而被選到的 tips 的機率與原本的機率分佈應該相差不遠。我們並沒有宣稱這個機率分佈的總和會等於原本的機率和，但上述的討論我們可以發現，兩者應該很接近。這表示選擇「壞」tip 的機率應維持低機率。在任何情況，並沒有太多的誘因讓自私的節點存在，因為只有微量減少其驗證時間。節點也並沒有理由放棄 MCMC tip 選擇演算法。

同樣，轉移機率也不一定如（14）那樣所定義的一成不變。除了指數函數外，我們還可以選擇其他衰減更快的函數，比如 $f(s)=s^{-3}$。可以自由的選擇 $W$ 與 $N$。事實上，作者覺得這一節最主要的貢獻就是提出 MCMC 當作 tip 選擇演算法；還未有更明確的「理論」論點告訴我們該如何設定這些參數。

4.2 分裂攻擊

針對 MCMC 演算法的如下攻擊策略由 Aviv Zohar 提出。在高負載區，攻擊者可以試圖將 tangle 分裂成兩個分支，並在這兩個分支中均保持自己的餘額，從而兩個分支繼續增長。為避免這種情況，誠實的節點會同時指向兩個分支（有效地合併兩個分支），攻擊者則必須在分裂開始的時候放入至少兩個相互衝突的交易。 然後，他/她就希望大概網路中各一半的交易貢獻給兩個分支，從而可以「補償」 無規漲落，即使他所擁有的只有相對較小的計算能力。這樣，攻擊者就可以在兩 個分支中都可以使用這筆資金。

為了抵抗這種攻擊，我們需要使用一些「高門檻」的規則（類似於比特幣中選擇最長的鏈）來使得同時維持兩個分支上的餘額是十分困難的。比如，假定一個分支具有總的權重（或者是其他我們可以使用的計量方式）為537，而另一個分支的總權重與此十分接近，比如說為 528。如果在這種情況下，一個誠實的節點選擇第一分支的概率就非常接近於 1/2，這樣很可能攻擊者也可以在兩個分支中都保持帳戶餘額。然而，如果誠實節點偏向於第一分支的概率比 1/2 要大很多的話，那麼攻擊者就很難維持兩個分支的餘額，因為經過不可避免的無規漲落， 網路會迅速選擇其中的一個分支，而拋棄掉另一個分支。很顯然，為了使得 MCMC 演算法具有這樣的行為，我們需要選擇一個迅速衰減函數 f，並且在一個相對較大 深度的節點開始進行無規行走（這樣就可以極大可能性地在網路分裂之前啟動無規行走）。這種情況下，無規行走就會有很大概率選擇「較重」的分支，即使兩 個分支的權重差很小。

當然，也可以考慮其他改進的 tip 選擇演算法。比如說，如果一個節點看到兩個大的 Subtangles，那麼就選擇其中自身權重之和較大的一個分支，然後進行上述的 MCMC 演算法。
而且，如下思路也許值得考慮： 設想在（14）中的轉移概率不僅僅與 $H_x-H_y$ 相關，而且還依賴於 $H_x$ ，這樣接下來的馬可夫鏈在無規行走的時候進入較深的 tangle 中（避免進入較弱的分支）就近乎是確定性的，而當接近于 tips 的時 候，無規行走就更分散一些（因此也就有足夠的隨機性來選擇兩筆交易進行驗證）。

結論：

1. 在攻擊者試圖超越網路進行雙重交易時，我們考慮了幾種攻擊策略。
2. 「大權重」攻擊意味著，為了進行雙重，攻擊者試圖發起一筆大權重雙重交易，從而超過合法的 Subtangle。這種攻擊在交易的自身權重不設上限的情況下，對於網路的確是一個威脅。因此，為了解決這個問題，我們可以限制交易的自身權重上限，或者將自身權重設為常數。
3. 當交易自身權重最大值為$m$的時候，攻擊者最好的策略是發起和生成的每筆交易都具有最大權重值，並且指向驗證雙重交易。如果交易輸入流中的誠實 交易相比攻擊者的計算能力要足夠大的時候，那麼雙重交易具有更多的累積權重的概率可以通過公式（14）來進行估計（同時也可以參考（14）下面的 例子）。
4. 構建「寄生鏈」的攻擊可以使得基於高度和積分的驗證策略無效，因為攻擊 者可以得到比合法 tangle 更高的積分。與此相反，4.1 節中描述的瑪律科夫蒙特卡洛 tip 選擇演算法可以抵抗這種攻擊。
5. 此外，上述方法還可以抵抗「懶惰節點」，也就是那些僅僅驗證很早之前的交易，而避免進行必要的計算來驗證 tangle。

5 抵抗量子計算

眾所周知（今天仍然只是假設），足夠大的量子電腦在解決那些只能通過猜測結果並重複進行檢驗的問題時具有極高的效率。為生成一個比特幣區塊而尋找 nonce 就是這類問題中的一個很好的例子。在目前，平均來說必須查找 $2^{68}$ 個 nonces 從而找到一個合適的雜湊值來生成區塊。眾所周知（例如文獻 [15]）量子電腦在解決上述類似的問題時的複雜度為 $\mathrm{\Theta }(\sqrt{N})$，而對於經典的電腦其複雜度則是 $\mathrm{\Theta }(N)$ 。因此量子電腦在比特幣挖礦方面相比常規的礦機具有 ${\sqrt{2}}^{68}=2^{34}\approx 170$億倍的效率。同時，請注意，如果區塊鏈在面對雜湊運算能力增加的時候不能夠同時增加挖礦難度的話，那麼這就將導致大量孤塊的增加。

基於相同的原因，我們可以看到上述所描述的「大權重」攻擊在量子電腦上同樣具有更高的效率。然而，前面所講的權重上限設置（如第 4 節所建議的） 因為如下的理由，可以有效地抵抗量子電腦的攻擊。在 IOTA 系統中，為發送交易而需要尋找合適的雜湊時，其尋找的 nonces 空間並不是很大，大概是 $3^8$ 左右。因此對於一個「理想」的量子電腦來說，其效率的提高也就在 $3^4=81$ 倍這個數量級，這相對來說是可以接受的（記住 $\mathrm{\Theta }(\sqrt{N})$ 也許意味著大概是 $10\sqrt{N}$）。而且，在 IOTA 的演算法中，發送交易的時候，尋找 nonce 所需要的時間不比其他任務所需要的時間多很多，而後面提到的那部分任務相對來說是更容易抵抗量子電腦的。

因此，上述討論表明 Tangle 相對於（比特幣）區塊鏈來說提供了更好的抵抗量子電腦的技術。

參考文獻

[1] Iota: a cryptocurrency for Internet-of-Things. See http://www.iotatoken.com/, and https://bitcointalk.org/index.php?topic=1216479.0

[2] bitcoinj. Working with micropayment channels. https://bitcoinj.github.io/working-with-micropayments

[3] people on nxtforum.org (2014) DAG, a generalized blockchain.
https://nxtforum.org/proof-of-stake-algorithm/dag-a-generalized-blockchain/
(registration at nxtforum.org required)

[4] Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar (2012) On Bitcoin and red balloons. Proc. 13th ACM Conf. Electronic Commerce, 56-73.

[5] Richard Durrett (2004) Probability - Theory and Examples. Duxbury advanced series.

[6] Sergio Demian Lerner (2015) DagCoin: a cryptocurrency without blocks.
https://bitslog.wordpress.com/2015/09/11/dagcoin/

[7] Yonatan Sompolinsky, Aviv Zohar (2013) Accelerating Bitcoin's Transaction Processing. Fast Money Grows on Trees, Not Chains.
https://eprint.iacr.org/2013/881.pdf

[9] Yoad Lewenberg, Yonatan Sompolinsky, Aviv Zohar (2015) Inclusive Block Chain Protocols.
http://www.cs.huji.ac.il/~avivz/pubs/15/inclusive_btc.pdf

[10] Joseph Poon, Thaddeus Dryja (2016) The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments.
https://lightning.network/lightning-network-paper.pdf

[11] Sheldon M. Ross (2012) Introduction to Probability Models. 10th ed.

[12] David Vorick (2015) Getting rid of blocks. slides.com/davidvorick/braids

[13] Amir Dembo, Ofer Zeitouni (2010) Large Deviations Techniques and Applications. Springer.

[14] Sheldon M. Ross (2009) A First Course in Probability. 8th ed.

[15] Gilles Brassard, Peter Hyer, Alain Tapp (1998) Quantum cryptanalysis of hash and claw-free functions. Lecture Notes in Computer Science 1380, 163-169.