Received-SPF: pass (sog-mx-1.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: <52796C14.5070300@quinnharris.me>
Date: Tue, 05 Nov 2013 19:07:16 -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>
In-Reply-To: <N1-9eAtMHauq2@Safe-mail.net>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [Bitcoin-development] Possible Solution To SM Attack
Precedence: list

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