BlockDAG Blue Selection Algorithm (Rust)

Posted on | Edited on | | Views:

BlockDAG blue set selection algorithm is the base of the blockDAG technology. The ‘blue set’ means a k-cluster SubDAG, let’s use S denotes it, such that |anticone(B)| ∩ S <= k, for all B ∈ S. We term this selection of a k-cluster a coloring of the DAG, and use the colors ‘blue’ and ‘red’ as a convention for blocks inside and outside the chosen cluster, respectively.

A special subtype of BlockDAG is the ‘0-cluster’ SubDAG, that is, BlockChain! Such as Bitcoin, Etherum, and so on. ‘k=0’ is the exact root cause of BlockChains have the highly restrictive throughput, for example ‘Bitcoin’ throughput is 3-7 transactions per second (tps). BlockDAG is the BlockChain’s future!

How to build a test?

For example, to run the simulation for the example Fig.3:
Fig.3

1
$ cargo test test_fig3 -- --nocapture

To run the algorithm simulation for an example of generating 1,000,000 random blocks, and execute the blue selection in a real-time calculation:

1
$ cargo test test_add_block -- --nocapture

To add your own BlockDAG example to see the blue selection behavior, it’s quite simple! For example, to test a DAG in this figure ‘Fig.4’, just add a piece of codes like this:
Fig.4

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#[test]
fn test_your_example() {

    let k: i32 = 3;

    let _ = env_logger::try_init();

    let node = Node::init("YourExampleDag");

    let mut node_w = node.write().unwrap();

    macro_rules! dag_add {
        ( block=$a:expr, references=$b:expr ) => (node_add_block($a, $b, &mut node_w, k, true));
    }
    dag_add!(block="Genesis", references=&Vec::new());

    dag_add!(block="B", references=&vec!["Genesis"]);
    dag_add!(block="C", references=&vec!["Genesis"]);
    dag_add!(block="D", references=&vec!["Genesis"]);
    dag_add!(block="E", references=&vec!["Genesis"]);

    dag_add!(block="F", references=&vec!["B","C"]);
    dag_add!(block="H", references=&vec!["E"]);
    dag_add!(block="I", references=&vec!["C","D"]);

    dag_add!(block="J", references=&vec!["F","D"]);
    dag_add!(block="K", references=&vec!["J","I","E"]);
    dag_add!(block="L", references=&vec!["F"]);
    dag_add!(block="N", references=&vec!["D","H"]);

    dag_add!(block="M", references=&vec!["L","K"]);
    dag_add!(block="O", references=&vec!["K"]);
    dag_add!(block="P", references=&vec!["K"]);
    dag_add!(block="Q", references=&vec!["N"]);

    dag_add!(block="R", references=&vec!["O","P","N"]);

    dag_add!(block="S", references=&vec!["Q"]);
    dag_add!(block="T", references=&vec!["S"]);
    dag_add!(block="U", references=&vec!["T"]);

    println!("{}", &node_w);

    dag_print(&node_w.dag);

    let blue_selection = dag_blue_print(&node_w.dag);
    println!("k={}, {}", k, &blue_selection);

    assert_eq!(2 + 2, 4);
}

then run it by cargo test test_your_example -- --nocapture

The output will be someghing like this:

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
running 1 test
node=fig4,height=7,size_of_dag=20,dag={Genesis,B,C,D,E,F,H,I,J,L,N,K,Q,M,O,P,S,R,T,U},tips={R,M,U}
dag={
 {name=Genesis,block=name=Genesis,height=0,size_of_past_set=0,size_of_past_blue=0,blue=1,prev={}}
 {name=B,block=name=B,height=1,size_of_past_set=1,size_of_past_blue=1,blue=1,prev={Genesis}}
 {name=C,block=name=C,height=1,size_of_past_set=1,size_of_past_blue=1,blue=1,prev={Genesis}}
 {name=D,block=name=D,height=1,size_of_past_set=1,size_of_past_blue=1,blue=1,prev={Genesis}}
 {name=E,block=name=E,height=1,size_of_past_set=1,size_of_past_blue=1,blue=0,prev={Genesis}}
 {name=F,block=name=F,height=2,size_of_past_set=3,size_of_past_blue=3,blue=1,prev={B,C}}
 {name=H,block=name=H,height=2,size_of_past_set=2,size_of_past_blue=1,blue=0,prev={E}}
 {name=I,block=name=I,height=2,size_of_past_set=3,size_of_past_blue=3,blue=1,prev={C,D}}
 {name=J,block=name=J,height=3,size_of_past_set=5,size_of_past_blue=5,blue=1,prev={F,D}}
 {name=L,block=name=L,height=3,size_of_past_set=4,size_of_past_blue=4,blue=0,prev={F}}
 {name=N,block=name=N,height=3,size_of_past_set=4,size_of_past_blue=2,blue=0,prev={H,D}}
 {name=K,block=name=K,height=4,size_of_past_set=8,size_of_past_blue=7,blue=1,prev={I,J,E}}
 {name=Q,block=name=Q,height=4,size_of_past_set=5,size_of_past_blue=2,blue=0,prev={N}}
 {name=M,block=name=M,height=5,size_of_past_set=10,size_of_past_blue=8,blue=1,prev={L,K}}
 {name=O,block=name=O,height=5,size_of_past_set=9,size_of_past_blue=8,blue=1,prev={K}}
 {name=P,block=name=P,height=5,size_of_past_set=9,size_of_past_blue=8,blue=1,prev={K}}
 {name=S,block=name=S,height=5,size_of_past_set=6,size_of_past_blue=2,blue=0,prev={Q}}
 {name=R,block=name=R,height=6,size_of_past_set=13,size_of_past_blue=10,blue=1,prev={O,N,P}}
 {name=T,block=name=T,height=6,size_of_past_set=7,size_of_past_blue=2,blue=0,prev={S}}
 {name=U,block=name=U,height=7,size_of_past_set=8,size_of_past_blue=2,blue=0,prev={T}}
}
k=3, blues={Genesis,B,C,D,F,I,J,K,M,O,P,R,} total=12/20
test tests::test_your_example ... ok

The source code open for this blue selection algorithm details.

The full source code is here: rust-dag.