Multiple-parents block  

  RSS

jerry
(@jerry)
Eminent Member
Joined:6 months  ago
Posts: 29
22/06/2018 1:51 pm  

Suppose there are two validators in a namespace. And the Validator I has the following local state .

local_state

At this point, Validator I, it is aware of itself's latest block is A.  And it sees the latest block from Validator II is B. So the Validator I has the view of latest messages {A, B}.

Now Validator I is packing a new block, according to their weights. Validator I chooses block A as the parent block of the new block. So far everything is correct, right?

Next, imagine the following situation

  • Block A packs state change in tuplespace for name a. 
  • Block B packs state change in tuplespace for name b.
  • The new block packs state change in tuplespace for name c.

The state change in each block are disjoint. That is to say, they don't have any conflict on state change. Also multiple-parents is allowed by parents hash ordered list of block header. And here muliple-parents would improve the degree of parallelism and throughput.

Theoretically the new block can be set with two parents -- primary parent A and stepparent B.

However, GHOST estimator only picks the heavies fork block A as parent, right? How will RChain to make the proper estimate here? 

 

Continue with the above example. Suppose

  • Block A packs state change in tuplespace for name a. 
  • Block B packs state change in tuplespace for name a & b.
  • The new block packs state change in tuplespace for name c.

The state change of Block A & B overlapps on name a. However, the state change of name a in block A is exactly the same as block B.  Is that a conflict? Can the new block still be set to multiple parents in this case?

 

 

 

 


ReplyQuote
MichaelBirch
(@michaelbirch)
Member Moderator
Joined:7 months  ago
Posts: 39
22/06/2018 2:28 pm  

The RChain implementation uses something called "inclusive GHOST", which is a slight modification that returns not just a single tip of the DAG, but rather all tips in the order they would be reached if the higher score branches did not exist. Or phrased another way, the resulting ordered tips has the property that i > j if and only if i would be favoured over j in GHOST traversal.

In your example, our Casper implementation would indeed pick both A and B as parents of the new block. As of now, we do not try to do any form of merging when two blocks have similar information, so in your second example A and B would be considered "in conflict" and only A would be chosen as the parent. We may refine this further in the future.


ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:6 months  ago
Posts: 29
23/06/2018 4:18 am  

the resulting ordered tips has the property that i > j if and only if i would be favoured over j in GHOST traversal.

@kent explained parent and stepparent in his lecture but he does not explain how the traversal is done in this case. 

In the first example, the genesis block is the last finalized block. Then compare the score of all the blocks whose parent pointing to the last finalized block -- they are block A and block B.
Obviously block A score is higher and hence it is the primary parent of new block. Then what's next?  This is the missing part of the traversal and I am trying to find out 🙂


ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:6 months  ago
Posts: 29
23/06/2018 5:05 am  

Here take a more complicated example with three validators.

  • Validator II has the following local state and it sees the latest blocks are C / E / F
  • The lastest finalized block is the genesis one.
  • Fork C does not conflict with fork D->E or D->F
  • Fork E does not conflict with fork F

casper2

Now suppose Validator II is packing a new block.

  1. it looks up all the blocks whose parent pointing to the latest finalized block,  they are A & B.  B has a higher score hence chooses B.
  2. Then compare B's forks, they are C & D; C has a higher score hence C is choosen.
  3. Because C is the latest block so C is selected as the primary parent of the new block.

    Starting here, the following is my assumption

  4. Validator II looks back to the parent block B of the selected primary block C, and traverse on other forks.
  5. It finds the siblings(block D) of primary block C.  D does not conflict with C so continues.
  6. It compares the forks of D -  E & F.   E has a higher score than E, and E is latest messages; Hence E is selected as stepparent.
  7. Repreat the traverse and check the siblings of E. That's F.  F is also latest messages; Hence F is also stepparent.

As a result, there are three parents C > E > F and they dont conflict with each other.  So the new block G's parents are set to them. Right?

E & F are stepparents of new block G, hence their score(2+1) is added into the new block G, right?

In next round when Validator II packs another new block,  the score of the block G - (2+1+2), right?


ReplyQuote
MichaelBirch
(@michaelbirch)
Member Moderator
Joined:7 months  ago
Posts: 39
25/06/2018 2:36 pm  

The way the fork choice is implemented right now is with two passes over the data. In the first pass we start from the latest messages and follow parent block pointers to genesis (last finalized block). During this pass all (non-zero) scores are computed and child map is constructed (i.e. the inverse map to the one for parent block pointers). In the second pass we start at genesis (last finalized block) and follow the child map back to the tips of the dag. During the second pass, we run the inclusive GHOST rule. This is implemented with a list of blocks that is updated using the child map. Each block in the list is replaced with its children (with non-zero score), sorted according to their score, until the tips of the DAG are reached. The final list is a sorted list of the tips of the DAG with the property I gave in my original response.

In your example the second pass would proceed as follows:

[Genesis] -> [B] -> [C, D] -> [C, E, F]

Once this full list of possible parents is created, then the actual parents are chosen from left to right (highest priority traversal to lowest) so that the complete set of parents are non-conflicting. In this case that means all are chosen.


ReplyQuote
  
Working

Please Login or Register