Bitcoin Forum

I started writing unit tests yesterday for re-enabling transaction replacement.  I'd like to ask the community for their ideas for transaction replacement use cases so that I can work toward a solution that would work for as many people as possible.

I'm also considering the idea that if transaction replacement is not enabled, many use cases would be enabled by changing the semantics of nLockTime such that transactions with an nLockTime in the future (either block number OR time) must not be accepted to the memory pool at all.

Some caveats to think about:

• CTransaction::IsNewerThan appears to have a flaw in the final loop of the method, unless there are side effects people care about.  In the current incarnation (which dates back to sometime in 2009 or possibly even back to the original code), it's possible for some inputs to have higher sequence numbers than the previous version of the transaction and for some to have lower sequence numbers and still have the transaction come out as "newer."  Unless this is done for specific side effects, it appears to be a bug (though easily fixed).  As far as I can tell, the only code that calls CTransaction::IsNewerThan is CTransaction::AcceptToMemoryPool, and that code path is never hit due to the disabling of transaction replacement.  In addition, that code doesn't use any side effects of that loop as far as I can see.
• I haven't found any code that prevents transactions from using the outputs of non-final transactions in CTransaction::AcceptToMemoryPool.  In the event of transaction replacement, such code will be necessary in case outputs are changed about.  It may be desirable to restrict the way outputs may be changed to prevent double spends.
• At the very least, we'll need to add output to RPC and possibly to the UI to show whether unconfirmed transactions are final or not.  This will be important to merchants to ensure that they don't take 0-confirm transactions that can be replaced out from under them, causing a double spend in reality, regardless of how they've propagated through the network.
• Some form of discouragement should be undertaken to prevent miners from including versions of transactions that aren't the latest version.  If this uses block rejection, this will cause miners not following the rules of the majority to mine blocks that will not be accepted in the consensus chain, causing lots of dead-end branches.  If this uses transaction fees to incentivize miners to get the maximum fees by including the latest version, it might be a good idea to restrict newer versions to force them to pay higher fees with each version.  This still requires guesswork on the part of the sender to predict how much of a transaction fee addition would make miners willing to validate the new version of the transaction.  It also means we may need to change the rules for transaction replacement with regard to inputs, allowing a new input to cover the additional transaction fees if needed (this would mean modifying at least CTransaction::FetchInputs as well).
• There are no incentives to forward multiple versions of a transaction; in fact, there is a disincentive: each time a new version is received, it must be validated before being accepted to the memory pool and forwarded.  This resource usage could actually cause a DoS, as Gavin has mentioned, if too many versions of a transaction are forwarded through the network.  Anti-DOS code would have to be added to somehow throttle propagation of new versions; some people may even modify their nodes to not propagate such transactions at all, which would defeat the purpose of this whole debate.
• Changing the semantics of nLockTime to mean that non-final transactions can't be in the memory pool doesn't change the block validation rules.  It also prevents non-miner nodes from having to validate a lot of different versions of a transaction, causing DoS.  The caveat is that in actual use, nLockTime will have to be set far enough out that the final version of the transaction has virtually 0 chance of not making it into a block by the time nLockTime expires.  This would prevent a timelocked transaction from being accepted by miners over a finalized transaction with a lower fee.

Do the current block validation rules not reject blocks that include transactions with unexpired lock times?

They do.  The problem happens when something like this occurs:

1. Timelocked transaction with an input that has a sequence of 1 is sent, paying 100 BTC back to the customer and 1 BTC in fees
2. Non-timelocked final transaction occurs right around when nLockTime expires, with 50 BTC to the vendor and 51 BTC to the customer
3. Before either version is included in a block, nLockTime expires

Now both of the transactions are valid.  Self-interested miners will try to mine the original transaction into a block.  Miners under the current rules (no transaction replacement) will also try to mine the original transaction into a block.  Miners that have implemented transaction replacement will try to mine the final transaction into a block.

Miners that have implemented transaction replacement would, under current rules, accept blocks from self-interested miners that go for the higher transaction fees and from miners that haven't implemented transaction replacement.  Unless, of course, we change the block validation rules so that if a block contains a transaction for which the memory pool holds a later version, that block is rejected.

The other alternative I can think of (and this would actually help protect against DoS, too) is to ensure that each newer version of a transaction has higher fees associated with it, thus aligning the incentives of miners with the way transaction replacement is supposed to work.  In that case, the final transaction in step 2 would have been constructed differently:  50 BTC to the vendor, 49 BTC to the customer and 2 BTC in fees.  This would align incentives, but it would have to be forced by the network (or at least by vendors in a multisignature scheme, who wouldn't deliver services until they knew the transaction they want is going to be the one that commits to the blockchain).

My alternative proposal, changing the semantics of nLockTime, keeps the block validation rules the same but changes the memory pool rules so that timelocked transactions are not allowed in the memory pool, thus allowing unlimited versions of the transaction to be created and potentially finalized as long as it happens before nLockTime expires and the original transaction is valid for broadcasting/committing to the blockchain.

Hmm.  I think I need to sit down and read everything again when I have time to be more thorough.  I'm not doing a very good job of keeping "is" distinct from "should be" as I walk through these scenarios.  Also on my todo list, look into how the lock timer really works.  There is a world of difference between absolute time and relative time.

I keep thinking that the network would see transaction # 2 as a double spend and reject it.  But we can't prevent the source from passing it directly to a friendly miner that could include it in a block, which would make it the real version regardless of how the rest of the network felt about things.

I'm not a big fan of mandatory fees, even trivially small ones.  But it does seem to work here, at first glance.

Exactly the problem.


It does, but only sort of, and the rules for anti-DOS would have to be tuned well.  Most schemes would have a timelocked transaction to keep money from getting nuked or to allow the customer to get his deposit back, and a finalized transaction to actually pay the vendor.  DoSing entities would send themselves multiple versions of multiple transactions rapidly, forcing each version to propagate through the network and use disk and CPU resources on each node for verification - thus, each version needs to cost more.  I'd even go so far to say that each new version should have to at least double the fees of the previous one, with the initial/timelocked transaction having a set minimum fee (or a percentage fee, even).  That increases the cost of multiple versions very rapidly while keeping the normal use case of a single replacement cheap.

Also, just because the fees align miners' incentives in general with transaction replacement doesn't mean double spends won't happen with "friendly" miners.  Then again, double spends can happen NOW with friendly miners assuming lots of mining power or lots of luck.

But that isn't the normal use case.  That is merely a normal use case.  Doubling fees with every replacement would certainly turn it into the only possible normal use case.

This is true, which is why I'm here asking for people for use cases for transaction replacement!  So far, the use cases I know of can be made to work by simply preventing non-final transactions (those with unexpired nLockTime) from ever entering the memory pool if the schemes are rearranged slightly.

The design of sequence numbers is subtle (read: confusing), but the code is correct. I wish Satoshi had tried to document this stuff better. I got the impression that he didn't intend to leave the project when he did, but decided he was getting too much attention for his liking.

Let me try and explain why this is as designed.

A contract may contain contributions by multiple parties. The definition of IsNewerThan() says, in English,

• If the transaction has the same number of inputs which are connected to the same outputs (ie, only the script+seqno are different), and ...
• at least one of the new inputs sequence numbers is higher than all of the other sequence numbers
• ... then allow tx replacement

Here is a table showing iterations of the core loop of IsNewerThan():


Because the sequence numbers are always zeroed out in SignatureHash(), this means that any partner in the contract can issue a new version without breaking the signatures on the other inputs.

If the sequence number was a signed property of the transaction, changing it would invalidate all other signatures. If it was an unsigned property of the transaction, anyone could issue new versions of the whole transaction. By making it a signed property of the input, only participants in the contract can issue new versions, and they can do so without requiring the involvement of the other parties.


The code appears to work, actually, though I've never tested it. It does however have a DoS attack (as is typical of Bitcoin).

You're allowed to depend on non-final transactions. If the tx is replaced, the dependees of that tx become orphans. They will stay in the memory pool forever because nothing deletes them. This is a general attack: you're allowed to fill up the memory pool with orphan transactions, it is independent of replacement, however replacing a TX on which other transactions depend can cause this too.

Other than wasting memory the code will not do anything incorrect. In any case, there is little legitimate reason to depend on a non final transaction because the moment it's replaced your tx becomes invalid. To reliably spend it you'd have to wait for the tx to finalize. There may be a use case for it I haven't thought of.


Yes. It may be safest to add a new parameter, defaulted to false, that indicates whether to show non-final transactions.


Why would a miner want to do that? Unless the fees on the newer tx are lower, there's no reason not to just follow the standard rules here.


You could just have a form of exponential backoff for updating transactions. If you try and replace a transaction way too frequently replacements would be dropped until it "cools down".

Thanks for clarifying; this is where I was getting hung up.  I was able to replace all but one version number with OLDER versions and at the same time increment just one version number and make it pass the IsNewerThan() test.  Now that I understand the semantics, it makes more sense.  I have more research/thinking/testing to do to see if I can still make it break.


Right, what I was trying to do is prevent merchants from relying on non-final transactions.  There may be a use case for it that neither of us has thought of, but there are merchants right now that rely on 0-confirmation transactions being "final."  I think your suggestion is probably the best method and should prevent merchants from even seeing transactions until they're finalized or committed to the blockchain, thus preventing double spends against them.


Miners colluding with senders who are (or are themselves) trying to double spend may find it beneficial to include previous versions of transactions rather than later versions.  Also, as you said, fees on the newer version may be lower.  Without discouragement of too-old transaction versions, there will be a greater chance of the latest version not being the one that gets committed.  This obviously gets mitigated in multisignature use cases but if there are use cases that I haven't thought of without multisignature, it could cause headaches.


My problem with this is that, as far as I can tell, it's still possible to DoS nodes by using many smaller transactions.  If an attacker broke up a 100BTC output into 5,000 .02BTC outputs and started to flood updates for all of those, she could still overwhelm the network.  Setting both per-transaction and global thresholds to prevent the scenario above could result in DoS not of nodes but of valid transaction replacements.

This would still be a problem for the exponentially increasing fee proposal I made (except the global threshold DoSing valid replacements; I don't think that'd be needed) but not as big a problem as for the exponential backoff as far as I can see.  Again, tuning the exponentially increasing fee (both the starting fee and how fast the fee increases) can help trade off costs for valid users vs. costs for attackers.  Also, I can't think of a reason not to make it adjustable and let nodes set their own policy about how severely they want to limit transaction replacements.

By the way, and only somewhat separately, here's another interesting use case for transaction replacement:  minimizing transaction fees.  A user sends a transaction that's not timelocked, has a non-max sequence number for the inputs, and has two outputs:  one back to himself for 5 BTC and one to some recipient for 5 BTC, with a fee of 0.0005 BTC.  After a while, the user sees that the transaction doesn't confirm and replaces it with a transaction that has a higher fee.  The user repeats this process every couple of blocks until the transaction does confirm.

Gah, sorry. I made a mistake in the above diagram and thus my explanation is buggy! The last example should be:


ie, fNewer == FALSE for this case, even though the sequence number is higher. This makes a lot more sense than my previous explanation because it prevents rollback attacks.

Let me try again.  The definition of IsNewerThan() says, in English,

• If the transaction has the same number of inputs which are connected to the same outputs (ie, only the script+seqno are different), and ...
• There are no sequence numbers in the new transaction lower than the previous transaction and ....
• At least one sequence number is higher

... then allow tx replacement.

However this contradicts what you put in your original post. I don't see how it's possible to have a sequence number be lower than before and have fNewer still come out to be true.


The latter case can be fixed by just telling people, don't do that :-)

Miners colluding with spenders is already a known attack vector from the very beginning. I'm not sure it is any different to the regular case (eg chain fork or finney attack).


The ideal way to handle DoS is to prioritize work effectively, so DoS transactions still get processed as fast as possible, but only after all other work has been done. So you can soak up 100% of a nodes resources but you can't actually deny service to other people.

For the tx replacement case, it means that there'd be a global work queue of signatures to check. Signatures found in blocks come first. Then transactions entering the memory pool for the first time. Then transactions that are replacing other transactions, ordered by last update time.

Changing Satoshis code to be written like this isn't particularly easy, but it could be done.

Thanks, rollback attack is the name for what I was thinking of.  I'm able to do these:


I think that's about right.  It essentially leaves an opportunity for one of the parties to the contract to sit around while the rest negotiate, and then roll back the negotiations to any previous point by incrementing its sequence number and picking any previously signed configuration.  I think this is partially mitigated by the fact that any change in the outputs actually requires a signature from all parties but if one of the parties signs new versions without incrementing its sequence number, that party will be able to execute a rollback attack.


That works for me, then.  The latter case is especially mitigated in multisignature situations where the receiving party won't accept later versions of a transaction with a lower fee.  Combined with non-final transactions by default not showing up until they're confirmed when using listtransactions and the like should mitigate the risk of most use cases unless the merchant intentionally tries to open himself up to being screwed.  So it's not idiot proof, but it takes a willful idiot.


I like this idea for DoS prevention and will work to implement it that way.  My background (most recently) is networking and network security, so queuing algorithms are familiar territory.  I can be myopic in my thinking sometimes, so thank you for pointing out this idea.

I had another thought.  When using nLockTime with transaction replacement, the timelocked transaction must not have all inputs' sequence numbers set to UINT_MAX, otherwise it's impossible to replace it.  So, to enable many of the contract use cases right now while working on enabling transaction replacement, it wouldn't be very disruptive to change nLockTime semantics so that any transactions with nLockTime in the future AND all input sequence numbers set to UINT_MAX may not be added to the memory pool.  This leaves nLockTime semantics the same for the transaction replacement use cases but enables many contracts to be modified to be possible NOW.  It also makes sense as a long-term rule because it's pointless (and potentially dangerous as it can lead to DoS) to accept a non-replaceable timelocked transaction.

Another DoS related thought, too.  As you mentioned, orphan transactions (dependents on previous versions of replaceable transactions) can fill up the memory pool.  When enabling transaction replacement, are there any disadvantages to deleting those dependent transactions from the memory pool?  I can't think of any at the moment.

Ugh you're right. My first explanation was correct. I confused myself the second time. This thread is such a mess, sorry :)

Satoshi had this to say on the topic when I discussed it with him some time ago:


I guess the reason you can do "rollback attacks" is to allow for that use case - somebody provably exits the negotiation by signing a sequence number of UINT_MAX so that they can't update the tx any further. So perhaps rollbacks aren't actually a problem for the use cases he had in mind.

I think it's fair to say we need to think about this more before changing the definition of newer.

I agree, let me chew on this too.  I'm going out of town for a week so I may be in and out of communication but I'm going to keep working on understanding how all this works.

In the meantime, I'd love to know what you think of the idea of declaring transactions with nLockTime in the future and ALL inputs at UINT_MAX as illegal to put in the memory pool.  This avoids all cases where transaction replacement could actually happen and allows nLockTime to be used the way hashcoin and I thought it was used before you clarified it for us.  It does change what's considered a double spend with such a transaction but nobody's using timelocked transactions the way they currently work anyway because it seems useless without transaction replacement.

Currently such a transaction would be considered finalized immediately regardless of the fact that it was time locked, so broadcasting it before its allotted time would be counterproductive. I need to think through the implications of changing that.

Put this stuff into BIP... I give $100 USD bounty for this to become real.

Bump...

Guys, we still need this... don't forget about it.

Can you tell me what is "TX replacement" in simple words, thanks!

This is the explanation I gave when I was at the Israel Bitcoin Meetup

Imagine you play poker with your friend... Both of you have stack of chips... During the game you stack of chips grows\shrinks... When you done you change chips into cash and go..

Now imagine you play with Bitcoins instead of chips...

Pot = 2-of-2 multi signature transaction ( tx A)

After each round you (you and your partner ) create transaction ( 1 input(tx A) and 2 outputs )  (don't transmit into network ) representing your bitcoins if the game will end right now.

When game is over and you want to cash out - you send latest transaction to network...

Is it clear now?

We haven't forgotten about it. These things are subtle and take time to get right. Don't worry about it.

I've definitely not forgotten about this.

I've started a new job that keeps me much busier than my previous one. I don't know if or when I'm going to have time to get back to championing transaction replacement.

On the nLockTime front, my suggested semantics change won't work. I misunderstood current semantics still and a more thorough look through the source code showed me why. I still think the IsNewerThan check is wrong but haven't had time to write it up.

We need functional transaction replacement to implement many of the more interesting contract ideas. I have other ideas too and way too little time to implement them. I'll at least try to write them up when I get the time in case other people are interested.

That's your duty for community... don't let them die in your head

Exactly why I want to write them up. I think it could be a killer app for Bitcoin.

Increasing the fee on each version is a perfect solution, except not doubling. It should increment by a constant predefined amount that is more than the maximum estimated cost of bandwidth and resources consumed by broadcasts. Then it's a user fee.

The inputs wouldn't have to change as long as there's a change return to reduce.

That would be a good temporary fix that would work in simple cases with only one nLockTime transaction, like an escrow expiration payment.

They shouldn't create multiple versions though, because if replacement is still disabled, then it's just a race at nLockTime to broadcast first and the version doesn't matter.

Another possible temporary fix would be to enable only a single replacement: final replaces non-final. That would allow a single lockTime transaction for expiration default, and is only one line of code without getting into all the issues. It's stupid that a lockTime transaction can sit in the pool and block a final transaction that trumps it.

For that, you just set sequence numbers to 0xfffffffe.  The maximum value is 0xffffffff, which means that there's only room for one replacement before the tx becomes actually-final.

EDIT: The point was, that you could make a or node-acceptance rule that only allows replacement on seq=0xfffffffe instead of any value

Either way will work. Just make sure they can't do this, like with 4 inputs:
0xfffffffe-0xfffffffe-0xfffffffe-0xfffffffe
0xfffffffe-0xfffffffe-0xfffffffe-0xffffffff
0xfffffffe-0xfffffffe-0xffffffff-0xffffffff
0xfffffffe-0xffffffff-0xffffffff-0xffffffff
0xffffffff-0xffffffff-0xffffffff-0xffffffff

Final replaces non-final is simple to implement, just add to the replacement conditions:
  if (!IsFinal())
      return false;

In other words, replacement is only allowed if you're replacing with this:
0xffffffff-0xffffffff-0xffffffff-0xffffffff

The only difference between this and blueadept's way is whether the lockTime transaction can get into the pool ahead of time, or they have to wait until lockTime to broadcast it (if they're still around by then).

Good point about the multi-input seq numbers.  I forgot they are per-TxIn, not per-Tx (like nLockTime).

Gavin and I debated your last point the other day, because we were determining if it was possible to have a "Seller automatically gets payment after 31 days" in escrow transactions, in case the buyer is too lazy to sign the escrowed Bitcoins to the seller.   What we determined is that if the locktime is in the future and any one sequence number is non-maxxed, then the tx will be accepted to the memory pool but not included in a block.

What this gives is you a very inconvenient implementation of what you have already proposed.  It is replaceable but only if you get a miner to agree to drop the locked tx in their memory pool and accept your final replacement tx.  If they have enough mining power and there is enough time, your tx will eventually make it into a block and invalidate the locked tx in all nodes' memory pools.

The issue, of course, is that it's not really feasible to have regular users contacting miners to help them replace tx like this (in the event that the seller broadcasts the 31-day tx right away, hoping the buyer can't figure out how to replace it).  Also, I didn't like the idea that anyone would be able to bribe a miner to replace their 0-confirmation tx.  But that's a whole 'nother story...

In the long run, I think we have to assume that miners will do what is most profitable, and design escrow/payment protocols around that assumption.

Replacing non-final transactions in the memory pool potentially opens up a whole bucket of worms, but I think the short-term challenge is to figure out if we should change the rules we have now. If we do (I think we should), then I think it would be a mistake to do anything other than "create rules that will maximize miner profits."  Because if we do something else, then sooner or later I believe there will be a "miners special" version of the code that has miner-friendly rules.

---

If you agree with me that the default rules in the client should maximize miners' profits, then it seems to me there's one simple rule change we should make:

If you've got two otherwise equivalent transactions that spend the same input(s), keep the one with the most fees.

Right now, the rule is "keep the first one you see."

The bag of worms comes into play if you've got two transactions that spend the same input(s) that, for example, look like this:

Transaction 1:  final transaction (can go into a block RIGHT NOW) that has a fee of 0.005 BTC
Transaction 2:  transaction that won't be final for 3 days that has a fee of 0.1 BTC

Should a miner put Transaction 1 into the block they're mining and take the smaller fee now, or not include it, hoping that nobody else mines Transaction 1 in the next 3 days so maybe they can mine Transaction 2 and get the bigger fee?

I'm not an expert in game theory, but I believe the winning strategy in the above situation, assuming everybody knows about both transactions, is to mine Transaction 1 right away (any economists reading who know a lot more about game theory than I do?).

That suggests the rules for transactions that spend the same inputs aught to be:

1. If you have two free transactions, keep the first one you see.
2. If you have a free and a fee-paying transaction, always keep the fee-paying one.
3. If you have two final, fee-paying transactions, keep/mine/relay the one with the higher fee.
4. If one or both of the transactions is non-final, keep/relay the one that will become final first.

FWIW, I completely agree with Gavin on this. As long as a transaction is valid, the rules should be ones that maximize miner profit so that miners play by the rules and transaction participants can know what to expect. If there's a conflict between rules and miner profit, transaction acceptance is not deterministic because you don't know whether a miner is playing by the official rules or the profit maximizing rules.

My concern is that we need to make sure people know not to trust unconfirmed non-multisignature transactions. If even some miners are taking final transactions in their memory pools and replacing them with double spend transactions having bigger fees, transactions have a significant chance of being reversed before they're confirmed.

This further cements Bitcoin's position as a settlement network, creating the necessity to create clearing mechanisms on top of it as recently mentioned by genjix. But enabling transaction replacement in this way can also make it easier to create such clearing mechanisms.

I am swayed.  Otherwise we're trying to swim upstream.  I just didn't like the idea that anyone can replace their not-in-the-blockchain-yet tx (final or not) just by submitting one with a bigger fee.  It seems to make the zero-conf tx even more useless than before.  On the other hand, maybe it's a good idea to do that and cement zero-conf tx as totally useless outside of the pure-trust tx (at least before, the person has to inject a replacement into the blockchain, not just broadcast it). 

It's fine and good to require ascending fees for lockTime transactions, which are explicitly replaceable...

It would be terrible for final transactions! Final transactions are explicitly not supposed to be replaced. Replacement is fraudulent double-spending! Sure, some miners might cheat, but I think most would be honest for smaller POS sized payments. As long as at least some are honest, the double-spender has a substantial chance that the double-spend won't work and he'll end up paying, which breaks most theft cases because of the discount at fencing goods. Only if you throw in the towel and say miners should intentionally side with double-spenders will they have 100% chance of getting away without paying.

The whole point of the Bitcoin network is supposed to be to witness which transactions came first. Don't give up on that!

The problem with this isn't apparent now but will be when fees make up most of miner income. When miners compete for every last Satoshi, any rules that aren't enforced as part of block validity will be bent for profit maximization. That means that anything in the memory pool is fair game. It's important to teach people not to rely on zero confirmation transactions before there's a whole lot of infrastructure based on trusting them built while miners can still afford to be benevolent.

Then instead make it in the miner's interest to stay with the first transaction:

When the client software receives a double-spend, display the first transaction as bad and immediately spend its entire amount to fee. It's in the miner's interest to include the first transaction in order to include the all-fee transaction after it.

Double spending is then pointless. You lose your money and still owe the merchant, and it's your fault for spoiling the payment with a double spend.

If the receiver is not online at the time, then he's not a double spending target because he's not even online to act on 0-confirmation transactions.

In the future, this is what any game theory understanding 0-confirmation accepting merchant will do to deter double spend fraud if there are any dishonest miners.

How do you do the bolded part?  And how do you know which is "first"?

The first transaction is the one paying to the recipient (merchant). This is the recipient doing this action.

Recipient receives tx 1, paying to him.
Recipient receives tx 2, which is a double spend of tx 1 paying back to double spender.
Recipient spends tx 1 to all fee.

Including tx 1 to get to the all fee transaction after it is now worth more fee than tx 2.

The problem with a double spend is that no one really knows which is the "right" spend.  Whichever one ends up in the next block is (by definition) the right one, as far as bitcoin is concerned.  If that is the one sent to the unknown person that you are calling "recipient", wouldn't the "recipient" be better off keeping the money?

Or are you saying that the miners will be willing to ignore tx2 if they see that (tx1+all_fee) goes into their pocket, unlike tx2, which does not?

Gavin and blueadept are speculating that could happen in the future. This is all in reply to that concern that there will be dishonest miners that will take the transaction with the largest fee, even if it's wasn't first.

The concern was that a double spender could make his double spend (tx2) with a larger fee to bribe the miners.

In that case, merchants would respond by increasing the fee on tx1 (tx1->all fee) so the double spender won't be rewarded. Double spending would always fail to get any money back, so it would be deterred.

The point is, if there are dishonest miners that can be bribed with fee to take a double spend, then merchants would not sit by while they get ripped off by double spenders.

No, in this scenario the double spender is bribing miners with fee so he would always win. The merchant can play that game too and raise his fee too. Then the first spend has the highest fee and is again in the miner's best interest.

jevon, I see what you're saying and agree with you, though it becomes a balancing act between profit maximization and DoS protection on the part of the miners. To add this kind of dependency resolution for multiple versions of a transaction without any change to the protocol to send sets of transactions in a single message will require miners to be vigilant about resource use consumed by storing multiple versions of a transaction to be able to tell what future transactions depend on them and how they affect fees.

This also doesn't change Gavin's proposed rules. It just makes them friendlier to accepting zero confirmation transactions in certain circumstances.

By the way, this still doesn't work all the time. If a sender sends to a 2 of 2 multisig address for escrow for goods or services that get delivered before a block is found, the sender can double spend without worrying that the cosigner can up the fees to stop him.

ETA: What Gavin and I are saying is that there will be selfish miners. Whether they're considered dishonest or not depends on whether the official rules align with incentives or ignore them. Right now they're mostly benevolent in regards to transactions in the memory pool because the overwhelming majority of their revenue comes from the block subsidy.

Can we please hold off on yet more rule changes? The BIP 16 effort drained months of effort away from other things, like making the standard client most people use scale. Attempting to change the rules yet again will be another huge, controversial effort at a time when what Bitcoin needs is stability and basic improvements to the user experience.

The proposed change would basically invalidate Satoshis reasoning around how small payments can be accepted for things like vending machines. It would also make it impossible for lightweight clients (ie, most users in future) to accept payments until a block had been mined, basically killing the whole concept of a usable currency. The point of having a mesh in which lots of nodes don't mine and lots do is to make it difficult to distribute double spends into the memory pool like that. Even if some miners change to the proposed for-profit rule, getting your transactions to such miners such that you reliably win should be difficult.

I explicitly disagree the rules should be designed to maximize miner profits against all other considerations. If you truly believe that, just make the software automatically measure the size of the fee increase then automatically fork the block chain so it can be overridden. Turn every miner into a "blackhat miner" that slows down transactions  and rewrites the block chain if there's enough profit to do so. Or, we could assume that miners also mine as part of expressing support for a particular set of ideas and rules - not just for profit. As most mining pools already do today.

Please let's just try and use the tools Satoshi left us with rather than constantly trying to change them. I'm strongly against trying to "improve" parts of the protocol that we've barely even begun to understand yet, like nLockTime and tx replacement.

Some of the big mining pool operators are already going their own way, experimenting with new types of transactions (e.g. deepbit and eligius), so I suspect the answer to your question "Can 'we' please hold off..." is "No."

Discussions like this one are how I start to understand parts of the protocol like nLockTime and transaction replacement better.


As for BIP 16 draining effort away from making the standard client scale:  I've been saying for a year that my top priorities are network stability and wallet security. Making the standard client scale is, in my opinion, a lower priority; I don't want a super-scalable client with a 4-minute blockchain initial block sync time if it is vulnerable to the user clicking one wrong link and getting infected by a trojan wallet stealer.

Over time hopefully p2pool will reduce the power of individual pools to impact rule changes, as most miners will just trust the de-facto judgement of the project maintainers in such matters (ie, you). And the biggest pools are all run by friendly, involved operators who aren't driven purely by profit maximization.

The proposed change would make it impossible for users on lightweight clients to do anything with a zero-confirm transaction, even for small amounts. That would make something as trivial as paying for a beer for Bitcoin largely impossible, which seems like a pretty basic litmus test of "does this currency actually work?".

What's more, allowing such double spends would mean that logically it should be extended to already confirmed transactions too. Once merchants all start waiting for 1 block, or 2 blocks, or whatever, large numbers of users would simply start broadcasting double spends after 3 blocks. Once you have enough replacements for transactions 3 blocks back, if all miners use the "profit by default" rule, everyone would start mining on a 3-block back fork automatically in order to claim the higher fees.

The system would become largely useless.

It is one thing to entice miners to prefer one unconfirmed transaction over another unconfirmed transaction.  Getting them to revert even one block is an entirely different sort of thing, even for a large reward.

P.S.  I don't think that the "convert to fee" idea would work anyway.

Why?

The proposal made here was for a specific technical thing, replacing of memory pool transactions with higher fee double spends, but the rationale given is a dramatically stronger set of design constraints that Bitcoin has not previously operated under. That would be a major direction change for the project!

The design of Bitcoin is already bound by pretty severe design constraints - constraints like there must be no central authorities for anything, including such basic things as announcing news to network participants (hence broadcast alerts). That fits with Satoshis vision of a pure p2p system but obviously complicates things a lot.

The constraint that the system must be built on the assumption that miners will do anything for profit, and thus we might as well help them, makes it radically harder still. I'm not even sure it's possible to do such a cryptocurrency well, at least, it would not be Bitcoin.

Consider the case of setting the inflation schedule. In a hypothetical world where Bitcoin is very successful, we assume it has lots of users and because of the block sizes involved most of those users are on lightweight clients. Lightweight clients cannot verify the size of a coinbase transaction, so they can't check the inflation schedule is being followed.

In this world miners are financially incentivized to change the inflation schedule and start making more Bitcoins than Satoshi intended. Inflation is a tax on all other system participants that accrues to miners, so it makes sense for them to do this. But with Bitcoin as it is today there's a very practical starting problem - you have to find a majority of mining power and convince them to switch to your new set of rules. Firstly, you can't find most miners, because mining happens anonymously. Secondly, of those you do find, some of them will reject your proposal for ideological reasons despite that it could lead to more profit for them. Thirdly, the act of trying to set up such a large conspiracy would certainly be detected and could be addressed via social means, like (e.g.) laws, or other forms of social pressure.

However if you assume that purely profit driven miners are inevitable and so we might as well just help them get on with it, you'd design the software to make resetting the inflation schedule automatic, like based on votes encoded into the coinbase. With this new design constraint you eliminate all 3 reasons above from your consideration, because in your world miners are driven purely by profit and have no other limits on their behavior, so there's no reason not to do this.

A Bitcoin in which miners can and do vote on how much inflation they'd like to award themselves is not a Bitcoin I'd feel like participating in. But it's the logical outcome of assuming miners are a perfectly informed conspiracy of entirely selfish actors.

Apologies for locking the topic. I've been reading/replying on my phone and must have accidentally fat fingered it. I'm still thinking through the implications of Mike's last post.

me thinks the problem is that there is no way to stop a miner which replaces a memory pool transaction with another one which offers a higher fee.

afaik only transactions in a block (older is better) are safed. all other ones are just maybe's.

but if only a few miners do this (transaction replacement) there is no use at all. you can't be sure that a zero-conf transaction don't get replaced AND you dont have the benefit of nlocktime and transaction replacements.

so i vote for "allow replacing of zero-conf transactions" so it would be possible to build escrow services around it.

The Bitcoin ecosystem consists of more that just miners, and even if miners decided to try to form a cabal to increase inflation merchants, users, and exchanges could all veto their block-chain by simply refusing to recognize it.

I think the policy of which transactions to keep in the memory pool is fundamentally different, because miners can do whatever they like and there's not a whole lot merchants/users/exchanges or other miners can do about it. There's no way to enforce a "first broadcast version of a transaction must be mined" rule, if there was then we wouldn't need the block chain at all.

As for re-writing the blockchain if an after-the-fact, large-fee double-spend is broadcast:  I think that's covered by this case:
Or, in other words, you'd need to be pretty sure that you've got a majority of miners who will cooperate with you to rewrite the block chain. The longer the chain, the harder that will be (because it becomes increasingly likely that one of your co-conspirators mined one of the blocks you want to overwrite).

Suppose there's a transaction for 100,000BTC and several blocks later a double spend with 50,000BTC fee... and by then the 100,000BTC was already spent out to others in smaller amounts.

It only takes 1 or 2 pool miners to have 51%.

(Maybe there should be a maximum fee per transaction--edit: nevermind, not possible)

With a maximum fee per transaction, you throw out the double spend defense you proposed of a recipient countering a double spend by spending the output of a previous transaction completely to fee. There are other ways to get around it too and they involve spamming the blockchain.

Or maybe you should wait 60 blocks before considering a half-a-million-dollar transaction final if you think there is any possibility of a mining cabal trying to do this.

All of this reminds me, I need to clean up my user-defined-checkpoints code for the 0.7 release, so a cabal of merchants and exchanges can get together and decide they will "lock in" an agreed-upon blockchain after 6 (or 60 or whatever) confirmations. I think that would go a long way towards infrastructure for injecting real-world knowledge about who is trustworthy into the block-chain.

He should wait before delivering the goods, but there's no incentive for him to wait to spend the BTC. Actually, he's better off if he does spend it and someone else down the line takes the loss.

What if they break it into 1000 payments of 100BTC, and then 1000 double spends with 50BTC fee?

I see three options for who should get the double spent amount:

1. The first transaction - Currently working OK, although imperfect incentive for miners. Double spend race attack is manageable.

2. The highest fee double spender - Aligned with miner incentive, but rewards double-spending even more.

3. Neither, the miner gets it automatically - Aligned with miner incentive, trumps fee bribe, and removes all incentive to double spend. See https://bitcointalk.org/index.php?topic=76276.0 (https://bitcointalk.org/index.php?topic=76276.0)

Can you remind me how "the miner gets it automatically"?  I think it would be a totally unacceptable change to allow coins to be transferred to a party/script that was not signed by the originator.  i.e. AddrA signed a tx to go to AddrB, but instead the network allows it to be awarded to AddrC.   I don't see how there's even a hint of feasibility in this idea, unless I'm misunderstanding the proposal...

There's also some legit reasons a tx might end up appearing to be a double spend, even though it's not.  Programmatically, it would be impossible to distinguish those cases, and miners would have free reign to eat up any such transactions anyway.

It's in "Defense against double spending" thread https://bitcointalk.org/index.php?topic=76276.0

Signing a second spend authorizes a miner to take it. So don't double spend!

The legit cases are where the outputs are the same, or any non-final. Don't count those as double spends.

Double spend = same input, different outputs.

The problem is that there are classes of changes that miners would want to make which cannot be recognized by a majority of users who will be on lightweight clients (assuming the system continues to grow, of course).

Lightweight clients can't efficiently calculate the size of the coinbase for a block without downloading the whole block and then downloading the dependencies of every transaction in that block, along with the Merkle branches linking them to the relevant block headers (which may also need to be fetched because I think in future lightweight clients will throw away very old headers).

In todays world it's not a big deal because most miners cash out immediately via a small number of exchanges, and if they chose not to recognize a rule change it wouldn't matter how many miners adopted it. But in future if there are lots more merchants and more competition in the exchange space (or even p2p exchanges), then the chances of miners being able to enforce major rule changes like that becomes a lot larger, because lots more users will just follow their new rules - either because they can't efficiently detect the change or because they don't want to deal with a big slowdown of the system.

I think there's enough resistance from other aspects of the system (can't find miners, people mine for ideological reasons, conspiracy would be detected) to ensure this won't happen with the way things are currently set up. But if we switch to a "miners profit is primary no matter what" assumption, the risk becomes much greater.


As long as most people are using the standard rules, actually performing such a transaction-switch isn't so easy. You have to find a miner who is using different rules, and you have to hope that this miner gets the next block. If they don't, you're out of luck. That's a high enough barrier that Finney attacks are likely to be rare in practice.

If you change the standard rules so everyone offers such a service by default, on the assumption that everyone would end up doing it anyway, then it's a self fulfilling prophecy. The attack would become a lot more reliable, so people would do it a lot more, so there's now profit to be had by using the new software, so people would upgrade, and it'd become basically impossible to do any kind of low-latency trade with lightweight clients.


Let's assume a world where mining is incented primarily by fees rather than inflation (as is, people don't usually attach fees anyway). If a transaction that was mined 3 blocks ago is re-broadcast with significantly higher fees, and every other transaction remains the same, everyone will be incented to reset the chain to that point so they have a chance of claiming the higher fee. All the other transactions can just be included in the new blocks being mined so it's no big deal. The co-conspirators who mined the blocks being replaced would lose their inflation, but presumably that's quite low at this point anyway and they can reclaim the fees on any other transactions that they re-include anyway. Once everyone is simultaneously incented to start re-mining from a few blocks back, the fees in all those transactions become up for grabs again so why not do it?

If we assume a low margin mining industry (not necessarily the case yet but it will be eventually), it will cost almost the same amount to mine a block as the block reward (even if the reward is mostly fees).

To mine the last three blocks, the fee increase would have to be at least as much as the total fees in those three blocks (as a proxy for the cost to mine those blocks again) to make it worthwhile. That means that if a transaction is sufficiently large, the receiver will need to wait until the fees/inflation paid since the transaction was confirmed are greater than the amount of the transaction or until the block chain is locked in as Gavin suggested, whichever is shorter.

Even with a conspiracy of 51% of mining power, it would be cheaper to keep mining the existing block chain unless the fee increase is large enough to pay for the mining power to remine previous blocks. Without a 51% conspiracy, you won't be able to remine those old blocks anyway.

ETA: I could be wrong though. Assuming a 51% cabal, there could be profit in taking the fees of the other 49% too. The recipient may want to wait until the fees and inflation paid to miners since her transaction is at least twice the value of all the inputs, in case the transaction involves other recipients and the value to th sender of a double spend is greater than the value oof no double spend to the recipient.

This opens up more cans of worms maybe. If double spenders collude to broadcast multiple double spends to incent miners to remine after delivery of goods because recipients only waited to be safe based on their own transactions, my assumption goes out the window.

I think I have an idea how to make accepting 0-confirmation transactions as safe as it is now and allow transaction replacement mechanics.

Preliminary requirement:

• if a miner has two conflicting transaction where one of them is a normal transaction and the other is multisig then multisig gets priority and goes into the next block.

Regarding the issue whether or not miner would act to maximize his own profit vs benefiting network as a whole, I think there is not enough information yet and we should wait and see what miners will do.

To accept 0-confirmation transaction, multisig transaction should be created, signed by both parties and broadcasted before releasing the purchase. An attacker won't be able to replace first transaction with another that conflicting it, because merchant won't sign second transaction.

EDIT: I am wondering if it's possible to create clearing house using multisig transactions to reduce the risk of accepting 0-confirmation transaction, e.g. a multisig transaction that has to be signed by several major pools

So what do we agree on?

I found this from etotheipi in mailing:


Why can't we have transaction replacement tied with multisignature, that way to replace transaction everyone involved has to explicitly agree on that? To elaborate:

1. Miner accepts multisignature transaction with nLockTime in future into memory pool.

2. Before nLockTime expires a new multisignature transaction comes in, and it has been signed by every private key that was used to sign previous transaction and maybe some more.
The new transaction also has greater sequence num, which is just an arbitrary number put by the one who created transaction (second party won't sign unfavourable transaction with greater sequence num).

3. Miner checks the new transaction and if it satisfies  those two conditions, then the old transaction gets replaced.


From wiki - Contracts (https://en.bitcoin.it/wiki/Contracts):
What is the rational behind implementing independent sequence number change? Why it is important for any participant to be able to issue a valid new version of a transaction independently?

I think "sequence number" must be extra fee for this transaction..

For example, transaction fee is 0.01 BTC + every next transaction will add 0.00001 BTC to it..

This way we can seduce miners to have oldest transaction in pool.

What do you think?

Yeah! it's brilliant idea, isn't it?? We can't avoid total protocol change though, because nLockTime still must be somewhere in transaction, but still...

PS. I assume nLockTime is some block number greater than current one, correct?

Re-activating nLockTime does not require any protocol changes exactly, just a reversion to the original protocol we had before the security scare. I don't agree with any of the arguments for trying to "fix" it at the same, the current system works fine.

There are examples of why you need per-input lock times in the contracts wiki.