warp

README

Avalanche Warp Messaging

Avalanche Warp Messaging (AWM) provides a primitive for cross-subnet communication on the Avalanche Network.

The Avalanche P-Chain provides an index of every Subnet's validator set on the Avalanche Network, including the BLS public key of each validator (as of the Banff Upgrade). AWM utilizes the weighted validator sets stored on the P-Chain to build a cross-subnet communication protocol between any two Subnets on the Avalanche Network.

Any Virtual Machine (VM) on Avalanche can integrate Avalanche Warp Messaging to send and receive messages across Avalanche Subnets.

Background

This README assumes familiarity with:

• Avalanche P-Chain / PlatformVM
• ProposerVM
• Basic familiarity with BLS Multi-Signatures

BLS Multi-Signatures with Public-Key Aggregation

Avalanche Warp Messaging utilizes BLS multi-signatures with public key aggregation in order to verify messages signed by another Subnet. When a validator joins a Subnet, the P-Chain records the validator's BLS public key and NodeID, as well as a proof of possession of the validator's BLS private key to defend against rogue public-key attacks.

AWM utilizes the validator set's weights and public keys to verify that an aggregate signature has sufficient weight signing the message from the source Subnet.

BLS provides a way to aggregate signatures off chain into a single signature that can be efficiently verified on chain.

AWM Serialization

Unsigned Message:

+-----------------+----------+--------------------------+
|      network_id :  uint32  |                 4 bytes  |
+-----------------+----------+--------------------------+
| source_chain_id : [32]byte |                32 bytes  |
+-----------------+----------+--------------------------+
|         payload :   []byte |       4 + size(payload)  |
+-----------------+----------+--------------------------+
                             |  40 + size(payload) bytes|
                             +--------------------------+

• networkID is the unique ID of an Avalanche Network (Mainnet/Testnet) and provides replay protection for BLS Signers across different Avalanche Networks
• sourceChainID is the hash of the transaction that created the blockchain on the Avalanche P-Chain. It serves as the unique identifier for the blockchain across the Avalanche Network so that each blockchain can only sign a message with its own id.
• payload provides an arbitrary byte array containing the contents of the message. VMs define their own message types to include in the payload

BitSetSignature:

+-----------+----------+---------------------------+
|   type_id :   uint32 |                   4 bytes |
+-----------+----------+---------------------------+
|   signers :   []byte |          4 + len(signers) |
+-----------+----------+---------------------------+
| signature : [96]byte |                  96 bytes |
+-----------+----------+---------------------------+
                       | 104 + size(signers) bytes |
                       +---------------------------+

• typeID is the ID of this signature type, which is 0x00000000
• signers encodes a bitset of which validators' signatures are included (a bitset is a byte array where each bit indicates membership of the element at that index in the set)
• signature is an aggregated BLS Multi-Signature of the Unsigned Message

BitSetSignatures are verified within the context of a specific P-Chain height. At any given P-Chain height, the PlatformVM serves a canonically ordered validator set for the source subnet (validator set is ordered lexicographically by the BLS public key's byte representation). The signers bitset encodes which validator signatures were included. A value of 1 at index i in signers bitset indicates that a corresponding signature from the same validator at index i in the canonical validator set was included in the aggregate signature.

The bitset tells the verifier which BLS public keys should be aggregated to verify the warp message.

Signed Message:

+------------------+------------------+-------------------------------------------------+
| unsigned_message :  UnsignedMessage |                          size(unsigned_message) |
+------------------+------------------+-------------------------------------------------+
|        signature :        Signature |                                 size(signature) |
+------------------+------------------+-------------------------------------------------+
                                      |  size(unsigned_message) + size(signature) bytes |
                                      +-------------------------------------------------+

Sending an Avalanche Warp Message

A blockchain on Avalanche sends an Avalanche Warp Message by coming to agreement on the message that every validator should be willing to sign. As an example, the VM of a blockchain may define that once a block is accepted, the VM should be willing to sign a message including the block hash in the payload to attest to any other Subnet that the block was accepted. The contents of the payload, how to aggregate the signature (VM-to-VM communication, off-chain relayer, etc.), is left to the VM.

Once the validator set of a blockchain is willing to sign an arbitrary message M, an aggregator performs the following process:

1. Gather signatures of the message M from N validators (where the N validators meet the required threshold of stake on the destination chain)
2. Aggregate the N signatures into a multi-signature
3. Look up the canonical validator set at the P-Chain height where the message will be verified
4. Encode the selection of the N validators included in the signature in a bitset
5. Construct the signed message from the aggregate signature, bitset, and original unsigned message

Verifying / Receiving an Avalanche Warp Message

Avalanache Warp Messages are verified within the context of a specific P-Chain height included in the ProposerVM's header. The P-Chain height is provided as context to the underlying VM when verifying the underlying VM's blocks (implemented by the optional interface WithVerifyContext).

To verify the message, the underlying VM utilizes this warp package to perform the following steps:

1. Lookup the canonical validator set of the Subnet sending the message at the P-Chain height
2. Filter the canonical validator set to only the validators claimed by the signature
3. Verify the weight of the included validators meets the required threshold defined by the receiving VM
4. Aggregate the public keys of the claimed validators into a single aggregate public key
5. Verify the aggregate signature of the unsigned message against the aggregate public key

Once a message is verified, it is left to the VM to define the semantics of delivering a verified message.

Design Considerations

Processing Historical Avalanche Warp Messages

Verifying an Avalanche Warp Message requires a lookup of validator sets at a specific P-Chain height. The P-Chain serves lookups maintaining validator set diffs that can be applied in-order to reconstruct the validator set of any Subnet at any height.

As the P-Chain grows, the number of validator set diffs that needs to be applied in order to reconstruct the validator set needed to verify an Avalanche Warp Messages increases over time.

Therefore, in order to support verifying historical Avalanche Warp Messages, VMs should provide a mechanism to determine whether an Avalanche Warp Message was treated as valid or invalid within a historical block.

When nodes bootstrap in the future, they bootstrap blocks that have already been marked as accepted by the network, so they can assume the block was verified by the validators of the network when it was first accepted.

Therefore, the new bootstrapping node can assume the block was valid to determine whether an Avalanche Warp Message should be treated as valid/invalid within the execution of that block.

Two strategies to provide that mechanism are:

• Require warp message validity for transaction inclusion. If the transaction is included, the warp message must have passed verification.
• Include the results of warp message verification in the block itself. Use the results to determine which messages passed verification.

Documentation

Index

• Variables
• func AggregatePublicKeys(vdrs []*Validator) (*bls.PublicKey, error)
• func SumWeight(vdrs []*Validator) (uint64, error)
• func TestSignerVerifies(t *testing.T, s Signer, sk *bls.SecretKey, networkID uint32, chainID ids.ID)
• func TestSignerWrongChainID(t *testing.T, s Signer, _ *bls.SecretKey, _ uint32, _ ids.ID)
• func TestSignerWrongNetworkID(t *testing.T, s Signer, _ *bls.SecretKey, networkID uint32, ...)
• func VerifyWeight(sigWeight uint64, totalWeight uint64, quorumNum uint64, quorumDen uint64) error
• type BitSetSignature
  • func (s *BitSetSignature) NumSigners() (int, error)
  • func (s *BitSetSignature) Verify(ctx context.Context, msg *UnsignedMessage, networkID uint32, ...) error
• type Message
  • func NewMessage(unsignedMsg *UnsignedMessage, signature Signature) (*Message, error)
  • func ParseMessage(b []byte) (*Message, error)
  • func (m *Message) Bytes() []byte
  • func (m *Message) Initialize() error
• type Signature
• type Signer
  • func NewSigner(sk *bls.SecretKey, networkID uint32, chainID ids.ID) Signer
• type UnsignedMessage
  • func NewUnsignedMessage(networkID uint32, sourceChainID ids.ID, payload []byte) (*UnsignedMessage, error)
  • func ParseUnsignedMessage(b []byte) (*UnsignedMessage, error)
  • func (m *UnsignedMessage) Bytes() []byte
  • func (m *UnsignedMessage) ID() ids.ID
  • func (m *UnsignedMessage) Initialize() error
• type Validator
  • func FilterValidators(indices set.Bits, vdrs []*Validator) ([]*Validator, error)
  • func GetCanonicalValidatorSet(ctx context.Context, pChainState ValidatorState, pChainHeight uint64, ...) ([]*Validator, uint64, error)
  • func (v *Validator) Less(o *Validator) bool
• type ValidatorState

Variables

var (
	ErrInvalidBitSet      = errors.New("bitset is invalid")
	ErrInsufficientWeight = errors.New("signature weight is insufficient")
	ErrInvalidSignature   = errors.New("signature is invalid")
	ErrParseSignature     = errors.New("failed to parse signature")
)

var (
	ErrWrongSourceChainID = errors.New("wrong SourceChainID")
	ErrWrongNetworkID     = errors.New("wrong networkID")
)

var (
	ErrUnknownValidator = errors.New("unknown validator")
	ErrWeightOverflow   = errors.New("weight overflowed")
)

var AnycastID = ids.ID{
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
}

AnycastID is a special DestinationChainID that is used to indicate that the message is intended to be able to be received by any chain.

var SignerTests = []func(t *testing.T, s Signer, sk *bls.SecretKey, networkID uint32, chainID ids.ID){
	TestSignerWrongChainID,
	TestSignerVerifies,
}

SignerTests is a list of all signer tests

Functions

func AggregatePublicKeys

func AggregatePublicKeys(vdrs []*Validator) (*bls.PublicKey, error)

AggregatePublicKeys returns the public key of the provided validators.

Invariant: All of the public keys in [vdrs] are valid.

func SumWeight

func SumWeight(vdrs []*Validator) (uint64, error)

SumWeight returns the total weight of the provided validators.

func TestSignerVerifies

func TestSignerVerifies(t *testing.T, s Signer, sk *bls.SecretKey, networkID uint32, chainID ids.ID)

Test that a signature generated with the signer verifies correctly

func TestSignerWrongChainID

func TestSignerWrongChainID(t *testing.T, s Signer, _ *bls.SecretKey, _ uint32, _ ids.ID)

Test that using a random SourceChainID results in an error

func TestSignerWrongNetworkID

func TestSignerWrongNetworkID(t *testing.T, s Signer, _ *bls.SecretKey, networkID uint32, blockchainID ids.ID)

Test that using a different networkID results in an error

func VerifyWeight

func VerifyWeight(
	sigWeight uint64,
	totalWeight uint64,
	quorumNum uint64,
	quorumDen uint64,
) error

VerifyWeight returns [nil] if [sigWeight] is at least [quorumNum]/[quorumDen] of [totalWeight]. If [sigWeight >= totalWeight * quorumNum / quorumDen] then return [nil]

Types

type BitSetSignature

type BitSetSignature struct {
	// Signers is a big-endian byte slice encoding which validators signed this
	// message.
	Signers   []byte                 `serialize:"true"`
	Signature [bls.SignatureLen]byte `serialize:"true"`
}

func (*BitSetSignature) NumSigners

func (s *BitSetSignature) NumSigners() (int, error)

func (*BitSetSignature) Verify

func (s *BitSetSignature) Verify(
	ctx context.Context,
	msg *UnsignedMessage,
	networkID uint32,
	pChainState validators.State,
	pChainHeight uint64,
	quorumNum uint64,
	quorumDen uint64,
) error

type Message

type Message struct {
	UnsignedMessage `serialize:"true"`
	Signature       Signature `serialize:"true"`
	// contains filtered or unexported fields
}

Message defines the standard format for a Warp message.

func NewMessage

func NewMessage(
	unsignedMsg *UnsignedMessage,
	signature Signature,
) (*Message, error)

NewMessage creates a new *Message and initializes it.

func ParseMessage

func ParseMessage(b []byte) (*Message, error)

ParseMessage converts a slice of bytes into an initialized *Message.

func (*Message) Bytes

func (m *Message) Bytes() []byte

Bytes returns the binary representation of this message. It assumes that the message is initialized from either New, Parse, or an explicit call to Initialize.

func (*Message) Initialize

func (m *Message) Initialize() error

Initialize recalculates the result of Bytes(). It does not call Initialize() on the UnsignedMessage.

type Signature

type Signature interface {
	// NumSigners is the number of [bls.PublicKeys] that participated in the
	// [Signature]. This is exposed because users of these signatures typically
	// impose a verification fee that is a function of the number of
	// signers.
	NumSigners() (int, error)

	// Verify that this signature was signed by at least [quorumNum]/[quorumDen]
	// of the validators of [msg.SourceChainID] at [pChainHeight].
	//
	// Invariant: [msg] is correctly initialized.
	Verify(
		ctx context.Context,
		msg *UnsignedMessage,
		networkID uint32,
		pChainState validators.State,
		pChainHeight uint64,
		quorumNum uint64,
		quorumDen uint64,
	) error
}

type Signer

type Signer interface {
	// Returns this node's BLS signature over an unsigned message. If the caller
	// does not have the authority to sign the message, an error will be
	// returned.
	//
	// Assumes the unsigned message is correctly initialized.
	Sign(msg *UnsignedMessage) ([]byte, error)
}

func NewSigner

func NewSigner(sk *bls.SecretKey, networkID uint32, chainID ids.ID) Signer

type UnsignedMessage

type UnsignedMessage struct {
	NetworkID     uint32 `serialize:"true"`
	SourceChainID ids.ID `serialize:"true"`
	Payload       []byte `serialize:"true"`
	// contains filtered or unexported fields
}

UnsignedMessage defines the standard format for an unsigned Warp message.

func NewUnsignedMessage

func NewUnsignedMessage(
	networkID uint32,
	sourceChainID ids.ID,
	payload []byte,
) (*UnsignedMessage, error)

NewUnsignedMessage creates a new *UnsignedMessage and initializes it.

func ParseUnsignedMessage

func ParseUnsignedMessage(b []byte) (*UnsignedMessage, error)

ParseUnsignedMessage converts a slice of bytes into an initialized *UnsignedMessage.

func (*UnsignedMessage) Bytes

func (m *UnsignedMessage) Bytes() []byte

Bytes returns the binary representation of this message. It assumes that the message is initialized from either New, Parse, or an explicit call to Initialize.

func (*UnsignedMessage) ID

func (m *UnsignedMessage) ID() ids.ID

ID returns an identifier for this message. It assumes that the message is initialized from either New, Parse, or an explicit call to Initialize.

func (*UnsignedMessage) Initialize

func (m *UnsignedMessage) Initialize() error

Initialize recalculates the result of Bytes().

type Validator

type Validator struct {
	PublicKey      *bls.PublicKey
	PublicKeyBytes []byte
	Weight         uint64
	NodeIDs        []ids.NodeID
}

func FilterValidators

func FilterValidators(
	indices set.Bits,
	vdrs []*Validator,
) ([]*Validator, error)

FilterValidators returns the validators in [vdrs] whose bit is set to 1 in [indices].

Returns an error if [indices] references an unknown validator.

func GetCanonicalValidatorSet

func GetCanonicalValidatorSet(
	ctx context.Context,
	pChainState ValidatorState,
	pChainHeight uint64,
	subnetID ids.ID,
) ([]*Validator, uint64, error)

GetCanonicalValidatorSet returns the validator set of [subnetID] at [pChcainHeight] in a canonical ordering. Also returns the total weight on [subnetID].

func (*Validator) Less

func (v *Validator) Less(o *Validator) bool

type ValidatorState

type ValidatorState interface {
	GetValidatorSet(ctx context.Context, height uint64, subnetID ids.ID) (map[ids.NodeID]*validators.GetValidatorOutput, error)
}

ValidatorState defines the functions that must be implemented to get the canonical validator set for warp message validation.