Dagx核心算法之交易单元生成过程
4 K1 Q, G" e1 P4 M  c  U
' |' Q8 ~+ H2 ?7 B+ b! A% j    交易单元生成过程& g8 F( o8 |7 m- Z; c* b
% C& E7 K# c" ^. y
    图结构包含结点和边两部分数据，结点数据主要使用数据表units存储，边主要采用数据表parenthoods存储。从数据结构角度来看，与结点数据相关的两个主要数据结构为：5 X: p+ l5 e: o) X/ x! S/ Z9 f
$ p; P2 e2 Y/ a! j( a' ~! v& ~
    1.交易单元（unit）：用来存储交易的属性数据，是核心数据结构，相关的数据表为units
6 Z6 |: ^7 O0 ?# N( A' Y' V- ?) R6 k* b0 v2 v
    2.连接点（joint）：主体由交易单元unit组成，同时包括一些结点的额外属性，比如ball、skiplist_units、unsigned等，相关的数据表包括joints、unhandled_joints、archived_joints、known_bad_joints。
9 m5 z' a( F$ @7 T; Y' p
3 _/ f; }' h: U" X5 Y    下面给出一个连接点joint数据的简单示例：" y0 A) t: D7 E: ^
% [9 Y% t8 m8 Z
    joint={
9 j% ~) {: i" ]$ @+ I- M% T1 U: U5 m9 e6 }( C7 _6 }( \3 z4 B5 n
    'unit':{
, g% }/ s6 N! v9 R& \) y8 c0 s* v& F+ C2 p- i1 u9 P
    'unit':unit_hash,
# f$ N' j" M" }/ w7 f  c+ F7 Q" c3 P1 g- c2 t; o; _
    'version':version,
: f4 z) d$ p; C6 p- D, ]' O, y- i* o. T2 f! \/ D0 q
    'alt':alt,
! c& Z7 u0 T: O2 W
% O* P- C- V0 ~6 `! ~$ w* S' J+ N* J    'messages':[
1 c& q! f( r& P- l+ ~/ I9 P7 |4 e& _3 Z, B  F
    {( `$ n# ]/ E" r8 p9 u2 u

) M) |3 a0 N" d; z    'app':'payment',
% c6 H. A0 y0 ]. B: v  M" }& i5 C1 C/ \" C0 |" O1 e
    'payload_location':'inline',) h+ R  f6 K6 l) }; w. o/ Z. m- W
1 Q0 t  k! O3 s# b
    'payload_hash':hash,
; x) ?# ^' ]/ j& @, b6 L
/ M' t" Z; d2 o; P- x* f8 z9 }    'payload':{; U/ z, W5 J) G: v; D/ g* R
7 n. B( P8 p3 L: n/ ~6 x; h
    'outputs':arrOutputs
) X0 V0 J- H) z
5 L9 c* c' u( k% r5 d0 {    }! g  A$ o0 k4 k  W1 B* |
5 z! E" ^) v! ~" s( }. e: J
    },...5 p9 m) \2 K$ y7 ]

4 ^; H/ {4 Y' Q# w- q    ],
& ^* E# ^0 Y2 q4 c2 t# O  S' m5 j8 f6 c6 p: D
    'authors':[* ^% Q) O9 h" e/ {' f9 D- @

* Y7 z+ U" [) {% h& \1 O. W    {  p! K$ ~/ m% x  J
( J  E3 O( Q. X# C
    'address':address,
( \# w9 h3 f* T3 _! R. w0 m2 m2 B' I/ n3 n) C
    'authentifiers':{- P: S2 l* |) {3 B! F9 q
3 D7 A% ^0 T6 R7 c: Q
    'path':signature( d" P/ c; U# o
0 R5 p/ _# g, n% S3 k! F: x5 Q
    }
+ U4 i8 ?9 f- }$ T
0 m- o8 W- D; _, F+ u/ B    },...- D3 R5 m" T: ~9 w- n8 h

5 z# k0 t6 Z8 Q; x; _9 G, H9 Q    ],$ Z5 Y+ O4 E" u
: h4 c' U4 t$ h( P5 g1 b9 E
    'earned_headers_commission_recipients':recipients,
; T$ z: r; c1 H
) L  I/ u9 z; q# V# k    'headers_commission':headers_commission,
: B& F# w4 h7 L$ d" F! l0 {$ ^
3 [7 m! o, v2 G. @$ }5 F    'payload_commission':payload_commission,
1 w7 Z- F- {+ \/ F" m% w
1 {. D; P8 _/ y4 g/ d    'parent_units':arrParentUnits,
8 Z  W( R- y$ L' S2 |1 h4 m) ^& O5 U) M8 C; O2 u- l
    'last_ball':last_stable_mc_ball,
5 y3 i+ q4 g1 f! C& w5 S- z( n. m& j% \3 T8 }9 `& q, Z
    'last_ball_unit':last_stable_mc_ball_unit,% V8 _% S: I  R, q4 h- z9 h
5 D! p6 h- A3 ?9 F1 S) @
    'witnesses':arrWitnesses,! @( t) y+ \+ M! @8 ~: H8 k
5 _1 a( p1 D1 v
    'witness_list_unit':witness_list_unit,//onlyallowedwitnessesorwitness_list_unit
' R8 A/ u  R" w% K
2 A5 ^6 [/ i- s    'timestamp':timestamp,, I2 V/ K3 |: j/ o( ^2 b9 r
. ]- P% A' l( u# p7 O
    'content_hash':content_hash//onlyallowedinfinishedball
+ d& ?2 w4 f  v2 z: c4 y& z( t& k' U. r$ \! h; c
    },8 D, W; F5 W& g7 E, y& T

0 k5 t6 _% M  t  [    'unsigned':?,1 G' g3 B, H& a7 R

" ]8 d# Q) `! F6 {' U# ^5 C    'ball':?,$ L) U' a/ i) u! Z
* ^4 _6 y9 \  i% ?2 l4 V  d& `, y
    'skiplist_units':?& M( Y( \7 f8 W) n% e

0 y1 e6 M2 [& b* I9 x- H    }
" f" l5 d0 x1 f9 K! r
9 |+ M8 w& t; E; |7 A8 N    交易单元的生成过程是Dagx中非常重要的部分，它的作用可以类比Bitcoin出块。在这个过程中，结点有几个关键属性需要构造：
% c% H: q) L- ^
' c5 g3 z# }! B4 z" N. A8 |    level：结点的级别，代表结点在DAG中所处的位置序号；/ r, o4 u* W' u' c/ N- M, |% |' f

4 f2 V/ `( Y) f3 v, K9 R    witnessed_level：结点的见证级别，代表沿结点当前所在主链回溯获得多数见证人支持的位置序号；
1 Z7 L/ w( @! }2 ]7 j: C
6 M! d4 P4 [; L  u3 f    best_parent_unit：结点的最优父结点；0 |& u5 [5 F8 p. H- c3 L8 o" W5 _
7 @2 s$ _5 x0 Y' S* B3 |
    witness_list_unit：结点的见证人列表；# q0 M8 ~9 d6 t1 W

, o, v8 {( H7 D# J* \: U    last_ball_unit：主链上距离最近的已稳定的结点。+ }5 L, z& u3 J6 }: `
6 T5 ^& W6 P- {: s: u9 s2 ]9 }
    选择见证人列表( x. t% ^. ~- M0 P! ^$ F

5 E7 t5 o* u1 x* ^" Y; P6 F    每个结点都具有见证人列表，这是结点看待“历史”所选取的角度，这好比在人类社会中人们是基于自身获取的信息源来得出对事情的看法。在保证见证人列表不能突变的情况下，“历史”只能缓慢地发生变化。  t# H' Q6 w5 ^( Q" W% V
, o* z  a; o& N4 d( A$ `, S
    与见证人列表相关的数据库表包括：6 I9 M9 Z$ V" Z6 J, q

. ^. b1 s: I9 Q* r( ~    my_witnesses：当前钱包所使用的见证人地址列表；
5 Q2 R" D2 h5 O! c! T
5 a8 u5 p/ e. d0 N2 r    unit_witnesses：记录交易单元unit中包含的见证人witness，每个见证人witness的地址为一条记录，可以用来做结点兼容性的检查；; }4 ~0 K4 N( i2 p: H5 M% K

) u& D, |( U9 n$ ?+ j, J! a    witness_list_hashes：记录交易单元unit对应的见证人列表hash值，相同的见证人列表对应的hash值相同，相同的见证人列表只记录第一次出现的unit。: c* ?6 R& V' d* z; ^
- H5 @( a7 i4 G5 A! U4 P
    如果见证人列表与之前结点的相同时，则采用witness_list_unit来代替就可以，若相应结点不在表中再单独记录。在构造交易单元时，应该优先使用witness_list_unit。对于一个交易单元unit而言，要么就是它本身可以在unit_witnesses中查到，要么就是它的witness_list_unit可以在unit_witnesses中查到。, M) q$ V1 D1 C$ K% L

0 R2 `, }6 }- W+ |    寻找父结点- q4 x7 `- _5 q) o3 s! ?% L
6 p* k: G! [- X( G
    如何选择新结点的父结点是新结点构造过程中极为关键的一步。对于新结点JJ，给定其见证人列表W∗W∗，在当前DAG中寻找其父结点的规则为：2 X9 w- Y: K5 `- D9 o3 d
9 U) i! z5 }2 B
    1.找到当前图中的自由结点集合Fi,i=1,2,…,nFi,i=1,2,…,n，并计算自由结点FiFi对应的见证人列表WiWi与给定的见证人列表W∗W∗中相同见证人的个数；' Y; _. A" x6 O* C8 `
$ g2 R" I1 `5 _) r; J$ v# N- E
    2.选择与给定见证人列表W∗W∗兼容的自由结点集合F′i,i=1,2,…,mFi′,i=1,2,…,m，即相同见证人的个数超过11个；
/ E' x8 z! F5 W" O9 J! R3 V- c4 l7 d+ c, w' `
    3.若自由结点集合F′iFi′不为空，则找出自由结点集合F′iFi′中的最优父结点MM；
) V8 P# @0 d* }8 u! O( y6 u0 L# o. W$ F
    4.如果新结点JJ的见证级别witnessed_level不小于最优父节点MM的见证级别witnessed_level，则自由结点集合F′iFi′作为新结点的父结点集合（最多16个）；5 e5 q4 y- h8 U; T3 D3 B9 u% z5 z4 }
- [3 J. x% l# e( v5 q% j+ C; ~7 R+ H
    5.如果新结点JJ的见证级别小于最优父结点MM的见证级别，则对最优父结点MM进行替换：选择仅具有MM作为子结点的结点进行替换，或者直接从集合F′iFi′中删除MM，生成新的自由结点集合F′i,i=1,2,…,kFi′,i=1,2,…,k，然后重复步骤3；
& L7 t2 z- {+ [2 X$ c/ t3 ]- g, r6 t. F* ^1 V2 u# V+ v6 T
    6.当找不到与给定见证人列表W∗W∗兼容的自由结点时，则选择主链上最后一个结点作为父结点（这是为了防止洪泛攻击来修改见证人列表），如果新结点JJ的见证级别witnessed_level小于父结点的见证级别witnessed_level时，则继续在主链上选择见证级别更低的结点作为父结点。
3 K9 q' E5 [7 f) p7 s1 p$ U7 u  ^  b1 N4 f
    在得到父结点集合后，还需要对见证人列表是否发生突变进行检查，要求从新结点JJ出发到last_ball_unit的主链上的所有结点对应的见证人列表witnesses差别不超过一个。如果见证人列表发生突变，则无法找到新结点的父结点，也就无法构造新结点。# o0 D+ W& I7 ^) B0 ~0 i4 ~
1 Y: K( w( F/ ~7 \  ?
    在上述规则中，选择最优父结点的方法为：  _& t' S1 N* ]1 x" N- X( \

  o" v2 M/ ~( o    1.优先级最高：父结点的见证级别witnessed_level越大越好；
0 |) d. O% D# y4 Z: U# R/ N* x
) W! b. L, U4 v% n( @    2.优先级次高：父结点的级别与见证级别之差level-witnessed_level越小越好；
; [" e7 _: M5 Y, ~  s3 j0 n
/ {/ I, Z* _& Q1 [7 S: ]. n    3.优先级最低：父结点的交易单元哈希值unit越小越好。; B! u8 r; V5 X9 W/ B* U" ?# ]

$ y& V5 l: n2 ^+ I' X" n    判断结点之间兼容的判断标准为：
* W7 `. A8 M& t1 l, H( ~/ m& L9 H* G/ ^
    1.witness_list_unit相同；
, S' Z$ s6 R6 r1 A, B1 R/ j7 @0 T
    2.见证人列表witnesses最多只有一个不同。
$ p% V3 \6 g! i! |3 m1 U+ g' ^
. p* f/ s% h5 B1 R    另外值得注意的是，如果子结点的见证人列表和父结点的相同时，子结点的见证级别witnessed_level肯定是不小于父结点的。那么，什么情况下子结点的见证级别witnessed_level什么情况下会小于父结点？答案就是：当子结点和父结点的见证人列表不同时，它们是在不同的视角下计算见证级别witnessed_level的。
& P7 v# ?$ L" p. Q1 w
7 @  L% U2 `+ b- A    计算结点的级别和见证级别3 M; h0 R% Q# }3 [2 S
$ D! R8 Z& Y% y4 e. n
    在已知结点的父结点集合的基础上，结点的级别level等于所有父结点中最大的级别max_level+1。' e! w+ b- O3 ^0 x

) p# \2 a1 L1 X! j5 h+ O1 `    给定结点的见证人列表和父结点集合时，计算结点的见证级别witnessed_level的步骤为：
. g; |$ S, A1 m2 H4 H' g0 X
; u& N2 S2 }+ I; L- `. ~    1.找到最优父结点；
$ ~* h+ T8 i/ m( d& I& V# M& O! r& [* l6 i( w
    2.开始从最优父结点沿主链开始回溯；
& f  w) B# X) Q/ S% }, l
8 I6 E' }. y4 c1 I7 h. T    3.当路径上出现多于7个不同见证人发出的结点时，回溯停止；- `' |3 j7 I, {, q
  K5 D% W' z, o( R
    4.以回溯停止处的结点的级别level作为见证级别witnessed_level。
) S  G4 p+ e3 k3 T' V; f  Y* T% D' a0 ^& ^* s9 B8 r
    寻找主链上最近的稳定结点9 }' `) X; k' l3 M4 [; D
! z# O, s1 K3 U+ C  T7 P7 A
    给定见证人列表，在主链上找到已达到稳定的结点中主链序号最大的那个结点，并记录其对应的ball、unit及main_chain_index。特别地，如果从父结点集合的角度来看该结点还没有达到稳定，则需要沿主链继续回溯，选择该结点的最优父结点作为新的稳定结点。