Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 80B969A for ; 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 ; Sun, 16 Aug 2015 06:19:57 +0000 (UTC) Received: by obbfr1 with SMTP id fr1so89572998obb.1 for ; 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 Date: Sun, 16 Aug 2015 03:19:17 -0300 Message-ID: To: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 , 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 . After one year, I=E2=80=99ve received very little feedback about it. Yet the selfish = mining 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 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+ 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 ). 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
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're free to skip my message if yo= u think it will never apply to Bitcoin.
=C2=A0
[ full article copied = from my blog: https://bitslog.wordpre= ss.com/2015/08/16/how-decor-can-eradicate-selfish-mining-incentive-by-desig= n/ ]

A year ago I proposed the DECOR protocol, 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 selfish mi= ning. After one year, I=E2=80=99ve received very little feedback about = it. Yet the selfish mining 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.

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, 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 DEC= OR+ 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, at least in all crypto= currencies 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.=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.

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.

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

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, since 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. If it happens (by the mistake of a user) that a public transaction pays an=20 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). 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.

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 blo= cks by including uncles in following blocks
  • 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).
  • 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).
  • Process all transactions i= n uncle blocks, quietly skipping the ones that conflict with existing ones.=
  • Pay fees to original miners for all non-conflicting transactions i= n uncle blocks
  • Decrease the money supply in blocks following blocks= including uncles to compensate for the increase in money supply.
  • 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.
  • Increase the coinbase immaturity period to at leas= t the period of money supply compensation.
Best regards, Sergio.
--e89a8fb1f33c8bea38051d67ac8e--