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

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

[Ittay]

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

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.

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

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

[Peter Todd]

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

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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Peter Todd]

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

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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Ittay]

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

On Tue, Nov 5, 2013 at 12:14 PM, Peter Todd <pete@petertodd.org> wrote:

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


The attack can be easily hidden. And be sure that before today, today,
and after today, very smart people are at their computer planning attacks
on Bitcoin. Exploits must be published and fixed FAST.

Nevertheless, I agree  that, as you say, we must not rush it. Look at the
BIP, find if we missed anything, and let's discuss it.


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

Not really. Please see the discussion section in our paper.


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

There is no flaw. You were just reiterating that the solution does not give
us the 51% percent security you thought you had before. We showed that
we're not getting this back, I'm afraid.

Best,
Ittay

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

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

[Mike Hearn]

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

On Tue, Nov 5, 2013 at 6:43 PM, Ittay <ittay.eyal@cornell.edu> wrote:

> The attack can be easily hidden. And be sure that before today, today,
> and after today, very smart people are at their computer planning attacks
> on Bitcoin. Exploits must be published and fixed FAST.
>

I think it would be helpful if you actually implemented and pulled off this
attack, by becoming the dominant miner capable of reversing spends at will.
Then we'd know how quickly it can be done.

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

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

[Alessandro Parisi]

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

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

WebSite: http://www.startithub.com
Per rimanere aggiornato in merito a Startup, Innovazione e Normativa di
settore, sottoscrivi la nostra newsletter:
http://www.startithub.com/blog/sottoscrivi-newsletter/


2013/11/5 Mike Hearn <mike@plan99.net>

> On Tue, Nov 5, 2013 at 6:43 PM, Ittay <ittay.eyal@cornell.edu> wrote:
>
>> The attack can be easily hidden. And be sure that before today, today,
>> and after today, very smart people are at their computer planning attacks
>> on Bitcoin. Exploits must be published and fixed FAST.
>>
>
> I think it would be helpful if you actually implemented and pulled off
> this attack, by becoming the dominant miner capable of reversing spends at
> will. Then we'd know how quickly it can be done.
>
>
>
>
>
> ------------------------------------------------------------------------------
> November Webinars for C, C++, Fortran Developers
> Accelerate application performance with scalable programming models.
> Explore
> techniques for threading, error checking, porting, and tuning. Get the most
> from the latest Intel processors and coprocessors. See abstracts and
> register
> http://pubads.g.doubleclick.net/gampad/clk?id=60136231&iu=/4140/ostg.clktrk
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

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

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

[Jeff Garzik]

On Tue, Nov 5, 2013 at 1:07 PM, Alessandro Parisi <startithub@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/

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

[Alessandro Parisi]

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

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 <jgarzik@bitpay.com>

> On Tue, Nov 5, 2013 at 1:07 PM, Alessandro Parisi <startithub@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/
>

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

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

[Jeff Garzik]

On Tue, Nov 5, 2013 at 1:55 PM, Alessandro Parisi <startithub@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/

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

[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\fsh 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 <startithub@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.
>

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

[Peter Todd]

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

On Tue, Nov 05, 2013 at 12:43:15PM -0500, Ittay wrote:
> On Tue, Nov 5, 2013 at 12:14 PM, Peter Todd <pete@petertodd.org> wrote:
> 
> > 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:
> >
> > 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
> 
> 
> The attack can be easily hidden. And be sure that before today, today,
> and after today, very smart people are at their computer planning attacks
> on Bitcoin. Exploits must be published and fixed FAST.

Not this exploit.

Here's a perfectly plausible worst-case scenario, that could be
happening right now: RAND High Frequency Trading Corp (a subsidiary of
General Evil) has a globe-spanning low-latency network of fiber,
line-of-sight microwave, and some experimental line-of-site neutrino
links criss-crossing the globe. They can get data to and from any point
on this planet faster than anyone else. Of course, in addition to their
spectacular network they have an immense amount of computing power, as
well as exotic overclocked liquid nitrogen bathed CPU's that run at
clockspeeds double what commercial hardware can do; in short, they have
access to scalar performance no-one else has. Of course, they like to
keep a healthy reserve so, 99% of all this fancy gear is constantly
idle. Whatever, they can afford it.

RAND just hired a bunch of fresh MIT graduates, the best of the best.
Problem is the best of the best tends to make not so best mistakes, so
RAND figures a Training Exercise is in order. Fortunately for them the NSA (a
subsidiary of General Evil) slipped a rootkit into my keyboard a week or
so ago - probably that time when I woke up in that farmers field with a
*splitting* headache - and are reading what I'm typing right now.

I go on to explain how an excellent training exercise for these fresh
MIT graduates would be to implement this nifty attack some Cornell
researchers came up with. It's really simple, elegant even, but to do it
best what you really want is the kind of low-latency network a
high-frequency-trading corporation would have. I then point out how a
good training exercise ideally is done in a scenario where there is
genuine risk and reward, but where the worst-case consequences are
manageable - new hires to tend to screw up. (I then go on to explain my
analog electronics background, and squeeze in some forced anecdote about
how I blew up something worth a lot of money owned by my employers at
some point in the distant past)

Unfortunately for the operators of BTC Guild, one of these new MIT grads
happens to have a: passed General Evil's psych screening with flying
colors, and b: have spent too much time around the MIT Kidnappng Club.
He decides it'd be easier to just kidnap the guy running BTC Guild than
fill out the paperwork to borrow RAND's FPGA cluster, so he does.

As expected the attack runs smoothly: with 30% of the hashing power,
neutrino burst generator/encoders's rigged around the globe to fire the
moment another pool gets a block, and the odd DoS attack for fun, they
quickly make a mockery of the Bitcoin network, reducing every other
miners profitability to zero in minutes. The other miners don't have a
hope: they're blocks have to travel the long way, along the surface of
the earth, while RAND's blocks shave off important milliseconds by
taking the direct route.


Of course, this doesn't go unnoticed, er, eventualy: 12 hours later the
operators of GHash.IO, Eligius, slush, Bitminter, Eclipse and ASICMiner
open their groggy eyes and mutter something about how that simulcast
Tuesday party really shouldn't have had an open bar... or so much coke.

They don't even notice that the team from BTC Guild has vanished, but
they do notice a YouTube video of Gavin right on bitcoin.org doing his
best Spock impression, er, I mean appealing for calm and promising that
Top Men are working on the issue of empty blocks as we speak. Meanwhile
CNN's top headline reads "IS THIS THE END OF BITCOIN?!?!"

It takes another hour for the Aspirin's to finally kick in, but
eventually get all get on IRC and start trying to resolve the issue -
seems that whenever any of them produce a block, somehow by incredible
coincidence someone else finds another block first. After a few rounds
of this they're getting suspicious. (if they weren't all so hung-over
they might have also found suspicious the fact that whenever they found
a block they saw a sudden blue flash - Cherenkov radiation emitted when
those neutrino's interacted with the vitreous humour in their eyeballs)

It's quickly realized that "somehow" BTC Guild isn't affected...
GHash.IO and Eligius, 22% and 13% of the hashing power respectively,
decide to try a little experiment: they peer to each other and only each
other through an encrypted tunnel and... hey, no more lucky blocks!
slush, 7% of the hashing power is invited to the peering group next,
followed by Bitminter, 6%, and Eclipse, 2%, and finally ASICMiner, 1%,
for a grand total of... 51% of the hashing power!

Of course, just creating blocks isn't useful for users, they need to be
distributed too, so someone quickly writes up a "one-way firewall" patch
that allows the group's blocks to propagate to the rest of the network.
Blocks created by anyone else are ignored.

It takes a few more hours, but eventually the attacker seems to run out
of blocks, and transaction processing returns to normal, albeit a little
slow. (20 min block average) Of course, soon there's a 3,000 post thread
on bitcointalk complaining about the "centralized pool cartel", but
somehow life goes on.

The next day Gavin goes on CNN, and gives a lovely interview about how
the past two days events show how the strength of the Bitcoin network is
in the community. For balance they interview this annoying "Peter Todd"
guy from "Keep Bitcoin Free!" who blathers on about how relying on
altruism or something will doom the Bitcoin network in the long run.
After the interview Gavin respectfully points out that maybe next time
they find a so called "developer" with a ratio of bitcointalk posts to
actual lines of code in the Bitcoin git repository better than one
hundred to one. The producer just wishes that "Mike Hearn" guy was
available; at least he's got a sense of fashion, sheesh!


Anyway, I'm out of space for my little story, but yeah, the ending
involves a group of now-rich pool operators who decide to start a large
financial services and data networking company, oh, and time-travel...


> Nevertheless, I agree  that, as you say, we must not rush it. Look at the
> BIP, find if we missed anything, and let's discuss it.

Indeed.

Quite seriously, your attack is a serious long-term risk, but in the
short term the social dynamics of Bitcoin are such that it's just not a
show-stopping risk. At worst some miners will lose a bunch of money -
that's something that's happened before with the March chain fork, and
sure enough Bitcoin survived just fine.

> > 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.
> >
> 
> Not really. Please see the discussion section in our paper.

You can hide *who* is the attacker - you can't hide the fact that an
attack is happening if done on a meaningful scale.

> > That Gregory Maxwell so quickly identified a flaw in this proposed
> > solution suggests we should proceed carefully.
> >
> 
> There is no flaw. You were just reiterating that the solution does not give
> us the 51% percent security you thought you had before. We showed that
> we're not getting this back, I'm afraid.

That's not what we're concerned about - what we're concerned about is
that your BIP doesn't discuss the issue, and you didn't seem to be aware
of it. That suggests that the analysis is incomplete. There's no
pressing need to rush changes, as explained above by example, so we're
best off understanding the issue thoroughly first.

There's a whole spectrum of potential solutions that haven't been
discussed - I myself have two approaches I'm working on that may solve
this problem in ways you haven't (publicly) considered. I'm sure there
are many others out there.

-- 
'peter'[:-1]@petertodd.org
00000000000000005144f6a7109b9f8543880a0a5f85a054ec53966bc2daa24c

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Ittay]

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

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 <pete@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
> 0000000000000005e25ca9b9fe62bdd6e8a2b4527ad61753dd2113c268bec707
>

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

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

[Patrick]

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

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 <pete@petertodd.org
> <mailto:pete@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 <http://petertodd.org>
>     0000000000000005e25ca9b9fe62bdd6e8a2b4527ad61753dd2113c268bec707
>
>
>
>
> ------------------------------------------------------------------------------
> November Webinars for C, C++, Fortran Developers
> Accelerate application performance with scalable programming models. Explore
> techniques for threading, error checking, porting, and tuning. Get the most 
> from the latest Intel processors and coprocessors. See abstracts and register
> http://pubads.g.doubleclick.net/gampad/clk?id=60136231&iu=/4140/ostg.clktrk
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


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

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

[Alessandro Parisi]

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

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

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

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

[Jeremy Spilman]

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

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

[-- Attachment #2.1: Type: text/html, Size: 3441 bytes --]

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

[Ittay]

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

On Tue, Nov 5, 2013 at 1:57 PM, Jeremy Spilman <jeremy@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

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

[Bitcoin-development] comments on selfish-mining model (Re: BIP proposal - patch to raise selfish mining threshold.)

[Adam Back]

(Talking about the paper, not the BIP).  With regard to racing the other
winner which catches up when private pool length=1:

i) the model does not appear to take into account that when another pool
goes on to mine a block, and the attacker publishes their selfishly-withheld
block, the selfish pool will not be able to change the existing winners
mind.  This is not insignificant as the pools have 30%, 20%, 15%, 7% etc. 

ii) The miners already have an incentive, as other big bitcoin processors,
to maintain fast, secure and redundant links to other significant miners. 

The attacker is giving up a large proportion of their winnings from the
times that they win at all.  Say the attacker IS the 30% pool, when he wins
and waits for someone else to win, > 80% of the network is pool mined, so
there is a good chance that the other winner individually represents a
non-negligible proportion of the network or a sufficiently well connected
portion of the network that the attacker will be unable to race them to
publication with a useful proportion of the network.

iii) Also broadcast is not instantaneous, lets say network propagation takes
10 seconds; a big proportion of the time, the actual mining times will be
more than 5 seconds apart so that by the time the selfish miner learns of
the block, much of the network will already have accepted it block as first.

iv) Even within the 10 seconds ambiguity period, the more powerful miner
will tend statistically to come first, and so reach a bigger portion of the
network, as well as having a stronger incentive to maintain links as in ii).

These four factors erode the achievable \gamma parameter.  I suspect it
unlikely \gamma>0.5 would be achievable, putting the profitable threshold
\alpha in 25% - 33%.  (And assuming whatever techniques to reduce latency
are used by the selfish pools can be used by other pools.)


Your main result that even with \gamma=0 (if you dont win any races) that
you still win once the selfish pool reaches 33% is an important new
indication, which needs further consideration.  (And you could expect to win
some percentage \gamma>0 even with the factors I mention, and full
implementation of the same latency reduction techniques in all moderate
sized miners, selfish and normal).

It is also not clear what will happen if multiple selfish miners compete
with each other.  A selfish miner cooperating as a peer to increase
percentage runs risk of mutual sabotage - he has to announce his private
block to his co-conspirator, and the co-conspirator may publish, or collude
with another non-selfish miner.  

Your supposition is there is a profit motive to collude.  However there are
other profit motives in bitcoin that are not exercised - for example there
were for sometime 2 pools that had excess of 50% power, and yet this was not
abused for double spending.  Of course increasing profit by a new mining
strategy is not theft as double spending which has a clear loser.  Miners
even exercised restraint and volutarily avoided growing over 50%.


As others have I think said by now analysis is welcome.  It seems that Peter
Todd may have observed the same or something similar wrt miner incentives
some months ago, though it wasnt as widely read nor formally verified.  

It might be useful to release the source for your simulator if that is open
to you.


In my opinion a constructive direction for reducing centralization risks is
to try to reduce the use of and motivation for pools.  Even at <51% per pool
there is (probabilistic) miner risk in double-spends.  And there is risk
that the large miners evolve to become a defacto policy enforcement point
for policies not aligned with user interests, or with fungibility of bitcoin
which itself presents another kind of risk (defacto reduced fungibility
should this arise would also be bad for bitcoin).

Also without even having mining power, there is scope to network hacking (eg
of routers in front of miners) to influence the mining profit, and even
double spend.  As I mentioned large miners have an incentive to maintain
secure redudant links (probably some links using Tor for blocks) as a
counter-measure. 

Adam

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.