qgb

x/qgb

Concepts

This module contains the Quantum Gravity Bridge (QGB) state machine implementation.

The QGB state machine is responsible for creating attestations which are signed by orchestrators, and submitted to EVM chains by relayers.

Attestations types

Attestations are requests for signatures generated by the state machine during the EndBlock phase. They facilitate alignment between orchestrators and relayers on which data to sign, and when to relay it.

There are two types of attestations, valsets and data commitments.

Valsets

A valset is an attestation type representing a validator set change. It allows for the validator set to change over heights which in turn defines which orchestrator should sign the attestations.

When an orchestrator sees a newly generated valset published by the Celestia state machine, it queries the previous valset and checks whether it's part of its validator set. Then, the orchestrator signs the new valset and submits that signature to the QGB P2P network. Otherwise, it ignores it and waits for new attestations.

A valset is comprised of the following fields:

// Valset is the EVM Bridge Multsig Set, each qgb validator also
// maintains an ETH key to sign messages, these are used to check signatures on
// ETH because of the significant gas savings
message Valset {
  option (cosmos_proto.implements_interface) = "AttestationRequestI";
  // Universal nonce defined under:
  // https://github.com/celestiaorg/celestia-app/pull/464
  uint64 nonce = 1;
  // List of BridgeValidator containing the current validator set.
  repeated BridgeValidator members = 2 [ (gogoproto.nullable) = false ];
  // Current chain height
  uint64 height = 3;
  // Block time where this valset was created
  google.protobuf.Timestamp time = 4
      [ (gogoproto.nullable) = false, (gogoproto.stdtime) = true ];
}

With BridgeValidator representing a validator EVM address and its power:

// BridgeValidator represents a validator's ETH address and its power
message BridgeValidator {
  // Voting power of the validator.
  uint64 power = 1;
  // EVM address that will be used by the validator to sign messages.
  string evm_address = 2;
}

1. nonce: is the universal nonce of the attestation. It is used to prevent front running attacks in the QGB smart contract. More details can be found in ADR-004.
2. members: contains the current validator set.
3. height: is the height at which the valset was created.
4. time: is the timestamp of the height at which the valset was created.

Validator power normalization

The QGB bridge power is obtained by normalizing the validators' voting power using the min-max normalization formula. This formula takes into account the ratio of each validator's voting power to the total voting power in the block and scales it to a value between 0 and 2^32.

By normalizing the voting power, we can significantly reduce the frequency of generating new validator set updates. For example, if there is a small increase in the total on-chain voting power due to inflation, there is no need to create a new validator set. This is because the relative proportions of the validators remain the same, and the normalized QGB power doesn't show any significant difference.

To ensure that the normalization process doesn't encounter overflow errors, the function normalizeValidatorPower uses BigInt operations. It scales the raw power value with respect to the total validator power, making sure the result falls within the range of 0 to 2^32.

This mechanism allows to increase/decrease the frequency at which validator set updates get created via increasing/decreasing the value of the SignificantPowerDifferenceThreshold constant (more details on it below).

Power diff

PowerDiff(...) is a function that calculates the difference in power between two sets of bridge validators. It's important to note that the power being compared is not the regular voting power in the Celestia consensus network, but a specific type called QGB bridge power (explained above).

Data commitments

A data commitment is an attestation type representing a request to commit over a set of blocks. It provides an end exclusive range of blocks for orchestrators to sign over and propagate in the QGB P2P network. The range is defined by the param DataCommitmentWindow, more on this below.

When an orchestrator sees a newly generated data commitment, it queries the previous valset and checks whether it's part of its validator set. Then, the orchestrator signs the new data commitment and submits that signature to the QGB P2P network. Otherwise, it ignores it and waits for new attestations.

A data commitment is comprised of the following fields:

// DataCommitment is the data commitment request message that will be signed
// using orchestrators.
// It does not contain a `commitment` field as this message will be created
// inside the state machine and it doesn't make sense to ask tendermint for the
// commitment there.
// The range defined by begin_block and end_block is end exclusive.
message DataCommitment {
  option (cosmos_proto.implements_interface) = "AttestationRequestI";
  // Universal nonce defined under:
  // https://github.com/celestiaorg/celestia-app/pull/464
  uint64 nonce = 1;
  // First block defining the ordered set of blocks used to create the
  // commitment.
  uint64 begin_block = 2;
  // End exclusive last block defining the ordered set of blocks used to create
  // the commitment.
  uint64 end_block = 3;
  // Block time where this data commitment was created
  google.protobuf.Timestamp time = 4
      [ (gogoproto.nullable) = false, (gogoproto.stdtime) = true ];
}

1. nonce: is the universal nonce of the attestation. It is used to prevent front running attacks in the QGB smart contract. More details can be found in ADR-004.
2. begin_block: the data commitment range first block.
3. end_block: the data commitment range last block. The range is end exclusive. Thus, the commitment will be over the set of blocks defined by [begin_block, end_block).
4. time: is the timestamp of the height at which the data commitment was created.

A commitment, aka DataRootTupleRoot, is an RFC-6962 merkle tree commitment over the set of DataRootTuples defined by a data commitment range.

A data root tuple contains the following fields:

/// @notice A tuple of data root with metadata. Each data root is associated
///  with a Celestia block height.
/// @dev `availableDataRoot` in
///  https://github.com/celestiaorg/celestia-specs/blob/master/src/specs/data_structures.md#header
struct DataRootTuple {
    // Celestia block height the data root was included in.
    // Genesis block is height = 0.
    // First queryable block is height = 1.
    uint256 height;
    // Data root.
    bytes32 dataRoot;
    // Celestia block original square size.
    uint256 squareSize;
}

1. height: the height of the block.
2. dataRoot: the data root, aka data hash, of the block.
3. squareSize: the square size of the block.

These commitments are queried by orchestrators from Celestia-core, signed, then submitted to the QGB P2P network as described here.

State

Attestations

Both types of attestations are set using the SetAttestationRequest(...) method and retrieved using the GetAttestationByNonce(...) method.

Latest attestation nonce

The latest attestation nonce represents the most recently generated nonce in the QGB state machine store. It is initialized to 0 in genesis, and gets incremented at block 1.

The latest attestation nonce can be set to the QGB state machine store using the SetLatestAttestationNonce(...) method and retrieved using the GetLatestAttestationNonce(...).

To check if the latest attestation nonce is defined in store, use the CheckLatestAttestationNonce(...) method.

Latest unbonding height

The latest unbonding height indicates the most recent height at which some validator started unbdonding. It is not initialized in genesis, and the keeper getter GetLatestUnBondingBlockHeight(...) returns 0 if the value is still not defined.

The latest unbonding height can be set to the QGB state machine store using the SetLatestUnBondingBlockHeight(...) method, and it is called in a hook when a validator starts unbonding. More details on hooks are below.

Earliest attestation nonce

The earliest attestation nonce corresponds to the nonce of the earliest generated attestation in the QGB state machine store. It is initialized to 1 in genesis, and gets incremented updated when pruning.

The earliest attestation nonce can be set to the QGB state machine store using the SetEarliestAvailableAttestationNonce(...) method, and retrieved using the GetEarliestAvailableAttestationNonce(...).

To check if the earliest attestation nonce is defined in store, use the CheckEarliestAvailableAttestationNonce(...) method.

State Transitions

End Block

During the EndBlock step, we're executing the logic that handles the generating new valsets, new data commitments, and prunes when needed.

Valset handler

A new valset is generated by the valset handler in the following cases:

No valset in store

When EndBlock is executed straight after genesis, the store doesn't have any valset created yet. So, it checks wether there is any valset in store, and generates a new one afterwards representing the initial validator set.

Validator starts unbonding

When a validator starts unbonding, the LatestUnbondingBlockHeight gets updated in a hook with the current block number. Then, inside EndBlock, we check whether the LatestUnbondingBlockHeight corresponds to the current block height. If so, then we generate a new valset that doesn't contain that unbonding validator.

Significant power change

The third scenario where a valset gets created is when there is a significant power change. As stated above, valsets contain an evmAddress -> power mapping for the validator sets they represent. When a significant power change happens, a new valset gets created. The significant power threshold is defined by the SignificantPowerDifferenceThreshold constant.

A significant power change can happen if a validator's delegation got reduced or increased significantly, or the powers of multiple validators changed in a way that the whole validator set variation is higher than the threshold. This calculus is done inside the PowerDiff(...) method.

Data commitment handler

The data commitment handler generates a new data commitment when a sufficient number of blocks have passed since the previous one.

The ranges of blocks, for which new data commitments are generated, are defined via the DataCommitmentWindow param. This latter is initialized in genesis and can be updated via governance votes or upgrades.

The data commitment window ranges from a minimum defined by MinimumDataCommitmentWindow to a maximum specified by the DataCommitmentBlocksLimit. This range is validated when initializing the DataCommitmentWindow value or when updating it via the validateDataCommitmentWindow method.

After a range update, the handler tries to generate any needed data commitment to catchup to the current height. An example of how these ranges are created can be found in tests. Thus, in the same height, multiple data commitments can be generated and added to the store.

Pruning

The third action done during the QGB EndBlock step is pruning.

The QGB state machine prunes old attestations up to the specified AttestationExpiryTime, which is currently set to 3 weeks, matching the consensus unbonding time.

So, on every block height, the state machine checks whether there are any expired attestations. Then, it starts pruning via calling the DeleteAttestation(...) method. Then, it prints a log message specifying the number of pruned attestations.

If the all the attestations in store are expired, which is an edge case that should never occur, the QGB state machine doesn't prune the latest attestation.

Hooks

Validator unbonding hook

When a validator starts unbonding, a hook is executed that sets the LatestUnBondingBlockHeight to the current block height. This allows creating a new valset that removes that validator from the valset members so that he doesn't need to sign attestations afterwards.

Events

New attestation event

After creating a new attestation, and adding it to the QGB store, an event is emitted containing its nonce.

Client

Query attestation command

The QGB query attestation command is part of the celestia-appd binary. It allows the user to query specific attestations by their corresponding nonce.

$ celestia-appd query qgb attestation --help
query an attestation by nonce

Usage:
  celestia-appd query qgb attestation <nonce> [flags]

Aliases:
  attestation, att

Verification command

The QGB verification command is part of the celestia-appd binary. It allows the user to verify that a set of shares has been posted to a specific QGB contract.

$ celestia-appd verify --help

Verifies that a transaction hash, a range of shares, or a blob referenced by its transaction hash were committed to by the QGB contract

Usage:
  celestia-appd verify [command]

Available Commands:
  blob        Verifies that a blob, referenced by its transaction hash, in hex format, has been committed to by the QGB contract.
  shares      Verifies that a range of shares has been committed to by the QGB contract
  tx          Verifies that a transaction hash, in hex format, has been committed to by the QGB contract

Flags:
  -h, --help   help for verify

Use "celestia-appd verify [command] --help" for more information about a command.

It currently supports three sub-commands:

• blob: Takes a transaction hash, in hex format, and verifies that the blob paid for by the transaction has been committed to by the QGB contract. It only supports one blob for now.
• shares: Takes a range of shares and a height, and verifies that these shares have been committed to by the QGB contract.
• tx: Takes a transaction hash, in hex format, and verifies that it has been committed to by the QGB contract.

Params

Data commitment window

The data commitment window, which is explained above, is defined as a parameter in here.

This param is validated using the validateDataCommitmentWindow(...) method.

Panics

During EndBlock step, the state machine generates new attestations if needed. During this generation, the state machine could panic.

Valset panics

When checking if the state machine needs to generate a new valset, the state machine might panic if it finds invalid state. This can happen in the following cases:

• When checking that a previous valset has been emitted, but it is unable to get it:

if k.CheckLatestAttestationNonce(ctx) && k.GetLatestAttestationNonce(ctx) != 0 {
   var err error
   latestValset, err = k.GetLatestValset(ctx)
   if err != nil {
      panic(err)
   }
}

• When getting the current valset:

vs, err := k.GetCurrentValset(ctx)
if err != nil {
   // this condition should only occur in the simulator
   // ref : https://github.com/Gravity-Bridge/Gravity-Bridge/issues/35
   if errors.Is(err, types.ErrNoValidators) {
      ctx.Logger().Error("no bonded validators",
         "cause", err.Error(),
      )
      return
   }
   panic(err)
}

• When creating the internal validator struct, i.e. mapping the validators EVM addresses to their powers:

intLatestMembers, err := types.BridgeValidators(latestValset.Members).ToInternal()
if err != nil {
   panic(sdkerrors.Wrap(err, "invalid latest valset members"))
}

Attestations panics

When storing a new attestation, the state machine can panic if it finds invalid state. This latter can happen in the following cases:

• The attestation request created is a duplicate of an existing attestation:

key := []byte(types.GetAttestationKey(nonce))
store := ctx.KVStore(k.storeKey)

if store.Has(key) {
   panic("trying to overwrite existing attestation request")
}

• An error happened while marshalling the interface:

b, err := k.cdc.MarshalInterface(at)
if err != nil {
   panic(err)
}

• The universal nonce wasn't incremented correctly by 1:

if k.CheckLatestAttestationNonce(ctx) && k.GetLatestAttestationNonce(ctx)+1 != nonce {
   panic("not incrementing latest attestation nonce correctly")
}

Hooks initialization panic

When initializing the QGB hooks, if the QGB store key is not setup correctly, the state machine will panic:

// if startup is mis-ordered in app.go this hook will halt the chain when
// called. Keep this check to make such a mistake obvious
if k.storeKey == nil {
   panic("hooks initialized before QGBKeeper")
}

Appendix

The smart contract implementation is in quantum-gravity-bridge.

The orchestrator and relayer implementations are in the orchestrator-relayer repo.

QGB ADRs are in the docs.