Re: [Bitcoin-development] we can all relax now

2014-05-10 Thread E willbefull
I've created a simulation framework called simbit to simulate the selfish
mining attack, though it is general enough to simulate any p2p network. I
even put together a rough simulation of MinCen. The goal is to be fun/easy
to rapidly prototype protocols and strategies, and visualize them. It's
written in javascript, so it can be demoed in the web browser or run on
Node.

It's still in early alpha and a lot of things are missing.

https://github.com/ebfull/simbit

https://bitcointalk.org/index.php?topic=603171.0

Feedback is appreciated!


On Tue, Nov 5, 2013 at 10:33 PM, kjj bitcoin-de...@jerviss.org wrote:

 One of the things that really gets me going is when someone devises a
 model, tests it against itself, and then pretends that they've learned
 something about the real world.

 Naturally, the Selfish Mining paper is exactly this sort of nonsense.
 Their model is one with no latency, and one where the attacker has total
 visibility across the network.  An iterated FSM is not a suitable
 simulation of the bitcoin system.  The bitcoin network does not have
 states, and to the extent that you can pretend that we do, you can't
 simulate transitions between them with static probabilities.

 The authors understand this deep down inside, even though they didn't
 work out the implications.  They handwave the issue by assuming a total
 sybil attack, and in true academic spirit, they don't realize that the
 condition necessary for the attack is far, far worse than the attack
 itself.

 Greg said he'd like to run some simulations, and I'm thinking about it
 too.  Unfortunately, he is busy all week, and I'm lazy (and also busy
 for most of tomorrow).

 If neither of us get to it first, I'm willing to pitch in 1 BTC as a
 bounty for building a general bitcoin network simulator framework. The
 simulator should be able to account for latency between nodes, and
 ideally within a node.  It needs to be able to simulate an attacker that
 owns varying fractions of the network, and make decisions based only on
 what the attacker actually knows.  It needs to be able to simulate this
 attack and should be generic enough to be easily modified for other
 crazy schemes.

 (Bounty offer is serious, but expires in one year [based on the earliest
 timestamp that my mail server puts on this email], and /may/ be subject
 to change if the price on any reputable exchange breaks 1000 USD per BTC
 in that period.)

 Basically, the lack of a decent network simulator is what allowed this
 paper to get press.  If the author had been able to see the importance
 of the stuff he was ignoring, we wouldn't be wasting so much time
 correcting him (and sadly the reporters that have no way to check his
 claims).

 https://bitcointalk.org/index.php?topic=324413.msg3495663#msg3495663




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

--
Is your legacy SCM system holding you back? Join Perforce May 7 to find out:
#149; 3 signs your SCM is hindering your productivity
#149; Requirements for releasing software faster
#149; Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] we can all relax now

2013-11-08 Thread Gregory Maxwell
On Fri, Nov 8, 2013 at 11:49 AM, Andreas M. Antonopoulos
andr...@rooteleven.com wrote:
 Nicholas Weaver is reporting that pools have already started delaying
 blocks, something that hints at Selfish Mining, since Nov. 3rd.
 https://medium.com/something-like-falling/d321a2ef9317

 He dismisses other reasons for delayed block propagation.

 Any ideas on whether pools are already mucking around with block delaying
 tactics?

 I have no idea if this report is accurate or explained by some other issue
 in the network, does anyone here have a comment on this?

The BC.i timestamps have historically been inaccurate relative to my
local GPS clock measurements on my own nodes... but not just that, it
sounds like he's comparing block timestamps and bc.i numbers.

Thats insane, because it tells you the delay between when the miner
_started_ a work unit and when BC.i claims to have found it. Even
assuming bc.i's times were accurate and assuming miner clocks are
accurate (they are often not) you expect there to be be a gap because
it takes time to compute work, send it to the miner, search for a
valid nonce (an average of 2^31 hash operations, often executed
sequentially on a single core taking ten seconds or so on a lot of
hardware) and then return a result.

Evidence of selfish miners wouldn't be block timestamps (which are
inaccurate and controlled by miners anyways), or data on
blockchain.info (which is inaccurate and controlled by bc.i) ... but
the existence of an unusual amount of orphan blocks. High levels of
blocks are _necessary_ evidence of this sort of things, there can be
other explanations of high orphaning levels, but they're required here
and couldn't be faked.

--
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] we can all relax now

2013-11-07 Thread Peter Todd
On Wed, Nov 06, 2013 at 10:59:28PM -0600, Kyle Jerviss wrote:
 Each block that you solve has a reward.  In practice, some blocks
 will be orphaned, so the expected reward is slightly less than the
 nominal reward.  Each second that you delay publishing a block, the
 expected reward drops somewhat.

You don't understand how to read papers.

A good author will state his assumptions. For instance my third
paragraph read:

Now in a purely inflation subsidy environment, where I don't care about
the other miners success, of course I should publish. However, if my
goals are to find *more* blocks than the other miners for whatever
reason, maybe because transaction fees matter or I'm trying to get
nLockTime'd announce/commit fee sacrifices, it gets more complicated.

Now that you understand the assumptions made, you can attack the paper
in one of two ways:

1) Show it's wrong.

2) Show its assumptions make it irrelevant.

You've done neither.

-- 
'peter'[:-1]@petertodd.org
0006d61eb32f3643aa30c2f9647e4e758af84b03abc43f09959f


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] we can all relax now

2013-11-07 Thread Mike Hearn
Once the ASIC race calms down because everyone has one, has more or less
optimal power supplies, process improvements aren't easily reachable
anymore etc then I'd expect people to dissipate from the large pools
because eliminating their fees will become the next lowest hanging fruit to
squeeze out extra profit. There's no particular reason we need only a
handful of pools that control a major fraction of the hashpower.

If we end up with a few hundred pools or lots of miners on p2pool, then a
lot of these theoretical attacks become not very relevant (I don't think ID
sacrifices will be so common or large as to justify a pile of custom mining
code+strategies at any point ...)


On Thu, Nov 7, 2013 at 2:24 PM, Peter Todd p...@petertodd.org wrote:

 On Thu, Nov 07, 2013 at 02:56:56PM +1000, Gavin Andresen wrote:
   P.S: If any large pools want to try this stuff out, give me a shout.
 You
   have my PGP key - confidentiality assured.
  
 
  If I find out one of the large pools decides to run this 'experiment' on
  the main network, I will make it my mission to tell people to switch to a
  more responsible pool.

 I hope they listen.

 A few months ago ASICMiner could have made use of that attack if my
 memories of their peak hashing power were correct. They certainely could
 have used the selfish miner version, (we need better name for that)
 although development costs would eat into profits.

 GHash.IO, 22%, says they're a private Bitfury ASIC mining pool - dunno
 what they mean by that, but they're involved with CEX.IO who has
 physical control of a bunch of hashing power so I guess that means their
 model is like ASICMiners. They're a bit short of 30%, but maybe some
 behind-the-scenes deals would fix that, and/or lowering the barrier with
 reactive block publishing. (a better name)

  And if you think you can get away with driving up EVERYBODY's orphan rate
  without anybody noticing, you should think again.

 ...and remember, if you only do the attack a little bit, you still can
 earn more profit, and only drive up the orphan rate a little bit. So who
 knows, maybe the orphans are real, or maybe they're an attack? ASICMiner
 was involved with a bunch of orphans a while back...

 You know what this calls for? A witchhunt!

 BURN THE LARGE POOLS!

   P.P.S: If you're mining on a pool with more than, like, 1% hashing
   power, do the math on varience... Seriously, stop it and go mine on a
   smaller pool, or better yet, p2pool.
  
 
  That I agree with.

 Glad to hear.

 --
 'peter'[:-1]@petertodd.org
 0007bd936f19e33bc8b8f9bb1f4c013b863ef60a7f5a6a5d2112


 --
 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] we can all relax now

2013-11-06 Thread Frank F
The problem with academics is that they don't have to worry about the real
world. They get paid to publish things, not to be helpful to society.


On Tue, Nov 5, 2013 at 11:33 PM, kjj bitcoin-de...@jerviss.org wrote:

 One of the things that really gets me going is when someone devises a
 model, tests it against itself, and then pretends that they've learned
 something about the real world.

 Naturally, the Selfish Mining paper is exactly this sort of nonsense.
 Their model is one with no latency, and one where the attacker has total
 visibility across the network.  An iterated FSM is not a suitable
 simulation of the bitcoin system.  The bitcoin network does not have
 states, and to the extent that you can pretend that we do, you can't
 simulate transitions between them with static probabilities.

 The authors understand this deep down inside, even though they didn't
 work out the implications.  They handwave the issue by assuming a total
 sybil attack, and in true academic spirit, they don't realize that the
 condition necessary for the attack is far, far worse than the attack
 itself.

 Greg said he'd like to run some simulations, and I'm thinking about it
 too.  Unfortunately, he is busy all week, and I'm lazy (and also busy
 for most of tomorrow).

 If neither of us get to it first, I'm willing to pitch in 1 BTC as a
 bounty for building a general bitcoin network simulator framework. The
 simulator should be able to account for latency between nodes, and
 ideally within a node.  It needs to be able to simulate an attacker that
 owns varying fractions of the network, and make decisions based only on
 what the attacker actually knows.  It needs to be able to simulate this
 attack and should be generic enough to be easily modified for other
 crazy schemes.

 (Bounty offer is serious, but expires in one year [based on the earliest
 timestamp that my mail server puts on this email], and /may/ be subject
 to change if the price on any reputable exchange breaks 1000 USD per BTC
 in that period.)

 Basically, the lack of a decent network simulator is what allowed this
 paper to get press.  If the author had been able to see the importance
 of the stuff he was ignoring, we wouldn't be wasting so much time
 correcting him (and sadly the reporters that have no way to check his
 claims).

 https://bitcointalk.org/index.php?topic=324413.msg3495663#msg3495663




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




-- 
*MONEY IS OVER!*
IF YOU WANT IThttp://www.zeitgeistmovie.com/
=
The causes of my servitude can be traced to the tyranny of money.
-Serj Tankian
--
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] we can all relax now

2013-11-06 Thread Jeff Garzik
I will contribute 1 BTC to this bounty, under same terms and expiration.
--
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] we can all relax now

2013-11-06 Thread Christophe Biocca
I might try building this sometime soon. I think it may also serve an
educational purpose when trying to understand the whole network's behaviour.

What level of accuracy are we looking for though? Obviously we need to
fully emulate the steps of the network protocol, and we need to be able to
specify time taken for transmission/processing for each node. Do we care
about the actual contents of the messages (to be able to simulate double
spend attempts, invalid transactions and blocks, SPV node communication),
and their validation (actual signatures and proof of work)?

I imagine the latter is pretty useless, beyond specifying that the
signature/proof of work is valid/invalid.

If we could build up a set of experiments we'd like to run on it, it would
help clarify what's needed.

Off the top of my head:

- Peter Todd's miner strategy of sending blocks to only 51% of the
hashpower.
- Various network split conditions, and how aware of the split nodes would
be (and the effect of client variability).
- Testing the feasability of network race double spends, or Finney attacks.
- Various network partition scenarios.
- Tricking SPV nodes.
On Nov 6, 2013 6:37 AM, Jeff Garzik jgar...@bitpay.com wrote:

 I will contribute 1 BTC to this bounty, under same terms and expiration.


 --
 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] we can all relax now

2013-11-06 Thread Jouke Hofman
bounty++

On 06-11-13 06:33, kjj wrote:
 One of the things that really gets me going is when someone devises a 
 model, tests it against itself, and then pretends that they've learned 
 something about the real world.
 
 Naturally, the Selfish Mining paper is exactly this sort of nonsense.  
 Their model is one with no latency, and one where the attacker has total 
 visibility across the network.  An iterated FSM is not a suitable 
 simulation of the bitcoin system.  The bitcoin network does not have 
 states, and to the extent that you can pretend that we do, you can't 
 simulate transitions between them with static probabilities.
 
 The authors understand this deep down inside, even though they didn't 
 work out the implications.  They handwave the issue by assuming a total 
 sybil attack, and in true academic spirit, they don't realize that the 
 condition necessary for the attack is far, far worse than the attack itself.
 
 Greg said he'd like to run some simulations, and I'm thinking about it 
 too.  Unfortunately, he is busy all week, and I'm lazy (and also busy 
 for most of tomorrow).
 
 If neither of us get to it first, I'm willing to pitch in 1 BTC as a 
 bounty for building a general bitcoin network simulator framework. The 
 simulator should be able to account for latency between nodes, and 
 ideally within a node.  It needs to be able to simulate an attacker that 
 owns varying fractions of the network, and make decisions based only on 
 what the attacker actually knows.  It needs to be able to simulate this 
 attack and should be generic enough to be easily modified for other 
 crazy schemes.
 
 (Bounty offer is serious, but expires in one year [based on the earliest 
 timestamp that my mail server puts on this email], and /may/ be subject 
 to change if the price on any reputable exchange breaks 1000 USD per BTC 
 in that period.)
 
 Basically, the lack of a decent network simulator is what allowed this 
 paper to get press.  If the author had been able to see the importance 
 of the stuff he was ignoring, we wouldn't be wasting so much time 
 correcting him (and sadly the reporters that have no way to check his 
 claims).
 
 https://bitcointalk.org/index.php?topic=324413.msg3495663#msg3495663
 
 
 
 --
 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] we can all relax now

2013-11-06 Thread Peter Todd
On Wed, Nov 06, 2013 at 01:06:47PM -0500, Christophe Biocca wrote:
 I might try building this sometime soon. I think it may also serve an
 educational purpose when trying to understand the whole network's behaviour.
 
 What level of accuracy are we looking for though? Obviously we need to
 fully emulate the steps of the network protocol, and we need to be able to
 specify time taken for transmission/processing for each node. Do we care
 about the actual contents of the messages (to be able to simulate double
 spend attempts, invalid transactions and blocks, SPV node communication),
 and their validation (actual signatures and proof of work)?
 
 I imagine the latter is pretty useless, beyond specifying that the
 signature/proof of work is valid/invalid.
 
 If we could build up a set of experiments we'd like to run on it, it would
 help clarify what's needed.
 
 Off the top of my head:
 
 - Peter Todd's miner strategy of sending blocks to only 51% of the
 hashpower.

Speaking of, I hadn't gotten around to doing up the math behind that
strategy properly; turns out 51% I was overly optimistic and the actual
threshold is 29.3%

Suppose I find a block. I have Q hashing power, and the rest of the
network 1-Q. Should I tell the rest of the network, or withhold that
block and hope I find a second one?

Now in a purely inflation subsidy environment, where I don't care about
the other miners success, of course I should publish. However, if my
goals are to find *more* blocks than the other miners for whatever
reason, maybe because transaction fees matter or I'm trying to get
nLockTime'd announce/commit fee sacrifices, it gets more complicated.


There are three possible outcomes:

1) I find the next block, probability Q
2) They find the next block, probability 1-Q
2.1) I find the next block, probability Q, or (1-Q)*Q in total.
2.2) They find the next block, probability (1-Q)^2 in total.

Note how only in the last option do I lose. So how much hashing power do
I need before it is just as likely that the other miners will find two
blocks before I find either one block, or two blocks? Easy enough:

Q + (1-Q)*Q = (1-Q)^2 - Q^2 - Q + 1/2 - Q = (1 - \sqrt(2))/2

Q ~= 29.2%

So basically, if I'm trying to beat other miners, once I have 29.3% of
the hashing power I have no incentive to publish the blocks I mine!

But hang on, does it matter if I'm the one who actually has that hashing
power? What if I just make sure that only 29.3% of the hashing power
has that block? If my goal is to make sure that someone does useless
work, and/or they are working on a lower height block than me, then no,
I don't care, which means my original send blocks to 51% of the
hashing power analysis was actually wrong, and the strategy is even
more crazy: send blocks to 29.3% of the hashing power (!)


Lets suppose I know that I'm two blocks ahead:

1) I find the next block: Q(3:0)
2) They find the next block: (1-Q) (2:1)
2.1) I find the next block: (1-Q)*Q(3:1)
2.2) They find the next block: (1-Q)^2 (2:2)
2.2.1) I find the next block: (1-Q)^2 * Q  (3:2)
2.2.2) They find the next block: (1-Q)^3   (2:3)

At what hashing power should I release my blocks? So remember, I win
this round on outcomes 1, 2.1, 2.2.1 and they only win on 2.2.2:

Q + (1-Q)*Q + (1-Q)^2*Q = (1-Q)^3 - Q = 1 - 2^-3

Q ~= 20.6%

Interesting... so as I get further ahead, or to be exact the group of
miners who have a given block gets further ahead, I need less hashing
power for my incentives to be to *not* publish the block I just found.
Conversely this means I should try to make my blocks propagate to less
of the hashing power, by whatever means necessary.

Now remember, none of the above strategy requires me to have a special
low-latency network or anything fancy. I don't even have to have a lot
of hashing power - the strategy still works if I'm, say, a 5% pool. It
just means I don't have the incentives people thought I did to propagate
my blocks widely.

The other nasty thing about this, is suppose I'm a miner and recently
got a block from another miner: should I forward that block, or not
bother? Well, it depends: if I have no idea how much of the hashing
power has that block, I should forward the block. But again, if my goal
is to be most likely to get the next block, I should only forward in
such a way that 30% of the hashing power has the block.

This means that if I have some information about what % already has that
block, I have less incentive to forward! For instance, suppose that
every major miner has been publishing their node addresses in their
blocks - I'll have a pretty good idea of who probably has that most
recent block, so I can easily make a well-optimized decision not to
forward. Similarly because the 30% hashing power figure is the
*integral* of time * hashes/second, if miners are forwarding
near-target-headers, I might as well wait a few seconds and see if I see
any near-target-headers; if I do for 

Re: [Bitcoin-development] we can all relax now

2013-11-06 Thread Kyle Jerviss
You are ignoring the gambler's ruin. We do not operate on an infinite 
timeline.  If you find a big pool willing to try this, please give me 
enough advance warning to get my popcorn ready.


Peter Todd wrote:

On Wed, Nov 06, 2013 at 01:06:47PM -0500, Christophe Biocca wrote:

I might try building this sometime soon. I think it may also serve an
educational purpose when trying to understand the whole network's behaviour.

What level of accuracy are we looking for though? Obviously we need to
fully emulate the steps of the network protocol, and we need to be able to
specify time taken for transmission/processing for each node. Do we care
about the actual contents of the messages (to be able to simulate double
spend attempts, invalid transactions and blocks, SPV node communication),
and their validation (actual signatures and proof of work)?

I imagine the latter is pretty useless, beyond specifying that the
signature/proof of work is valid/invalid.

If we could build up a set of experiments we'd like to run on it, it would
help clarify what's needed.

Off the top of my head:

- Peter Todd's miner strategy of sending blocks to only 51% of the
hashpower.

Speaking of, I hadn't gotten around to doing up the math behind that
strategy properly; turns out 51% I was overly optimistic and the actual
threshold is 29.3%

Suppose I find a block. I have Q hashing power, and the rest of the
network 1-Q. Should I tell the rest of the network, or withhold that
block and hope I find a second one?

Now in a purely inflation subsidy environment, where I don't care about
the other miners success, of course I should publish. However, if my
goals are to find *more* blocks than the other miners for whatever
reason, maybe because transaction fees matter or I'm trying to get
nLockTime'd announce/commit fee sacrifices, it gets more complicated.


There are three possible outcomes:

1) I find the next block, probability Q
2) They find the next block, probability 1-Q
2.1) I find the next block, probability Q, or (1-Q)*Q in total.
2.2) They find the next block, probability (1-Q)^2 in total.

Note how only in the last option do I lose. So how much hashing power do
I need before it is just as likely that the other miners will find two
blocks before I find either one block, or two blocks? Easy enough:

Q + (1-Q)*Q = (1-Q)^2 - Q^2 - Q + 1/2 - Q = (1 - \sqrt(2))/2

Q ~= 29.2%

So basically, if I'm trying to beat other miners, once I have 29.3% of
the hashing power I have no incentive to publish the blocks I mine!

But hang on, does it matter if I'm the one who actually has that hashing
power? What if I just make sure that only 29.3% of the hashing power
has that block? If my goal is to make sure that someone does useless
work, and/or they are working on a lower height block than me, then no,
I don't care, which means my original send blocks to 51% of the
hashing power analysis was actually wrong, and the strategy is even
more crazy: send blocks to 29.3% of the hashing power (!)


Lets suppose I know that I'm two blocks ahead:

1) I find the next block: Q(3:0)
2) They find the next block: (1-Q) (2:1)
2.1) I find the next block: (1-Q)*Q(3:1)
2.2) They find the next block: (1-Q)^2 (2:2)
2.2.1) I find the next block: (1-Q)^2 * Q  (3:2)
2.2.2) They find the next block: (1-Q)^3   (2:3)

At what hashing power should I release my blocks? So remember, I win
this round on outcomes 1, 2.1, 2.2.1 and they only win on 2.2.2:

Q + (1-Q)*Q + (1-Q)^2*Q = (1-Q)^3 - Q = 1 - 2^-3

Q ~= 20.6%

Interesting... so as I get further ahead, or to be exact the group of
miners who have a given block gets further ahead, I need less hashing
power for my incentives to be to *not* publish the block I just found.
Conversely this means I should try to make my blocks propagate to less
of the hashing power, by whatever means necessary.

Now remember, none of the above strategy requires me to have a special
low-latency network or anything fancy. I don't even have to have a lot
of hashing power - the strategy still works if I'm, say, a 5% pool. It
just means I don't have the incentives people thought I did to propagate
my blocks widely.

The other nasty thing about this, is suppose I'm a miner and recently
got a block from another miner: should I forward that block, or not
bother? Well, it depends: if I have no idea how much of the hashing
power has that block, I should forward the block. But again, if my goal
is to be most likely to get the next block, I should only forward in
such a way that 30% of the hashing power has the block.

This means that if I have some information about what % already has that
block, I have less incentive to forward! For instance, suppose that
every major miner has been publishing their node addresses in their
blocks - I'll have a pretty good idea of who probably has that most
recent block, so I can easily make a well-optimized decision not to
forward. Similarly because the 30% hashing 

Re: [Bitcoin-development] we can all relax now

2013-11-06 Thread Peter Todd
On Wed, Nov 06, 2013 at 10:15:40PM -0600, Kyle Jerviss wrote:
 You are ignoring the gambler's ruin. We do not operate on an
 infinite timeline.  If you find a big pool willing to try this,
 please give me enough advance warning to get my popcorn ready.

Gamblers ruin has nothing to do with it.

At every point you want to evaluate the chance the other side will get
ahead, vs. cashing in by just publishing the blocks you have. (or some
of them) I didn't mention it in the analysis, but obviously you want to
keep track of how much the blocks you haven't published are worth to
you, and consider publishing some or all of your lead to the rest of the
network if you stand to lose more than you gain.

Right now it's a mostly theoretical attack because the inflation subsidy
is enormous and fees don't matter, but once fees do start to matter
things get a lot more complex. An extreme example is announce/commit
sacrifices to mining fees: if I'm at block n+1, the rest of the network
is at block n, and there's a 100BTC sacrifice at block n+2, I could
easily be in a situation where I have zero incentive to publish my block
to keep everyone else behind me, and just hope I find block n+2. If I
do, great! I'll immediately publish to lock-in my winnings and start
working on block n+3


Anyway, my covert suggestion that pools contact me was more to hopefully
strike fear into the people mining at a large pool and get them to
switch to a small one. :) If everyone mined solo or on p2pool none of
this stuff would matter much... but we can't force them too yet.

-- 
'peter'[:-1]@petertodd.org
0005713cac303bd2d529ebeffa82fff60be5307010a83933698d


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] we can all relax now

2013-11-06 Thread Kyle Jerviss
What I want is configurable 1/10/100 millisecond ticks, and accurate 
flow of information.


It doesn't seem necessary to really emulate the whole protocol, nor to 
be overly concerned with the content of messages, nor to simulate every 
little housekeeping step or network message.


I'm not looking for a bitcoin-network-in-a-bottle, I just want to see 
flows.  In the current situation, how often does a miner win if they 
hold their block until they see another one?  How does that change with 
various numbers of remote sensors?


Other applications in the future could very well involve transaction 
spread, double spends, network partitions, transaction replacement, etc.


If the simulation run in question involves blocks, I'd like realistic 
latencies for blocks.  If it is about transactions, the latencies should 
be realistic for transactions.


What is realistic for those?  That brings me to...

I'll kick in another 1 BTC for an instrumentation package for the 
reference client.  Same conditions as before.  A runtime option, 
disabled by default, that collects data for the simulator.  If this 
creates an uproar, I'll also accept a compile-time option. Support 
dumping to a file that can be uploaded to a parser as the bare minimum, 
and if you are feeling clever, add automatic uploads to a server 
specified in the conf file, or whatever.  All data should be anonymous, 
of course.  Local file should be in a format that humans can read (JSON, 
XML, CSV, etc) so that people can verify that the data is indeed anonymous.


I want stats on peers (number, turnover, latency, in/out, etc), stats on 
local operations (I/O stats, sigs per second when verifying a block, 
fraction of sig cache hits when validating, etc) and whatever else might 
be useful to a simulator.  Each parameter should collect min, max, mean, 
std. deviation, etc so that the simulator can provide realistic virtual 
nodes.


Also, I don't want anyone to think that they need to satisfy me 
personally to collect on either of these two bounties.  I will pay mine 
for a product that is generally along the lines I have laid out, if a 
couple of the core devs (Gavin, Greg, Jeff, sipa, Luke, etc) agree that 
your work is useful.



Christophe Biocca wrote:


I might try building this sometime soon. I think it may also serve an 
educational purpose when trying to understand the whole network's 
behaviour.


What level of accuracy are we looking for though? Obviously we need to 
fully emulate the steps of the network protocol, and we need to be 
able to specify time taken for transmission/processing for each node. 
Do we care about the actual contents of the messages (to be able to 
simulate double spend attempts, invalid transactions and blocks, SPV 
node communication), and their validation (actual signatures and proof 
of work)?


I imagine the latter is pretty useless, beyond specifying that the 
signature/proof of work is valid/invalid.


If we could build up a set of experiments we'd like to run on it, it 
would help clarify what's needed.


Off the top of my head:

- Peter Todd's miner strategy of sending blocks to only 51% of the 
hashpower.
- Various network split conditions, and how aware of the split nodes 
would be (and the effect of client variability).
- Testing the feasability of network race double spends, or Finney 
attacks.

- Various network partition scenarios.
- Tricking SPV nodes.

On Nov 6, 2013 6:37 AM, Jeff Garzik jgar...@bitpay.com 
mailto:jgar...@bitpay.com wrote:


I will contribute 1 BTC to this bounty, under same terms and
expiration.



--
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
mailto: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