Foundry Light Client

Foundry Light Client

Background

One of Foundry(https://github.com/CodeChain-io/foundry)’s main features is support for the IBC (Inter Blockchain Communication) protocol. The IBC protocol’s specifications are defined in the ICS (Interchain Standards, https://github.com/cosmos/ics), and Foundry has to implement all the requirements and interfaces that satisfy the ICS. One of the important parts of the ICS is the light client since each chain has to verify whether each other’s state reflects packets that they sent/received. Light clients are also important outside the IBC context. They are useful for end users who don’t mine or validate blocks.

Motivation & Goal

Our goal is to implement a light client of the foundry chain that follows the ICS specifications. By doing so,

  1. We can have a proof-of-concept of our verification algorithm. It will include the Merkle proof, header verification and the validator set verification. All these processes are required to implement a light client regardless whether it is for the ICS or not.
  2. We can provide a reference standard implementation of the light client that verifies our chain. Technically a chain should implement a light client of the other side chain to have an IBC. Our implementation will serve as a reference for those developers who want to implement a light client that supports IBC with Foundry.
  3. We can support Foundry-to-Foundry IBC. Both must verify each other’s state, and the same light client algorithm can be used.
  4. We can reuse modules or even simulate the relayer to implement a stand-alone light client which is not for the IBC.

It’s not our goal to implement all other parts of the IBC and actually run the IBC with some other chain, at least for this proposal. Instead, we will run the implementation by unit tests.

New Consensus

We modify some parts of the consensus protocol to elaborate the light client algorithm:

  1. Hash of validator set: The new consensus now includes the hash of validator set directly in the header. We define the validator set as a [(Public Key, Delegation)] and it suffices to verify the next header, while being recorded as a hash on the last header. The order of the list should be the same as the one in the state trie, as well as the bitset in the sealing. Currently the validator set is stored somewhere in the state trie indirectly, so the proof of it will be Merkle nodes, which is complicated and heavy for the light client. If we handle a separated validator set from the state and record the hash on the header, the proof will be just the validator set itself, which is much lighter. The validator set that is already in the state trie will be kept.
  2. History quiz: The new consensus now includes a combined hash of two entries. One is a pseudo-randomly chosen single state entry, which is from one of the past K states. The other one is a pseudo-randomly chosen byte snippet that is either from the block header or the validator set among the whole chain from the Genesis. The pseudo-random function takes a seed as the Merkle root of transactions (It just represents some random value that can’t be predicted until the validators actually observe the proposed block). Every other validator now has to keep K past states, all header chains, and all past validator sets. This will be helpful for the light client and VeriSync(https://medium.com/codechain/verisync-baf0583ade47) node to easily retrieve data that they might need (Imagine where a light client is trying to sync the header chain from the Genesis). This doesn’t have to be considered right now, since it doesn’t affect the verification of the light clients at all, but only the full node. It will be discussed deeply later.

Merkle Proof

The full node (or the relayer) must be able to provide a Merkle proof of the requested transaction/state. In case of states, which is important in ICS light clients, there should also be a proof of absence.

  • Proof of absence: If the key that the light client tries to find doesn’t exist, then a full node can provide a Merkle proof up to the last branch, which is a table that has ‘null’ in the slot of the next character. The light client can check the table and verify that it’s absent.

ICS

A client type is a set of definitions of the data structure, initializer, validity predicate, and misbehaviour predicate. It is an abstraction of the light client, and the IBC requires each chain to implement it properly. For simplicity, we omit the ‘previous hash’ in the block header. The verification power of the ‘previous hash’ is equivalent to checking the height in PoS (no fork). It will appear only in the actual implementation for further possible utilization.

Note: Each abstract type/function is neither concrete nor consistent enough in the specification. Finding out correspondings in our case out of abstraction requires more discussion and understanding of such vague standards. ICS7(https://github.com/cosmos/ics/tree/master/spec/ics-007-tendermint-client) is an example of Tendermint instance, which is highly relevant to us, but still being developed and seems to need more discussion there. Thus, be aware that the following are tentative and may be incorrect.

ConsensusState is an opaque data structure used to verify new commits & state roots, which represents the state of a validity predicate.

  • In our case, the hash of a validator set for a given block + commitment root.
  • A state tree carries all ConsensusStates cumulatively. (For all K past blocks)
  • If there are two ConsensusStates in the same height, then it’s called ‘equivocation’

Header is an opaque data structure used to update ConsensusState. It essentially just represents a new observation from the other chain (which must be verified).

  • In our case, it represents the header of a newly proposed block + current validator set + hash of next validator set + precommits, where ‘block’ includes height and CommitmentRoot.
  • To avoid possible confusion, the actual block header will be called ‘block header’ from now.

Consensus is a Header generating function that takes the previous ConsensusState with the messages.

  • In our case, an identity function. We assume that the relayer will give all required info(which constructs the Header) in a compact way.

Validity predicate is an opaque function to verify Headers depending on the current ConsensusState.

  • It should be far more efficient than replaying the Consensus.
  • In our case, precommits verification + checking ⅔ stake + consequent height.

Misbehaviour predicate is an opaque function used to check if data constitutes a violation of consensus protocol.

  • Existence of two signed headers is a violation of the protocol.
  • There is an associated Evidence type, which represents the proof of misbehaviour. In our case, it will be two headers with the same parent.
  • The function itself is simple: just check the evidence.

ClientState is an opaque data structure that keeps arbitrary internal state to track verified roots and past misbehaviours.

  • In our case, the hash of next validator set + latest height + frozen height(optional)
  • There must be a function that initializes ClientState from ConsensusState.
  • A state trie has only one ClientState for that block, unlike ConsensusState.

CommitmentProof is an opaque data structure that verifies the presence or absence of a particular key-value pair in a state.

  • In our case, the Merkle proof.
  • It will be tested with some CommitmentRoot.

We have to implement all data types and functions above to complete a working light client in terms of ICS.

Interfaces

  • ClientState Initialize(ConsensusState css, set<…> next_validator)
  • Header Consensus(Some_Composition_that_represents_the_Header b);
  • checkValidityAndUpdateState(ClientState cts, Header hd)
  • checkMisbehaviourAndUpdateState(ClientState cts, Evidence ev)

Light client itself can be expressed in a single statement:

checkValidityAndUpdateState(current_clientstate, Consensus(relayer.getNewblock()));

There are additional series of required functions, which all have ClientState, height, prefix, proof, port identifier, channel identifier as parameters. These functions are part of the protocol and each will be invoked in their respective appropriate times. Furthermore, their implementation would be trivial: just get an associated state from the trie and verify membership of the entry (which differs with each function) with the proof. Note that the membership is that of the other chain.

  • verifyClientConsensusState()
  • verifyConnectionState()
  • verifyChannelState()
  • verifyPacketData()
  • verifyPacketAcknowledgement()
  • verifyPacketAcknowledgementAbsence()
  • verifyNextSequenceRecv()

Reference

1 Like