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
|
Return-Path: <cserveny.tamas@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id ADFD8D49
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 1 Sep 2017 12:47:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f49.google.com (mail-vk0-f49.google.com
[209.85.213.49])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0A15EB0
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 1 Sep 2017 12:47:19 +0000 (UTC)
Received: by mail-vk0-f49.google.com with SMTP id z187so325765vkd.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 01 Sep 2017 05:47:19 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=4bn+MiU/4GqNQHUHfYTMiIfM3pn8PN0SmUp2f5jv6q4=;
b=st6vzzK+IVnD/ha/hZIpQTyd6fCFFs38mcq1DE3rQ6VhNeIFCgaLArW6VWY4Dq0AkM
wuuGn/uUFjG81RrBvyOjPA+MQOWrH55MNdNNtBfDeb/F1DF6Bx9QIV0KkGiovQUZphKu
vssGGaQNd8NV+xsF5kNIRG6hIvK561K2i6HiQ6dQn2GtE1TNn1vlyvlc/YcfaAho4Wc0
FKblh8r6uuWhrn/N2slnyusaWZ9LYI3Oq8mSF8gAPX3MLO2yRmuku2L+6Q9IIlUwHKtb
FHTpAjlETk52Y2jtYw94qWPFQj3oDNBWqC3ykdr5K4g87Varfn7U279eGyoJ4OTFgbWz
SO1Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=4bn+MiU/4GqNQHUHfYTMiIfM3pn8PN0SmUp2f5jv6q4=;
b=V4AvVqIPd3oWyd8gtT76a+ikvD5+6ZBlqnuevOgHZufHBdXtkVBp6PeB1tvyQhr4Q/
bhYf/v0ayFTxayKO2xu/9uKXaeUHBiYzb+zj2+sohNLKrAwShdtOcnCVt6z5eZIcL2vt
cI+hCKZStASL6GI/c0UvA7sGYYGmtgbOqrV1XN80IvrcO+op0hlyejwEBvrcdPdiigM1
JGeAFCqCD2LvPuQFKuvPrMeBafOCcqrv5V9tSro0ZmFhps1O2BtCEJjwDLQ/I851fDNH
aB8TYZcLJWswCSUS5y2SMaHu4ezL3OghvfUQuAauk5++vftvWHU93l/Fg5QFlDhcmaNH
siAA==
X-Gm-Message-State: AHPjjUiIE6Ioa0qnxwAXko8KQiw56GPXgRk48Mn+qWEItoXf4Rl/7mGB
Tr8o/HQkCrxCgzzDwphDHA1Fntfqdt2r
X-Google-Smtp-Source: ADKCNb7jUVB0nrCcnFxMeUvAqxwFpjLTk4sDNJP+RX5Dma7F1T64E+LOBp/upqAll015IW7ffZYf0pRyRpUKrNcTGko=
X-Received: by 10.31.94.136 with SMTP id s130mr1163132vkb.170.1504270038814;
Fri, 01 Sep 2017 05:47:18 -0700 (PDT)
MIME-Version: 1.0
From: Cserveny Tamas <cserveny.tamas+bc@gmail.com>
Date: Fri, 01 Sep 2017 12:47:08 +0000
Message-ID: <CACY+MSO8PM89VTtKfuZiQGvAs7a7R6_4mY+onhZh9KnvwxW2uw@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="001a114e5e384f543f05582029c1"
X-Spam-Status: No, score=0.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Fri, 01 Sep 2017 12:54:50 +0000
Subject: [bitcoin-dev] Horizontal scaling of blockchain
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: Fri, 01 Sep 2017 12:47:20 -0000
--001a114e5e384f543f05582029c1
Content-Type: text/plain; charset="UTF-8"
Hi,
I was thinking about how to scale the block-chain.
The fundamental problem is that if the miners add capacity it will only
increase (protect) their share of block reward, but does not increase the
speed of transactions. This will only raise the fee in the long run with
the block reward decreasing.
The throughput is limited by the block size and the complexity. Changing
any of variables in the above equation was raised already many times and
there was no consensus on them.
The current chain is effectively single threaded. If we look around in the
sw industry how single threaded applications could be scaled, one viable
option emerge: horizontal scaling. This is an option if the problem can be
partitioned, and transactions in partitions could be processed alongside.
Number of partitions would be start with a fairly low number, something
between 2-10, but nothing is against setting it to a higher number later on
according to a schedule.
Partitioning key alternatives:
*Ordering on inputs:*
1) In this case transactions would need to be mined per input address
partition.
2) TX have inputs in partition 1 and 2, then needs a confirmation in both
partitions.
3) All partitioned chains have the same longest valid approach.
4) Only one chain needed to be considered for double spending, others are
invalid in case they contain that input.
This opens up questions like:
- how the fee will be shared? Fees per partition?
- Ensure a good hash function which spreads evenly, because the inputs
cannot be manipulated for load balancing
- What to do about half mined transactions (Maybe they should be two
transactions and then there is less effect about it, but payment won't be
atomic in both partitions)
*Ordering on transaction ids:*
1) Transactions would be partitioned by their TX-id. Maybe a field allowing
txid-s to match a given partition.
2) Creating blocks like this parallel would be safe for bonefide
transactions. A block will be created each 10 mins.
3) In order to get malicious/doublespent transactions out of the system
another layer must be introduced.
- This layer would be used to merge the parallel blocks. It would have to
refer all previous blocks considered for unspent inputs.
- Most of the blocks will merge just fine as normally block 1 and block 2
would not contain double spending. (of course malicious double spending
will revert speed to current levels, because the miner might have to drop a
block in the partition because it contains a spent input on another
stronger branch)
- The standard longest chain wins strategy would be used for validity on
the meta level
- Meta does not require mining, a branches can be added and they are valid
unless there are double spent inputs inside. Block inside this meta already
"paid for".
Generally both ways would have an effect on the block reward and
complexity, which is needs to be adjusted. (not to create more BTC at the
end, reduced hashing power on partitions.)
I think complexity is not an issue, the important thing is that we tune it
to 10mins / block rate per partition.
Activation could be done by creating the infrastructure first and using
only one partitions only, which is effectively the same as today. Then
activate partitions on a certain block according to a schedule. From that
block, partition enforcement will be active and the transactions will be
sorted to the right partition / chain.
It is easy to make new partitions, just need to activate them on branch
block number.
Closing partitions is a bit more complex in case of TX partitioned
transactions, but managed by the meta layer and activated at a certain
partition block. Maybe it is not even possible in case of input partitions.
I could imagine that it is too big change. Many cons and pros on partition
keys.
What is your opinion about it?
Cheers,
Tamas
--001a114e5e384f543f05582029c1
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hi,<div><br></div><div>I was thinking about how to scale t=
he block-chain.</div><div><br></div><div>The fundamental problem is that if=
the miners add capacity it will only increase (protect) their share of blo=
ck reward, but does not increase the speed of transactions. This will only =
raise the fee in the long run with the block reward decreasing.=C2=A0</div>=
<div>The throughput is limited by the block size and the complexity. Changi=
ng any of variables in the above equation was raised already many times and=
there was no consensus on them.=C2=A0</div><div><br></div><div>The current=
chain is effectively single threaded. If we look around in the sw industry=
how single threaded applications could be scaled, one viable option emerge=
: horizontal scaling. This is an option if the problem can be partitioned, =
and transactions in partitions could be processed alongside.=C2=A0</div><di=
v>Number of partitions would be start with a fairly low number, something b=
etween 2-10, but nothing is against setting it to a higher number later on =
according to a schedule.</div><div><br></div><div>Partitioning key alternat=
ives:</div><div><b>Ordering on inputs:</b>=C2=A0</div><div><br></div><div>1=
) In this case transactions would need to be mined per input address partit=
ion.=C2=A0</div><div>2) TX have inputs in partition 1 and 2, then needs a c=
onfirmation in both partitions.=C2=A0<br></div><div>3) All partitioned chai=
ns have the same longest valid approach.</div><div>4) Only one chain needed=
to be considered for double spending, others are invalid in case they cont=
ain that input.</div><div><br></div><div>This opens up questions like:<br><=
/div><div>- how the fee will be shared? Fees per partition?</div><div>- Ens=
ure a good hash function which spreads evenly, because the inputs cannot be=
manipulated for load balancing</div><div>- What to do about half mined tra=
nsactions (Maybe they should be two transactions and then there is less eff=
ect about it, but payment won't be atomic in both partitions)</div><div=
><br></div><div><b>Ordering on transaction ids:</b></div><div><br></div><di=
v>1) Transactions would be partitioned by their TX-id. Maybe a field allowi=
ng txid-s to match a given partition.<br></div><div>2) Creating blocks like=
this parallel would be safe for bonefide transactions. A block will be cre=
ated each 10 mins.<br></div><div>3) In order to get malicious/doublespent t=
ransactions out of the system another layer must be introduced.=C2=A0</div>=
<div>- This layer would be used to merge the parallel blocks. It would have=
to refer all previous blocks considered for unspent inputs.</div><div>- Mo=
st of the blocks will merge just fine as normally block 1 and block 2 would=
not contain double spending. (of course malicious double spending will rev=
ert speed to current levels, because the miner might have to drop a block i=
n the partition because it contains a spent input on another stronger branc=
h)</div><div>- The standard longest chain wins strategy would be used for v=
alidity on the meta level</div><div>- Meta does not require mining, a branc=
hes can be added and they are valid unless there are double spent inputs in=
side. Block inside this meta already "paid for".</div><div><br></=
div><div>Generally both ways would have an effect on the block reward and c=
omplexity, which is needs to be adjusted. (not to create more BTC at the en=
d, reduced hashing power on partitions.)</div><div><div>I think complexity =
is not an issue, the important thing is that we tune it to 10mins / block r=
ate per partition.=C2=A0</div><div><br></div>Activation could be done by cr=
eating the infrastructure first and using only one partitions only, which i=
s effectively the same as today. Then activate partitions on a certain bloc=
k according to a schedule. From that block, partition enforcement will be a=
ctive and the transactions will be sorted to the right partition / chain.<b=
r class=3D"inbox-inbox-Apple-interchange-newline"></div><div><br></div><div=
>It is easy to make new partitions, just need to activate them on branch bl=
ock number.=C2=A0</div><div>Closing partitions is a bit more complex in cas=
e of TX partitioned transactions, but managed by the meta layer and activat=
ed at a certain partition block. Maybe it is not even possible in case of i=
nput partitions.</div><div><br></div><div>I could imagine that it is too bi=
g change. Many cons and pros on partition keys.</div><div><br></div><div>Wh=
at is your opinion about it?</div><div><br></div><div>Cheers,</div><div><br=
></div><div>Tamas</div></div>
--001a114e5e384f543f05582029c1--
|