mirror of
https://github.com/fluencelabs/tendermint
synced 2025-04-26 15:22:15 +00:00
225 lines
8.1 KiB
Markdown
225 lines
8.1 KiB
Markdown
# Checking Validator Set (CheckVS)
|
|
|
|
As part of the light client, the CheckVS procedure has to check, whether given
|
|
two headers (whose heigts differ by more than 1), the LightClient can trust the
|
|
newer header under the assumption it trusted the old one.
|
|
|
|
This document contains some math formulas. To ease reading, the file
|
|
/tendermint/docs/spec/pdfs/checkvalidators.pdf
|
|
displays them correctly.
|
|
|
|
## Definitions
|
|
|
|
* header fields
|
|
- $height$
|
|
- $bfttime$: the chain time when the header (block) was generated
|
|
- $V$: validator set containing validators.
|
|
- $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).
|
|
Similarly we define $faulty(v,t)$.
|
|
* For each header $h$ it has locally stored, the LightClient stores whether
|
|
it trusts $h$. We write $trust(h) = true$, if this is the case.
|
|
* Validator fields. We will write a validator as a tuple $(v,p)$ such that
|
|
+ $v$ is the identifier (we assume identifiers are unique in each validator set)
|
|
+ $p$ is its voting power
|
|
|
|
## LightClient Trusting Spec
|
|
|
|
### LightClient Invariant
|
|
For each LightClient $l$ and each header $h$:
|
|
if $l$ has set $trust(h) = true$,
|
|
then validators that are correct until time $h.bfttime + tp$ have more than two thirds of the voting power in $h.V$. (Or/and $h.nextV$)
|
|
|
|
Formally,
|
|
\[\sum_{(v,p) \in h.V \wedge \\correct(v,h.bfttime + tp)} p > 2/3 \sum_{(v,p) \in h.V} p\]
|
|
|
|
Equivalently,
|
|
\[\sum_{(v,p) \in h.V \wedge\\ faulty(v,h.bfttime + tp)} p < 1/3 \sum_{(v,p) \in h.V} p\]
|
|
|
|
**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$.
|
|
|
|
|
|
|
|
|
|
## High Level Solution
|
|
|
|
Upon initialization, the LightClient is given a header *inithead* it trusts by
|
|
social consensus. It is assumed that *inithead* satisfies the LightClient
|
|
Invariant.
|
|
|
|
When a LightClients sees a new header it has to decide whether to trust the new
|
|
header. Trust can be obtained by (possibly) the combination of two methods.
|
|
|
|
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
|
|
that violates the fault assumption.
|
|
|
|
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
|
|
contains > 2/3 correct voting power. If such a validator set commits a block, we
|
|
can trust it, as these processes have been continuously correct by the
|
|
invariant.
|
|
|
|
###Examples: for the "trusting period" method
|
|
|
|
* *oh*: the old trusted header
|
|
* *nh*: the new header that has to be checked
|
|
|
|
Let's assume $oh.bfttime + tp > nh.bfttime$ and $oh.bfttime + tp > now$.
|
|
In the following examples, the pairs $(v,p)$ denote validators and their voting power.
|
|
|
|
####Example: Identical VSets
|
|
|
|
\[
|
|
oh.V = \{(1,1), ... (4,1)\}\\
|
|
nh.V = \{(1,1), ... (4,1)\}
|
|
\]
|
|
|
|
As we trust oh.V (at oh.bfttime) and the trusting period is not over yet, we
|
|
trust nh.V.
|
|
|
|
####Example: Changed Voting powers
|
|
|
|
\[
|
|
oh.V = \{(1,1), ... (4,1)\}\\
|
|
nh.V = \{(1,1), ... (4,2)\}
|
|
\]
|
|
|
|
|
|
Validator 4 has more than a third voting power in nh.V. As trusting oh does not
|
|
rule out that 4 is faulty, the fault assumption might be violated in $nh.V$. Thus, $nh.V$
|
|
cannot be trusted.
|
|
|
|
####Example: Lucky case with $n> 3t +1$
|
|
|
|
\[
|
|
oh.V = \{(1,1), ... (6,1)\}\\
|
|
nh.V = \{(1,1), ... (7,1)\}
|
|
\]
|
|
|
|
By the fault assumption ($n > 3t$), at most one validator in
|
|
$oh.V$ is faulty. In addition, validator 7 may be faulty. As a result
|
|
there are at most 2 faulty validators in $nh.V$. Because $7 > 3 \cdot 2$ we
|
|
say that oh.V provides sufficient trust in order to trust $nh.V$.
|
|
|
|
####Example: Swapping validators
|
|
|
|
\[
|
|
oh.V = \{(1,1), ... (4,1)\}\\
|
|
nh.V = \{(2,1), ... (5,1)\}
|
|
\]
|
|
|
|
|
|
|
|
|
|
Observe that validator 1 is not present in $nh.V$. Conservatively, we have to
|
|
assume 1 is correct, and there may be a fault among 2,3,4. In addition, we don't
|
|
know 5, so that conservatively, we have to assume 5 may be faulty. Thus among
|
|
2,3,4,5, there may be two faults which violates the faults assumption. Thus $oh$
|
|
does **not** provide sufficient trust in order to trust $nh$.
|
|
|
|
|
|
## Basics for the "trusting period" method
|
|
|
|
The function `CheckVS(oh, nh)` returns true, when *oh* provides sufficient
|
|
trust to trust nh.
|
|
|
|
### Assumptions
|
|
|
|
1. $tp < unbonding period$.
|
|
2. $nh.bfttime < now$
|
|
3. $nh.bfttime < oh.bfttime+tp$
|
|
4. $trust(oh)=true$
|
|
|
|
### Some Maths
|
|
|
|
**Observation 1.** If $oh.bfttime + tp > now$, we trust the old
|
|
validator set $oh.V$.
|
|
|
|
In the following let's assume oh is trusted and sufficiently new.
|
|
|
|
**Definition 1.** Let $PA \subseteq oh.V$ be a *potential adversary* in $oh$, if
|
|
the sum of the voting powers in PA is less than 1/3 of the voting
|
|
powers in $oh.V$, that is,
|
|
\[
|
|
\sum_{(v,p) \in PA} p < 1/3 \sum_{(v,p) \in oh.V} p
|
|
\]
|
|
|
|
**Proposition 1.** The set of faulty processes
|
|
\[oh.V \setminus \{(v,p): (v,p) \in oh.V \wedge correct(v,oh.bfttime + tp)\}\]
|
|
is a potential adversary.
|
|
|
|
*Proof.* By the LightClient invariant.
|
|
|
|
**Definition 2.** Let the *unknown validators* UV be the validators that appear in $nh.V$ and not in
|
|
$oh.V$, that is,
|
|
\[
|
|
UV = \{(v,p): (v,p) \in nh.V \wedge \nexists (v,x) \in oh.V \}.
|
|
\]
|
|
|
|
|
|
|
|
|
|
**Theorem 1.** If for all potential adversaries PA, in $nh$ the combined voting
|
|
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
|
|
|
|
\[
|
|
\sum_{(v,old) \in PA \wedge \\ (v,p) \in nh.V} p + \sum_{(v,p) \in UV} p < 1/3
|
|
\sum_{(v,p) \in nh.V} p,
|
|
\]
|
|
then
|
|
\[
|
|
\sum_{(v,p) \in nh.V \wedge \\correct(v,oh.bfttime + tp)} p > 2/3 \sum_{(v,p) \in h.V} p
|
|
\]
|
|
|
|
*Proof.* By the definition of PA, Proposition 1, and the LightClient invariant.
|
|
|
|
By Assumption 3, there is sufficient voting power to trust the new validator set. (And thus the validator set it signs in that block, for which the $tp$ starts at the $bfttime$ of the header).
|
|
|
|
Below, we thus sketch a function that checks whether the premise of Theorem 1 holds. If the results is positive, we can trust $nh$, otherwise not.
|
|
|
|
|
|
|
|
### An Algorithm
|
|
|
|
In pseudo go...
|
|
|
|
```go
|
|
func CheckVS(oh, nh) bool {
|
|
if oh.bfttime + unbonding_period < now { // Observation 1
|
|
return false // old header was once trusted but it is expired
|
|
}
|
|
|
|
PAs := compute_all_PAs(oh) // Definition 1
|
|
PAs := reduce (PAs) // remove every PA that is a subset of another PA
|
|
UV := compute_UV(oh,nh) // Definition 2
|
|
|
|
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
|
|
|
|
return vpMaxPA + vpUV < 1/3 * vpNH // Theorem 1. It must be smaller for all
|
|
// so it must be smaller for the max
|
|
}
|
|
```
|
|
|
|
|
|
## 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.
|
|
|
|
**To Do.** The current invariant assumes that the 1/3 fault assumption is always satisfied. If this is not the case, and there is slashing, etc., we should write the spec of the fault assumptions with temporary violations. Cf. fork accountability, slashing, "counter factual signing" etc.
|