NextValidatorSetHash

[ebuchman]

jae:

Light-client syncing of validator-changes

BTW, take a look at the current Block Header structure.

type Header struct {
	ChainID        string    `json:"chain_id"`
	Height         int       `json:"height"`
	Time           time.Time `json:"time"`
	NumTxs         int       `json:"num_txs"` // XXX: Can we get rid of this?
	LastBlockID    BlockID   `json:"last_block_id"`
	LastCommitHash []byte    `json:"last_commit_hash"` // commit from validators from the last block
	DataHash       []byte    `json:"data_hash"`        // transactions
	ValidatorsHash []byte    `json:"validators_hash"`  // validators for the current block
	AppHash        []byte    `json:"app_hash"`         // state after txs from the previous block
}

Gradual changes

This is assuming that there are many validators, and that the total amount of voting power that changes per block is small (e.g. << 1/3 of the voting power) and that the change is gradual.

Lets say we have the validator set V(H) for block H. That is, +2/3 of V(H) have signed block H's blockhash. Lets say the light client trusts block H. As long as the validator-set changes are gradual, for many subsequent blocks, even though the validator set is not exactly V(H), we will be able to find a sufficinet number of signatures for block H+x (x > 0) where the signatures come from the set V(H). What is a sufficient number of signatures? Well, it only needs to be 1/3+ because these validators are signing blocks at H+x whose Header includes the ValidatorsHash hash. While 1/3+ signatures isn't enough to make a commit, e.g. they may move on to subsequent rounds and actually commit another block, all valid proposals for block H+x should include the same identical ValidatorsHash because it was determined by the previous transactions that were committed at block H+x-1 and prior.

So, we can find the largest x (where x < unbonding period) such that the light client is convinced of the new validator set. And in this way the light-client can fast-forward, and as long as the validator-set changes are very gradual, the light client need only sync the validator set a few times, and still get the 1/3+ economic guarantee. This is assuming that validators are slashed for signing a block that includes an invalid header.ValidatorsHash. (If we don't assume this we can do something else, but more on that later)

Sudden changes

This is about when the validator-set can change dramatically from 1 block to another.

Header.ValidatorsHash represents the validator set that is responsible for signing that block.

Lets say we have the Commit for a block. Now, the transactions (Merkleized into DataHash) of this block haven't been executed yet, so we haven't gotten the result of EndBlock which determines who the next validators will be. But after the execution of this block, EndBlock will return validator diffs, and the next block will need to be signed by the updated validator set. (according to the current implementation of Tendermint)

This is unfortunate, because what we really want is something like this:

type Header struct {
	...
	ValidatorsHash []byte        `json:"validators_hash"`  // validators for the current block
	NextValidatorsHash []byte    `json:"validators_hash"`  // validators for the next block
	AppHash        []byte        `json:"app_hash"`         // state after txs from the previous block
}

Then we can look at the Commit for the block.Header, which would be signed by +2/3 of the validators represented by ValidatorsHash, and a light client can know how the validator-set is to evolve for the next block.

Maybe we can delay the effect of EndBlock>validator diffs for 1 block, and thereby allow us to include this NextValidatorsHash. Are there other good solutions?

Note to self: I think we want to make this change anyways in order to allow for lightweight validator signing devices that can always update

[ethanfrey]

@ebuchman @jaekwon If you could answer this question, that would be super helpful. We should also improve the current documentation on the tendermint.com website to explain this better.

I'm still very confused how to even get the signatures and validate with non-changing validator sets, without trusting any particular node. That is, I assume any information I receive over RPC may be a lie, but that if I see enough signatures, then I can trust it safely (even if the given node is lying, a signed document cannot be forged).

This is somewhat described in (somewhat outdated) html docs but I would like to get a bit more clarity to make sure I am not making a mistake here.

• A Block contains LastCommit: +2/3 precommit signatures for the previous block.
• A Commit is a set of Votes
• Each Vote contains info including the BlockHash and the signatures for it
• The BlockHash is computed from deterministically hashing the Header for that block
• The Header contains AppHash, which in code has deviated significantly from the html docs. The code says AppHash is state after txs from the previous block

If I understand this properly, if a transaction is included in Block.Data for height N, then you can query the block N+1 to see both the AppHash for the state resulting from that transaction, and the precommit votes for block N, which allow me to verify it was actually committed. However, if I want to verify this AppHash is legitimate, I must query block N+2 to get the votes for block N+1. Is this correct?

Or in general (when the transaction happened some time ago), the client needs the following to be sure:

• A merkle proof from the key-value pair leading to an AppHash for height N.
• BlockHeader for height N demonstrating that this AppHash belongs to height N and providing the BlockHash for height N
• Block for height N+1, containing the precommit votes for the block at height N
• The proper validator set to verify that these votes constitute a >2/3 majority of legitimate validators.

This issue is about the last step, but even assuming that the validator set is static for the moment (to simplify the issue), I still need a proof for height N (from the abci app), the block header for height N, and the full block for height N+1. Is that correct? Or is there a shortcut to get all this info?

[jaekwon]

If I understand this properly, if a transaction is included in Block.Data for height N, then you can query the block N+1 to see both the AppHash for the state resulting from that transaction,

Yes

and the precommit votes for block N, which allow me to verify it was actually committed.

If you just want to know that the transaction was committed. But that doesn't tell you whether the transaction was valid. You probably want to check that the AppHash is valid, and get a Merkle proof to that AppHash to prove whatever you want proven. (We will also support merkle-izing ABCI result codes, and that will be included in block N+1. This isn't yet supported).

However, if I want to verify this AppHash is legitimate, I must query block N+2 to get the votes for block N+1. Is this correct?

Yes. But there's no reason why we need to extract this from N+2, it's possible to extend the Tendermint RPC to return the commit for N+1 without getting the block at N+2. Also see "LastSeenCommit" in Tendermint which is a valid commit, but not necessarily the "canonical" commit that will get included in block N+2. For the purpose of IBC etc, LastSeenCommit may be sufficient. In any case, we should extend Tendermint RPC to return commits for any block number.

[jaekwon]

Currently MerkleEyes is programmed such that after committing block N, its internal height gets set to N. It's definitely confusing that one would get Merkle proofs for height N, and have to query Tendermint for block N+1 to get the necessary Header.AppHash.

(And of course confusing to have to query N+2 Block.Commit to prove N+1 Header, but that can be solved by expose an RPC /get_commit?height=N.)

One solution is to rename Block.Header.AppHash as Block.Header.LastAppHash. But I'm not sure that's good either. It might be better for ABCI Query to just increment 1 to the height. In other words, make MerkleEyes's internal height be 2 after committing block 1.

[ethanfrey]

Okay, so I did understand the current situation more or less correctly, but this situation needs to change soon.

I like your proposal to extend the RPC interface, so we can provide all info the client needs in one call (rather than two or three), even if it is stored in two blocks in the db. But this is part of 0.9.0/develop, right? Enhancement rather than bugfix?

[jaekwon]

0.9.0, yes. The new RPC endpoints can probably wait a bit.

[ebuchman]

This issue became 3 parts: the nextValSetHash, the merkleeyes query height, and the tendermint rpc commit. the latter two are done (tendermint/abci#61 and #405). The nextValSetHash should be bumped to 0.10.0.

[ethanfrey]

Uh, the merkleeyes query height is exposed in the abci app, but is not implemented not exposed in the rpc. I wouldn't quite call it done.

But, yes, finishing this by 0.10.0 makes sense

[ebuchman]

@ethanfrey do we still need this ?

[ethanfrey]

IMO we don't need this.

The only use case it helps us with is >1/3 validators changing in one block. Then a light client could never prove the transition externally with the given rules.

However, I think this is a pathological case and we should not complicate the code to support it. Rather, I would propose something like limiting the validator change per block to 10% or 20%. The abci app should do this, but maybe some checks in tendermint.

[ebuchman]

Cool. Why not just set the limit to <1/3 ? And then it's up to the app to ensure <1/3 changes in a block

[ebuchman]

Ok, replaced by #950