How do I compute merkle root for genesis block?

Question

I wanted to help out the community and create a pure C application independent of the reference client, that given a timestamp and a public key, will produce a merkle root for creation of a genesis block.

My knowledge of C++ is very little to none. After looking at the source code, this is the relevant code

    const char* pszTimestamp = "The Times 03/Jan/2009 Chancellor on brink of second bailout for banks";
    CTransaction txNew;
    txNew.vin.resize(1);
    txNew.vout.resize(1);
    txNew.vin[0].scriptSig = CScript() << 486604799 << CBigNum(4) << vector<unsigned char>((const unsigned char*)pszTimestamp, (const unsigned char*)pszTimestamp + strlen(pszTimestamp));
    txNew.vout[0].nValue = 50 * COIN;
    txNew.vout[0].scriptPubKey = CScript() << ParseHex("04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f") << OP_CHECKSIG;

Which produces this merkle hash

 4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b

I am not sure whether CScript() << 486604799 << CBigNum(4) <<... is bitshifting all of this, or simply writing it out to .scriptSig. And I am going to assume that CScript() is the constructor that initializes .scriptSig.

As I delved into the source code and following what BuildMerkleTree calls I ended up in

template<typename T>
uint256 SerializeHash(const T& obj, int nType=SER_GETHASH, int     nVersion=PROTOCOL_VERSION)
{
    CHashWriter ss(nType, nVersion);
    ss << obj;
    return ss.GetHash();
}

So I started following ChashWriter, and ended up in

template<typename T>
CHashWriter& operator<<(const T& obj) {
    // Serialize to this stream
    ::Serialize(*this, obj, nType, nVersion);
    return (*this);
}

And I got lost there. But the closest I got was double SHA256-ing this

04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73 5000000000 04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f OP_CHECKSIG after supposedly converting to a byte array.

And I was obviously wrong about it, as the result was not correct.

Apparently, Bitcoin uses something known as Serialization to serialize the object's variables, perhaps concatenate them, but unfortunately due to my inexperience with C++ I could not understand which variables, in what order and so on. Basically, the Bitcoin source code was more complex than I had imagined.

So my question is how I may produce a merkle hash for a genesis block, without using serialization and in C?

Answer 1

Instead of looking at the source code, take a look at the relevant wiki page.

As blockexplorer will reveal, the merkle root of the genesis block is equal to the hash of the transaction in it. This is because building a hash tree of one transaction will simply result in that one transaction, and the hash of that tree will be the same as the hash of that one transaction.

When dealing with more transactions, simply put them in a tree and hash them from bottom to top, as the wiki page mentions.