GRANDPA Client - Cosmos Docs

概述

本文档规定了一个用于采用 GRANDPA 的区块链的客户端（验证算法）。 GRANDPA（基于 GHOST 的递归祖先推导前缀一致性，GHOST-based Recursive Ancestor Deriving Prefix Agreement）是一种将用于 Polkadot 中继链的最终性工具。它现在已有 Rust 实现，并且是 Substrate 的一部分，因此使用 Substrate 构建的区块链很可能会将 GRANDPA 用作其最终性工具。

动机

使用 GRANDPA 最终性工具的区块链可能希望通过 IBC 与其他复制状态机或独立机器进行互操作。

定义

函数和术语的定义见 ICS 2。

期望属性

本规范必须满足 ICS 2 中定义的客户端接口。

技术规范

本规范依赖于 GRANDPA 最终性工具及其轻客户端算法的正确实例化。

客户端状态

GRANDPA 客户端状态跟踪最新高度以及一个可能存在的冻结高度。

interface ClientState {
  latestHeight: uint64
  frozenHeight: Maybe<uint64>
}

权威集

GRANDPA 的权威集合。

interface AuthoritySet {
  // this is incremented every time the set changes
  setId: uint64
  authorities: List<Pair<AuthorityId, AuthorityWeight>>
}

共识状态

GRANDPA 客户端会为所有先前已验证的共识状态跟踪权威集和承诺根。

interface ConsensusState {
  authoritySet: AuthoritySet
  commitmentRoot: []byte
}

头部

GRANDPA 客户端头部包括高度、承诺根、区块证明以及权威集。（实际上，这里给出的是权威集证明而不是权威集本身，但我们可以使用固定键来验证该证明并提取真实集合，此处忽略具体细节。）

interface Header {
  height: uint64
  commitmentRoot: []byte
  justification: Justification
  authoritySet: AuthoritySet
}

证明

区块最终性的 GRANDPA 证明，其中包括一条提交消息，以及一份祖先证明，其中包含把所有预提交目标区块追溯到提交目标区块所需的全部头部。例如，最新区块为 A - B - C - D - E - F，其中 A 是最后一个已终局化的区块，F 是可以收集到多数投票的位置（它们可能投给 B、C、D、E、F）。那么该证明需要包含从 F 回溯到 A 的所有头部。

interface Justification {
  round: uint64
  commit: Commit
  votesAncestries: []Header
}

提交

一条提交消息，它是带签名预提交的聚合。

interface Commit {
  precommits: []SignedPrecommit
}

interface SignedPrecommit {
  targetHash: Hash
  signature: Signature
  id: AuthorityId
}

拜占庭行为

Misbehaviour 类型用于检测不当行为，并在适用时冻结客户端，以阻止后续数据包流转。 GRANDPA 客户端的 Misbehaviour 由同一高度上的两个头部组成，且轻客户端都会认为它们有效。

interface Misbehaviour {
  fromHeight: uint64
  h1: Header
  h2: Header
}

客户端初始化

GRANDPA 客户端初始化需要一个（主观选择的）最新共识状态，其中包括完整的权威集。

function initialise(identifier: Identifier, height: uint64, consensusState: ConsensusState): ClientState {
    set("clients/{identifier}/consensusStates/{height}", consensusState)
    return ClientState{
      latestHeight: height,
      frozenHeight: null,
    }
}

GRANDPA 客户端的 latestClientHeight 函数返回最新存储的高度，并且每次验证新的（更高的）头部后都会更新该高度。

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

有效性判定

GRANDPA 客户端的有效性检查会验证某个头部是否由当前权威集签名，并验证权威集证明，以确定权威集是否发生了预期变更。如果所提供的头部有效，则更新客户端状态，并将新验证的承诺写入存储。

function checkValidityAndUpdateState(
  clientState: ClientState,
  header: Header) {
    // assert header height is newer than any we know
    assert(header.height > clientState.latestHeight)
    consensusState = get("clients/{identifier}/consensusStates/{clientState.latestHeight}")
    // verify that the provided header is valid
    assert(verify(consensusState.authoritySet, header))
    // update latest height
    clientState.latestHeight = header.height
    // create recorded consensus state, save it
    consensusState = ConsensusState{header.authoritySet, header.commitmentRoot}
    set("clients/{identifier}/consensusStates/{header.height}", consensusState)
    // save the client
    set("clients/{identifier}", clientState)
}

function verify(
  authoritySet: AuthoritySet,
  header: Header): boolean {
  let visitedHashes: Hash[]
  for (const signedPrecommit of Header.justification.commit.precommits) {
    if (checkSignature(authoritySet, signedPrecommit)) {
      visitedHashes.push(signedPrecommit.targetHash)
    }
  }
  return visitedHashes.equals(Header.justification.votesAncestries.map(hash))
}

拜占庭行为判定

GRANDPA 客户端的拜占庭行为检查用于判断同一高度上的两个冲突头部是否都能说服轻客户端。

function checkMisbehaviourAndUpdateState(
  clientState: ClientState,
  misbehaviour: 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)
    // fetch the previously verified commitment root & authority set
    consensusState = get("clients/{identifier}/consensusStates/{misbehaviour.fromHeight}")
    // check if the light client "would have been fooled"
    assert(
      verify(consensusState.authoritySet, misbehaviour.h1) &&
      verify(consensusState.authoritySet, misbehaviour.h2)
      )
    // set the frozen height
    clientState.frozenHeight = min(clientState.frozenHeight, misbehaviour.h1.height) // which is same as h2.height
    // save the client
    set("clients/{identifier}", clientState)
}

状态验证函数

GRANDPA 客户端状态验证函数会根据先前已验证的承诺根检查 Merkle 证明。

function verifyClientConsensusState(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  clientIdentifier: Identifier,
  consensusStateHeight: uint64,
  consensusState: ConsensusState) {
    path = applyPrefix(prefix, "clients/{clientIdentifier}/consensusState/{consensusStateHeight}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided consensus state has been stored
    assert(root.verifyMembership(path, consensusState, proof))
}

function verifyConnectionState(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  connectionIdentifier: Identifier,
  connectionEnd: ConnectionEnd) {
    path = applyPrefix(prefix, "connections/{connectionIdentifier}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided connection end has been stored
    assert(root.verifyMembership(path, connectionEnd, proof))
}

function verifyChannelState(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  channelEnd: ChannelEnd) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided channel end has been stored
    assert(root.verifyMembership(path, channelEnd, proof))
}

function verifyPacketData(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  sequence: uint64,
  data: bytes) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/packets/{sequence}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided commitment has been stored
    assert(root.verifyMembership(path, hash(data), proof))
}

function verifyPacketAcknowledgement(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  sequence: uint64,
  acknowledgement: bytes) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/acknowledgements/{sequence}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided acknowledgement has been stored
    assert(root.verifyMembership(path, hash(acknowledgement), proof))
}

function verifyPacketReceiptAbsence(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  sequence: uint64) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/acknowledgements/{sequence}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that no acknowledgement has been stored
    assert(root.verifyNonMembership(path, proof))
}

function verifyNextSequenceRecv(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  nextSequenceRecv: uint64) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/nextSequenceRecv")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the nextSequenceRecv is as claimed
    assert(root.verifyMembership(path, nextSequenceRecv, proof))
}

属性与不变量

由 GRANDPA 轻客户端算法提供的正确性保证。

向后兼容性

不适用。

向前兼容性

不适用。对客户端验证算法的修改将需要新的客户端标准。

示例实现

暂无。

历史

2020 年 3 月 15 日 - 初始版本

版权

此处所有内容均基于 Apache 2.0 许可发布。

Synopsis

This specification document describes a client (verification algorithm) for a blockchain using GRANDPA. GRANDPA (GHOST-based Recursive Ancestor Deriving Prefix Agreement) is a finality gadget that will be used by the Polkadot relay chain. It now has a Rust implementation and is part of the Substrate, so likely blockchains built using Substrate will use GRANDPA as its finality gadget.

Motivation

Blockchains using GRANDPA finality gadget might like to interface with other replicated state machines or solo machines over IBC.

Definitions

Functions & terms are as defined in ICS 2.

Desired Properties

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

Technical Specification

This specification depends on correct instantiation of the GRANDPA finality gadget and its light client algorithm.

Client state

The GRANDPA client state tracks latest height and a possible frozen height.

interface ClientState {
  latestHeight: uint64
  frozenHeight: Maybe<uint64>
}

Authority set

A set of authorities for GRANDPA.

interface AuthoritySet {
  // this is incremented every time the set changes
  setId: uint64
  authorities: List<Pair<AuthorityId, AuthorityWeight>>
}

Consensus state

The GRANDPA client tracks authority set and commitment root for all previously verified consensus states.

interface ConsensusState {
  authoritySet: AuthoritySet
  commitmentRoot: []byte
}

Headers

The GRANDPA client headers include the height, the commitment root, a justification of block and authority set. (In fact, here is a proof of authority set rather than the authority set itself, but we can use a fixed key to verify the proof and extract the real set, the details are ignored here)

interface Header {
  height: uint64
  commitmentRoot: []byte
  justification: Justification
  authoritySet: AuthoritySet
}

Justification

A GRANDPA justification for block finality, it includes a commit message and an ancestry proof including all headers routing all precommit target blocks to the commit target block. For example, the latest blocks are A - B - C - D - E - F, where A is the last finalised block, F is the point where a majority for vote (they may on B, C, D, E, F) can be collected. Then the proof needs to include all headers from F back to A.

interface Justification {
  round: uint64
  commit: Commit
  votesAncestries: []Header
}

Commit

A commit message which is an aggregate of signed precommits.

interface Commit {
  precommits: []SignedPrecommit
}

interface SignedPrecommit {
  targetHash: Hash
  signature: Signature
  id: AuthorityId
}

Misbehaviour

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

interface Misbehaviour {
  fromHeight: uint64
  h1: Header
  h2: Header
}

Client initialisation

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

function initialise(identifier: Identifier, height: uint64, consensusState: ConsensusState): ClientState {
    set("clients/{identifier}/consensusStates/{height}", consensusState)
    return ClientState{
      latestHeight: height,
      frozenHeight: null,
    }
}

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

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

Validity predicate

GRANDPA client validity checking verifies a header is signed by the current authority set and verifies the authority set proof to determine if there is an expected change to the authority set. If the provided header is valid, the client state is updated & the newly verified commitment written to the store.

function checkValidityAndUpdateState(
  clientState: ClientState,
  header: Header) {
    // assert header height is newer than any we know
    assert(header.height > clientState.latestHeight)
    consensusState = get("clients/{identifier}/consensusStates/{clientState.latestHeight}")
    // verify that the provided header is valid
    assert(verify(consensusState.authoritySet, header))
    // update latest height
    clientState.latestHeight = header.height
    // create recorded consensus state, save it
    consensusState = ConsensusState{header.authoritySet, header.commitmentRoot}
    set("clients/{identifier}/consensusStates/{header.height}", consensusState)
    // save the client
    set("clients/{identifier}", clientState)
}

function verify(
  authoritySet: AuthoritySet,
  header: Header): boolean {
  let visitedHashes: Hash[]
  for (const signedPrecommit of Header.justification.commit.precommits) {
    if (checkSignature(authoritySet, signedPrecommit)) {
      visitedHashes.push(signedPrecommit.targetHash)
    }
  }
  return visitedHashes.equals(Header.justification.votesAncestries.map(hash))
}

Misbehaviour predicate

GRANDPA client misbehaviour checking determines whether or not two conflicting headers at the same height would have convinced the light client.

function checkMisbehaviourAndUpdateState(
  clientState: ClientState,
  misbehaviour: 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)
    // fetch the previously verified commitment root & authority set
    consensusState = get("clients/{identifier}/consensusStates/{misbehaviour.fromHeight}")
    // check if the light client "would have been fooled"
    assert(
      verify(consensusState.authoritySet, misbehaviour.h1) &&
      verify(consensusState.authoritySet, misbehaviour.h2)
      )
    // set the frozen height
    clientState.frozenHeight = min(clientState.frozenHeight, misbehaviour.h1.height) // which is same as h2.height
    // save the client
    set("clients/{identifier}", clientState)
}

State verification functions

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

function verifyClientConsensusState(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  clientIdentifier: Identifier,
  consensusStateHeight: uint64,
  consensusState: ConsensusState) {
    path = applyPrefix(prefix, "clients/{clientIdentifier}/consensusState/{consensusStateHeight}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided consensus state has been stored
    assert(root.verifyMembership(path, consensusState, proof))
}

function verifyConnectionState(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  connectionIdentifier: Identifier,
  connectionEnd: ConnectionEnd) {
    path = applyPrefix(prefix, "connections/{connectionIdentifier}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided connection end has been stored
    assert(root.verifyMembership(path, connectionEnd, proof))
}

function verifyChannelState(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  channelEnd: ChannelEnd) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided channel end has been stored
    assert(root.verifyMembership(path, channelEnd, proof))
}

function verifyPacketData(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  sequence: uint64,
  data: bytes) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/packets/{sequence}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided commitment has been stored
    assert(root.verifyMembership(path, hash(data), proof))
}

function verifyPacketAcknowledgement(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  sequence: uint64,
  acknowledgement: bytes) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/acknowledgements/{sequence}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the provided acknowledgement has been stored
    assert(root.verifyMembership(path, hash(acknowledgement), proof))
}

function verifyPacketReceiptAbsence(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  sequence: uint64) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/acknowledgements/{sequence}")
    // 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/{identifier}/consensusStates/{height}")
    // verify that no acknowledgement has been stored
    assert(root.verifyNonMembership(path, proof))
}

function verifyNextSequenceRecv(
  clientState: ClientState,
  height: uint64,
  prefix: CommitmentPrefix,
  proof: CommitmentProof,
  portIdentifier: Identifier,
  channelIdentifier: Identifier,
  nextSequenceRecv: uint64) {
    path = applyPrefix(prefix, "ports/{portIdentifier}/channels/{channelIdentifier}/nextSequenceRecv")
    // 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/{identifier}/consensusStates/{height}")
    // verify that the nextSequenceRecv is as claimed
    assert(root.verifyMembership(path, nextSequenceRecv, proof))
}

Properties & Invariants

Correctness guarantees as provided by the GRANDPA light client algorithm.

Backwards Compatibility

Not applicable.

Forwards Compatibility

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

Example Implementations

None yet.

History

March 15, 2020 - Initial version

Copyright

All content herein is licensed under Apache 2.0.

​概述

​动机

​定义

​期望属性

​技术规范

​客户端状态

​权威集

​共识状态

​头部

​证明

​提交

​拜占庭行为

​客户端初始化

​有效性判定

​拜占庭行为判定

​状态验证函数

​属性与不变量

​向后兼容性

​向前兼容性

​示例实现

​历史

​版权

​Synopsis

​Motivation

​Definitions

​Desired Properties

​Technical Specification

​Client state

​Authority set

​Consensus state

​Headers

​Justification

​Commit

​Misbehaviour

​Client initialisation

​Validity predicate

​Misbehaviour predicate

​State verification functions

​Properties & Invariants

​Backwards Compatibility

​Forwards Compatibility

​Example Implementations

​History

​Copyright

概述

动机

定义