æternity consensus protocol

This document defines the æternity consensus protocol.

Introduction

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.

Notation

x || y, x concatenated with y

Overview

Blockchain

A blockchain is a specific instance of a distributed ledger made up from blocks, which are arranged as a tree with the root of the tree being the genesis block. Each node in this tree has exactly one parent but can have multiple children. Blocks specify their parent via the prev_hash field in the block header, with the genesis block having a prev_hash of all 0.

At any point, the block height is the distance from the current valid top block to the genesis block. The genesis block has height zero.

A valid block here means valid according to the consensus rules described below.

We use temporary random leader to build the tree of blocks.

In order to find the best valid chain given a tree of blocks, every node operator in the network sums the amount of work (see Proof of Work) done on each chain. The best valid chain is then the chain that has the most work done. Any ties here will be resolved by the time a block was received at, i.e. it will prefer the block it received first.

Blocks

This document depends on Bitcoin-NG protocol that describes rules for building blockchain.

Bitcoin NG introduces two types of blocks:

Key Blocks - Key Blocks carry a Public Key of a leader and Proof-of-Work evidence and associated metadata
Micro Blocks - Micro Blocks carry transactions confirmed by a leader and associated metadata

There may be 0-N Micro Blocks between two Key Blocks. Micro Blocks are small and they are produced very often i.e. every three seconds.

Key Blocks are generated by miners. New coins are introduced by each Key Block. Micro Blocks are generated by miners who become leaders by mining Key Blocks.

Genesis block

The genesis block is special in the sense that it does not have a parent and contains the initial state of the æternity blockchain. Part of initial state is generated from the distribution of the æternity ERC20 token on the Ethereum blockchain.

The genesis block is a key block.

Transactions

æternity follows the "fat protocol" approach, which means that the protocol itself has many features built in, as opposed to e.g. Ethereum, which maps any functionality beyond basic transactions changing the state of an account to smart contracts.

Transaction signature

We sign serialized transaction (or the hash of the serialized transaction - from Lima hard-fork) prefixed with the id of the network. See serialization definition for details.

NetworkId             :: binary()
SerializedObject      :: binary()
Signature             :: binary()

Signature = sign(NetworkId + SerializedObject)
or Signature = sign(NetworkId + Blake2b(SerializedObject))

Prefix defaults to ae_mainnet (binary()) and it is configurable via node config. The prefix is not part of a serialized transaction. We add it only for signature. Consider changing the id in case of forking the blockchain network, in order to lower danger of replay attacks.

Note: After the Lima protocol upgrade it is allowed to sign either the full serialized object, or the hash of the serialized object; prefixed with the network id in either case.

Note: For the inner transaction of a PayingFor the network id should be extended to <network id>-inner_tx in order to make the inner transaction not replayable on-chain.

Proof of Work

Cuckoo Cycle is the algorithm used for proof of work. It was designed to prevent the dynamics that have developed in Bitcoin and similar systems, where the mining operations are dominated by special purpose hardware. The problem being solved is that of finding cycles in a bipartite graph.

Proof of work is used for leader election, which happens via key blocks in Bitcoin-NG. Micro blocks do not require any proof of work.

Accounts

Each account holds a balance, and can be of any one of the following types.

Basic (or plain old) account

The address is a public key. It has an increasing nonce. It authorizes a transaction by signing it.

For the actual wire format please consult the serialisation document.

Account associated to a contract

Please refer to the dedicated document.

Generic account

Please refer to the dedicated document.

Available from the Fortuna consensus protocol version.

P2P network

The peer-to-peer network is not part of the consensus and will be described in a separate document.

Coins

æternity coins

We use the following denominations:

1                          | aetto
1_000
1_000_000
1_000_000_000
1_000_000_000_000
1_000_000_000_000_000
1_000_000_000_000_000_000

Specification

Crypto

Blake2b (256 bits digest) and ed25519

Keys

Key generation is done according to RFC8032, note that we have 64-byte secret keys that consists of the seed concatenated with the public key in order to save CPU cycles when signing The public key is 32 byte.

Signatures

EDDSA (curve 25519), signature is 64 bytes.

Blocks

Consensus protocol versions

PROTOCOL_VERSION

Name

Minimum height at which protocol is effective

Roma

0 (genesis)

Minerva

47800

Fortuna

90800

Lima

161150

Iris

441444

The consensus protocol version number in each block is monotonically increasing in the chain of blocks.

Key Blocks

PROTOCOL_VERSION: 1 (Roma release) or greater

the timestamp of a key block MUST be smaller than now() + 9m
the timestamp of a key block MUST be bigger than:
- the median timestamp of the last 11 blocks (if height >= 12)
- the timestamp of the genesis block (if height <= 11)
the version MUST match the expected PROTOCOL_VERSION
the pow_evidence MUST be valid
MUST have 0 <= nonce <= MAX_NONCE
txs_hash MUST be correct root hash of the merkle tree of all transactions.
TODO: fill in missing rules

PROTOCOL_VERSION: 2 (Minerva release) or greater

an optional info field is added to the key header
the presence of the info field MUST be marked by setting the info field flag to 1
the absence of the info field MUST be marked by setting the info field flag to 0
the info field, if present, is uninterpreted, but included in the block hash (i,e., it is under consensus).

Block/header serialization format

Micro Blocks

PROTOCOL_VERSION: 1 (Roma release) or greater

the timestamp of a micro block MUST be smaller than now() + 9m
if the previous block is a micro block:
- the timestamp MUST be bigger than or equal to the timestamp of the previous block + 3s
if the previous block is a key block:
- the timestamp MUST be bigger than the timestamp of the previous block
the version MUST match the expected PROTOCOL_VERSION
the signature must be a valid signature produced by the issuer of the previous key block
the sum of gas of transactions in a micro block MUST be lower or equal to the gas limit per micro block
TODO: fill in missing rules

Header serialization format

Block serialization format

Transactions

Authorization transactions

Signed transaction

 Fieldname       Size (bytes)
 -------------- -----
| data         | var |
 -------------- -----
| signatures   | var |
 -------------- -----

MUST have valid signature from private key belonging to sender.

For the actual wire format please consult the serialisation document.

Generic account meta transaction

Please refer to the dedicated document.

Common fields for transactions

Each (on-chain) transaction has the following fields:

Fee. It MUST be at least the gas for the transaction multiplied by the minimal gas price, which (after MINERVA hard fork height) is 1000000 (*10^-18) aettos. (Before MINERVA hard fork height it was 1 (*10^-18) aettos.)
Time to live (TTL). The last generation where the transaction is valid. 0 means it is valid forever (and is the default value in many places).

Note: There is also a node configurable minimum gas price - this is the minimum gas price a node accepts and is not under consensus. This value is higher than or equal to the minimal gas price as dictated by consensus. For contract transactions (Create, Call, GAAttach, GAMeta), the minimum applies to both the Fee and the GasPrice.

Spend transaction

 Fieldname       Size (bytes)
 -------------- -----
| sender       | 32  |
 -------------- -----
| recipient    | 32  |
 -------------- -----
| amount       | var |
 -------------- -----
| fee          | var |
 -------------- -----
| nonce        | 8   |
 -------------- -----

PayingFor transaction

Available from protocol version 5, Iris release. The tx field size depends on the size of the inner transaction.

 Fieldname       Size (bytes)
 -------------- -----
| payer        | 32  |
 -------------- -----
| fee          | var |
 -------------- -----
| nonce        | 8   |
 -------------- -----
| tx           | var |
 -------------- -----

Note: When signing the inner transaction the network id should be extended to <network id>-inner_tx in order to make the inner transaction not replayable on-chain.

Contract transactions

Please refer to the dedicated document.

Oracle transactions

Please refer to the dedicated document.

Naming system transactions

Please refer to the dedicated document.

Channel transactions

Please refer to the dedicated document.

Generalized account attach transaction

Please refer to the dedicated document.

Gas

In order to control the size and the number of transactions in a micro block, each transaction has a gas. The sum of gas of all the transactions cannot exceed the gas limit per micro block, which is 6 000 000.

The gas of a transaction is the sum of:

the base gas;
other gas components, such as gas proportional to the byte size of the transaction or relative TTL, gas needed for contract execution.

Note on "other gas components" - up until Iris the micro block gas limit was computed towards the static (upper) gas limit of a transaction. From Ceres the micro block gas limit is computed towards the actual used gas. This mainly affects contract calls (and GA Meta transactions) where the gas limit can be overestimated which pre-Ceres would cause micro blocks to be under-utilized.

Transaction

Base gas

Other gas components

Spend

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(SpendTx) * GasPerByte

Oracle register

BaseGas

Proportional to oracle TTL argument TTL (interpreted as relative), specifically: ceiling(32000 * RelativeTTL / floor(60 * 24 * 365 / key_block_interval)) and the byte size of the transaction, specifically: byte_size(OracleRegisterTx) * GasPerByte

Oracle query

BaseGas

Proportional to oracle query TTL argument QTTL (interpreted as relative), specifically: ceiling(32000 * RelativeTTL / floor(60 * 24 * 365 / key_block_interval)) and the byte size of the transaction, specifically: byte_size(OracleQueryTx) * GasPerByte

Oracle respond

BaseGas

Proportional to oracle response TTL argument RTTL in oracle query (as found in the oracle query in the state, and interpreted as relative), specifically: ceiling(32000 * RelativeTTL / floor(60 * 24 * 365 / key_block_interval)) and the byte size of the transaction, specifically: byte_size(OracleRespondTx) * GasPerByte

Oracle extend

BaseGas

Name preclaim

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(NamePreclaimTx) * GasPerByte

Name claim

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(NameClaimTx) * GasPerByte

Name update

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(NameUpdateTx) * GasPerByte

Name transfer

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(NameTransferTx) * GasPerByte

Name revoke

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(NameRevokeTx) * GasPerByte

Channel create

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelCreateTx) * GasPerByte

Channel deposit

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelDepositTx) * GasPerByte

Channel withdraw

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelWithdrawTx) * GasPerByte

Channel settle

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelSettleTx) * GasPerByte

Channel slash

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelSlashTx) * GasPerByte

Channel close solo

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelCloseSoloTx) * GasPerByte

Channel close mutual

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelCloseMutualTx) * GasPerByte

Channel snapshot solo

BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ChannelSnapshotSoloTx) * GasPerByte

Channel force progress

BaseGas before Fortuna and 30 * BaseGas from Fortuna on

Proportional to the byte size of the transaction, specifically: byte_size(ChannelForceProgressTx) * GasPerByte. It may also include gas for contract execution.

Channel offchain

Contract create

5 * BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ContractCreateTx) * GasPerByte. It also includes gas for contract execution.

Contract call (FATE)

12 * BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ContractCallTx) * GasPerByte. It also includes gas for contract execution.

Contract call (AEVM)

30 * BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(ContractCallTx) * GasPerByte. It also includes gas for contract execution.

GA Attach

5 * BaseGas

Proportional to the byte size of the transaction, specifically: byte_size(GAAttachTx) * GasPerByte. It also includes gas for execution of the init function.

GA Meta

5 * BaseGas

Fortuna and Lima : Proportional to the byte size of the transaction, specifically: byte_size(GAMetaTx) * GasPerByte. It also includes gas for execution of the authentication function + recursively gas corresponding to the wrapped transaction(s) (excluding the byte size portion - in order not to account for the size of wrapped transactions multiple times).

5 * BaseGas

From Iris : Proportional to the byte size of GAMeta part of transaction, specifically: (byte_size(GAMetaTx) - byte_size(InnerTx)) * GasPerByte. It also includes gas for execution of the authentication function + recursively gas corresponding to the wrapped transaction(s)

PayingFor

BaseGas / 5

Proportional to the byte size of the PayingFor part of the transaction, specifically: (byte_size(PayingForTx) - byte_size(InnerTx)) * GasPerByte.

BaseGas is 15 000.

GasPerByte is 20.

Note byte_size(<TxType>) is the size of the serialized transaction without the signature.

Proof of Work

HIGHEST_TARGET_SCI: 0x2100ffff
HIGHEST_TARGET_INT: 0xffff000000000000000000000000000000000000000000000000000000000000
NONCE_BITS: 64
MAX_NONCE: 0xffffffffffffffff
EXPECTED_BLOCK_MINE_RATE: 60 * 3 # every 3 minutes
RECALCULATE_DIFFICULTY_FREQUENCY: 10

Cuckoo cycle is used as the proof of work algorithm. Solutions take the form of arrays length l, where l is the length (PROOFSIZE) of the cycle in the bipartite graph. The size of the graph is denoted by the 2-log of the graph size, which is the size in bits of the node identifiers EDGEBITS. The difficulty of a graph with M nodes and N edges is based on the ratio M/N, with the standard implementation being fixed at M/N = 1/2. Please refer to the whitepaper for more details. These indices are referred to as micrononces, not to be confused with the nonce included in the header itself. This graph is generated by hashing every edge i in (0..N) twice with a keyed hash function h (SipHash). The key used for these operations is the hash of a block header plus a nonce. The first node belonging to every edge is given by hashing h(key, index*2) and the second by h(key, index*2+1).

Current defaults:

PROOFSIZE: 42
EDGEBITS: 29

header = version || flags || height || prev_hash || prev_key_hash || state_hash || miner || beneficiary || target || evidence || nonce || time
           32         32       64         256            256            256         256         256          32       42*32       64       64

For the purpose of computing a proof of work puzzle solution, the evidence and nonce are set to [0] * 42 and 0 respectively, since neither are available before the puzzle has been solved.

When a node receives a new key block it must repeat the process, setting evidence and nonce to all 0, in order to be able to validate the proof of work.

h_header = Blake2b(header)

The default key for cuckoo is 80 bytes long. The nonce here is expressed in little-endian notation, to keep consistent with cuckoo cycle, which does the same. Note that both the hashed header and the nonce are base64 encoded. This means that the hashed header is 44 bytes long, and the nonce is 12 bytes.

key = h_header || nonce || 0..0
        352        92      196

A valid solution MUST:

be encoded according to the solution encoding rules
form a cycle (TODO: make this more precise)
only contain micrononces < 2^EDGEBITS - 1
have micrononces in ascending order
pass the difficulty check

Solution Encoding Rules

Since EDGEBITS < 32, we can encode an edge as a 32bit integer, otherwise it would have to be 64 bits. Therefore a solution is currently [u32; 42].

Difficulty target

See Chapter 9 of the cuckoo cycle paper:

For further control, a difficulty target 0 < T < 2^256 is introduced, and we impose the additional constraint that the Blake2b 256 bit digest of the cycle nonces in ascending order be less than T, thus reducing the success probability by a factor of 2^256.

Thus we adopt the target notion from Bitcoin and also use the same way to express it.

The target threshold relates to another value: the difficulty. This is proportional to the hardness of the PoW task:

difficulty = <target of difficulty 1> / target

a floating point value.

Bitcoin uses 0x00000000FFFF0000000000000000000000000000000000000000000000000000 as Difficulty 1 target (0x1d00ffff in scientific notation, see below). For Cuckoo Cycle we need a lighter filtering of solutions than for SHA-256 as the basic algorithm is much slower than a simple hash generation, so we use the largest possible value: 0xFFFF000000000000000000000000000000000000000000000000000000000000 (0x2100ffff in scientific notation) as difficulty 1.

We store the current target threshold in the block header in scientific notation. Difficulty is used to select the winning fork of new blocks: the difficulty of a chain of blocks is the sum of the difficulty of each block.

Integers represented in scientific notation: 2^24 * <base-2 exponent + 3> + the first 3 most significant bytes (i.e., the significand). The + 3 corresponds to the length of the significand (i.e., the int value is 0.<significand> * 8^<exponent>). https://en.bitcoin.it/wiki/Difficulty#How_is_difficulty_stored_in_blocks.3F)

Target adjustment

Some concepts:

Difficulty = HIGHEST_TARGET / Target
Rate       = Capacity / Difficulty  (blocks/ms)
Capacity   = number of potential solutions per ms generated by miners

DesiredTimeBetweenBlocks = aec_governance:expected_block_mine_rate()
DesiredRate              = 1 / DesiredTimeBetweenBlocks

The basic idea of the algorithm is to estimate the current network capacity based on the N (= 17) previous blocks and use that to set the new target:

NewDifficulty = EstimatedCapacity / DesiredRate
NewTarget     = HIGHEST_TARGET / NewDifficulty
              = HIGHEST_TARGET * DesiredRate / EstimatedCapacity

We can estimate the network capacity used to mine a given block i as

EstimatedCapacity[i] = Difficulty[i] / MiningTime[i]
MiningTime[i]        = Time[i] - Time[i - 1]

The estimated capacity across all N blocks is then the weighted (by time) average of the estimated capacities for each block. Note, since MiningTime[i] require Time[i - 1] and we do not use the genesis block timestamp in target adjustment we cannot start using the target estimation until block N + 2 (= 19).

EstimatedCapacity = Sum(EstimatedCapacity[i] * MiningTime[i]) / TotalTime
                  = Sum(Difficulty[i]) / TotalTime
                  = Sum(HIGHEST_TARGET / Target[i]) / TotalTime

To get a good trade-off between response time and stability we use a variant of DigiShield. That means we compute a tempered TotalTime (total solve time in algorithm description):

TotalTime'        = Sum(SolveTime[i])
SolveTime[i]      = max(-FTL, min(6 * DesiredTimeBetweenBlocks, Time[i] - Time[i-1]))
TemperedTotalTime = 0.75 * N * DesiredTimeBetweenBlocks + 0.2523 * TotalTime

Where FTL = Future Time Limit - i.e. the time a block is allowed to be "from the future". We use 9 minutes (540 s) i.e. 3 times the DesiredTimeBetweenBlocks.

Now, the problem is that we can't do any floating point arithmetic (to ensure the calculation can be verified by other nodes), so we pick a reasonably big integer K (= HIGHEST_TARGET * 2^32) and compute

EstimatedCapacity ≈ Sum(K * HIGHEST_TARGET div Target[i]) / TotalTime / K
TemperedTotalTime ≈ (3 * N * DesiredTimeBetweenBlocks) div 4 + (2523 * TotalTime') div 10000

Then

NewTarget = HIGHEST_TARGET * DesiredRate / EstimatedCapacity
          ≈ HIGHEST_TARGET * DesiredRate * TotalTime * K / Sum(K * HIGHEST_TARGET div Target[i])
          ≈ DesiredRate * TotalTime * K / Sum(K div Target[i])
          ≈ TotalTime * K div (DesiredTimeBetweenBlocks * Sum(K div Target[i]))

PreviousChannel off-chain state NextBitcoin-NG for æternity

Last updated 1 month ago