Avalanche

• date: 2023-02-04
• last updated: 2023-02-04

Overview

Avalanche is good candidate because it samples from a large number of validators to produce blocks, uses generic methods for signing blocks (RSA on a X.509 certificate), is moving to transition to BLS signatures for validators, and has numerous subnets.

In Avalanche, there are two types of consensus mechanisms (Avalanche, partially ordered, and Snowman, linearly ordered similar to other blockchains). Users can create arbitrary subnets in Avalanche, and any validator is free to participate the consensus for any subnet¹, besides the mandatory participation of the special subnet - the Primary Network. Each subnet has three types of chains, each with different roles and runs different consensus mechanism and process different transaction types: (1) P-Chain, which defines validator sets and process validator related transactions; (2) X-Chain, for exchanging assets, where blocks are partially ordered; (3) C-Chain, which runs an EVM and handles smart contract interactions ².

Note: On march 23rd, 2023 Avalanche published an article³ giving an overviow of the Cortina release, it's move to linearize the X-chain to enable support for WARP messaging.

We limit our scope to only the Primary Network, since any bridging implementation is likely replicable in subnets, and subnets are likely to be interoperable soon. For trustless bridging, only events from C-Chain are relevant, since the bridge must be a smart contract and all cross-chain operations can be conveniently wrapped inside contract interactions.

The active Avalanche validator set is unrestricted and permissionless, and has more than 1000 members at this time ⁴. Block proposers are randomly sampled from the active validator set, therefore any validator could potentially sign a block ⁵. The validators use X.509 (TLS)certificate to sign and verify blocks ⁶, and the block headers contain both the certificate and the signature ⁷. Neither Avalanche documentation or code specifies the key and signing algorithms for the X.509 certificate, but the certificate auto-generated by the code (invoked via validator command-line tools) creates 4096-bit RSA key by default ⁸.

In recent releases^{9 10 11 12 13 14} of Avalanche, validators may also load or generate an optional BLS key. This is to support Avalanche Warp Messaging (AWM) ^{15 16} supporting inter-subnet messaging. This suggests the protocol may replace its signature scheme from RSA to BLS in the near future.

Note that RSA signature can be cheaply verified on-chain, per EIP-198 ¹⁷ . Solidity libraries ¹⁸ are also available for RSA signature verification. In the worst case, even if any validator chooses to use a non-RSA custom-made certificate, most of the signing algorithms (ECDSA, EDDSA) supported by chosen crypto library in Go can also be verified on-chain.

Consensus Mechanisms

There are two main consensus algorithms: Avalanche and Snowman. As stated above our focus is bridging from the C-Chain (contract(C) Chain) which uses Snowman Consensus.

Avalanche Primary Network

Avalanche is a network of blockchains¹⁹, this diagram gives an overview of the avalanche primiary network.

Avalanche Consensus

Following is an excerpt from the Avalanche Consensus Whitepaper ²⁰, it is also recommended reviewing Avalanche Blockchain Consensus Documentation ²¹.

This paper introduces a family of leaderless Byzantine fault tolerance protocols, built around a metastable mechanism via network subsampling. These protocols provide a strong probabilistic safety guarantee in the presence of Byzantine adversaries while their concurrent and leaderless nature enables them to achieve high throughput and scalability. Unlike blockchains that rely on proof-of-work, they are quiescent and green. Unlike traditional consensus protocols where one or more nodes typically process linear bits in the number of total nodes per decision, no node processes more than logarithmic bits. It does not require accurate knowledge of all participants and exposes new possible tradeoffs and improvements in safety and liveness for building consensus protocols.

The paper describes the Snow protocol family, analyzes its guarantees, and describes how it can be used to construct the core of an internet-scale electronic payment system called Avalanche, which is evaluated in a large scale deployment. Experiments demonstrate that the system can achieve high throughput (3400 tps), provide low confirmation latency (1.35 sec), and scale well compared to existing systems that deliver similar functionality. For our implementation and setup, the bottleneck of the system is in transaction verification.

Snowman Consensus

Snowman consensus is one of the consensus mechanisms for single blockchains supported by snow ²², the following excerp and diagram give an overview of how a blockchain (in our case the C-chain) can leverage one of snows mulitple conensus mechanisms (in our case snowman).

Each blockchain on Avalanche has several components: the virtual machine, database, consensus engine, sender, and handler. These components help the chain run smoothly. Blockchains also interact with the P2P layer and the chain router to send and receive messages.

In the case of the C-Chain, avalanche uses coreth²³ a modified version of geth, as it's vm to provide EVM support. It also uses Snowman++ ²⁴ as a congestion controle mechanism, effectively pre-selecting a set of proposers and giving them a submission window to submit blocks. If they fail to submit within their WindowDuration then any other validator can issue the block.

Below is an excerpt of how Snowman vms ²⁵ and the consensus engine work.

Implementing the Snowman VM Block From the perspective of the consensus engine, the state of the VM can be defined as a linear chain starting from the genesis block through to the last accepted block.

Following the last accepted block, the consensus engine may have any number of different blocks that are processing. The configuration of the processing set can be defined as a tree with the last accepted block as the root.

In practice, this looks like the following:

   G
   |
   .
   .
   .
   |
   L
   |
   A
 /   \
B     C

Signing Mechanisms

Consensus Signing Mechanism

Avalanche is not prescriptive about addressing schemes, choosing to instead leave addressing up to each blockchain ²⁶.

Avalanche uses Transport Layer Security, TLS, to protect node-to-node communications from eavesdroppers. TLS combines the practicality of public-key cryptography with the efficiency of symmetric-key cryptography.

Inter-Subnet Message Signing Mechanism

Avalanche Warp Messaging (AWM)^{15 16} enables Subnet Validators to collectively produce a BLS Multi-Signature that attests to the validity of an arbitrary message (e.g., transfer, contract data, etc.) that can be verified by any other Subnet.

Transaction Signing Mechanism

The addressing scheme of the X-Chain and the P-Chain relies on secp256k1. Avalanche follows a similar approach as Bitcoin and hashes the ECDSA public key. The 33-byte compressed representation of the public key is hashed with sha256 once. The result is then hashed with ripemd160 to yield a 20-byte address.

The Avalanche virtual machine uses elliptic curve cryptography, specifically secp256k1, for its signatures on the blockchain.

Verification Walkthrough

1. Transactions are gossiped via P2P mechanisms in coreth

// Block represents an entire block in the Ethereum blockchain.
type Block struct {
 header       *Header
 uncles       []*Header
 transactions Transactions
 
 // Coreth specific data structures to support atomic transactions
 version uint32
 extdata *[]byte
 
 // caches
 hash atomic.Value
 size atomic.Value
}
 
// Header represents a block header in the Ethereum blockchain.
type Header struct {
 ParentHash  common.Hash    `json:"parentHash"       gencodec:"required"`
 UncleHash   common.Hash    `json:"sha3Uncles"       gencodec:"required"`
 Coinbase    common.Address `json:"miner"            gencodec:"required"`
 Root        common.Hash    `json:"stateRoot"        gencodec:"required"`
 TxHash      common.Hash    `json:"transactionsRoot" gencodec:"required"`
 ReceiptHash common.Hash    `json:"receiptsRoot"     gencodec:"required"`
 Bloom       Bloom          `json:"logsBloom"        gencodec:"required"`
 Difficulty  *big.Int       `json:"difficulty"       gencodec:"required"`
 Number      *big.Int       `json:"number"           gencodec:"required"`
 GasLimit    uint64         `json:"gasLimit"         gencodec:"required"`
 GasUsed     uint64         `json:"gasUsed"          gencodec:"required"`
 Time        uint64         `json:"timestamp"        gencodec:"required"`
 Extra       []byte         `json:"extraData"        gencodec:"required"`
 MixDigest   common.Hash    `json:"mixHash"`
 Nonce       BlockNonce     `json:"nonce"`
 ExtDataHash common.Hash    `json:"extDataHash"      gencodec:"required"`
 
 // BaseFee was added by EIP-1559 and is ignored in legacy headers.
 BaseFee *big.Int `json:"baseFeePerGas" rlp:"optional"`
 
 // ExtDataGasUsed was added by Apricot Phase 4 and is ignored in legacy
 // headers.
 //
 // It is not a uint64 like GasLimit or GasUsed because it is not possible to
 // correctly encode this field optionally with uint64.
 ExtDataGasUsed *big.Int `json:"extDataGasUsed" rlp:"optional"`
 
 // BlockGasCost was added by Apricot Phase 4 and is ignored in legacy
 // headers.
 BlockGasCost *big.Int `json:"blockGasCost" rlp:"optional"`
}

2. The block is then wrapped into an innerBlock by snowman++ and has the following interfaces

type Block interface {
 ID() ids.ID
 ParentID() ids.ID
 Block() []byte
 Bytes() []byte
 
 initialize(bytes []byte) error
}
 
type SignedBlock interface {
 Block
 
 PChainHeight() uint64
 Timestamp() time.Time
 Proposer() ids.NodeID
 
 Verify(shouldHaveProposer bool, chainID ids.ID) error
}
 
type statelessUnsignedBlock struct {
 ParentID     ids.ID `serialize:"true"`
 Timestamp    int64  `serialize:"true"`
 PChainHeight uint64 `serialize:"true"`
 Certificate  []byte `serialize:"true"`
 Block        []byte `serialize:"true"`
}
 
type statelessBlock struct {
 StatelessBlock statelessUnsignedBlock `serialize:"true"`
 Signature      []byte                 `serialize:"true"`
 
 id        ids.ID
 timestamp time.Time
 cert      *x509.Certificate
 proposer  ids.NodeID
 bytes     []byte
}

The block is initialized using block.Build which currently uses StakingCertLeaf not StakingBLSKey

 statelessChild, err = block.Build(
  parentID,
  newTimestamp,
  pChainHeight,
  p.vm.ctx.StakingCertLeaf,
  innerBlock.Bytes(),
  p.vm.ctx.ChainID,
  p.vm.ctx.StakingLeafSigner,
 )

The Build function takes the StakingCertLeaf as input for cert *x509.Certificate

func Build(
 parentID ids.ID,
 timestamp time.Time,
 pChainHeight uint64,
 cert *x509.Certificate,
 blockBytes []byte,
 chainID ids.ID,
 key crypto.Signer,
)

Signatures are verified using Verify which checks the signature as follows

 return b.cert.CheckSignature(b.cert.SignatureAlgorithm, headerBytes, b.Signature)

Code Review

Folllowing is a review of . Avalanche also has a coreth codebase which was inspired by geth. Please see here for a code review of geth. Following is an excerpt from coreth README.md.

Coreth (from core Ethereum) is the Virtual Machine (VM) that defines the Contract Chain (C-Chain). This chain implements the Ethereum Virtual Machine and supports Solidity smart contracts as well as most other Ethereum client functionality.

Signing

• Avalanche Signing Codebase
  • getStakingSigner: Configuration retrieving validators BLS key. (go)
  • Signer Interface: returns the public BLS key if it exists. (go)
  • bls signature: Includes functions SignatureToBytes, SignatureFromBytes and AggregateSignatures aggregates a non-zero number of signatures into a single aggregated signature.
  • secp256kr1: Avalanches implementation of the ECSDA secp256k1r curve (go)
  • tx.go: Includes function for signing transactions using a Secp256k1r private key.

Consensus

• Avalanche ConsensusContext Codebase: Context is information about the current executio including NetworkID is the ID of the network this context exists within. ChainID is the ID of the chain this context exists within. NodeID is the ID of this node. (go)
• Avalanche Consensus CodeBase: Contains consenus engines snowball, snowman, snowstorm and avalanche (go)
  • Avalanche snow README.md: Documentation of the folow of a Single Blockchain.
  • consensus.go: Consensus code (go). Consensus represents a general avalanche instance that can be used directly to process a series of partially ordered elements.
  • avalanche poll: Avalanches Polling (validator voting) mechanism (go).
  • snowman consensus.go: Snowman consenus code (go). represents a general snowman instance that can be used directly to process a series of dependent operations.
  • avalanche snowman poll: Snowman Polling (validator voting) mechanism (go).

Cryptographic Primitives

• bag: Mulitset with the ability to set thresholds add elements, compare against other bags, filter, split and return all elements which have been added a number of times.
• beacon: Beacons are a structure contiaining the NodeId and IPPort.
• bloom: Avalanches implementation of BloomFilteres
• bufer: Buffer with queuing mechanisms including an unbounded deque double-ended queue. Not safe for concurrent access.
• cb58: CB58 is a format used to represent keys, addresses, and other binary values in web wallets and APIs. CB58 is the concatenation of the data bytes and a checksum. The checksum is created by taking the last four bytes of the SHA256 hash of the data bytes.
• compare: Compares slices and returns true iff the slices have the same elements, regardless of order.
• compression: compresss and decompresses messages using gzip compression.
• constants: Constants for avalanche including aliases, applications, network_ids, network constantns and vm_ids.
• crypto
  • bls: Provides the interface to the blst BLS12-381 signature library.
  • keychain: implements functions for a keychain to return its main address and to sign a hash.
  • ledger: Ledger is a wrapper around the low-level Ledger Device interface that provides Avalanche-specific access.
  • secp256k1: Avalanche implementation of secp256k1
• dynamicip: Updates and resolves public IP's using ifconfig's format.
• filesystem: Reads and renames files.
• formatting: Formats addresses. Parse takes in an address string and splits returns the corresponding parts. This returns the chain ID alias, bech32 HRP, address bytes, and an error if it occurs.
• hashing: see hash functions below.
• ips: ip utlitilties including claim (A self contained proof that a peer is claiming ownership of an IPPort at a given time.) and lookup (Lookup attempts to resolve a hostname to a single IP. If multiple IPs are found.
• json; utilities for marshalling and unmarshalling json.
• linkedhashmap: is a hashmap that keeps track of the oldest pairing and the newest pairing. hashmap provides an O(1) mapping from a comparable key to any value.
• math: mathematic functions
• metric: Provide metrics by integrating with Prometheus.
• password: Implements password Hashing using Argon2
• perms: provides the ability to modify file permissions.
• profiler: Profiler provides helper methods for measuring the current performance of processes/
• resource: provides resource usage information including active cpu and disk usage.
• rpc: Manages requests for avalanche rpc endpoints.
• sampler: sample a specified valued based on a provided weighted distribution. Sampling is performed by executing a modified binary search over the provided elements. Rather than cutting the remaining dataset in half, the algorithm attempt to just in to where it think the value will be assuming a linear distribution of the element weights.
• set: Return a new set with initial capacity [size]. More or less than [size] elements can be added to this set. Using NewSet() rather than Set[T] is just an optimization that can be used if you know how many elements will be put in this set.
• storage: File system storage
• timer: Timer wraps a timer object. This allows a user to specify a handler. Once specifying the handler, the dispatch thread can be called. The dispatcher will only return after calling Stop. SetTimeoutIn will result in calling the handler in the specified amount of time.
• ulimit: Manages resource limits.
• units: Unit Constants (e.g. Avax uint64 = 1000 * MilliAvax )
• window: an interface which represents a sliding window of elements.
• wrappers: Wrappers for packing and unpacking data.

• hashing
  • sha256: Implements SHA256 hashing.
  • ripmed160: Implements RIPEMD (RIPE Message Digest), a family of cryptographic hash functions developed in 1992 (the original RIPEMD) and 1996 (other variants). There are five functions in the family: RIPEMD, RIPEMD-128, RIPEMD-160, RIPEMD-256, and RIPEMD-320, of which RIPEMD-160 is the most common.
  • ring: Ring is an interface for a consistent hashing ring.
• Argon2 password hashing: Implements password Hashing using Argon2

• vms: Avalanche Virtual Machines

References

• Scalable and Probabilistic Leaderless BFT Consensus through Metastability: This paper introduces a family of leaderless Byzantine fault tolerance protocols, built around a metastable mechanism via network subsampling.

• Avalanche Blockchain Consensus Documentation: Overive of the Snowball Algorithm used for Avalanche Consenus and it's use of Directed Acyclic Graphs (DAGs).

• Avalanche Subnet Overview Documentation: Overview of Avalanches Subnets and their use of Avalanche's 3 built-in blockchains: Platform Chain (P-Chain), Contract Chain (C-Chain) and Exchange Chain (X-Chain).

• Avalanche Get Current Validator Documentation: List the current validators of the given Subnet. Signer is the node's BLS public key and proof of possession.

• Avalanche Get Node Id Documentation: Get the ID of this node. nodePOP is this node's BLS key and proof of possession.

• Avalanche Platform Transaction Format Documentation: Documenation on how transactions are serialized and the use of the primitive serialization format for packing and secp256k1 for cryptographic user identification.

• Avalanche Network Status Dashboard:

• Avalanche Cryptographic Primitive Documentation: Overview of Avalanches cryptographic primitives focusing on it's use of TLS AND Secp256k1.
• Avalanche BLS Support Release Documentation
  • Release v1.8.6: Apricot Phase 6: Adds BLS key file and exposes blos proof of posession
  • Release v1.9.1: Banff.1: Added BLS signer to the snow.Context
  • Release v1.9.2: Banff.2 - Additional BLS Support: Added bls proof of possession to platform.getCurrentValidators and platform.getPendingValidators. Added bls public key to in-memory staker objects. Improved memory clearing of bls secret keys.
• Avalanch BLS Relevant Commits
  • Add BLS key to AddPermissionlessValidatorTx for the Primary Network (#1987)
  • Add BLS signer to snow.Context (#2069)

• Avalanche Staking Documentation: Staking Parameters on Avalanche

• UTXO Codebase: Unsigned Transaction Output Handling.
• xsvm: Cross Subnet Asset Transfers README Overview

Footnotes

Overview

Avalanche BLS Support Release Documentation

Avalanche BLS Relevant Commits

Warp Messaging

RSA Support

consensus

signing