From the forums: one-confirmation attack

vector76 on the Forums posted this interesting variation on a 'Finney attack' :
  https://bitcointalk.org/index.php?topic=36788.msg463391#msg463391

"Let's say I observe the timing of when nodes are broadcasting transactions and how they are propagating through the network. By watching for which nodes are earliest to broadcast transactions from my target, I manage to establish a direct connection to my target.

I use a similar method of watching block broadcasts to establish connections to most of the mining pools.

Now I create a transaction making a valid, large deposit into my target. I do not broadcast this transaction but I add it to a block that I am attempting to mine. I mine solo, just like normal, except that I have an extra non-broadcasted tx that I am including.

Eventually, I succeed in creating a valid block. I do not broadcast it immediately, but instead I wait until someone else mines a block, and when that happens, I immediately broadcast my block to my target. If my target sees my block before the other block, they will accept it, and my transaction will have one confirmation. The block chain has forked, and my target (and possibly other nodes, if my target relays quickly enough) will believe that my block is the correct one, while other nodes will believe that the other fork is the correct one.

I immediately request a withdrawal, and my target generates a transaction sending the large amount of coins to an address I control. I also double-spend some of the inputs, sending the coins to myself. The part of the network that did not receive my block first (which hopefully is most of the miners) will accept this as valid and work to include it in the next block.

If my block eventually "wins" because enough miners saw my block first and added onto it first, then I have just made a deposit and withdrawal, and I lose nothing.

If my block eventually "loses", then the deposit is invalidated. If the deposit tx was not one of the inputs to the withdrawal transaction, then the withdrawal is still valid."

-------------------------------

The lessons are "don't accept 1-confirmation transactions" and "try to be well-connected."

But maybe the deeper lesson is "don't trust information you get from only one peer." Or maybe "watch for peers that are trying to fool you."

On Thu, 2011-08-18 at 10:00 -0400, Gavin Andresen wrote:

> The lessons are "don't accept 1-confirmation transactions" and  "try
> to be well-connected."
>
> But maybe the deeper lesson is "don't trust information you get from
> only one peer." Or maybe "watch for peers that are trying to fool
> you."

This particular attack seems quite dependant on the target not using the deposit Tx as input. I believe this whole class of attacks become ineffective if each account has it's own separate wallet.

Also, receiving a block with a transaction that hasn't been broadcast to the network is in itself quite suspect. Are there cases where that happens legitimately? Perhaps in such a case, don't treat the block it came in as a confirmation at all. Instead, start counting from the next one.

- Joel

> Also, receiving a block with a transaction that hasn't been broadcast to
> the network is in itself quite suspect. Are there cases where that
> happens legitimately?

There's no way to obtain the memory pools of your peers today, so if you're newly started up it can happen that you get blocks with unseen transactions.

For vectors variant, I wonder if it'd be safe to report the number of confirmations differently for the duration of a chain split. If you have a block but a majority of peers relayed a block that split the chain, subtract 1 from each confirmation reported via RPC.

> For vectors variant, I wonder if it'd be safe to report the number of
> confirmations differently for the duration of a chain split. If you
> have a block but a majority of peers relayed a block that split the
> chain, subtract 1 from each confirmation reported via RPC.

Or maybe report them as 'suspicious.' Changing the meaning of 'confirmations' is likely to break code (e.g. code like block = current_blockchain[blockcount-tx.confirmations] ... would give the wrong block).

A floating-point 0.0-1.0 'confidence' measure might be a good idea to go along with the integer confirmations. I can think of all sorts of ways of gauging the reliability of transactions or blocks (did it come from a trusted peer-- assuming we eventually have trusted peers. Does it have a lot of confirmations? Are there no active block chain forks? Have we been getting new blocks at the rate we expect? etc etc etc)

We could start with an as simple-as-possible "confidence == 0 if confirmations < 2, otherwise confidence = function(#confirmations)" and improve it from there.

On Thu, Aug 18, 2011 at 12:16 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:

> We could start with an as simple-as-possible "confidence == 0 if
> confirmations < 2, otherwise confidence = function(#confirmations)"
> and improve it from there.

At the same time, if this causes people to wait less than the 6 blocks that the software currently waits for before leaving unconfirmed status then that would be sad.

Simply waiting a number of blocks is an excellent metric and provides robustness against almost all attack patterns in a way that various one-off-heuristics can not as it equates to _real difficulty_ (and real expense (hashing computation, loss of income on the orphaned blocks)) in a way that can't be faked.

A few weeks back when there was some rumor going around that mybitcoin lost coin based on some kind of one confirmation attack I described on IRC a similar attack pattern which had a useful improvement:

* The attacker runs many widely distributed sybil nodes (e.g. using botnet drones as simple tcp proxies to appear at many addresses). He takes advantage of the fact the bitcoin won't connect to /16s that have already connected to it to further isolate nodes.

* By creating normal looking probe transactions which his own nodes won't forward he detects network partitions which he is able to create. He searches for a cut which causes there to be at least two partitions which contain significant mining power.

* He creates two accounts at MoronBank. He doesn't even bother identifying MoronBank's node. MoronBank will be in one partition or another. He makes deposits in both partitions, and conflicting transactions in the opposite partitions, while carefully filtering out these transactions from crossing the boundary.

(Notably, the network doesn't appear partitioned to everyone else now because he's still forwarding blocks and transactions unrelated to his attack— it only becomes visible once some of his evil transactions are mined)

* After the funds show up in MoronBank he withdraws and drops the partitioning.

Only if he has difficulty getting MoronBank into the smaller partition does he need to bother locating it and attacking it directly.

The bad thing about this attack is that it doesn't require the attacker to have any hash power at all: he captures miners as unwilling (or willing but plausibly deniable) participants. The lost income from orphaned blocks is externalized to the victimized miners (and since most pools don't pay orphaned blocks out of pocket a pool operator would be inclined to help out).

The good thing about it is that it's killed dead by nodes adding in a few manually configured peerings, they don't even really need to be trusted: You just need to trust that they don't all go to a single bad-guy conspiracy. At a minimum all major miners should be fully meshed.

Unfortunately, We don't currently have software for this as addnode doesn't worry about keeping the links up... and the major pools also don't seem to be interested in participating.

> The part of the network that did not receive my block first (which
> hopefully is most of the miners) will accept this as valid and work to
> include it in the next block.

To make this more difficult, nodes that receive new transactions via blocks should relay the new transactions as if they had received them normally. Then the double-spend transaction will be rejected by most of the network because the other version is already widely-known.

On Thu, Aug 18, 2011 at 12:47 PM, theymos <theymos@mm•st> wrote:

> To make this more difficult, nodes that receive new transactions via
> blocks should relay the new transactions as if they had received them
> normally. Then the double-spend transaction will be rejected by most of
> the network because the other version is already widely-known.

Not that helpful. In that attack pattern the attacker can release the block and the conflicting transaction at the same time (to different nodes, of course). They can also inject the conflicting transaction into many places in the network at once.

Gregory said: "...if this causes people to wait less than the 6 blocks that the software currently waits for before leaving unconfirmed status then that would be sad."

People are already considering transactions 'confirmed enough' at less than six blocks. I'm guilty, too-- 3 is/was the magic number for ClearCoin.

And people are already experimenting with ways of safely accepting 0-confirmation transactions, like InstaWallet's "green" payments (sent from a trusted-not-to-double-spend address).

Since there is definitely market demand for "as fast as possible" confirmation, I'm thinking adding a placeholder to the RPC interface might be a good idea. Although after thinking about it some more, maybe a signed integer "trust" rating for blocks/transactions would be a better way of doing it...

RE: miners connecting themselves together in a semi-trusted "bitcoin backbone" : agreed.

Matt submitted a patch to connect and stay-connected to a set of nodes, but I complained about the implementation. Seems to me the networking code needs an overhaul, to implement a priority queue of potential peers (trusted peers would be sorted to near the top of the queue, peers you think are badly-behaved would be sorted to the bottom, with lots of randomness so not everybody on the network is trying to connect to the same set of peers). With peer rotation to mitigate manipulate-time and other Sybil attacks.