Instant TX for established business relationships (need replacements/nLockTime)

[hashcoin]

Yet more reason for replacements/nLockTime to be turned on, you would never need an "account" on mtgox that you had to deposit more than you were going to immediately use into.

In general long-term business relationships can agree to just "settle it in the blockchain later", but still do it in a way that neither can screw the other.
 
1) Do the "standard escrow setup":
    a) Write Tx A w/ output spendable by sig from you AND mtgox, don't sign it yet.
    b) Write Tx B spending Tx A back to you with nLockTime some time in the future and seq number 0.
    c) Hand mtgox both these *unsigned* (don't sign TxA until he has signed TxB), demand he sign them, get them back and sign them, broadcast them.

2) For quick withdraw, mtgox can do the same thing in reverse with you.

3) To start off, Tx B has seq 0 and gives all coins in TxA back to you.  When you need to give mtgox money, you send him a signed replacement of
TxB that is final, and sends some of TxA to him and the rest back to you.  These are all offline, not sent to network.

4) As you need to give more money, you send new replacements for TxB giving more to mtgox and less to yourself.  Again these are all offline.

5) Finally, sometime before the original TxB expires, mtgox should broadcast the last signed replacement you gave him (the one that gives him the most money).
 

In this scheme, money is tied up, but still cannot be spent by the other party without authorization from you.  On the other hand, you can provide that authorization to them instantly offline of the blockchain.

[theymos]

I wouldn't really consider MtGox full-reserve if they did that, since someone could "burn" their deposits.

[hashcoin]

I wouldn't really consider MtGox full-reserve if they did that, since someone could "burn" their deposits.

I don't understand.  Once you have signed a TX and sent it to mtgox, he has the money.  He just chooses not to broadcast it until later, so that rather than paying a TX fee/waiting for every small deposit/withdraw, you only do this when you want to.  You cannot cheat mtgox out of money...

[theymos]

Actually, I thought about this for a long time and I now think it might have some uses.

At first I thought that tx A could be broadcast without signing tx B, which would allow the withdrawer to burn coins. But the site just needs to count BTC as temporarily withdrawn until tx B is signed.

Then I thought that the side sending tx A would have a long time to generate a block and choose any version of tx B they want, ignoring sequence. But they'll actually have only tens of minutes to do this.

The risk still seems unacceptable for most sites. The attacker can't easily use network-based attacks as with regular 0-confirmation transactions, but they still only need to solve one block, and they can try the attack many times without cost until it works. Maybe the method could be used if other security measures were taken, such as delaying USD withdrawals out of exchanges.

[hashcoin]

I think you must be misunderstanding something or my post was not clear because there is no security risk in this scheme.  This is not "slightly less risky instant transactions".  This is indeed "zero-risk" instant transactions, where "zero risk" means the same level of risk as non-instant transactions.  The catch is that the money can only be spent to one person.  Intuitively, double-spending is trivial to prevent if each piece of money is tagged so that it can only go to one person!
Please describe exactly how one could cheat the other if they both follow this scheme.

Here are two subtle points incase you are not understanding why they are crucial:
1) You must get a sig from the other party on txB before you sign txA.   Otherwise, the money could be stuck.
2) The other party should not sign any TxB replacements he receives until he is ready to broadcast the final one.  That is, the TxB replacements are signed by one person (the person paying more money), and then held by the other party.  The other party keeps them to himself until they are ready to settle the balance, at which point he signs that replacement.  Since any update requires BOTH signatures, the first party cannot single-handedly make ANY update without approval from the second party.

I think (2) is what you are missing.  TxA was written so it requires 2 sigs to spend.  So the payer can't just broadcast an earlier version of TxB.
Note the TxB replacements are not increasing in sequence number -- they are FINAL, and not time-locked.

In other words, there will only EVER be TWO valid TX spending TxA:
- The very first one, giving it back to the first person.  This is replaceable and uses nLockTime at say, 30 days in the future.
- The very last replacement sent by the first person to the second.  This is not replacable and is locked immediately.  The second person does not sign any of the others, thus they are never actually valid replacements.

So the second person just keeps a bunch of half-transactions in his pocket, until it gets to say, 5 days before the first TX will expire.  Then he decides to settle the balance, by signing and broadcasting the last half-signed TX he received (the one giving him the most money).  At this point, should they decide to continue the business relationship, they repeat.

[theymos]

Ah, I missed that the fully-signed intermediate versions would be kept private. This would be safe. Great idea!

[hashcoin]

With extra TX script magic this can be done even more efficiently, so that sending a new payment merely requires a hash computation, rather than an ECDSA sig.  (This is a huge difference: a CPU can do about 5M Hash/sec [remember, single hash, not double like mining], but only maybe 500 ECDSA sigs/second).

The scheme is Rivest-Shamir Paywords[1].

The paywords scheme is basically a really efficient way of doing what I suggest above, with hashes instead of signatures.
Say I want to do this scheme with you for $100, and I want to transfer to you in increments of $0.01.

I pick a random message X_0 and hash it 10,000 times, generating X_10000. (i.e., hash X_0 to get X_1, then hash X_1 to get X_2, etc).
I send you the following signed promise:
"If you know a string that hashes to X_10000 after K iterations, you may collect $0.01 * K from me".

Now to pay you I send you X_9999, X_9998, etc.  You need only keep track of the last one, and you can check that X_k indeed hashes to X_k+1.

This doesn't fit quite as nicely into bitcoin unfortunately because it needs TX that can have variable output depending on the script.
You would need to be able to write a script saying something like:
"This tx is spendable with a signature from party B, plus a value Y.  If Y hashes K times to X_10000, then the output is K * something to output B, and rest to output A".

To get an idea of how powerful this is, with this kind of scheme you could include a payment on every packet going over the internet, or all kinds of extreme micro-payments.

[1] http://people.csail.mit.edu/rivest/RivestShamir-mpay.ps

[TierNolan]

"This tx is spendable with a signature from party B, plus a value Y.  If Y hashes K times to X_10000, then the output is K * something to output B, and rest to output A".

You can't have for loops in script, so hashing 10000 times would require that you have 10000 opcodes.

There is a limit on the number of opcodes per script, so it wouldn't be extendable.

To get an idea of how powerful this is, with this kind of scheme you could include a payment on every packet going over the internet, or all kinds of extreme micro-payments.

You have to pay a tx fee to spend coins.  If you have 1000 coins each with value of 0.00000001, then they can't be spent very easily.

You would have to send the transaction with 100 inputs and 1 output.  With the way things are set up, that would cost more than the value of the coins in tx fees.

However, miners might start charging on the basis of CPU time to verify, rather than the length of the transaction.  A verification that only requires hashing could have lower tx fees.

Also, if you don't care to much about double spending (and that seems reasonable for micro-payments), then hashing 10000 times is probably overkill.

You could just create 1 transaction which has 1 input and 1000 micro coins as outputs.  The requirement to spend the outputs would just be to provide a string that hashes to the given hash.

The seller can then combine lots of those coins into a large transaction and protect the output with the standard ECDSA signature system.

[hashcoin]

You can't have for loops in script, so hashing 10000 times would require that you have 10000 opcodes.

There is a limit on the number of opcodes per script, so it wouldn't be extendable.

Right, see where I said "you can't do this in bitcoin now".  There is a more important issue than no loops, namely that output value can't be set by scripts.

You have to pay a tx fee to spend coins.  If you have 1000 coins each with value of 0.00000001, then they can't be spent very easily.

Er no you misunderstood the scheme then.  Take a look again at the OP.  Note that all those TX replacements occur *offline*.  There is only ONE TX ever actually settled in the blockchain.  So in addition to being instant, all of those TXs only end up paying one fee at the very end to settle!

However, miners might start charging on the basis of CPU time to verify, rather than the length of the transaction.  A verification that only requires hashing could have lower tx fees.

Indeed, this is true.  But I think it would be much cheaper, since CPU time is cheaper than permanently adding to the blockchain.

[theymos]

Allowing variable output values would be a pretty major change. It might be worth thinking about, though, since it would solve many problems.

[d'aniel]

"This tx is spendable with a signature from party B, plus a value Y.  If Y hashes K times to X_10000, then the output is K * something to output B, and rest to output A".

You can't have for loops in script, so hashing 10000 times would require that you have 10000 opcodes.

There is a limit on the number of opcodes per script, so it wouldn't be extendable.

Couldn't you just add 10000 more words to the scripting language: OP_SHA256X1, OP_SHA256X2, ... , OP_SHA256X10000?

There is a more important issue than no loops, namely that output value can't be set by scripts.

What problems are introduced by allowing this?  Is it that it would make it too easy to DoS the network?  Could a special exception be made for scripts of this type, since hashing 10000 times is only as difficult as checking a single ECDSA sig?

To get an idea of how powerful this is, with this kind of scheme you could include a payment on every packet going over the internet, or all kinds of extreme micro-payments.

Holy shit.  If this is doable then it'd be insane not to do it, and somebody else surely will.

Tying direct economic incentives into packet routing would be revolutionary for the Internet.  Extreme micro-payments would provide the incentives necessary for wireless mesh networks to form spontaneously, as well as geographically close distributed storage (using this https://bitcointalk.org/index.php?topic=22581.msg304888#msg304888).  They'd incentivise participation in Bittorrent and Tor.  Easily Bitcoin's "killer app" if it's possible.

[julz]

If I understand this correctly, then for the duration of this 'Business Relationship Session' (I'll call it BRS for want of a better term), the merchant will be delivering micro-services because they know they will ultimately be paid - but are unable to access the money for these intermediate spends until settlement of this BRS.

This means that if the exchange rate is volatile - as it is today, the merchant won't know how much value in his relevant fiat currency each spend is worth. 
Presumably, especially if the exchange rate is tumbling, a merchant would want to settle the balance of the BRS very quickly, and immediately establish a new BRS.
Wouldn't this mean that the duration of these things is more likely to be minutes than even hours or days?

Also - if the merchant is a reseller or service aggregator of some sort, they may need to onpay the intermediate spends as they go. Would they need to hold a balance equivalent to all their active BRSs, or could they somehow spend parts of another unsettled BRS? 

These factors suggest to me that a very short settlement time would be the norm. Would all this setup/teardown cause delays, or would the parties be setting up a replacement BRS in advance of settling the previous so that it's seamless? 

Maybe as a merchant who wants to establish long-running BRSs with clients - I would have to establish a separate BRS with some financial provider who allows me to show evidence of BRSs in progress and lock in current exchange rates?

Sorry - these questions are perhaps a bit premature when you're discussing more low level mechanics.. but then understanding the higher level ramifications is surely part of getting the design right.

[d'aniel]

julz,

Even though settlement is not occurring immediately on the block chain, there is never any counterparty risk in these exchanges, so I don't see why anyone should ever feel rushed into "settling the balance of a BRS" (it's always "settled" in the meaningful sense).

If the USD/BTC exchange rate drops then people would just find they've maxed out the BRS faster than they expected, but then they would simply start a new one with a higher limit.  Conversely, if it increases and people find they want to use the resulting excess of value locked up in the BRS for something else, then they can just settle it on the block chain and start up a new BRS with a lower limit.

[dinox]

Really great idea, following this thread!

[ByteCoin]

Allowing variable output values would be a pretty major change. It might be worth thinking about, though, since it would solve many problems.

For future reference, could you please outline the other problems it would solve?

ByteCoin

[theymos]

For future reference, could you please outline the other problems it would solve?

I was referring to the problems solved by hashcoin's "Paywords" scheme. A sender and recipient touches the network once to set up a transfer and once to finalize it. Between those network transactions, they can do transactions between themselves safely, without touching the network at all. They don't have to worry about confirmations or transaction fees on microtransactions, and no ECDSA signing/verification is required.

I'm pretty sure it would work if Bitcoin supported variable values for outputs and loops in script. While variable output values are probably possible to do safely, it's probably too big of a change to ever be implemented in Bitcoin.

[hashcoin]

I was referring to the problems solved by hashcoin's "Paywords" scheme. A sender and recipient touches the network once to set up a transfer and once to finalize it. Between those network transactions, they can do transactions between themselves safely, without touching the network at all. They don't have to worry about confirmations or transaction fees on microtransactions, and no ECDSA signing/verification is required.

I'm pretty sure it would work if Bitcoin supported variable values for outputs and loops in script. While variable output values are probably possible to do safely, it's probably too big of a change to ever be implemented in Bitcoin.

Er, just to clarify, the original scheme, which bitcoin supports now modulo scripts and locktime, also has the property that the people can transact between themselves without touching the network, without needing any confirmations, and without paying any fees except to settle.  That much does not require variable-output TX.  But, an ECDSA sign/verify is required for each payment (offline between the two parties).

The purpose of Rivest-Shamir Paywords is to lower that cost to a single hash computation.  A single hash is reasonable for a payment on every internet packet; an ECDSA sign/verify is not.  This is why OpenSSL uses pubkey crypto for the initial handshake, but after that uses HMACs which are very fast.

[jav]

Really interesting idea! I was thinking that this might be a good technique to combine with a payment processor. Customers would then only have to form a single one of these "business relationship sessions" - namely with the payment processor - and could still pay instantaneously everywhere where the payment processor is accepted. Merchants would accept standard, zero-confirmation transactions from the payment processor on the assumption, that the payment processor is honest.

If the changes to Bitcoin necessary for this would be made, I would probably try to adopt something like this for Instawallet. Combined with the green address technique, that seems to me like a pretty workable solution for instant payments to any number of merchants without the customer having to risk depositing coins in an e-wallet.

[jtimon]

This could be used for decentralized instant POS payments too !!
These escrow accounts could be used to form a web of trust like ripple uses lines of credit.
Imagine A has an account to pay B and B to pay C.
A can pay C instantly through B. But you need to make the payment from A to B, and the one from B to C to occur atomically.
Can this be combined with the technique used to exchange currencies of a different chain to attain atomicity?
I still have to think how.

If so, the instant payment could have multiple hops. Payer -> Intermediary 1 -> ... -> Intermediary n -> Recipient.
This would increase the liquidity of a given payer and the number of payers a merchant can trust.
Maybe even payment processors can be avoided if there's a "trust path" between the payer and the recipient.

[d'aniel]

This could be used for decentralized instant POS payments too !!
These escrow accounts could be used to form a web of trust like ripple uses lines of credit.
Imagine A has an account to pay B and B to pay C.
A can pay C instantly through B. But you need to make the payment from A to B, and the one from B to C to occur atomically.
Can this be combined with the technique used to exchange currencies of a different chain to attain atomicity?
I still have to think how.

If so, the instant payment could have multiple hops. Payer -> Intermediary 1 -> ... -> Intermediary n -> Recipient.
This would increase the liquidity of a given payer and the number of payers a merchant can trust.
Maybe even payment processors can be avoided if there's a "trust path" between the payer and the recipient.

I don't think this is feasible since payment processors would have to tie up bitcoins in so called BRSs with every single one of their clients, and because the same coins can't be used for multiple BRSs.