Potential blockchain weakness during tie

DrHaribo

legendary

Activity: 2730

Merit: 1034

Needs more jiggawatts

Be careful or we'll orphan your blocks! Cheesy

By the way, if you have a tie with blocks A and B and

25% evil hashpower working on block C (prevblock A or B)
37.5% good hashpower working on block X (prevblock A)
37.5% good hashpower working on block Y (prevblock B)

then your 25% evil hashpower still has only 25% chance of creating the next block. This doesn't change because of a fork.

By choosing A or B as prevblock you do skew the odds for which past to keep as reality though (62.5% vs. 37.5%).

Erasing a lost bet at SatoshiDice by double spending would still only have 25% odds as the other 37.5% hashpower working on the same side of the fork are likely to include your lost bet in the new block.

zvs

legendary

Activity: 1680

Merit: 1000

https://web.archive.org/web/*/nogleg.com

http://blockchain.info/tx/290727df9b999ec9329b6017289c298342cf63fa3c39cf03318dfe52787ce482

http://blockchain.info/tx/7dcb47f5851199088e83e6f0a00387d357521f1a133540ce77c6216a955cf776

so the bitminter one is picked up by the blockchain spies 1 second after the btcguild one

ah, so prophetic

zvs

legendary

Activity: 1680

Merit: 1000

https://web.archive.org/web/*/nogleg.com

Quote from: RoboTeddy on March 06, 2013, 06:56:37 AM

Quote

And what are you thinking they will do with this one block that they create? To do anything destructive they would need to have the ability to regenerate old blocks that are already part of the blockchain or sustain continuous control over all new blocks. Generating a single block makes you a miner, not an attacker.

An attacker with 25% capacity might be able to notice a tie and then continually exploit it by causing subsequent ties. He could connect to every node so he's aware of exactly when someone else finds a block, and send out his own at that time (he has found one by now with p=0.5), to generate another tie. So, the probability of him generating n blocks in a row would be (1/2)^n; e.g. he'd have a 1/4 chance of controlling two blocks in a row.

How many blocks does an attacker need to generate in a row in order to cause trouble?

these two transactions are similar to what happens when there is a "tie" on blocks:

http://blockchain.info/tx/5ae820ef31cc5a3d1a34f7373d0b675cacc74786c160317d8648c24933f55874

First Seen 2013-03-08 11:04:13, relayed 1566

http://blockchain.info/tx/7a6a8ea2c4b2eed6b5ceee2d1b3783e293f00773a6d7f9cc5ac106b826efd49d

First Seen 2013-03-08 11:04:13, relayed 63

not really much relevance anyway. what is someone going to do with this evil tie breaker block? maybe if it was an evil tie breaker block followed up by another 5 or so.. anything w/ improper transactions would get turned down by 99% of nodes (if snoopy is running somewhere, it'd grab it)

but really the closest you'll get to ties are when some pool with a well connected bitcoind is a few seconds later than one without.. btcguild comes to mind, they've had at least two clear losers a few seconds and a few transactions earlier than some other pools, but got lucky by getting next block anyway.. p2pool would be another good example (depending on who solves it)

(oh, in case someone doesn't look at the transactions themselves instead of the node list:

#1

http://blockchain.info/tx-index/59188147/5ae820ef31cc5a3d1a34f7373d0b675cacc74786c160317d8648c24933f55874

#2

http://blockchain.info/tx-index/59188145/7a6a8ea2c4b2eed6b5ceee2d1b3783e293f00773a6d7f9cc5ac106b826efd49d

crafty.. i guess... the 145 one was actually sent first

.. oh, is it just me, or did satoshi dice really get owned there?

RoboTeddy

newbie

Activity: 3

Merit: 0

Quote

And what are you thinking they will do with this one block that they create? To do anything destructive they would need to have the ability to regenerate old blocks that are already part of the blockchain or sustain continuous control over all new blocks. Generating a single block makes you a miner, not an attacker.

An attacker with 25% capacity might be able to notice a tie and then continually exploit it by causing subsequent ties. He could connect to every node so he's aware of exactly when someone else finds a block, and send out his own at that time (he has found one by now with p=0.5), to generate another tie. So, the probability of him generating n blocks in a row would be (1/2)^n; e.g. he'd have a 1/4 chance of controlling two blocks in a row.

How many blocks does an attacker need to generate in a row in order to cause trouble?

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: RoboTeddy on March 06, 2013, 04:28:18 AM

From Satoshi's paper (http://bitcoin.org/bitcoin.pdf):

Quote

If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first. In that case, they work on the first one they received, but save the other branch in case it becomes longer. The tie will be broken when the next proofof-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.

In the event of a perfect tie, 50% of the honest nodes would be working on one branch, and 50% on the other. That means an attacker with only 25% of the power would have a 50% chance of choosing the next block. The false block would break the tie, and all the honest nodes would now work away at the new longest chain (the one with the false block). An attacker might even be able to detect ties, and thus know when to try to attack.

The frequency ties, and how evenly computational power is split during a tie, probably depend on the specifics of the gossip protocol. I don't know how often they happen in practice.

I'm a bitcoin newb, so this might not actually be a weakness -- if it's not, I'm interested in knowing what I don't understand!

And what are you thinking they will do with this one block that they create? To do anything destructive they would need to have the ability to regenerate old blocks that are already part of the blockchain or sustain continuous control over all new blocks. Generating a single block makes you a miner, not an attacker.

RoboTeddy

newbie

Activity: 3

Merit: 0

From Satoshi's paper (http://bitcoin.org/bitcoin.pdf):

Quote

If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first. In that case, they work on the first one they received, but save the other branch in case it becomes longer. The tie will be broken when the next proofof-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.

In the event of a perfect tie, 50% of the honest nodes would be working on one branch, and 50% on the other. That means an attacker with only 25% of the power would have a 50% chance of choosing the next block. The false block would break the tie, and all the honest nodes would now work away at the new longest chain (the one with the false block). An attacker might even be able to detect ties, and thus know when to try to attack.

The frequency ties, and how evenly computational power is split during a tie, probably depend on the specifics of the gossip protocol. I don't know how often they happen in practice.

I'm a bitcoin newb, so this might not actually be a weakness -- if it's not, I'm interested in knowing what I don't understand!

Topic: Potential blockchain weakness during tie (Read 662 times)