Does the forks resolved only with partial ordering?

#1

Hello all,i think i have something that i am struggling to understand.I read your paper and you said in order to resolve the forks that occurs when multiple DS nodes solve the puzzle together, your algorithm sorts them in a increasing order. I am not get convinced that all the nodes agree on the same order due to network latency.This will lead for some messages to be lost or delayed.Thus, some nodes may follow wrong leader.What about that??How you preserve the consistency on this matter?Are there any synchronization mechanism? you are not so clear in the paper.

i would be grateful at a reply at your earliest convenience

#2

Hi,

Are you referring to the PoW puzzle or something else? If you are asking about the PoW puzzle: In the current implementation, as long as the PoW submissions fulfill the DS_POW_DIFFICULTY level, they will be selected to join the network as DS nodes. Then, they will be sorted by difficulty of the puzzles solved first and then by the timestamps of puzzle submissions. At last, only the top 10 of these qualifying nodes will be enrolled in the DS committee. This whole process takes about 5 minutes.

#3

i will give you an Example to be more clear. We have some DS nodes and we want to find the leader based on POW_1.Each DS node retrieves the nonce field from the received header and sort them in increasing order.Lets assume that we have three DS nodes A,B,C.Lets imagine that both A,B finds a solution simultaneously and the both send message to all DS nodes include C with timestamp 2,8 respectively.so all DS nodes check timestamps in a partial order, C founds that A has lower timestamp so C listen to A.In the meanwhile, B despite that he found a valid solution he saw that his timestamp is greater so he admits that A was found a correct solution earlier and he listens to him.Am i correct until now??My question now is what happened if C don’t get the message by A so C will consider B as the next lowest Timestamp and he will listen B as leader which is incorrect because A timestamp is lower than B(2<8).That leads to a fork i quess. How handle this case?

#4

In order to agree on the set of the DS nodes (10 in each DS epoch) to enter the network, all DS nodes (600 of them) have to create a DS block that contains the info of these new nodes identities and solutions. In pBFT, the leader will propose this block and all other nodes will commit and challenge the leader. If 2/3 of the current DS nodes comes to an agreement on the new set of DS nodes to enter, they will create this new DS block and the network proceeds.

If there is less than 2/3 agreement due to bandwidth issues (not receiving the messages in time), this consensus process will timeout and we go into view change mode to change the leader and refreshes the view. We then go into PoW process once again, and attempt to form the DS block.

In pBFT, there is no forks. You can only stall the network till it continues to propagate.

#5

Hi, thanks for the explanation, could you explain more on “in pBFT there are no forks”?

#6

pBFT has finality, hence every block created is the truth. You cannot have forks in the network as in protocols using Nakamoto consensus.

The only downside of pBFT is liveness is not guaranteed, as you can have a stall in consensus due to not even commits from nodes in a network, and the chain will not propagate further. For example, in Zilliqa, if a shard has less than 401/600 commits, there will not be a TX block formed. To mitigate this, you need something called a “View change”, after the consensus phase has timed out. A “View change” changes the leader who is proposing the block and refreshes the view of all nodes in order for everyone redo consensus from scratch and move on.

For more information: https://www.comp.nus.edu.sg/~rahul/allfiles/cs6234-16-pbft.pdf

1 Like