技術科普 | DAG原理解析
DAG數學基礎
定義:在有向圖G=(V,E)中,對於任意一個頂點v∈V,都不存在一條路徑p=(e1,e2,…),ei∈E,使得從v開始出發到v終止,則G稱為有向無環圖(DAG, Directed Acyclic Graph)
在圖論中,相比於一般圖,DAG的很多問題可以在多項式級甚至線性複雜度條件下得到求解。DAG具有以下幾條數學性質:
l DAG具有拓撲順序,即DAG的所有節點可以轉換為節點序列(線性化),使得每條邊的起始節點位於終止節點之前,且該過程可以線上性複雜度條件下完成;
l DAG中相互連通的節點可以進行排序,如果從節點u出發可到達節點v,則可稱為u≤v;
l DAG具有唯一的傳遞閉包;
l DAG具有唯一的傳遞規約,傳遞規約的邊數最大不超過V−1條,V是DAG的節點數;
l DAG中給定兩個節點,其最短路徑和最長路徑可以線上性時間內求解。
DAG常用來做任務的排程規劃,比如Spark在做並行處理時使用DAG來任務規劃,Git採用DAG來做版本管理。DAG在區塊鏈上的應用可以參考 《DAG也許是真正的區塊鏈3.0》,下面將對使用DAG作為區塊鏈的Dagx原理進行詳細的解析。
Dagx的區塊鏈結構
DagX的產品原型是Byteball, 此處對dagx的闡述同樣適用byteball,Dagx區塊鏈如上圖所示,其基本組成為單元(unit),所有單元共同構成DAG。其中,單元G為創世交易,它與所有單元連通,且是從所有單元出發到達的終點。
l 父單元與子單元:從單元A出發可直接到達單元B,即單元A到單元B的路徑長度為1,則單元B稱為單元A的父單元,單元A稱為單元B的子單元。
l 直接包含:如果單元A為單位B的子單元,則單元A直接包含或者驗證了單元B。
l 間接包含:如果從單元A出發到達單元B的路徑長度大於1,則單元A間接包含或者驗證了單元B。
l 頂端單元:不具有任何子單元的單元,也可稱為無子單元或未經驗證的單元。
l 創世單元:由創世交易構成的單元,不具有任何父單元。
相比於Bitcoin中一對一的鏈式區塊結構,Dagx中單元在發出時,可以同時包含多個父單元,因此可以容納更多的交易並獲得更快的確認。由於進入DAG的單元將被所有與其連通的單元直接或間接地驗證,如果要修改該單元的內容,則需要相應地修改驗證了它的所有單元。直觀上來講,將要修改的單元數量(歸屬於不同的使用者)像滾雪球一樣急速增加,從而使得修改無法實現,這也是DAG可以作為區塊鏈的重要基礎。
單元的結構如下所示,其主要由三部分組成:
1. 單元資料:資料以message的形式構成;
2. 地址簽名:輸入所需的相應地址簽名;
3. 父單元:當前單元的父單元列表。
從中可以看出Dagx採用的交易模型是UTXO,即當前交易輸出作為後續交易的輸入。所有bytes是在創世交易中發出,因此Dagx本質上就是一種完全預挖的幣。bytes可用於支付手續費,或在地址之間相互傳輸。
{
version: '1.0',
alt: '1',
messages: [ {
app: 'payment',
payload_location: 'inline',
payload_hash: 'AegecfpDzh8xvdyIABdynrcP6CTd4Pt42gvRiv0Ftjg=',
payload: {
inputs: [{
unit: '7yctnKyuAk5P+mFgFQDdDLza88nkceXYjsTs4e3doQA=',
message_index: 0,
output_index: 1
} ],
outputs: [
{ address: 'DJ6LV5GPCLMGRW7ZB55IVGJRPDJPOQU6', amount: 208 },
{ address: 'Z36JFFX2AH7X5JQ2V2C6AQUUOWFESKZ2', amount: 3505 }
] }
} ],
authors: [ {
address: 'DJ6LV5GPCLMGRW7ZB55IVGJRPDJPOQU6',
authentifiers: {
r: '3eQPIFiPVLRwBwEzxUR5thqn+zlFfLXUrzAmgemAqOk35UvDpa4h79Fd6TbPbGfb8VMiJzqdNGHCKyAjl786mw=='
}
} ],
parent_units: [
'B63mnJ4yNNAE+6J+L6AhQ3EY7EO1Lj7QmAM9PS8X0pg=',
'D6O1/D9L8vCMhv+8f70JecF93UoLKDp3e2+b92Yh2mI=',
'ZxqzWP6q6hDNF50Wax8HUK212lH/KSIRdW5a6T9h3DM='
],
last_ball: '8S2ya9lULt5abF1Z4lIJ4x5zYY9MtEALCl+jPDLsnsw=',
last_ball_unit: 'bhdxFqVUut6V3N2D6Tyt+/YD6X0W+QnC95dMcJJWdtw=',
witness_list_unit: 'f252ZI2MN3xu8wFJ+LktVDGsay2Udzi/AUauE9ZaifY='
}
當某個單元達到穩定之後,就可以生成球(ball),此時它的狀態(是否有效)將確定性的固定下來,球的結構如下所示:
{
unit: "hash of unit",
parent_balls: [array of hashes of balls based on parent units],
is_nonserial: true, // this field included only if the unit is nonserial
skiplist_balls: [array of earlier balls used to build skiplist]
}
單元的結構中還包括見證人列表單元,這是為了節省儲存空間,表示當前單元的見證人列表與其相同。關於球、見證人我們再後續解析共識演算法時會詳細討論到。
Dagx的共識演算法
主鏈
在Dagx中,從任何一個頂端單元出發到達創世單元的最優路徑稱為候選主鏈(Candidate Mainchain)。最優路徑通過選擇最優父單元產生,選擇策略用於保證整個網路的安全性。不同的候選主鏈會在某個單元位置交叉(最差的情況是在創世單元交叉),該交叉點稱為穩定點(Stable Point)。對於所有候選主鏈,從穩定點到創世單元的路徑完全相同,該路徑稱為穩定主鏈(Stable Mainchain)。穩定主鏈是一條確定的路徑,從候選路徑變為穩定主鏈是一個從不確定逐漸變成確定的過程。後續討論中,如果沒有明確區分,主鏈一般指的是候選主鏈。
DAG中的每個單元要麼直接位於主鏈上,要麼經過較短的路徑就能到達主鏈,主鏈可以形象地看作是一條連線著許多側面道路的高速公路。一個單元一旦進入DAG中,它所在的主鏈也相應確定,因為後續單元只能作為其子單元,而無法更改其父單元。
給定一條主鏈,與之相關的所有單元均可以在此基礎上進行排序,其序號稱為主鏈序號(MCI, Main Chain Index)。創世單元的MCI為0,依次加1直到鏈尾。對於不在主鏈上的單元,其MCI等於主鏈上最先包含(直接或者間接)該單元的那個單元的MCI。MCI代表了從主鏈視角來看單元在DAG中的總序,對於發生衝突的雙花交易,MCI較小的單元為有效單元。
最優父單元的選擇策略
• 單元級別 :由當前單元出發至創世單元的最長路徑長度定義為單元級別(unit level)
• 見證級別 :從當前單元開始沿主鏈回溯,並對路徑中不同見證人進行計數(相同見證人只計數1次),當遇到的見證人數足夠多時(超過大多數的已知見證人)停止回溯;然後計算停止位置的單元級別,將其稱作當前單元的見證級別(witnessed level)。
最優父單元的選擇策略由以下三部分組成:
1. 在選擇最優父單元時,見證級別最高的父單元為最優父單元;
2. 如果見證級別相同,則單元級別最低的作為最優父單元;
3. 如果兩者都相同,則選擇單元雜湊值(base64編碼)更小的作為最優父單元。
那麼,從頂端單元出發,只需要遞迴地在其父單元中選取最優父單元即可形成主鏈。在上述選擇策略中,見證人成為了某個單元看待歷史的視角,每個單元可以維護自己的見證人列表,也可以通過witness_list_unit引用其它單元的見證人列表。
• 單元相容 :如果兩個單元的見證人列表差別最多一項,則稱這兩個單元相容
在選擇最優父單元時,僅可以從與當前單元相容的父單元中進行選擇,以保證看待歷史視角的連續性。不相容的父單元仍然被承認,但是他們不能成為最優父單元。特別地,在發出新單元時,如果與所有頂端單元都不相容,則應從上一級別的父單元中進行選擇。
雙花問題
在使用者地址發出新單元時,要求相同地址釋出的所有單元應當直接或間接包含該地址之前所有的單元,即相同地址的所有單元連通(有序或連續)。
雙花交易:相同地址發出的任何無序的交易都視為雙花交易,即使它們沒有使用相同的輸出,也可稱為衝突交易或者矛盾交易。
因此,在相同地址的所有單元都連通的情況下,在路徑上出現較早的交易為有效交易。如果有攻擊者特意製造出雙花交易,那麼可以通過主鏈序號來解決,主鏈序號較小的交易為有效交易。
上圖給出了一種攻擊場景,攻擊者製造出一條影子鏈,並在上面釋出雙花交易。當影子連結入到真實的DAG中時,根據最優父單元選擇策略,影子鏈上的見證人個數少,因此它不會成為主鏈的一部分,從而解決了這種場景下的雙花問題。值得注意的是,如果大多數見證人與攻擊者合謀,並在其影子鏈上釋出單元,則攻擊者有可能攻擊成功。
單元成為穩定點的條件
根據上面的分析可知,所有候選主鏈在穩定點之後到達創世單元的路徑完全相同,即穩定主鏈成為最終狀態。這也意味著,從穩定主鏈上單元直接或間接包含的那些單元也將無法再被篡改。因此,只要隨著新單元的不斷加入,穩定點可以不斷地向後擴充套件,且不同的使用者節點的穩定點擴充套件方式保持一致,則全網的所有使用者節點可以實現共識。
對於所有單元,如果只保留其與其最優父單元的連線,則DAG將退化為一棵樹T,所有的候選主鏈只可能從這棵樹中產生。下面根據穩定點是否具有多個子單元分兩種情況對穩定點的擴充套件方式進行討論。
當前主鏈:在DAG中,從不同頂端單元出發具有不同的候選主鏈,從見證級別最高的頂端節點出發的候選主鏈稱為當前主鏈(Current Mainchain)。
假設當前穩定點的見證人列表為W,單元級別為l,它只有一個子單元,如上圖所示。以W作為見證人列表,從當前主鏈的頂端節點進行回溯,直到遇見W中的大部分見證人,記錄這些見證人發出的單元中的最小見證級別,記作minwl。如果minwl>l,則擴充套件當前穩定點至其子單元,否則不進行擴充套件。由於大部分見證人已經在當前主鏈上了,後續這些見證人釋出的單元將繼續支援當前路徑,從而使得穩定點可以向前擴充套件。
假設當前穩定點具有多個子單元,如上圖所示。在當前穩定點的所有子單元中(除了位於當前主鏈的子單元),找出見證級別大於當前穩定點的子單元,並將其中最大的單元級別記為maxl。也就是說,除了當前主鏈外,當前穩定點其它分支上的單元見證級別將不超過maxl。如果minwl>maxl,那麼穩定點可以沿當前主鏈向前擴充套件。
隨著穩定點的不斷前進,穩定主鏈及其相關單元的狀態被最終確定下來。只要DAG中的單元相同,其形成的主鏈和穩定點也是相同的。因此,不同的使用者節點,只要最終收到相同的單元,它們最終將達到一致的狀態。
Dagx的地址、指令碼及合約
地址的定義
Dagx中使用者使用地址進行收發交易。地址本質上對應的是一段具有特定含義的指令碼,該指令碼稱為地址的定義。任何能夠使地址定義指令碼輸出為真(也稱作解鎖該指令碼)的人具有使用該地址資產的許可權。與Bitcoin類似,最常用的地址定義指令碼是公鑰(採用BASE64編碼),即具有相應私鑰的人可以使用該地址的資產,比如
["sig",{"pubkey":"Ald9tkgiUZQQ1djpZgv2ez7xf1ZvYAsTLhudhvn0931w"}]
對於地址定義指令碼進行雜湊,再加上校驗位就得到了地址,Dagx的地址採用BASE32編碼。Dagx地址的校驗位並不是全部放在尾部,而是穿插著放在雜湊值中間,防止有攻擊者在地址中間進行惡意修改。
按照此流程,上面公鑰指令碼對應的地址為:
A2WWHN7755YZVMXCBLMFWRSLKSZJN3FU
如果地址僅用於接收交易,其定義指令碼可以不對外公佈。但是當用戶首次使用該地址進行傳送交易時,他需要在傳送的單元中宣告該地址的定義指令碼,比如
unit: {
...
authors: [ {
address: 'DJ6LV5GPCLMGRW7ZB55IVGJRPDJPOQU6',
definition: [
"sig", {"pubkey":"AsnvZ3w7N1lZGJ+P+bDZU0DgOwJcGJ51bjsWpEqfqBg6"}
],
authentifiers: {
r: '3eQPIFiPVLRwBwEzxUR5thqn+zlFfLXUrzAmgemAqOk35UvDpa4h79Fd6TbPbGfb8VMiJzqdNGHCKyAjl786mw=='
}
} ],
...
}
其中,authentifiers是使用者採用私鑰對除authentifiers之外的資料進行的簽名。在使用者使用該地址首次傳送單元之後,它不允許再發送地址的定義。當然,只有在該地址的第一個單元到達穩定後,使用者才可以傳送後續單元。
使用者可以在保持地址不變的條件下修改地址的定義指令碼,使用者需要傳送訊息
unit: {
...
messages: [
...
{
app: "address_definition_change",
definition_chash: "I4Z7KFNIYTPHPJ5CA5OFC273JQFSZPOX"
},
...
],
...
}
definition_chash為新的地址定義指令碼生成的地址。那麼,下一個從原地址發出的單元有以下兩條要求:
1. 必須把address_definition_change這個單元作為其last_ball;
2. 在修改地址定義指令碼後發出第一個單元時,需要把新的定義指令碼作為第一條message。
顯然,新的地址定義指令碼生成的地址跟原地址是不相同的。當用戶遷移到新的裝置上,同時想保持地址不變時,可以使用這種方式來修改地址定義指令碼。
地址定義指令碼中必須顯式地(使用sig)或隱式地(使用address)包含至少一個sig。為了防止消耗過量的資源,指令碼的操作總數限制在100以內,包括授權地址及指令碼模板中的所有操作。
相比於Ethereum,Dagx的指令碼語言的解釋能力有限,它定義的幾乎都是邏輯判斷語句。但是,Dagx本身是為了提供給那些並不太懂程式設計的人群使用的,其語言必須便於理解且不容易出錯。
邏輯運算指令碼
與運算:當多個條件同時滿足時,指令碼輸出為真。比如,同時需要兩個私鑰簽名的指令碼
["and", [
["sig", {pubkey: "one pubkey in base64"}],
["sig", {pubkey: "another pubkey in base64"}]
]]
或運算:多個條件中有一個滿足時,指令碼輸出為真。比如,僅需要laptop、smartphone或者talet中某一個私鑰就可以解鎖的指令碼
["or", [
["sig", {pubkey: "laptop pubkey"}],
["sig", {pubkey: "smartphone pubkey"}],
["sig", {pubkey: "tablet pubkey"}]
]]
非運算:指令碼中不含sig、hash、address、cosigned by或者in merkle的條件可以進行非運算,比如
["not", [
"in data feed",
[["NOAA ADDRESS"], "wind_speed", ">", "200"]
]]
邏輯巢狀:邏輯運算可以巢狀使用。比如,必須同時擁有smartphone私鑰以及laptop或者tablet中某一個私鑰就可以解鎖的指令碼
["and", [
["or", [
["sig", {pubkey: "laptop pubkey"}],
["sig", {pubkey: "tablet pubkey"}]
]],
["sig", {pubkey: "smartphone pubkey"}]
]]
最小數量運算:當滿足條件的個數超過門限時,指令碼輸出為真。比如,具有2個以上私鑰就可以解鎖的指令碼
["r of set", {
required: 2,
set: [
["sig", {pubkey: "laptop pubkey"}],
["sig", {pubkey: "smartphone pubkey"}],
["sig", {pubkey: "tablet pubkey"}]
]
}]
最低權重運算:當滿足條件的權重值超過門限時,指令碼輸出為真。比如,當幾個私鑰簽名的權重之和大於50時可以解鎖的指令碼
["weighted and", {
required: 50,
set: [
{weight: 40, value: ["sig", {pubkey: "CEO pubkey"}] },
{weight: 20, value: ["sig", {pubkey: "COO pubkey"}] },
{weight: 20, value: ["sig", {pubkey: "CFO pubkey"}] },
{weight: 20, value: ["sig", {pubkey: "CTO pubkey"}] }
]
}]
地址授權指令碼
授權使用其它地址來解鎖指令碼,其定義的語法為
["and", [
["address", "ADDRESS 1 IN BASE32"],
["address", "ADDRESS 2 IN BASE32"]
]]
這可以很方便地用來構造共享控制的地址。比如,上面給出的地址定義指令碼生成的地址將由ADDRESS1和ADDRESS2共同控制。
共同簽名指令碼
要求與另一個地址共同簽名才可以解鎖指令碼
["cosigned by", "ANOTHER ADDRESS IN BASE32"]
地址已用指令碼
要求由某個地址發出的單元至少有一個成為last_ball_unit
["seen address", "ANOTHER ADDRESS IN BASE32"]
資料訂閱指令碼
通過訂閱的資料是否符合條件來解鎖指令碼,其語法格式為
["in data feed", [
["ADDRESS1", "ADDRESS2", ...],
"data feed name",
"=",
"expected value"
]]
上述指令碼表示:當資料來源地址ADDRESS1、ADDRESS2等中某個地址發出的訊息中訂閱資料data feed name等於expected value時,指令碼輸出為真。
地址發出的資料訂閱訊息格式為
unit: {
...
messages: [
...
{
app: "data_feed",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
"data feed name": "value",
"another data feed name": "value2",
...
}
},
...
],
...
}
對賭合約
當某個地址可以作為可靠的資料訂閱源時,使用者可以使用其作為外部資料條件來構造合約。比如,
["or", [
["and", [
["address", "ADDRESS 1"],
["in data feed", [["EXCHANGE ADDRESS"], "EURUSD", ">", "1.1500"]]
]],
["and", [
["address", "ADDRESS 2"],
["in data feed", [["TIMESTAMPER ADDRESS"], "datetime", ">", "2016-10-01 00:00:00"]]
]]
]]
上述指令碼給出了ADDRESS 1和ADDRESS 2之間的一個簡單合約,假設其對應的地址為ADDRESS X。當EXCHANGE ADDRESS釋出的匯率資料EURUSD大於1.1500時,僅使用ADDRESS 1的私鑰就可以取走ADDRESS X中的資產。而當TIMESTAMPER ADDRESS釋出的時間資料datetime大於2016-10-01 00:00:00時,僅使用ADDRESS 2的私鑰就可以取走ADDRESS X中的資產。也就是說,上述指令碼定義的是對賭合約:如果2016-10-01 00:00:00之前EURUSD匯率超過1.1500,地址ADDRESS 1獲勝,否則地址ADDRESS 2獲勝。
商品合約
當顧客購買商品時,也可以使用上述方式來制定合約,比如
["or", [
["and", [
["address", "MERCHANT ADDRESS"],
["in data feed", [["FEDEX ADDRESS"], "tracking", "=", "123456"]]
]],
["and", [
["address", "BUYER ADDRESS"],
["in data feed", [["TIMESTAMPER ADDRESS"], "datetime", ">", "2016-10-01 00:00:00"]]
]]
]]
上述指令碼給出了顧客BUYER ADDRESS和商戶MERCHANT ADDRESS之間的合約,假設其對應的地址為ADDRESS Y。顧客在購買商品時,將款項打入地址ADDRESS Y。如果快遞公司FEDEX ADDRESS釋出資料表明相應的快遞已簽收,則商戶MERCHANT ADDRESS可以從ADDRESS Y中取走貨款;如果TIMERSTAMPER ADDRESS釋出的時間資料datetime大於2016-10-01 00:00:00時,則顧客BUYER ADDRESS可以從ADDRESS Y中取回貨款。
上述場景中,快遞公司需要對每一個快遞都發布其簽收狀態資料,這將需要釋出大量的資料。Merkle資料訂閱可以降低需要釋出的資料量。只需要核實關心的hash值出現在資料來源地址釋出的Merkle樹中時,即可證明該事件已發生。其定義語法如下:
["in merkle", [
["ADDRESS1", "ADDRESS2", ...],
"data feed name",
"hash of expected value"
]]
此時,快遞公司只需要定期將一大批快遞狀態構造Merkle樹,併發布Merkle根即可。商戶可以通過相應快遞的Merkle路徑來解鎖Merkle資料訂閱的指令碼。
單元約束指令碼
指令碼可以對相應地址發出的單元資料進行約束,其定義格式為:
['has', {
what: 'input'|'output',
asset: 'assetID in base64 or "base" for bytes',
type: 'transfer'|'issue',
own_funds: true,
amount_at_least: 123,
amount_at_most: 123,
amount: 123,
address: 'INPUT OR OUTPUT ADDRESS IN BASE32'
}]
上述指令碼要求單元至少有一個輸入/輸出滿足後續定義所有的條件。特別地,可以使用has one來強制要求有且僅有一個輸入/輸出滿足後續所有條件。
其它類似的約束還有求和約束,要求輸入/輸出之和滿足特定條件,其格式為
['sum', {
filter: {
what: 'input'|'output',
asset: 'asset or base',
type: 'transfer'|'issue',
own_funds: true,
address: 'ADDRESS IN BASE32'
},
at_least: 120,
at_most: 130,
equals: 123
}]
交易合約
單元約束指令碼可以用來實現去中心化交易。假設使用者USER ADDRESS希望使用不高於1000bytes的價格購買1200units的其它資產。使用者可以傳送1000bytes至如下指令碼定義的地址上:
["or", [
["address", "USER ADDRESS"],
["and", [
["address", "EXCHANGE ADDRESS"],
["has", {
what: "output",
asset: "ID of alternative asset",
amount_at_least: 1200,
address: "USER ADDRESS"
}]
]]
]]
或邏輯or的第一個條件表明,在未成交之前,使用者可以隨時取回他的1000bytes。或邏輯or的第二個條件表明,其他使用者可以使用EXCHANGE ADDRESS地址私鑰來取走著1000bytes,只要他同時在同一單元中將1200units其它資產輸出到USER ADDRESS。通過這種方式,使用者之間可以實現不同資產之間的交易。
借貸合約
單元約束指令碼還可以用來實現抵押借貸。假設借款人抵押某種資產借貸10000bytes,那麼借款人和借貸人可以共同簽名一筆交易,其中借貸人將bytes傳送給借款人,同時借款人將抵押資產轉入以下指令碼定義的地址上:
["or", [
["and", [
["address", "LENDER ADDRESS"],
["in data feed", [["TIMESTAMPER ADDRESS"], "datetime", ">", "2017-06-01 00:00:00"]]
]],
["and", [
["address", "BORROWER ADDRESS"],
["has", {
what: "output",
asset: "base",
amount: 10000,
address: "LENDER ADDRESS"
}]
]],
["and", [
["address", "LENDER ADDRESS"],
["address", "BORROWER ADDRESS"]
]]
]]
上述指令碼包括了三層含義:
1. 當時間超過2017-06-01 00:00:00時,借貸人可以取走抵押資產;
2. 當借款人歸還10000bytes至借貸人地址LENDER ADDRESS時,借款人可以取回抵押資產;
3. 借貸人和借款人可以協商解除合約。
指令碼模板
通過預先設定的指令碼模板可以很方便地定義指令碼,只需要對模板中的引數進行修改即可
["definition template", [
"hash of unit where the template was defined",
{param1: "value1", param2: "value2"}
]]
指令碼模板需要在單元中傳送app=’definition_template’的訊息,並且需要單元到達穩定狀態後,指令碼模板才可以使用。訊息內容與普通的地址定義指令碼相同,引數使用@param1及@param2表示。
Dagx的網路結構
從節點功能角度來講,Dagx網路節點可以分為中繼節點(Relay)、中樞節點(Hub)、播報節點(Oracle)、見證人節點(Witness)、錢包節點(Wallet):
- 中繼節點(Relay):負責向與其連線的節點轉發單元,儲存整個Dagx區塊鏈資料庫,但它本身不儲存任何私鑰,也不傳送任何單元;
- Hub節點(Hub):負責為連線到它的裝置提供端到端的加密訊息傳輸通道,用於比如收發私密資產、多簽名交易、聊天資訊等,其它功能與中繼節點相同,預設的Hub地址為wss://Dagx.org/bb;
- 播報節點(Oracle):負責不間斷地向Dagx網路播報資料,資料可以是時間、價格、甚至是Bitcoin交易;
- 見證人節點(Witness):負責不間斷地以固定地址傳送單元,任何滿足該條件的節點都有可能成為見證人;
- 錢包節點(Wallet):負責與使用者互動,收發交易、訊息等。
下圖給出了Dagx網路結構的示意圖:
輕節點及其驗證過程
從是否儲存了完整的區塊鏈資料角度來講,節點也可以分為全節點和輕節點,全節點儲存了完整的區塊鏈資料,而輕節點沒有。使用者在安裝錢包時可以選擇是使用全節點還是輕節點。輕節點僅儲存與其地址相關的那些單元,它需要從全節點上下載所需要的資料,請求條件包括它信任的見證人列表以及它關注的地址。
跳躍列表:假設直接位於主鏈上的球的MCI為i,如果imod10=0,則該球具有跳躍列表(skiplist_balls),跳躍列表中的值指向之前的球;對於i尾數具有的每一個0,跳躍列表中都有一個MCI值與之對應;跳躍列表中的MCI值等於在保持尾數0個數相同的情況下最接近i的MCI,比如i=3000時,對應的跳躍列表為[2990,2900,2000]。
跳躍距離:對於跳躍列表中的MCI值,它與當前球的MCI值的差值稱為跳躍距離。
最近的球:當前節點已知的距離當前時刻最近的球(last_ball),每個單元在傳送時必須包含其已知的最近的球。
全節點接收到輕節點發送的見證人列表和關注地址,在其儲存單元的資料庫中搜索與輕節點關注地址相關的單元。同時,對於每一個相關的單元,全節點構造一條證據鏈,構造方法如下:
1. 沿著主鏈回溯,當已收集到輕節點給定見證人列表中的絕大部分見證人時停止(這是尋找見證人的過程),記錄這些主鏈上的單元,記作單元集合C;
2. 選擇單元集合C中時間最早的單元(也是MCI最小的單元),獲取其last_ball;
3. 從last_ball這個單元開始沿著主鏈回溯,直至遇見包含skiplist_balls的球停止,記錄這些主鏈上的球,記作球集合B;
4. 使用skiplist_balls繼續沿主鏈回溯,跳轉到skiplist_balls中跳躍距離最大的球(這是不斷加速跳躍的過程);
5. 重複步驟4,當下一次跳躍超過目標單元時,減小跳躍距離(這是降速跳躍的過程,極限情況下,不使用skiplist_balls回溯,只利用父單元進行回溯),直到目標單元停止。
對於輕節點而言,全節點給出的證據鏈是可信的,主要有以下兩個原因:
1. 證據鏈開始的那些單元包含了輕節點信任的見證人發出的單元;
2. 證據鏈中的連線使用的是parent_units(尋找見證人過程)、last_ball、skiplist_balls、parent_balls。
因此,通過證據鏈的方式,輕節點可以判斷某個單元是否有效。
端到端加密通道
中樞節點Hub用於為不同的使用者裝置之間提供可靠的端到端加密資料通道,有點類似郵件伺服器。Hub為使用者裝置提供儲存轉發服務,使用者裝置可以選擇連線到不同的Hub。使用者裝置使用websocket連線到到Hub,並採用TLS加密。Hub一旦收到發往某個裝置地址的訊息,它就會立即轉發,轉發成功後刪除訊息。
裝置地址是用於標識使用者裝置的,從而接收其它裝置傳送的訊息,類似於郵件地址。裝置地址與錢包地址不同,可以在不同的裝置上使用相同的錢包地址。每個裝置儲存一把永久性的私鑰,其對應的公鑰做Hash後進行BASE32編碼得到裝置地址。為了和錢包地址區分開來,裝置地址在其開始位置新增0作為標識(0本身並不是BASE32字元)。完整的裝置地址還要包括Hub名稱,比如[email protected]。當切換到不同的Hub是,@之間的地址是保持不變的。
假設傳送訊息的裝置記作sender,接收訊息的裝置記作receiver,receiver所連線的Hub為hub。那麼,當sender想要與receiver進行通訊時,它需要進行以下操作:
1. sender修改其Hub地址為hub,預設情況下所有裝置連線的都是wss://Dagx.org/bb;
2. sender與receiver進行配對,可以使用掃描二維碼、配對字串、或者使用Dagx://起始的連結。
所有裝置之間的通訊均採用了端到端加密(ECDH+AES)和數字簽名(ECDSA)。作為通訊的唯一中間人,Hub也無法檢視或者修改訊息內容,為了提高轉發的安全性,裝置會生成一個臨時私鑰,並將對應的公鑰上傳至它連線的Hub上。同時,裝置可以定時地更換臨時私鑰和公鑰。
因此,sender在向receiver傳送訊息時,它需要完成以下步驟:
1. 與hub連線;
2. 從hub獲取receiver的臨時公鑰;
3. 生成一次性的金鑰對;
4. 根據一次性私鑰和receiver的臨時公鑰生成ECDH金鑰;
5. 使用ECDH金鑰對訊息進行AES加密;
6. 新增一次性公鑰;
7. 使用裝置私鑰對整個訊息進行簽名;
8. 將訊息傳送給hub
對於receiver,它首先需要驗證訊息的簽名,然後使用sender的一次性公鑰和本地的臨時私鑰解密訊息,從而獲得訊息的內容。
基於Hub的裝置端到端加密訊息通道可以用於裝置之間通訊,裝置之間相互發送的訊息不存入Dagx資料庫中。使用者可以利用該通道來發送加密文字訊息、多簽名交易、隱私資產(比如blackbytes)等。
Dagx的應用
數字資產
Dagx本質上是基於DAG的分散式資料庫,資料狀態一旦確定則不可逆轉。在各種型別的資料中,具有社會普遍意義的資料是比較有價值的,比如個人資產資料。在Dagx中,資產可以釋出、轉移以及交換,類似於Dagx的基本貨幣bytes。資產可以代表任何有價值的東西,比如債務、股票、會員積分、通話時間、商品、其它加密貨幣等。
定義新資產的訊息格式為:
unit: {
...
messages: [
...
{
app: "asset",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
cap: 1000000,
is_private: false,
is_transferrable: true,
auto_destroy: false,
fixed_denominations: false,
issued_by_definer_only: true,
cosigned_by_definer: false,
spender_name_attested: true,
attestors: [
"2QLYLKHMUG237QG36Z6AWLVH4KQ4MEY6",
"X5ZHWBYBF4TUYS35HU3ROVDQJC772ZMG"
]
}
},
...
],
...
}
在定義新資產時,可以設定以下屬性:
cap:資產總量,比如bytes的總量為1015
is_private:資產轉移是否公開,比如bytes為公開
is_transferrable:資產是否可以在無發行方允許的條件下進行流通,如果不可流通,則資產的收發方中必須有發行方,比如bytes為可流通
auto_destroy:資產在傳送回發行方時是否自動銷燬,比如bytes為不自動銷燬
fixed_denominations:資產是否以固定面額進行流通(類似紙幣),比如bytes可以以任意金額流通
- issued_by_definer_only:資產是否僅由發行方釋出,比如bytes均在創世單元中釋出
- cosigned_by_definer:資產在每次轉移時是否必須由發行方共同簽名,比如bytes是不需要的
- spender_attested:資產在使用時使用者是否需要通過認證,比如bytes是不需要的
- attestors:受資產發行方認可的認證地址,可以在後續過程中修改
- denominations:如果資產具有固定面額,定義面額種類以及各類別總量
- transfer_condition:資產轉移需要的額外條件,語法與地址定義指令碼相同(除了不使用sig之外)
- issue_condition:資產釋出需要的額外條件
在定義資產時,每個單元中最多隻能有一條asset訊息。當資產定義單元釋出後,後續都通過引用該單元的hash來引用該資產。資產只能定義一次,除了attestors之外均不能進行修改。資產定義的解釋權在發行方,其具體含義由其進行解釋。資產定義中的不同屬性的組合可以適用不同的場景。
釋出資產的訊息格式為:
unit: {
...
messages: [
...
{
app: "payment",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
asset: "hash of unit where the asset was defined",
inputs: [
{
type: "issue",
amount: 1000000,
serial_number: 1,
address: "ISSUER ADDRESS" // only when multi-authored
},
...
],
outputs: [
{
address: "BENEFICIARY ADDRESS",
amount: 12345
},
...
]
}
},
...
],
...
}
總量有限的資產必須在一個交易中全部發布,比如,所有的bytes都是在創世單元中釋出的。如果資產總量有限,釋出時serial_number必須為1;如果資產總量不受限,每次釋出時serial_number必須保證不同。
轉移資產與bytes類似,只是需要加上資產的ID,其訊息格式為:
unit: {
...
messages: [
...
{
app: "payment",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
asset: "hash of unit where the asset was defined",
inputs: [
{
unit: "hash of source unit",
message_index: 0,
output_index: 1
},
...
],
outputs: [
{
address: "BENEFICIARY ADDRESS",
amount: 12345
},
...
]
}
},
...
],
...
}
隱私資產
公開資產在轉移過程中,其內容在交易中是完全公開的。而對於隱私財產,在轉移時,僅傳送特定時間點資產轉移的證據;同時,傳送者通過私有通道把資產傳送給接收者;接收者可以通過區塊鏈上的資產轉移證據來驗證是否得到該筆資產。
為了解決雙花問題,需要在單元增加新的欄位spend_proof,要求:
- 它僅依賴於其所花費的輸出,相同的輸出將產生相同的spend_proof
- 無法通過它逆向推斷出所花費輸出的任何資訊
例如採用如下方式生成spend_proof:
spend_proof = hash({
asset: payload.asset,
unit: input.unit,
message_index: input.message_index,
output_index: input.output_index,
address: src_output.address,
amount: src_output.amount,
blinding: src_output.blinding
})
其中,payload.asset表示需要轉移的資產,input則表示花費輸出src_output的輸入。隱私資產的輸出必須包含擾亂因子blinding,它使得無法通過spend_proof來逆向推到出其使用了哪個輸出。
對於隱私資產的發行來講,其spend_proof為:
spend_proof = hash({
asset: payload.asset,
address: "ISSUER ADDRESS",
serial_number: input.serial_number, // always 1 for capped assets
amount: input.amount, // issue amount
denomination: 1 // always 1 for arbitrary-amounts payments
})
在發行隱私資產時,由於需要公開表明已發行該資產,因此不需要新增擾亂因子。在資產傳遞過程中,傳送者已知擾亂因子,雖然他可以知道接收者是否花費了這筆資產,但是他無法知道這筆資產的下一個接收者是誰,也就無法繼續跟蹤該筆資產的進一步流向了。
spend_proof需要新增到區塊鏈單元中,其格式為:
unit: {
...
spend_proofs: [
{
spend_proof: "the above hash in base64",
address: "SPENDING ADDRESS" // only if multi-authored
},
...
],
...
}
在傳送隱私資產時,傳送者需要完成以下幾件事情:
• 對每個輸出新增擾亂因子
• 將隱私資產通過私有通道傳送給接收者,以及該資產傳遞所在的區塊鏈單元
• 對於單元中每個輸入,計算相應的spend_proof並加入單元中
接收者需要檢查兩件事情:
• 檢查收到的隱私資產的hash值是否與區塊鏈單元中的payload_hash相同
• 檢查通過收到的隱私資產計算得到的spend_proof是否與區塊鏈單元中的匹配
接收者可以驗證整個資產轉移的過程,並能夠回溯到該資產的釋出單元。
Dagx中提供了一種隱私數字資產blackbytes,其定義如下所示:
{
cap: 2,111,100,000,000,000,
is_private: true,
is_transferrable: true,
auto_destroy: false,
fixed_denominations: true,
issued_by_definer_only: true,
cosigned_by_definer: false,
spender_name_attested: false,
denominations: [
{denomination: 1, count_coins: 10,000,000,000},
{denomination: 2, count_coins: 20,000,000,000},
{denomination: 5, count_coins: 10,000,000,000},
{denomination: 10, count_coins: 10,000,000,000},
{denomination: 20, count_coins: 20,000,000,000},
{denomination: 50, count_coins: 10,000,000,000},
{denomination: 100, count_coins: 10,000,000,000},
{denomination: 200, count_coins: 20,000,000,000},
{denomination: 500, count_coins: 10,000,000,000},
{denomination: 1000, count_coins: 10,000,000,000},
{denomination: 2000, count_coins: 20,000,000,000},
{denomination: 5000, count_coins: 10,000,000,000},
{denomination: 10000, count_coins: 10,000,000,000},
{denomination: 20000, count_coins: 20,000,000,000},
{denomination: 50000, count_coins: 10,000,000,000},
{denomination: 100000, count_coins: 10,000,000,000}
]
}
資料
非結構化資料(文字)
使用者可以在Dagx中儲存文字資訊,訊息格式為:
unit: {
...
messages: [
...
{
app: "text",
payload_location: "inline",
payload_hash: "hash of payload",
payload: "any text"
},
...
],
...
}
文字可以是任意內容:使用者可以利用這個釋出不能被篡改的公告、微博等等;也可以儲存一些非明文的內容,比如合約的hash值之類的。
結構化資料
使用者也可以使用Dagx儲存任意的結構化資料,訊息格式為:
unit: {
...
messages: [
...
{
app: "data",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
key: "value",
another_key: {
subkey: "other value",
another_subkey: 232
}
}
},
...
],
...
}
投票
使用者可以使用Dagx發起投票,訊息格式為:
unit: {
...
messages: [
...
{
app: "poll",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
question: "Should the United Kingdom remain a member of the European Union or leave the European Union?",
choices: ["Leave", "Remain"]
}
},
...
],
...
}
同時,使用者可以響應投票,其訊息格式為:
unit: {
...
messages: [
...
{
app: "vote",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
unit: "hash of the unit where the poll was defined",
choice: "Leave"
}
},
...
],
...
}
投票的有效性需要由發起投票方來決定,Dagx僅僅檢查投票選項是否在給定集合內。比如,如果發起投票方要求只允許經過認證的或在白名單上的使用者進行投票,那些無效的投票也會被Dagx記錄,需要由發起方自行判別。
認證
使用者可以通過Dagx釋出和儲存個人資訊,訊息格式為
unit: {
...
messages: [
...
{
app: "profile",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
name: "Joe Average",
emails: ["[email protected]", "[email protected]"],
twitter: "joe"
}
},
...
],
...
}
使用者可以釋出任意的個人資訊,但是其真實性是無法保證的,只有通過認證的資訊才是可信的。
認證訊息用於確定使用者釋出的個人資訊的真實性,其訊息格式為
unit: {
...
messages: [
...
{
app: "attestation",
payload_location: "inline",
payload_hash: "hash of payload",
payload: {
address: "ADDRESS OF THE SUBJECT"
profile: {
name: "Joe Average",
emails: ["[email protected]"]
}
}
},
...
],
...
}
認證訊息中的個人資訊不一定與使用者自己釋出的資訊一致,事實上,使用者甚至沒有自己釋出過個人資訊。
Dagx中的認證者類似於現實世界中的實名認證,認證某個地址是歸屬於某個個人或組織。認證方可以向被認證方收取少量費用。一般來講,見證人節點是需要通過認證的,這樣可以提高手信任度。被認證方可以選擇不公佈認證資訊,而只在Dagx中儲存認證證據,並在合適的時機公佈。
總結
Dagx是一種基於DAG結構的不可逆分散式資料庫,它可以儲存任何有價值的資料。Dagx中每一個新的資料單元都間接地確認了之前所有資料單元的存在性。對已達到穩定狀態的資料單元的修改將變得不可實現。
相比於BTC和ETH,Dagx使用了DAG結構作為底層,並使用見證人作為共識機制,從而具有以下特點:
- 沒有區塊,只有交易單元,確認速度快
- 極少的手續費
- 交易單元具有最終狀態
Dagx中發行了一種用於支付儲存的貨幣bytes,支付費用與所需要儲存的資料大小相關。自由開發者可以在Dagx平臺上自由開發各種應用,根據不同的應用場景釋出相應的數字資產。在Dagx上面可以輕鬆地實現去中心化交易所、互助保險、賭球、彩票、投票、認證等等功能。Dagx還提供了類似telegram的加密端到端通道,可以實現使用者之間的隱私通訊。Dagx最與眾不同的是,它提供了一種隱私數字資產blackbytes,可以完整地保護使用者的隱私資訊。
總的來說,不管從使用技術的先進性,還是其提供功能的多樣性,DAG都是區塊鏈領域中的佼佼者。
(作者:DAGX,內容來自鏈得得內容開放平臺“得得號”;本文僅代表作者觀點,不代表鏈得得官方立場)