Topic: TX replacement and nLockTime - page 3. (Read 6870 times)

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.

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

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?

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

Bump...

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

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

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.

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.

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.

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.

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 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 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.

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".

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.

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.

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.

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.

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.

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

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.