path: root/67/44529d394cd487e0512aa40dd4880b9efde4a1

Return-Path: <n210241048576@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id BF3BDA7F
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 16 Jan 2016 18:20:14 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f169.google.com (mail-io0-f169.google.com
	[209.85.223.169])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 92C7914B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 16 Jan 2016 18:20:13 +0000 (UTC)
Received: by mail-io0-f169.google.com with SMTP id q21so516028375iod.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 16 Jan 2016 10:20:13 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:date:message-id:subject:from:to:content-type;
	bh=Z9Irepp7PoRNYP7U5u9Ryv+WX5L2hjdpduNXf2Z+QTk=;
	b=G9mO1KYksZkGoDoehCj9R6a5QDdQICrXEhLIxuF9X723bijcRlUTELsNOl1GI3pDeR
	N4pLTJKKtv5bSuM3GUaD7CeIN78TGlSoXtO9M/Qcn2UmaWxuBmjtr3AnxoZZHCtMf7h7
	LNAHO0ccub+4byu0KS/Y1nvfeapAEUTkt/Srcii/mlJXHbblhKOOkX5eXBj/nHs0gK26
	xlTZHW628YXVJuVUtrOF4VIpb5RdvO5cGHMaKnyoMT9HeMaqFhl81JdcFla89TQtUXJo
	mPmyTg3byKCZFsXKK+/KiR/RYJxyb98aUjI2GDKjJadxl1ZKAwsj/0plwuH2s3mOB1tg
	rIww==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:date:message-id:subject:from:to
	:content-type;
	bh=Z9Irepp7PoRNYP7U5u9Ryv+WX5L2hjdpduNXf2Z+QTk=;
	b=ZSjv6/olcWMKGvXZvXnN2S1ubXqCy3aTpGz6yVrueJJyxrNDVKATydVsPCPom6G6VP
	KAOVtiCHUtx9iXPp6qmyCyImzbvUMvyysqEq/5WiJ0xgfDL9IooGFItNrr6wB1NE2v6Z
	sbYI9ls8/bz8VP9YSNYYg5Nvah2RHwIV4GSBwZDwvX3dhwHGVcjNMSrITo2tvimYzo0l
	HZZlpVNN0Wuigc2+ZWrQib6eFpnvDiYtL5jPTPOiHXZ7BQ0spuEI0AAqftYQxCuzmUq9
	d/KMghPHrYMMUiyyDDsR5rbvEW+f/vBr6qMwgEz+NXNeeyKR+Gs/qKNb4VNxxwmIW1jC
	nnkA==
X-Gm-Message-State: ALoCoQkOkV7w19LEM+LUm3JDdVd1mgSymRyOtknF4MnL95DLxO54ySE7U8z2mi7xXZ3XgPwotLKYKqG6FUytrzw6/lCEc6t47w==
MIME-Version: 1.0
X-Received: by 10.107.157.83 with SMTP id g80mr15403177ioe.187.1452968413099; 
	Sat, 16 Jan 2016 10:20:13 -0800 (PST)
Received: by 10.36.108.74 with HTTP; Sat, 16 Jan 2016 10:20:13 -0800 (PST)
Date: Sat, 16 Jan 2016 10:20:13 -0800
Message-ID: <CALJjGitKqSPOCC32-HiVG+s159Gn4dLm+7v=60zoqr2_my21Pg@mail.gmail.com>
From: Robert Grosse <n210241048576@gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a11407aac2200b10529779250
X-Spam-Status: No, score=-2.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,
	FROM_LOCAL_DIGITS, FROM_LOCAL_HEX, 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
X-Mailman-Approved-At: Mon, 18 Jan 2016 06:05:05 +0000
Subject: [bitcoin-dev] [BIP Draft] A modest proposal to increase maximum
 transactions per block without requiring a hardfork
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: Sat, 16 Jan 2016 18:20:14 -0000

--001a11407aac2200b10529779250
Content-Type: text/plain; charset=UTF-8

Summary: This describes a new transaction format which allows most
transactions to take up less space (and thus fit more per block) and a
method to implement it requiring only a (non generalized) softfork.

= Compressed transactions =
This format is designed to allow the majority of transactions to take up
less space, by removing flexibility and unnecessary data. The requirements
to use a compressed transaction are

* Non-coinbase
* 1-8 inputs and 1-8 outputs
* Pay to pubkey hash only

Transactions which want to use arbitrary scripts or a larger number of
inputs and outputs can still use the existing transaction format.

A compressed transaction consists of
header byte, compressed inputs, compressed outputs, optional lock_time

header byte has the following format
* bit 7: Always 1, to make it easy to distinguish compressed and
uncompressed transactions
* bit 6: 1 if lock_time is used, otherwise 0
* bit 5-3: Number of inputs - 1
* bit 2-0: Number of outputs - 1

This saves 5+ bytes from omitting the version number and the input and
output count fields. Additionally, most transactions will not have
lock_time, saving another 4 bytes.

Compressed input:
previous transaction hash, index byte, signature, pubkey, optional
sequence_no

This has the following differences from a normal input: Index is only 1
byte, since it is at most 8 anyway. The top bit of the index byte indicates
whether the input has a sequence number. ScriptSig length is completely
omitted, and signature and public key are included directly, saving space
from the data push and check opcodes. And as before, sequence_no is
optional and usually omitted.

Compressed output:
compressed value (1-7 bytes), pubkeyhash

compressed value format: The high 3 bits of the first byte give the number
of following bytes. The lower 5 bits and the n following bytes comprise the
output value. The maximum possible value is 2099999997690000 satoshis,
which requires 7 bytes to encode, but most values will be far shorter. For
example, a value of 0.01 BTC could be encoded in just 3 bytes, saving 5.

As before the script length field is completely omitted, and the pubkeyhash
is included directly, without extra opcodes.


= Consensus =

Like all softforks, adoption by a minority of miners would cause problems.
Therefore, these changes would only take effect after a consensus. Miners
can advertise support for the new format by increment the version code.
Once X% of Y consecutive blocks have this version, the new changes take
effect. Users who do not upgrade will still work but will not always see
accurate balances in other addresses and miners who do not upgrade risk
mining an invalid block, encouraging them to upgrade.

= The Shadow Chain =

Now for the interesting part: Implementing the new format with only a
softfork. In order to qualify as a softfork, every valid block under the
new rules also has to be valid under the old rules.

Among other things this means that compressed transactions can't just be
included in place of an ordinary transaction in a block, since the legacy
(non-upgraded) clients will consider that invalid. Instead, they will be
hidden as extra data inside the coinbase transaction, which is allowed to
contain arbitrary data.

Additionally, in order to support interoperability between compressed and
uncompressed transactions, uncompressed transactions can hide compressed
inputs and ouputs inside of the normal inputs and outputs using a currently
unused opcode (OP_NOP1, hereafter referred to as OP_SHADOW). OP_SHADOW
isn't a script operation per se; instead it marked scripts that should be
interpreted differently under the new rules.


In the following, shadow input/output refers to a compressed input/output,
which is hidden as metadata and hence not visible to legacy clients.

The blockchain must also still be valid when all the hidden data is
ignored. When moving money from the visible to the shadow chain, there is
no problem, but when moving money back, things get trickier, since the
legacy client won't know about any of the shadow transactions. Therefore,
when sending money to the shadow chain, the transaction includes a
specially marked anyone-can-spend output. When moving money back from the
shadow chain, the transaction "spends" any available such outputs.

Since an arbitrary amount of splitting and combining can occur inside the
shadow chain, these will not be 1:1. Instead a pool of available ouputs is
maintained with a total balance equal to the total balance inside the
shadow chain. The validation rules of upgraded clients ensure that this is
always maintained. A legacy client may try to spend these outputs, but it
would fail validation under the new rules and quickly become orphaned.

= Sending money from the visible to the shadow chain =
An uncompressed transaction is created with a specially formatted output.

OP_SHADOW OP_PUSHDATA1 <shadow output>

Where <shadow output> is a compressed output using the format described in
the previous section.

A legacy client will interpret this as an anyone-can-spend output. An
upgraded client will see the OP_SHADOW and interpret this specially, rather
than as a normal script. Instead it will interpret the data as a compressed
output, and add it as a shadow UTXO, which can be spent by compressed
transactions. Additionally, it will note that the visible output can be
used later when withdrawing from the shadow chain.

= Sending money from the shadow chain to the visible chain =
An uncompressed transaction is created with a specially formatted input.

OP_SHADOW OP_PUSHDATA1 <shadow input>

Where <shadow input> is a compressed input using the format described in
the previous section.

The legacy client will interpret this as spending one of the
anyone-can-spend outputs from earlier. The upgraded client will see the
leading OP_SHADOW and recognize that it should be interpreted specially. It
will perform all the normal verification that <shadow input> is a valid
input and not already spent in the shadow chain, etc. Thus the blockchain
is seen as valid by both legacy and upgraded clients.

Note: These scripts are currently considered nonstandard and will not be
relayed by legacy clients. As part of implementing the new protocol,
upgraded clients will obviously be modified to relay these transactions.
Since the consensus step earlier ensures that these are a majority of the
network before the changes take effect, this shouldn't be much of a problem.

= Combining and splitting inputs =

The above illustrates the simplest case. In practice, it will often by the
case that the available pool of OP_SHADOW marked anyone-can-spend UTXOs
doesn't match up exactly with the amount being withdrawn.

If the amounts available are too small, the uncompressed transaction can
include multiple inputs. The first one will contain the shadow input data
as above, and the subsequent inputs will just say

OP_SHADOW OP_TRUE

Likewise, the left over change will be included as an extra output with the
script
OP_SHADOW

Each uncompressed transaction can include up to 8 shadow inputs and up to 8
shadow outputs. The validation rules require that the total amount of
marked anyone-can-spend outputs being spent and created matches up with the
total balance leaving and entering the shadow chain.

What if you want to create an actual anyone-can-spend output under the new
rules? Just include an empty script as before. Only scripts that begin with
OP_SHADOW take part in the shadow deposit/withdrawal process.

I hope I explained my idea well enough. It's fairly complex, but I think it
works. Unlike the "generalized softfork" proposals, this is a true
softfork, as the new blockchain is still valid under the old rules, just
interpreted a bit differently.

--001a11407aac2200b10529779250
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><span style=3D"font-size:12.8px">Summary: This describes a=
 new transaction format which allows most transactions to take up less spac=
e (and thus fit more per block) and a method to implement it requiring only=
 a (non generalized) softfork.</span><div style=3D"font-size:12.8px"><br></=
div><div style=3D"font-size:12.8px">=3D Compressed transactions =3D</div><d=
iv style=3D"font-size:12.8px">This format is designed to allow the majority=
 of transactions to take up less space, by removing flexibility and unneces=
sary data. The requirements to use a compressed transaction are</div><div s=
tyle=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">* Non-c=
oinbase</div><div style=3D"font-size:12.8px">* 1-8 inputs and 1-8 outputs</=
div><div style=3D"font-size:12.8px">* Pay to pubkey hash only</div><div sty=
le=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">Transacti=
ons which want to use arbitrary scripts or a larger number of inputs and ou=
tputs can still use the existing transaction format.</div><div style=3D"fon=
t-size:12.8px"><br></div><div style=3D"font-size:12.8px">A compressed trans=
action consists of</div><div style=3D"font-size:12.8px">header byte, compre=
ssed inputs, compressed outputs, optional lock_time</div><div style=3D"font=
-size:12.8px"><br></div><div style=3D"font-size:12.8px">header byte has the=
 following format</div><div style=3D"font-size:12.8px">* bit 7: Always 1, t=
o make it easy to distinguish compressed and uncompressed transactions</div=
><div style=3D"font-size:12.8px">* bit 6: 1 if lock_time is used, otherwise=
 0</div><div style=3D"font-size:12.8px">* bit 5-3: Number of inputs - 1</di=
v><div style=3D"font-size:12.8px">* bit 2-0: Number of outputs - 1</div><di=
v style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">This=
 saves 5+ bytes from omitting the version number and the input and output c=
ount fields. Additionally, most transactions will not have lock_time, savin=
g another 4 bytes.</div><div style=3D"font-size:12.8px"><br></div><div styl=
e=3D"font-size:12.8px">Compressed input:</div><div style=3D"font-size:12.8p=
x">previous transaction hash, index byte, signature, pubkey, optional seque=
nce_no</div><div style=3D"font-size:12.8px"><br></div><div style=3D"font-si=
ze:12.8px">This has the following differences from a normal input: Index is=
 only 1 byte, since it is at most 8 anyway. The top bit of the index byte i=
ndicates whether the input has a sequence number. ScriptSig length is compl=
etely omitted, and signature and public key are included directly, saving s=
pace from the data push and check opcodes. And as before, sequence_no is op=
tional and usually omitted.</div><div style=3D"font-size:12.8px"><br></div>=
<div style=3D"font-size:12.8px">Compressed output:</div><div style=3D"font-=
size:12.8px">compressed value (1-7 bytes), pubkeyhash</div><div style=3D"fo=
nt-size:12.8px"><br></div><div style=3D"font-size:12.8px">compressed value =
format: The high 3 bits of the first byte give the number of following byte=
s. The lower 5 bits and the n following bytes comprise the output value. Th=
e maximum possible value is=C2=A02099999997690000 satoshis, which requires =
7 bytes to encode, but most values will be far shorter. For example, a valu=
e of 0.01 BTC could be encoded in just 3 bytes, saving 5.</div><div style=
=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">As before t=
he script length field is completely omitted, and the pubkeyhash is include=
d directly, without extra opcodes.=C2=A0</div><div style=3D"font-size:12.8p=
x"><br></div><div style=3D"font-size:12.8px"><br></div><div style=3D"font-s=
ize:12.8px">=3D Consensus =3D=C2=A0</div><div style=3D"font-size:12.8px"><b=
r></div><div style=3D"font-size:12.8px">Like all softforks, adoption by a m=
inority of miners would cause problems. Therefore, these changes would only=
 take effect after a consensus. Miners can advertise support for the new fo=
rmat by increment the version code. Once X% of Y consecutive blocks have th=
is version, the new changes take effect. Users who do not upgrade will stil=
l work but will not always see accurate balances in other addresses and min=
ers who do not upgrade risk mining an invalid block, encouraging them to up=
grade.</div><div style=3D"font-size:12.8px"><br></div><div style=3D"font-si=
ze:12.8px">=3D The Shadow Chain =3D=C2=A0</div><div style=3D"font-size:12.8=
px"><br></div><div style=3D"font-size:12.8px">Now for the interesting part:=
 Implementing the new format with only a softfork. In order to qualify as a=
 softfork, every valid block under the new rules also has to be valid under=
 the old rules.=C2=A0</div><div style=3D"font-size:12.8px"><br></div><div s=
tyle=3D"font-size:12.8px">Among other things this means that compressed tra=
nsactions can&#39;t just be included in place of an ordinary transaction in=
 a block, since the legacy (non-upgraded) clients will consider that invali=
d. Instead, they will be hidden as extra data inside the coinbase transacti=
on, which is allowed to contain arbitrary data.=C2=A0</div><div style=3D"fo=
nt-size:12.8px"><br></div><div style=3D"font-size:12.8px">Additionally, in =
order to support interoperability between compressed and uncompressed trans=
actions, uncompressed transactions can hide compressed inputs and ouputs in=
side of the normal inputs and outputs using a currently unused opcode (OP_N=
OP1, hereafter referred to as OP_SHADOW). OP_SHADOW isn&#39;t a script oper=
ation per se; instead it marked scripts that should be interpreted differen=
tly under the new rules.</div><div style=3D"font-size:12.8px"><br></div><di=
v style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">In t=
he following, shadow input/output refers to a compressed input/output, whic=
h is hidden as metadata and hence not visible to legacy clients.=C2=A0<br><=
/div><div style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8=
px">The blockchain must also still be valid when all the hidden data is ign=
ored. When moving money from the visible to the shadow chain, there is no p=
roblem, but when moving money back, things get trickier, since the legacy c=
lient won&#39;t know about any of the shadow transactions. Therefore, when =
sending money to the shadow chain, the transaction includes a specially mar=
ked anyone-can-spend output. When moving money back from the shadow chain, =
the transaction &quot;spends&quot; any available such outputs.=C2=A0</div><=
div style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">Si=
nce an arbitrary amount of splitting and combining can occur inside the sha=
dow chain, these will not be 1:1. Instead a pool of available ouputs is mai=
ntained with a total balance equal to the total balance inside the shadow c=
hain. The validation rules of upgraded clients ensure that this is always m=
aintained. A legacy client may try to spend these outputs, but it would fai=
l validation under the new rules and quickly become orphaned.</div><div sty=
le=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">=3D Sendi=
ng money from the visible to the shadow chain =3D</div><div style=3D"font-s=
ize:12.8px">An uncompressed transaction is created with a specially formatt=
ed output.</div><div style=3D"font-size:12.8px"><br></div><div style=3D"fon=
t-size:12.8px">OP_SHADOW OP_PUSHDATA1 &lt;shadow output&gt;</div><div style=
=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">Where &lt;s=
hadow output&gt; is a compressed output using the format described in the p=
revious section.</div><div style=3D"font-size:12.8px"><br></div><div style=
=3D"font-size:12.8px">A legacy client will interpret this as an anyone-can-=
spend output. An upgraded client will see the OP_SHADOW and interpret this =
specially, rather than as a normal script. Instead it will interpret the da=
ta as a compressed output, and add it as a shadow UTXO, which can be spent =
by compressed transactions. Additionally, it will note that the visible out=
put can be used later when withdrawing from the shadow chain.</div><div sty=
le=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">=3D Sendi=
ng money from the shadow chain to the visible chain =3D</div><div style=3D"=
font-size:12.8px">An uncompressed transaction is created with a specially f=
ormatted input.<br></div><div style=3D"font-size:12.8px"><br></div><div sty=
le=3D"font-size:12.8px">OP_SHADOW OP_PUSHDATA1 &lt;shadow input&gt;</div><d=
iv style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">Whe=
re &lt;shadow input&gt; is a compressed input using the format described in=
 the previous section.<br></div><div style=3D"font-size:12.8px"><br></div><=
div style=3D"font-size:12.8px">The legacy client will interpret this as spe=
nding one of the anyone-can-spend outputs from earlier. The upgraded client=
 will see the leading OP_SHADOW and recognize that it should be interpreted=
 specially. It will perform all the normal verification that &lt;shadow inp=
ut&gt; is a valid input and not already spent in the shadow chain, etc. Thu=
s the blockchain is seen as valid by both legacy and upgraded clients.</div=
><div style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">=
Note: These scripts are currently considered nonstandard and will not be re=
layed by legacy clients. As part of implementing the new protocol, upgraded=
 clients will obviously be modified to relay these transactions. Since the =
consensus step earlier ensures that these are a majority of the network bef=
ore the changes take effect, this shouldn&#39;t be much of a problem.</div>=
<div style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">=
=3D Combining and splitting inputs =3D=C2=A0</div><div style=3D"font-size:1=
2.8px"><br></div><div style=3D"font-size:12.8px">The above illustrates the =
simplest case. In practice, it will often by the case that the available po=
ol of OP_SHADOW marked anyone-can-spend UTXOs doesn&#39;t match up exactly =
with the amount being withdrawn.=C2=A0</div><div style=3D"font-size:12.8px"=
><br></div><div style=3D"font-size:12.8px">If the amounts available are too=
 small, the uncompressed transaction can include multiple inputs. The first=
 one will contain the shadow input data as above, and the subsequent inputs=
 will just say=C2=A0</div><div style=3D"font-size:12.8px"><br></div><div st=
yle=3D"font-size:12.8px">OP_SHADOW OP_TRUE</div><div style=3D"font-size:12.=
8px"><br></div><div style=3D"font-size:12.8px">Likewise, the left over chan=
ge will be included as an extra output with the script</div><div style=3D"f=
ont-size:12.8px">OP_SHADOW</div><div style=3D"font-size:12.8px"><br></div><=
div style=3D"font-size:12.8px">Each uncompressed transaction can include up=
 to 8 shadow inputs and up to 8 shadow outputs. The validation rules requir=
e that the total amount of marked anyone-can-spend outputs being spent and =
created matches up with the total balance leaving and entering the shadow c=
hain.=C2=A0</div><div style=3D"font-size:12.8px"><br></div><div style=3D"fo=
nt-size:12.8px">What if you want to create an actual anyone-can-spend outpu=
t under the new rules? Just include an empty script as before. Only scripts=
 that begin with OP_SHADOW take part in the shadow deposit/withdrawal proce=
ss.<br></div><div style=3D"font-size:12.8px"><br></div><div style=3D"font-s=
ize:12.8px">I hope I explained my idea well enough. It&#39;s fairly complex=
, but I think it works. Unlike the &quot;generalized softfork&quot; proposa=
ls, this is a true softfork, as the new blockchain is still valid under the=
 old rules, just interpreted a bit differently.</div></div>

--001a11407aac2200b10529779250--