Merge AuxPoW support from Namecore

Includes the following commits:

commit 2ea1b5cd8cf2bdd08e43ae39fb76352eebe14895
commit f2a8220c34275f022f02d81e9e84d4cec33bd51c
commit 84b8b56113e6057b0253475b83e797dc1fed2eed
commit 8471d5db221f145f5a40022ed1897c1b996b628e
commit 2f125ad0a67e1b8f71b18a14a3b41d7e577391d1
commit e01dbc3608703b4cb4e9882738125f2b7816cdb8
commit f0421312631cd44669f9f84d339a0c470b4423b9
commit 1fd522db5dfddfd0e1b0c794b82fae2cc7bdb099
commit 71f63ad99f70ff6461c795fd728aea16aa1008f8
commit a7c44d98a8ded4df0e8455c4c5629b1a5b303bbf
commit e1d7b4fc15addf3dfeb3853fa66230a8bdacd75f
commit d016f2fa02572fd340129176b942b3f19bd5260b
commit f4716e5a168a697afce854a37350fdae0988bdd8
commit 03a575e3b13bf06cbb0a007d6672b05d2085c26e
commit d7ea37444bd9e9ac461a3dda0b16afefd160b062
commit db22affa01e050ff847a12e20c83b88952d80b59
commit 9b7e14986655f914b2d0903ca1d79367c92c6c7e
commit e21034f9c124893d5b9631e9ca231b0b9ede3d52

Changes are as below:

Wrap CBlockHeader::nVersion into a new class (CBlockVersion).  This allows to take care of interpreting the field into a base version, auxpow flag and the chain ID.

Update getauxblock.py for new 'generate' RPC call.

Add 'auxpow' to block JSON.

Accept auxpow as PoW verification.

Add unit tests for auxpow verification.

Add check for memory-layout of CBlockVersion.

Weaken auxpow chain ID checks for the testnet.

Allow Params() to overrule when to check the auxpow chain ID and for legacy blocks.  Use this to disable the checks on testnet.

Introduce CPureBlockHeader.

Split the block header part that is used by auxpow and the "real" block header (that uses auxpow) to resolve the cyclic dependency between the two.

Differentiate between uint256 and arith_uint256.

This change was done upstream, modify the auxpow code.

Add missing lock in auxpow_tests.

Fix REST header check for auxpow headers.

Those can be longer, thus take that into account.  Also perform the check actually on an auxpow header.

Correctly set the coinbase for getauxblock results.

Call IncrementExtraNonce in getauxblock so that the coinbase is actually initialised with the stuff it should be.  (BIP30 block height and COINBASE_FLAGS.)

Implement getauxblock plus regression test.

Turn auxpow test into FIXTURE test.

This allows using of the Params() calls.

Move CMerkleTx code to auxpow.cpp.

Otherwise we get linker errors when building without wallet.

Fix rebase with BIP66.

Update the code to handle BIP66's nVersion=3.

Enforce that auxpow parent blocks have no auxpow block version.

This is for compatibility with namecoind.  See also https://github.com/namecoin/namecoin/pull/199.

Move auxpow-related parameters to Consensus::Params.

1 files changed, 442 insertions, 0 deletions

diff --git a/src/test/auxpow_tests.cpp b/src/test/auxpow_tests.cpp
new file mode 100644
index 000000000..1630d000d
--- /dev/null
+++ b/src/test/auxpow_tests.cpp
@@ -0,0 +1,442 @@
+// Copyright (c) 2014-2015 Daniel Kraft
+// Distributed under the MIT/X11 software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "auxpow.h"
+#include "chainparams.h"
+#include "coins.h"
+#include "main.h"
+#include "uint256.h"
+#include "primitives/block.h"
+#include "script/script.h"
+
+#include "test/test_bitcoin.h"
+
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+#include <vector>
+
+BOOST_FIXTURE_TEST_SUITE(auxpow_tests, BasicTestingSetup)
+
+/* ************************************************************************** */
+
+/**
+ * Tamper with a uint256 (modify it).
+ * @param num The number to modify.
+ */
+static void
+tamperWith(uint256& num)
+{
+    arith_uint256 modifiable = UintToArith256(num);
+    modifiable += 1;
+    num = ArithToUint256(modifiable);
+}
+
+/**
+ * Utility class to construct auxpow's and manipulate them.  This is used
+ * to simulate various scenarios.
+ */
+class CAuxpowBuilder
+{
+public:
+    /** The parent block (with coinbase, not just header).  */
+    CBlock parentBlock;
+
+    /** The auxpow's merkle branch (connecting it to the coinbase).  */
+    std::vector<uint256> auxpowChainMerkleBranch;
+    /** The auxpow's merkle tree index.  */
+    int auxpowChainIndex;
+
+    /**
+   * Initialise everything.
+   * @param baseVersion The parent block's base version to use.
+   * @param chainId The parent block's chain ID to use.
+   */
+    CAuxpowBuilder(int baseVersion, int chainId);
+
+    /**
+   * Set the coinbase's script.
+   * @param scr Set it to this script.
+   */
+    void setCoinbase(const CScript& scr);
+
+    /**
+   * Build the auxpow merkle branch.  The member variables will be
+   * set accordingly.  This has to be done before constructing the coinbase
+   * itself (which must contain the root merkle hash).  When we have the
+   * coinbase afterwards, the member variables can be used to initialise
+   * the CAuxPow object from it.
+   * @param hashAux The merge-mined chain's block hash.
+   * @param h Height of the merkle tree to build.
+   * @param index Index to use in the merkle tree.
+   * @return The root hash, with reversed endian.
+   */
+    std::vector<unsigned char> buildAuxpowChain(const uint256& hashAux, unsigned h, int index);
+
+    /**
+   * Build the finished CAuxPow object.  We assume that the auxpowChain
+   * member variables are already set.  We use the passed in transaction
+   * as the base.  It should (probably) be the parent block's coinbase.
+   * @param tx The base tx to use.
+   * @return The constructed CAuxPow object.
+   */
+    CAuxPow get(const CTransaction& tx) const;
+
+    /**
+   * Build the finished CAuxPow object from the parent block's coinbase.
+   * @return The constructed CAuxPow object.
+   */
+    inline CAuxPow
+    get() const
+    {
+        assert(!parentBlock.vtx.empty());
+        return get(parentBlock.vtx[0]);
+    }
+
+    /**
+   * Build a data vector to be included in the coinbase.  It consists
+   * of the aux hash, the merkle tree size and the nonce.  Optionally,
+   * the header can be added as well.
+   * @param header Add the header?
+   * @param hashAux The aux merkle root hash.
+   * @param h Height of the merkle tree.
+   * @param nonce The nonce value to use.
+   * @return The constructed data.
+   */
+    static std::vector<unsigned char> buildCoinbaseData(bool header, const std::vector<unsigned char>& auxRoot, unsigned h, int nonce);
+};
+
+CAuxpowBuilder::CAuxpowBuilder(int baseVersion, int chainId)
+    : auxpowChainIndex(-1)
+{
+    parentBlock.nVersion.SetBaseVersion(baseVersion);
+    parentBlock.nVersion.SetChainId(chainId);
+}
+
+void
+CAuxpowBuilder::setCoinbase(const CScript& scr)
+{
+    CMutableTransaction mtx;
+    mtx.vin.resize(1);
+    mtx.vin[0].prevout.SetNull();
+    mtx.vin[0].scriptSig = scr;
+
+    parentBlock.vtx.clear();
+    parentBlock.vtx.push_back(mtx);
+    parentBlock.hashMerkleRoot = parentBlock.BuildMerkleTree();
+}
+
+std::vector<unsigned char>
+CAuxpowBuilder::buildAuxpowChain(const uint256& hashAux, unsigned h, int index)
+{
+    auxpowChainIndex = index;
+
+    /* Just use "something" for the branch.  Doesn't really matter.  */
+    auxpowChainMerkleBranch.clear();
+    for (unsigned i = 0; i < h; ++i)
+        auxpowChainMerkleBranch.push_back(ArithToUint256(arith_uint256(i)));
+
+    const uint256 hash = CBlock::CheckMerkleBranch(hashAux, auxpowChainMerkleBranch, index);
+
+    std::vector<unsigned char> res = ToByteVector(hash);
+    std::reverse(res.begin(), res.end());
+
+    return res;
+}
+
+CAuxPow
+CAuxpowBuilder::get(const CTransaction& tx) const
+{
+    LOCK(cs_main);
+    CAuxPow res(tx);
+    res.SetMerkleBranch(parentBlock);
+
+    res.vChainMerkleBranch = auxpowChainMerkleBranch;
+    res.nChainIndex = auxpowChainIndex;
+    res.parentBlock = parentBlock;
+
+    return res;
+}
+
+std::vector<unsigned char>
+CAuxpowBuilder::buildCoinbaseData(bool header, const std::vector<unsigned char>& auxRoot, unsigned h, int nonce)
+{
+    std::vector<unsigned char> res;
+
+    if (header)
+        res.insert(res.end(), UBEGIN(pchMergedMiningHeader), UEND(pchMergedMiningHeader));
+    res.insert(res.end(), auxRoot.begin(), auxRoot.end());
+
+    const int size = (1 << h);
+    res.insert(res.end(), UBEGIN(size), UEND(size));
+    res.insert(res.end(), UBEGIN(nonce), UEND(nonce));
+
+    return res;
+}
+
+/* ************************************************************************** */
+
+BOOST_AUTO_TEST_CASE(check_auxpow)
+{
+    const Consensus::Params& params = Params().GetConsensus();
+    CAuxpowBuilder builder(5, 42);
+    CAuxPow auxpow;
+
+    const uint256 hashAux = ArithToUint256(arith_uint256(12345));
+    const int32_t ourChainId = params.nAuxpowChainId;
+    const unsigned height = 30;
+    const int nonce = 7;
+    int index;
+
+    std::vector<unsigned char> auxRoot, data;
+    CScript scr;
+
+    /* Build a correct auxpow.  The height is the maximally allowed one.  */
+    index = CAuxPow::getExpectedIndex(nonce, ourChainId, height);
+    auxRoot = builder.buildAuxpowChain(hashAux, height, index);
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    scr = (CScript() << 2809 << 2013) + COINBASE_FLAGS;
+    scr = (scr << OP_2 << data);
+    builder.setCoinbase(scr);
+    BOOST_CHECK(builder.get().check(hashAux, ourChainId, params));
+
+    /* Check that the auxpow is invalid if we change either the aux block's
+     hash or the chain ID.  */
+    uint256 modifiedAux(hashAux);
+    tamperWith(modifiedAux);
+    BOOST_CHECK(!builder.get().check(modifiedAux, ourChainId, params));
+    BOOST_CHECK(!builder.get().check(hashAux, ourChainId + 1, params));
+
+    /* Non-coinbase parent tx should fail.  Note that we can't just copy
+     the coinbase literally, as we have to get a tx with different hash.  */
+    const CTransaction oldCoinbase = builder.parentBlock.vtx[0];
+    builder.setCoinbase(scr << 5);
+    builder.parentBlock.vtx.push_back(oldCoinbase);
+    builder.parentBlock.hashMerkleRoot = builder.parentBlock.BuildMerkleTree();
+    auxpow = builder.get(builder.parentBlock.vtx[0]);
+    BOOST_CHECK(auxpow.check(hashAux, ourChainId, params));
+    auxpow = builder.get(builder.parentBlock.vtx[1]);
+    BOOST_CHECK(!auxpow.check(hashAux, ourChainId, params));
+
+    /* The parent chain can't have the same chain ID.  */
+    CAuxpowBuilder builder2(builder);
+    builder2.parentBlock.nVersion.SetChainId(100);
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+    builder2.parentBlock.nVersion.SetChainId(ourChainId);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    /* Disallow too long merkle branches.  */
+    builder2 = builder;
+    index = CAuxPow::getExpectedIndex(nonce, ourChainId, height + 1);
+    auxRoot = builder2.buildAuxpowChain(hashAux, height + 1, index);
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height + 1, nonce);
+    scr = (CScript() << 2809 << 2013) + COINBASE_FLAGS;
+    scr = (scr << OP_2 << data);
+    builder2.setCoinbase(scr);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    /* Verify that we compare correctly to the parent block's merkle root.  */
+    builder2 = builder;
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+    tamperWith(builder2.parentBlock.hashMerkleRoot);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    /* Build a non-header legacy version and check that it is also accepted.  */
+    builder2 = builder;
+    index = CAuxPow::getExpectedIndex(nonce, ourChainId, height);
+    auxRoot = builder2.buildAuxpowChain(hashAux, height, index);
+    data = CAuxpowBuilder::buildCoinbaseData(false, auxRoot, height, nonce);
+    scr = (CScript() << 2809 << 2013) + COINBASE_FLAGS;
+    scr = (scr << OP_2 << data);
+    builder2.setCoinbase(scr);
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+
+    /* However, various attempts at smuggling two roots in should be detected.  */
+
+    const std::vector<unsigned char> wrongAuxRoot = builder2.buildAuxpowChain(modifiedAux, height, index);
+    std::vector<unsigned char> data2 = CAuxpowBuilder::buildCoinbaseData(false, wrongAuxRoot, height, nonce);
+    builder2.setCoinbase(CScript() << data << data2);
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+    builder2.setCoinbase(CScript() << data2 << data);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    data2 = CAuxpowBuilder::buildCoinbaseData(true, wrongAuxRoot, height, nonce);
+    builder2.setCoinbase(CScript() << data << data2);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+    builder2.setCoinbase(CScript() << data2 << data);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    builder2.setCoinbase(CScript() << data << data2);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+    builder2.setCoinbase(CScript() << data2 << data);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    data2 = CAuxpowBuilder::buildCoinbaseData(false, wrongAuxRoot, height, nonce);
+    builder2.setCoinbase(CScript() << data << data2);
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+    builder2.setCoinbase(CScript() << data2 << data);
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+
+    /* Verify that the appended nonce/size values are checked correctly.  */
+
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    builder2.setCoinbase(CScript() << data);
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+
+    data.pop_back();
+    builder2.setCoinbase(CScript() << data);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height - 1, nonce);
+    builder2.setCoinbase(CScript() << data);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce + 3);
+    builder2.setCoinbase(CScript() << data);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    /* Put the aux hash in an invalid merkle tree position.  */
+
+    auxRoot = builder.buildAuxpowChain(hashAux, height, index + 1);
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    builder2.setCoinbase(CScript() << data);
+    BOOST_CHECK(!builder2.get().check(hashAux, ourChainId, params));
+
+    auxRoot = builder.buildAuxpowChain(hashAux, height, index);
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    builder2.setCoinbase(CScript() << data);
+    BOOST_CHECK(builder2.get().check(hashAux, ourChainId, params));
+}
+
+/* ************************************************************************** */
+
+/**
+ * Mine a block (assuming minimal difficulty) that either matches
+ * or doesn't match the difficulty target specified in the block header.
+ * @param block The block to mine (by updating nonce).
+ * @param ok Whether the block should be ok for PoW.
+ * @param nBits Use this as difficulty if specified.
+ */
+static void
+mineBlock(CBlockHeader& block, bool ok, int nBits = -1)
+{
+    if (nBits == -1)
+        nBits = block.nBits;
+
+    arith_uint256 target;
+    target.SetCompact(nBits);
+
+    block.nNonce = 0;
+    while (true) {
+        const bool nowOk = (UintToArith256(block.GetHash()) <= target);
+        if ((ok && nowOk) || (!ok && !nowOk))
+            break;
+
+        ++block.nNonce;
+    }
+
+    if (ok)
+        BOOST_CHECK(CheckProofOfWork(block.GetHash(), nBits, Params().GetConsensus()));
+    else
+        BOOST_CHECK(!CheckProofOfWork(block.GetHash(), nBits, Params().GetConsensus()));
+}
+
+BOOST_AUTO_TEST_CASE(auxpow_pow)
+{
+    /* Use regtest parameters to allow mining with easy difficulty.  */
+    SelectParams(CBaseChainParams::REGTEST);
+    const Consensus::Params& params = Params().GetConsensus();
+
+    const arith_uint256 target = (~arith_uint256(0) >> 1);
+    CBlockHeader block;
+    block.nBits = target.GetCompact();
+
+    /* Verify the block version checks.  */
+
+    block.nVersion.SetGenesisVersion(1);
+    mineBlock(block, true);
+    BOOST_CHECK(CheckProofOfWork(block, params));
+
+    block.nVersion.SetGenesisVersion(2);
+    mineBlock(block, true);
+    BOOST_CHECK(!CheckProofOfWork(block, params));
+
+    block.nVersion.SetBaseVersion(2);
+    block.nVersion.SetChainId(params.nAuxpowChainId);
+    mineBlock(block, true);
+    BOOST_CHECK(CheckProofOfWork(block, params));
+
+    block.nVersion.SetChainId(params.nAuxpowChainId + 1);
+    mineBlock(block, true);
+    BOOST_CHECK(!CheckProofOfWork(block, params));
+
+    /* Check the case when the block does not have auxpow (this is true
+     right now).  */
+
+    block.nVersion.SetChainId(params.nAuxpowChainId);
+    block.nVersion.SetAuxpow(true);
+    mineBlock(block, true);
+    BOOST_CHECK(!CheckProofOfWork(block, params));
+
+    block.nVersion.SetAuxpow(false);
+    mineBlock(block, true);
+    BOOST_CHECK(CheckProofOfWork(block, params));
+    mineBlock(block, false);
+    BOOST_CHECK(!CheckProofOfWork(block, params));
+
+    /* ****************************************** */
+    /* Check the case that the block has auxpow.  */
+
+    CAuxpowBuilder builder(5, 42);
+    CAuxPow auxpow;
+    const int32_t ourChainId = params.nAuxpowChainId;
+    const unsigned height = 3;
+    const int nonce = 7;
+    const int index = CAuxPow::getExpectedIndex(nonce, ourChainId, height);
+    std::vector<unsigned char> auxRoot, data;
+
+    /* Valid auxpow, PoW check of parent block.  */
+    block.nVersion.SetAuxpow(true);
+    auxRoot = builder.buildAuxpowChain(block.GetHash(), height, index);
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    builder.setCoinbase(CScript() << data);
+    mineBlock(builder.parentBlock, false, block.nBits);
+    block.SetAuxpow(new CAuxPow(builder.get()));
+    BOOST_CHECK(!CheckProofOfWork(block, params));
+    mineBlock(builder.parentBlock, true, block.nBits);
+    block.SetAuxpow(new CAuxPow(builder.get()));
+    BOOST_CHECK(CheckProofOfWork(block, params));
+
+    /* Mismatch between auxpow being present and block.nVersion.  Note that
+     block.SetAuxpow sets also the version and that we want to ensure
+     that the block hash itself doesn't change due to version changes.
+     This requires some work arounds.  */
+    block.nVersion.SetAuxpow(false);
+    const uint256 hashAux = block.GetHash();
+    auxRoot = builder.buildAuxpowChain(hashAux, height, index);
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    builder.setCoinbase(CScript() << data);
+    mineBlock(builder.parentBlock, true, block.nBits);
+    block.SetAuxpow(new CAuxPow(builder.get()));
+    BOOST_CHECK(hashAux != block.GetHash());
+    block.nVersion.SetAuxpow(false);
+    BOOST_CHECK(hashAux == block.GetHash());
+    BOOST_CHECK(!CheckProofOfWork(block, params));
+
+    /* Modifying the block invalidates the PoW.  */
+    block.nVersion.SetAuxpow(true);
+    auxRoot = builder.buildAuxpowChain(block.GetHash(), height, index);
+    data = CAuxpowBuilder::buildCoinbaseData(true, auxRoot, height, nonce);
+    builder.setCoinbase(CScript() << data);
+    mineBlock(builder.parentBlock, true, block.nBits);
+    block.SetAuxpow(new CAuxPow(builder.get()));
+    BOOST_CHECK(CheckProofOfWork(block, params));
+    tamperWith(block.hashMerkleRoot);
+    BOOST_CHECK(!CheckProofOfWork(block, params));
+}
+
+/* ************************************************************************** */
+
+BOOST_AUTO_TEST_SUITE_END()