在part2中，我們學(xué)習(xí)了unweighted random walk選擇算法。本章節(jié)，我們將學(xué)習(xí)更高級的變形算法：the weighted random walk。
算法the weighted random walk的其中一個(gè)核心作用是避免lazy tips 被選擇認(rèn)證。這里，lazy tips 的定義為，新加入的交易在選擇tangle 中的交易認(rèn)證時(shí)，選擇一個(gè)舊的交易認(rèn)證，而不是選擇最近的tip 交易認(rèn)證。一方面，我們知道，一筆交易只有被認(rèn)證了，才會(huì)對tangle 的狀態(tài)作出變更，并將該筆被認(rèn)證的交易進(jìn)行網(wǎng)絡(luò)廣播，然后在由別的tangle 節(jié)點(diǎn)進(jìn)行狀態(tài)變更。換言之，如果一筆新交易選擇了一筆舊交易（已經(jīng)被認(rèn)證過）再次進(jìn)行認(rèn)證，雖然說，舊交易能被認(rèn)證成功，但該交易已經(jīng)被執(zhí)行狀態(tài)變更，因此，該就交易不會(huì)在二次變更。這樣一來，不僅沒有新的tip 交易被認(rèn)證，而且對于整體的tangle 網(wǎng)絡(luò)來說也不會(huì)有一點(diǎn)幫助。
在圖1-1 的例子中，交易14 則被認(rèn)為時(shí)lazy tip,因?yàn)樗x擇了交易1 和交易 3 兩筆已經(jīng)被認(rèn)證過的交易再次進(jìn)行認(rèn)證。如果我們使用的是uniform random 的tip 選擇算法，交易14 同樣可能不會(huì)被選擇。同樣，在part2 所介紹的 unweighted walk算法會(huì)有同樣的問題，甚至?xí)鼑?yán)重，因?yàn)楦鶕?jù)unweighted walk選擇算法，在游歷者選擇過程中，不管是 tip 交易還是非tip 交易，它的選擇概率是一致的，但游歷者是從genesis 交易開始選擇，換言之，lazy tip的出現(xiàn)概率會(huì)大于uniform random 算法。
那么，如何來處理lazy tip 所帶來的問題？在提出解決方案前，這里可以明確的是，我們無法強(qiáng)制任何的交易去選擇較新的tip，因?yàn)檫@會(huì)與去中心化的理念想違背。相反，任何新交易都可以自愿選擇tangle 中的任意一筆交易進(jìn)行認(rèn)證。另外，我們也不能提供一個(gè)自認(rèn)為可靠的規(guī)則去強(qiáng)制新到來交易進(jìn)行選擇認(rèn)證。
我們的解決方案是通過一種系統(tǒng)內(nèi)置的激勵(lì)行為，帶權(quán)重的隨機(jī)游歷，即the weighted random walk來盡量避免lazy tip 被選擇。具體的策略是，每一筆交易都會(huì)一個(gè)累計(jì)權(quán)重( term cumulative weight)來指明自身的重要性。累計(jì)權(quán)重的定義非常簡單：統(tǒng)計(jì)直接或間接證明該交易的交易數(shù)即可。例如圖1-2 的例子中，交易[3] 的累計(jì)權(quán)重為5(交易[5] 為直接認(rèn)證交易，交易[7]、[8]、[10]為間接認(rèn)證一共為4，但計(jì)算時(shí)，都會(huì)加上自身，則為5)。
我們在通過圖1-3 的例子來闡述為什么該算法可以有效的避免lazy tip 被選擇。根據(jù)定義，交易[16]為lazy tip。如果交易[16]被選擇，前提條件時(shí)游歷者必須游歷到交易[7],因此，會(huì)面臨 交易[9] 以及交易[16] 兩個(gè)選擇，而交易[9] 的累計(jì)權(quán)重為7，遠(yuǎn)大于交易[16]的累計(jì)權(quán)重1，因此，交易[9]會(huì)大概率被選擇并進(jìn)行移動(dòng)，而交易[16] 基本不可能被選擇。這樣一來，則可以避免lazy tip 被選擇認(rèn)證。
這時(shí)，我們會(huì)有個(gè)疑問：the weighted random walk 中的隨機(jī)性還需要嗎？因此，我們提出一種變形算法the super-weighted random walk。該算法的核心則是在the weighted random walk的基礎(chǔ)上進(jìn)行調(diào)整。即在路徑選定過程中完全按照累計(jì)權(quán)重因素，不涉及任何概率運(yùn)算。按照新變形的算法，tangle 的圖形會(huì)大致演變成圖1-4。
從圖4-1的例子中，我們可以看出如果，整個(gè)tangle 網(wǎng)絡(luò)一直使用the super-weighted random walk算法，walker 只往權(quán)重大的交易游歷，這樣一來會(huì)帶來新的問題，會(huì)有大量的交易將永遠(yuǎn)無法被選擇認(rèn)證。
為了盡量規(guī)避the super-weighted random walk算法所引伸出的問題。我們提出了另一個(gè)解決方案?；叵胍幌?，the super-weighted random walk僅通過權(quán)重因素來精確得出walker 交易選擇路徑，但細(xì)想一下，我們無需這么精確，我們只需盡量偏向權(quán)重高的交易即可。所以，我們引進(jìn)一個(gè)新的參數(shù)α。參數(shù)α 意味著偏向累積權(quán)重的重要性。精確的定義可在白皮書中查看，當(dāng)然這篇文章 也從數(shù)學(xué)角度給出準(zhǔn)確的定義。
雖然說白皮書有詳盡的定義，但還是來概要說明一下該參數(shù)的具體含義。如果我們設(shè)定參數(shù)α 值為0，則意味著該算法會(huì)回退成unweighted walk。反之，如果α 的值特別高，算法則會(huì)進(jìn)化成 super-weighted walk。因此，我們需要尋找一個(gè)相對平衡的值，來確保既可以盡量避免lazy tip 被選擇，也可以盡量避免tip 永不被選擇的情況出現(xiàn)。而 確認(rèn)一個(gè)理想的α 值是IOTA 一個(gè)重要的研究課題。
具體的方式是通過設(shè)定一種指定的規(guī)則，在該規(guī)則下，使得walker在隨機(jī)游歷過程中的每一步，都可以計(jì)算出具體的概率。該規(guī)則稱為馬爾可夫鏈蒙特卡羅技術(shù)（ Markov Chain Monte Carlo，簡稱MCMC）。在馬爾可夫鏈中，下一步的概率計(jì)算不依賴于前一步，而是遵循預(yù)先確定的規(guī)則。
到這里，本文完畢。我們將在下意章節(jié)中，詳細(xì)講解 一筆交易認(rèn)證 另一筆交易是什么含義，并且 進(jìn)一步了解何時(shí)可以確認(rèn)一筆交易。
