[Bitcoin-development] Possible Solution To SM Attack

[Bitcoin-development] Possible Solution To SM Attack

[colj]

Preliminary:
Alice has the ability to hear of a block before all other miners do.

The Problem:
Say Alice built a block, A1, from previous block 0. She doesn't let other miners know about it. She then works on A2 with previous block A1. Bob on the other hand is still working on B1 with previous block 0. Bob now finds a block and he broadcasts it. The assumption here is Alice will be the first miner to hear of this block and she will send her previously mined block, A1, to all other miners. By the time Bobs block arrives to other miners majority of them will already have received Block A1 and Bobs block will most likely be orphaned. Alice revealed her block, A1, only when Bob broadcast his block. This means she has been mining on block A2 with previous block A1 for longer than any other miner thus gaining an advantage without increasing her hash rate.

What We Know:
Alice has gained an advantage with time. She mines longer on the valid block.
In order for this attack to work Alice must reveal her previously mined block as late as possible, gaining her the most time spent working on the valid block. Since she has such good view of the Bitcoin network she can wait until a miner finds a block to release her previously mined block.

The most obvious sign of this attack taking place is the timing. A miner will receive a block and very quickly hear of another block both built from the same previous block.

The block that a miner hears first is the one which will be mined on.

Possible Solution:
If N amount of blocks built of the same previous block are received within a time frame of T mine on the block with the lowest hash.

Logic:
In order for Alice to pull of this attack she not only has to propagate her blocks first she must also ensure her blocks are of the smallest hash.

Alice would now have to decrease her target to pull of this attack. Since she has a lower target it will take her longer to find a valid block negating her time advantage.


colj

Re: [Bitcoin-development] Possible Solution To SM Attack

[Quinn Harris]

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.

Its better if the block is chosen in a way that doesn't let Alice know 
the probability her block will be chosen.  One simple possibility is to 
start at the least significant bit of the hash and whichever has a 1 is 
chosen and if both bits are the same the next bit is used.

This should be pseudo random and not give Alice any knowledge ahead of 
time if her block will be chosen.  This would prevent the network hash 
power from being split between two branches unlike each node choosing a 
random block.

Quinn

On 11/05/2013 05:51 PM, colj@Safe-mail.net wrote:
> Preliminary:
> Alice has the ability to hear of a block before all other miners do.
>
> The Problem:
> Say Alice built a block, A1, from previous block 0. She doesn't let other miners know about it. She then works on A2 with previous block A1. Bob on the other hand is still working on B1 with previous block 0. Bob now finds a block and he broadcasts it. The assumption here is Alice will be the first miner to hear of this block and she will send her previously mined block, A1, to all other miners. By the time Bobs block arrives to other miners majority of them will already have received Block A1 and Bobs block will most likely be orphaned. Alice revealed her block, A1, only when Bob broadcast his block. This means she has been mining on block A2 with previous block A1 for longer than any other miner thus gaining an advantage without increasing her hash rate.
>
> What We Know:
> Alice has gained an advantage with time. She mines longer on the valid block.
> In order for this attack to work Alice must reveal her previously mined block as late as possible, gaining her the most time spent working on the valid block. Since she has such good view of the Bitcoin network she can wait until a miner finds a block to release her previously mined block.
>
> The most obvious sign of this attack taking place is the timing. A miner will receive a block and very quickly hear of another block both built from the same previous block.
>
> The block that a miner hears first is the one which will be mined on.
>
> Possible Solution:
> If N amount of blocks built of the same previous block are received within a time frame of T mine on the block with the lowest hash.
>
> Logic:
> In order for Alice to pull of this attack she not only has to propagate her blocks first she must also ensure her blocks are of the smallest hash.
>
> Alice would now have to decrease her target to pull of this attack. Since she has a lower target it will take her longer to find a valid block negating her time advantage.
>
>
> colj
>
> ------------------------------------------------------------------------------
> 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

Re: [Bitcoin-development] Possible Solution To SM Attack

[Drak]

[-- Attachment #1: Type: text/plain, Size: 1118 bytes --]

On 5 November 2013 22:07, Quinn Harris <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.

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

[-- Attachment #2: Type: text/html, Size: 1525 bytes --]

Re: [Bitcoin-development] Possible Solution To SM Attack

[Quinn Harris]

[-- 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 --]

Re: [Bitcoin-development] Possible Solution To SM Attack

[Drak]

[-- Attachment #1: Type: text/plain, Size: 841 bytes --]

On 5 November 2013 20:51, <colj@safe-mail.net> wrote:

> Possible Solution:
> If N amount of blocks built of the same previous block are received within
> a time frame of T mine on the block with the lowest hash.
>
> Logic:
> In order for Alice to pull of this attack she not only has to propagate
> her blocks first she must also ensure her blocks are of the smallest hash.
>
> Alice would now have to decrease her target to pull of this attack. Since
> she has a lower target it will take her longer to find a valid block
> negating her time advantage.


If I understand the issue properly, this seems like a pretty elegant
solution: if two blocks are broadcast within a certain period of eachother,
chose the lower target. That's a provable fair way of randomly choosing the
winning block and would seem like a pretty simply patch.

Drak

[-- Attachment #2: Type: text/html, Size: 1251 bytes --]

Re: [Bitcoin-development] Possible Solution To SM Attack

[Gregory Maxwell]

On Tue, Nov 5, 2013 at 2:15 PM, Drak <drak@zikula.org> wrote:
> If I understand the issue properly, this seems like a pretty elegant
> solution: if two blocks are broadcast within a certain period of eachother,
> chose the lower target. That's a provable fair way of randomly choosing the
> winning block and would seem like a pretty simply patch.

uh. and so when my solution is, by chance, unusually low... I am
incentivized to hurry up and release my block because?

I've simulated non-first-block-heard strategies in the past (in the
two nearly tied miner with network latency model) and they result in
significant increase in large (e.g. >>6 block) reorgs). It's easy to
make convergence worse or to create additional perverse incentives.

Re: [Bitcoin-development] Possible Solution To SM Attack

[Drak]

[-- Attachment #1: Type: text/plain, Size: 1424 bytes --]

On 5 November 2013 23:06, Gregory Maxwell <gmaxwell@gmail.com> wrote:

> On Tue, Nov 5, 2013 at 2:15 PM, Drak <drak@zikula.org> wrote:
> > If I understand the issue properly, this seems like a pretty elegant
> > solution: if two blocks are broadcast within a certain period of
> eachother,
> > chose the lower target. That's a provable fair way of randomly choosing
> the
> > winning block and would seem like a pretty simply patch.
>
> uh. and so when my solution is, by chance, unusually low... I am
> incentivized to hurry up and release my block because?


Yes, I saw the flaw as pointed out by Quinn so I then suggested two step
solution:

1. Decide high or low by taking a the leading bytes from
hash(alice)+hash(bob): above certain number we the rule is "higher wins",
below a certain number the "lower hash wins"
2. Chose winner based on the higher or lower of hash(alice) or hash(bob)
based on the rule coming from 1

Now you have a situation where you don't know the rules of the game in
advance (whether high or low wins) until the hands are already dealt nor
have any idea about how high or low Bob's hash will be since it's not based
on target anymore, but on a hash of the blockhash so it makes it a guessing
game.

You might have an unusually high or low hash, but then you have no idea
whether higher or lower is going to win. So it is better for Alice to just
broadcast the block.

What do you think?

Drak

[-- Attachment #2: Type: text/html, Size: 2100 bytes --]

Re: [Bitcoin-development] Possible Solution To SM Attack

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 635 bytes --]

> What do you think?
>

I would like to be convinced that there is, actually, a real-world problem
before thinking about potential solutions.

I'd like to see more analysis of the proposed selfish-mining algorithm at a
particular share-of-network and gamma=0 (assume second-broadcast blocks
always lose, to make the math easier). I can't reproduce the finding in the
paper if I take into account the "opportunity cost" of working on more
blocks in the private chain that might be orphaned instead of always simply
extending the public chain, but it is very possible my little brain is
missing something obvious.

-- 
--
Gavin Andresen

[-- Attachment #2: Type: text/html, Size: 1216 bytes --]

Re: [Bitcoin-development] Possible Solution To SM Attack

[rob.golding]

> The Problem:
> Say Alice built a block, A1, from previous block 0. She doesn't let
> other miners know about it. She then works on A2 with previous block
> A1. Bob on the other hand is still working on B1 with previous block
> 0. Bob now finds a block and he broadcasts it. The assumption here is
> Alice will be the first miner to hear of this block and she will send
> her previously mined block, A1, to all other miners. By the time Bobs
> block arrives to other miners majority of them will already have
> received Block A1 and Bobs block will most likely be orphaned. Alice
> revealed her block, A1, only when Bob broadcast his block. This means
> she has been mining on block A2 with previous block A1 for longer than
> any other miner thus gaining an advantage without increasing her hash
> rate.

Unless A1 gets orphaned and B1 gets accepted, in which case all the work 
done on A2 is 'wasted'.

The question is whether there is any 'real' advantage over time for A 
over B.

> What We Know:
> Alice has gained an advantage with time. She mines longer on the valid 
> block.

She mines longer on *a* block which *may* become the valid block, yes.

> In order for this attack to work Alice must reveal her previously
> mined block as late as possible, gaining her the most time spent
> working on the valid block. Since she has such good view of the
> Bitcoin network she can wait until a miner finds a block to release
> her previously mined block.

Then the simple 'fix' would be for the block-acceptance to take into 
account either the total transactions or the total fees, and for the the 
'accepted' block for mining the next block to be the one with the lowest 
hash of one of those values if 2 are released to the network at the same 
time

That is of of course assuming there is really a problem to fix, 
currently I'm not convinced.

Rob