Clique Oracle  

  RSS

jerry
(@jerry)
Eminent Member
Joined:4 months  ago
Posts: 26
06/07/2018 3:34 am  

1
This slide traverses in this way:

  1. Start with latest block of left validator - #4 of left validator
  2. Find the block of right validator referenced by justification of the block #4 of left validator -  that is #2 of right validator
  3. Check if candidate block is included in the parent block fork of #2 of right validator  -  Yes, it is included.

2

This slide traverses in this way:

  1. Start with latest block of right validator - #3 of right validator
  2. Find the block of left validator referenced by justification of #3 of right validator -  that is #2 of left validator
  3. Check if candidate block is included in the parent block fork of #2 of left validator  -  Yes, it is included.

4

This slide traverses in this way:

  1. Start with latest block of left validator - #4 of left validator
  2. Find the block of left validator referenced by justification of #4 of left validator -  that is #2 of right validator
    Question: Why #3 of left validator is highlighted in this slide?
  3. Check if candidate block is included in the parent block fork of #2 of right validator  -  Yes, it is included.

 

3

This slide traverses in this way:

  1. Start with latest block of right validator - #3 of right validator
  2. Find the block of left validator referenced by justification of #3 of right validator -  that is #2 of left validator
  3. Check if candidate block is included in the parent block fork of #2 of left validator  -  Yes, it is included.

 

 

Do I get it correctly? 

First, we starts with the perspective of current validator,  that is the justification of the latest block of each validator.
Then, the perspective is changed to the latest block of other validators, that is the latest blocks seen by current validator.

When there are N validators,  each validator has to make 2xN checks, right?
In other words, there are 4 checks for 2 validators. Either left validator or right validator has to complete these 4 checks, right?  


ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:5 months  ago
Posts: 9
06/07/2018 4:01 am  

For the third check, we highlight #3 and #4 of the left validator specifically because they are above #2, which is what is the latest block of the left validator from the perspective of the right validator.

There are n choose 2 pairs of validators and each pair has 4 checks. For example for 10 validators, we have 180 checks.


ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:4 months  ago
Posts: 26
07/07/2018 4:46 am  

Thanks @kent

For the third check, we highlight #3 and #4 of the left validator specifically because they are above #2, which is what is the latest block of the left validator from the perspective of the right validator.

I still don't quite get it. Is my explaination about the traversal correct? From the right validator's view, the latest block of left validator is #4. The traversal goes in the way latest block #4 => #2 of right(justification of #4 from right validator). 

I think the highlight blocks represents the traversal  flow, and from what I see, it  does not go through #3 of left validator.

 

There are n choose 2 pairs of validators and each pair has 4 checks. For example for 10 validators, we have 180 checks.

So there are C2n pairs in n validators.  When n=10, C210=45.  
When a pair passed all 4 checks above, we draw a edge between two vertexes , each of them represents a validators in this pair.

 

Clique oracle is described in doc as below.

The name of clique oracle gives a good clue as to the next step: we search for the biggest clique of validators in the graph. If this clique is greater than 50% by weight, then we can say that we have some degree of fault tolerance on this estimate. Otherwise, the majority of validators are not locked into this estimate, and we cannot say this estimate is safe.

The intuition for this oracle is fairly straight forward: as the estimator functions are determined by validator weight, if the majority of validator weight is locked into seeing a single estimate, this estimate is safe.

Note that this oracle is also a lower bound and only recognizes safety in certain situations

Particularly, I don't understand what a clique is. 

clique  

For example,  vertex A has connections(edges) with vertexes(B/C/D/E/F).
Then why area A-B-C-D-E-F-A is not the biggest clique?

Sorry I am lacking of background knowledge of graph theory.  Could you provide some clues so that I can understand it fast.


ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:5 months  ago
Posts: 9
07/07/2018 11:10 am  

From the right validator's view, the latest block of left validator is #4.

No it is #2.

I think the highlight blocks represents the traversal flow, and from what I see, it does not go through #3 of left validator.

You can break this down into two parts. We are checking that #3 leads to the candidate and then we check that #4 leads to the candidate. If there were a #5, then we would do another check. The important part is that we do this check for all the blocks above #2 because that is the latest block from the right validator's view.

When n=10, C210=45.  

Yeah so there are 4 checks for each pair so we get 4*45 = 180 checks.

Then why area A-B-C-D-E-F-A is not the biggest clique?

There is no edge between FB, FC, FD, EB, or EC and so it isn't a complete subgraph. See https://en.wikipedia.org/wiki/Complete_graph .

 

Edited: 2 weeks  ago

ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:4 months  ago
Posts: 26
08/07/2018 1:07 pm  

The important part is that we do this check for all the blocks above #2 because that is the latest block from the right validator's view.

I think the keyword is above from your explaination. Here I marked the blocks with alphabet to be more clear.

1
So what's the logic behide to select above blocks?
The first block in left validator chooses candidate block A as its fork choice?
If that is true,The orphan block E is the first above block in left validator choosing candicate.
And we still need check E/F/G?

 

 


ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:5 months  ago
Posts: 9
08/07/2018 2:20 pm  

Do you understand the first two checks? If so, think about why the first two checks is not enough to establish a clique of any two validators (aka an edge between any pair of validators) in https://github.com/rchain/rchain/tree/master/docs/casper/images (see no finalizable block mistake with no disagreement check.png).

So what's the logic behide to select above blocks?

In order to show that the right validator sees the left validator agreeing with the candidate, we start from C and then traverse down its justification to E and then show that the candidate A is in the chain of E. But imagine if between B and C, the right validator produced a block X such that A is NOT in the blockchain of X. If the right validator sends X to the left validator, it is possible that the left validator may switch its fork choice to include X and not A. Hence, we need to check that all blocks above (with a higher sequence number than) E have the candidate A in their blockchain. If those checks pass, then it eliminates the possibility that the right validator will eventually see the left validator disagreeing with the candidate A. Now you might think "wait a minute, what if the left validator never receives block X?" But if you notice, since block X is above B, when we do the check that the left validator will never eventually see that the right validator disagrees with the candidate, X will cause that check to fail.

And we still need check E/F/G?

No just F and G.


ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:4 months  ago
Posts: 26
09/07/2018 2:38 pm  

Thanks @kent, finnally I get it 😀 

One more question, how to determine block is safe in the context of Byzantine Fault Tolerance.

If all validators are honest, then because of GHOST rule, when clique weight is greater than 50%, the estimate will never be changed.
Now if involving Byzantine Fault Tolerance, suppose Byzantine Fault Tolerance = 1/3, what's the minimal weight to determine a safe estimate in this case?
I think minimal safe weight = 50% / (1-1/3)  = 3/4, right?

So the following case is unsafe(60%<75%) when Byzantine Fault Tolerance = 1/3. correct?

to

 


ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:5 months  ago
Posts: 9
11/07/2018 1:01 pm  

Now if involving Byzantine Fault Tolerance, suppose Byzantine Fault Tolerance = 1/3, what's the minimal weight to determine a safe estimate in this case?

The formula is as follows: twice the clique's weight minus the total weight must be greater than your fault tolerance minus the initial fault. Hence for a fault tolerance of 1/3 of the total weight, we need the clique's weight to be greater than 2/3 of the total weight.


ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:4 months  ago
Posts: 26
12/07/2018 11:18 am  

@kent, what's initial fault?


ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:5 months  ago
Posts: 9
12/07/2018 11:21 am  

@kent, what's initial fault?

It is the total weight of the equivocations you have seen so far. It will usually be 0.


ReplyQuote
  
Working

Please Login or Register