From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XVNSY-0002Dm-Ci for bitcoin-development@lists.sourceforge.net; Sat, 20 Sep 2014 16:24:30 +0000 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; Received: from outmail149115.authsmtp.co.uk ([62.13.149.115]) by sog-mx-3.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1XVNSX-0007pw-66 for bitcoin-development@lists.sourceforge.net; Sat, 20 Sep 2014 16:24:30 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt18.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s8KGOKOX014327; Sat, 20 Sep 2014 17:24:20 +0100 (BST) Received: from muck (cpe-74-71-46-2.nyc.res.rr.com [74.71.46.2]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s8KGOHIM031204 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Sat, 20 Sep 2014 17:24:19 +0100 (BST) Date: Sat, 20 Sep 2014 12:24:16 -0400 From: Peter Todd To: Peter Grigor Message-ID: <20140920162416.GA28251@muck> References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="BOKacYhQ+x31HxR3" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 92df9f5d-40e2-11e4-b396-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAIUC1AEAgsB AmIbWlNeUll7WGo7 bA5PagRDZkxQXRpv WE9WQxwRHH4ffmR4 ex4dUxtyc0tHeXh4 ZwhrXCQNVRJ/IVt5 QhtWCGwHMGN9OmMW Vl1YdwFReQMbfxoR O1cxNiYHcQ51Pz4z GA41ejw8IzhbLzxQ TwcRGBo8W0EOVjQ4 QBsBVW1nAUpNTSE0 JB9udQRATRdZLkU/ eX4sQ1EcPn1aEApZ AwlMG2dFJ1RJXCMu AEtTRgYCEDAVSiBd BBchORIAHiZbXDFR D1dETBdHCi8DGBZI WX5cSWUxDFE1cCoA X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 74.71.46.2/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust [62.13.149.115 listed in list.dnswl.org] -0.0 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1XVNSX-0007pw-66 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? X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 20 Sep 2014 16:24:30 -0000 --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--