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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <akaramaoun@gmail.com>) id 1Z4siC-0000jJ-Bs
for bitcoin-development@lists.sourceforge.net;
Tue, 16 Jun 2015 15:23:40 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.223.182 as permitted sender)
client-ip=209.85.223.182; envelope-from=akaramaoun@gmail.com;
helo=mail-ie0-f182.google.com;
Received: from mail-ie0-f182.google.com ([209.85.223.182])
by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1Z4siA-0000Hs-Un
for bitcoin-development@lists.sourceforge.net;
Tue, 16 Jun 2015 15:23:40 +0000
Received: by iebgx4 with SMTP id gx4so15115811ieb.0
for <bitcoin-development@lists.sourceforge.net>;
Tue, 16 Jun 2015 08:23:33 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.107.36.84 with SMTP id k81mr1238167iok.35.1434468213573;
Tue, 16 Jun 2015 08:23:33 -0700 (PDT)
Sender: akaramaoun@gmail.com
Received: by 10.64.20.229 with HTTP; Tue, 16 Jun 2015 08:23:33 -0700 (PDT)
In-Reply-To: <CAL8tG=k90nzt9w99QjSx5R=+LeBxkfVvcEvcNAyVkJHkaQZAgg@mail.gmail.com>
References: <CAL8tG==LG=xC_DzOaghbGGKab4=UVpGLQV7781pU4wg+WnFdMg@mail.gmail.com>
<CAPg+sBjqQ66f1Rmhi9HOBYP5BDjBHvTNPpUN-y3o-KX8dXBMhg@mail.gmail.com>
<557D2571.601@gmail.com>
<CAL8tG=kEv9AfQM+1Rv+tqBujFEjCp+BsjQ-1s7eJC-usogFFqw@mail.gmail.com>
<CAPg+sBjrSed4r+8-d2RGBVhbzaXxX+o=qqw2u-2jpF2RUqmEmA@mail.gmail.com>
<CANEZrP1D0AN_iRobD2RYXHCCWhU7Vk6yZ35+ytsQ0zonSCG_HQ@mail.gmail.com>
<CAL8tG=k90nzt9w99QjSx5R=+LeBxkfVvcEvcNAyVkJHkaQZAgg@mail.gmail.com>
Date: Tue, 16 Jun 2015 15:23:33 +0000
X-Google-Sender-Auth: 3RRV21iPbxTKm6BUIhuPn9_gL1I
Message-ID: <CAL8tG=mVJk3or0C5RbmJWiA=9+sh+Dgje7fkCZRhO3nYK1KOhA@mail.gmail.com>
From: Andrew <onelineproof@gmail.com>
To: Mike Hearn <mike@plan99.net>
Content-Type: multipart/alternative; boundary=001a114027a44fcef90518a428d5
X-Spam-Score: -0.6 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(akaramaoun[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 HTML_MESSAGE BODY: HTML included in message
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1Z4siA-0000Hs-Un
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Scaling Bitcoin with Subchains
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Tue, 16 Jun 2015 15:23:40 -0000
--001a114027a44fcef90518a428d5
Content-Type: text/plain; charset=UTF-8
Let me ask a simpler question. How do you prove the state of the UTXO
database corresponding to your wallet? With my subchain method, all the
addresses in a wallet can be constrained to a path of subchains, so the
proof is O(log n). Yes, I know some people will say that it is not really a
proof because I didn't verify the transactions involving sibling chains
outside my path of chains. But the protocol is "parent chain always decides
in case of conflict". And the parent chains will have an incentive to be
careful with what child blocks they commit to as they will be merge mining
the (direct) child chains. Yes, the parents can make a mistake with some
really deep children chain transactions, but the deeper you go, the less
value the transactions, and the less important. Also, the children of the
parents are parents themselves so they will have incentive to be careful
with what child chains they commit to. So recursively, the system takes
care of itself.
I challenge anyone to come up with a <= O(log n) proof that each address
(output) they have in their wallet really has the balance they think it
has. If someone can do this, then maybe I will drop this idea. Actually,
rusty asked this on #bitcoin-wizards last night and no one was able to
answer it.
On Mon, Jun 15, 2015 at 6:00 PM, Andrew <onelineproof@gmail.com> wrote:
> Pieter: I kind of see your point (but I think you're missing some key
> points). You mean just download all the headers and then just verify the
> transactions you filter out by using their corresponding merkle trees,
> right? But still, I don't think that would scale as well as with the tree
> structure I propose. Because, firstly, you don't really need the headers of
> the sibling chains. You just need the headers of the parent chains since
> the parent verifies all the siblings. All you really need in a typical
> (non-mining) situation is the headers or full blocks in one path going down
> the tree starting from the root chain. So that means O(log n) needs to be
> stored (headers or blocks) (n the number of transaction on the network).
> With big blocks, you still need O(n) headers. I know headers are small, but
> still they take up space and verification time. Also, since you are storing
> the full blocks on the chains you want, you are validating the headers of
> those blocks and you are sure that you are seeing all transactions on those
> blocks. And if certain addresses must stay on those blocks, you will know
> that you are catching all of the transactions corresponding to those
> blocks. If you just filter out based on addresses or other criteria, you
> can be denied some of those transactions by full nodes, and you may not
> know about it. Say for example, your government representative publishes on
> of his public addresses that is used for paying for expenses. Then with my
> system, you can be sure to catch every transaction being spent from that
> address (or UTXO or whatever you want to call it). If you just filter on
> any transaction that includes that address, you may not catch all of those
> transactions. Same with incoming funds.
>
> There are also advantages for mining decentralization as I have explained
> in my previous posts. So still not sure you are right here...
>
> Thanks
>
> On Mon, Jun 15, 2015 at 5:18 PM, Mike Hearn <mike@plan99.net> wrote:
>
>> It's simple: either you care about validation, and you must validate
>>> everything, or you don't, and you don't validate anything.
>>>
>> Pedantically: you could validate a random subset of all scripts, to give
>> yourself probabilistic verification rather than full vs SPV. If enough
>> people do it with a large enough subset the probability of a problem being
>> detected goes up a lot. You still pay the cost of the database updates.
>>
>> But your main point is of course completely right, that side chains are
>> not a way to scale up.
>>
>
>
>
> --
> PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
>
--
PGP: B6AC 822C 451D 6304 6A28 49E9 7DB7 011C D53B 5647
--001a114027a44fcef90518a428d5
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Let me ask a simpler question. How do you prove the s=
tate of the UTXO database corresponding to your wallet? With my subchain me=
thod, all the addresses in a wallet can be constrained to a path of subchai=
ns, so the proof is O(log n). Yes, I know some people will say that it is n=
ot really a proof because I didn't verify the transactions involving si=
bling chains outside my path of chains. But the protocol is "parent ch=
ain always decides in case of conflict". And the parent chains will ha=
ve an incentive to be careful with what child blocks they commit to as they=
will be merge mining the (direct) child chains. Yes, the parents can make =
a mistake with some really deep children chain transactions, but the deeper=
you go, the less value the transactions, and the less important. Also, the=
children of the parents are parents themselves so they will have incentive=
to be careful with what child chains they commit to. So recursively, the s=
ystem takes care of itself.<br><br></div>I challenge anyone to come up with=
a <=3D O(log n) proof that each address (output) they have in their wal=
let really has the balance they think it has. If someone can do this, then =
maybe I will drop this idea. Actually, rusty asked this on #bitcoin-wizards=
last night and no one was able to answer it.<br></div><div class=3D"gmail_=
extra"><br><div class=3D"gmail_quote">On Mon, Jun 15, 2015 at 6:00 PM, Andr=
ew <span dir=3D"ltr"><<a href=3D"mailto:onelineproof@gmail.com" target=
=3D"_blank">onelineproof@gmail.com</a>></span> wrote:<br><blockquote cla=
ss=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pa=
dding-left:1ex"><div dir=3D"ltr">Pieter: I kind of see your point (but I th=
ink you're missing some key points). You mean just download all the hea=
ders and then just verify the transactions you filter out by using their co=
rresponding merkle trees, right? But still, I don't think that would sc=
ale as well as with the tree structure I propose. Because, firstly, you don=
't really need the headers of the sibling chains. You just need the hea=
ders of the parent chains since the parent verifies all the siblings. All y=
ou really need in a typical (non-mining) situation is the headers or full b=
locks in one path going down the tree starting from the root chain. So that=
means O(log n) needs to be stored (headers or blocks) (n the number of tra=
nsaction on the network). With big blocks, you still need O(n) headers. I k=
now headers are small, but still they take up space and verification time. =
Also, since you are storing the full blocks on the chains you want, you are=
validating the headers of those blocks and you are sure that you are seein=
g all transactions on those blocks. And if certain addresses must stay on t=
hose blocks, you will know that you are catching all of the transactions co=
rresponding to those blocks. If you just filter out based on addresses or o=
ther criteria, you can be denied some of those transactions by full nodes, =
and you may not know about it. Say for example, your government representat=
ive publishes on of his public addresses that is used for paying for expens=
es. Then with my system, you can be sure to catch every transaction being s=
pent from that address (or UTXO or whatever you want to call it). If you ju=
st filter on any transaction that includes that address, you may not catch =
all of those transactions. Same with incoming funds.<br><br>There are also =
advantages for mining decentralization as I have explained in my previous p=
osts. So still not sure you are right here...<br><br>Thanks<br></div><div c=
lass=3D"gmail_extra"><div><div class=3D"h5"><br><div class=3D"gmail_quote">=
On Mon, Jun 15, 2015 at 5:18 PM, Mike Hearn <span dir=3D"ltr"><<a href=
=3D"mailto:mike@plan99.net" target=3D"_blank">mike@plan99.net</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"><div dir=3D"ltr"><div class=3D"g=
mail_extra"><div class=3D"gmail_quote"><span><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
><p dir=3D"ltr">It's simple: either you care about validation, and you =
must validate everything, or you don't, and you don't validate anyt=
hing.</p></blockquote></span><div>Pedantically: you could validate a random=
subset of all scripts, to give yourself probabilistic verification rather =
than full vs SPV. If enough people do it with a large enough subset the pro=
bability of a problem being detected goes up a lot. You still pay the cost =
of the database updates.</div><div><br></div><div>But your main point is of=
course completely right, that side chains are not a way to scale up.=C2=A0=
<br></div></div></div></div>
</blockquote></div><br><br clear=3D"all"><br></div></div><span class=3D"">-=
- <br><div>PGP: B6AC 822C 451D 6304 6A28 =C2=A049E9 7DB7 011C D53B 5647</di=
v>
</span></div>
</blockquote></div><br><br clear=3D"all"><br>-- <br><div class=3D"gmail_sig=
nature">PGP: B6AC 822C 451D 6304 6A28 =C2=A049E9 7DB7 011C D53B 5647</div>
</div>
--001a114027a44fcef90518a428d5--
|