RFC-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 64 bytes of extra data; 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;
• witness_mr;
• kernel_mr;
• kernel_mmr_size;
• total_kernel_offset;
• script_kernel_offset;
• validator_node_mr;
• validator_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_mmr_size

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

The Output_mmr_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 tree root of all non-coinbase outputs, appended with the Merkle mountain range tree root of all 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 blocks, this MUST be 0.

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 C29).
• pow_data for RandomX blocks as an array of unsigned 8-bit integers (bytes) in little-endian format, containing the RandomX merge-mining Proof-of-Work data.
  • The RandomX seed, stored as randomx_key within the RandomX block, MUST NOT have been first seen in a block with more than max_randomx_seed_height confirmations.
• pow_data for Sha3x blocks MUST be empty.

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 two 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, and vice versa.

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 calculated as (T*N)/20, with T and N defined as:

• T: Target time — the ideal time that should pass between mined blocks.
• N: Block window — the number of blocks used when calculating difficulty adjustments.

MTP

The Median Time Passed (MTP) is the lower bound calculated by taking the median timestamp of the last N blocks. Any block with a timestamp less than 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 four independent proof-of-work algorithms rated at different difficulties. To compare them, they are simply multiplied together into one number: $$ \begin{align} \textit{accumulated_randomxM_difficulty} * \textit{accumulated_sha3x_difficulty} * \textit{accumulated_randomxT_difficulty} * \textit{accumulated_C29_difficulty} \end{align} \tag{3} $$ 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