Home About John Resume/CV References Writing Research

Avalanche

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 subnet1, 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 2.

Note: On march 23rd, 2023 Avalanche published an article3 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 4. Block proposers are randomly sampled from the active validator set, therefore any validator could potentially sign a block 5. The validators use X.509 (TLS)certificate to sign and verify blocks 6, and the block headers contain both the certificate and the signature 7. 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 8.

In recent releases9 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 17 . Solidity libraries 18 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 blockchains19, this diagram gives an overview of the avalanche primiary network.

Avalanche Primary Network

Avalanche Consensus

Following is an excerpt from the Avalanche Consensus Whitepaper 20, it is also recommended reviewing Avalanche Blockchain Consensus Documentation 21.

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.

Avalanche Consensus

Snowman Consensus

Snowman consensus is one of the consensus mechanisms for single blockchains supported by snow 22, 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.

Avalanche flow of a single blockchain

In the case of the C-Chain, avalanche uses coreth23 a modified version of geth, as it’s vm to provide EVM support. It also uses Snowman++ 24 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 25 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 26.

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"`
}
  1. 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

Consensus

Cryptographic Primitives

general primitives

hash functions

encryption

random number generators

serilization

virtual machines

References

Consensus

Signing

Staking

Additional

Footnotes

  1. Avalanche introductory documentation: Avalanche is a heterogeneous network of blockchains allowing separate chains to be created for different applications. ↩

  2. Snowman VM: To the consensus engine, the Snowman VM is a black box that handles all block building, parsing, and storage and provides a simple block interface for the consensus engine to call as it decides blocks. ↩

  3. Cortina: X-Chain Linearization: This upgrade linearizes the X-chain, introduces delegation batching to the P-chain, and increases the maximum block size on the C-chain. (Release notes are here and changelog is here) ↩

  4. Avalanche explorer: Block Explorere showing subnets, totoal blockchains, total validators and totals stake amount. ↩

  5. Snowman++: a congestion control mechanism available for snowman VMs. ↩

  6. block verify function: statelessBlock Verify function in proposervm. ↩

  7. block structure: statelessBlock structure in proposervm. ↩

  8. NewCertAndKeyBytes: Creates a new staking private key / staking certificate pair. Returns the PEM byte representations of both. ↩

  9. release notes on GitHub and code commit search result ↩

  10. Release v1.8.6: Apricot Phase 6: Adds BLS key file and exposes blos proof of posession ↩

  11. Release v1.9.1: Banff.1: Added BLS signer to the snow.Context ↩

  12. 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. ↩

  13. Add BLS key to AddPermissionlessValidatorTx for the Primary Network (#1987) ↩

  14. Add BLS signer to snow.Context (#2069) ↩

  15. Avalanche Warp Messaging (AWM): AWM 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. ↩ ↩2

  16. avalanchego warp codebase: Codebase supporting bls signing of inter-subnet messages. ↩ ↩2

  17. EIP-198: Big integer modular exponentiation. Pre-compile for Ethereum which allows for efficient RSA verification inside of the EVM, as well as other forms of number theory-based cryptography. ↩

  18. SolRsaVerify: Solidity Library which allows verification of RSA Sha256 Pkcs1.5 Signatures ↩

  19. Avalanche Platform: Avalanche is a heterogeneous network of blockchains. The Primary Network is a special Subnet that contains all validators (including validators of any custom Subnets). ↩

  20. Avalanche Consensus Whitepaper: 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. ↩

  21. Avalanche Docs: Consensus: a consensus protocol that is scalable, robust, and decentralized. It has low latency and high throughput. It is energy efficient and does not require special computer hardware. ↩

  22. Snow README.md: 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. ↩

  23. Coreth and the C-Chain: Coreth is a dependency of AvalancheGo which is used to implement the EVM based Virtual Machine for the Avalanche C-Chain. ↩

  24. Snowman++: congestion control for Snowman VMs: Snowman++ introduces a soft proposer mechanism which attempts to select a single proposer with the power to issue a block, but opens up block production to every validator if sufficient time has passed without blocks being generated. ↩

  25. Snowman VM’s: To the consensus engine, the Snowman VM is a black box that handles all block building, parsing, and storage and provides a simple block interface for the consensus engine to call as it decides blocks. ↩

  26. Avalanche Cryptographic Primitive Documentation: Overview of Avalanches cryptographic primitives focusing on it’s use of TLS AND Secp256k1. ↩