docs: Add check validators spec by josef-widder · Pull Request #3710 · tendermint/tendermint

josef-widder · 2019-06-03T13:52:56Z

Updated all relevant documentation in docs
Updated all code comments where relevant
Wrote tests
Updated CHANGELOG_PENDING.md

codecov-io · 2019-06-03T13:54:41Z

Codecov Report

Merging #3710 into develop will decrease coverage by 0.02%.
The diff coverage is n/a.

@@             Coverage Diff             @@
##           develop    #3710      +/-   ##
===========================================
- Coverage    63.35%   63.33%   -0.03%     
===========================================
  Files          218      218              
  Lines        18239    18239              
===========================================
- Hits         11556    11552       -4     
- Misses        5707     5710       +3     
- Partials       976      977       +1

Impacted Files	Coverage Δ
blockchain/reactor.go	`71.49% <0%> (-2.81%)`	⬇️
blockchain/pool.go	`79.6% <0%> (-2.64%)`	⬇️
consensus/state.go	`79.97% <0%> (+0.23%)`	⬆️
consensus/reactor.go	`71.71% <0%> (+0.93%)`	⬆️

ancazamfir · 2019-06-04T20:32:18Z

docs/spec/consensus/checkvalidators.md

+powers of PA and UV is less than a third of the total voting power, then in
+$nh$, more than 2/3 of the voting power is held by correct processes. Formally,
+if for all PA
+


I am not sure where we take into account the power change of common validators. Should we consider that as an increase of "bad" power (add it to the left of the <) ?

Note that in the expression below, we fix PA from old header, but we take into account only its voting power in the new header.

But the calculation on the old header just gives us the maximum possible bad voting power. It doesn't tell us that in fact the validators in the PA that gives that maximum are faulty. It can happen that actual bad validators outside PA have increased in power and good validators have decreased in power. I will try to find an example for this.

We don't do calculation on the old header. Note that the sum is only on p which is voting power of validators from PA in the new header. We only intersect with the old header.

ancazamfir · 2019-06-04T22:18:27Z

docs/spec/consensus/checkvalidators.md

+
+  vpUV := votingpower(UV,nh)  // second sum in Theorem 1
+  vpNH := votingpower(nh.V,nh) // right hand side of premise of Theorem 1
+  vpMaxPA := maximumvotingpower(PAs,nh) // voting powers of all PA and big max


Not sure if you looked into the complexity here yet. Maybe we can use the 0/1 knapsack algorithm (pseudo-polynomial), i.e. determine vpMaxPA, the maximum power that can fill a knapsack no bigger than 1/3 total voting power.
It would be O(n*vpNH), better than the O(2**n) for compute_all_PAs(oh) but still not great.
n - number validators (~100)
vpNH - 1/3 total voting power, would have to look into real numbers but I think it is high...maybe can be optimized using normalization of powers (weights in knapsack problem)?.

Haven't been thinking about efficient way of implementing it. We would need your help there :)

See below comment.

ancazamfir · 2019-06-05T04:35:45Z

docs/spec/consensus/checkvalidators.md

+  vpMaxPA := maximumvotingpower(PAs,nh) // voting powers of all PA and big max
+
+  return vpMaxPA + vpUV < 1/3 * vpNH  // Theorem 1. It must be smaller for all
+                                        // so it must be smaller for the max


Maybe we can memoize (vpMaxPA + vpUV) as the vpMaxPA of next iteration's old header so we would only need to do the expensive computation once for initial header.

ancazamfir · 2019-06-05T11:22:26Z

docs/spec/consensus/checkvalidators.md

+## Remarks
+
+**Remark.** Computing all PAs might be too expensive (all subsets of $oh.V$ that have a certain combined voting power in oh). Similarly, we then have to compute all voting powers of PAs in nh to get the maximum. This is disturbing, as right now, based on the examples, I expect that CheckVS will mostly return false, assuming that there are frequent changes in the validator sets. However, $oh.V=nh.V$ might be the common case.
+


Should this spec also cover what the lite client should do if CheckVS returns false? There might be just doing bisection or maybe a smarter strategy

Yes, it should be complete algorithm that includes bisection most probably. We need to integrate this with the old spec so it complete. There are also some parts missing regarding counter factual slashing.

cwgoes

Left comments! I wonder if it will be clearer to reason about lite clients as somehow corresponding to the behaviour of full nodes rather than formulating a separate correct-process assumption.

This should probably be fused with #3795 and #3796.

cwgoes · 2019-07-15T14:33:20Z

docs/spec/consensus/checkvalidators.md

+    - $nextV$: next validators
+  * $tp$: trusting period   
+  * for a time $t$, the predicate $correct(v,t)$ is true if the validator $v$
+    follows the protocol until time $t$ (we will see about recovery later).


What is t in reference to? A local clock or a global clock?

cwgoes · 2019-07-15T14:38:08Z

docs/spec/consensus/checkvalidators.md

+
+## LightClient Trusting Spec
+
+### LightClient Invariant


I am not sure this is the best place to start the light client definition. Is this how we define full nodes? I think we just want the light client header acceptance algorithm to reflect what a full node would have done given the same set of messages (condensed into headers in the case of a light client).

In particular, this does not even hold for subsequent blocks (block 11 following block 10) if the validator set changes by more than 1/3, which is possible. It also doesn't capture fault-accountability (which we should be able to capture precisely, such that a light client could only diverge from a full node if a slashable signature event by at least a well-defined fraction of stake had occurred).

cwgoes · 2019-07-15T14:38:29Z

docs/spec/consensus/checkvalidators.md

+
+**Question:** What should be the precise assumption here. Is the invariant on $h.V$ or on $h.NextV$ or both?
+
+*Assumption:* If a header is properly generated, then the above equations hold.


What does this mean? No, I don't think they do, if the validator set changes by enough even in a single block.

cwgoes · 2019-07-15T14:39:22Z

docs/spec/consensus/checkvalidators.md

+
+### Liveness
+
+*Draft:* If a header $h$ as been properly generated by the blockchain (and its age is less than the trusting period), then a correct LightClient will eventually set $trust(h) = true$.


We need to assume synchronous data availability of headers, which is fine. Maybe we should emphasize that headers can be received out of order and the light client will determine which it needs to query for at what times?

cwgoes · 2019-07-15T14:40:52Z

docs/spec/consensus/checkvalidators.md

+1. **an uninterrupted sequence of proof.** If a block is appended to the chain, where the last block
+is trusted (and properly committed by the old validator set in the next block),
+and the new block contains a new validator set, the new block is trusted if the LightClient knows all headers in the prefix.
+Intuitively, a trusted validator set is assumed to not chose a new validator set


OK, but it's also the case, critically, that headers contain the hash of the next validator set, so the light client can verify that the validator set of block n (which they trust) signed off on the validator set of block n + 1, which provides some level of assurance (in practice) on what has happened in the state machine, e.g. that the new validators have put up stake which could be slashed.

cwgoes · 2019-07-15T14:41:04Z

docs/spec/consensus/checkvalidators.md

+
+2. **trusting period.** Based on a trusted block *h*, and the LightClient
+Invariant, which ensures the fault assumption during the trusting period, we can
+try to infer wether it is guaranteed that the validator set of the new block


Suggested change

try to infer wether it is guaranteed that the validator set of the new block

try to infer whether it is guaranteed that the validator set of the new block

cwgoes · 2019-07-15T14:44:17Z

docs/spec/consensus/checkvalidators.md

+\]
+
+
+Validator 4 has more than a third voting power in nh.V. As trusting oh does not


This could occur on subsequent blocks.

docs/spec/consensus/checkvalidators.md

cwgoes · 2019-07-15T14:52:26Z

docs/spec/consensus/checkvalidators.md

+
+  vpUV := votingpower(UV,nh)  // second sum in Theorem 1
+  vpNH := votingpower(nh.V,nh) // right hand side of premise of Theorem 1
+  vpMaxPA := maximumvotingpower(PAs,nh) // voting powers of all PA and big max


See below comment.

tac0turtle · 2019-07-22T13:33:23Z

Closing this PR and #3796, as @milosevic & @josef-widder will open a new pr with these two documents combined.

Josef Widder added 3 commits June 3, 2019 15:35

draft spec

782c655

pdf version of draft spec

4214694

fixes

2506acb

cwgoes self-assigned this Jun 3, 2019

xla changed the title ~~Josef/check validators~~ Add check validators spec Jun 4, 2019

xla changed the title ~~Add check validators spec~~ docs: Add check validators spec Jun 4, 2019

ancazamfir reviewed Jun 4, 2019

View reviewed changes

ancazamfir reviewed Jun 5, 2019

View reviewed changes

tac0turtle changed the base branch from develop to master June 26, 2019 15:35

cwgoes mentioned this pull request Jun 29, 2019

Write Tendermint light client ADR cosmos/ibc#117

Closed

tac0turtle added the C:docs Component: Documentation label Jul 1, 2019

tac0turtle added the WIP label Jul 10, 2019

cwgoes suggested changes Jul 15, 2019

View reviewed changes

cwgoes removed their assignment Jul 15, 2019

milosevic mentioned this pull request Jul 15, 2019

[ADR -44] Lite Client with Weak Subjectivity #3795

Merged

tac0turtle mentioned this pull request Jul 22, 2019

Lite Client Spec #3796

Closed

5 tasks

tac0turtle closed this Jul 22, 2019

		## Remarks

		Remark. Computing all PAs might be too expensive (all subsets of $oh.V$ that have a certain combined voting power in oh). Similarly, we then have to compute all voting powers of PAs in nh to get the maximum. This is disturbing, as right now, based on the examples, I expect that CheckVS will mostly return false, assuming that there are frequent changes in the validator sets. However, $oh.V=nh.V$ might be the common case.


		Question: What should be the precise assumption here. Is the invariant on $h.V$ or on $h.NextV$ or both?

		Assumption: If a header is properly generated, then the above equations hold.


		### Liveness

		Draft: If a header $h$ as been properly generated by the blockchain (and its age is less than the trusting period), then a correct LightClient will eventually set $trust(h) = true$.

	try to infer wether it is guaranteed that the validator set of the new block
	try to infer whether it is guaranteed that the validator set of the new block

		\]


		Validator 4 has more than a third voting power in nh.V. As trusting oh does not

Conversation

josef-widder commented Jun 3, 2019

Uh oh!

codecov-io commented Jun 3, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ancazamfir Jun 5, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cwgoes left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tac0turtle commented Jul 22, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

codecov-io commented Jun 3, 2019 •

edited

Loading

ancazamfir Jun 5, 2019 •

edited

Loading