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 ------------------------------------------------------------------------------ LogMeIn Central: Instant, anywhere, Remote PC access and management. Stay in control, update software, and manage PCs from one command center Diagnose problems and improve visibility into emerging IT issues Automate, monitor and manage. Do more in less time with Central http://p.sf.net/sfu/logmein12331_d2d _______________________________________________ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
