Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BF3BDA7F for ; 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 ; Sat, 16 Jan 2016 18:20:13 +0000 (UTC) Received: by mail-io0-f169.google.com with SMTP id q21so516028375iod.0 for ; 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: From: Robert Grosse 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 Where 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 Where 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 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
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.

=3D Compressed transactions =3D
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

* Non-c= oinbase
* 1-8 inputs and 1-8 outputs
* Pay to pubkey hash only

Transacti= ons which want to use arbitrary scripts or a larger number of inputs and ou= tputs can still use the existing transaction format.

A compressed trans= action consists of
header byte, compre= ssed inputs, compressed outputs, optional lock_time

header byte has the= following format
* bit 7: Always 1, t= o 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 c= ount fields. Additionally, most transactions will not have lock_time, savin= g another 4 bytes.

Compressed input:
previous transaction hash, index byte, signature, pubkey, optional seque= nce_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 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.

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

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.

As before t= he script length field is completely omitted, and the pubkeyhash is include= d directly, without extra opcodes.=C2=A0


=3D Consensus =3D=C2=A0
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.

=3D The Shadow Chain =3D=C2=A0

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

Among other things this means that compressed tra= nsactions can'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

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't a script oper= ation per se; instead it marked scripts that should be interpreted differen= tly under the new rules.


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
<= /div>

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'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 "spends" any available such outputs.=C2=A0
<= 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.

=3D Sendi= ng money from the visible to the shadow chain =3D
An uncompressed transaction is created with a specially formatt= ed output.

OP_SHADOW OP_PUSHDATA1 <shadow output>

Where <s= hadow output> is a compressed output using the format described in the p= revious 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 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.

=3D Sendi= ng money from the shadow chain to the visible chain =3D
An uncompressed transaction is created with a specially f= ormatted input.

OP_SHADOW OP_PUSHDATA1 <shadow input>

Whe= re <shadow input> is a compressed input using the format described in= the previous section.

<= 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 <shadow inp= ut> 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.

= 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't be much of a problem.
=

= =3D Combining and splitting inputs =3D=C2=A0

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't match up exactly = with the amount being withdrawn.=C2=A0

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

OP_SHADOW OP_TRUE

Likewise, the left over chan= ge will be included as an extra output with the script
OP_SHADOW

<= 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

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.

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