Skip to content

Latest commit

 

History

History
447 lines (358 loc) · 18.2 KB

README.md

File metadata and controls

447 lines (358 loc) · 18.2 KB
Raw
ics title stage category kind implements author created modified
7
Tendermint Client
draft
IBC/TAO
instantiation
2
Christopher Goes <[email protected]>
2019-12-10
2019-12-19

Synopsis

This specification document describes a client (verification algorithm) for a blockchain using Tendermint consensus.

Motivation

State machines of various sorts replicated using the Tendermint consensus algorithm might like to interface with other replicated state machines or solo machines over IBC.

Definitions

Functions & terms are as defined in ICS 2.

currentTimestamp is as defined in ICS 24.

The Tendermint light client uses the generalised Merkle proof format as defined in ICS 23.

hash is a generic collision-resistant hash function, and can easily be configured.

Desired Properties

This specification must satisfy the client interface defined in ICS 2.

Note on "would-have-been-fooled logic

The basic idea of "would-have-been-fooled" detection is that it allows us to be a bit more conservative, and freeze our light client when we know that another light client somewhere else on the network with a slightly different update pattern could have been fooled, even though we weren't.

Consider a topology of three chains - A, B, and C, and two clients for chain A, A_1 and A_2, running on chains B and C respectively. The following sequence of events occurs:

  • Chain A produces a block at height h_0 (correctly).
  • Clients A_1 and A_2 are updated to the block at height h_0.
  • Chain A produces a block at height h_0 + n (correctly).
  • Client A_1 is updated to the block at height h_0 + n (client A_2 is not yet updated).
  • Chain A produces a second (equivocating) block at height h_0 + k, where k <= n.

Without "would-have-been-fooled", it will be possible to freeze client A_2 (since there are two valid blocks at height h_0 + k which are newer than the latest header A_2 knows), but it will not be possible to freeze A_1, since A_1 has already progressed beyond h_0 + k.

Arguably, this is disadvantageous, since A_1 was just "lucky" in having been updated when A_2 was not, and clearly some Byzantine fault has happened that should probably be deal with by human or governance system intervention. The idea of "would-have-been-fooled" is to allow this to be detected by having A_1 start from a configurable past header to detect misbehaviour (so in this case, A_1 would be able to start from h_0 and would also be frozen).

There is a free parameter here - namely, how far back is A_1 willing to go (how big can n be where A_1 will still be willing to look up h_0, having been updated to h_0 + n)? There is also a countervailing concern, in and of that double-signing is presumed to be costless after the unbonding period has passed, and we don't want to open up a denial-of-service vector for IBC clients.

The necessary condition is thus that A_1 should be willing to look up headers as old as it has stored, but should also enforce the "unbonding period" check on the misbehaviour, and avoid freezing the client if the misbehaviour is older than the unbonding period (relative to the client's local timestamp). If there are concerns about clock skew a slight delta could be added.

Technical Specification

This specification depends on correct instantiation of the Tendermint consensus algorithm and light client algorithm.

Client state

The Tendermint client state tracks the current revision, current validator set, trusting period, unbonding period, latest height, latest timestamp (block time), and a possible frozen height.

interface ClientState {
  chainID: string
  trustLevel: Rational
  trustingPeriod: uint64
  unbondingPeriod: uint64
  latestHeight: Height
  frozenHeight: Maybe<uint64>
  upgradePath: []string
  maxClockDrift: uint64
  proofSpecs: []ProofSpec
}

Consensus state

The Tendermint client tracks the timestamp (block time), the hash of the next validator set, and commitment root for all previously verified consensus states (these can be pruned after the unbonding period has passed, but should not be pruned beforehand).

interface ConsensusState {
  timestamp: uint64
  nextValidatorsHash: []byte
  commitmentRoot: []byte
}

Height

The height of a Tendermint client consists of two uint64s: the revision number, and the height in the revision.

interface Height {
  revisionNumber: uint64
  revisionHeight: uint64
}

Comparison between heights is implemented as follows:

function compare(a: TendermintHeight, b: TendermintHeight): Ord {
  if (a.revisionNumber < b.revisionNumber)
    return LT
  else if (a.revisionNumber === b.revisionNumber)
    if (a.revisionHeight < b.revisionHeight)
      return LT
    else if (a.revisionHeight === b.revisionHeight)
      return EQ
  return GT
}

This is designed to allow the height to reset to 0 while the revision number increases by one in order to preserve timeouts through zero-height upgrades.

Headers

The Tendermint headers include the height, the timestamp, the commitment root, the hash of the validator set, the hash of the next validator set, and the signatures by the validators who committed the block. The header submitted to the on-chain client also includes the entire validator set, and a trusted height and validator set to update from. This reduces the amount of state maintained by the on-chain client and prevents race conditions on relayer updates.

interface TendermintSignedHeader {
  height: uint64
  timestamp: uint64
  commitmentRoot: []byte
  validatorsHash: []byte
  nextValidatorsHash: []byte
  signatures: []Signature
}
interface Header {
  TendermintSignedHeader
  identifier: string
  validatorSet: List<Pair<Address, uint64>>
  trustedHeight: Height
  trustedValidatorSet: List<Pair<Address, uint64>>
}

// GetHeight will return the header Height in the IBC ClientHeight
// format.
// Implementations may use the revision number to increment the height
// across height-resetting upgrades. See ibc-go for an example
func (Header) GetHeight() {
  return Height{0, height}
}

Header implements ClientMessage interface.

Misbehaviour

The Misbehaviour type is used for detecting misbehaviour and freezing the client - to prevent further packet flow - if applicable. Tendermint client Misbehaviour consists of two headers at the same height both of which the light client would have considered valid.

interface Misbehaviour {
  identifier: string
  h1: Header
  h2: Header
}

Misbehaviour implements ClientMessage interface.

Client initialisation

Tendermint client initialisation requires a (subjectively chosen) latest consensus state, including the full validator set.

function initialise(
  chainID: string, consensusState: ConsensusState,
  trustLevel: Fraction, height: Height, trustingPeriod: uint64, unbondingPeriod: uint64,
  upgradePath: []string, maxClockDrift: uint64, proofSpecs: []ProofSpec): ClientState {
    assert(trustingPeriod < unbondingPeriod)
    assert(height > 0)
    assert(trustLevel >= 1/3 && trustLevel <= 1)
    // implementations may define a identifier generation function
    identifier = generateClientIdentifier()
    set("clients/{identifier}/consensusStates/{height}", consensusState)
    return ClientState{
      chainID,
      trustLevel,
      latestHeight: height,
      trustingPeriod,
      unbondingPeriod,
      frozenHeight: null,
      upgradePath,
      maxClockDrift,
      proofSpecs
    }
}

The Tendermint client latestClientHeight function returns the latest stored height, which is updated every time a new (more recent) header is validated.

function latestClientHeight(clientState: ClientState): Height {
  return clientState.latestHeight
}

Validity Predicate

Tendermint client validity checking uses the bisection algorithm described in the Tendermint spec. If the provided header is valid, the client state is updated & the newly verified commitment written to the store.

function verifyClientMessage(
  clientMsg: ClientMessage) {
    switch typeof(clientMsg) {
      case Header:
        verifyHeader(clientMsg)
      case Misbehaviour:
        verifyHeader(clientMsg.h1)
        verifyHeader(clientMsg.h2)
    }
}

Verify validity of regular update to the Tendermint client

function verifyHeader(header: Header) {
    clientState = get("clients/{header.identifier}/clientState")
    // assert trusting period has not yet passed
    assert(currentTimestamp() - clientState.latestTimestamp < clientState.trustingPeriod)
    // assert header timestamp is less than trust period in the future. This should be resolved with an intermediate header.
    assert(header.timestamp - clientState.latestTimeStamp < clientState.trustingPeriod)
    // trusted height revision must be the same as header revision
    // if revisions are different, use upgrade client instead
    // trusted height must be less than header height
    assert(header.GetHeight().revisionNumber == header.trustedHeight.revisionNumber)
    assert(header.GetHeight().revisionHeight > header.trustedHeight.revisionHeight)
    // fetch the consensus state at the trusted height
    consensusState = get("clients/{header.identifier}/consensusStates/{header.trustedHeight}")
    // assert that header's trusted validator set hashes to consensus state's validator hash
    assert(hash(header.trustedValidatorSet) == consensusState.nextValidatorsHash)

    // call the tendermint client's `verify` function
    assert(tmClient.verify(
      header.trustedValidatorSet,
      clientState.latestHeight,
      clientState.trustingPeriod,
      clientState.maxClockDrift,
      header.TendermintSignedHeader,
    ))
}

Misbehaviour Predicate

CheckForMisbehaviour will check if an update contains evidence of Misbehaviour. If the ClientMessage is a header we check for implicit evidence of misbehaviour by checking if there already exists a conflicting consensus state in the store or if the header breaks time monotonicity.

function checkForMisbehaviour(
  clientMsg: clientMessage) => bool {
    clientState = get("clients/{clientMsg.identifier}/clientState")
    switch typeof(clientMsg) {
      case Header:
        // fetch consensusstate at header height if it exists
        consensusState = get("clients/{clientMsg.identifier}/consensusStates/{header.GetHeight()}")
        // if consensus state exists and conflicts with the header
        // then the header is evidence of misbehaviour
        if consensusState != nil && consensusState.commitmentRoot != header.commitmentRoot {
          return true
        }

        // check for time monotonicity misbehaviour
        // if header is not monotonically increasing with respect to neighboring consensus states
        // then return true
        // NOTE: implementation must have ability to iterate ascending/descending by height
        prevConsState = getPreviousConsensusState(header.GetHeight())
        nextConsState = getNextConsensusState(header.GetHeight())
        if prevConsState.timestamp >= header.timestamp {
          return true
        }
        if nextConsState != nil && nextConsState.timestamp <= header.timestamp {
          return true
        }
      case Misbehaviour:
        // assert that the heights are the same
        assert(misbehaviour.h1.height === misbehaviour.h2.height)
        // assert that the commitments are different
        assert(misbehaviour.h1.commitmentRoot !== misbehaviour.h2.commitmentRoot)
    }
}

UpdateState

UpdateState will perform a regular update for the Tendermint client. It will add a consensus state to the client store. If the header is higher than the lastest height on the clientState, then the clientState will be updated.

function updateState(
  clientMsg: clientMessage) {
    clientState = get("clients/{clientMsg.identifier}/clientState)
    header = Header(clientMessage)
    // only update the clientstate if the header height is higher
    // than clientState latest height
    if clientState.height < header.GetHeight() {
      // update latest height
      clientState.latestHeight = header.GetHeight()

      // save the client
      set("clients/{clientMsg.identifier}/clientState", clientState)
    }

    // create recorded consensus state, save it
    consensusState = ConsensusState{header.timestamp, header.nextValidatorsHash, header.commitmentRoot}
    set("clients/{clientMsg.identifier}/consensusStates/{header.GetHeight()}", consensusState)
    // these may be stored as private metadata within the client in order to verify
    // that the delay period has passed in proof verification
    set("clients/{clientMsg.identifier}/processedTimes/{header.GetHeight()}", currentTimestamp())
    set("clients/{clientMsg.identifier}/processedHeights/{header.GetHeight()}", currentHeight())
}

UpdateStateOnMisbehaviour

UpdateStateOnMisbehaviour will set the frozen height to a non-zero sentinel height to freeze the entire client.

function updateStateOnMisbehaviour(clientMsg: clientMessage) {
    clientState = get("clients/{clientMsg.identifier}/clientState)
    clientState.frozenHeight = Height{0, 1}
    set("clients/{clientMsg.identifier}/clientState", clientState)
}

Upgrades

The chain which this light client is tracking can elect to write a special pre-determined key in state to allow the light client to update its client state (e.g. with a new chain ID or revision) in preparation for an upgrade.

As the client state change will be performed immediately, once the new client state information is written to the predetermined key, the client will no longer be able to follow blocks on the old chain, so it must upgrade promptly.

function upgradeClientState(
  clientState: ClientState,
  newClientState: ClientState,
  height: Height,
  proof: CommitmentPrefix) {
    // assert trusting period has not yet passed
    assert(currentTimestamp() - clientState.latestTimestamp < clientState.trustingPeriod)
    // check that the revision has been incremented
    assert(newClientState.latestHeight.revisionNumber > clientState.latestHeight.revisionNumber)
    // check proof of updated client state in state at predetermined commitment prefix and key
    path = applyPrefix(clientState.upgradeCommitmentPrefix, clientState.upgradeKey)
    // check that the client is at a sufficient height
    assert(clientState.latestHeight >= height)
    // check that the client is unfrozen or frozen at a higher height
    assert(clientState.frozenHeight === null || clientState.frozenHeight > height)
    // fetch the previously verified commitment root & verify membership
    root = get("clients/{clientMsg.identifier}/consensusStates/{height}")
    // verify that the provided consensus state has been stored
    assert(root.verifyMembership(path, newClientState, proof))
    // update client state
    clientState = newClientState
    set("clients/{clientMsg.identifier}/clientState", clientState)
}

State verification functions

Tendermint client state verification functions check a Merkle proof against a previously validated commitment root.

These functions utilise the proofSpecs with which the client was initialised.

function verifyMembership(
  clientState: ClientState,
  height: Height,
  delayTimePeriod: uint64,
  delayBlockPeriod: uint64,
  proof: CommitmentProof,
  path: CommitmentPath,
  value: []byte) {
    // check that the client is at a sufficient height
    assert(clientState.latestHeight >= height)
    // check that the client is unfrozen or frozen at a higher height
    assert(clientState.frozenHeight === null || clientState.frozenHeight > height)
    // assert that enough time has elapsed
    assert(currentTimestamp() >= processedTime + delayPeriodTime)
    // assert that enough blocks have elapsed
    assert(currentHeight() >= processedHeight + delayPeriodBlocks)
    // fetch the previously verified commitment root & verify membership
    // Implementations may choose how to pass in the identifier
    // ibc-go provides the identifier-prefixed store to this method
    // so that all state reads are for the client in question
    root = get("clients/{clientIdentifier}/consensusStates/{height}")
    // verify that <path, value> has been stored
    assert(verifyMembership(root, proof, path, value))
}

function verifyNonMembership(
  clientState: ClientState,
  height: Height,
  delayTimePeriod: uint64,
  delayBlockPeriod: uint64,
  proof: CommitmentProof,
  path: CommitmentPath) {
    // check that the client is at a sufficient height
    assert(clientState.latestHeight >= height)
    // check that the client is unfrozen or frozen at a higher height
    assert(clientState.frozenHeight === null || clientState.frozenHeight > height)
    // assert that enough time has elapsed
    assert(currentTimestamp() >= processedTime + delayPeriodTime)
    // assert that enough blocks have elapsed
    assert(currentHeight() >= processedHeight + delayPeriodBlocks)
    // fetch the previously verified commitment root & verify membership
    // Implementations may choose how to pass in the identifier
    // ibc-go provides the identifier-prefixed store to this method
    // so that all state reads are for the client in question
    root = get("clients/{identifier}/consensusStates/{height}")
    // verify that nothing has been stored at path
    assert(verifyMembership(root, proof, path))
}

Properties & Invariants

Correctness guarantees as provided by the Tendermint light client algorithm.

Backwards Compatibility

Not applicable.

Forwards Compatibility

Not applicable. Alterations to the client verification algorithm will require a new client standard.

Example Implementation

None yet.

Other Implementations

None at present.

History

December 10th, 2019 - Initial version December 19th, 2019 - Final first draft

Copyright

All content herein is licensed under Apache 2.0.