I-TIP-RFC-MT-0120: Consensus

Base Layer Consensus

Licence

The 3-Clause BSD Licence.

Copyright 2019 The Tari Development Community

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of this document must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS DOCUMENT IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS”, AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Language

The keywords “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “NOT RECOMMENDED”, “MAY” and “OPTIONAL” in this document are to be interpreted as described in BCP 14 (covering RFC2119 and RFC8174) when, and only when, they appear in all capitals, as shown here.

Disclaimer

This document and its content are intended for information purposes only and may be subject to change or update without notice.

This document may include preliminary concepts that may or may not be in the process of being developed by the Tari community. The release of this document is intended solely for review and discussion by the community of the technological merits of the potential system outlined herein.

Goals

The aim of this Request for Comment (RFC) is to describe the fields that a block should contain, as well as all consensus rules that determine the validity of a block.

Related Requests for Comment

• RFC-0122: Burn outputs
• RFC-0130: Mining
• RFC-0140: SyncAndSeeding

Description

Blockchain consensus is a set of rules that a majority of nodes agree on, which determines the state of the blockchain.

This RFC details the consensus rules for the Tari network.

Blocks

Every block MUST:

• have exactly one valid block header, as per the Block Headers section

• have exactly one coinbase transaction

• have a total transaction weight less than the consensus maximum

• be able to calculate matching Merkle roots (kernel_mr, output_mr, and input_mr)

• each transaction input MUST:

  • be of an allowed transaction input version
  • spend an existing valid UTXO with a maturity less than or equal to the current block height
  • satisfy the covenant attached to the UTXO
  • have a valid script signature
  • be in a canonical order (see Transaction ordering)

• each transaction output MUST:

  • be of an allowed transaction output version
  • have a unique domain-separated hash (version || features || commitment|| RangeProof Hash || Sender Offset Public Key || Metadata signature || script || covenant || encrypted_data || minimum value promise) with the domain (transaction_output)
  • have a unique commitment in the current UTXO set
  • be in a canonical order (see Transaction ordering)
  • have a valid range proof
  • have a valid metadata signature
  • contain only allowed opcodes in the script

• each transaction kernel MUST:

  • have a valid kernel excess signature
  • have a unique excess

• have a valid total script offset, \( \gamma \); see script-offset.

• The number of BURNED outputs MUST equal the number of BURNED_KERNEL kernels exactly.

• The commitment value of each burnt output MUST match the commitment value of each corresponding BURNED_KERNEL exactly.

• The transaction commitments and kernels MUST balance, as follows:

  $$ \begin{align} &\sum_i\mathrm{Cout_{i}} - \sum_j\mathrm{Cin_{j}} + \text{fees} \cdot H \stackrel{?}{=} \sum_k\mathrm{K_k} + \text{offset} \\ & \text{for each output}, i, \\ & \text{for each input}, j, \\ & \text{for each kernel excess}, k \\ & \text{and }\textit{offset }\text{is the total kernel offset} \\ \end{align} \tag{1} $$

If a block does not conform to the above, the block SHOULD be discarded, and the node MAY ban the peer that sent it.

Coinbase

A coinbase transaction contained in a block MUST:

• be the only transaction in the block with the coinbase flag
• consist of at least one output and one kernel (no inputs)
• have a valid kernel signature
• have a value exactly equal to the emission at the block height it was minted (see emission schedule) plus the total transaction fees within the block
• have a lock-height as per consensus
• MUST NOT have an offset other than 0
• MUST NOT have a script offset other than 0

A coinbase transaction contained in a block MAY:

• include any arbitrary extra data up to 256 bytes (as limited by coinbase_output_features_extra_max_length); see coinbase-extra

Block Headers

Every block header MUST contain the following fields:

• version;
• height;
• prev_hash;
• timestamp;
• input_mr;
• output_mr;
• block_output_mr;
• output_smt_size;
• kernel_mr;
• kernel_mmr_size;
• total_kernel_offset;
• total_script_offset;
• validator_node_mr;
• validator_node_size;
• pow;
• nonce.

The block header MUST conform to the following:

• The nonce and PoW MUST be valid for the block header.
• The [achieved difficulty] MUST be greater than or equal to the target difficulty.
• The timestamp MUST satisfy the FTL and MTP rules, detailed below.
• The block hash MUST NOT appear in the bad block list.

The Merkle roots are validated as part of the full block validation, detailed in Blocks.

If the block header does not conform to any of the above, the block SHOULD be rejected, and the node MAY ban the peer that sent it.

Version

This is the version currently running on the chain.

The version MUST conform to the following:

• It is represented as an unsigned 16-bit integer.
• Version numbers MUST be incremented whenever there is a change in the blockchain schema or validation rules, starting from 0.
• The version MUST be one of the allowed versions for the consensus rules at this block’s height.

Height

A counter indicating how many blocks have passed since the genesis block (inclusive).

The height MUST conform to the following:

• Represented as an unsigned 64-bit integer.
• The height MUST be exactly one more than the block referenced in the prev_hash block header field.
• The genesis block MUST have a height of 0.

Prev_hash

This is the hash of the previous block’s header.

The prev_hash MUST conform to the following:

• Represented as an array of unsigned 8-bit integers (bytes) in little-endian format.
• MUST be a hash of the entire contents of the previous block’s header using the domain (block_header).

Timestamp

This is the timestamp at which the block was mined.

The timestamp MUST conform to the following:

• MUST be transmitted as a UNIX timestamp.
• MUST be less than FTL.
• MUST be higher than the MTP.

Output_mr

The output_mr MUST be calculated as the sparse Merkle tree root of all UNSPENT outputs in the blockchain, after this block has been applied. The output_mr MUST conform to the following:

• Represented as an array of unsigned 8-bit integers (bytes) in little-endian format.
• The hashing function used MUST be blake2b with a 256-bit digest.

Output_smt_size

This is the total number of leaves in the output sparse Merkle tree (Jellyfish Merkle Tree), which tracks the current UTXO set.

The Output_smt_size MUST conform to the following:

• Represented as a single unsigned 64-bit integer.

Block_output_mr

The block_output_mr MUST be calculated as the Merkle mountain range root of a structure that contains, as leaves, the hash of each coinbase output in canonical order, followed by the Merkle mountain range root of all non-coinbase outputs.

The block_output_mr MUST conform to the following:

• Represented as an array of unsigned 8-bit integers (bytes) in little-endian format.
• The hashing function used MUST be blake2b with a 256-bit digest.

Input_mr

This is the Merkle root of all the inputs in the block, consisting of the hashed inputs. It is used to prove that all inputs are correct and have not been changed after mining. This MUST be constructed by adding, in order, the hash of every input contained in the block.

The input_mr MUST conform to the following:

• Represented as an array of unsigned 8-bit integers (bytes) in little-endian format.
• The hashing function MUST be blake2b with a 256-bit digest.

Kernel_mr

This is the Merkle root of the kernels.

The kernel_mr MUST conform to the following:

• MUST be transmitted as an array of unsigned 8-bit integers (bytes) in little-endian format.
• The hashing function used MUST be blake2b with a 256-bit digest.

Kernel_mmr_size

This is the total size of the leaves in the kernel Merkle mountain range.

The Kernel_mmr_size MUST conform to the following:

• Represented as a single unsigned 64-bit integer.

Total_kernel_offset

This is the total summed offset of all the transactions in this block.

The total_kernel_offset MUST conform to the following:

• MUST be transmitted as an array of unsigned 8-bit integers (bytes) in little-endian format.

Total_script_offset

This is the total summed script offset of all the transactions in this block.

The total_script_offset MUST conform to the following:

• MUST be transmitted as an array of unsigned 8-bit integers (bytes) in little-endian format.

Nonce

This is the Nonce used in solving the Proof of Work.

The Nonce MUST conform to the following:

• MUST be transmitted as an unsigned 64-bit integer.
• For RandomX-M (Monero merge-mined) blocks, this MUST be 0. RandomX-T blocks may use the nonce as part of the PoW solution.

PoW

This is the Proof of Work algorithm used to mine the block. It is used in conjunction with the Nonce.

The [PoW] MUST contain the following:

• pow_algo as an enum (0 for RandomX-M, 1 for Sha3x, 2 for RandomX-T, and 3 for Cuckaroo, also known as C29).
• pow_data for RandomX-M (Monero merge-mined) blocks as an array of unsigned 8-bit integers (bytes) in little-endian format, containing the Monero merge-mining Proof-of-Work data.
  • The RandomX seed, stored as randomx_key within the RandomX-M block, MUST NOT have been first seen in a block with more than max_randomx_seed_height confirmations (3000 blocks on mainnet).
• pow_data for RandomX-T (Tari solo RandomX) blocks MUST be at most 32 bytes.
• pow_data for Sha3x blocks MUST be empty.
• pow_data for Cuckaroo blocks MUST be exactly ceil(cuckaroo_cycle_length * cuckaroo_edge_bits / 8) bytes (153 bytes on mainnet where cycle length=42 and edge bits=29), containing the packed cuckaroo cycle edges. The last byte MUST be zero-padded if the total bit count is not a multiple of 8.

Difficulty Calculation

The target difficulty represents how difficult it is to mine a given block. This difficulty is not fixed and needs to constantly adjust to changing network hash rates.

The difficulty adjustment MUST be calculated using a linear-weighted moving average (LWMA) algorithm (2): $$ \newcommand{\solvetime}{ \mathrm{ST_i} } \newcommand{\solvetimemax}{ \mathrm{ST_{max}} } $$

$$ \begin{align} & \textit{weighted_solve_time} = \sum\limits_{i=1}^N(\solvetime*i) \\ & \textit{weighted_target_time} = (\sum\limits_{i=1}^Ni) * \mathrm{T} \\ & \textit{difficulty} = \mathrm{D_{avg}} * \frac{\textit{weighted_target_time}}{\textit{weighted_solve_time}}\\ \end{align} \tag{2} $$

It is important to note that the proof-of-work algorithms are calculated independently; i.e., if the current block uses SHA3x proof of work, the block window and solve times only include SHA3x blocks. The same applies to each of the other algorithms (RandomX-M, RandomX-T, and Cuckaroo).

FTL

The Future Time Limit (FTL) defines how far into the future a timestamp is accepted as valid. Any block with a timestamp beyond the FTL is rejected until the current time catches up.

The FTL is hardcoded per consensus version. On mainnet it is 540 seconds. The design formula is (T_chainN)/20, where T_chain is the overall chain target block time (the ideal time between any two consecutive blocks, which equals the per-algorithm target time divided by the number of active PoW algorithms), and N is the difficulty block window (90). For mainnet, T_chain = 120s (e.g. 240s/2 algos or 480s/4 algos), so FTL = 12090/20 = 540. Note that T_chain is distinct from the per-algorithm target time T used in the difficulty calculation table.

MTP

The Median Time Passed (MTP) is the lower bound calculated by taking the median timestamp of the last median_timestamp_count blocks (11 blocks on mainnet). This is a separate consensus constant from the difficulty block window N. Any block with a timestamp less than or equal to the MTP will be rejected.

Total accumulated proof of work

This is defined as the total accumulated proof of work done on the blockchain. Tari uses up to four independent proof-of-work algorithms rated at different difficulties. To compare them, their accumulated difficulties are multiplied together into one number. The total accumulated difficulty is computed as the product of the accumulated RandomX-M, RandomX-T, and SHA3x difficulties. The accumulated Cuckaroo (C29) difficulty is additionally included in the product only when the consensus flag include_c29_accumulated_difficulty_into_total is set (on mainnet, this is true from block height 126,000 onward): $$ \begin{align} \textit{total} = \textit{accumulated_randomxM} \times \textit{accumulated_randomxT} \times \textit{accumulated_sha3x} \quad [\times \textit{accumulated_cuckaroo} \text{ if enabled}] \end{align} \tag{3} $$ Algorithms that have not yet been activated have an accumulated difficulty of 1 (the minimum), so they do not affect the product. This value is used to compare chain tips to determine the strongest chain.

Transaction Ordering

The order in which transaction inputs, outputs, and kernels are added to the Merkle mountain range completely changes the final Merkle root. Input, output, and kernel ordering within a block is, therefore, part of consensus.

The block MUST be transmitted in canonical ordering. The advantage of this approach is that sorting does not need to be done by the whole network, and verification of sorting is exceptionally cheap.

• Transaction outputs are sorted lexicographically by the byte representation of their Pedersen commitment, i.e. \(k \cdot G + v \cdot H\).
• Transaction kernels are sorted lexicographically by the excess signature byte representation.
• Transaction inputs are sorted lexicographically by the hash of the output that is spent by the input.

Change Log