From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 419DD71 for ; Sat, 18 Jun 2016 03:22:25 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-io0-f170.google.com (mail-io0-f170.google.com [209.85.223.170]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7BA47172 for ; Sat, 18 Jun 2016 03:22:24 +0000 (UTC) Received: by mail-io0-f170.google.com with SMTP id n127so92240375iof.3 for ; Fri, 17 Jun 2016 20:22:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bittorrent-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=sSgGyvFfNMKom6hK3HvlL6FInODtRKrFeRvH74iiPyk=; b=WDBKlC61ynksbG0KvyVjeFU0uwt1EMGmYXwYM1fV/40hFlUxUX7PwSt1ItIciVr5Fz IUM+hkxpXMWUbvZFMcn0rUfanlJMXFe/K8NKkeVXjL79TUM5VRYW0jmqS5eBwrfOcu6T THH/vO6bBHucXJilZKXv9cQ6+jT6jctx3WLbJtE3Jw8fa3GEYr8jpUwzbP5lgfVAoams QTwNhEK9KScArPDBsppn79LCkKEzMiwr/UY2PX96t7uEThs7ukVEqbCryxu2scS4AYQe y80mjYoUe4wM7ymI9TgojfcwcOGPMeU36lorUHTydVs5L8ZAobVFEQWP8z4EgcqvaTlz Zhwg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=sSgGyvFfNMKom6hK3HvlL6FInODtRKrFeRvH74iiPyk=; b=NwMT36vbOWxoGrlkcb8QUu6XYQlUvWMJEj8IWewuv9eNvvyOUEVO4tL79ozA9vQDcQ yKgKfCy/Rmsg5YxCAFtscDPXdbcQBr7RPprWyrlKzHXLnLIseFFV9FGdbqEb958ZkD/5 JXEQrMgqTMZF3QEtunjmuzWmaKUiZs6cO9sd7OYmTLR9VcZbf14PSwL+nTZ7D+7G/nTF 8gvFAjEqzaJKDuaEabrr9stcBIqSogn5E7U0QMsVqUfQBX5FIVuNECzoTzj3C+R2EO/S 85m9qmv8qSrhtKPx65xBJwsxd2A5mu+gsA5uPW0h+XJ7XEHCZ/6HJpGgTCMnpgyTcIZZ UutA== X-Gm-Message-State: ALyK8tK3v203+yiTzwm4vOWQ0ZXRFIAmKEb6/PHO9CmR+4yD/XjDd4nKWMp2rvRcQ0/U1KEw6s+c1Z6OiK6KWPRT X-Received: by 10.107.129.18 with SMTP id c18mr8158208iod.102.1466220143825; Fri, 17 Jun 2016 20:22:23 -0700 (PDT) MIME-Version: 1.0 Received: by 10.36.134.68 with HTTP; Fri, 17 Jun 2016 20:22:04 -0700 (PDT) In-Reply-To: <20160616001040.GA5026@fedora-21-dvm> References: <20160616001040.GA5026@fedora-21-dvm> From: Bram Cohen Date: Fri, 17 Jun 2016 20:22:04 -0700 Message-ID: To: Peter Todd Content-Type: multipart/alternative; boundary=001a113f970ad5eda4053584fa92 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Merkle trees and mountain ranges X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 18 Jun 2016 03:22:25 -0000 --001a113f970ad5eda4053584fa92 Content-Type: text/plain; charset=UTF-8 On Wed, Jun 15, 2016 at 5:10 PM, Peter Todd 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. --001a113f970ad5eda4053584fa92 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On W= ed, 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 th= e
> utxo commitments trail a bit. Computing utxo commitments takes a certa= in
> amount of time, too much to hold up block propagation but still hopefu= lly
> vastly less than the average amount of time between blocks. Trailing b= y a
> single block is probably a bad idea because you sometimes get blocks b= ack
> 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 exces= sive
> - would do a perfectly good job of keeping latency from every becoming= an
> issue. Smaller commitments for the utxos added and removed in each blo= ck
> alone could be added without any significant performance penalty. That= way
> all blocks would have sufficient commitments for a completely up to da= te
> proofs of inclusion and exclusion. This is not a controversial approac= h.

Agreed - regardless of approach adding latency to commitment calcula= tions 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! I= f roots of what's added and deleted in each block are added as well, th= en a proof of inclusion can be done by having a proof of inclusion of the t= railing utxo set followed by a proof of exclusion from all the following de= letion sets, or a proof of inclusion in one of the single block addition se= ts 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.

<= div>This does make proofs larger (except in the case of recent deletions an= d maybe recent additions) and adds complexity, so it shouldn't be done = unless necessary. But validation before block propagation needs to be extre= mely fast, so for utxo roots this trick is probably both necessary and suff= icient.

--001a113f970ad5eda4053584fa92--