path: root/e7/5e5bf69010044150a15372cc94a58b9721bdd8

Return-Path: <sergio.d.lerner@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 80B969A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 16 Aug 2015 06:20:00 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ob0-f173.google.com (mail-ob0-f173.google.com
	[209.85.214.173])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id EA80F1A9
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 16 Aug 2015 06:19:57 +0000 (UTC)
Received: by obbfr1 with SMTP id fr1so89572998obb.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 15 Aug 2015 23:19:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:from:date:message-id:subject:to:content-type;
	bh=22LxG8/AUR7IOqRXjqRIBuLpDr+OdP6EHs4g4KhsS+0=;
	b=ULVMl/yMNuJV1p17WPnMp4glIJg28v4yyZurBPAS0Q6jyJhX6RxmjoT4AqzBsdxxcJ
	/G69RffMpeTr8qXHo+b/k83EEbybPKKwI5HWGCl4E+kNTWfZcc5j4O7wN6+rYHGsTM+g
	o1qlvGDHmdQccxQ1ylKCmBr+oAh1SrkKcQhkHhQTrs54Ui7XbqZLcc1u0DRnQ8hMHtFA
	a13ke2MWixd3gKLKC5+hEhkhrAAkOzQYDR0p/R3E72GQV7dSeGtbN4kYXiuYo/UAK+ji
	BNM0ShwhXVW1Wenb4i0C4KFVLI+6h4gKECgg682bfbiOxb3iMGT1eTpUEX0D/Dr8tqkE
	WOUg==
X-Received: by 10.182.91.4 with SMTP id ca4mr45360730obb.11.1439705997239;
	Sat, 15 Aug 2015 23:19:57 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.202.78.77 with HTTP; Sat, 15 Aug 2015 23:19:17 -0700 (PDT)
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Sun, 16 Aug 2015 03:19:17 -0300
Message-ID: <CAKzdR-rBXMQ22d6F3R23TLTTOALgWsPivyiiwuO-jz1QRLzatw@mail.gmail.com>
To: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev
	<bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=e89a8fb1f33c8bea38051d67ac8e
X-Spam-Status: No, score=0.0 required=5.0 tests=BAYES_50,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
Subject: [bitcoin-dev] How DECOR++ can eradicate selfish mining incentive by
	design
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: Sun, 16 Aug 2015 06:20:00 -0000

--e89a8fb1f33c8bea38051d67ac8e
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

In these shocking forking times, nothing more relaxing that to immerse
yourself in a pure technical reading about cryptocurrency design, letting
aside Bitcoin politics for a moment. This message is about cryptocurrencies
design in general, so you're free to skip my message if you think it will
never apply to Bitcoin.

[ full article copied from my blog:
https://bitslog.wordpress.com/2015/08/16/how-decor-can-eradicate-selfish-mi=
ning-incentive-by-design/
]

A year ago I proposed the DECOR protocol
<https://bitslog.wordpress.com/2014/05/02/decor/>, a new rule for
cryptocurrencies to reduce significantly the amount of orphan blocks and
then allow block rate to be as high as one block every 5 seconds, and at
the same time it promised to address the problem of selfish mining
<http://hackingdistributed.com/2013/11/04/bitcoin-is-broken/>. After one
year, I=E2=80=99ve received very little feedback about it. Yet the selfish =
mining
<http://hackingdistributed.com/2013/11/04/bitcoin-is-broken/> problem has
been argued over and over against certain changes in Bitcoin, as if selfish
mining were something inevitable to all POW-based cryptocurrencies. But it
is not.

In a nutshell, DECOR is a protocol that permits miners to share the block
reward if both mine competing blocks. This is done by publishing block
header siblings (sometime called uncles) into child blocks, and modifying
the cryptocurrency protocol to pay some amount to the miners of uncles. If
all miners are honest, this strategy increases slightly the probability of
1-block reversals, but reduces considerably the probability of longer
reversals, as all miners choose the same parent. A few months after my
post, Ethereum <https://www.ethereum.org/>adopted a similar strategy of
paying a certain amount of ether to uncles, but the amount paid was created
out of thin ear, and at that time there could be any amount of uncles, so
basically it distorted the money supply function into a uncapped
inflationary one, if all miners decided to collude. After I reported this
issue, they restricted the number of uncles that can be included, but still
it leaves an incentive for all miners to collude to increase miner revenue.
DECOR does reward sharing, so the supply function cap is maintained. But it
does not solve the Selfish mining problem: miners withholding a block get
paid a full reward but the remaining miners are working (without knowing
it) for a half of the block reward. So my original strategy does not work
for rational (but not necessarily honest) miners. A few posts later I
presented DECOR+ <https://bitslog.wordpress.com/2014/05/07/decor-2/> to try
to address the problem of unbalanced rewards: what happens if there are two
competing blocks, but one has a 12.5 BTC reward, but the other has a 20 BTC
reward due to additional fees? But again, if miners are dishonest, the
proposed scheme does not solve the underlying problem, as miners can
artificially increase their fees to win the conflict resolving rule, at
least in all cryptocurrencies that do not burn transaction fees. How can we
fix it?

*DECOR++*

We=E2=80=99ll fix DECOR by doing three changes. The first is by paying full=
 rewards
to all competing blocks, either the parent or the uncles. To prevent
increasing the money supply, first we set a maximum number of uncles U than
can be included over a period of N blocks. For example we can set U=3D100 a=
nd
N=3D1000 (a maximum orphan rate of 10%). Then we create rule to decrease th=
e
money supply per time interval in case it previously was increased. So to
prevent miners colluding to increase the money supply in U/N, we either
decrease the subsidies of the following N blocks by the excess amount in
the previous period or we make N coincident with block difficulty re-target
interval and we consider uncles in the rate computation, so mining
afterward simply gets more difficult. If all miners collude to try to
increase their revenue by U/N, they will see their revenue decrease by the
same amount in the following re-target interval.

Miners could start switching between two cryptocurrencies to mine only
during the low difficulty interval and avoid the high difficulty interval.
But here are no competing valuable non-merged mined cryptocurrency using
SHA256D, so this is no problem for Bitcoin. Also the cryptocurrency left
without mining power would become insecure and its price will fall to near
zero. So increasing the immaturity lock time for coinbases to at least N
blocks destroys any miner earnings if all decide to switch all at once.

The second change is to choose the parent block in case of conflict based
on a deterministic random selection in case of deciding between several
chains with the same accumulated difficulty but different tip: we order the
competing tip blocks by their hash digest values, we hash the hashes and we
use the resulting hash digest as seed to a PRNG to choose an index in the
sorted list of the block to choose as parent.

The third change is to process the transactions of all competing blocks
(the actual block and its siblings) in case of a conflict. The transactions
on the parent block will be processed first as normal. The others will be
processed in the order they are referenced in following child blocks.
Conflicting transactions (double-spends) present in uncle blocks with
respect to the main block are skipped, while obviously internal conflicts
in the uncle blocks make them invalid, as usual. Now, as long as the
subsidy dominates the fees, miners have no incentive to withhold blocks.

Let=E2=80=99s analyze what can happen in the long term, when fees dominate =
the
block reward. In the future there may be two kinds of transactions: public
transactions and private transactions. Public transactions are the current
standard transactions: they pay a fee in the standard way and are broadcast
over the public network. Private transactions may appear if miners decide
to negotiate inclusion in blocks directly with web wallets or gateways:
private transactions will pay fees as an output to the miner=E2=80=99s publ=
ic key.
Blocks with high rewards competing with blocks with low rewards due to
public transactions will be rare, since for the benefit of the miner most
transactions included in blocks should be present in all other miners
memory pools to accelerate propagation, so all miners are exposed to the
same reward pool. If it happens (by the mistake of a user) that a public
transaction pays an extremely high fee, the withholding incentive may
reappear. But in a far future, when subsidy disappears and miners receive
the payment mainly because of fees, they may adopt the more competitive
commercial strategy of rely mainly in private transactions (or maybe using =
Mike
Hearn=E2=80=99s assurance contracts
<https://en.bitcoin.it/wiki/Funding_network_security>). As fees from
private transactions are not shared between competing blocks, they won=E2=
=80=99t
affect selfish mining. I conclude that DECOR++ is currently incentive
compatible and it is highly probable that remains incentive compatible in
the future.

To summarize, DECOR++ main protocol properties are:

   - Choose a parent by a deterministic pseudo-random coin toss based on
   competing block headers
   - Give standard subsidy to all competing blocks by including uncles in
   following blocks
   - Give small monetary incentive to include uncle blocks in blocks
   (miners including blocks can get a small share of included blocks reward=
s).
   - Give small monetary incentive to choose deterministically one of the
   competing blocks as the main block (this can be done by burning some rew=
ard
   share if other parent is chosen).
   - Process all transactions in uncle blocks, quietly skipping the ones
   that conflict with existing ones.
   - Pay fees to original miners for all non-conflicting transactions in
   uncle blocks
   - Decrease the money supply in blocks following blocks including uncles
   to compensate for the increase in money supply.
   - Limit the amount of uncles that can be included over an interval of
   blocks, and make that interval long enough to capture normal variances i=
n
   orphan rates.
   - Increase the coinbase immaturity period to at least the period of
   money supply compensation.

Best regards, Sergio.

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

<div dir=3D"ltr">In these shocking forking times, nothing more relaxing tha=
t to immerse yourself in a pure technical reading about cryptocurrency desi=
gn, letting aside Bitcoin politics for a moment. This message is about cryp=
tocurrencies design in general, so you&#39;re free to skip my message if yo=
u think it will never apply to Bitcoin.<br>=C2=A0<br>[ full article copied =
from my blog: <a href=3D"https://bitslog.wordpress.com/2015/08/16/how-decor=
-can-eradicate-selfish-mining-incentive-by-design/">https://bitslog.wordpre=
ss.com/2015/08/16/how-decor-can-eradicate-selfish-mining-incentive-by-desig=
n/</a> ]<br><br><p>A year ago I proposed the<a href=3D"https://bitslog.word=
press.com/2014/05/02/decor/"> DECOR protocol</a>,
 a new rule for cryptocurrencies to reduce significantly the amount of=20
orphan blocks and then allow block rate to be as high as one block every 5=
=20
seconds, and at the same time it promised to address the problem of <a href=
=3D"http://hackingdistributed.com/2013/11/04/bitcoin-is-broken/">selfish mi=
ning</a>. After one year, I=E2=80=99ve received very little feedback about =
it. Yet the <a href=3D"http://hackingdistributed.com/2013/11/04/bitcoin-is-=
broken/">selfish mining</a>
 problem has been argued over and over against certain changes in=20
Bitcoin, as if selfish mining were something inevitable to all POW-based
 cryptocurrencies. But it is not.</p>
<p>In a nutshell, DECOR is a protocol that permits miners to share the=20
block reward if both mine competing blocks. This is done by publishing=20
block header siblings (sometime called uncles) into child blocks, and=20
modifying the cryptocurrency protocol to pay some amount to the miners=20
of uncles. If all miners are honest, this strategy increases slightly=20
the probability of 1-block reversals, but reduces considerably the=20
probability of longer reversals, as all miners choose the same parent. A
 few months after my post, <a href=3D"https://www.ethereum.org/">Ethereum <=
/a>adopted
 a similar strategy of paying a certain amount of ether to uncles, but=20
the amount paid was created out of thin ear, and at that time there=20
could be any amount of uncles, so basically it distorted the money=20
supply function into a uncapped inflationary one, if all miners decided=20
to collude. After I reported this issue, they restricted the number of=20
uncles that can be included, but still it leaves an incentive for all=20
miners to collude to increase miner revenue. DECOR does reward sharing,=20
so the supply function cap is maintained. But it does not solve the=20
Selfish mining problem: miners withholding a block get paid a full=20
reward but the remaining miners are working (without knowing it) for a=20
half of the block reward. So my original strategy does not work for=20
rational (but not necessarily honest) miners. A few posts later I=20
presented <a href=3D"https://bitslog.wordpress.com/2014/05/07/decor-2/">DEC=
OR+</a>
 to try to address the problem of unbalanced rewards: what happens if=20
there are two competing blocks, but one has a 12.5 BTC reward, but the=20
other has a 20 BTC reward due to additional fees? But again, if miners=20
are dishonest, the proposed scheme does not solve the underlying=20
problem, as miners can artificially increase their fees to win the=20
conflict resolving rule, <span lang=3D"en-US">at least </span>in all crypto=
currencies that do not burn transaction fees. How can we fix it?</p>
<p><strong>DECOR++</strong></p>
<p>We=E2=80=99ll fix DECOR by doing three changes. The first is by <span la=
ng=3D"en-US">paying
 full rewards to all competing blocks, either the parent or the uncles.=20
To prevent increasing the money supply, first we set a maximum number of
 uncles U than can be included over a period of N blocks. For example we
 can set U=3D100 and N=3D1000 (a maximum orphan rate of 10%). Then we creat=
e
 rule to decrease the money supply per time interval in case it=20
previously was increased. So to prevent miners colluding to increase the
 money supply in U/N, we either decrease the subsidies of the following N
 blocks by the excess amount in the previous period or we make N=20
coincident with block difficulty re-target interval and we consider=20
uncles in the rate computation, so mining afterward simply gets more=20
difficult. If all miners collude to try to increase their revenue by=20
U/N, they will see their revenue decrease by the same amount in the=20
following re-target interval. </span></p>
<p><span lang=3D"en-US">Miners could start switching between two=20
cryptocurrencies to mine only during the low difficulty interval and=20
avoid the high difficulty interval. But here are no competing valuable=20
non-merged mined cryptocurrency using SHA256D, so this is no problem for
 Bitcoin. Also the cryptocurrency left without mining power would become
 insecure and its price will fall to near zero. So increasing the=20
immaturity lock time for coinbases to at least N blocks destroys any=20
miner earnings if all decide to switch all at once.</span></p>
<p>The second change is to choose the parent block in case of conflict=20
based on a deterministic random selection in case of deciding between=20
several chains with the same accumulated difficulty but different tip:=20
we order the competing tip blocks by their hash <span lang=3D"en-US">digest=
 </span>values, we hash the hashes and we use the resulting hash <span lang=
=3D"en-US">digest</span> as seed to a PRNG to choose an index in the sorted=
 list of the block to choose as parent.</p>
<p><span lang=3D"en-US">The third change is </span>to process <span lang=3D=
"en-US">the transactions of </span>all
 competing blocks (the actual block and its siblings) in case of a=20
conflict. The transactions on the parent block will be processed first=20
as normal. The others will be processed in the order they are referenced
 in following child blocks. Conflicting transactions (double-spends)=20
present in uncle blocks with respect to the main block are skipped,=20
while obviously internal conflicts in the uncle blocks make them=20
invalid, as usual. Now, as long as the subsidy dominates the fees,=20
miners have no incentive to withhold blocks.</p>
<p><span lang=3D"en-US">Let=E2=80=99s analyze what can happen in the long t=
erm,=20
when fees dominate the block reward. In the future there may be two=20
kinds of transactions: public transactions and private transactions.=20
Public transactions are the current standard transactions: they pay a=20
fee in the standard way and are broadcast over the public network.=20
Private transactions may appear if miners decide to negotiate inclusion=20
in blocks directly with web wallets or gateways: private transactions=20
will pay fees as an output to the miner=E2=80=99s public key. Blocks with h=
igh=20
rewards competing with blocks with low rewards due to public transactions w=
ill be rare, s</span>ince for the=20
benefit of the miner most transactions included in blocks should be=20
present in all other miners memory pools to accelerate propagation, so=20
all miners are exposed to the same reward pool. <span lang=3D"en-US">If it
 happens (by the mistake of a user) that a public transaction pays an=20
extremely high fee, the withholding incentive may reappear. </span>But in a=
 far future, when <span lang=3D"en-US">subsidy disappears and </span>miners=
 receive the payment mainly because of fees, they may adopt <span lang=3D"e=
n-US">the </span>more competitive commercial strateg<span lang=3D"en-US">y =
of rely mainly in private transactions (or maybe using <a href=3D"https://e=
n.bitcoin.it/wiki/Funding_network_security">Mike Hearn=E2=80=99s assurance =
contracts</a>).
 As fees from private transactions are not shared between competing=20
blocks, they won=E2=80=99t affect selfish mining. I conclude that DECOR++ i=
s=20
currently incentive compatible and it is highly probable that remains=20
incentive compatible in the future.</span></p>
<p>To summarize, DECOR++ main protocol properties are:</p>
<ul><li>Choose a parent by a deterministic pseudo-random coin toss based on=
 competing block headers</li><li>Give standard subsidy to all competing blo=
cks by including uncles in following blocks</li><li>Give small monetary inc=
entive to include uncle blocks in blocks=20
(miners including blocks can get a small share of included blocks=20
rewards).</li><li>Give small monetary incentive to choose deterministically=
 one of the
 competing blocks as the main block (this can be done by burning some=20
reward share if other parent is chosen).</li><li>Process all transactions i=
n uncle blocks, quietly skipping the ones that conflict with existing ones.=
</li><li>Pay fees to original miners for all non-conflicting transactions i=
n uncle blocks</li><li>Decrease the money supply in blocks following blocks=
 including uncles to compensate for the increase in money supply.</li><li>L=
imit the amount of uncles that can be included over an interval of=20
blocks, and make that interval long enough to capture normal variances=20
in orphan rates.</li><li>Increase the coinbase immaturity period to at leas=
t the period of money supply compensation.</li></ul>Best regards, Sergio.<b=
r></div>

--e89a8fb1f33c8bea38051d67ac8e--