Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

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

飞儿506
108 0 0
假设有网络中有4个节点(A,B,C,D),每个节点都发送一笔交易,交易被包含在一个event里gossip到其他节点,一次gossip会把本节点的所知道的对方不知道的交易随机发送给其他节点,每个节点维护一个完整的图谱,通过投票算法,最后对每个event打一个时间戳,讲解具体逻辑前,我们先看一下event的数据结构。, m5 H) ?4 c1 k0 j
$ m7 [) X- _  `* _+ O
    typeEventstruct{& N+ ?. R. A' a: `% {
. N7 u. K* P2 x* u
    Transactions[][]byte//thepayload
* A8 K4 `' Z% h$ J  j2 c. z9 V* c- r- `
    selfParentstring
& t1 y* @; M8 k* S$ Y, a( b& Z# O* u( C7 K
    otherParentstring
" f1 b7 ^1 T' F6 j4 }) d+ r: P6 J% [
6 D1 f$ q( [' [/ h# J! B    Creator[]byte//creator’spublickey
  f, k. r) r0 x/ B
: l; B2 C& `2 l% X# j    Timestamptime.Time//creator’sclaimedtimestampoftheevent’screation: v+ I3 c3 I5 V& ]% z/ B( e, }7 @
' ^9 n1 X: m" m9 R. R' C8 o
    roundReceived*int
, r. O. n, F8 V. X, E! Z( A0 r# i
    consensusTimestamptime.Time6 f0 H/ ^$ X! e) }4 U
$ o, h4 i# q3 e. B5 b2 A
    }
% x" o0 C, Y8 P( K% U& m
! {# i/ r' s" ^& l    Transactions字段是Event里包含的所有交易,selfParent和otherParent是该Event父Event的hash,包括了自己创建的父Event和其他节点创建的父Event,Creator是创建者的公钥,Timestamp是创建Event时的时间戳,roundRecevied是Event被第几层round里的famouswitnesses所共识的,consensusTimestamp是Event被共识时的时间戳。
  j$ ?* y0 M3 n5 v: r+ K% T0 l% [+ V( B7 M& n! a
    接下来我们来看看具体的共识过程# `0 n* B  w) I, `- T: e' T+ ]

% f. v1 F) }  @# a( X  V    第一步4 _4 B0 ~; [, q* |# A, I9 {7 ]1 p
; Q+ D( B4 N1 O& K/ c, n" C
    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最后创建的)。
( z& _) d5 D0 A* q2 {; A
; z% F( {- U+ Q/ a; d# V    第二步) t  a+ Q4 `( ~' c

1 C) v  s1 y6 K4 ^& [    B再随机选择A,然后把自己知道的4个Event发送给A,A创建一个新的Event,这样一直增长下去,就形成了一个图谱结构。6 L4 ^% T5 c$ H  d6 e
& s; h: Z6 t3 F5 L& W4 i
    famouswitnesses的确定,首先有几个概念我们来看一下,see和stronglysees,see就是说Event之间有祖孙关系,假设有Event(B2)和Event(A3),假设B2是A3的祖先,A3是B2的子孙,那么就说A3可以看到B2。3 d  F! ]# v, w) p5 V9 |! _
! H1 b" v( i: k5 E# u& e# M" s
    stronglysees是两个Event之间存在祖孙关系,并且这两个Event所有相连的所有路径中所过节点和超过2/3的节点,视为其中一个Event强看见另一个Event。
4 @9 ]* z( |8 S- g7 H  h9 Y2 G
1 n: f- }) G: [3 K$ I3 z( a    witness是一个round中的第一个Event(rootEvent都是witness),round的确定方法是,一个Event可以强看见当前round里的2/3以上witness,那么该Event的round加一。: w2 {! b6 U. }/ P3 M; ?; o

4 |1 e' S* y, g: `    第三步, j& `2 v1 _9 E! E. V0 \5 ^
1 Q7 s6 @$ l7 Q2 n) M1 \& F8 N
    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。3 K, q8 e3 z% _/ k8 V. F/ R& c
- q, Q: w5 U8 P" `, i& X' ^. h
    第四步6 f) f+ @' o5 E6 `# j$ N& r

2 V# R' ?- G2 L2 _: I    当确定了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。( C0 D+ \$ L8 y, D& v/ G
" F/ X( K4 `3 i- w% f# F1 _
    被打上consensusTimestamp的event便是形成共识的event,然后根据roundRecevied对event进行排序。' j  e! X6 W  S- ]! o0 L2 {
6 B" k) n# Z5 t: g- J# W( X4 g
    ①这里不仅有区块链前沿技术干货,还可以帮你一键发链https://www.achainlabs.com/
' \" h: p& e  f: A2 q6 R1 V  H) n9 i1 |' M! V$ k: H+ M8 c6 g3 J
    ②想融入区块链技术的小圈子?添加研究员微信ALabsBlockChain就好啦~
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

飞儿506 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    11