Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of quinnharris.me
	designates 67.223.164.214 as permitted sender)
	client-ip=67.223.164.214; envelope-from=btcdev@quinnharris.me;
	helo=fza.durangomail.com; 
Message-ID: <52798CD3.3060806@quinnharris.me>
Date: Tue, 05 Nov 2013 21:26:59 -0300
From: Quinn Harris <btcdev@quinnharris.me>
User-Agent: Mozilla/5.0 (X11; Linux i686;
	rv:24.0) Gecko/20100101 Thunderbird/24.1.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <N1-9eAtMHauq2@Safe-mail.net> <52796C14.5070300@quinnharris.me>
	<CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com>
In-Reply-To: <CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com>
Content-Type: multipart/alternative;
	boundary="------------000601080001070909040108"
Subject: Re: [Bitcoin-development] Possible Solution To SM Attack
Precedence: list

This is a multi-part message in MIME format.
--------------000601080001070909040108
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

On 11/05/2013 08:03 PM, Drak wrote:
> On 5 November 2013 22:07, Quinn Harris <btcdev@quinnharris.me 
> <mailto:btcdev@quinnharris.me>> wrote:
>
>     I don't think choosing the block with the lowest hash is the best
>     option.  The good and bad miners have an equal probability of
>     finding a
>     lower hash.  But after Alice finds a block she can easily
>     determine the
>     probability that someone else will find a lower hash value that meets
>     the difficulty requirement.  This can be used to judge if its best to
>     start working on the next block or work on finding a lower value
>     hash to
>     increase the chance her block is used.
>
>
> Well in that case, you could make it unpredictable by choosing based 
> on a hash of the blockhash and chose the lowest from two. There is no 
> way for Alice to know if Bob's resulting hash will be higher or lower 
> than hers since she does not know Bob's blockhash in advance and 
> therefore she would be better broadcasting her block immediately.
>
I don't think that will work but the bit test I suggested won't work either.

Alice can calculate the hash of her blockhash and if the block to mine 
is chosen based on the lowest result she will know the probability Bobs 
block will be used.  This complexity doesn't change anything.  If hers 
is more than 50% likely to be used she should mine the next block 
otherwise its best to work to find a better current block.

But if the block determination takes into account the current difficulty 
we can prevent Alice from knowing if Bobs or any block she mines is more 
likely to win.

Assuming
a = hash of block A
b = hash of block B
difficulty = current difficulty such that A < difficulty and b < difficulty

The following code could be used to determine if the higher or lower 
block should be chosen

uint256 choose_block(uint256 a, uint256 b, uint256 difficulty)
{
   bool choice = false; // false for lower hash, true for greater hash
   uint256 am = (a + d/4) % difficulty;
   uint256 bm = (b + d/4) % difficulty
   if (a + d/4 >= d)
     choice = b > a || b < am || bm > a || bm < am;
   else
     choice = (b > a && b < am) || (bm > a && bm < am);
   return choice ? (a > b ? a : b) : (a > b ? b : a);
}

The basic idea is to find a range over 0 to difficulty starting at A and 
B that is 1/4 of the range of the difficulty.  If the two ranges overlap 
which should be 1/2 of the time pick the greater hash is used otherwise 
the lower hash.

There is likely a cleaner solution but this demonstrates the basic idea.

You could use the hash of the blockhash and just set the difficulty to 
the maximum hash value which would really just end up removing all the 
modulus stuff and make the code simpler.  But that code requires much 
less computation that any cryptographic hash.

I think this is preferable to each node randomly picking a block to mine 
on as the paper suggests.  This should be completely unpredictable but 
deterministic so all the miners should end up working on the same block.

> You could even add another unpredictable factor: deciding the rules of 
> whether higher or lower wins by hashing both competing blockhashes. If 
> the leading two hex digits are below 128 lower wins, and if above, 
> higher wins.
>
> Drak
>
>
> ------------------------------------------------------------------------------
> November Webinars for C, C++, Fortran Developers
> Accelerate application performance with scalable programming models. Explore
> techniques for threading, error checking, porting, and tuning. Get the most
> from the latest Intel processors and coprocessors. See abstracts and register
> http://pubads.g.doubleclick.net/gampad/clk?id=60136231&iu=/4140/ostg.clktrk
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--------------000601080001070909040108
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

<html>
  <head>
    <meta content="text/html; charset=ISO-8859-1"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <div class="moz-cite-prefix">On 11/05/2013 08:03 PM, Drak wrote:<br>
    </div>
    <blockquote
cite="mid:CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com"
      type="cite">
      <div dir="ltr">On 5 November 2013 22:07, Quinn Harris <span
          dir="ltr">&lt;<a moz-do-not-send="true"
            href="mailto:btcdev@quinnharris.me" target="_blank">btcdev@quinnharris.me</a>&gt;</span>
        wrote:<br>
        <div class="gmail_extra">
          <div class="gmail_quote">
            <blockquote class="gmail_quote" style="margin:0 0 0
              .8ex;border-left:1px #ccc solid;padding-left:1ex">I don't
              think choosing the block with the lowest hash is the best<br>
              option. &nbsp;The good and bad miners have an equal probability
              of finding a<br>
              lower hash. &nbsp;But after Alice finds a block she can easily
              determine the<br>
              probability that someone else will find a lower hash value
              that meets<br>
              the difficulty requirement. &nbsp;This can be used to judge if
              its best to<br>
              start working on the next block or work on finding a lower
              value hash to<br>
              increase the chance her block is used.</blockquote>
            <div><br>
            </div>
            <div>Well in that case, you could make it unpredictable by
              choosing based on a hash of the blockhash and chose the
              lowest from two. There is no way for Alice to know if
              Bob's resulting hash will be higher or lower than hers
              since she does not know Bob's blockhash in advance and
              therefore she would be better broadcasting her block
              immediately.</div>
            <div><br>
            </div>
          </div>
        </div>
      </div>
    </blockquote>
    I don't think that will work but the bit test I suggested won't work
    either.<br>
    <br>
    Alice can calculate the hash of her blockhash and if the block to
    mine is chosen based on the lowest result she will know the
    probability Bobs block will be used.&nbsp; This complexity doesn't change
    anything.&nbsp; If hers is more than 50% likely to be used she should
    mine the next block otherwise its best to work to find a better
    current block.<br>
    <br>
    But if the block determination takes into account the current
    difficulty we can prevent Alice from knowing if Bobs or any block
    she mines is more likely to win.<br>
    <br>
    Assuming<br>
    a = hash of block A<br>
    b = hash of block B<br>
    difficulty = current difficulty such that A &lt; difficulty and b
    &lt; difficulty<br>
    <br>
    The following code could be used to determine if the higher or lower
    block should be chosen<br>
    <br>
    uint256 choose_block(uint256 a, uint256 b, uint256 difficulty)<br>
    {<br>
    &nbsp; bool choice = false; // false for lower hash, true for greater
    hash<br>
    &nbsp; uint256 am = (a + d/4) % difficulty;<br>
    &nbsp; uint256 bm = (b + d/4) % difficulty<br>
    &nbsp; if (a + d/4 &gt;= d)<br>
    &nbsp;&nbsp;&nbsp; choice = b &gt; a || b &lt; am || bm &gt; a || bm &lt; am;<br>
    &nbsp; else<br>
    &nbsp;&nbsp;&nbsp; choice = (b &gt; a &amp;&amp; b &lt; am) || (bm &gt; a
    &amp;&amp; bm &lt; am);<br>
    &nbsp; return choice ? (a &gt; b ? a : b) : (a &gt; b ? b : a);<br>
    }<br>
    <br>
    The basic idea is to find a range over 0 to difficulty starting at A
    and B that is 1/4 of the range of the difficulty.&nbsp; If the two ranges
    overlap which should be 1/2 of the time pick the greater hash is
    used otherwise the lower hash.&nbsp; <br>
    <br>
    There is likely a cleaner solution but this demonstrates the basic
    idea.<br>
    <br>
    You could use the hash of the blockhash and just set the difficulty
    to the maximum hash value which would really just end up removing
    all the modulus stuff and make the code simpler.&nbsp; But that code
    requires much less computation that any cryptographic hash.<br>
    <br>
    I think this is preferable to each node randomly picking a block to
    mine on as the paper suggests.&nbsp; This should be completely
    unpredictable but deterministic so all the miners should end up
    working on the same block.<br>
    <br>
    <blockquote
cite="mid:CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <div>You could even add another unpredictable factor:
              deciding the rules of whether higher or lower wins by
              hashing both competing blockhashes. If the leading two hex
              digits are below 128 lower wins, and if above, higher
              wins.</div>
            <div><br>
            </div>
            <div>Drak</div>
          </div>
        </div>
      </div>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">------------------------------------------------------------------------------
November Webinars for C, C++, Fortran Developers
Accelerate application performance with scalable programming models. Explore
techniques for threading, error checking, porting, and tuning. Get the most 
from the latest Intel processors and coprocessors. See abstracts and register
<a class="moz-txt-link-freetext" href="http://pubads.g.doubleclick.net/gampad/clk?id=60136231&amp;iu=/4140/ostg.clktrk">http://pubads.g.doubleclick.net/gampad/clk?id=60136231&amp;iu=/4140/ostg.clktrk</a></pre>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
Bitcoin-development mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-development@lists.sourceforge.net</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/bitcoin-development">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a>
</pre>
    </blockquote>
    <br>
  </body>
</html>

--------------000601080001070909040108--