Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

DAG的算法逻辑

chespher
82 0 0
假设有网络中有4个节点(A,B,C,D),每个节点都发送一笔交易,交易被包含在一个event里gossip到其他节点,一次gossip会把本节点的所知道的对方不知道的交易随机发送给其他节点,每个节点维护一个完整的图谱,通过投票算法,最后对每个event打一个时间戳,讲解具体逻辑前,我们先看一下event的数据结构。, {* p5 f8 ]3 D5 U  N( f
type Event struct {
8 C2 A3 d3 Y! W) t9 u& T/ c4 O9 KTransactions [][]byte //the payload
: e/ M; _  ?7 U3 n. nselfParent string9 v, E7 t! Y, ~' q; g; x
otherParent string* p2 V8 P( k1 H5 B7 g5 k8 b
Creator []byte //creator’s public key% Q% ~3 J6 E+ K- l, V
Timestamp time.Time //creator’s claimed timestamp of the event’s creation$ m0 }- _/ U4 }4 }' k/ y; o
roundReceived *int
: V; \/ v# i) \: ^$ n6 Y9 P& Z/ WconsensusTimestamp time.Time
' p4 \6 i3 K, o. _}
4 m* c3 c5 t  L9 R# c ' A4 S  S3 ]; _2 B" I
" |/ @2 [9 @9 z, ^3 q9 `6 r! X+ m
    Transactions字段是Event里包含的所有交易,selfParent和otherParent是该Event父Event的hash,包括了自己创建的父Event和其他节点创建的父Event,Creator是创建者的公钥,Timestamp是创建Event时的时间戳,roundRecevied是Event被第几层round里的famouswitnesses所共识的,consensusTimestamp是Event被共识时的时间戳。
: X5 T- k8 ~% ]
. }& F. H. z2 Q! o" I9 U    接下来我们来看看具体的共识过程
! _6 [1 f- h/ h, k* u; J3 L! u
4 r9 `4 X) j. I    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最后创建的)。
; X2 M3 a# P7 b% R5 R( H0 G( t/ Q  N0 O4 {. @0 t
    B再随机选择A,然后把自己知道的4个Event发送给A,A创建一个新的Event,这样一直增长下去,就形成了一个图谱结构。
4 d  ?" @* H2 t) K
! d$ q* [) G5 \2 H    famouswitnesses的确定,首先有几个概念我们来看一下,see和stronglysees,see就是说Event之间有祖孙关系,假设有Event(B2)和Event(A3),假设B2是A3的祖先,A3是B2的子孙,那么就说A3可以看到B2。
; D2 N; ]8 B& i3 x$ y. H# P( p
$ B% t- i/ ^# c) Z/ g( h    stronglysees是两个Event之间存在祖孙关系,并且这两个Event所有相连的所有路径中所过节点和超过2/3的节点,视为其中一个Event强看见另一个Event。
. Q8 N( ]9 l3 y+ E* H" {
/ k: {6 r7 \% r0 T/ I+ u) \1 N; w    witness是一个round中的第一个Event(rootEvent都是witness),round的确定方法是,一个Event可以强看见当前round里的2/3以上witness,那么该Event的round加一。. i6 T. }9 f+ _+ f2 z* M

! a! b2 j, d4 t( j' \    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。% j7 T2 z3 |1 |2 a

4 l" W8 U! H. h8 t    当确定了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 ]: J# `" ~3 A3 O' e0 _

- o7 L, P, m$ }# o8 q2 L/ D    被打上consensusTimestamp的event便是形成共识的event,然后根据roundRecevied对event进行排序。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

chespher 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    2