Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A double-spend protocol to make 0-confirmation transactions secured by consensus rules.

0-Confirmation Double-Spend Protocol

The problem

Bitcoin-accepting merchants want to receive payment and provide services instantly. However, block construction times can be as much as 10 minutes after the moment a bitcoin transaction is broadcast. In the time after a transaction but before a block’s creation, that transaction can be superseded by another transaction with a larger fee paid to miners.

With the change in the mempool protocol from first-seen-first-included and the rejection of conflicting double spends, to the inclusion of double spends and prioritizing transactions with larger fees attached, 0-conf transactions can no longer be reasonably secure for any sized transaction.

The idea of replace-by-fee was that miners will follow their immediate self-interest, and if miners sporadically act that way, could potentially decrease trust in the system. Now that this approach has been assumed and is the default behavior of miner software, we might consider amending the protocol by building off this assumption.

Double-spend attempts are profitable because double spenders can trick others into providing a good or service, and then send out a conflicting transaction attached to a higher fee which enables them to keep all their bitcoin and retain their good or service. However, these transactions are completely out in the open. Every node participating in the mempool relays transactions and can verify that a double-spend transaction has occurred. The network has the power to punish any double-spend attempt without harming the counter party so long as the amount of a transaction is collateralized by at least an equal amount of the outputs in a transaction. All that is required is a consensus change to allow miners to do so.

Proposed approach

Let's define a double-spend as any set of transactions with overlapping inputs, where the union of all outputs in those transactions sends more than the union of the set's inputs. For any set of transactions available to a miner which meet these criteria, let that miner select the smallest transaction to include in the transaction block section, place the rest of the transactions in a double-spend block section which are not processed, and claim the fee reward plus any collateral placed in the transactions.

This part of the protocol is secure if all transactions are included in the next block, but there are a few ways to game this system if those transactions don't get included.

Delayed Double-Spend Attack

Alice has 100 Bitcoin split among 5 UTXOs.

let UTXOSet = [10,40,20,10,20]

Over the course of this attack, she sends 3 transactions

  1. Alice to Bob, 49 btc, sends 1 btc back to own address, low fee, {spend: UTXOSet[0]-1 + UTXOSet[1], collateral: UTXOSet[2] + UTXOSet[3] + UTXOSet[4]}
  2. Alice to Alice, 50 btc, high fee, UTXOSet[2] + UTXOSet[3] + UTXOSet[4]
  3. Alice to Alice, 48.9 btc, sends 1.1 btc back to own address, low fee, UTXOSet[0]-1.1 + UTXOSet[1]

Alice sends Bob transaction 1. After receiving the coffee, Alice sends transaction 2 so that she can get a large her collateral back without triggering the double-spend. After 2 is mined in the next block, but not 1, The state of Alice’s address is [10,40]. Now she sends 3. Since 3 returns 0.1 btc more than 1 back to the address, the profit maximizing option is for the miner to include 1 in the double-spend section. It then records 3 in the recorded transactions and takes the 1.1 bitcoin as its reward for mining a double-spend. Alice has saved 46.8 btc from the entire transaction.

Miner Double Spend Store Attack

Alice has 100 Bitcoin in her address.

Alice sends 3 transactions

  1. Alice to Bob, 1 btc, low fee
  2. Alice to Bob, 1 btc, higher fee
  3. Alice to Alice, 99 btc

Due to high transaction volumes Transaction 1 is never included and eventually drops out of the mempool. A miner keeps this transaction saved for the next time Alice sends a transaction to a different address. Alice sends 2 to fulfill her obligation she was paying Bob for earlier. Then later, she sends 3 to consolidate her addresses. The miner which kept the old transaction includes that transaction in the block and uses the 99 btc transaction as a double spend proof, taking 98 btc and sending the original 1 btc to Bob.

Mitigation

The first part of this protocol enables double-spend security so long as all transactions are broadcast and available to miners simultaneously. However, if a double-spender splits their double-spend transactions into multiple transactions, it's possible to game this system and perform a double spend across multiple blocks. It also enables miners to save transactions which were never included in a block and lost to the mempool with the intention of including those transactions later to prove a double-spend attempt.

The solution to both is to add a single component to transactions, and an extra consensus rule.

Overlapping Block Range Double-Spend

The current block height is known to everyone +/- 2 blocks due to block propagation times, and the schedule for proceeding block creation is a reasonably constant rate. With this information, users can declare what range of blocks their transaction will be valid for. With this new component, let's amend our definition. A double-spend is any set of transactions with overlapping inputs, where the union of all outputs in those transactions sends more than the union of the set's inputs, and every member's block range overlaps with at least one other member of that set, including previously mined transactions.

Spite Attack Example

For this example, we'll start at block 500.

Alice has 100 Bitcoin split among 5 UTXOs in her address.

let UTXOSet = [10,40,20,10,20]

Over the course of this attack, she sends 3 transactions

  1. Alice to Bob, 501-600, 49 btc, sends 1 btc back to own address, low fee, {spend: UTXOSet[0]-1 + UTXOSet[1], collateral: UTXOSet[2] + UTXOSet[3] + UTXOSet[4]}
  2. Alice to Alice, 501-501, 50 btc, high fee, UTXOSet[2] + UTXOSet[3] + UTXOSet[4]
  3. Alice to Alice, 502-502, 48.9 btc, sends 1.1 btc back to own address, low fee, UTXOSet[0]-1.1 + UTXOSet[1]

Alice sends Bob transaction 1 with a large valid block period to give Bob assurance that the transaction will succeed. After receiving the coffee, Alice sends transaction 2 so that she can get a large amount of her bitcoin without triggering the double-spend address loss. Then Alice sends transaction 3. The miner sees that 3 and 1 would cause a double-spend. This time however, instead of mining 1 or 3, the miner see's the previously mined transaction 2's block range overlaps with 1, and that 1 overlaps with 3. Collectively each member in the set overlaps with one other member. So, the miner can include both 1 and 3 in the double-spend block and keep the remaining 50 btc for itself. Alice has effectively paid 50 btc for a 49 btc cup of coffee.

Vulnerabilities

In the last example, Bob was deprived of payment and the coffee he sold, but it was not in the interest of Alice to perform this attack. If Bob believes that Alice could be malicious and spiteful enough to pay 1 BTC to ensure Bob loses this transaction, he can always demand that Alice pay the fee to ensure the transaction is included in the next block. All Bob must ensure is that the block range is large enough that the transaction be mined, and the transaction is less than or equal to the collateral. The larger the collateral, the costlier it is for a spiteful attacker to deprive their target of funds.

Another concern is that block height is not precisely known because of block propagation times. This fact bolsters 0-conf security. Honest transactions specify large block ranges in hopes of being included and signaling to the recipient that this transaction can be used for double-spend proof for a lengthy period. It's mostly double-spenders who require precision of block range, which is much harder to accomplish given the relatively uncertain current block.

While this protocol modification is resilient to non-miner collusion attacks, it's still subject to fraud in the form of Finney attacks.

Finney Attack Example

Let UTXOSet = [10,20,30];

2 Transactions occur.

  1. Alice sends UTXOSet[1-3] to Alice
  2. Alice sends UTXOSet[1] to Bob

Alice mines a block with 1 but doesn't broadcast that block. Alice goes to Bob, broadcasts 2, receives coffee. Alice Broadcasts blocks, Bob loses 0-conf, and double-spend proof will have no effect.

This 0-conf attack method was first noted by Hal Finney, and it was an exploit that was used by some mining pools when playing Santoshi dice, who accepted 0-confirmation transactions and paid out winnings within 30 seconds.

Mitigation

Any transaction with double-spend safe inputs totaling greater than the collateral included in the transaction UTXO total cannot be included in the main block space but must be placed in the double-spend section of the block. In addition, a Finney attacker knowing about this protocol can intentionally trigger a double-spend to self. To mitigate this, for a period of 3 blocks, the outputs of the collateral can not be collected by the miner for a period of 3 blocks, and any double spend proof provided by another miner will superceed a previous collateral claim. But an override cannot be overridden. So any Finney attacker that attempts a double spend will have to mine one of the next 3 blocks after their attack in order to secure their collaterl.

With this amendment, we can delay the validity of a full spend, ensure that miners see a Finney attack before it's valid, and reward any miner that includes Alice's broadcast transaction to Bob.

Replace-By-Fee

With this protocol, replace-by-fee is not possible for legitimate batching of asynchronous transactions would save block space, and therefore fees.

Legitimate Replace-By-Fee Example

Alice has 4 Bitcoin in her address.

let UTXOSet = [2,2]

Alice sends 2 transactions

  1. Alice to Bob, 1 btc, { input: UTXOSet[0], output: {Bob: 1, Alice: 1}, collateral: UTXOSet[1] }
  2. Alice to Carol, 1 btc, Replace tansaction 1, { input: UTXOSet[0], output: {Bob: 1, Carol:1}, collateral: UTXOSet[1] }

Under this new protocol, a double spend because you has occured 2 signed transactions sending the same inputs, but the unique outputs are totaling greater than the inputs. When the set of outputs are unioned, we get { Alice: 1, Bob: 1, Carol:1 }.

Recipient Signed Update

If we let Alice exclude her output from the double-spend proof though, we can give update the transaction the transaction and cancel the double spend proof. To do this, we exclude any outputs from our union where the transaction is signed by the recipent. If alice signs 2 with her recieving adddress from 1, we know that permission has been given by the recipient to replace the transaction.

Therefore the set union of outputs without updates signed by recipients is { Bob: 1, Carol: 1 }. A miner cannot use an output which has a double-spend signed by a previous recipient in order to prove a double spend and claim the collateral.

With this, let us modify our definition of a double-spend one last time. A double-spend is any set of transactions with overlapping inputs, where the union of all outputs in those transactions, filtering outputs that conflict with other transactions where those transactions are signed by recipiant of that output, sends more than the union of the set's inputs, and every member's block range overlaps with at least one other member of that set, including previously mined transactions.

Opt-In Addresses

With this approach, it’s possible to make this entire protocol opt-in. Instead of running these double-spend checks on all addresses, a new address type can be created, much like segregated witness addresses. These addresses can be treated like checking accounts, capable of assuring merchants and recipients that the 0-conf transactions broadcast to the network will be impossible to double-spend profitably. We can take advantage of the fact that these addresses are only meant to be collateralized spends, and enforce a protocol based on those assumptions. With opt-in addresses however, inputs and collateral will have to come exclusively from these new address types.

This is much like funding payment channels, but with the possibility to send transactions to any address when they’re offline, and without anything like the lightning network, which creates a queryable honeypot of hot wallets, a likely new target for zero-day exploits.

Side Benefits

Lightning Network reduces the need to run a full node as transactions are moved off chain, and only keeping updated with the mempool and the last 48 blocks will be needed to monitor for broadcasts of payment channels in an old state. With the double-spend protected 0-conf, you need a fully validating node to know if a 0-conf transaction can even be included under consensus rules.

With this change, not only are 0-conf transactions made more secure, but so are n-conf transactions. Even if a block is orphaned, the block range enables miners to punish double-spends up to the specified block validity period.

Also, this modification enables other changes to the protocol, such as increasing the block production period. An increased block production time would vastly decrease the likelihood of orphaned blocks, but also make the entire block chain resilient to incredibly high latency. Examples include…

  • A future where Earth has colonized Mars for example, the universal speed limit, lightspeed, creates a minimum communication time of 3 minutes. Setting the block production time to 1 hour or 1 day would make this trivial. But with this protocol, 0-conf transactions are immediate and consensus secure.
  • Alternatively, if the internet is somehow disabled here on Earth, a somewhat more immediate if less probable concern, Bitcoin could be made resilient to even this level of failure and switch over to RFC 1149 (IP over avian carrier). With latency as high as required by carrier pigeons, a block production time might be on the order of weeks or months.

Also, with longer block production times, reliance on 0-conf, and therefore running fully validating nodes becomes more worthwhile. If you want to make running a full node as useful as possible, then this is the ultimate lever to pull. If you were to push the block production period to the order of months, you’d reduces transaction fee spikes and smooth them across a longer time horizon.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.