Zero IBC
ics: 118 title: ZK IBC stage: draft category: IBC/TAO kind: instantiation implements: 2 version compatibility: ibc-go v7.0.0 author: Ping Liang ping@side.one created: 2023-11-22 modified: 2023-11-22
This specification document outlines a solution that implements IBC using Zero Knowledge Proof technology.
Extend IBC to non-Tendermint consensus blockchains, such as Ethereum and BSC.
-
High Gas Consumption: Implementing a ZK client for EVM requires verifying blocks signed by validators on the source blockchain. Verifying ed25519 signatures from multiple validators can exceed the EVM gas limit. ZKP offers an ideal solution.
-
Proof Size: Verification of IBC light clients involves complexities like signatures, Merkle trees, and voting power. Combining many proofs into one using recursive proof is necessary.
-
Proving Time: ZK SNARKs often take a long time to produce a proof, especially for large-scale circuits like the ed25519 circuit (2^18). GPU acceleration significantly reduces proving time.
-
ZKP Efficiency: Combining ZK STARKs and ZK SNARKs is an effective way to reduce circuit scale and enhance proving efficiency.
Functions & terms of Solidity Client 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.
Functions & terms of Relayer are as defined in ICS 18
- Minimum Trust: The process should not involve any trusted third parties.
- Low Gas Consumption: Gas required to validate the proof should be reasonably low.
- No Permissions: No specific authority is needed to run relayers or integrate.
- Time Efficiency: The time taken to produce a proof should be less than 30 seconds.
- Minimum Modification: Any changes made should not compromise the security assumptions of the cometBFT consensus or alter the underlying consensus algorithms.
- Massive Adoption: Should be adaptable to most existing IBC light clients.
The CometBFT client state tracks the current revision, hash of current validator set, total voting power, 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
}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
totalVotingPower: uint64
}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.
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
zkProof: []byte
}interface Header {
signedHeader: TendermintSignedHeader
identifier: string
trustedHeight: Height
trustedValidatorSetHash: []byte
trustedTotalVotingPower: 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.
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.
Tendermint client initialisation requires a (subjectively chosen) latest consensus state, including the full validator set.
function initialise(
identifier: Identifier,
clientState: ClientState,
consensusState: ConsensusState
) {
assert(clientState.trustingPeriod < clientState.unbondingPeriod)
assert(clientState.height > 0)
assert(clientState.trustLevel >= 1/3 && clientState.trustLevel <= 1)
provableStore.set("clients/{identifier}/clientState", clientState)
provableStore.set("clients/{identifier}/consensusStates/{height}", consensusState)
}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
}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 = provableStore.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 = provableStore.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 zk proof verify instead of tmClient.verify
assert(zkProof.verify(
header.trustedValidatorSetHash,
header.trustedTotalVotingPower, // might be 0 for non-cometBFT
clientState.latestHeight,
clientState.trustingPeriod,
clientState.maxClockDrift,
))
}Function 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): boolean {
clientState = provableStore.get("clients/{clientMsg.identifier}/clientState")
switch typeof(clientMsg) {
case Header:
// fetch consensusstate at header height if it exists
consensusState = provableStore.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.timestamp == header.timestamp &&
consensusState.commitmentRoot == header.commitmentRoot &&
consensusState.nextValidatorsHash == header.nextValidatorsHash
) {
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:
if (misbehaviour.h1.height < misbehaviour.h2.height) {
return false
}
// if heights are equal check that this is valid misbehaviour of a fork
if (misbehaviour.h1.height === misbehaviour.h2.height && misbehaviour.h1.commitmentRoot !== misbehaviour.h2.commitmentRoot) {
return true
}
// otherwise if heights are unequal check that this is valid misbehavior of BFT time violation
if (misbehaviour.h1.timestamp <= misbehaviour.h2.timestamp) {
return true
}
return false
}
}Function 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 = provableStore.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
provableStore.set("clients/{clientMsg.identifier}/clientState", clientState)
}
// create recorded consensus state, save it
consensusState = ConsensusState{header.timestamp, header.nextValidatorsHash, header.commitmentRoot}
provableStore.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
provableStore.set("clients/{clientMsg.identifier}/processedTimes/{header.GetHeight()}", currentTimestamp())
provableStore.set("clients/{clientMsg.identifier}/processedHeights/{header.GetHeight()}", currentHeight())
}Function updateStateOnMisbehaviour will set the frozen height to a non-zero sentinel height to freeze the entire client.
function updateStateOnMisbehaviour(clientMsg: clientMessage) {
clientState = provableStore.get("clients/{clientMsg.identifier}/clientState")
clientState.frozenHeight = Height{0, 1}
provableStore.set("clients/{clientMsg.identifier}/clientState", clientState)
}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: CommitmentProof
) {
// 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
// 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
consensusState = provableStore.get("clients/{clientIdentifier}/consensusStates/{height}")
// verify that the provided consensus state has been stored
assert(verifyMembership(consensusState.commitmentRoot, proof, path, newClientState))
// update client state
clientState = newClientState
provableStore.set("clients/{clientIdentifier}/clientState", clientState)
}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
): Error {
// 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
consensusState = provableStore.get("clients/{clientIdentifier}/consensusStates/{height}")
// verify that <path, value> has been stored
if !verifyMembership(consensusState.commitmentRoot, proof, path, value) {
return error
}
return nil
}
function verifyNonMembership(
clientState: ClientState,
height: Height,
delayTimePeriod: uint64,
delayBlockPeriod: uint64,
proof: CommitmentProof,
path: CommitmentPath
): Error {
// 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
consensusState = provableStore.get("clients/{clientIdentifier}/consensusStates/{height}")
// verify that nothing has been stored at path
if !verifyNonMembership(consensusState.commitmentRoot, proof, path) {
return error
}
return nil
}- Prove Validator Set
prove that the all validators must be included in header.validatorSetHash
fn run_merkle_stark(validatorHash: BigUint) -> Proof {
const D: usize = 2;
type C = PoseidonGoldilocksConfig;
type F = <C as GenericConfig<D>>::F;
type S = MerkleTreeStark<F, D>;
let validators = fetchBlockValidatorSet();
let config = StarkConfig::standard_fast_config();
let num_rows = validators.length();
let public_inputs = [F::from_noncanonical_biguint(validatorHash)];
let stark = S::new(num_rows);
let trace = stark.generate_trace(validators, public_inputs[0]);
let proof = prove::<F, C, S, D>(
stark,
&config,
trace,
public_inputs,
&mut TimingTree::default(),
)?;
return proof;
}- Prove Signatures
prove that the current block root(header.commitmentRoot) is signed by the corresponding validator set
fn run_signature_stark(commitment_root: BigUint) -> Proof {
const D: usize = 2;
type C = PoseidonGoldilocksConfig;
type F = <C as GenericConfig<D>>::F;
type S = Ed25519SignatureStark<F, D>;
let signatures = fetchBlockSignatures();
let config = StarkConfig::standard_fast_config();
let num_rows = signatures.length();
let public_inputs = [F::from_noncanonical_biguint(commitment_root)];
let stark = S::new(num_rows);
let trace = stark.generate_trace(signatures, public_inputs[0]);
let proof = prove::<F, C, S, D>(
stark,
&config,
trace,
public_inputs,
&mut TimingTree::default(),
)?;
return proof;
}- Prove Voting Power
prove that the sum of voting power of participated validators is greater than header.trustedTotalVotingPower
fn run_signature_stark(trusted_voting_power: u64) -> Proof {
const D: usize = 2;
type C = PoseidonGoldilocksConfig;
type F = <C as GenericConfig<D>>::F;
type S = Ed25519SignatureStark<F, D>;
let validators = fetchBlockValidatorSet();
let config = StarkConfig::standard_fast_config();
let num_rows = validators.length();
let public_inputs = [F::from_noncanonical_biguint(trusted_voting_power * clientState.trustLevel)]; // the minimum voting power
let stark = S::new(num_rows);
let trace = stark.generate_trace(validators, public_inputs[0]);
let proof = prove::<F, C, S, D>(
stark,
&config,
trace,
public_inputs,
&mut TimingTree::default(),
)?;
return proof;
}fn recursive_proof<
F: RichField + Extendable<D>,
C: GenericConfig<D, F = F>,
S: Stark<F, D> + Copy,
InnerC: GenericConfig<D, F = F>,
const D: usize,
>(
stark: S,
inner_proof: StarkProofWithPublicInputs<F, InnerC, D>,
inner_config: &StarkConfig,
print_gate_counts: bool,
) -> Result<()>
where
InnerC::Hasher: AlgebraicHasher<F>,
[(); S::COLUMNS]:,
[(); S::PUBLIC_INPUTS]:,
{
let circuit_config = CircuitConfig::standard_recursion_config();
let mut builder = CircuitBuilder::<F, D>::new(circuit_config);
let mut pw = PartialWitness::new();
let degree_bits = inner_proof.proof.recover_degree_bits(inner_config);
let pt = add_virtual_stark_proof_with_pis(&mut builder, stark, inner_config, degree_bits);
set_stark_proof_with_pis_target(&mut pw, &pt, &inner_proof);
verify_stark_proof_circuit::<F, InnerC, S, D>(&mut builder, stark, pt, inner_config);
if print_gate_counts {
builder.print_gate_counts(0);
}
let data = builder.build::<C>();
let proof = data.prove(pw)?;
data.verify(proof)
}In essence, the Zero Relayer aligns with the functions and terms outlined in ICS 18. However, it introduces a coordinator responsible for generating a zero-knowledge proof and relaying it alongside the corresponding packet.
- The relay algorithms in Zero Relayer remain consistent with the official specifications.
function relay(C: Set<Chain>) {
for (const chain of C)
for (const counterparty of C)
if (counterparty !== chain) {
const datagrams = chain.pendingDatagrams(counterparty)
for (const localDatagram of datagrams[0])
chain.submitDatagram(localDatagram)
for (const counterpartyDatagram of datagrams[1])
counterparty.submitDatagram(counterpartyDatagram)
}
}function pendingDatagrams(chain: Chain, counterparty: Chain): List<Set<Datagram>> {
/// ... omit official code here
// Deal with packets
// First, scan logs for sent packets and relay all of them
sentPacketLogs = queryByTopic(height, "sendPacket")
for (const logEntry of sentPacketLogs) {
// relay packet with this sequence number
packetData = Packet{logEntry.sequence, logEntry.timeoutHeight, logEntry.timeoutTimestamp,
localEnd.portIdentifier, localEnd.channelIdentifier,
remoteEnd.portIdentifier, remoteEnd.channelIdentifier, logEntry.data}
counterpartyDatagrams.push(PacketRecv{
packet: packetData,
proof: coordinator.productProof(header),
proofHeight: height,
})
}
}Not applicable.
Not applicable.
All content herein is licensed under Apache 2.0.