* [Bitcoin-development] Possible Solution To SM Attack
@ 2013-11-05 20:51 colj
2013-11-05 22:07 ` Quinn Harris
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: colj @ 2013-11-05 20:51 UTC (permalink / raw)
To: Bitcoin-development
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 20:51 [Bitcoin-development] Possible Solution To SM Attack colj
@ 2013-11-05 22:07 ` Quinn Harris
2013-11-05 23:03 ` Drak
2013-11-05 22:15 ` Drak
2013-11-06 0:37 ` rob.golding
2 siblings, 1 reply; 9+ messages in thread
From: Quinn Harris @ 2013-11-05 22:07 UTC (permalink / raw)
To: bitcoin-development
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 20:51 [Bitcoin-development] Possible Solution To SM Attack colj
2013-11-05 22:07 ` Quinn Harris
@ 2013-11-05 22:15 ` Drak
2013-11-05 23:06 ` Gregory Maxwell
2013-11-06 0:37 ` rob.golding
2 siblings, 1 reply; 9+ messages in thread
From: Drak @ 2013-11-05 22:15 UTC (permalink / raw)
To: bitcoin-development
[-- 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 --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 22:07 ` Quinn Harris
@ 2013-11-05 23:03 ` Drak
2013-11-06 0:26 ` Quinn Harris
0 siblings, 1 reply; 9+ messages in thread
From: Drak @ 2013-11-05 23:03 UTC (permalink / raw)
To: bitcoin-development
[-- 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 --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 22:15 ` Drak
@ 2013-11-05 23:06 ` Gregory Maxwell
2013-11-05 23:44 ` Drak
0 siblings, 1 reply; 9+ messages in thread
From: Gregory Maxwell @ 2013-11-05 23:06 UTC (permalink / raw)
To: Drak; +Cc: Bitcoin Development
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 23:06 ` Gregory Maxwell
@ 2013-11-05 23:44 ` Drak
2013-11-06 0:00 ` Gavin Andresen
0 siblings, 1 reply; 9+ messages in thread
From: Drak @ 2013-11-05 23:44 UTC (permalink / raw)
To: bitcoin-development
[-- 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 --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 23:44 ` Drak
@ 2013-11-06 0:00 ` Gavin Andresen
0 siblings, 0 replies; 9+ messages in thread
From: Gavin Andresen @ 2013-11-06 0:00 UTC (permalink / raw)
To: Drak; +Cc: Bitcoin Dev
[-- 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 --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 23:03 ` Drak
@ 2013-11-06 0:26 ` Quinn Harris
0 siblings, 0 replies; 9+ messages in thread
From: Quinn Harris @ 2013-11-06 0:26 UTC (permalink / raw)
To: bitcoin-development
[-- 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 --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Bitcoin-development] Possible Solution To SM Attack
2013-11-05 20:51 [Bitcoin-development] Possible Solution To SM Attack colj
2013-11-05 22:07 ` Quinn Harris
2013-11-05 22:15 ` Drak
@ 2013-11-06 0:37 ` rob.golding
2 siblings, 0 replies; 9+ messages in thread
From: rob.golding @ 2013-11-06 0:37 UTC (permalink / raw)
To: bitcoin-development
> 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
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2013-11-06 1:02 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-11-05 20:51 [Bitcoin-development] Possible Solution To SM Attack colj
2013-11-05 22:07 ` Quinn Harris
2013-11-05 23:03 ` Drak
2013-11-06 0:26 ` Quinn Harris
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
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox