Rapidly adjusted micropayments and multisig/P2SH

[blueadept]

So I've been curious about uses for the two-party escrow mechanism enabled by multisignature transactions and P2SH.  I'm interested in replacing Contracts example 7 with something that doesn't require nLockTime or transaction versioning.

As I understand it, a two-party escrow mechanism would work as follows for minimized-trust transactions:

1. Alice wants to buy a widget worth X BTC from Bob
2. Alice creates two public keys, A1 and A2.  Bob creates two public keys, B1 and B2
3. Together, Alice and Bob create a 2-of-2 multisignature address C1 from A1 and B1
4. Alice signs a partial transaction T1 with an input of 2X BTC and an output of 3X BTC to C1 and passes it to Bob
5. Bob adds an input of X BTC to T1, signs it, and broadcasts T1 to the network
5a. The result is that Alice paid 2X BTC and Bob paid X BTC to the address, so they both have a stake in agreeing about how to release the money and griefing/fraud are prevented by both Alice and Bob by making those actions more expensive than playing honestly. In addition, both Alice and Bob are protected from fraud in the initial transaction as T1 is invalid unless both inputs are valid unspent outputs from previous transactions.
6. Bob sends Alice the widget
7. Upon receipt of the widget, Alice signs a transaction T2 from C1 paying 2X BTC to Bob at key B2 and X BTC back to herself at key A2 and passes T2 to Bob
8. Bob signs T2 and broadcasts it to the network, receiving his payment and "security deposit" and sending Alice's "security deposit" back to her

In the event that Alice and Bob can't agree on who should get how much money based on partial/complete nonperformance of the contract, they can both pick an arbitrator Trent, who generates three public keys, R1, R2 and R3.  A new 3-of-4 multisignature address is created for A1, B1, R1 and R2 so that Trent can only spend the money with agreement of either Alice or Bob, and this turns into a third-party escrow situation if the parties desire.  Eventually, some amount is sent to A2, some to B2 and some to R3.

Would this work in rapidly-adjusted microtransactions as well?  For example:

1. Alice wants to buy about 100MB of transfer from a Wi-Fi access point operated by Bob and pay .0001 BTC per 10kB
2. Alice and Bob create a transaction T1 to C1 as in previous steps 1-5, with Alice paying in 2 BTC and Bob paying in 1 BTC
3. Alice signs a transaction T2 from C1 with 1.0001 BTC going to Bob at key B2 and 1.9999 BTC going back to herself at key A2, sending T2 to Bob who does not broadcast it
4. Alice continues to use 10kB of bandwidth at a time, signing a new version of T2 each time with an ever-increasing amount going to Bob and ever-decreasing amount going back to her
5. Alice notifies Bob when she is done, at which point Bob stops providing services to Alice and signs and broadcasts T2, thereby completing the exchange

This would enable such rapidly-adjusted microtransactions without relying on transaction versions or nLockTime, which means they're practical as soon as P2SH is available on the network.

I would like to know whether this would actually work as I described it, as I have some other ideas relying on transactions like this.

Edit: Changed Trent's keys from T1, T2, T3 to R1, R2, R3 so they aren't confused with transactions T1 and T2.

[1714912878]

1714912878

[1714912878]

1714912878

[1714912878]

1714912878

[cbeast]

There have been a couple other threads with more-or-less this idea. Micro-payments make pay-as-you-go seem much less intimidating. I hope it catches on and that Bitcoin fills that niche.

[blueadept]

There have been a couple other threads with more-or-less this idea. Micro-payments make pay-as-you-go seem much less intimidating. I hope it catches on and that Bitcoin fills that niche.

Right, I just wanted to make sure I'm getting it right in the way it'd be implemented because it might matter for the application ideas I have.

ETA: One reason I'm interested in whether this would work is that it would make possible a system similar to what I describe below.

TL;DR version: This would make possible a distributed Ripple-like network where nodes wouldn't have to trust each other because they could pay each other as they go with adjustable transactions.  Such a network would support only transactions denominated in BTC, which would reduce the need for complicated routing/distributed transaction commitment inside the network by eliminating inter-asset trade and allowing any node to trade with any other node without intermediaries.  It could reduce blockchain bloat, increase anonymity, and enable instant payments without having to trust proprietary "banks" or "eWallets" with your money, and due to the collateral requirements of such a network, it could actually increase the BTC-to-fiat exchange rate as it gets more use.

Long version:  Imagine a set of independent "payment processors" that forward payments from their customers to other payment processors' customers and vice versa.

To establish a "connection" (think of a pair of IPSec SAs, one for each direction of flow), two payment processors would decide on a "lifetime" L (or maximum transaction amount before settlement) for the connection.  Then they would establish two transactions as in the framework above, one for payments from processor A to processor B and the other for payments from processor B to processor A.  The collateral from each processor into each P2SH address would be L, so in reality 2L in each direction or 4L in total is locked into the pair of transactions that make up the connection.

A merchant would establish a unidirectional connection (only one transaction, from payment processor to merchant) with her preferred payment processor, and L is set to the expected maximum transaction volume before settlement.  The merchant puts up L BTC as collateral for the ongoing transaction and the payment processor puts up L as well, locking 2L into the unidirectional connection.  Likewise, a customer would establish a unidirectional connection with her preferred payment processor as well, and probably only the customer would put up the expected lifetime amount.

When a merchant requests a payment from a customer, the merchant gives the customer their receiving account information and their payment processor (almost like an e-mail address, merchant@paymentprocessor or something similar, probably identified by a public key), a transaction ID and the amount.  The customer sends a message to their payment processor including the information from the merchant and a signed updated transaction with a higher amount going to the payment processor and a lower amount going back to the customer.  The customer's payment processor then sends a similar message to the merchant's payment processor (assuming they already have a connection) and the merchant's payment processor to the merchant, which then gives the customer their merchandise.

Negotiation of the connections is an important part of the implementation; my first idea would be scaling up L from a multiple of the size of the first transaction to start with, to the maximum total transaction amount in an hour; implementations can also scale L differently in each direction (assuming some processors are more merchant-friendly and some are more consumer-friendly).  Fees can be charged on all sides (payment processors can charge merchants, customers and other payment processors) and while merchants and customers can shop around, it'd be more difficult for payment processors to auto-negotiate fees with each other and guarantee connectivity.  In this idea, I've tried to avoid the hassle of trying to design payment routing (and all-at-once commitment) through more than two payment processors by forcing direct connections between payment processors since unlike Ripple, all transactions would be denominated directly in BTC.

This type of infrastructure would function as almost an overlay network over Bitcoin that could make instant irreversible payments possible, though settlement would take a while longer (at the option of the funds recipient).  It would also reduce blockchain bloat and potentially improve anonymity of transactions with respect to information contained in the blockchain, as the only visible transactions from this network will be aggregated and thus correlating payments from customers to merchants will be impossible without the cooperation of the payment processors (and I'd expect at least some payment processors to pop up as Tor hidden services or eepsites and refuse to log, etc).

One more interesting effect is that merchants, customers and payment processors would all need to hold more BTC (and "lock it up" in ongoing transactions), meaning bitcoins would have value as collateral for such instant bitcoin transactions and this may increase the exchange rate of BTC vs. fiat.

[trout]

the escrow mechanism in the OP looks pretty cool. And it's not from those contracts in 'smart money' examples.

it could be used to make a P2P market.

[Mike Hearn]

Re-activating tx replacement isn't all that hard. It just takes somebody to write unit tests and convince Gavin it won't cause any problems. If you are capable of implementing contracts for wifi payments you are capable of doing that too.

The versioning is useful for the case where the wifi hotspot you were trading with vanishes.

[blueadept]

Re-activating tx replacement isn't all that hard. It just takes somebody to write unit tests and convince Gavin it won't cause any problems. If you are capable of implementing contracts for wifi payments you are capable of doing that too.

Is the only place relevant to transaction replacement in main.cpp, in CTransaction::AcceptToMemoryPool?  I'm not yet as familiar with the Bitcoin code as I'd like to be so I could be wrong about most of the following but if I'm right, there are probably additional changes to be made.

Assuming not all miners agree that this is a good thing and upgrade/patch their systems at the same time, this could be as difficult an implementation as P2SH.  The way I understand it, transaction replacement won't work if nLockTime expires before any miners include the updated transaction in a block and one of the big pools that runs a customized version of the software and hasn't yet implemented the new feature (like Deepbit with P2SH) puts the earliest version of your transaction in a block, thus stealing funds from the recipient.  If you modify Bitcoin to reject as invalid blocks that contain a transaction for which you have a newer version, you risk a fork; either way, I think this involves more effort and community coordination than just writing unit tests and working with Gavin.

This doesn't even take into account some of the other things that people may want enabled beyond just removing the disabling line (currently 496 in main.cpp).  It looks like both CTransaction::AcceptToMemoryPool and CTransaction::FetchInputs should be updated to allow adding new inputs.  In addition, when replacing the transaction, I don't see any code that updates/deletes transactions dependent on the old version of the transaction.

In any case, I'm less interested in Wi-Fi payments (not that I'm disinterested, I think the idea could even be extended to a Wi-Fi mesh network) than applicability to other P2P networks like an overlay payment network described above and networks that let you purchase ad-hoc computing resources such as relay bandwidth, processing time, storage, etc. from the other nodes on the network using micropayments.  At least some of these things are easier than modifying Bitcoin and getting miners to accept the changes.

The versioning is useful for the case where the wifi hotspot you were trading with vanishes.

With the hotspot owner (or other funds recipient) putting their own funds as performance collateral into the P2SH address, they'll have incentive to store the latest version of the transaction and sign/broadcast it eventually to get their own funds back.  Such griefing (intentional or not) is one of the reasons I put that in there.  The way it's structured means you don't have to worry about an unknown peer refusing to sign a multisignature transaction just to prevent you from getting your own change back.

I'm not saying enabling transaction replacement isn't worth it; this is just one scenario where it would be useful.  I'm saying I'm interested in exploring the full potential of P2SH, which we're about to finally have available to us.

[hashcoin]

Why are sequence numbers/replacements needed?  To do this kind of thing securely, redeeming the "micropayments" should require a secret only the person being payed knows, so that the payer may not broadcast it early.  Thus, there should never be a fully valid non-final transaction anyway (the person being payed won't sign any of the other half-signed TXs he got).

[blueadept]

Why are sequence numbers/replacements needed?  To do this kind of thing securely, redeeming the "micropayments" should require a secret only the person being payed knows, so that the payer may not broadcast it early.  Thus, there should never be a fully valid non-final transaction anyway (the person being payed won't sign any of the other half-signed TXs he got).

I think this is to give the vendor a deadline (nLockTime) to broadcast a finalized transaction before losing all the money.  In my scheme, if the vendor disappears, she loses the money that she put up as collateral for finalizing the transaction but the customer also loses her change.  The vendor can always redeem the transaction in the future, and that gives the customer back her change.  In Mike's scheme, only the vendor loses money and it's only the money owed.  The customer gains the money owed and gets her change back; the vendor never puts up collateral.  In my scheme, there's the potential for the permanent loss of money if the vendor loses her key.

[hashcoin]

The way I understand it, transaction replacement won't work if nLockTime expires before any miners include the updated transaction in a block and one of the big pools that runs a customized version of the software and hasn't yet implemented the new feature (like Deepbit with P2SH) puts the earliest version of your transaction in a block, thus stealing funds from the recipient.  If you modify Bitcoin to reject as invalid blocks that contain a transaction for which you have a newer version, you risk a fork; either way, I think this involves more effort and community coordination than just writing unit tests and working with Gavin.

This is why TX replacement seems useless to me.  Either the current TX is already fully valid, in which case some party may broadcast it early.  Or it is not valid, and thus to miners/clients it might as well not exist.

Typically when one "updates" some TX, that update will be to the benefit of one party and detriment of another.  So it seems to me wherever one would use TX replacement, they actually need a 2-signature-required TX so that one of those parties can't go and immediately broadcast it.
 
What I meant is, are you sure you need tx replacement?  The reason I ask is I don't know of any good example that requires TX replacement, and TX replacement semantics are weird anyway for quoted reason.

I suspect I'm missing something or else Satoshi wouldn't have included tx replacement functionality at all.
What is TX replacement being used for?

edit Not articulating question well; to be more precise: why would the bitcoin network ever be interested in knowing/caring about if a TX is updateable/replaceable or not.  Even if it is, the old version is valid and hence must be accepted in a block by clients/miners.  E.g. if an updated TX reduced a fee, a miner could just decide to include the older TX in the block, ignore the update, and that must be perfectly OK.  So it seems to me replacements accomplish nothing.  What am I missing?

From the point of view of a miner/tx verifier, a TX is either valid right now (has signatures for all inputs, nLockTime has passed) or it's not.   If not, it should have absolutely no meaning to me.  If valid, I am free to put it in a block right now.

[blueadept]

The way I understand it, transaction replacement won't work if nLockTime expires before any miners include the updated transaction in a block and one of the big pools that runs a customized version of the software and hasn't yet implemented the new feature (like Deepbit with P2SH) puts the earliest version of your transaction in a block, thus stealing funds from the recipient.  If you modify Bitcoin to reject as invalid blocks that contain a transaction for which you have a newer version, you risk a fork; either way, I think this involves more effort and community coordination than just writing unit tests and working with Gavin.

This is why TX replacement seems useless to me.  Either the current TX is already fully valid, in which case some party may broadcast it early.  Or it is not valid, and thus to miners/clients it might as well not exist.

If a party broadcasts it early, as far as I understand it, nLockTime makes it stay in the memory pool but not make it into a block until nLockTime is expired.  I assume blocks are checked to make sure that the transactions within them don't violate nLockTime (though with the allowance for clock skew in block timestamps, you wouldn't have a guarantee that this is accurate for any smaller an amount of time than the clock skew allowance).

The problem is that even if everyone respects nLockTime, you'd need nearly 100% of the hash power to allow transaction replacement before it's safe to do.  This would necessitate several months of pleading with mining pools; worse, when Bitcoin mining is hopefully more decentralized, it'll require getting hundreds of thousands or even millions of miners to upgrade their Bitcoin software.

Typically when one "updates" some TX, that update will be to the benefit of one party and detriment of another.  So it seems to me wherever one would use TX replacement, they actually need a 2-signature-required TX so that one of those parties can't go and immediately broadcast it.
 
What I meant is, are you sure you need tx replacement?  The reason I ask is I don't know of any good example that requires TX replacement, and TX replacement semantics are weird anyway for quoted reason.

I suspect I'm missing something or else Satoshi wouldn't have included tx replacement functionality at all.
What is TX replacement being used for?

To be clear, my scheme above doesn't require replacements at all.  Mike's scheme requires it.  Mike's scheme requires nLockTime to also be used to prevent the TX from making it into a block until the lock time expires.  The vendor, in the scheme, actually broadcasts the non-finalized transaction with an nLockTime in the future.  The deadline to finalize that transaction is nLockTime; only two versions (the original and the final) are broadcast to the network.

I believe the idea of using nLockTime and transaction replacement in his scheme is to prevent griefing where the griefer allows the customer to send coins to a multisig address, but then never signs any transaction that redeems those coins.  It'd be a free exploit if not for the way Mike had set it up.

Again, in my scheme, neither nLockTime nor transaction replacements are used and it's done exactly as you suggest: there's no finalized transaction until the very end.  The difference is that in my scheme, griefing is prevented by forcing the vendor to put up collateral equal to the amount put up by the customer.  Griefing is still possible but costly, forcing the griefer to lose more money than any individual customer would lose.

edit Not articulating question well; to be more precise: why would the bitcoin network ever be interested in knowing/caring about if a TX is updateable/replaceable or not.  Even if it is, the old version is valid and hence must be accepted in a block by clients/miners.  E.g. if an updated TX reduced a fee, a miner could just decide to include the older TX in the block, ignore the update, and that must be perfectly OK.  So it seems to me replacements accomplish nothing.  What am I missing?

From the point of view of a miner/tx verifier, a TX is either valid right now (has signatures for all inputs, nLockTime has passed) or it's not.   If not, it should have absolutely no meaning to me.  If valid, I am free to put it in a block right now.

You make great point:  it's possible to include the earlier version not only due to the miners not updating their software to accept replacements, but because miners will have two equally valid versions of a transaction and may have an incentive to commit the earlier one.  That's why I said that enabling replacement could create a blockchain fork.  If you're to force the latest version of the transaction to be the only valid one, you have to reject any blocks that uses an earlier version.

Since transaction replacement isn't enabled right now, it would make sense to change the incentives slightly if it's ever re-enabled so that a newly version of a transaction must include higher fees or it'd be invalid.  This would incent miners to both upgrade and to wait until the last possible version of the transaction to commit it.  Then there would also need to be additional restrictions to prevent double-spending by replacing transactions.  All in all, I'm with you on not being sure that transaction replacement is a good idea or even safe to re-enable.

[Mike Hearn]

The way TX replacement was disabled only impacts the memory pool, it doesn't change the block validation rules. I don't think it'd be a big deal for miners to upgrade because the change is relatively small (just delete one line) compared to something much more involved like P2SH where backporting it is harder.

I agree that it'd take a while to roll out (as do any changes to the network rules), but Bitcoin is a long term project. A few months here or there isn't a big deal given that nobody has actually ever implemented any non-trivial contract anyway. Certainly for something as complicated as on-the-fly bandwidth trading you could add back nLockTime support and whilst you write the rest of the software ecosystem required, people will be upgrading. You can measure the utility by broadcasting simple locked transactions to yourself then attempting replacement. Measure how often the first vs second version gets into the chain.

As hashcoin says, tx replacement is indeed designed to be used along with multi-sig outputs. If you look at the contracts that use it on the wiki, you can see that it's most often used to prepare a default/fallback option that closes the contract if one of the parties goes away or stops agreeing to changes in the primary contract.

This isn't only about griefing. Without timelocking, the purchaser of the bandwidth can take back their coins before the provider has had a chance to broadcast the latest version of the transaction, thus they get free bandwidth. That seems like a fatal problem for automated negotiation.

[Gavin Andresen]

RE: tx replacement:

Somebody aught to start experimenting with transaction replacement with testnet-in-a-box.

Put together a test plan, modify the code and try to break it.

Assuming it all works, submit a pull request to enable transaction replacement on testnet (with a pointer to your test plan and results of testing, please).

Then we can start trying to break transaction replacement on testnet; again, assuming no bugs/hacks/issues turn up after "enough" testing, and if there's general consensus that the benefits outweigh the risks, it could be rolled out to the production network.

We just pulled a DoS fix involving filling up memory with orphan transactions; one concern with transaction replacement is DoS (could I fill up the memory pool by spamming "will be replaced" transactions?)

[Mike Hearn]

We just pulled a DoS fix involving filling up memory with orphan transactions; one concern with transaction replacement is DoS (could I fill up the memory pool by spamming "will be replaced" transactions?)

I think nodes shouldn't have any requirement to actually hold a transaction in the memory pool, at least not for a long period of time. Miners will be incentivized to do so for any transaction with a fee: sorting the memory pool by fee or allowing them to be swapped to disk might make sense.

Scaling the memory pool isn't very important right now, but once timelocking becomes common it would become interesting. I don't see why having hundreds of thousands of transctions in the "memory" pool should be a bad thing if the software can handle it in a graceful manner, and there is some incentive to keep them.

For the contractual case, it's usually enough to just have the timelocked transaction around. You don't actually need to broadcast it, unless you see a competitor transaction be broadcast as well. If you notice that you would immediately broadcast the replacement. It's racy but would likely work well enough most of the time.

[hashcoin]

As hashcoin says, tx replacement is indeed designed to be used along with multi-sig outputs. If you look at the contracts that use it on the wiki, you can see that it's most often used to prepare a default/fallback option that closes the contract if one of the parties goes away or stops agreeing to changes in the primary contract.

What I was asking/wondering is where you actually need replacement rather than just locktime.  I don't understand the utility of the TX replacement mechanism.  It seems to me to serve no purpose.

locktime is what is needed for the escrow, not replacements.  In general, if a transaction is going to be "updated" it must not be finalized or else nothing prevents a miner from including it.  Either it should be missing required signatures, or future-dated.  In any case, the first valid TX incorporated into a block gets to spend a given output.

Replacements are pointless because to a miner, a TX is either ready-to-include-in-a-block-right-now, or not.  If not he should just ignore it.  There's no reason to hold invalid TX around.  The party who broadcast the TX should just hold onto it themselves and broadcast it when the time is right.

This confusion comes up again and again and seems to be the reason many people object to enabling locktime, because replaceable TX are hard to reason about.  I agree, which is why I suggest Enable nlocktime only, NOT replaceable TX.  Locktime is easy for everyone to understand: it's just a post-dated check.

If I take a post-dated check to deposit at a bank, they should turn me away and tell me to come back in the future.  They should not hold onto it in their "memory pool" and agree to deposit on that date, provided it is not "updated".

[ByteCoin]

The party who broadcast the TX should just hold onto it themselves and broadcast it when the time is right.

And of course wills are pointless for similar reasons. You should just tell people what you want done with your stuff now you're dead.

ByteCoin

[Mike Hearn]

Bear in mind a replacement must have the same inputs. It's allowed to have different outputs. Perhaps Satoshi can explain better than I can. Here is a quote where he discusses nLockTime:

One use of nLockTime is high frequency trades between a set of parties.  They can keep updating a tx by unanimous agreement.  The party giving money would be the first to sign the next version.  If one party stops agreeing to changes, then the last state will be recorded at nLockTime.  If desired, a default transaction can be prepared after each version so n-1 parties can push an unresponsive party out.  Intermediate transactions do not need to be broadcast.  Only the final outcome gets recorded by the network.  Just before nLockTime, the parties and a few witness nodes broadcast the highest sequence tx they saw.

Replacements are pointless because to a miner, a TX is either ready-to-include-in-a-block-right-now, or not.  If not he should just ignore it.  There's no reason to hold invalid TX around.  The party who broadcast the TX should just hold onto it themselves and broadcast it when the time is right.

Miners have an incentive to keep a transaction that will become valid around so they can include it when it's valid and thus claim the fees.

Replacements are not pointless. You need to have the combination of timelocked transactions and replacement to ensure security in some cases. Look again at the example I gave above. For the wireless access example, if you don't do replacements, then you cannot sell access:

• User makes a transaction of 10 BTC to a 2-of-2 output with the access point. He sends the hash of this transaction to the AP, which then creates a tx that spends the given output back to the user and signs it.
• User gives tx 1 to the AP which broadcasts it, thus locking in the money.
• The AP and user co-operate to resign versions of the second transaction in which the balance between the APs output and the users output is the amount to pay. Because it's just a signature and there's no need to broadcast/wait, the value can be rapidly adjusted, like for every kilobyte of data transferred.
• To be secure this scheme must create the transactions timelocked and use sequence numbers so each adjustment to the value of the contract has a higher version number. Otherwise the user can broadcast the initial payment tx (the one when they hadn't bought much/any bandwidth) before the trade is finalized, thus taking back their money and leaving the AP out of pocket.

Is it clearer now? With replacements the AP doesn't have to worry about the latter scenario. If the user broadcasts the initial payment tx even after payments of greater value were signed, it just broadcasts the last transaction it saw which overrides the users broadcast. The time locking gives a window in which there is time for the network to be presented with newer versions of the same transaction.

[hashcoin]

Replacements are not pointless. You need to have the combination of timelocked transactions and replacement to ensure security in some cases. Look again at the example I gave above. For the wireless access example, if you don't do replacements, then you cannot sell access:

• User makes a transaction of 10 BTC to a 2-of-2 output with the access point. He sends the hash of this transaction to the AP, which then creates a tx that spends the given output back to the user and signs it.
• User gives tx 1 to the AP which broadcasts it, thus locking in the money.
• The AP and user co-operate to resign versions of the second transaction in which the balance between the APs output and the users output is the amount to pay. Because it's just a signature and there's no need to broadcast/wait, the value can be rapidly adjusted, like for every kilobyte of data transferred.
• To be secure this scheme must create the transactions timelocked and use sequence numbers so each adjustment to the value of the contract has a higher version number. Otherwise the user can broadcast the initial payment tx (the one when they hadn't bought much/any bandwidth) before the trade is finalized, thus taking back their money and leaving the AP out of pocket.

Is it clearer now? With replacements the AP doesn't have to worry about the latter scenario. If the user broadcasts the initial payment tx even after payments of greater value were signed, it just broadcasts the last transaction it saw which overrides the users broadcast. The time locking gives a window in which there is time for the network to be presented with newer versions of the same transaction.

The output of the setup TX should require *both* parties signatures to spend.  The user can't broadcst anything himself.  Rather, every so often, the user makes a new TX spending that output, splitting it between himself and the provider.  These are not updates; they are separate TX that happen to all spend the same output in different ways.  The user signs them and then sends to the provider.  Again, the user can't broadcast them because they lack the providers sig.

Now the provider just maintains the user-signed TX giving him the most money(the most recentvone).  When he's ready, the provider takes the most favorable TX he's seen, adds his sign, and then broadcasts.

[kjj]

Replacements are not pointless. You need to have the combination of timelocked transactions and replacement to ensure security in some cases. Look again at the example I gave above. For the wireless access example, if you don't do replacements, then you cannot sell access:

• User makes a transaction of 10 BTC to a 2-of-2 output with the access point. He sends the hash of this transaction to the AP, which then creates a tx that spends the given output back to the user and signs it.
• User gives tx 1 to the AP which broadcasts it, thus locking in the money.
• The AP and user co-operate to resign versions of the second transaction in which the balance between the APs output and the users output is the amount to pay. Because it's just a signature and there's no need to broadcast/wait, the value can be rapidly adjusted, like for every kilobyte of data transferred.
• To be secure this scheme must create the transactions timelocked and use sequence numbers so each adjustment to the value of the contract has a higher version number. Otherwise the user can broadcast the initial payment tx (the one when they hadn't bought much/any bandwidth) before the trade is finalized, thus taking back their money and leaving the AP out of pocket.

Is it clearer now? With replacements the AP doesn't have to worry about the latter scenario. If the user broadcasts the initial payment tx even after payments of greater value were signed, it just broadcasts the last transaction it saw which overrides the users broadcast. The time locking gives a window in which there is time for the network to be presented with newer versions of the same transaction.

The output of the setup TX should require *both* parties signatures to spend.  The user can't broadcst anything himself.  Rather, every so often, the user makes a new TX spending that output, splitting it between himself and the provider.  These are not updates; they are separate TX that happen to all spend the same output in different ways.  The user signs them and then sends to the provider.  Again, the user can't broadcast them because they lack the providers sig.

Now the provider just maintains the user-signed TX giving him the most money(the most recentvone).  When he's ready, the provider takes the most favorable TX he's seen, adds his sign, and then broadcasts.

Unless the provider decides to hold the deposit for ransom by refusing to sign and broadcast until the client pays 50% of the remaining balance...

In Mike's scenario, the client retains control of his money until he has proof that his deposit will be returned.

[Mike Hearn]

Yes, or (not just ransom) due to bugs/incompetence simply goes away.

I think it's important that your phone can just automatically set this up without any intervention on your part, like how a phone roams onto a new cell tower automatically. Otherwise it's not really more convenient than regular wifi. It means there can't be any scope for malicious or messed up providers nuking your money.

Eg, imagine somebody taking an access point that offers a very cheap rate to a bitcoin conference. Lots of peoples phones might try to buy access from it automatically, and after having the multi-sig output be broadcast that AP simply connects you to a page that says "if you want any of your money back, here is a tx you can sign". Such an access point could be hidden in somebodies pocket or bag, you would never find it or know who did it.

[blueadept]

I agree that transaction replacement is useful to prevent coins from getting lost/nuked.  This is why my version of the scheme requires the vendor/provider/AP/etc. to also put up collateral.  It's motivation for both sides to eventually get a transaction signed.  If the two parties don't agree, they both lose money and all our coins end up more valuable.  AP operators would quickly notice if their bandwidth sales software started losing money rather than making it.

[kjj]

I agree that transaction replacement is useful to prevent coins from getting lost/nuked.  This is why my version of the scheme requires the vendor/provider/AP/etc. to also put up collateral.  It's motivation for both sides to eventually get a transaction signed.  If the two parties don't agree, they both lose money and all our coins end up more valuable.  AP operators would quickly notice if their bandwidth sales software started losing money rather than making it.

Why not just stick with the solution that doesn't require anyone to put up collateral?

[blueadept]

Why not just stick with the solution that doesn't require anyone to put up collateral?

The one that doesn't require collateral isn't possible without transaction replacement and I don't have the ability at this point to champion transaction replacement to make it possible.  I mainly started the thread to see if my idea was viable, not to see if it was better than Mike's.  If it is viable, then application developers have a way of doing it without the Bitcoin software having to be modified beyond the current short-term plans.  I do see transaction replacement as being difficult to enable for reasons I stated above, but my C++ is rusty-ish and I'm not very familiar with the code so I could've missed things that answer my concerns with it.

[hashcoin]

Unless the provider decides to hold the deposit for ransom by refusing to sign and broadcast until the client pays 50% of the remaining balance...

In Mike's scenario, the client retains control of his money until he has proof that his deposit will be returned.

The initial TX is designed to handle that; I was discussing what happens after.  The full scheme I originally described here:

https://bitcointalk.org/index.php?topic=25786.0

Note that thread says it uses replacements.  That's a mistake, as I myself was confused about the need for replacements, but later in the thread I mentioned they aren't needed.  The contracts wiki example looks to be copied from my thread, and it looks like they copied my confusion about replacements along with it.

The full protocol, no replacements, no DOS:

1. Write a transaction TXA spending some coins I have to a two-party owner: my key and provider's key.  Don't sign TXA.
2. Write a transaction TXB spending TXA entirely back to myself but with a locktime in the future.  Sign it.
3. Present unsigned TXA and half-signed TXB to provider, requesting they add their signature to TXB.
4. After provider has added signature to TXB, it is now safe to sign TXA.  Sign,Broadcast TXA and hold TXB in a safe place.

Now if I want to give the provider money, I make a new transaction TXB' spending TXA splitting output between myself and the provider, and proceed as I described above.

The point, which makes this protocol easy to reason about, is there are only ever two valid transactions possibly spending TXA.  The very first one, which won't be valid until sometime in the future.  And the very last one, which the provider will sign and broadcast.  Any intermediate TXB' are missing the providers signature and therefore invalid.

Why not just stick with the solution that doesn't require anyone to put up collateral?

There's no known way to do this and it's likely impossible.  That is, simultaneously having instant TX payable to anyone and preventing double-spending.  The intuition/thinking for my scheme is that you can make a tradeoff;  if Alice is willing to temporarily mark some of her coins as "this coin may only be spent to Bob for the next 5 days", then Bob may safely accept such coins with zero confirmations, without even broadcasting it to the network, because he can be sure there isn't some other TX spending the same coins to someone else.  But this is only possible if Alice really can't spend the coins to someone else, i.e., they are "locked up" for a bit as collateral.

[hashcoin]

Also to address the OP scheme: my scheme doesn't need replacement either.  What your scheme is trading is, having both parties put up collateral in exchange for not requiring nlocktime.  It's an interesting idea, both ways seem to have some advantages and disadvantages.  I was aiming to minimize collateral but this alternate scheme might have some merits.

The scheme is exactly the same after initial setup, it's just TXA is slightly different.  It would go like this:

1.  I write a transaction TXA with two inputs and one output.  The output is two-party multisig with my key and providers key.  But rather than just my coins, TXA now has an input from the provider too.  So X coins from me, Y coins from the provider.
2. I write TXB spending TXA splitting the coins back up, X to me and Y to you.
3. I sign my halves of TXA and TXB and send them to provider.
4. Provider, seeing TXB gives him a way to get his coins back nomatter what, signs TXA and gives it back to me.  He keeps the half-signed TXB safe.

Now to pay, I make new transactions TXB' spending TXA as before, except adjusting the split from X me Y you to X-1 me, Y+1 you etc.

Now to settle, provider broadcasts something spending TXA.  Presumably, he will broadcast the one giving his output the most.

Since provider saw TXB before signing TXA, user can never lockup providers coins.

The provider, however, can lock up both parties coins.  I.e., the provider may  lock up X coins of the user forever if he's willing to lockup Y of his own coins forever.

[Andrew Vorobyov]

Also to address the OP scheme: my scheme doesn't need replacement either.  What your scheme is trading is, having both parties put up collateral in exchange for not requiring nlocktime.  It's an interesting idea, both ways seem to have some advantages and disadvantages.  I was aiming to minimize collateral but this alternate scheme might have some merits.

The scheme is exactly the same after initial setup, it's just TXA is slightly different.  It would go like this:

1.  I write a transaction TXA with two inputs and one output.  The output is two-party multisig with my key and providers key.  But rather than just my coins, TXA now has an input from the provider too.  So X coins from me, Y coins from the provider.
2. I write TXB spending TXA splitting the coins back up, X to me and Y to you.
3. I sign my halves of TXA and TXB and send them to provider.
4. Provider, seeing TXB gives him a way to get his coins back nomatter what, signs TXA and gives it back to me.  He keeps the half-signed TXB safe.

Now to pay, I make new transactions TXB' spending TXA as before, except adjusting the split from X me Y you to X-1 me, Y+1 you etc.

Now to settle, provider broadcasts something spending TXA.  Presumably, he will broadcast the one giving his output the most.

Since provider saw TXB before signing TXA, user can never lockup providers coins.

The provider, however, can lock up both parties coins.  I.e., the provider may  lock up X coins of the user forever if he's willing to lockup Y of his own coins forever.

Seems as a very nice idea if we are talking about joint participation in collateral. txB can be 2-of-3 with 3rd party involved in case of dispute resolution ( provider\client was hit by bus)

[blueadept]

The full protocol, no replacements, no DOS:

1. Write a transaction TXA spending some coins I have to a two-party owner: my key and provider's key.  Don't sign TXA.
2. Write a transaction TXB spending TXA entirely back to myself but with a locktime in the future.  Sign it.
3. Present unsigned TXA and half-signed TXB to provider, requesting they add their signature to TXB.
4. After provider has added signature to TXB, it is now safe to sign TXA.  Sign,Broadcast TXA and hold TXB in a safe place.

Now if I want to give the provider money, I make a new transaction TXB' spending TXA splitting output between myself and the provider, and proceed as I described above.

The point, which makes this protocol easy to reason about, is there are only ever two valid transactions possibly spending TXA.  The very first one, which won't be valid until sometime in the future.  And the very last one, which the provider will sign and broadcast.  Any intermediate TXB' are missing the providers signature and therefore invalid.

Currently, how would the network handle a transaction like TXB where nLockTime isn't for some time in the future? If you perform a few "instant" transactions by signing later versions of TXB and then broadcast the original version to the network, is the provider guaranteed that broadcasting her non-timelocked version will replace the timelocked version?

Also, I like your modification of my OP scheme that prevents the user from locking up the provider's coins.  I'm probably less worried about a provider locking up coins (losing reputation and money with each such event is bound to add up for providers) than about hordes of users locking up the coins of a merchant they don't like.

[kjj]

But if you are putting nLockTime back into the system, why not sequence numbers too?  And why should the provider have to wait out the lock on TxA to collect his earnings?  Wouldn't the lock make more sense on the transaction that can be replaced than on the transaction that is fixed?

[blueadept]

Seems as a very nice idea if we are talking about joint participation in collateral. txB can be 2-of-3 with 3rd party involved in case of dispute resolution ( provider\client was hit by bus)

True.  Also, instead of doing it that way (where you always have to do 2-of-3), you can make it 2-of-2, and both parties pre-sign but don't broadcast a transaction to a 2-of-3 address including an arbitrator.  That way, in case of catastrophe or otherwise, either party has the option to take it to an arbitrator at any time without having to involve the arbitrator from the start.  The extra transaction fees are then only paid when there's an actual conflict and will be smaller than the fees for arbitration, and the blockchain may be less bloated assuming arbitration isn't used so often that the extra transactions take more space than having every such transaction add a 3rd key.

Also, when 2-party escrow disputes go to arbitration, 3-of-4 addresses may be useful to prevent the parties from accepting the arbitrator's decision but signing off on it themselves and cutting the arbitrator out of her fees.  I don't think that's possible with P2SH since AFAICT, its max is n-of-3.

But if you are putting nLockTime back into the system, why not sequence numbers too?  And why should the provider have to wait out the lock on TxA to collect his earnings?  Wouldn't the lock make more sense on the transaction that can be replaced than on the transaction that is fixed?

I thought nLockTime is already enabled, but transaction replacement is not?

[Andrew Vorobyov]

Also, when 2-party escrow disputes go to arbitration, 3-of-4 addresses may be useful to prevent the parties from accepting the arbitrator's decision but signing off on it themselves and cutting the arbitrator out of her fees.  I don't think that's possible with P2SH since AFAICT, its max is n-of-3.

I don't get it... can you elaborate? give me use case

[hashcoin]

Currently, how would the network handle a transaction like TXB where nLockTime isn't for some time in the future? If you perform a few "instant" transactions by signing later versions of TXB and then broadcast the original version to the network, is the provider guaranteed that broadcasting her non-timelocked version will replace the timelocked version?

Also, I like your modification of my OP scheme that prevents the user from locking up the provider's coins.  I'm probably less worried about a provider locking up coins (losing reputation and money with each such event is bound to add up for providers) than about hordes of users locking up the coins of a merchant they don't like.

In my scheme TXB should never be broadcast, unless no payments were made.  The provider must broadcast TXB' long before TXB is valid to be safe.  In that case TXB will be rejected like any other doublespend.

[hashcoin]

But if you are putting nLockTime back into the system, why not sequence numbers too?  And why should the provider have to wait out the lock on TxA to collect his earnings?  Wouldn't the lock make more sense on the transaction that can be replaced than on the transaction that is fixed?

The provider never needs to wait.  TXB is timelocked, but no TXB' are.

The user must wait until either the deadline or the provider to close out early.

[blueadept]

Also, when 2-party escrow disputes go to arbitration, 3-of-4 addresses may be useful to prevent the parties from accepting the arbitrator's decision but signing off on it themselves and cutting the arbitrator out of her fees.  I don't think that's possible with P2SH since AFAICT, its max is n-of-3.

I don't get it... can you elaborate? give me use case

Customer and vendor decide they hate each other's guts and go to arbitrator to solve it.  The arbitrator comes up with a solution they can both live with.

If the funds are behind a 2-of-3 lock, the customer and vendor can then sign a version of the transaction that gives the arbitrator no fees but splits the transaction the way the arbitrator has decided.

If the funds are behind a 3-of-4 lock with the arbitrator having 2 keys and the customer and vendor each having 1 key, the arbitrator must consent to having that money sent anywhere and must have the agreement of at least one party in the dispute.  I'd say this is exploitable by the arbitrator to maximize fees by colluding with either customer or vendor to get them to bid up fees against each other but this is easily fixable by ensuring the arbitrator has a standard fee schedule.  Since all such transactions are public due to being in the blockchain, the arbitrator can show its history of sticking to the fee schedule to demonstrate that it does not accept bribes.

[blueadept]

In my scheme TXB should never be broadcast, unless no payments were made.  The provider must broadcast TXB' long before TXB is valid to be safe.  In that case TXB will be rejected like any other doublespend.

Is there specific documentation about how nLockTime is handled?  Because if the customer does broadcast (and possibly continues to broadcast) TXB before the provider broadcasts TXB', there is a chance of TXB' never making it to miners' memory pools.

Basically, I'm saying that I'm not sure how (or even if!) nLockTime is currently implemented and that would affect the security of both this scheme and my dominant assurance contract scheme.

[hashcoin]

In my scheme TXB should never be broadcast, unless no payments were made.  The provider must broadcast TXB' long before TXB is valid to be safe.  In that case TXB will be rejected like any other doublespend.

Is there specific documentation about how nLockTime is handled?  Because if the customer does broadcast (and possibly continues to broadcast) TXB before the provider broadcasts TXB', there is a chance of TXB' never making it to miners' memory pools.

Basically, I'm saying that I'm not sure how (or even if!) nLockTime is currently implemented and that would affect the security of both this scheme and my dominant assurance contract scheme.

TXB is invalid until the date, so miners should just ignore it.

If memory pool is buggy and miners are keeping TXB, then some subset of miners must run a fixed version.  Nomatter what, TXB can't get into a block, and even miners holding TXB must drop it if they see a block with TXB' mined by someone else.

So worst case, timelock period must be longer and provider must broadcast TXB' early enough that a patched miner will find a block before TXB goes live.   E.g.  if only 5% of miners are patched, and provider broadcasts 20 blocks before deadline, he has a roughly even (actually 1/e) chance of losing.   For strong security, he should aim for a e^-k probability of loss for k=80 or so.  He can do that by leading by k times as long.

(Obviously since block times are stochastic, the analysis is a bit more but you get the idea)

[Mike Hearn]

The full protocol, no replacements, no DOS:

1. Write a transaction TXA spending some coins I have to a two-party owner: my key and provider's key.  Don't sign TXA.
2. Write a transaction TXB spending TXA entirely back to myself but with a locktime in the future.  Sign it.
3. Present unsigned TXA and half-signed TXB to provider, requesting they add their signature to TXB.
4. After provider has added signature to TXB, it is now safe to sign TXA.  Sign,Broadcast TXA and hold TXB in a safe place.

Signing TXA changes its hash, which invalidates the connection on TXBs input. So you can't do that.

What you can do is sign TX A and then send only the hash to the provider.

The point, which makes this protocol easy to reason about, is there are only ever two valid transactions possibly spending TXA.  The very first one, which won't be valid until sometime in the future.  And the very last one, which the provider will sign and broadcast.  Any intermediate TXB' are missing the providers signature and therefore invalid.

The bandwidth purchaser can continue signing and adjusting TXB' until they decide they are done, and then broadcast the first TX B, the one that spends everything back to themselves with a lock time. It enters the memory pool and won't commit for some time, but because there are no replacements, that doesn't matter. The buyer has taken back their coins.

For this protocol to work, the access point must be able to override the users broadcast transaction.

TXB is invalid until the date, so miners should just ignore it. If memory pool is buggy and miners are keeping TXB, then some subset of miners must run a fixed version.

The semantics of nLockTime are that transactions that have it set are kept in the memory pool until that time is reached. Double spends against that transaction are dropped. That's the point of the feature - Satoshi designed timelocked transactions to be replaceable.

You can't just handwave this away and say well, the software should be changed, because if you're going to change all the nodes behavior you might as well just re-activate tx replacement and be done with it.

[hashcoin]

The full protocol, no replacements, no DOS:

1. Write a transaction TXA spending some coins I have to a two-party owner: my key and provider's key.  Don't sign TXA.
2. Write a transaction TXB spending TXA entirely back to myself but with a locktime in the future.  Sign it.
3. Present unsigned TXA and half-signed TXB to provider, requesting they add their signature to TXB.
4. After provider has added signature to TXB, it is now safe to sign TXA.  Sign,Broadcast TXA and hold TXB in a safe place.

Signing TXA changes its hash, which invalidates the connection on TXBs input. So you can't do that.

What you can do is sign TX A and then send only the hash to the provider.

This should be doable with proper OPCODESEPARATOR.

The bandwidth purchaser can continue signing and adjusting TXB' until they decide they are done, and then broadcast the first TX B, the one that spends everything back to themselves with a lock time. It enters the memory pool and won't commit for some time, but because there are no replacements, that doesn't matter. The buyer has taken back their coins.

For this protocol to work, the access point must be able to override the users broadcast transaction.

I see now why you argue replaceable TX are needed.  I'd argue this memory pool policy is a bug.  Fortunately, its in miners incentives to fix it (get fees others wouldn't), and as mentioned above, only a small fraction need make this change.  Miners should greedily pack whatever they can into blocks, not wait on other TX.

I can wave it away, because as I said, only a small fraction need make this change.  That memory pool policy makes no sense: those same miners who are rejecting TXB'  absolutely MUST accept a block that contains a TX conflicting with it.  So such a policy puts oneself at a disadvantage.

[blueadept]

The semantics of nLockTime are that transactions that have it set are kept in the memory pool until that time is reached. Double spends against that transaction are dropped. That's the point of the feature - Satoshi designed timelocked transactions to be replaceable.

You can't just handwave this away and say well, the software should be changed, because if you're going to change all the nodes behavior you might as well just re-activate tx replacement and be done with it.

If this is the case, then my dominant assurance contract scheme also needs TX replacement to work.  Without it, the contributors can just broadcast the timelocked transaction and have the vendor's collateral for free when nLockTime expires regardless of whether the vendor can get enough contributions to make the contract succeed.

[Mike Hearn]

This should be doable with proper OPCODESEPARATOR.

OP_CODESEPARATOR is a holdover from a previous buggy design, it was an implementation detail of how scripts were run (not intended to be actually placed in a tx).

It isn't usable for the same reason - inserting a signature to a transaction changes its hash and thus invalidates any other transactions that depended on it.

I see now why you argue replaceable TX are needed.  I'd argue this memory pool policy is a bug.

Well, you can certainly argue for alternative designs but Satoshi designed it to work this way, the software is working as designed, therefore it's not a bug.

I can wave it away, because as I said, only a small fraction need make this change.  That memory pool policy makes no sense: those same miners who are rejecting TXB'  absolutely MUST accept a block that contains a TX conflicting with it.  So such a policy puts oneself at a disadvantage.

Bitcoin isn't completely resistant to miners that don't care about the wider ecosystem. For instance nothing stops you claiming the inflation even if you don't ever include any transactions. Not validating transactions is certainly cheaper than doing so, but we see that miners generally do it anyway.

If you wanted to allow time locked transactions to not be kept in the memory pool, you would have to explain why your design is better than Satoshis. I'm not seeing it - the only rationale presented for no-replacement based protocols is that re-activating tx replacement would take some work, but it's not any more work than changing the rules around nLockTime.