Mining - Extra Nonce

See: Technical_Articles

Introduction

VeriBlock provides a 64-bit integer extra nonce field that is factored into the computation of the merkle root, and hence the block hash. This field should be used as opposed to common alternatives, such as timestamp manipulation. The aim of this article is to provide an explanation of the VeriBlock merkle root and the extra nonce field's role.

Let's take an example UCP Mining Job message to use throughout this document.

{  
   "command":"MINING_JOB",
   "request_id":{  
      "type":"REQUEST_ID",
      "data":1107123451
   },
   "job_id":{  
      "type":"JOB_ID",
      "data":224
   },
   "block_index":{  
      "type":"BLOCK_INDEX",
      "data":1010
   },
   "block_version":{  
      "type":"BLOCK_VERSION",
      "data":2
   },
   "previous_block_hash":{  
      "type":"BLOCK_HASH",
      "data":"0000000000009AD1F05D1C1A6B79DF3E3B59711579D3BB37"
   },
   "second_previous_block_hash":{  
      "type":"BLOCK_HASH",
      "data":"000000000000C09BE6D14004A7D8F2DD91B99CF316246920"
   },
   "third_previous_block_hash":{  
      "type":"BLOCK_HASH",
      "data":"000000000001917F9EE65F9B3BD9DB54CB81C3383034C4AA"
   },
   "pool_address":{  
      "type":"ADDRESS",
      "data":"VCTHaNxhxGPCuwG1eUKHg5iLZ68aG9"
   },
   "merkle_root":{  
      "type":"TOP_LEVEL_MERKLE_ROOT",
      "data":"78F71FD9F518B5B43738477D84A3421ABDABFE2EDC503165"
   },
   "timestamp":{  
      "type":"TIMESTAMP",
      "data":1554374816
   },
   "difficulty":{  
      "type":"DIFFICULTY",
      "data":117480792
   },
   "mining_target":{  
      "type":"TARGET",
      "data":"00000000ffffffffffffffffffffffffffffffffffffffff"
   },
   "ledger_hash":{  
      "type":"LEDGER_HASH",
      "data":"A6FD19B41E1F97F887C87BA5D785432A2061EA23F3ACD055"
   },
   "coinbase_txid":{  
      "type":"TRANSACTION_ID",
      "data":"E07B589BA4903404FA8A6E228A988826AE510105A45213E3E3A21E41BECD2334"
   },
   "pop_datastore_hash":{  
      "type":"POP_DATASTORE_HASH",
      "data":"F5A5FD42D16A20302798EF6ED309979B43003D2320D9F0E8EA9831A92759FB4B"
   },
   "miner_comment":{  
      "type":"MINER_COMMENT",
      "data":""
   },
   "pop_transaction_merkle_root":{  
      "type":"INTERMEDIATE_LEVEL_MERKLE_ROOT",
      "data":"0000000000000000000000000000000000000000000000000000000000000000"
   },
   "normal_transaction_merkle_root":{  
      "type":"INTERMEDIATE_LEVEL_MERKLE_ROOT",
      "data":"0000000000000000000000000000000000000000000000000000000000000000"
   },
   "intermediate_metapackage_hash":{  
      "type":"INTERMEDIATE_METAPACKAGE_HASH",
      "data":"219819F77F0E0DB759594E61F3952C168231D6FEE0C6C30AFC933A120914BECE"
   },
   "extra_nonce_start":{  
      "type":"EXTRA_NONCE",
      "data":0
   },
   "extra_nonce_end":{  
      "type":"EXTRA_NONCE",
      "data":999999
   }
}

In this message, we're able to identify the merkle root that will be used as a component of the block hash computation. The value in the above message is: 78F71FD9F518B5B43738477D84A3421ABDABFE2EDC503165. The last 12 properties in the above message represent raw ingredients that go into the computation of the merkle root.

VeriBlock Merkle Tree

Before delving into the computation, it's important to understand a few things about the VeriBlock merkle tree. It is somewhat unique in that it is essentially composed of three sub-trees. The three sub-trees represent the "Block Content Metapackage", the PoP Transactions Merkle tree and the "normal" transactions Merkle tree. The PoP transaction Merkle tree and normal transaction Merkle tree are each typical transaction Merkle trees. If we were to represent this in a hierarchical format, it would look like this:

                   [MERKLE_ROOT]
               /                   \
[METAPACKAGE_ROOT]               [TRANSACTION_ROOT]
                               /                    \
            [POP_TRANSACTION_ROOT]              [NORMAL_TRANSACTION_ROOT]

Block Content Metapackage

Referring back to our sample UCP Mining Job message, we see that we are given the merkle roots for each of the transaction trees in the properties "pop_transaction_merkle_root" and "normal_transaction_merkle_root". Now, to calculate the metapackage merkle root:

1. The intermediate hash of the intermediate_metapackage_hash is provided.
2. Concatenate the intermediate_metapackage_hash and the extra nonce (64-bit integer), represented as a byte[]
3. Sha256 hash the concatenated value

Merkle Root

Having produced the complete metapackage hash above, it can be joined with the transaction root hash to produce the top-level Merkle root. The Mining Job message is initially computed with the "extra_nonce_start" value used in the above metapackage computation. The final merkle root is trimmed to the first 24 bytes.

Sample Java Test

Below is a sample program, written in Java, that computes the top-level Merkle root from the properties supplied in the Mining Job message above.

import javax.xml.bind.DatatypeConverter;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class ExtraNonceDemo {
    public static void main(String[] args) {
        String popTxMerkleRoot = "0000000000000000000000000000000000000000000000000000000000000000";
        String normalTxMerkleRoot = "0000000000000000000000000000000000000000000000000000000000000000";

        String intermediateMetapackageHash = "219819F77F0E0DB759594E61F3952C168231D6FEE0C6C30AFC933A120914BECE";

        long extraNonce = 0L;

        byte[] intermediateMetapackageHashBytes = DatatypeConverter.parseHexBinary(intermediateMetapackageHash);


        // Calculate the block content metapackage with the extra nonce
        byte[] blockContentMerkleRootWithExtraNonce = SHA256ReturnBytes(concat(intermediateMetapackageHashBytes, longToByteArray(extraNonce)));

        byte[] txMerkleRoot = SHA256ReturnBytes(concat(DatatypeConverter.parseHexBinary(popTxMerkleRoot), DatatypeConverter.parseHexBinary(normalTxMerkleRoot)));

        byte[] merkleRoot = SHA256ReturnBytes(concat(blockContentMerkleRootWithExtraNonce, txMerkleRoot));
        byte[] trimmedContentMerkleRoot = new byte[24];
        System.arraycopy(merkleRoot, 0, trimmedContentMerkleRoot, 0, trimmedContentMerkleRoot.length);

        System.out.println(DatatypeConverter.printHexBinary(trimmedContentMerkleRoot));
    }

    public static byte[] longToByteArray(long input) {
        return new byte[]{
                (byte) ((input & 0xFF00000000000000l) >> 56),
                (byte) ((input & 0x00FF000000000000l) >> 48),
                (byte) ((input & 0x0000FF0000000000l) >> 40),
                (byte) ((input & 0x000000FF00000000l) >> 32),
                (byte) ((input & 0x00000000FF000000l) >> 24),
                (byte) ((input & 0x0000000000FF0000l) >> 16),
                (byte) ((input & 0x000000000000FF00l) >> 8),
                (byte) ((input & 0x00000000000000FFl)),
        };
    }

    public static byte[] concat(byte[] first, byte[] second) {
        byte[] result = new byte[first.length + second.length];
        System.arraycopy(first, 0, result, 0, first.length);
        System.arraycopy(second, 0, result, first.length, second.length);
        return result;
    }

    public static byte[] SHA256ReturnBytes(String input) {
        return SHA256ReturnBytes(input.getBytes(StandardCharsets.UTF_8));
    }

    public static byte[] SHA256ReturnBytes(byte[] input) {
        return _sha256.digest(input);
    }



    private static MessageDigest _sha256;

    static {
        try {
            _sha256 = MessageDigest.getInstance("SHA-256");
        } catch (
                NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
    }
}

Extra Nonce

Each subscribed UCP mining client is assigned an extra nonce range, represented above by the properties "extra_nonce_start" and "extra_nonce_end". Supplying values outside of your assigned range will result in a rejection of the submission.

To aid in third-party implementations, below are the calculated merkle roots for 5 different extra nonce values in the range specified above.

Extra Nonce: 552 -> A4D09298321FE8C5893F45A07633EB80E044612F22ACC7BB

Extra Nonce: 983 -> C349240F588FBBBBCD3BC9A1DD99DC5FDB4E17A498AC956C

Extra Nonce: 10478 -> CBA028C21DCDFAF3CF2FACF3192A6DB5C4647103F33C3F08

Extra Nonce: 55231 -> 38E87C83FE132D5235D5364AB82103CBC5EBCA2CA567F0AB

Extra Nonce: 887166 -> 025D310D312997A50A46A654FAE78EE0CDF9F55190A52CDA