Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of petertodd.org
	designates 62.13.149.115 as permitted sender)
	client-ip=62.13.149.115; envelope-from=pete@petertodd.org;
	helo=outmail149115.authsmtp.co.uk; 
Date: Sat, 20 Sep 2014 12:24:16 -0400
From: Peter Todd <pete@petertodd.org>
To: Peter Grigor <peter@grigor.ws>
Message-ID: <20140920162416.GA28251@muck>
References: <CAGpx8BUav93VTHyaBcuqk+FmsNBrq_ue8L4exfZ1iq8Om_WGiA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="BOKacYhQ+x31HxR3"
Content-Disposition: inline
In-Reply-To: <CAGpx8BUav93VTHyaBcuqk+FmsNBrq_ue8L4exfZ1iq8Om_WGiA@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] From block 0 to block 72499 the Merkle
 root is the same as the coinbase transaction id. Why is that?
Precedence: list


--BOKacYhQ+x31HxR3
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sat, Sep 20, 2014 at 08:38:15AM -0700, Peter Grigor wrote:
> From block 0 to block 72499 the Merkle root is the same as the
> coinbase transaction id. Why is that?

It's because of how the merkle tree algorithm works:

    uint256 CBlock::BuildMerkleTree() const
    {
        vMerkleTree.clear();

So here all the txids are pushed onto the vMerkleTree vector:

        BOOST_FOREACH(const CTransaction& tx, vtx)
            vMerkleTree.push_back(tx.GetHash());

For most of the early blocks there's just the coinbase transaction and
no other transactions.

        int j =3D 0;
        for (int nSize =3D vtx.size(); nSize > 1; nSize =3D (nSize + 1) / 2)

That means this for loop never executes! nSize =3D vtx.size() =3D=3D 1, and
the loop terminates when nSize <=3D 1

        {
            for (int i =3D 0; i < nSize; i +=3D 2)
            {
                int i2 =3D std::min(i+1, nSize-1);
                vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]),  END(vM=
erkleTree[j+i]),
                                           BEGIN(vMerkleTree[j+i2]), END(vM=
erkleTree[j+i2])));
            }
            j +=3D nSize;
        }
        return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
    }

Thus the vMerkleTree still has only the coinbase txid in it, and and
vMerkleTree.back() returns that txid as the merkle root. There's no
problem with the merkle root algorithm working that way - to make a long
story short all this means is that the merkle tree algorithm
consistently uses the txid as the merkle root whenever there is only one
transaction. The contents of the block is still being securely committed
to by the merkleroot, which is the important thing, and there's no way
to lie about those contents.

There is however a serious flaw in the algorithm, unrelated to the case
of a single transaction, where the merkle tree is indistinguishable from
a merkle tree with duplicate txids if there are a non-power-of-two
number of items in the tree. For bitcoin we fixed this flaw with BIP30
and BIP34; for any other application you should *never* use the Satoshi
merkle root calculation code. Get it right on day one and do things
correctly.

--=20
'peter'[:-1]@petertodd.org
00000000000000000fbf83c9e14d8711e4b2264ceda0d1d06d169c811387eadd

--BOKacYhQ+x31HxR3
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQGrBAEBCACVBQJUHaosXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDAwZmJmODNjOWUxNGQ4NzExZTRiMjI2NGNlZGEwZDFkMDZk
MTY5YzgxMTM4N2VhZGQvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfuayQf/fI70Aaebfi26mPipEXsiKsFk
WPeVd1kmWMZIg83mCYCgPy0fdgz87Sp59hwI8FFrK1MctY6Nb6pVTAivalmD4VTD
KMbDCHEWzVq9CCfucpK9xFGYPkmS2Q7ccKHSmKZFGtjOKSNmre+Zq6SYpgV+5Bd3
4pupQVfYHIRM5EIB5en8qZ5ADN7viONGwO54nFE/G29m4Kx4+jU2UObBs5UppWKT
7cBrM+t4r2Brfp16+3xhSZt9es19HgfY5gtjDwlR0tB6whi/xGj1QvTOrjYeBazd
vPTsD4y6qHYmd01CHnBRNlGhO0MownJeU6enkM2Q0klPvVP0LcDeqeiQ2tXWRA==
=fbIP
-----END PGP SIGNATURE-----

--BOKacYhQ+x31HxR3--