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
|
Return-Path: <loi.luuthe@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 86710BCA
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 9 Dec 2015 06:30:45 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ig0-f178.google.com (mail-ig0-f178.google.com
[209.85.213.178])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id BFF44107
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 9 Dec 2015 06:30:44 +0000 (UTC)
Received: by igcto18 with SMTP id to18so33628390igc.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 08 Dec 2015 22:30:44 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:from:date:message-id:subject:cc
:content-type; bh=Ja2oqgF1EfeWMpyYs97/eHELmbY6LqEyOvzAGJPa+0Y=;
b=MJwO0wn3vYWAMlXMLsTOO4UadmgyqUxOfbxHRhssQl7Wzxmv9nB63X35JPWgDMpmZ1
M5TH2wgyP3U+OyqGzEQ8AY0yIJ/nXUhptYy6v6/kd6eLj/euVAJznNecGRzwPbCO8rgJ
MW2bOa66uloFDf1bPVChSTJ2p0U+rTVKTBAa/qtvda3n4c97N/5gAWnrrNKZ+4cO3EmU
hwn3c6+X4orKGNgVXysrcT81lvgUDod4LHPFrrOD0PLeHmGZCtc7nfJH9Y0FozmVjmhL
3sNKTOTeHlgVp5EnmXDlXCSZOgTMzcRiugnVZFKoMek0A0qxzxjRMkQjK6pvwXmr5hJZ
Eufw==
X-Received: by 10.50.183.37 with SMTP id ej5mr8218122igc.95.1449642644223;
Tue, 08 Dec 2015 22:30:44 -0800 (PST)
MIME-Version: 1.0
Received: by 10.64.252.168 with HTTP; Tue, 8 Dec 2015 22:30:24 -0800 (PST)
In-Reply-To: <CABCnA7Wqz76m8qo5BYT41Z=hBH+fUfOc4xsFAGg=Niv7Jgkqsg@mail.gmail.com>
References: <CABCnA7Wqz76m8qo5BYT41Z=hBH+fUfOc4xsFAGg=Niv7Jgkqsg@mail.gmail.com>
From: Loi Luu <loi.luuthe@gmail.com>
Date: Wed, 9 Dec 2015 14:30:24 +0800
Message-ID: <CAJmQggC1X5Lgt4xGoMtBZ_v3hC2GXcYaj2FngV2_7A=TDfSuEg@mail.gmail.com>
Cc: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a1135e154dc60860526713a59
X-Spam-Status: No, score=-0.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
MALFORMED_FREEMAIL,
MISSING_HEADERS,RCVD_IN_DNSWL_LOW autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 09 Dec 2015 06:32:07 +0000
Subject: Re: [bitcoin-dev] Scaling by Partitioning
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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: Wed, 09 Dec 2015 06:30:45 -0000
--001a1135e154dc60860526713a59
Content-Type: text/plain; charset=UTF-8
Dear Akiva,
Its Loi Luu, one of the authors of the SCP protocol (
http://eprint.iacr.org/2015/1168.pdf ).
Before SCP, we had been thinking hard about how to do sharding efficiently
without degrading any security guarantee. A simple solution which splits
the coins, or TXs in to several partitions will just not work. You have to
answer more questions to have a good solutions. For example, I wonder in
your proposal, if a transaction spends a "coin" that ends in "1" and
creates a new coin that ends in "1", which partition should process the
transaction? What is the prior data needed to validate that kind of TXs?
The problem with other proposals, and probably yours as well, that we see
is that the amount of data that you need to broadcast immediately to the
network increases linearly with the number of TXs that the network can
process. Thus, sharding does not bring any advantage than simply using
other techniques to publish more blocks in one epoch (like Bitcoin-NG,
Ghost). The whole point of using sharding/ partition is to localize
the bandwidth used, and only broadcast only a minimal data to the network.
Clearly we are able to localize the bandwidth used with our SCP protocol.
The cost is that now recipients need to themselves verify whether a
transaction is double spending. However, we think that it is a reasonable
tradeoff, given the potential scalability that SCP can provides.
Thanks,
Loi Luu.
On Wed, Dec 9, 2015 at 12:27 AM, Akiva Lichtner via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Hello,
>
> I am seeking some expert feedback on an idea for scaling Bitcoin. As a
> brief introduction: I work in the payment industry and I have twenty years'
> experience in development. I have some experience with process groups and
> ordering protocols too. I think I understand Satoshi's paper but I admit I
> have not read the source code.
>
> The idea is to run more than one simultaneous chain, each chain defeating
> double spending on only part of the coin. The coin would be partitioned by
> radix (or modulus, not sure what to call it.) For example in order to
> multiply throughput by a factor of ten you could run ten parallel chains,
> one would work on coin that ends in "0", one on coin that ends in "1", and
> so on up to "9".
>
> The number of chains could increase automatically over time based on the
> moving average of transaction volume.
>
> Blocks would have to contain the number of the partition they belong to,
> and miners would have to round-robin through partitions so that an attacker
> would not have an unfair advantage working on just one partition.
>
> I don't think there is much impact to miners, but clients would have to
> send more than one message in order to spend money. Client messages will
> need to enumerate coin using some sort of compression, to save space. This
> seems okay to me since often in computing client software does have to
> break things up in equal parts (e.g. memory pages, file system blocks,) and
> the client software could hide the details.
>
> Best wishes for continued success to the project.
>
> Regards,
> Akiva
>
> P.S. I found a funny anagram for SATOSHI NAKAMOTO: "NSA IS OOOK AT MATH"
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
--001a1135e154dc60860526713a59
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><span style=3D"font-size:12.8000001907349px">Dear Akiva,</=
span><div style=3D"font-size:12.8000001907349px"><br></div><div style=3D"fo=
nt-size:12.8000001907349px">Its Loi Luu, one of the authors of the SCP prot=
ocol (<a href=3D"http://eprint.iacr.org/2015/1168.pdf" rel=3D"noreferrer" t=
arget=3D"_blank" style=3D"font-size:12.8000001907349px">http://eprint.iacr.=
org/2015/1168.pdf</a><span style=3D"font-size:12.8000001907349px">=C2=A0).<=
/span></div><div style=3D"font-size:12.8000001907349px"><span style=3D"font=
-size:12.8000001907349px"><br></span></div><div style=3D"font-size:12.80000=
01907349px"><span style=3D"font-size:12.8000001907349px">Before SCP, we had=
been thinking hard about how to do sharding efficiently without degrading =
any security guarantee. A simple solution which splits the coins, or TXs in=
to several partitions will just not work. You have to answer more question=
s to have a good solutions. For example, I wonder in your proposal, if a tr=
ansaction spends a "coin" that ends in "1" and creates =
a new coin that ends in "1", which partition should process the t=
ransaction? What is the prior data needed to validate that kind of TXs?</sp=
an></div><div style=3D"font-size:12.8000001907349px"><span style=3D"font-si=
ze:12.8000001907349px"><br></span></div><div style=3D"font-size:12.80000019=
07349px"><span style=3D"font-size:12.8000001907349px">The problem with othe=
r proposals, and probably yours as well,=C2=A0=C2=A0that we see is that the=
amount of data that you need to broadcast immediately to the network incre=
ases linearly with the number of TXs that the network can process. Thus, sh=
arding does not bring any advantage than simply using other techniques to p=
ublish more blocks in one epoch (like Bitcoin-NG, Ghost). The whole point o=
f using sharding/ partition is to localize the=C2=A0bandwidth=C2=A0used, an=
d only broadcast only a=C2=A0minimal=C2=A0data to the network.</span></div>=
<div style=3D"font-size:12.8000001907349px"><span style=3D"font-size:12.800=
0001907349px"><br></span></div><div style=3D"font-size:12.8000001907349px">=
<span style=3D"font-size:12.8000001907349px">Clearly we are able to localiz=
e the bandwidth used with our SCP protocol. The cost is that now=C2=A0recip=
ients=C2=A0need to=C2=A0</span><span style=3D"font-size:12.8000001907349px"=
>=C2=A0</span><span style=3D"font-size:12.8000001907349px">themselves=C2=A0=
verify whether a transaction is double spending. However, we think that=C2=
=A0it is=C2=A0a reasonable tradeoff, given the potential scalability that S=
CP can provides.</span></div><div class=3D"gmail_extra"><br clear=3D"all"><=
div><div class=3D"gmail_signature"><div dir=3D"ltr"><span style=3D"font-fam=
ily:arial,sans-serif;font-size:13px;border-collapse:collapse;color:rgb(136,=
136,136)"><span style=3D"color:rgb(0,0,102)"><div>Thanks,</div><div>Loi Luu=
.<br></div></span></span></div></div></div>
<br><div class=3D"gmail_quote">On Wed, Dec 9, 2015 at 12:27 AM, Akiva Licht=
ner via bitcoin-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lis=
ts.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation=
.org</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"lt=
r"><div><div><div><div><div><div><div><div>Hello,<br><br></div>I am seeking=
some expert feedback on an idea for scaling Bitcoin. As a brief introducti=
on: I work in the payment industry and I have twenty years' experience =
in development. I have some experience with process groups and ordering pro=
tocols too. I think I understand Satoshi's paper but I admit I have not=
read the source code.<br><br></div>The idea is to run more than one simult=
aneous chain, each chain defeating double spending on only part of the coin=
. The coin would be partitioned by radix (or modulus, not sure what to call=
it.) For example in order to multiply throughput by a factor of ten you co=
uld run ten parallel chains, one would work on coin that ends in "0&qu=
ot;, one on coin that ends in "1", and so on up to "9".=
<br><br></div>The number of chains could increase automatically over time b=
ased on the moving average of transaction volume.<br><br></div>Blocks would=
have to contain the number of the partition they belong to, and miners wou=
ld have to round-robin through partitions so that an attacker would not hav=
e an unfair advantage working on just one partition.<br></div><div><br></di=
v><div>I don't think there is much impact to miners, but clients would =
have to send more than one message in order to spend money. Client messages=
will need to enumerate coin using some sort of compression, to save space.=
This seems okay to me since often in computing client software does have t=
o break things up in equal parts (e.g. memory pages, file system blocks,) a=
nd the client software could hide the details.<br></div></div><div><br></di=
v><div>Best wishes for continued success to the project.<br></div><div><br>=
</div>Regards,<br></div>Akiva<br><br></div>P.S. I found a funny anagram for=
SATOSHI NAKAMOTO: "NSA IS OOOK AT MATH"<br><br></div>
<br>_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br></blockquote></div><br></div></div>
--001a1135e154dc60860526713a59--
|