[Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Ittay
Hello,

Please see below our BIP for raising the selfish mining threshold.
Looking forward to your comments.

Best,
Ittay

---

Bitcoin Improvement Proposal

Owners: Ittay Eyal and Emin Gun Sirer

We suggest a change in the propagation and mining algorithm for chains of
the same difficulty, to raise the threshold on Selfish Mining attacks.

* Current situation:
When a miner is notified of a new chain of the same difficulty as the one
it is mining on, it will ignore it.

* Background:
The selfish mining attack and its implications were described in detail in
the following research paper:
http://arxiv.org/abs/1311.0243v1

* Proposal:
To thwart selfish mining attacks launched by less than 25% of the mining
power, we propose the following change to the protocol:
When a miner learns of more than one chain of the same difficulty, it
should propagate all of them, and choose one of them to mine on uniformly
at random among all chains of the same difficulty.

When hearing of a chain of maximal difficulty that it did not know of
before:
1. Add it to a local list of maximal difficulty chains.
2. Propagate it to its neighbors.
3. Choose a branch uniformly at random from the local list, and mine on it.

* Example:
t0: learn of chain A of difficulty x.
propagate A to neighbors.
start mining on A.
t1: learn of chain B of difficulty x.
propagate B to neighbors.
toss a coin between A and B; if B wins, switch to mining on B.
t2: learn of chain C of difficulty x.
propagate C to neighbors.
toss a 3 faced coin among A, B, and C; switch to mining on the winning
chain.

* Concerns and answers:
1. No harm to miners when all are honest.
Mining blocks is a random Poisson process, which is memoryless. Having
mined on the block in the past does not provide an advantage in locating a
solution in the future. Therefore, a miner is not harmed by switching the
chain on which it mines.

2. No new vulnerabilities introduced:
Currently the choice among equal-length chains is done arbitrarily,
depending on network topology. This arbitrariness is a source of
vulnerability. We replace it with explicit randomness, which is at the
control of the protocol. The change does not introduce executions that were
not possible with the old protocol.

3. Complete backward compatibility:
Any subset of the miners can switch to the proposed protocol.

4. Progressive improvement:
Each miner that adopts the change raises the threshold a little bit. The
threshold will reach 25% with universal adoption.
--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Peter Todd
On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote:
 Hello,
 
 Please see below our BIP for raising the selfish mining threshold.
 Looking forward to your comments.

snip

 2. No new vulnerabilities introduced:
 Currently the choice among equal-length chains is done arbitrarily,
 depending on network topology. This arbitrariness is a source of
 vulnerability. We replace it with explicit randomness, which is at the
 control of the protocol. The change does not introduce executions that were
 not possible with the old protocol.

Credit goes to Gregory Maxwell for pointing this out, but the random
choice solution does in fact introduce a vulnerability in that it
creates incentives for pools over a certain size to withhold blocks
rather than immediately broadcasting all blocks found.

The problem is that when the pool eventually choses to reveal the block
they mined, 50% of the hashing power switches, thus splitting the
network. Like the original attack this can be to their benefit. For
pools over a certain size this strategy is profitable even without
investing in a low-latency network; Maxwell or someone else can chime in
with the details for deriving that threshold.

I won't get a chance to for a few hours, but someone should do the
analysis on a deterministic switching scheme.

-- 
'peter'[:-1]@petertodd.org
0005e25ca9b9fe62bdd6e8a2b4527ad61753dd2113c268bec707


signature.asc
Description: Digital signature
--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Peter Todd
On Tue, Nov 05, 2013 at 12:05:41PM -0500, Peter Todd wrote:
 On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote:
  Hello,
  
  Please see below our BIP for raising the selfish mining threshold.
  Looking forward to your comments.
 
 snip
 
  2. No new vulnerabilities introduced:
  Currently the choice among equal-length chains is done arbitrarily,
  depending on network topology. This arbitrariness is a source of
  vulnerability. We replace it with explicit randomness, which is at the
  control of the protocol. The change does not introduce executions that were
  not possible with the old protocol.
 
 Credit goes to Gregory Maxwell for pointing this out, but the random
 choice solution does in fact introduce a vulnerability in that it
 creates incentives for pools over a certain size to withhold blocks
 rather than immediately broadcasting all blocks found.
 
 The problem is that when the pool eventually choses to reveal the block
 they mined, 50% of the hashing power switches, thus splitting the
 network. Like the original attack this can be to their benefit. For
 pools over a certain size this strategy is profitable even without
 investing in a low-latency network; Maxwell or someone else can chime in
 with the details for deriving that threshold.
 
 I won't get a chance to for a few hours, but someone should do the
 analysis on a deterministic switching scheme.

Oh, and I don't want to give the wrong impression: there's no need to
rush to get this problem fixed. Even if someone wanted to launch an
attack right now, with a fair amount of resources, there's a lot of
counter-measures based on human intervention that can definitely stop
the attack in the short-term; what's needed is at worst moderate-term,
and much more likely a long-term approach. In addition, keep in mind
that this attack is very easy to detect, so if one is actually launched
we will know immediately and can start taking direct counter-measures at
that time.

That Gregory Maxwell so quickly identified a flaw in this proposed
solution suggests we should proceed carefully.

It'd be good to do a test of this attack, as well as possible solutions,
on testnet to better explore it and possible counter-measures.

-- 
'peter'[:-1]@petertodd.org
000a03ea8c90161a275ee63d077ec35c1b582c77934c0be12a02


signature.asc
Description: Digital signature
--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Alessandro Parisi
Patrick, could you please explain us why the solution proposed by Ittay
would drop the actual honest miners ratio, becoming so backfire? Thanks a
lot


2013/11/5 Patrick patr...@intersango.com

  The ratio of honest miners that mine the first block they see is  0.5

 Your proposed solution would reduce that ratio to 0.5

 In other words your proposed change would make the attack you describe
 easier not harder.


 On 11/05/2013 09:26 AM, Ittay wrote:

 That sounds like selfish mining, and the magic number is 25%. That's the
 minimal pool size.
 Today the threshold is 0% with good connectivity.

  If I misunderstood your point, please elaborate.

  Ittay



 On Tue, Nov 5, 2013 at 12:05 PM, Peter Todd p...@petertodd.org wrote:

 On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote:
  Hello,
 
  Please see below our BIP for raising the selfish mining threshold.
  Looking forward to your comments.

  snip

  2. No new vulnerabilities introduced:
  Currently the choice among equal-length chains is done arbitrarily,
  depending on network topology. This arbitrariness is a source of
  vulnerability. We replace it with explicit randomness, which is at the
  control of the protocol. The change does not introduce executions that
 were
  not possible with the old protocol.

  Credit goes to Gregory Maxwell for pointing this out, but the random
 choice solution does in fact introduce a vulnerability in that it
 creates incentives for pools over a certain size to withhold blocks
 rather than immediately broadcasting all blocks found.

 The problem is that when the pool eventually choses to reveal the block
 they mined, 50% of the hashing power switches, thus splitting the
 network. Like the original attack this can be to their benefit. For
 pools over a certain size this strategy is profitable even without
 investing in a low-latency network; Maxwell or someone else can chime in
 with the details for deriving that threshold.

 I won't get a chance to for a few hours, but someone should do the
 analysis on a deterministic switching scheme.

 --
 'peter'[:-1]@petertodd.org
 0005e25ca9b9fe62bdd6e8a2b4527ad61753dd2113c268bec707




 --
 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 
 registerhttp://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk



 ___
 Bitcoin-development mailing 
 listBitcoin-development@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/bitcoin-development




 --
 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=60136231iu=/4140/ostg.clktrk
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Jeff Garzik
On Tue, Nov 5, 2013 at 1:07 PM, Alessandro Parisi startit...@gmail.com wrote:
 I agree with Ittay: when bugs are found, they must be fixed ASAP, expecially
 when they affect a sensitive sw such as Bitcon; in IT security, every flaw
 that is exploitable in abstract, is going to be exploited in real, sooner or
 later, also taking into account the increasing parallel computing power;
 beware of false sense of security

That is quite ignorant.  Bitcoin is far more complex than standard IT
security fix ASAP mantra.  Distributed consensus is a new field of
computer science, and blindly applying standard logic to bitcoin will
quickly result in large problems.

Every fix has the chance of changing the game theory or economics of
bitcoin.  A change to the core consensus protocol within bitcoin --
mining -- is even more game-theory- and economically-critical to the
core system.  Changes thus have more impact, where any change
potentially reduces bitcoin's value to zero in the worst case.

Bitcoin is akin to medical device or avionics software.  We cannot
just change at will, without significant research, analysis and
testing.   It is a bug, it must be fixed ASAP is ignorant and
dangerous.

Further, this is at present a THEORETICAL problem, and the solution
presented has some obvious flaws, that would make our current, WORKING
SYSTEM more fragile, and less secure.

-- 
Jeff Garzik
Senior Software Engineer and open source evangelist
BitPay, Inc.  https://bitpay.com/

--
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=60136231iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Alessandro Parisi
Thank you very much for your fair response, Sir;
this means that anytime a bug is found in Bitcoin protocol, chances are
that it would take a lot more time to get fixed


2013/11/5 Jeff Garzik jgar...@bitpay.com

 On Tue, Nov 5, 2013 at 1:07 PM, Alessandro Parisi startit...@gmail.com
 wrote:
  I agree with Ittay: when bugs are found, they must be fixed ASAP,
 expecially
  when they affect a sensitive sw such as Bitcon; in IT security, every
 flaw
  that is exploitable in abstract, is going to be exploited in real,
 sooner or
  later, also taking into account the increasing parallel computing power;
  beware of false sense of security

 That is quite ignorant.  Bitcoin is far more complex than standard IT
 security fix ASAP mantra.  Distributed consensus is a new field of
 computer science, and blindly applying standard logic to bitcoin will
 quickly result in large problems.

 Every fix has the chance of changing the game theory or economics of
 bitcoin.  A change to the core consensus protocol within bitcoin --
 mining -- is even more game-theory- and economically-critical to the
 core system.  Changes thus have more impact, where any change
 potentially reduces bitcoin's value to zero in the worst case.

 Bitcoin is akin to medical device or avionics software.  We cannot
 just change at will, without significant research, analysis and
 testing.   It is a bug, it must be fixed ASAP is ignorant and
 dangerous.

 Further, this is at present a THEORETICAL problem, and the solution
 presented has some obvious flaws, that would make our current, WORKING
 SYSTEM more fragile, and less secure.

 --
 Jeff Garzik
 Senior Software Engineer and open source evangelist
 BitPay, Inc.  https://bitpay.com/

--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Jeff Garzik
On Tue, Nov 5, 2013 at 1:55 PM, Alessandro Parisi startit...@gmail.com wrote:
 this means that anytime a bug is found in Bitcoin protocol, chances are that
 it would take a lot more time to get fixed

Correct.  There is significant potential that a fix can create other
problems...   and any major mistake could instantly destroy  $2
billion worth of value.

-- 
Jeff Garzik
Senior Software Engineer and open source evangelist
BitPay, Inc.  https://bitpay.com/

--
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=60136231iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Jeremy Spilman


Great paper Ittay, thanks for all your work on this.
Today the threshold is 0% with good connectivity.Fig. 2 captures this well, the threshold is only zero if 'y' is 1. In Section 6 and 6.1 you argue y - 1 but the sybil attack you describe, isn't that more like how *all* sophisticated miners would want to ensure their blocks are widely propagated? I think you can't assume only the selfish miner is doing it.Based on the current
'first seen'
algorithm, as you say, competing longest chains happen about every 60 blocks. The rest of the time, a single block propagates through the vast majority of the network 'uncontested'. If there are multiple valid longest blocks being simultaneously propagated, then propagation pattern of the competing blocks will determine hash rate on each.Selfish mining requires exploiting the race condition between learning about a competing block, and publishing your own. Usually we talk about minimizing publishing latency so that your block ends up uncontested 59/60 times, and in the 1/60 times, even then your block has the best chance of winning.Selfish mining forgoes the 59/60 chance of your block being uncontested, and instead chooses to 'race the network' every time. You start 'one step behind' the competing block (since of course you only learn about it after it starts propagating), so you must rely on being able to outrace propagation of the competing block through a private low-latency side-network which can inject your block at multiple points throughout the bitcoin p2p network to outrace the competitor.I think it's a stretch to say 'y' is 0 with good connectivity. Even the best connected mining pools today are concerned with this 'y' factor.Here's a probably very dumb idea... to throw out one possible "solution"...You want a way to fake-out the 'selfish miner' into disclosing their blocks -- how can your force their hand to prevent them from accumulating longer private chains?What if you propagate (and relay) an encrypted block header which honest miners will timestamp when they receive it, then 10 seconds later propagate the decryption key to unblind it. But here's the catch - maybe the decryption results in junk, maybe it results a new longer block. If it's a real block then it gets priority based on when the ciphertext was received instead of when the decryption key was received. Now 'selfish miner' can't race the network anymore, because they are always in state 0' and can't tell if they are up against a ghost, or a real competing block. If they wait for the decryption key to check, it's too late, and they are guaranteed to lose unless they can out-race the network, e.g. back at t=50%. Of course there would need to be some way to anti-DDoS this which allows for some amount of these fake-outs without letting them get out of hand.Thanks,Jeremy--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Jameson Lopp
The conversations that spawned from this paper have been fascinating to 
read, but I have a problem with the conclusions. To quote the paper:

The Bitcoin ecosystem is open to manipulation, and potential takeover, 
by miners seeking to maximize their rewards. This paper presented 
Selfish-Mine, a mining strategy that enables pools of colluding miners
that adopt it to earn revenues in excess of their mining power. Higher 
revenues can lead new rational miners to join selsh miner pools, 
leading to a collapse of the decentralized currency.

Please explain to me why any rational miner would collude to earn 
slightly higher short term profits at the expense of then wiping out the 
value of all their bitcoins in the long term.

Also, if you felt that this vulnerability is an immediate danger to the 
Bitcoin network, why publish the vulnerability publicly rather than 
first disclosing it privately to the core developers? Apologies if you 
did disclose it privately in the past; I've seen no mention of it.
--
Jameson Lopp
Software Engineer
Bronto Software

On 11/05/2013 01:58 PM, Jeff Garzik wrote:
 On Tue, Nov 5, 2013 at 1:55 PM, Alessandro Parisi startit...@gmail.com 
 wrote:
 this means that anytime a bug is found in Bitcoin protocol, chances are that
 it would take a lot more time to get fixed

 Correct.  There is significant potential that a fix can create other
 problems...   and any major mistake could instantly destroy  $2
 billion worth of value.


--
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=60136231iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


[Bitcoin-development] Possible Solution To SM Attack

2013-11-05 Thread 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

--
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=60136231iu=/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

2013-11-05 Thread 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, c...@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=60136231iu=/4140/ostg.clktrk
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--
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=60136231iu=/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

2013-11-05 Thread Drak
On 5 November 2013 20:51, c...@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
--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.

2013-11-05 Thread Ittay
On Tue, Nov 5, 2013 at 1:57 PM, Jeremy Spilman jer...@taplink.co wrote:


 I think it's a stretch to say 'y' is 0 with good connectivity. Even the
 best connected mining pools today are concerned with this 'y' factor.


Check out the following paper for the effect a single node can have on
propagation, and on the relation between block size and propagation speed.
This strongly supports our assumption.
http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf



 Here's a probably very dumb idea... to throw out one possible solution...

 You want a way to fake-out the 'selfish miner' into disclosing their
 blocks -- how can your force their hand to prevent them from accumulating
 longer private chains?

 What if you propagate (and relay) an encrypted block header which honest
 miners will timestamp when they receive it, then 10 seconds later propagate
 the decryption key to unblind it. But here's the catch - maybe the
 decryption results in junk, maybe it results a new longer block. If it's a
 real block then it gets priority based on when the ciphertext was received
 instead of when the decryption key was received. Now 'selfish miner' can't
 race the network anymore, because they are always in state 0' and can't
 tell if they are up against a ghost, or a real competing block. If they
 wait for the decryption key to check, it's too late, and they are
 guaranteed to lose unless they can out-race the network, e.g. back at
 t=50%. Of course there would need to be some way to anti-DDoS this which
 allows for some amount of these fake-outs without letting them get out of
 hand.


That's a dangerous way to go, opening the door to DoS attacks, as you
mention. Besides, it makes a simple algorithm complicated, and doing such
changes may lead to different vulnerabilities that are difficult to cover.

Best,
Ittay
--
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=60136231iu=/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

2013-11-05 Thread Drak
On 5 November 2013 22:07, Quinn Harris btc...@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
--
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=60136231iu=/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

2013-11-05 Thread Gregory Maxwell
On Tue, Nov 5, 2013 at 2:15 PM, Drak d...@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.

--
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=60136231iu=/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

2013-11-05 Thread Drak
On 5 November 2013 23:06, Gregory Maxwell gmaxw...@gmail.com wrote:

 On Tue, Nov 5, 2013 at 2:15 PM, Drak d...@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
--
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=60136231iu=/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

2013-11-05 Thread Quinn Harris

On 11/05/2013 08:03 PM, Drak wrote:
On 5 November 2013 22:07, Quinn Harris btc...@quinnharris.me 
mailto:btc...@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=60136231iu=/4140/ostg.clktrk


___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Message Signing based authentication

2013-11-05 Thread Melvin Carvalho
On 2 November 2013 22:57, slush sl...@centrum.cz wrote:

 Glad to see that there are more and more people wanting to replace
 passwords with digital signatures.

 Although such method has been already used on other websites like Eligius
 or bitcoin-otc, I dont think theres any standard way to doing so yet.

 Two comments to your proposal:

 A) message-to-be-signed need to be carefully composed to be both
 structured and human readable. It should contain at least:
 Desired username/identity handler
 Server identifier (url)
 Timestamp to prevent replay attack
 Server challenge

 Then the user can see what he's signing, instead of signing some binary
 blob which can contain some evil data.

 B)
 Same structured data should be a part of html page in some header tag,
 ideally signed by server certificate to confirm that the request is valid.
 Then the login request can be processed by machine automatically, without a
 need of copypaste by a user.

But where are the private keys stored?  Crypto in the browser with help,
but although they will expose ECC via the NSS, I dont think bitcoin's
particular curve will be supported, because it's not NIST approved.  If the
use case was presented though, they may add it.

This can actually be done today using client side certificates.  Two
methods.

Method 1:

In your client side certificate, put in your bitcoin address in the
subjectAlternativeName field.  This is a field that lets you tell the
server I have another identity

From the bitcoin address look up via a .well-known key server some items
previously uploaded.  This would normally be a signed value of the key
used, or a signed value of the the certificate.  The server checks this and
logs you in.

Method 2:

In your client side certificate, put in an HTTP address.  That HTTP address
contains your bitcoin address and a signed copy of your cert public key or
the cert itself.

The advantage here is that you dont need a key server.


Both methods work, I've been doing this kind of thing for 5 years+, and I'd
never go back to passwords on anything I build.

I'm all for recreating this UI in javascript too, but I just wonder how to
protect the private keys ...


 Slush


 On Sat, Nov 2, 2013 at 6:01 AM, bitcoingr...@gmx.com wrote:

 Passwords are inefficient by design: frequently we hear news from Sony,
 Square Enix, Adobe, and various others about passwords being compromised,
 databases being copied and stolen. This story remains true in the Bitcoin
 space. In light of the recent Bitcointalk forum breach echoes an increasing
 need for passwords to become a thing of the past.



 In celebration of the 5 year anniversary of the Bitcoin whitepaper, we
 are delighted to introduce the Message Signing based authentication method.



 In brief, the authentication work as follows:



 Server provides a token for the client to sign.

 client passes the signed message and the bitcoin address back to the
 server.

 server validates the message and honors the alias (optional) and bitcoin
 address as identification.



 http://forums.bitcoingrant.org/



 Above is a proof of concept forum that utilize this authentication
 method. Following Kerckhoffs's principle, this forum only stores the signed
 message and bitcoin address the users provide the first time they use the
 site, both are public information. In addition, there is no database,
 everything is simply an RSS feed. For the sake of usability we have
 included a redis for the sessions, at the cost of additional exposure to
 potential risks: users no longer need to sign a token every time they wish
 to post.



 All source code will be available on github in the next few days.



 We welcome any feedback or suggestions.





 --
 Android is increasing in popularity, but the open development platform
 that
 developers love is also attractive to malware creators. Download this
 white
 paper to learn more about secure code signing practices that can help keep
 Android apps secure.

 http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development




 --
 Android is increasing in popularity, but the open development platform that
 developers love is also attractive to malware creators. Download this white
 paper to learn more about secure code signing practices that can help keep
 Android apps secure.
 http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development



Re: [Bitcoin-development] Message Signing based authentication

2013-11-05 Thread Melvin Carvalho
On 2 November 2013 22:14, Johnathan Corgan johnat...@corganlabs.com wrote:

 On 11/01/2013 10:01 PM, bitcoingr...@gmx.com wrote:

  Server provides a token for the client to sign.

 Anyone else concerned about signing an arbitrary string?  Could be a
 hash of $EVIL_DOCUMENT, no?  I'd want to XOR the string with my own
 randomly generated nonce, sign that, then pass the nonce and the
 signature back to the server for verification.


Good point.

There are actually times you may want to sign a transaction.

There's a little know HTTP code, 402, Payment Required.  We should really
start using this at some point ...

http://en.wikipedia.org/wiki/List_of_HTTP_status_codes

Reserved for future use.[2] The original intention was that this code might
be used as part of some form of digital cash or micropayment scheme, but
that has not happened, and this code is not usually used. As an example of
its use, however, Apple's defunct MobileMe service generated a 402 error if
the MobileMe account was delinquent.[citation needed] In addition, YouTube
uses this status if a particular IP address has made excessive requests,
and requires the person to enter a CAPTCHA.



 --
 Johnathan Corgan, Corgan Labs
 SDR Training and Development Services
 http://corganlabs.com


 --
 Android is increasing in popularity, but the open development platform that
 developers love is also attractive to malware creators. Download this white
 paper to learn more about secure code signing practices that can help keep
 Android apps secure.
 http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--
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=60136231iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


[Bitcoin-development] [ANN] High-speed Bitcoin Relay Network

2013-11-05 Thread Matt Corallo
Recently, there has been a reasonable amount of discussion about the
continued fragility of the public Bitcoin network on IRC and elsewhere
(1). To this extent, I'm organizing a system of peering between nodes in
the network by creating a system of high-speed relay nodes for miners
and merchants/exchanges. This system will a) act as a fallback in the
case that the public Bitcoin network encounters issues and b) decrease
block propagation times between miners.
It is NOT designed to in any way replace or decrease the need for the
public Bitcoin P2P network. It is NOT any kind of attempt at
centralization, and I still encourage interested parties to establish
their own private peering agreements with large miners as needed.

Currently the network consists of one specially-designed relay node, but
I hope to bring more online in the coming days.

This network is open to everyone via a few public relay nodes, but also
will have nodes which are made available only to large miners and
merchants/exchanges to mitigate the ability of malicious parties to DoS
the network.

To peer with the public relay nodes, simply select the closest region
out of us-west (West Coast US), us-east (East Coast US), eu (Western
Europe), au (Australia), or jpy (Japan) and add
public.REGION.relay.mattcorallo.com to your addnode list. Note that
since all of the relay nodes will relay between each other, you gain no
latency advantage by peering with more than the closest node to you (and
currently all the regions map to one node, so there they're redundant
anyway).

For each relay node, you can connect to either port 8334 or 8335.
Connecting on port 8334 will relay only blocks, and port 8335 will relay
both blocks and transactions. The relay nodes will request any
transactions which appear in your invs no matter which port you connect to.

Relay node details:
 * The relay nodes do some data verification to prevent DoS, but in
order to keep relay fast, they do not fully verify the data they are
relaying, thus YOU SHOULD NEVER mine a block building on top of a
relayed block without fully checking it with your own bitcoin validator
(as you would any other block relayed from the P2P network).
 * The relay nodes do not follow the standard inv-getdata-tx/block flow,
but instead relay transactions/blocks immediately after they have done
their cursory verification. They do keep some track of whether or not
your nodes claim to have seen the transactions/blocks before relaying,
but you may see transactions/blocks being sent which you already have
and have not requested, if this is a problem for you due to bandwith
issues, you should reconsider your bandwith constraints and/or are
peering with too many nodes.
 * The relay nodes will all relay among themselves very quickly, so
there is no advantage to peering with as many relay nodes as you can
find, in fact, the increased incoming bandwidth during block relay
spikes may result in higher latency for your nodes.
 * The relay nodes are NOT designed to ensure that you never miss data,
and may fail to relay some transactions. Additionally, because the relay
nodes do not respond to standard getdata requests, if you miss a relay
and then reconnect, that data will not be sent again by the relay nodes.
The relay nodes are NOT a replacement for having peers on the standard
P2P network, they are only there to augment the existing P2P network.

If you are a merchant/exchange/large miner/other important node operator
and wish to gain access to additional domain names which map to relay
nodes with fewer peers, please fill out the form at
https://docs.google.com/forms/d/1UL82QdcXXEhZwSHJAK04Sk_cWg4zLOu8a216nO7Mt8c/viewform

You can find the source for the relay nodes at
https://github.com/TheBlueMatt/RelayNode

If you have any comments/concerns/suggestions, please do not hesitate to
email bitcoin-peer...@mattcorallo.com

Thanks,
Matt


(1) There has been extended discussion on #bitcoin-wizards as well as
#bitcoin-dev of the very small number of active, listening nodes.
Additionally, because many of those nodes are versions prior to 0.8.4,
it seems very likely that maliciously creating network splits or at
least drastically reducing the number of peers for most nodes would not
be particularly challenging in the current network. Also,
http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf
noted that they were able to single-handledly decrease the network-wide
orphan rate by around 50% by improving network peering. Finally, you've
all seen the recent discussion on malicious mining algorithms. Though
those are not entirely prevented by reducing block propagation times,
they can be significantly limited compared to the current, rather
disjoint, network.

--
November Webinars for C, C++, Fortran Developers
Accelerate application performance with scalable programming models. Explore
techniques for threading, error