Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id D665389E for ; 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 ; Tue, 10 Nov 2015 20:37:22 +0000 (UTC) Received: by ykba77 with SMTP id a77so15015913ykb.2 for ; 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: From: David Vorick 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Prior discussion: http://gnusha.org/bitcoin-wizards/20= 15-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 difficult= y, typically some fraction such as 5%.

'Strong Block': a blo= ck that meets the full target. Also called a block.
=C2=A0=C2=A0 =C2=A0<= br>---

Introduction:

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.

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.

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.

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.

---

Construction:

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.

Example:

[strong bloc= k] -> [weak block - 200kb] -> [weak block - 400kb] -> [strong bloc= k - 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=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.

This construction establishes a 'pre-consensus' 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.

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.

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.

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

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.

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.

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.

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.

---

Conclusion:
<= 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.

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