Difference between revisions of "Mining - Extra Nonce"

From Veriblock Wiki
Jump to: navigation, search
(Created page with "See: Technical_Articles __TOC__ === Introduction === VeriBlock provides a 64-bit integer extra nonce field that is factored into the computation of the merkle root, and...")
(No difference)

Revision as of 21:45, 15 January 2019

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": 1919582661
	},
	"job_id": {
		"type": "JOB_ID",
		"data": 2555
	},
	"block_index": {
		"type": "BLOCK_INDEX",
		"data": 326661
	},
	"block_version": {
		"type": "BLOCK_VERSION",
		"data": 1
	},
	"previous_block_hash": {
		"type": "BLOCK_HASH",
		"data": "0000000000036C36D081B6E1A3A1F632F6D580642E0EF43D"
	},
	"second_previous_block_hash": {
		"type": "BLOCK_HASH",
		"data": "000000000001785388664F04161BF23CC968F26CD868D5F6"
	},
	"third_previous_block_hash": {
		"type": "BLOCK_HASH",
		"data": "00000000000348E63152B5F9F71F86D69CA2117FB6BAEDB2"
	},
	"pool_address": {
		"type": "ADDRESS",
		"data": "V7GwB117zoE58Htr57gDVb6Wg8GM7E"
	},
	"merkle_root": {
		"type": "TOP_LEVEL_MERKLE_ROOT",
		"data": "D108A340DB59542A3887F9E238BE367A050BD0686B8D40FE"
	},
	"timestamp": {
		"type": "TIMESTAMP",
		"data": 1547055606
	},
	"difficulty": {
		"type": "DIFFICULTY",
		"data": 103841256
	},
	"mining_target": {
		"type": "TARGET",
		"data": "000000ffffffffffffffffffffffffffffffffffffffffff"
	},
	"ledger_hash": {
		"type": "LEDGER_HASH",
		"data": "CFA51D122F7AEE447EF3479604EEBC67F31E5C970495ED0E"
	},
	"coinbase_txid": {
		"type": "TRANSACTION_ID",
		"data": "619E8E714BD4D8653B1D8E7B0A5DD97D41031E97AD19B1F8301BD1338F5D848F"
	},
	"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": "E46ABBD3921267FC9070FBB32C554F3740BC6398D4B7E5EE21BD240A686FF379"
	},
	"normal_transaction_merkle_root": {
		"type": "INTERMEDIATE_LEVEL_MERKLE_ROOT",
		"data": "2F22E087E3441CCD5E8857ECD66D5B5B5E528E82B815187A39129066991D637F"
	},
	"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: D108A340DB59542A3887F9E238BE367A050BD0686B8D40FE. The last 8 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. There are ALWAYS four leaf nodes in the metapackage.
    1. Coinbase TxId ("coinbase_txid") - Represented as a hex string in the message, should be converted to byte[]
    2. PoP Datastore Hash ("pop_datastore_hash") - Represented as a hex string in the message, should be converted to byte[]
    3. Miner Comment ("miner_comment") - Represented as a UTF-8 string in the message, should be converted to byte[]
    4. Ledger Hash ("ledger_hash") - Represented as a hex string in the message, should be converted to byte[]
  2. Each leaf node in raw byte[] format is Sha256 hashed and built into an intermediate merkle root
  3. Concatenate the resulting intermediate merkle root and the extra nonce (64-bit integer), represented as a byte[]
  4. Sha256 hash the concatenated value

Merkle Root

Having produced the metapackage hash above, it can be joined with the transaction root hash to produce the 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 test, written in Java, that computes the merkle root from the properties supplied in the Mining Job message above. Please note that the "Crypto" and "Utility" methods are just simple helpers to make the code more readable.

    @Test
    public void calculateMerkleRoot() {
        String popTxMerkleRoot = "E46ABBD3921267FC9070FBB32C554F3740BC6398D4B7E5EE21BD240A686FF379";
        String normalTxMerkleRoot = "2F22E087E3441CCD5E8857ECD66D5B5B5E528E82B815187A39129066991D637F";

        String ledgerHash = "CFA51D122F7AEE447EF3479604EEBC67F31E5C970495ED0E";
        String coinbaseTxId = "619E8E714BD4D8653B1D8E7B0A5DD97D41031E97AD19B1F8301BD1338F5D848F";
        String popDatastoreHash = "F5A5FD42D16A20302798EF6ED309979B43003D2320D9F0E8EA9831A92759FB4B";
        String minerComment = "";

        long extraNonce = 0L;

        Crypto c = new Crypto();

        byte[] hashCoinbaseTxId = c.SHA256ReturnBytes(Utility.hexToBytes(coinbaseTxId));
        byte[] hashPoPDatastoreHash = c.SHA256ReturnBytes(Utility.hexToBytes(popDatastoreHash));
        byte[] hashMinerComment = c.SHA256ReturnBytes(minerComment.getBytes());
        byte[] hashLedgerHash = c.SHA256ReturnBytes(Utility.hexToBytes(ledgerHash));

        // Calculate interim merkle root for block content metapackage. Needs doing 1 time
        byte[] leftParent = c.SHA256ReturnBytes(Utility.concat(hashCoinbaseTxId, hashPoPDatastoreHash));
        byte[] rightParent = c.SHA256ReturnBytes(Utility.concat(hashMinerComment, hashLedgerHash));
        byte[] interimRoot = c.SHA256ReturnBytes(Utility.concat(leftParent, rightParent));

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

        byte[] txMerkleRoot = c.SHA256ReturnBytes(Utility.concat(Utility.hexToBytes(popTxMerkleRoot), Utility.hexToBytes(normalTxMerkleRoot)));

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

        Assert.assertEquals("D108A340DB59542A3887F9E238BE367A050BD0686B8D40FE", Utility.bytesToHex(trimmedContentMerkleRoot));
    }

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 10 different extra nonce values in the range specified above.

Extra Nonce: 112012 -> D8FF2E84224B7363DBFC4D90048B5BE7089B6F61BD2E25A7

Extra Nonce: 247465 -> 1D1FA061D6651B4CFCA5DFD29E9DFA50DF24F291CDA91B09

Extra Nonce: 452910 -> F557864EE74FB7CCBBC78E02F815F870D43F21CAD0A3CD2C

Extra Nonce: 462112 -> E35E0EA8045C8FE7065CA4F1346F87824BA02AB97DC17D0A

Extra Nonce: 421824 -> 87FBE908EB218BF921897E8837F9949988943C2617A789EC

Extra Nonce: 204383 -> CB167431CE24C52CF67508787BCD053212B0A52BF19EA428

Extra Nonce: 623725 -> F9BBB077EFA29253B64A818D1E38DAD4C948E7A1F1839E74

Extra Nonce: 563624 -> 907DFEF38E2DA95ED44E4CBF9E100C550FAB5098C9CB6174

Extra Nonce: 558308 -> EF1BD48534F6F6FF6A9C871087A6700FD850E4233BBE6398

Extra Nonce: 855216 -> A7795794A9F7C03FB43430BEE71E13B00B6A8B9349156E11