Date: Tue, 6 Nov 2012 20:14:58 +0100
From: Pieter Wuille <pieter.wuille@gmail.com>
To: Mike Hearn <mike@plan99.net>
Message-ID: <20121106191455.GA23467@vps7135.xlshosting.net>
References: <CANEZrP0XALwBFJyZTzYd5xBp4MRrjv0s_y2tOXbO7UgjWF2HzA@mail.gmail.com>
	<CAAS2fgScydOWz_eqnhWxQNVUOtzvSBwkj7tttP3_DLdW+=3CTQ@mail.gmail.com>
	<CANEZrP2sBZL=UYAxtjU2Su13Z12wB7s04LxmcyUR2hH51tcN9g@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CANEZrP2sBZL=UYAxtjU2Su13Z12wB7s04LxmcyUR2hH51tcN9g@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Draft BIP for Bloom filtering
Precedence: list

On Fri, Oct 26, 2012 at 04:01:58PM +0200, Mike Hearn wrote:
> I don't feel I understand the effort required to do some kind of
> partial tree encoding. Having a kind of custom compression whereby
> branches are represented as varint indexes into a dictionary, I can
> feel how much work that involves and maybe I can make time over the
> next few weeks to implement it. Has anyone got example code for
> representing partial Merkle trees?

I've implemented code for efficient representation of partial merkle
trees: see https://github.com/sipa/bitcoin/commits/partialmerkle

The encoding/decoding algorithm uses a depth-first traversal of the tree, at
each node outputting whether anything relevant is beneath, and if not, storing
its hash and not descending into the children.

Furthermore, thanks to some properties of the tree, some hard upper bounds on
the size of the serialized structures are guaranteed. See the comments in the
code for details.

Unit tests are included to verify that
1) encoding and decoding a subset of transactions is an identity
2) the calculated merkle root matches the merkle root calculated by the existing merkle algorithm in the source code
3) the calculated merkle root actually depends on all hashes in the data structure.
4) serialization/deserialization is an identity
5) bounds on the size of the serialization are respected

Hope it is clear enough to port to other languages.

-- 
Pieter