From: Pieter Wuille <pieter.wuille@gmail•com>
To: Mike Hearn <mike@plan99•net>
Cc: Bitcoin Dev <bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] Draft BIP for Bloom filtering
Date: Tue, 6 Nov 2012 20:14:58 +0100 [thread overview]
Message-ID: <20121106191455.GA23467@vps7135.xlshosting.net> (raw)
In-Reply-To: <CANEZrP2sBZL=UYAxtjU2Su13Z12wB7s04LxmcyUR2hH51tcN9g@mail.gmail.com>
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
next prev parent reply other threads:[~2012-11-06 19:15 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-10-24 15:56 Mike Hearn
2012-10-24 16:22 ` Pieter Wuille
2012-10-24 16:35 ` Mike Hearn
2012-10-24 17:11 ` Pieter Wuille
2012-10-24 18:54 ` Gavin Andresen
2012-10-24 19:00 ` Matt Corallo
2012-10-24 19:10 ` Mike Hearn
2012-10-24 20:29 ` Gavin Andresen
2012-10-24 20:58 ` Mike Hearn
2012-10-24 21:55 ` Jeff Garzik
2012-10-25 16:56 ` Gregory Maxwell
2012-10-25 17:01 ` Gregory Maxwell
2012-10-26 14:01 ` Mike Hearn
2012-10-26 14:17 ` Gregory Maxwell
2012-10-26 14:21 ` Mike Hearn
2012-10-26 14:34 ` Gregory Maxwell
2012-11-06 19:14 ` Pieter Wuille [this message]
2012-11-21 15:15 ` Pieter Wuille
2012-11-21 18:38 ` Matt Corallo
2012-11-27 21:10 ` Pieter Wuille
2013-01-10 15:21 ` Mike Hearn
2013-01-11 3:59 ` Matt Corallo
2013-01-11 5:02 ` Jeff Garzik
2013-01-11 14:11 ` Mike Hearn
2013-01-11 14:13 ` Mike Hearn
2013-01-16 10:43 ` Mike Hearn
2013-01-16 15:00 ` Matt Corallo
2013-01-18 16:38 ` Mike Hearn
2013-01-19 9:51 ` Andreas Schildbach
2013-01-30 11:09 ` Mike Hearn
2013-01-30 11:13 ` Mike Hearn
2013-02-06 16:33 ` Mike Hearn
2013-02-06 16:45 ` Gregory Maxwell
2013-02-20 12:44 ` Mike Hearn
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20121106191455.GA23467@vps7135.xlshosting.net \
--to=pieter.wuille@gmail$(echo .)com \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=mike@plan99$(echo .)net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox