1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 419DD71
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 18 Jun 2016 03:22:24 +0000 (UTC)
Received: by mail-io0-f170.google.com with SMTP id n127so92240375iof.3
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <CA+KqGkosGrWQ2Lpg3Ptc+UyidK7H4_HLQ_QWx2DOAFRmLkv4zQ@mail.gmail.com>
<20160616001040.GA5026@fedora-21-dvm>
From: Bram Cohen <bram@bittorrent.com>
Date: Fri, 17 Jun 2016 20:22:04 -0700
Message-ID: <CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
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 <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <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.
--001a113f970ad5eda4053584fa92
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On W=
ed, Jun 15, 2016 at 5:10 PM, Peter Todd <span dir=3D"ltr"><<a href=3D"ma=
ilto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>></span=
> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex"><span class=3D"">On Tue, Jun 14,=
2016 at 05:14:23PM -0700, Bram Cohen via bitcoin-dev wrote:<br></span><spa=
n class=3D""><br>
> The fundamental approach to handling the latency problem is to have th=
e<br>
> utxo commitments trail a bit. Computing utxo commitments takes a certa=
in<br>
> amount of time, too much to hold up block propagation but still hopefu=
lly<br>
> vastly less than the average amount of time between blocks. Trailing b=
y a<br>
> single block is probably a bad idea because you sometimes get blocks b=
ack<br>
> to back, but you never get blocks back to back to back to back. Having=
the<br>
> utxo set be trailing by a fixed amount - five blocks is probably exces=
sive<br>
> - would do a perfectly good job of keeping latency from every becoming=
an<br>
> issue. Smaller commitments for the utxos added and removed in each blo=
ck<br>
> alone could be added without any significant performance penalty. That=
way<br>
> all blocks would have sufficient commitments for a completely up to da=
te<br>
> proofs of inclusion and exclusion. This is not a controversial approac=
h.<br>
<br>
</span>Agreed - regardless of approach adding latency to commitment calcula=
tions of<br>
all kinds is something I think we all agree can work in principle, although=
<br>
obviously it should be a last resort technique when optimization fails.<br>=
</blockquote><div><br></div><div>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><div><br></div><=
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.</div><div><br></div></div></div></div>
--001a113f970ad5eda4053584fa92--
|
