2

There is an almost trivial double-spending attack against Bitcoin if an attacker has a MITM (man-in-the-middle) attack against a victim: the attacker prevents all blocks from being seen, and replaces them with their own. The argument against this I've read online is that "it will take an extremely long time for the attacker to generate their own blocks, so the victim will notice there's something wrong".

But what about the following attack?

  1. Attacker "Mallory" has a MITM attack against victim "Alice". Say it takes Mallory T minutes to generate a block, where T >> 10
  2. When the N-th block is generated on the network, Mallory waits C*N minutes before forwarding it to Alice (here C is a small arbitrary constant, and N=1 is the first block generated on the network after the MITM attack begins). In other words, only a small amount of time is added to each block, but Alice's blockchain gets further and further behind the "real" blockchain as time goes on.
  3. Let M=6*T/C. After M blocks, Alice's blockchain will be C*M = 6*T minutes behind the real blockchain. Mallory starts generating blocks against the real blockchain's head at this point. She inserts a malicious fake transaction into the first block she finds, and fills the rest with transactions from the real blockchain.
  4. By the time Alice catches up to that point of the blockchain, Mallory will have generated 6 blocks, enough to make Alice believe the malicious transaction has been confirmed.

In other words, Mallory builds up time for herself to generate some blocks by adding C extra minutes between each block. Once she's accumulated enough time, she then "spends" it to generate some fake blocks.

Alice still sees a block ~every 10+C minutes, so as long as C is small she never notices anything is wrong. She also sees her own transactions eventually going through, just with an extra delay of N*C minutes.

Does Bitcoin somehow protect against this? Or is this a legitimate double-spending attack?

  • Assume Alice runs a full node, the full node would expect to receive transactions. If suddenly no more tx come in, this is a reason of concern, especially since 6 blocks. On each new block the client would want to verify the tx in a block ... should all 6 blocks be "0 tx blocks", and how comes the fake tx into the block? – pebwindkraft Feb 16 '18 at 16:35
  • @pebwindkraft: Where does it say no more TX would come in? Mallory can include whatever TX she'd like in the blocks, including the TX from the "real" next 6 blocks. – BlueRaja - Danny Pflughoeft Feb 16 '18 at 16:46
  • Yup, correct, I put this as “statement”. If the blocks have valid tx, then the full node would verify each tx. And probably recognize nothing. Then comes faulty tx: Node would check previous tx ID, output script and the signature (amongst others). So if Mallory injects a faulty tx in a block, I am trying to think, what type it should be? What should trick Alice? – pebwindkraft Feb 16 '18 at 17:47
2
+50

Is this man-in-the-middle double-spending attack against Bitcoin viable?

To complete a double spending attack on Bitcoin as described, you need to be able to present an alternate block that is otherwise valid and with valid proof of work.

To create such a block in a 10-minute average requires as much mining power as exists in all the rest of the network (a 51% attack).

Yes, Mallory can delay Alice from receiving a new block but, Mallory must also successfully present Alice with a valid alternate block. There is one significant failing:

  1. The proposed attack suggests insertion of a malicious fake transaction (temporary may be a better word) into a maliciously crafted block, a temporary transaction we suppose is Mallory paying to Alice while on the real blockchain Mallory is paying to herself.
  2. Mallory puts Alice on drip-feed only giving new blocks slowly so that the real blockchain is ahead.
  3. After Mallory lets the real blockchain get far enough ahead Mallory wants to build a fake block on top of a real block {blockheight-6}
  4. Mallory requires as much mining power as exists in all of the rest of the mining network in order to solve the malicious block in a 10-minute average. Note that even in that case since it is an average it could take as long as 20-minutes. So, with approximately 25,681,575,019 GH/s[1] of mining power the attack can probably be carried out unnoticed. With half as much mining power as exists in all of the rest of the network Mallory would be able to solve a new block in a 20-minute average or, about 40-minutes max.

The problem in completing a 51% attack is revealed when it is understood that one modest Bitcoin miner is probably capable of just 13,500 GH/s.

Setting aside plausibility, the transaction would need to be of exceptionally large value to be financially viable.

EDIT: On the point that with 1% of the mining power a block can be generated in an average of 16 hours (max 32 hours) this is in theory not totally implausible, however, it should be noted that would still require currently ~19023 Antminer S9's. Also, if you test drip feeding the node in a laboratory environment to get 16~32 hours behind to see how the node behaves I doubt that Alice would not notice, even more so if also waiting for 6 confirmations. If Mallory also had access to Alice's computer to replace the software with a modified version then the attack becomes more realistic. Note that Mallory will still need to make private arrangements to distribute work amongst her miners i.e. a private mining pool.

rel:
[1] https://blockchain.info/stats

  • Your point #4 is a complete non-sequitur. The entire point of the attack is that Mallory does not need to generate a block in 10 minutes. She could have an arbitrarily small amount of hashing power and the attack would still work (with eg. 1% of the hashing power, she could generate blocks in 16 hours). – BlueRaja - Danny Pflughoeft Mar 12 '18 at 15:25
  • @BlueRaja-DannyPflughoeft I have edited my answer in case some large attacker wished to purchase ~20,000 Antminer S9's. – Willtech Mar 12 '18 at 20:35
  • Er, well congratulations on the bounty, despite the answer being completely incorrect. I guess I'll ask on the cryptography stackexchange instead. – BlueRaja - Danny Pflughoeft Mar 20 '18 at 12:49
1

Somehow there is some illogical connection between "an almost trivial attack", double spends and creating blocks. Double spends are tx based, and would mean, that "my" transaction to a bitcoin user is spent again to a third bitcoin user. There is no example in the above statement, where this double spend comes into the game. Also one cannot see, who is tricked by the double spend scenario with this "trivial mtm attack".

Instead OP is talking about creating blocks, aka mining. MCCSS already replied. And if a miner has only one active connection (through an mtm), then you can talk about triviality of the attack concept, but not against bitcoin. A single miner might have an issue, but not bitcoin.

I might update the answer, if more detail is provided.

In summary: there is no trivial attack against bitcoin, and no visible double spend in the OP recognizable. Bitcoin remains well protected, if a single person is mining through a mtm.

  • If a single user can be tricked into believing they were given money that was actually spent elsewhere, that is an issue with Bitcoin. In fact that is literally the definition of a double-spend attack. In both the trivial attack and the attack presented, the attacker is the one mining; the victim is only on the receiving end of a (fake) transaction. – BlueRaja - Danny Pflughoeft Feb 19 '18 at 19:28
  • I see, a theoretical approach: an mtm is done against a target, and the isolated host has a problem to recognize reality. This shall be the bitcoin problem... A full node would need to be tricked with correct hash values of previous tx IDs, signatures and pubkey hashes. If you send a wrong value of bitcoin to the isolated user, you would need to re-create a tx based on previous tx, and recalculate the hash values and create the block nonce and all following nonces. How possible is this? - MCCCS showed the timing problem with it. But maybe you have a different scenario, that you could show? – pebwindkraft Feb 19 '18 at 22:29
  • Yes, as I mentioned in the question, the "trivial" MITM attack relies on being able to generate blocks, which takes time T >> 10 minutes (>> means "much greater than"). Alice will notice that the time between blocks has gone up drastically and will realize there is a problem. The attack in my question gets around that by delaying every block by a small amount for several days, to build up time to generate a block. – BlueRaja - Danny Pflughoeft Feb 20 '18 at 3:06
  • @BlueRaja-DannyPflughoeft The 'trick' block generated must be valid and, cannot begin to be mined before the block that it is building on since it contains the hash of the previous block. The attack is not viable. – Willtech Mar 11 '18 at 21:44
  • @Willtech: Yes that's correct, Mallory's blocks are valid and based on a previous block from the real blockchain. But what about that implies the attack is "not viable"? The "trick" is that Alice will not see that parent block for a while, because she is behind the real blockchain. – BlueRaja - Danny Pflughoeft Mar 12 '18 at 3:11
1

It turns out this is a valid attack, and it's even mentioned on the wiki. It's called Timejacking.

0

plus an additional 5 confirmation blocks

Each block contains the hash of the previous block, so Mallory can't remove one of the blocks behind those and put his without invalidating them.

However, as Mallory sends her blocks with delay, Alice will think "Blocks come with delays longer than 10 minutes. The difficulty will decrease." Mallory will be able to create more blocks after M blocks with lower difficulty. Nonetheless, for this method to work, N needs to be very large or C needs to be somewhat large.

The most important point here is

Miners need to be connected to hundreds of nodes, to be able to receive the latest block as fast as they can. You can't MitM all of them.

Less importantly

Even if you MitM the connections between Alice and all the nodes, miners use some kind of software to steal hashes and other block headers from other pools. They'd see that those pools' block heights will be higher than Alice's and Alice will notice it.

  • "Mallory can't remove one of the blocks behind those and put his without invalidating them" - She doesn't need to. The trick is that the next M blocks exist, but Alice hasn't seen them yet, so Mallory can send them to Alice in the meantime while Mallory computes the final 6 blocks. – BlueRaja - Danny Pflughoeft Feb 16 '18 at 15:54
  • delaying blocks has no sense. blocks are timestamped. – amaclin Mar 12 '18 at 4:35
  • @amaclin: Interesting, I wasn't aware of that. Do you have a source for that? And do bitcoin clients actually check the timestamps? If so, what is the allowable drift before the client complains? If it's small, that should defeat this attack. – BlueRaja - Danny Pflughoeft Mar 12 '18 at 15:36
  • Less than a few hours: bitcoin.stackexchange.com/a/20490/5406 – Murch Apr 24 '18 at 6:48
0

Can I call you Dan? I'm going to call you Dan.

This is an intriguing idea you purport. I believe it may actually be possible. But first I think it's important to go over the basics.

1. Introduction Commerce on the Internet has come to rely almost exclusively on financial institutions serving as trusted third parties to process electronic payments. While the system works well enough for most transactions, it still suffers from the inherent weaknesses of the trust based model. Completely non-reversible transactions are not really possible, since financial institutions cannot avoid mediating disputes. The cost of mediation increases transaction costs, limiting the minimum practical transaction size and cutting off the possibility for small casual transactions, and there is a broader cost in the loss of ability to make non-reversible payments for nonreversible services. With the possibility of reversal, the need for trust spreads. Merchants must be wary of their customers, hassling them for more information than they would otherwise need. A certain percentage of fraud is accepted as unavoidable. These costs and payment uncertainties can be avoided in person by using physical currency, but no mechanism exists to make payments over a communications channel without a trusted party. What is needed is an electronic payment system based on cryptographic proof instead of trust, allowing any two willing parties to transact directly with each other without the need for a trusted third party. Transactions that are computationally impractical to reverse would protect sellers from fraud, and routine escrow mechanisms could easily be implemented to protect buyers. In this paper, we propose a solution to the double-spending problem using a peer-to-peer distributed timestamp server to generate computational proof of the chronological order of transactions. The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.

2. Transactions We define an electronic coin as a chain of digital signatures. Each owner transfers the coin to the next by digitally signing a hash of the previous transaction and the public key of the next owner and adding these to the end of the coin. A payee can verify the signatures to verify the chain of ownership.

enter image description here The problem of course is the payee can't verify that one of the owners did not double-spend the coin. A common solution is to introduce a trusted central authority, or mint, that checks every transaction for double spending. After each transaction, the coin must be returned to the mint to issue a new coin, and only coins issued directly from the mint are trusted not to be double-spent. The problem with this solution is that the fate of the entire money system depends on the company running the mint, with every transaction having to go through them, just like a bank. We need a way for the payee to know that the previous owners did not sign any earlier transactions. For our purposes, the earliest transaction is the one that counts, so we don't care about later attempts to double-spend. The only way to confirm the absence of a transaction is to be aware of all transactions. In the mint based model, the mint was aware of all transactions and decided which arrived first. To accomplish this without a trusted party, transactions must be publicly announced 1, and we need a system for participants to agree on a single history of the order in which they were received. The payee needs proof that at the time of each transaction, the majority of nodes agreed it was the first received.

3. Timestamp Server The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post [2-5]. The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.

enter image description here

4. Proof-of-Work To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proofof-work system similar to Adam Back's Hashcash [6], rather than newspaper or Usenet posts. The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash. For our timestamp network, we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

enter image description here

The proof-of-work also solves the problem of determining representation in majority decision making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains. To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes. We will show later that the probability of a slower attacker catching up diminishes exponentially as subsequent blocks are added. To compensate for increasing hardware speed and varying interest in running nodes over time, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour. If they're generated too fast, the difficulty increases.

5. Network The steps to run the network are as follows: 1) New transactions are broadcast to all nodes. 2) Each node collects new transactions into a block. 3) Each node works on finding a difficult proof-of-work for its block. 4) When a node finds a proof-of-work, it broadcasts the block to all nodes. 5) Nodes accept the block only if all transactions in it are valid and not already spent. 6) Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash. Nodes always consider the longest chain to be the correct one and will keep working on extending it. 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

New transaction broadcasts do not necessarily need to reach all nodes. As long as they reach many nodes, they will get into a block before long. Block broadcasts are also tolerant of dropped messages. If a node does not receive a block, it will request it when it receives the next block and realizes it missed one.

6. Incentive By convention, the first transaction in a block is a special transaction that starts a new coin owned by the creator of the block. This adds an incentive for nodes to support the network, and provides a way to initially distribute coins into circulation, since there is no central authority to issue them. The steady addition of a constant of amount of new coins is analogous to gold miners expending resources to add gold to circulation. In our case, it is CPU time and electricity that is expended. The incentive can also be funded with transaction fees. If the output value of a transaction is less than its input value, the difference is a transaction fee that is added to the incentive value of the block containing the transaction. Once a predetermined number of coins have entered circulation, the incentive can transition entirely to transaction fees and be completely inflation free. The incentive may help encourage nodes to stay honest. If a greedy attacker is able to assemble more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing back his payments, or using it to generate new coins. He ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.

7. Reclaiming Disk Space Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space. To facilitate this without breaking the block's hash, transactions are hashed in a Merkle Tree 7[5], with only the root included in the block's hash. Old blocks can then be compacted by stubbing off branches of the tree. The interior hashes do not need to be stored.

enter image description here

A block header with no transactions would be about 80 bytes. If we suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computer systems typically selling with 2GB of RAM as of 2008, and Moore's Law predicting current growth of 1.2GB per year, storage should not be a problem even if the block headers must be kept in memory

TL;DR: A solid maybe.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.