這是我們剛剛實(shí)現(xiàn)的一個基于STAG的框架。我們把它命名為Graphchain。接著我們會討論設(shè)計(jì)選擇和主要挑戰(zhàn)，最后給出結(jié)論。

如果你對它的來源感興趣，最初我和Xavier Boyen、Thomas Haines一起在2016年寫了這篇論文——Graphchain：一種無區(qū)塊鏈的可擴(kuò)展去中心化賬本。我們把它放到了ePrint上，在ERIM News上可能有一個更可讀的版本。這篇論文在其他地方也有發(fā)表，但這兩個地方可能最容易找到。

什么是DAG？

首先，DAG是什么含義？它指的是有向無環(huán)圖。這是圖論中的一個數(shù)學(xué)術(shù)語，通常包含由頂點(diǎn)和邊組成的集合。邊就是有序的頂點(diǎn)對，在有向圖中通常用箭頭表示。如果不能從一個頂點(diǎn)出發(fā)，沿著箭頭返回一個頂點(diǎn)，那么圖就是無環(huán)的。你也許意識到這不完全是一個數(shù)學(xué)術(shù)語。

下圖是一個DAG的例子。箭頭表示邊，橙色的方框表示頂點(diǎn)。你可以通過檢查發(fā)現(xiàn)圖中沒有環(huán)。你不能從其中一個橙色方框出發(fā)，沿著箭頭返回一個橙色方框。這就是一個DAG。你也可以給這些DAG加上標(biāo)記。

如果這樣做，你將得到一個所謂的偏序集。在我們所做的工作中，談及了很多關(guān)于偏序集。這里的思想是，如果你定義箭頭指向一個比出發(fā)點(diǎn)更高的頂點(diǎn)從而得到一個偏序，那么你會很容易發(fā)現(xiàn)k是所有字母中最高的那一個。你也可以很快發(fā)現(xiàn)對于f和h，它們之間沒有排序。我們所知道的就是f和h都高于d并且都低于i。

因此，它是一個偏序，不像我們所熟悉的另一種DAG，即區(qū)塊鏈（下圖），它是完全有序的。實(shí)際上，如果你開始思考如何處理這些孤塊，以及會有多少孤塊，你會發(fā)現(xiàn)這真的很有意思。我沒有時(shí)間深入這個話題，但它真的很有意思，相信我。你會得到分叉，但是區(qū)塊鏈本質(zhì)上也是DAG，只是他們受到的限制更多。你無法擁有所有這些額外的偏序。

為什么我們需要DAG？

我們想要解決什么？這里我們試圖解決的主要問題是去中心化和擴(kuò)展性。區(qū)塊鏈技術(shù)存在很多問題。這可能是最常被談?wù)摰膬蓚€問題——還有一些其他問題，但我最感興趣的兩個問題是去中心化問題，這實(shí)際上歸結(jié)為安全問題，以及可擴(kuò)展性問題，這和可用性相關(guān)。擴(kuò)展性問題仍然存在。這些問題是從哪里來的？這些問題似乎源于交易塊的使用？可能是這樣的。

我們整個項(xiàng)目的目標(biāo)是：能否創(chuàng)建一個系統(tǒng)，讓個體的努力得到回報(bào)？主要的問題，可能你已經(jīng)意識到了，是礦池造成了一些問題。它們造成問題的原因是實(shí)際上它們的權(quán)力有點(diǎn)太大了——有些人認(rèn)為它們權(quán)力過大。我傾向于這樣理解。這不一定是壞事，有很多支持和反對它們的論據(jù)，我真的不想卷入這個話題，但是如果我們不需要它們不是更好嗎？

我們能否消除加入礦池的動機(jī)？這是其中一個問題。此外，這么做的同時(shí)，是否也可以允許更快的交易處理。如果我們可以廣播附加了工作量證明的交易，整理這些交易并用它們構(gòu)建一個圖，會怎么樣呢？那么，我們還需要區(qū)塊嗎？至少，這是基于DAG的思想。

為什么這很重要？因?yàn)?1%的誠實(shí)用戶就足夠了？不！這些我們早就知道了。那么，什么是去中心化呢？這是一個更加棘手的問題。它跟分布式設(shè)計(jì)的概念有點(diǎn)混淆，所以你可能會問去中心化究竟是什么含義。實(shí)際上我認(rèn)為這個問題很難回答。有很多人思考過去中心化的真正含義，特別是在加密貨幣方面。大致上，我們希望全世界有許多運(yùn)行相同系統(tǒng)的獨(dú)立機(jī)器。如果有的話，就可以保證所有機(jī)器在計(jì)算上是等價(jià)的。就像我說的，這不是什么新鮮事物，人們已經(jīng)談?wù)摿艘魂囎恿恕?/p>

我們在談的這些是什么？我們在談?wù)摰V池和礦場。在“全世界運(yùn)行相同系統(tǒng)的獨(dú)立機(jī)器”上——實(shí)際上機(jī)器在運(yùn)行一個礦池系統(tǒng)。并且，從計(jì)算上等價(jià)的機(jī)器的角度來說，我們有礦場。因此，本質(zhì)上我們擁有一臺能力非常強(qiáng)的機(jī)器。第二個問題我不認(rèn)為是DAG必須處理的問題。這取決于功能。

不過，可擴(kuò)展性也是一個主要問題。當(dāng)我們談?wù)搮^(qū)塊鏈時(shí)，為什么需要關(guān)心可擴(kuò)展性？因?yàn)閰^(qū)塊鏈?zhǔn)菂^(qū)塊的線性集合，其中一筆交易引用下一筆交易。問題是，無論處理哪種類型的區(qū)塊鏈，區(qū)塊都包含一定數(shù)量的交易。有某個特定的時(shí)間段內(nèi)可以接收交易。正如我們剛才所聽到的，我們知道以太坊的限制，也知道比特幣的限制。

問題的一部分是因?yàn)槲覀冇袇^(qū)塊，并且將它們和如此多的交易綁定在一起，所以我們可能會有兩個不同的區(qū)塊，其中一個包含交易T1到Tn，另一個包含交易T1到Tn‘。我們不知道它們是否相同——也許它們包含相同的交易列表，也許不是。

使用區(qū)塊鏈，如果發(fā)生了分裂，我們就必須從中選擇一條。這是一種分叉，對吧。因此，我們現(xiàn)在在等著看哪一條會被擴(kuò)展，然后才能確定我們知曉哪些交易。如果我在T’中有一些交易，現(xiàn)在我將不得不等它們稍后在某個地方被包含進(jìn)去。我們不能依賴所包含的交易。

當(dāng)然，這只是通常情況。可以想象一下，由于一些反常的事件，你同時(shí)生產(chǎn)了大量的區(qū)塊。使用區(qū)塊鏈+，即以太坊和ghost協(xié)議的內(nèi)容，你就擁有了可以被包含的叔塊。這真是一個非常聰明的主意，但不會包含里面的交易。因此，你仍然可以獎勵某人的努力，這是關(guān)于創(chuàng)建這個額外區(qū)塊的一個非常明智的想法，因?yàn)槿藗儜?yīng)該因他們的努力而獲得獎勵。

本質(zhì)上，整個想法是：我們是否也可以擁有這樣的系統(tǒng)，你可以在其中創(chuàng)建一個新的區(qū)塊，同時(shí)包含來自T和T‘的交易，也就是這些交易的合集？

這本質(zhì)上就是Graphchain。我們擁有的東西是：如果沒有區(qū)塊會怎么樣？交易只引用之前的交易，隨便多少都可以。要發(fā)送交易，只需要簡單地收集你認(rèn)可的交易并引用它們，并在交易中附上一些工作量證明。

這是如何工作的？

我們可以定義一種抽象的工作量證明函數(shù)。這是一個相當(dāng)抽象的想法，但在實(shí)踐中通過哈希函數(shù)很容易實(shí)現(xiàn)。假定工作量證明函數(shù)S包含問題a和它的一個解b。如果b是a的解的話，我們就說S（a，b）為真。以區(qū)塊鏈為例，解可能是一個nonce，你的a是指交易集合以及和之前區(qū)塊之間的鏈接和所有其他數(shù)據(jù)。

我們想對工作量進(jìn)行量化，從而我們可以說這個工作量證明函數(shù)的工作量=d。我們可以做到這一點(diǎn)，大多數(shù)時(shí)候都可以做到。如果你能部分地反轉(zhuǎn)一個哈希函數(shù)，你可以說它一定花費(fèi)了這么多的計(jì)算量，或者我們期望它花費(fèi)了這么多的計(jì)算量。

因此，我們能夠做到這一點(diǎn)，而且這已經(jīng)發(fā)生了，因?yàn)榈V池本質(zhì)上是在做同樣的事情。如果你為一個礦池工作，你不是先解出這個區(qū)塊，然后把它交給他們，而是通過向他們展示你已經(jīng)解決了一個更小范圍的問題來證明你是在為他們工作。所以，如果是在比特幣中，你可能想要找到低于某個閾值的數(shù)值。你向他們展示你已經(jīng)找到了低于更高閾值的解——但至少它表明你正在為他們工作。

本質(zhì)上，我們可以使用同樣的方法。其目的是量化為解決某個問題所做的工作。抽象函數(shù)可以是任何我們可以量化的尋找問題解的難度。我們甚至不需要哈希函數(shù)，你可以想象用其他方法來實(shí)現(xiàn)這一點(diǎn)。我們再一次試圖把它作為一個框架來設(shè)想。我們可以廣播包含相關(guān)工作量的交易。這樣做的目的是我們可以說：這里有一個區(qū)塊，它的工作量為8。

因此，你再次拿走DAG，然后你可以想象一些數(shù)字，你可以說：好了，現(xiàn)在我們有了所有這些數(shù)字，這意味著什么呢？好問題。我們要做的是定義權(quán)重和高度這兩個概念。這跟區(qū)塊鏈非常相似，因?yàn)槟阌欣鄯e的工作量。一旦我們用工作量對圖進(jìn)行了標(biāo)記，就可以用其他值來標(biāo)記它了。

例如，對于權(quán)重，我們把這種累積工作量和交易及其所有后代相關(guān)聯(lián)。高度是和交易及其所有祖先相關(guān)聯(lián)的累積工作量。例如，你會發(fā)現(xiàn)，權(quán)重本質(zhì)上就是把每一筆交易中的工作量證明的值相加。

所以，我們可以說（下圖），交易的權(quán)重是61。為什么這么說？因?yàn)樗屛覀兟亟⑵痍P(guān)于該交易在系統(tǒng)中的嵌套程度的概念。對于高度，你擁有了一個計(jì)算所有子交易的系統(tǒng)。有趣的是，交易本身也計(jì)算在內(nèi)。所以，對于第二個交易（也在下圖中，深紅色），我們可以說它的高度為80。本質(zhì)上，這只是兩個例子，但我們想說的是，我們可以建立一個概念，即一個交易在圖中的高度是基于它所包含的工作量證明的。

在基于DAG的系統(tǒng)中還需要做一件事。我們需要開始去除進(jìn)一步下降的交易。我們必須這么做的原因是，如果給你一個新的圖，因而你最近沒有看到任何交易，并且你必須即刻計(jì)算出它們有多高，那么隨著系統(tǒng)中交易數(shù)量的增加，它會很快變得非常消耗算力。你必須限制這一點(diǎn)，并最終開始擺脫進(jìn)一步后退的交易。這是一件單獨(dú)的事情。

這種基于DAG的設(shè)計(jì)增加了復(fù)雜性，這非常棘手。本質(zhì)上，我們這么做的目的就是為了獲得這種收斂性。如果交易可以引用任何其他先前的交易，那么通過什么來阻止用戶在非常老的節(jié)點(diǎn)上創(chuàng)建新交易呢？

你需要提供激勵。這也是框架的一部分。我們需要激勵，希望用戶從圖的頂部構(gòu)建新交易，所以獎勵和高度的某種函數(shù)相關(guān)聯(lián)。因此，為了簡單起見，我只寫了這些。然而，這并沒有那么簡單。比如說，如果這個函數(shù)是一個反函數(shù)，那么它將無法正常工作。但是你的確需要高度的某種函數(shù)來創(chuàng)造這種從前面開始工作的激勵。這樣做的關(guān)鍵是我們能夠執(zhí)行交易，并鼓勵人們在交易的最前面開始工作。我們沒有具體說明這一點(diǎn)，因?yàn)槲覀冊趪L試開發(fā)一個框架。

收斂的關(guān)鍵在于你最終得到了一個基本上位于列表頂部的綠色交易。它是收斂的交易，并且它下面的每個交易都是其祖先的一部分。而且，根據(jù)這個函數(shù)，每個人都想構(gòu)建這個新的綠色交易——如果你想要構(gòu)建一個新的交易，你將會引用這個頂部交易。就是這個思想。

不過，我們還要擔(dān)心其他問題。我們得擔(dān)心一些類似于雙花的問題。讓我們考慮一個雙花的場景。你有一個這樣的交易圖（如下），突然這兩個紅色的交易在雙花某筆錢。

好，那你怎么克服這個問題呢？比較一下這些交易。最終你必須比較這些并決定你想要繼續(xù)使用哪一個。想象一下你有一個積極的對手的情況。我們可以將系統(tǒng)中的分裂概括為：如果對手實(shí)質(zhì)上想要永久保持系統(tǒng)的分裂，會怎么樣？基本上，你可以將其一般化為兩個不能作為基礎(chǔ)的圖，因?yàn)槟悴荒芤脙蓚€沖突的交易。他們是否需要雙花并確保系統(tǒng)永不收斂？

對手現(xiàn)在的形勢是他們必須基于這兩個交易中的一個進(jìn)行構(gòu)建。他們還必須趕超網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，后者正試圖在其中一個交易上進(jìn)行構(gòu)建。因此，設(shè)想一種情況，即誠實(shí)的節(jié)點(diǎn)，或者更確切地說，激勵上兼容的節(jié)點(diǎn)首先創(chuàng)建了一個高度足夠高的交易，就好像“這是新的真實(shí)的圖”，然后對手必須在另一條鏈上創(chuàng)建一個新的交易。我們可以給它分配一些概率。然后這種情況不斷地發(fā)生，以此類推，你最終會得到這樣的概率（如下）。

你可以看到它很快變得非常小。但這只在對手沒有過半數(shù)算力的情況下才有效。這是它的論據(jù)之一。

只是為了給你們一點(diǎn)Graphchain的概述：你按照自己的節(jié)奏創(chuàng)建交易，你會因個人努力而獲得回報(bào)。受激勵影響你更傾向于在頂部創(chuàng)建交易，并且我們允許多筆交易獲得收斂性。工作量證明建立在更接近于實(shí)時(shí)的基礎(chǔ)上，所以希望你擁有這些由個人創(chuàng)建的小得多的交易，并且工作量證明是由交易的個體建立的。最后，框架對于工作量證明函數(shù)，或者甚至在某種程度上對于獎勵函數(shù)都是不可知的。

和現(xiàn)存DAG系統(tǒng)之間的差異

所以，你可能聽說過其他的DAG系統(tǒng)。IOTA可能是最著名的，有一段時(shí)間它的市值很高。主要的區(qū)別是，它實(shí)際上沒有任何激勵措施——有一種挖礦方式，但實(shí)際上沒有激勵措施。他們目前正在使用協(xié)調(diào)員。但它們在框圖和內(nèi)容方面非常相似，它們的網(wǎng)站使用的框圖跟我剛才展示的圖很類似。你可以去查一下，其實(shí)挺有意思的。

其他的一些實(shí)現(xiàn)：Byteball——它們看起來有點(diǎn)類似，但在可信見證人這一點(diǎn)上有區(qū)別。Nano采用分布式權(quán)益證明協(xié)議，通過投票消除沖突。這兩個系統(tǒng)都很酷，我建議你去研究研究。它們顯然各有利弊。我們的框架試圖變得更加不可知，更加去中心化。

結(jié)論

我不僅從事學(xué)術(shù)研究——我們有這篇論文——我也在挪威的NTNU全職開發(fā)這個框架并使之成為一種有效的加密貨幣。我大概六個月前在挪威國家電視臺上做了一次演講，之后我和這些TTO（技術(shù)轉(zhuǎn)讓辦公室）的人員進(jìn)行了交談，現(xiàn)在我正在努力將其發(fā)展成一種有效的加密貨幣——為了好玩，結(jié)果發(fā)現(xiàn)真的很難。但我們還處于項(xiàng)目的初級階段。我們最近剛剛?cè)诹艘恍┵Y金，正在招聘開發(fā)人員。

總之，我們正在努力保持甚至擴(kuò)展去中心化加密貨幣的思想，我們也希望有一個可擴(kuò)展的系統(tǒng)。這是我們擁有的最重要的東西。也許在實(shí)用中可擴(kuò)展性會受到某種程度的限制——但它很可能對很多用戶都有吸引力。感謝你們的傾聽。

問答

您能翻回到有平衡攻擊的那頁幻燈片嗎？您在哪里展示了對手的概率？我想這里沒有提到，您是假設(shè)誠實(shí)節(jié)點(diǎn)將會在某條鏈上進(jìn)行構(gòu)建，但實(shí)際上，誠實(shí)節(jié)點(diǎn)不知道哪一條是正確的。

你說得對，但事實(shí)是，對手必須同時(shí)在兩條鏈上構(gòu)建。如果對手知道誠實(shí)節(jié)點(diǎn)正在哪一條鏈上構(gòu)建，它就可以在另一條上構(gòu)建。但事實(shí)并非如此，所以對手必須同時(shí)在兩條鏈上構(gòu)建，因而也必須拆分它的算力。這就是它的工作原理。實(shí)際上我在這里漏掉了一個術(shù)語——通常情況下，誠實(shí)的參與者們有可能會同時(shí)創(chuàng)建一條鏈。我有意這樣做是因?yàn)槲乙詾闆]人會注意到。不過，最主要的一點(diǎn)是，對手必須將其算力拆分以便同時(shí)擴(kuò)展兩條鏈，因?yàn)樗膊恢览硇缘膮⑴c者將會首先擴(kuò)展哪條鏈。

但是，您仍然希望并行出塊，因?yàn)檫@就是可擴(kuò)展性的關(guān)鍵所在？然后在一條鏈上有誠實(shí)的區(qū)塊，在另一個鏈上也有誠實(shí)的區(qū)塊，它們的出塊速率大致相同。只需要一點(diǎn)點(diǎn)哈希率來平衡兩者。

我認(rèn)為它們的速率大致相同，如果它們沒有在這個術(shù)語所指的重要的點(diǎn)上往前推進(jìn)的話。它仍然會很快變得非常小。顯然，這取決于對手的算力。