From: Quinn Harris <btcdev@quinnharris•me>
To: bitcoin-development@lists•sourceforge.net
Subject: Re: [Bitcoin-development] Possible Solution To SM Attack
Date: Tue, 05 Nov 2013 21:26:59 -0300 [thread overview]
Message-ID: <52798CD3.3060806@quinnharris.me> (raw)
In-Reply-To: <CANAnSg19N6Ri9vVkKqP2VB14KgLN6=whAbtzV9EBcLUfDs_dJQ@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 3929 bytes --]
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
[-- Attachment #2: Type: text/html, Size: 6372 bytes --]
next prev parent reply other threads:[~2013-11-06 0:27 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-11-05 20:51 colj
2013-11-05 22:07 ` Quinn Harris
2013-11-05 23:03 ` Drak
2013-11-06 0:26 ` Quinn Harris [this message]
2013-11-05 22:15 ` Drak
2013-11-05 23:06 ` Gregory Maxwell
2013-11-05 23:44 ` Drak
2013-11-06 0:00 ` Gavin Andresen
2013-11-06 0:37 ` rob.golding
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=52798CD3.3060806@quinnharris.me \
--to=btcdev@quinnharris$(echo .)me \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox