path: root/5c/5a7fcf8742cf5cbbceeb5c90c38035c63f2a12

Return-Path: <david.vorick@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id D665389E
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 Nov 2015 20:37:23 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yk0-f169.google.com (mail-yk0-f169.google.com
	[209.85.160.169])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 93E5015D
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 Nov 2015 20:37:22 +0000 (UTC)
Received: by ykba77 with SMTP id a77so15015913ykb.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 10 Nov 2015 12:37:21 -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=geLcSkGDTgmoWPEFwwwB9W5iVNKUDdmVI/veFPL3uZQ=;
	b=mwQhobPHRGGc/J5AAn1rbDErM840/X+pEwLi1MQs3+HbBXYQfiZZJWaTloJ+UUK9tB
	d/n9LJDg8q2NqmsQ2/Cz+P7m78yt734b9o/RA17+E4lMET9qNKrP9TpUwD6H1FYVpRLa
	lvkEnr9Ibx/KAl94FGgoimHKENHMOSIKz5bWtBvpWjLWcwPF6X7yem9pxwgbRJXih9Vr
	5CNyMF3uHGjgHFZ8B9Re4M3BqRkx91+7L3lqLaYQJswQzuHCsGXSPVJWBe33iuip/QCe
	z58KOM9wqSUaxR7/ZZHGC4YPixDJlxYudTHZKsR/m1iGfNU74KjtUP9jgIdPAGekWnBV
	rQQA==
MIME-Version: 1.0
X-Received: by 10.129.29.12 with SMTP id d12mr5143183ywd.206.1447187841647;
	Tue, 10 Nov 2015 12:37:21 -0800 (PST)
Received: by 10.31.54.87 with HTTP; Tue, 10 Nov 2015 12:37:21 -0800 (PST)
Date: Tue, 10 Nov 2015 15:37:21 -0500
Message-ID: <CAFVRnyoFgZmwU9DRkaStcAo=K3Txv4PbG=jM5EK5_vUT7YrGCg@mail.gmail.com>
From: David Vorick <david.vorick@gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a11429512398c06052435adf6
X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_20,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,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: Tue, 10 Nov 2015 20:44:56 +0000
Subject: [bitcoin-dev] Proposal - Mandatory Weak Blocks
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: Tue, 10 Nov 2015 20:37:24 -0000

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

Prior discussion: http://gnusha.org/bitcoin-wizards/2015-11-09.log

Goal: Increase transaction throughput without increasing miner
centralization pressure, and without putting undue burden on full
validating nodes.

'Weak Block': a block which meets a target with a lower difficulty,
typically some fraction such as 5%.

'Strong Block': a block that meets the full target. Also called a block.

---

Introduction:

One of the key sources of miner centralization is the orphan rate. Miners
with 33% hash power are guaranteed to instantly validate 33% of the blocks,
while miners with only 1% hashrate only get this advantage for 1% of the
blocks. If the average orphan rate on the network is high, miners with
significantly more hashpower will have a substantial advantage over smaller
miners.

One of the strongest reasons to keep the block size small is to keep the
orphan rate low. This is to protect smaller miners. Numerous pre-consensus
schemes have been discussed which attempt to drive the orphan rate down.
When considering these schemes, the adversarial case must be considered as
well as the average case.

The circulation of weak blocks has been discussed as a form of
preconsensus. Upon finding a weak block, miners circulate the block to the
other miners, and then when a full block is found, a diff between the weak
block and full block can be circulated instead of just the full block. This
diff is both quicker to validate and quicker to circulate, resulting in
substantially improved block propagation times and a reduced orphan rate,
thus reduced miner centralization pressure.

The adversarial case is not addressed by this scheme. It is still possible
to find and circulate a large, difficult-to-verify block that slowly
propagates through the network and drives up the orphan rate for smaller
miners. A new construction (below) introduces a set of new consensus rules
which protect small miners even from the adversarial case.

---

Construction:

After a block is found, pre-consensus for the next block begins.
Pre-consensus consists of building a chain of weak blocks which meet a
target that has 5% the difficulty of a full block. Each weak block can
introduce at most 200kb of new transactions to the weak-block chain. On
average, a new weak block will appear every 30 seconds. When the next
strong block is found, it must be at the head of a weak block chain and it
must itself introduce a maximum of 200kb in transactions new to the
weak-block chain. The maximum size of a strong block is 16mb, but can be
composed of any number of weak blocks.

Example:

[strong block] -> [weak block - 200kb] -> [weak block - 400kb] -> [strong
block - 600kb] -> [weak block - 200kb]...

---

Analysis:

On average, weak blocks will be found every 30 seconds and each block will
build on top of 20 weak blocks. The average block size will be 4mb. 80 weak
blocks are required to construct a block of the maximum size of 16mb, which
will probably happen 3 out of every 1000 blocks. The race-size for blocks
is kept low, and as explained later, adversarial mining is inherently
decentivized.

This construction establishes a 'pre-consensus' that allows miners to do
faster validation when a new block is found. Assuming that the miner has
seen most of the precursor weak blocks, only a few hundred kilobytes of
validation must be performed even when the blocks are multiple megabytes in
size. In the usual case, only 100kb of validation needs to be performed.

More consistent transaction throughput is achieved. Strong blocks that are
found in rapid succession are likely to each be small, due to having a
small number of weak blocks that they build on top of. Strong blocks that
are found a long time after the previous strong block are likely to have
many weak blocks that they build on top of.

Better censorship resistance is achieved. Creating large blocks requires
building on top of weak blocks. A miner actively trying to censor certain
transactions will have to ignore all weak-block chains that contain the
offensive transaction, and thus will be at a disadvantage due to
consistently producing smaller (and less fee-rich) blocks.

An attacker that is trying to flood the network with intentionally
slow-validating blocks can no longer easily construct blocks at the maximum
size, and instead must create and hide weak blocks which build up to a
strong block that has many unseen transactions. Hiding weak blocks has an
opportunity cost, because in building a chain of weak block is exclusive to
the attacker, the attacker is missing out on the opportunity of building on
top of the other weak blocks being produced.

Compared to Bitcoin-NG, this construction lacks the vulnerability where a
single, more easily-targeted leader is elected and placed in charge of the
next round of consensus.

Everyone has incentive to build on top of the most recent weak block. In
the event that the next weak block discovered is also a strong block, the
fees reaped by the miner will be maximized.

Larger miners appear to have an incentive to withhold weak blocks in an
attempt to drive smaller miners off of the network. Large miners
withholding weak blocks will gain an advantage that amounts to (% chance of
finding a weak block) * (% chance of finding the full block) * (average fee
addition of a weak block) / (average total block reward). Assuming that
fees make up entire block reward, the advantage for a miner performing a
withholding attack is (hashrate^2 * weak block difficulty). For a 50%
miner, that advantage comes to 1.25%. For a 20% miner, this advantage is
just 0.2%. There are probably multiple ways to decentivize this behavior,
the simplest of which involves directly rewarding miners for announcing
weak blocks.

The orphan rate for weak blocks is going to be substantially higher for
smaller miner, due to the increased rate of appearance. I do not think that
this is going to create any issues, because small miners are still going to
have high visibility of the longest weak-block chain, and are still going
to be able to create blocks that are nearly as full as the blocks created
by larger miners.

The more time that passes between mining blocks, the more a block is worth
(because it will have more weak-blocks, and therefore more transactions).
Hashrate is therefore more valuable when a block has not been found for a
while, and may result in hashrate hopping, where hashrate is disabled or
clocked-down immediately after a block is found and then clocked-up if a
block is not found for a while. This is only a problem while fees from new
transactions make up a significant portion of the block reward.

---

Conclusion:

A forced-weak-blocks scheme potentially provides a powerful way to reduce
the orphan rate, increasing the safety margins on miner centralization
pressure and allowing the overall transaction throughput to be increased as
a result.

Additional analysis is needed to be certain that there are not new attack
vectors or mal-aligned incentives that have been introduced.

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

<div dir=3D"ltr">Prior discussion: <a href=3D"http://gnusha.org/bitcoin-wiz=
ards/2015-11-09.log" target=3D"_blank">http://gnusha.org/bitcoin-wizards/20=
15-11-09.log</a><br><br>Goal:
 Increase transaction throughput without increasing miner centralization
 pressure, and without putting undue burden on full validating nodes.<br><b=
r>&#39;Weak Block&#39;: a block which meets a target with a lower difficult=
y, typically some fraction such as 5%.<br><br>&#39;Strong Block&#39;: a blo=
ck that meets the full target. Also called a block.<br>=C2=A0=C2=A0 =C2=A0<=
br>---<br><br>Introduction:<br><br>One
 of the key sources of miner centralization is the orphan rate. Miners=20
with 33% hash power are guaranteed to instantly validate 33% of the=20
blocks, while miners with only 1% hashrate only get this advantage for=20
1% of the blocks. If the average orphan rate on the network is high,=20
miners with significantly more hashpower will have a substantial=20
advantage over smaller miners.<br><br>One of the strongest reasons to=20
keep the block size small is to keep the orphan rate low. This is to=20
protect smaller miners. Numerous pre-consensus schemes have been=20
discussed which attempt to drive the orphan rate down. When considering=20
these schemes, the adversarial case must be considered as well as the=20
average case.<br><br>The circulation of weak blocks has been discussed=20
as a form of preconsensus. Upon finding a weak block, miners circulate=20
the block to the other miners, and then when a full block is found, a=20
diff between the weak block and full block can be circulated instead of=20
just the full block. This diff is both quicker to validate and quicker=20
to circulate, resulting in substantially improved block propagation=20
times and a reduced orphan rate, thus reduced miner centralization=20
pressure.<br><br>The adversarial case is not addressed by this scheme.=20
It is still possible to find and circulate a large, difficult-to-verify=20
block that slowly propagates through the network and drives up the=20
orphan rate for smaller miners. A new construction (below) introduces a=20
set of new consensus rules which protect small miners even from the=20
adversarial case.<br><br>---<br><br>Construction:<br><br>After a block=20
is found, pre-consensus for the next block begins. Pre-consensus=20
consists of building a chain of weak blocks which meet a target that has
 5% the difficulty of a full block. Each weak block can introduce at=20
most 200kb of new transactions to the weak-block chain. On average, a=20
new weak block will appear every 30 seconds. When the next strong block=20
is found, it must be at the head of a weak block chain and it must=20
itself introduce a maximum of 200kb in transactions new to the=20
weak-block chain. The maximum size of a strong block is 16mb, but can be
 composed of any number of weak blocks.<br><br>Example:<br><br>[strong bloc=
k] -&gt; [weak block - 200kb] -&gt; [weak block - 400kb] -&gt; [strong bloc=
k - 600kb] -&gt; [weak block - 200kb]...<br><br>---<br><br>Analysis:<br><br=
>On
 average, weak blocks will be found every 30 seconds and each block will
 build on top of 20 weak blocks. The average block size will be 4mb. 80=20
weak blocks are required to construct a block of the maximum size of=20
16mb, which will probably happen 3 out of every 1000 blocks. The=20
race-size for blocks is kept low, and as explained later, adversarial=20
mining is inherently decentivized.<br><br>This construction establishes a
 &#39;pre-consensus&#39; that allows miners to do faster validation when a =
new=20
block is found. Assuming that the miner has seen most of the precursor=20
weak blocks, only a few hundred kilobytes of validation must be=20
performed even when the blocks are multiple megabytes in size. In the=20
usual case, only 100kb of validation needs to be performed.<br><br>More=20
consistent transaction throughput is achieved. Strong blocks that are=20
found in rapid succession are likely to each be small, due to having a=20
small number of weak blocks that they build on top of. Strong blocks=20
that are found a long time after the previous strong block are likely to
 have many weak blocks that they build on top of.<br><br>Better=20
censorship resistance is achieved. Creating large blocks requires=20
building on top of weak blocks. A miner actively trying to censor=20
certain transactions will have to ignore all weak-block chains that=20
contain the offensive transaction, and thus will be at a disadvantage=20
due to consistently producing smaller (and less fee-rich) blocks.<br><br>An
 attacker that is trying to flood the network with intentionally=20
slow-validating blocks can no longer easily construct blocks at the=20
maximum size, and instead must create and hide weak blocks which build=20
up to a strong block that has many unseen transactions. Hiding weak=20
blocks has an opportunity cost, because in building a chain of weak=20
block is exclusive to the attacker, the attacker is missing out on the=20
opportunity of building on top of the other weak blocks being produced.<br>=
<br>Compared
 to Bitcoin-NG, this construction lacks the vulnerability where a=20
single, more easily-targeted leader is elected and placed in charge of=20
the next round of consensus.<br><br>Everyone has incentive to build on=20
top of the most recent weak block. In the event that the next weak block
 discovered is also a strong block, the fees reaped by the miner will be
 maximized.<br><br>Larger miners appear to have an incentive to withhold
 weak blocks in an attempt to drive smaller miners off of the network.=20
Large miners withholding weak blocks will gain an advantage that amounts
 to (% chance of finding a weak block) * (% chance of finding the full=20
block) * (average fee addition of a weak block) / (average total block=20
reward). Assuming that fees make up entire block reward, the advantage=20
for a miner performing a withholding attack is (hashrate^2 * weak block=20
difficulty). For a 50% miner, that advantage comes to 1.25%. For a 20%=20
miner, this advantage is just 0.2%. There are probably multiple ways to=20
decentivize this behavior, the simplest of which involves directly=20
rewarding miners for announcing weak blocks.<br><br>The orphan rate for=20
weak blocks is going to be substantially higher for smaller miner, due=20
to the increased rate of appearance. I do not think that this is going=20
to create any issues, because small miners are still going to have high=20
visibility of the longest weak-block chain, and are still going to be=20
able to create blocks that are nearly as full as the blocks created by=20
larger miners.<br><br>The more time that passes between mining blocks,=20
the more a block is worth (because it will have more weak-blocks, and=20
therefore more transactions). Hashrate is therefore more valuable when a
 block has not been found for a while, and may result in hashrate=20
hopping, where hashrate is disabled or clocked-down immediately after a=20
block is found and then clocked-up if a block is not found for a while.=20
This is only a problem while fees from new transactions make up a=20
significant portion of the block reward.<br><br>---<br><br>Conclusion:<br><=
br>A
 forced-weak-blocks scheme potentially provides a powerful way to reduce
 the orphan rate, increasing the safety margins on miner centralization=20
pressure and allowing the overall transaction throughput to be increased
 as a result.<br><br>Additional analysis is needed to be certain that=20
there are not new attack vectors or mal-aligned incentives that have=20
been introduced.</div>

--001a11429512398c06052435adf6--