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
|
Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 5E7D29D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 18 Jun 2016 22:09:36 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail149113.authsmtp.com (outmail149113.authsmtp.com
[62.13.149.113])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 6A9E79C
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 18 Jun 2016 22:09:35 +0000 (UTC)
Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247])
by punt24.authsmtp.com (8.14.2/8.14.2/) with ESMTP id u5IM9XuE074079;
Sat, 18 Jun 2016 23:09:33 +0100 (BST)
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
[52.5.185.120]) (authenticated bits=0)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id u5IM9UEX064633
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Sat, 18 Jun 2016 23:09:31 +0100 (BST)
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 4B9DA400E9;
Sat, 18 Jun 2016 22:07:31 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id 8400820278; Sat, 18 Jun 2016 18:09:29 -0400 (EDT)
Date: Sat, 18 Jun 2016 18:09:29 -0400
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@bittorrent.com>
Message-ID: <20160618220929.GA24713@fedora-21-dvm>
References: <CA+KqGkosGrWQ2Lpg3Ptc+UyidK7H4_HLQ_QWx2DOAFRmLkv4zQ@mail.gmail.com>
<20160616001040.GA5026@fedora-21-dvm>
<CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="IS0zKkzwUGydFO0o"
Content-Disposition: inline
In-Reply-To: <CA+KqGko2jW9999A9vkkBrM3EPb5OXYe4OPu0_Ot=fGnc7Cge-Q@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: 5581974b-35a1-11e6-bcde-0015176ca198
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdwoUEkAaAgsB AmAbWVdeUFR7WmE7 bghPaBtcak9QXgdq
T0pMXVMcUQARfBVk c3YeVB10dAYIeX5x ZkQsW3VTXU19cRRg
QUsFFHAHZDJmdTJM BBVFdwNVdQJNeEwU a1l3GhFYa3VsNCMk
FAgyOXU9MCtqYAFY WAIJIBoOW0sGBXY1 QRxKGDIyG1EMRiN7 NRUgJVMHdAAA
X-Authentic-SMTP: 61633532353630.1038:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 52.5.185.120/25
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,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 22:09:36 -0000
--IS0zKkzwUGydFO0o
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Fri, Jun 17, 2016 at 08:22:04PM -0700, Bram Cohen wrote:
> On Wed, Jun 15, 2016 at 5:10 PM, Peter Todd <pete@petertodd.org> wrote:
> > Agreed - regardless of approach adding latency to commitment calculatio=
ns
> > of
> > all kinds is something I think we all agree can work in principle, alth=
ough
> > obviously it should be a last resort technique when optimization fails.
> >
>=20
> 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.
>=20
> 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 unle=
ss
> necessary.
So, to be clear you're assuming that blocks commit to key:value maps of the
block contents, specifically a pre-block "UTXO deletion/things that this bl=
ock
spent" set? First of all, it's interesting how the much smaller dataset of a
pre-block key:value map would make L2/L3 caching optimizations much more li=
kely
to be relevant. :)
That type of solution would be very similar to the solutions treechains wou=
ld
need to prove coins haven't been doublespent. Basically, in treechains the
system as a whole is a datastructure indexed by time and prefix. So, if you
want to prove a valid spend you need to convince me of three things:
1. The coin existed as of time t1 at prefix p
2. At t2, p, a valid spend was published.
3. Between t1 and t2 at prefix p no other valid spend was published.
Paths to any prefix p as of time t, will have about log2(len(p)) size (beyo=
nd
the top-level chain), similar to your above suggestion. Of course, unlike y=
our
above suggestion, in treechains it's not clear if step #1 can be done witho=
ut
another n*log(N)-ish sized proof in a truly trustless environment!
> But validation before block propagation needs to be extremely
> fast, so for utxo roots this trick is probably both necessary and
> sufficient.
I'm _not_ of the optinion that validation before propagation needs to be do=
ne
at all - I think it's perfectly reasonable to propgate blocks that you have=
not
validated at all (beyond checking PoW as an anti-DoS measure). The time it
takes miners to start mining the next block - and collecting fees - is howe=
ver
very important.
In practice, I think we're mostly in agreement here, but because I'm happy =
to
propagate prior to validating I'd be ok with protocol designs that required
miners to have relatively large amounts of RAM - say 32GB - dedicated to UT=
XO
lookup because that wouldn't require relay nodes to also have those kinds of
resources available to them once validationless propagation was implemented.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--IS0zKkzwUGydFO0o
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJXZcaWAAoJEGOZARBE6K+ytI4H/2ifzMFzewtKW97h6SVMVD7l
xfSKnAIErFsJYPwjpUXCAL2cdMDTzwCBTvuRcErcAMwYrHodExx+bGyuju7hQbWg
XN3aGcXGsdIsl7U4JXVcvb1gwjg7PPHjWRb8lu7Qk4ai9hlVLGV20AYZwV2IIe6t
WesU3SVBr39OO1sTp1GVTNhwjQpxmqQwsYeIsRhwLV2FJul/fvU7EynI4UN0b09f
tya1f8/Tfyi52SBiKnWL2+Yla165q5ZG532j6FPsZhAhqQhAV/8+B4g5kAHCPLDR
Oi0ucVLOQeGg7jidzIUzyzh51q608OrB8AUDJKxVcPM9BzqbYBkdxFEhdhEmgwg=
=hPgB
-----END PGP SIGNATURE-----
--IS0zKkzwUGydFO0o--
|
