Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

小白学习区块链之:DAG的算法逻辑

飞儿506
147 0 0
假设有网络中有4个节点(A,B,C,D),每个节点都发送一笔交易,交易被包含在一个event里gossip到其他节点,一次gossip会把本节点的所知道的对方不知道的交易随机发送给其他节点,每个节点维护一个完整的图谱,通过投票算法,最后对每个event打一个时间戳,讲解具体逻辑前,我们先看一下event的数据结构。
( n. X% i* j  k$ k9 m2 u. K& t: I- z& d6 X- G/ b8 Q: _
    typeEventstruct{$ Q/ k! H  ]4 }+ _# ^: b. K" \
5 h  n; W6 z! i# q$ W1 d0 |% X
    Transactions[][]byte//thepayload
7 W  U, I* _: A+ w7 K' {& i
5 g! r2 c4 j" l0 t- a    selfParentstring0 p8 I: A* E8 t
+ D: M, @2 i8 l0 b* a2 F3 ^
    otherParentstring# @  }8 }9 I  i# y

. k/ O% q% d! j! h* z    Creator[]byte//creator’spublickey
7 U& Y# O3 ]6 |/ B* `6 C7 K
+ ?1 n6 c% q4 e2 l; _) r$ s. o" n    Timestamptime.Time//creator’sclaimedtimestampoftheevent’screation- M* E- \: x; Z6 g8 P
8 b7 Y5 g4 D* ~2 v
    roundReceived*int! t9 ?; [- U- b7 z; N

; b( e/ g/ V. ^    consensusTimestamptime.Time$ L0 D- R5 M1 _

1 X6 d1 w1 Q: B4 ~3 X# i/ Q    }& i! T$ }  ^0 ~$ c7 U

# A7 g8 X$ Y' i7 O& Q2 D5 R4 @3 C0 |    Transactions字段是Event里包含的所有交易,selfParent和otherParent是该Event父Event的hash,包括了自己创建的父Event和其他节点创建的父Event,Creator是创建者的公钥,Timestamp是创建Event时的时间戳,roundRecevied是Event被第几层round里的famouswitnesses所共识的,consensusTimestamp是Event被共识时的时间戳。
7 P/ a7 w+ Z/ G( R; O: K1 K
. O, S4 |1 h6 J- o2 F    接下来我们来看看具体的共识过程
. V9 \1 C9 i. H* r2 F4 |# V* e1 {( {3 T" i% t$ T
    第一步
0 U# @' L3 R& G. u. B: s7 R+ R& M
    A,B,C,D在初始化时,各自创建一个rootEvent,然后B随机选择一个节点(假设选中的是D),然后B把自己所知道的D不知道的所有Events发送给D(这里只有B在一开始创建的rootEvent),D创建一个新的Event(该Event的selfParent为D的rootEvent,otherParent是B的rootEvent),然后D再随机把自己知道的Event(包括新创建的)全部发送给B,B再创建一个新的Event,这样B就知道了4个Event(自己创建的两个和D创建的两个),D知道3个Event(不包括B最后创建的)。& a/ V9 L: Q/ l0 d3 C2 T

" D+ s1 {) }* I4 i  p& L    第二步
! s: N* K) g6 D6 d+ J5 k
$ @/ N2 C* j( X: ?    B再随机选择A,然后把自己知道的4个Event发送给A,A创建一个新的Event,这样一直增长下去,就形成了一个图谱结构。
1 u4 K$ B9 P4 y+ k) U: O( ~$ Y5 h4 l! B* j( x
    famouswitnesses的确定,首先有几个概念我们来看一下,see和stronglysees,see就是说Event之间有祖孙关系,假设有Event(B2)和Event(A3),假设B2是A3的祖先,A3是B2的子孙,那么就说A3可以看到B2。
) h! x0 h4 m5 D$ y+ b7 L3 [  Z5 x1 }9 m7 V) b
    stronglysees是两个Event之间存在祖孙关系,并且这两个Event所有相连的所有路径中所过节点和超过2/3的节点,视为其中一个Event强看见另一个Event。4 i5 o/ }& Y. {7 H: y

& L% A+ Y( Z1 U    witness是一个round中的第一个Event(rootEvent都是witness),round的确定方法是,一个Event可以强看见当前round里的2/3以上witness,那么该Event的round加一。
( Q2 S" ^7 e, _2 X% D+ _/ i! H9 L! S4 }
    第三步& F+ P9 s) M; F0 z& k6 E- a& ^
8 j8 K* f. e& X. a
    famouswitness的确定机制是,下一层round里的witness对上一层可见的witness进行投票,再下一层round里的witness来计票,具体规则是,如果一个witness(A3)对上一层里的witness(B2)可见,那么投YES,当所有投票的witness(A3,B3,C3,D3)对被投票的witness(B2)投了YES,那么被投票的witness(B2)声明为famous,再下一层的witness(B4)对参与投票的witness(A3,B3,C3,D3)如果是强可见的,那么计票为YES,那么该投票是有效的,当有效的票数超过2/3,那么被投票的witness(B2)选为famouswitness。$ @$ a7 a- z: y# Y5 G

5 y% g5 J4 e" B# l+ S    第四步
" u/ ^/ }; t9 ]) T% L* v
6 [% x, Y$ d4 z# I; o    当确定了famouswitnesses,我们就可以为events找到一个consensusTimestamp和一个roundRecevied,规则是,当一个event(X)可以被下一层round里的所有famouswitnesses看见,那么该event(X)的roundRecevied便是看见它所有famouswitnesses所在的round值,该event(X)的consensusTimestamp确定规则是,找出所有famouswitness的祖先event,并且是该event(X)的子孙的events,把这些events的时间戳排序,然后找中间的那个时间戳作为该event(X)的consensusTimestamp。
4 ]9 H0 p: G0 w0 G' A; U
9 }' N+ h6 ^, v: K7 T    被打上consensusTimestamp的event便是形成共识的event,然后根据roundRecevied对event进行排序。5 F8 i* U. A& _9 O2 f  G

% F- V  M2 s8 g2 I" d& W    ①这里不仅有区块链前沿技术干货,还可以帮你一键发链https://www.achainlabs.com/
( n8 [" s7 g% y; ], v
, T# o9 p% g6 _2 X    ②想融入区块链技术的小圈子?添加研究员微信ALabsBlockChain就好啦~
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

飞儿506 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    11