From: Bram Cohen <bram@bittorrent•com>
To: Peter Todd <pete@petertodd•org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkle trees and mountain ranges
Date: Fri, 17 Jun 2016 20:22:04 -0700 [thread overview]
Message-ID: <CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com> (raw)
In-Reply-To: <20160616001040.GA5026@fedora-21-dvm>
[-- Attachment #1: Type: text/plain, Size: 2323 bytes --]
On Wed, Jun 15, 2016 at 5:10 PM, Peter Todd <pete@petertodd•org> wrote:
> On Tue, Jun 14, 2016 at 05:14:23PM -0700, Bram Cohen via bitcoin-dev wrote:
>
> > The fundamental approach to handling the latency problem is to have the
> > utxo commitments trail a bit. Computing utxo commitments takes a certain
> > amount of time, too much to hold up block propagation but still hopefully
> > vastly less than the average amount of time between blocks. Trailing by a
> > single block is probably a bad idea because you sometimes get blocks back
> > to back, but you never get blocks back to back to back to back. Having
> the
> > utxo set be trailing by a fixed amount - five blocks is probably
> excessive
> > - would do a perfectly good job of keeping latency from every becoming an
> > issue. Smaller commitments for the utxos added and removed in each block
> > alone could be added without any significant performance penalty. That
> way
> > all blocks would have sufficient commitments for a completely up to date
> > proofs of inclusion and exclusion. This is not a controversial approach.
>
> Agreed - regardless of approach adding latency to commitment calculations
> of
> all kinds is something I think we all agree can work in principle, although
> obviously it should be a last resort technique when optimization fails.
>
An important point: Adding latency to utxo commitments does not imply
latency to proofs of inclusion and exclusion! If roots of what's added and
deleted in each block are added as well, then a proof of inclusion can be
done by having a proof of inclusion of the trailing utxo set followed by a
proof of exclusion from all the following deletion sets, or a proof of
inclusion in one of the single block addition sets followed by proofs of
exclusion from all the more recent deletion sets. Likewise a proof of
exclusion can be a proof of exclusion from the utxo set followed by proofs
of exclusion from all the more recent addition sets or a single proof of
inclusion in a recent deletion set.
This does make proofs larger (except in the case of recent deletions and
maybe recent additions) and adds complexity, so it shouldn't be done unless
necessary. But validation before block propagation needs to be extremely
fast, so for utxo roots this trick is probably both necessary and
sufficient.
[-- Attachment #2: Type: text/html, Size: 2803 bytes --]
next prev parent reply other threads:[~2016-06-18 3:22 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-06-15 0:14 Bram Cohen
2016-06-16 0:10 ` Peter Todd
2016-06-16 1:16 ` Bram Cohen
2016-06-16 3:26 ` Peter Todd
2016-06-16 9:07 ` Bram Cohen
2016-06-17 4:34 ` Peter Todd
2016-06-18 2:43 ` Bram Cohen
2016-06-18 23:01 ` Peter Todd
2016-07-15 23:00 ` Bram Cohen
2016-06-18 3:22 ` Bram Cohen [this message]
2016-06-18 22:09 ` Peter Todd
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='CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com' \
--to=bram@bittorrent$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=pete@petertodd$(echo .)org \
/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