path: root/86/4ab307d4544ca190b6e3533498d688863ad71d

Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 46FA1B55
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 27 Jan 2017 20:36:17 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from sender163-mail.zoho.com (sender163-mail.zoho.com
	[74.201.84.163])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A691C15B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 27 Jan 2017 20:36:15 +0000 (UTC)
Received: from [10.8.8.2] (119246245241.ctinets.com [119.246.245.241]) by
	mx.zohomail.com with SMTPS id 1485549368382397.1743079740338;
	Fri, 27 Jan 2017 12:36:08 -0800 (PST)
From: Johnson Lau <jl2012@xbt.hk>
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_9E2F2FF1-9C72-4F5C-BF19-F4B2A195C4C7"
Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3259\))
Message-Id: <7FA94C9F-970F-4526-AD83-C04078FEDA60@xbt.hk>
Date: Sat, 28 Jan 2017 04:36:03 +0800
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
X-Mailer: Apple Mail (2.3259)
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: [bitcoin-dev] Consensus critical limits in Bitcoin protocol and
 proposed block resources limit accounting
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, 27 Jan 2017 20:36:17 -0000


--Apple-Mail=_9E2F2FF1-9C72-4F5C-BF19-F4B2A195C4C7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

There are many consensus critical limits scattered all over the Bitcoin =
protocol. The first part of this post is to analyse what the current =
limits are. These limits could be arranged into different categories:

1. Script level limit. Some limits are restricted to scripts, including =
size (10000 bytes), nOpCount (201), stack plus alt-stack size (1000), =
and stack push size (520). If these limits are passed, they won=E2=80=99t =
have any effects on the limits of the other levels.

2. Output value limit: any single output value must be >=3D0 and <=3D 21 =
million bitcoin

3. Transaction level limit: The only transaction level limit we have =
currently, is the total output value must be equal to or smaller than =
the total input value for non-coinbase tx.

4. Block level limit: there are several block level limits:
a. The total output value of all txs must be equal to or smaller than =
the total input value with block reward.
b. The serialised size including block header and transactions must not =
be over 1MB. (or 4,000,000 in terms of tx weight with segwit)
c. The total nSigOpCount must not be over 20,000 (or 80,000 nSigOpCost =
with segwit)

There is an unavoidable layer violation in terms of the block level =
total output value. However, all the other limits are restricted to its =
level. Particularly, the counting of nSigOp does not require execution =
of scripts. BIP109 (now withdrawn) tried to change this by implementing =
a block level SigatureHash limit and SigOp limit by counting the =
accurate value through running the scripts.

So currently, we have 2 somewhat independent block resources limits: =
weight and SigOp. A valid block must not exceed any of these limits. =
However, for miners trying to maximise the fees under these limits, they =
need to solve a non-linear equation. It=E2=80=99s even worse for wallets =
trying to estimate fees, as they have no idea what txs are miners trying =
to include. In reality, everyone just ignore SigOp for fee estimation, =
as the size/weight is almost always the dominant factor.

In order to not introduce further non-linearity with segwit, after =
examining different alternatives, we decided that the block weight limit =
should be a simple linear function:  3*base size + total size, which =
allows bigger block size and provides incentives to limit UTXO growth. =
With normal use, this allows up to 2MB of block size, and even more if =
multi-sig becomes more popular. A side effect is that allows a =
theoretical way to fill up the block to 4MB with mostly non-transaction =
data, but that=E2=80=99d only happen if a miner decide to do it due to =
non-standardness. (and this is actually not too bad, as witness could be =
pruned in the future)

Some also criticised that the weight accounting would make a =E2=80=9Csimp=
le 2MB hardfork=E2=80=9D more dangerous, as the theoretical limits will =
be 8MB which is too much. This is a complete straw man argument, as with =
a hardfork, one could introduce any rules at will, including =
revolutionising the calculation of block resources, as shown below.

=E2=80=94=E2=80=94=E2=80=94=E2=80=94=E2=80=94=E2=80=94=E2=80=94=E2=80=94=E2=
=80=94
Proposal: a new block resources limit accounting

Objectives:=20
1. linear fee estimation
2. a single, unified, block level limit for everything we want to limit
3. do not require expensive script evaluation

Assumptions:
1. the maximum base block size is about 1MB (for a hardfork with bigger =
block, it just needs to upscale the value)
2. a hardfork is done (despite some of these could also be done with a =
softfork)

Version 1: without segwit
The tx weight is the maximum of the following values:
=E2=80=94 Serialised size in byte
=E2=80=94 accurate nSigOpCount * 50 (statical counting of SigOp in =
scriptSig, redeemScript, and previous scriptPubKey, but not the new =
scriptPubKey)
The block level limit is 1,000,000

Although this looks similar to the existing approach, this actually =
makes the fee estimation a linear problem. Wallets may now calculate =
both values for a tx and take the maximum, and compare with other txs on =
the same basis. On the other hand, the total size and SigOpCount of a =
block may never go above the existing limits (1MB and 20000) no matter =
how the txs look like. (In some edge cases, the max block size might be =
smaller than 1MB, if the weight of some transactions is dominated by the =
SigOpCount)

Version 2: extending version 1 with segwit
The tx weight is the maximum of the following values:
=E2=80=94 Serialised size in byte * 2
=E2=80=94 Base size * 3 + total size
=E2=80=94 accurate SigOpCount * 50 (as a hardfork, segwit and non-segwit =
SigOp could be counted in the same way and no need to scale)=20
The block level limit is 4,000,000

For similar reasons the fee estimation is also a linear problem. An =
interesting difference between this and BIP141 is this will limit the =
total block size under 2MB, as 4,000,000 / 2 (the 2 as the scaling =
factor for the serialised size). If the witness inflation really happens =
(which I highly doubt as it=E2=80=99s a miner initiated attack), we =
could introduce a similar limit just with a softfork.

Version 3: extending version 2 to limit UTXO growth:
The tx weight is the maximum of the following values:
=E2=80=94 Serialised size in byte * 2
=E2=80=94 Adjusted size =3D Base size * 3 + total size + (number of =
non-OP_RETURN outputs - number of inputs) * 4 * 41
=E2=80=94 accurate SigOpCount * 50

I have explained the rationale for the adjusted size in an earlier post =
but just repeat here. =E2=80=9C4=E2=80=9D in the formula is the witness =
scale factor, and =E2=80=9C41=E2=80=9D is the minimum size of =
transaction input (32 hash + 4 index + 4 sequence + 1 for empty =
scriptSig). This requires everyone to pay a significant portion of the =
spending fee when they create a UTXO, so they pay less when it is spent. =
For transactions with 1:1 input and output ratios, the effect is =
cancelled out and won=E2=80=99t actually affect the weight estimation. =
When spending becomes cheaper, even UTXOs with lower value might become =
economical to spend, which helps cleaning up the UTXO. Since UTXO is the =
most expensive aspect, I strongly believe that any block size increase =
proposal must somehow discourage further growth of the set.

Version 4: including a sighash limit
This is what I actually implemented in my experimental hardfork network: =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/01347=
2.html =
<https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/0134=
72.html>
I=E2=80=99m not repeating here, but it shows how further limits might be =
added on top of the old ones through a softfork. Basically, you just add =
more metrics, and always take to maximum one.=

--Apple-Mail=_9E2F2FF1-9C72-4F5C-BF19-F4B2A195C4C7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=utf-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" =
class=3D"">There are many consensus critical limits scattered all over =
the Bitcoin protocol. The first part of this post is to analyse what the =
current limits are. These limits could be arranged into different =
categories:<div class=3D""><br class=3D""></div><div class=3D"">1. =
Script level limit. Some limits are restricted to scripts, including =
size (10000 bytes), nOpCount (201), stack plus alt-stack size (1000), =
and stack push size (520). If these limits are passed, they won=E2=80=99t =
have any effects on the limits of the other levels.</div><div =
class=3D""><br class=3D""></div><div class=3D"">2. Output value limit: =
any single output value must be &gt;=3D0 and &lt;=3D 21 million =
bitcoin</div><div class=3D""><br class=3D""></div><div class=3D"">3. =
Transaction level limit: The only transaction level limit we have =
currently, is the total output value must be equal to or smaller than =
the total input value for non-coinbase tx.</div><div class=3D""><br =
class=3D""></div><div class=3D"">4. Block level limit: there are several =
block level limits:</div><div class=3D"">a. The total output value of =
all txs must be equal to or smaller than the total input value with =
block reward.</div><div class=3D"">b. The serialised size including =
block header and transactions must not be over 1MB. (or 4,000,000 in =
terms of tx weight with segwit)</div><div class=3D"">c. The total =
nSigOpCount must not be over 20,000 (or 80,000 nSigOpCost with =
segwit)</div><div class=3D""><br class=3D""></div><div class=3D"">There =
is an unavoidable layer violation in terms of the block level total =
output value. However, all the other limits are restricted to its level. =
Particularly, the counting of nSigOp does not require execution of =
scripts. BIP109 (now withdrawn) tried to change this by implementing a =
block level SigatureHash limit and SigOp limit by counting the accurate =
value through running the scripts.</div><div class=3D""><br =
class=3D""></div><div class=3D"">So currently, we have 2 somewhat =
independent block resources limits: weight and SigOp. A valid block must =
not exceed any of these limits. However, for miners trying to maximise =
the fees under these limits, they need to solve a non-linear equation. =
It=E2=80=99s even worse for wallets trying to estimate fees, as they =
have no idea what txs are miners trying to include. In reality, everyone =
just ignore SigOp for fee estimation, as the size/weight is almost =
always the dominant factor.</div><div class=3D""><br class=3D""></div><div=
 class=3D"">In order to not introduce further non-linearity with segwit, =
after examining different alternatives, we decided that the block weight =
limit should be a simple linear function: &nbsp;3*base size + total =
size, which allows bigger block size and provides incentives to limit =
UTXO growth. With normal use, this allows up to 2MB of block size, and =
even more if multi-sig becomes more popular. A side effect is that =
allows a theoretical way to fill up the block to 4MB with mostly =
non-transaction data, but that=E2=80=99d only happen if a miner decide =
to do it due to non-standardness. (and this is actually not too bad, as =
witness could be pruned in the future)</div><div class=3D""><br =
class=3D""></div><div class=3D"">Some also criticised that the weight =
accounting would make a =E2=80=9Csimple 2MB hardfork=E2=80=9D more =
dangerous, as the theoretical limits will be 8MB which is too much. This =
is a complete straw man argument, as with a hardfork, one could =
introduce any rules at will, including revolutionising the calculation =
of block resources, as shown below.</div><div class=3D""><br =
class=3D""></div><div class=3D"">=E2=80=94=E2=80=94=E2=80=94=E2=80=94=E2=80=
=94=E2=80=94=E2=80=94=E2=80=94=E2=80=94</div><div class=3D"">Proposal: a =
new block resources limit accounting</div><div class=3D""><br =
class=3D""></div><div class=3D"">Objectives:&nbsp;</div><div class=3D"">1.=
 linear fee estimation</div><div class=3D"">2. a single, unified, block =
level limit for everything we want to limit</div><div class=3D"">3. do =
not require expensive script evaluation</div><div class=3D""><br =
class=3D""></div><div class=3D"">Assumptions:</div><div class=3D"">1. =
the maximum base block size is about 1MB (for a hardfork with bigger =
block, it just needs to upscale the value)</div><div class=3D"">2. a =
hardfork is done (despite some of these could also be done with a =
softfork)</div><div class=3D""><br class=3D""></div><div =
class=3D"">Version 1: without segwit</div><div class=3D"">The tx weight =
is the maximum of the following values:</div><div class=3D"">=E2=80=94 =
Serialised size in byte</div><div class=3D"">=E2=80=94 accurate =
nSigOpCount * 50 (statical counting of SigOp in scriptSig, redeemScript, =
and previous scriptPubKey, but not the new scriptPubKey)</div><div =
class=3D"">The block level limit is 1,000,000</div><div class=3D""><br =
class=3D""></div><div class=3D"">Although this looks similar to the =
existing approach, this actually makes the fee estimation a linear =
problem. Wallets may now calculate both values for a tx and take the =
maximum, and compare with other txs on the same basis. On the other =
hand, the total size and SigOpCount of a block may never go above the =
existing limits (1MB and 20000) no matter how the txs look like. (In =
some edge cases, the max block size might be smaller than 1MB, if the =
weight of some transactions is dominated by the SigOpCount)</div><div =
class=3D""><br class=3D""></div><div class=3D"">Version 2: extending =
version 1 with segwit</div><div class=3D""><div class=3D"">The tx weight =
is the maximum of the following values:</div><div class=3D"">=E2=80=94 =
Serialised size in byte * 2</div><div class=3D"">=E2=80=94 Base size * 3 =
+ total size</div><div class=3D"">=E2=80=94&nbsp;accurate&nbsp;SigOpCount =
* 50 (as a hardfork, segwit and non-segwit SigOp could be counted in the =
same way and no need to scale)&nbsp;</div><div class=3D"">The block =
level limit is 4,000,000</div></div><div class=3D""><br =
class=3D""></div><div class=3D"">For similar reasons the fee estimation =
is also a linear problem. An interesting difference between this and =
BIP141 is this will limit the total block size under 2MB, as 4,000,000 / =
2 (the 2 as the scaling factor for the serialised size). If the witness =
inflation really happens (which I highly doubt as it=E2=80=99s a miner =
initiated attack), we could introduce a similar limit just with a =
softfork.</div><div class=3D""><br class=3D""></div><div =
class=3D"">Version 3: extending version 2 to limit UTXO =
growth:</div><div class=3D""><div class=3D"">The tx weight is the =
maximum of the following values:</div><div class=3D"">=E2=80=94 =
Serialised size in byte * 2</div><div class=3D"">=E2=80=94 Adjusted size =
=3D Base size * 3 + total size + (number of non-OP_RETURN outputs - =
number of inputs) * 4 * 41</div><div =
class=3D"">=E2=80=94&nbsp;accurate&nbsp;SigOpCount * 50</div></div><div =
class=3D""><br class=3D""></div><div class=3D"">I have explained the =
rationale for the adjusted size in an earlier post but just repeat here. =
=E2=80=9C4=E2=80=9D in the formula is the witness scale factor, and =
=E2=80=9C41=E2=80=9D is the minimum size of transaction input (32 hash + =
4 index + 4 sequence + 1 for empty scriptSig). This requires everyone to =
pay a significant portion of the spending fee when they create a UTXO, =
so they pay less when it is spent. For transactions with 1:1 input and =
output ratios, the effect is cancelled out and won=E2=80=99t actually =
affect the weight estimation. When spending becomes cheaper, even UTXOs =
with lower value might become economical to spend, which helps cleaning =
up the UTXO. Since UTXO is the most expensive aspect, I strongly believe =
that any block size increase proposal must somehow discourage further =
growth of the set.</div><div class=3D""><br class=3D""></div><div =
class=3D"">Version 4: including a sighash limit</div><div class=3D"">This =
is what I actually implemented in my experimental hardfork =
network:&nbsp;<a =
href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-Janua=
ry/013472.html" =
class=3D"">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-Ja=
nuary/013472.html</a></div><div class=3D"">I=E2=80=99m not repeating =
here, but it shows how further limits might be added on top of the old =
ones through a softfork. Basically, you just add more metrics, and =
always take to maximum one.</div></body></html>=

--Apple-Mail=_9E2F2FF1-9C72-4F5C-BF19-F4B2A195C4C7--