block in GHOST  

  RSS

jerry
(@jerry)
Eminent Member
Joined:7 months  ago
Posts: 31
19/06/2018 3:45 am  

1

Regarding the above slide.

1. These two columns represent how a DAG chain is constructed in an individual namespace by two validators,right?

2. How does weight come from?
     Casper paper defines weight as a map from validator names to positive real numbers. W : V -> R+
      The weight 2 and 3 of the left and right validators, which factors would impact them? how exactly do they impact?

3. Casper paper defines GHOST messages as below.

2

The dotted arrows in the slide represent blocks' justifications; and solid arrows  represent blocks' parents.
There are some blocks do not have dotted arrows, does that means its justification is the same as its parent? 
Or justifications can be empty set?

4. What's the logic behind for a validator to peak certain previous block as some block's justifications?
      

 

5. I watched the video several times still dont quite understand how score is computed. 🤣 
3
4
The block score is calculated from the latest(top) to the genesis block, right?
The latest(top) is assigned with the validator's weight, right?
Then for each previous block, its score is added by the other blocks who linked it as parent, right?

Then what's the role of justifications here? From the formula, it looks like justifications are a condition to compute the estimate. But I couldnt understand it and It seems redundant.


ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:8 months  ago
Posts: 9
19/06/2018 4:23 am  

1. These two columns represent how a DAG chain is constructed in an individual namespace by two validators, right?

Yes

2. How does weight come from?
     Casper paper defines weight as a map from validator names to positive real numbers. W : V -> R+
      The weight 2 and 3 of the left and right validators, which factors would impact them? how exactly do they impact?

The left and right validators have weight 2 and 3 respectively. In Rchain, they will correspond to how much stake the validators have bonded. But in general, it isn't important what they are - you can just assign arbitrary values for the weights or just say they all have the same weight.

3. The dotted arrows in the slide represent blocks' justifications; and solid arrows represent blocks' parents.
There are some blocks do not have dotted arrows, does that means its justification is the same as its parent?
Or justifications can be empty set?

There is exactly one justification per validator. In other words, in this diagram, each block must have two dotted arrows and one solid arrow (if they overlap you'll only see the solid arrow). If any block is missing a dotted arrow to a block in a either validator's column, then it is implied that it has the same dotted arrow (justification pointer) as the parent block. The justification can only be the empty set for the genesis block.

4. What's the logic behind for a validator to peak certain previous block as some block's justifications?

The validator picks the latest ones they see.

5. I watched the video several times still dont quite understand how score is computed.

The block score is calculated from the latest(top) to the genesis block, right?
The latest(top) is assigned with the validator's weight, right?
Then for each previous block, its score is added by the other blocks who linked it as parent, right?

Let us be consistent with the terminology. What you are calling "The latest(top)" is the latest messages. There are exactly the same number of latest messages as there are validators. In other words, for this example there are 2 latest messages. In a diagram like this they are easy to identify because they are the blocks at the top of each column.

Then for each parent block, the validator's weight is added to that block's score.

As an exercise try listing the scores for this diagram - once you get the hang of it, the score is really easy to compute for each block:

Then what's the role of justifications here? From the formula, it looks like justifications are a condition to compute the estimate. But I couldnt understand it and It seems redundant.

Yeah justifications are a condition parameter to compute the estimate indeed. If validators didn't include justifications, other validators wouldn't be able to verify that the estimate that was chosen is accurate.

Edited: 4 months  ago

ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:7 months  ago
Posts: 31
20/06/2018 2:10 am  

Thanks @kent

There is exactly one justification per validator.

Q6. Does this imply a validator has to be aware of other validators from the same namepsace?  Or justification per the validator seen by the current validator?

 

The validator picks the latest ones they see.

Q7. What about conflicting blocks?

Imagine there are 4 validators in an individual namespace.

  • There is a name a in tuplespace.
  • a1 / a2 / a3 / a4 represent different status of this name in tuplespace. 
  • Each block packs the reduction logs and also the post state of tuplespace,  e.g.  a1->a2 represents status change of this name from a1 to a2.

Now suppose when validator#4 is packing the new block#14, it sees latest blocks of other validators : block#11 / block#12 / block#13.
Then we have the following diagram.
conflicts

Q7.1 Which block could be block#14's parents?

block#12 absolutely cannot be block#14's parent because its status change conflicts.
So I guess the parents of block#14 could be one of following cases. Right?

  • block#11
  • block#13
  • block#11 and block#13

Q7.2 Which blocks are bock#14's justifications?

According to "exactly one justification per validator" rule, I assume the justifications of block#14 are block#11, block#12, block#13, block#04. Even block#12 obviously conflicts with block#14, it is still included in its justifications. Hence justifications can be considered as "a set of potential parent block".  Please correct me if I am wrong.

Hence the estimator ε is a function whose input parameters are justifications, and its output is the "fork choice", namely the parents of the new block. 

Back to the slide

estimate

A safe estimate means it will be included in furture estimate.  That is to say, a fork choice will be respected by future fock choice. Right?

Q8. But here is the left validator producing unsafe estimate?

e.g. when it is producing estimate 2,  estimate 1 is not included; when it is producing estimate 3, estimate 2 is not included.

They are orphan blocks.  orphan blocks = unsafe estimate?  Will the the left validator be punished or slashed?

 

 


Kent liked
ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:8 months  ago
Posts: 9
20/06/2018 3:25 am  

Q6. Does this imply a validator has to be aware of other validators from the same namepsace?  Or justification per the validator seen by the current validator?

In short, yes.

More pedantically, a validator has to include a justification block for each validator that is bonded according to the block it is about to produce. That justification block can be the genesis. The genesis block is considered a block produced by all initial validators. So in theory a validator can choose to ignore seeing blocks from other validators and just point to the genesis block for those validator's justifications.

Q7.1 Which block could be block#14's parents?

It is slightly confusing because you have decided what the state changes in the block are before assigning which is the parent of which. In practice, you choose your parent block first and then create your current block which applies state changes according to the transactions you are including into the current block.

But given the information you have given, the parent of block #14 can also be block #02 or block #04. Since you haven't given justification pointers (dotted arrows), there is no evidence that validator #4 has seen block #12 yet. Similarly, the justification of block #14 for validator #2 can be either block #02 or block #12. 

Hence justifications can be considered as "a set of potential parent block"

Yes

Q8. But here is the left validator producing unsafe estimate?

That slide that you have linked shows the first step of GHOST traversal and is slightly misleading as it is incomplete. I would prefer if you used the next slide.

All blocks are not finalized when they are initially produced unless you have a single validator with more than majority of the stake. GHOST doesn't tell you which blocks are safe, the algorithm only tells you which block you are supposed to use as your parent block if you are going to create a new block.

Edited: 4 months  ago

ReplyQuote
jerry
(@jerry)
Eminent Member
Joined:7 months  ago
Posts: 31
20/06/2018 7:16 am  

Hi @kent

As I understand, a validator seeing a block  means the block is received and verified by the validator. Within a namespace bonded  with n validators, each validator need to broadcast its block to n-1 validators.  So the overall propagated block number would be O(n2). Right? 

All blocks are not finalized when they are initially produced unless you have a single validator with more than majority of the stake. GHOST doesn't tell you which blocks are safe, the algorithm only tells you which block you are supposed to use as your parent block if you are going to create a new block.

Casper Safety Proof deducts estimate safety ⇒ consensus safety.

In my opinion

  • consensus safety is a predictable state of a block among the RChain validators in a near-further time. 
  • estimate safety is the present state of an estimate produced by a validator

When most(< Byzantium fault tolerance)  of validators produce safe estimates, block in DAG chain converges to a finality state in a near-further time. Thus, consensus safety is a conclusion of estimate safety. 

So from my perspective, your explanation about estimate safety relies on the conclusion of estimate safety, and that sounds like a loop. 😉 

I am trying to understand estimate safety in the context of RChain. I believe the estimate resulted from GHOST rule is safe. But still don't quite get it.

As Casper paper says

An estimate is said to be "safe" for a particular protocol sate if it is returned by the estimator on all future protocol states. In the blockchain consensus, a block is said to be "safe" for a particular protocol state if it is also in the fork choice for all future protocol states.

forkchoice

Still take the slide as an example.

  • When left validator estimates on B, its fork choice is A
  • When left validator estimates on D, its fork choice is C, which has C->A
  • When left validator estimates on F, its fork choice is E, which has E->C->A
  • When left validator estimates on H, its fork choice is F, which has F->E->C->A

Do I get it right?  A safe estimate means the chosen fork is part of furture's chosen fork of the same validator ?

 

Best Regards


ReplyQuote
Kent
 Kent
(@kent)
Member Moderator
Joined:8 months  ago
Posts: 9
22/06/2018 2:19 am  

As I understand, a validator seeing a block  means the block is received and verified by the validator. Within a namespace bonded  with n validators, each validator need to broadcast its block to n-1 validators.  So the overall propagated block number would be O(n2). Right? 

The chain goes on forever. Are you interested in the number of blocks received per finalized block? That would be dependent on the block proposal scheme. With round-robin you can actually get O(1); see https://twitter.com/VladZamfir/status/942279992553197568 .

I believe the estimate resulted from GHOST rule is safe.

No. The estimator (GHOST) is a function that outputs an estimate. The safety oracle is a function that takes a block/estimate (and the block DAG) and outputs whether the block is safe or not.

An estimate is said to be "safe" for a particular protocol sate if it is returned by the estimator on all future protocol states. In the blockchain consensus, a block is said to be "safe" for a particular protocol state if it is also in the fork choice for all future protocol states.

Read this carefully. It says "if it is returned by the estimator on all future protocol states". It does NOT say if the estimate is returned by the estimator right now, then the estimate is safe.

When left validator estimates on B, its fork choice is A...

 

This is nitpicking on the language but it should say as follows:

When the left validator runs the estimator (GHOST) on B, then the estimate A is chosen as the parent.  The forkchoice is A -> B.

...

When left validator runs the estimator (GHOST) on H, then the estimate F is chosen as the parent. The forkchoice is A -> C -> E -> F -> H.

A safe estimate means the chosen fork is part of furture's chosen fork of the same validator

A safe estimate is a block that will always be part of the validator's future forkchoice given less than t faults.

 

 

 

Edited: 4 months  ago

ReplyQuote
  
Working

Please Login or Register