Fold validator root(s) into state root (app hash)

[liamsi]

Summary

Fold the validator roots (Header.ValidatorsHash and Header.NextValidatorsHash) into the single state root.

Problem Definition

Tendermint is designed in a way that it does not need to understand how the app that is using it is computing the state root (Header.AppHash). Only a minimal subset of the state needed by tendermint to function properly. It includes the validator set changes (computed by the app). The commitment to that part of state is computed by tendermint (and not by the app). This makes sense as this works independently on how the app tracks state and leaves and apps can define whatever business logic they want.

For LL we want to avoid several roots as every additional root means a new kind of fraud proof that needs to be defined and implemented. Hence, we want to "fold" the commitment to the validator sets into the state root (which is usually computed by the app and an opaque blob to tendermint).

Proposal

There are basically two ways we can go about this (both blur the line between the app and tendermint):

1. Remove the validator roots from tendermint and move computing the commitment into the app. Add verification logic in tendermint that requires some knowledge on how the (subset of the) state is computed.
2. Compute the commitment to the validator roots in tendermint directly using a sparse merkle tree and use the result of the app (the app hash) as subtree and merge both trees.

Both approaches have some pros and cons that we need to understand and discuss here first. One observation is that while (2.) even further blurs the line between app and tendermint, it is closer to what is already there and might have less implications on the cosmos-sdk app we will build (i.e. we can probably reuse more of the existing SDK modules without big changes).

ref: https://github.com/lazyledger/lazyledger-core/compare/ismail/unsafe_removal_ofvalhashes?expand=1
ref: celestiaorg/celestia-specs#78

[musalbas]

For any modifications we need to make, I think it's best to do them in a way that is compatible with the philosophy of Tendermint, where the ABCI client is responsible for consensus and the ABCI server is responsible for the state machine.

[liamsi]

(1.) would mean following above mentioned philosophy more than the tendermint implementation itself. Probably the desired approach if it isn't difficult to do inside the SDK (need to check).

[liamsi]

The main work for this will happen in celestiaorg/cosmos-sdk#7 but let's keep this issue around as this means we also need to change the light client to understand the subtree of the state tree in the app that contains the validators.

[liamsi]

The decision was made to keep the validator hashes as they are in the header for now.