Message-ID: <5369B705.9090406@certimix.com>
Date: Wed, 07 May 2014 01:31:01 -0300
From: Sergio Lerner <sergiolerner@certimix.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:17.0) Gecko/20130509 Thunderbird/17.0.6
MIME-Version: 1.0
To: Joseph Bonneau <jbonneau@princeton.edu>
References: <mailman.122233.1398039406.2207.bitcoin-development@lists.sourceforge.net>
	<52CDA01B-13BF-4BB8-AC9A-5FBBB324FD15@sant.ox.ac.uk>
	<20140423150555.GE19430@savin>
	<CAOe4Ui=OaVLvh0vUnNv-1j41YB4B2x896DQ5b6xt4oUJ5oLPFg@mail.gmail.com>
	<53638616.2030009@certimix.com> <536388F9.3040607@certimix.com>
	<CAOe4UimBEe4t1Z41du3r8pQUOmzd_1V_aESizuiH2U6uvN9nFA@mail.gmail.com>
In-Reply-To: <CAOe4UimBEe4t1Z41du3r8pQUOmzd_1V_aESizuiH2U6uvN9nFA@mail.gmail.com>
Content-Type: multipart/alternative;
	boundary="------------040209020706000103040702"
Cc: bitcoin-research@lists.cs.princeton.edu,
	"bitcoin-development@lists.sourceforge.net"
	<bitcoin-development@lists.sourceforge.net>
Subject: [Bitcoin-development] DECOR+ Better block selection rule
Precedence: list

This is a multi-part message in MIME format.
--------------040209020706000103040702
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This e-mail is an extract of my post:
http://bitslog.wordpress.com/2014/05/07/decor-2/

Some posts ago I presented the DECOR protocol. One of the assumptions I
did was that the amount of coins each miner earned in competing blocks
was approximately the same. This could be true for cryptocurrencies with
never ending block subsidies (inflationary designs) because the block
subsidy may be an order of magnitude higher than the fees collected in
the block. In Bitcoin we don’t really know what will happen with fees
when the reward is halved. Less we know if in that case the number of
transactions per block (and fees collected) will be fairly constant or
there will be high variability. If Alice and Bob compete for a certain
block height with blocks A and B respectively, and Alice’s block reward
(subsidy+fees) is half of Bob’s reward, then even if Hash(A) < Hash(B)
(and the DECOR incentives are set to prefer A) it may be the case that
both Alice and Bob would prefer to mine on top of B since they both earn
much more even paying the higher penalty d of burnt coins. In limit
cases, Alice’s optimal choice may not be the same as Bob’s optimal
choice. I propose a slight modification of the protocol such that even
with different block rewards the optimal choice of parent is always the
same for all miners. Instead of choosing the block with less hash
digest, miners will choose the block with higher reward (subsidy+fees).
Splitting the higher reward block would always be more profitable than
splitting lowest reward block. In the rare case both blocks have exactly
the same reward, then the block with lowest hash is chosen. Even if
rewards are approximately equal, the change adds a new monetary
incentive to cooperate. Compared with the DECOR protocol, the only
modification is in step 6.

*DECOR+ Mining strategy*

 1. If there is no block Y having a sibling X in the main chain whose
    reward has not matured then mine in the standard way and exit this
    procedure
 2. Add a reference to Y in the new block that is being prepared.
 3. Let x  := BlockReward(X)
 4. Let q := x*a
 5. Let z :=x*b
 6. If (BlockReward(X)<BlockReward(Y)) OR
    (BlockReward(X)=BlockReward(Y)) AND (Hash(X)>Hash(Y)) then
    q :=q-(x*c)
    z :=z+(x*d)
 7. Let w :=x*e
 8. Add a transaction that has as input the coinbase output of X and has
    four outputs:
          o pay q coins to the address specified in the coinbase output
            of block Y
          o pay w coins to an owned address
          o burns z coins
          o pay the remaining coins to the same address as the input
            address.

 

BlockReward() returns the block subsidy plus the transaction fees in the
block.

*Conditions on constants*

If you want to choose different values of a,b,c,d,e that still force
miners selections converge into a single parent then these conditions
must be satisfied:

  * e > 0
  * 1-a-e-b > a-c
  * 1+e-a-e-b > a-c
  * a > 1-a-c-e-b-d
  * a+e > 1-a-c-e-b-d

And all constants are between 0 and 1.

It's interesting that now it's much easier to prove that for two
competing miners the DECOR+ protocol cannot be abused, since there is no
dependence on the block content.

Best regards,
 Sergio.

--------------040209020706000103040702
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<html>
  <head>
    <meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
  </head>
  <body text="#000000" bgcolor="#FFFFFF">
    <div class="moz-cite-prefix">This e-mail is an extract of my post:
      <a class="moz-txt-link-freetext" href="http://bitslog.wordpress.com/2014/05/07/decor-2/">http://bitslog.wordpress.com/2014/05/07/decor-2/</a><br>
      <br>
      Some posts ago I presented the DECOR protocol. One of the
      assumptions I did was that the amount of coins each miner earned
      in competing blocks was approximately the same. This could be true
      for cryptocurrencies with never ending block subsidies
      (inflationary designs) because the block subsidy may be an order
      of magnitude higher than the fees collected in the block. In
      Bitcoin we don’t really know what will happen with fees when the
      reward is halved. Less we know if in that case the number of
      transactions per block (and fees collected) will be fairly
      constant or there will be high variability. If Alice and Bob
      compete for a certain block height with blocks A and B
      respectively, and Alice’s block reward (subsidy+fees) is half of
      Bob’s reward, then even if Hash(A) &lt; Hash(B) (and the DECOR
      incentives are set to prefer A) it may be the case that both Alice
      and Bob would prefer to mine on top of B since they both earn much
      more even paying the higher penalty d of burnt coins. In limit
      cases, Alice’s optimal choice may not be the same as Bob’s optimal
      choice. I propose a slight modification of the protocol such that
      even with different block rewards the optimal choice of parent is
      always the same for all miners. Instead of choosing the block with
      less hash digest, miners will choose the block with higher reward
      (subsidy+fees). Splitting the higher reward block would always be
      more profitable than splitting lowest reward block. In the rare
      case both blocks have exactly the same reward, then the block with
      lowest hash is chosen. Even if rewards are approximately equal,
      the change adds a new monetary incentive to cooperate. Compared
      with the DECOR protocol, the only modification is in step 6.<br>
      <p><strong>DECOR+ Mining strategy</strong></p>
      <ol>
        <li>If there is no block Y having a sibling X in the main chain
          whose reward has not matured then mine in the standard way and
          exit this procedure</li>
        <li>Add a reference to Y in the new block that is being
          prepared.</li>
        <li>Let x  := BlockReward(X)</li>
        <li>Let q := x*a</li>
        <li>Let z :=x*b</li>
        <li>If (BlockReward(X)&lt;BlockReward(Y)) OR
          (BlockReward(X)=BlockReward(Y)) AND (Hash(X)&gt;Hash(Y)) then<br>
          q :=q-(x*c)<br>
          z :=z+(x*d)</li>
        <li>Let w :=x*e</li>
        <li>Add a transaction that has as input the coinbase output of X
          and has four outputs:
          <ul>
            <ul>
              <li>pay q coins to the address specified in the coinbase
                output of block Y</li>
              <li>pay w coins to an owned address</li>
              <li>burns z coins</li>
              <li>pay the remaining coins to the same address as the
                input address.</li>
            </ul>
          </ul>
        </li>
      </ol>
      <p> </p>
      <p>BlockReward() returns the block subsidy plus the transaction
        fees in the block.</p>
      <p><strong>Conditions on constants</strong></p>
      <p>If you want to choose different values of a,b,c,d,e that still
        force miners selections converge into a single parent then these
        conditions must be satisfied:</p>
      <ul>
        <li>e &gt; 0</li>
        <li>1-a-e-b &gt; a-c</li>
        <li>1+e-a-e-b &gt; a-c</li>
        <li>a &gt; 1-a-c-e-b-d</li>
        <li>a+e &gt; 1-a-c-e-b-d</li>
      </ul>
      <p>And all constants are between 0 and 1.</p>
      It's interesting that now it's much easier to prove that for two
      competing miners the DECOR+ protocol cannot be abused, since there
      is no dependence on the block content. <br>
      <br>
      Best regards,<br>
       Sergio.<br>
    </div>
  </body>
</html>

--------------040209020706000103040702--