Decentralized networks for instant, off-chain payments

[blueadept]

I've written up a rough draft of an idea for decentralized networks allowing instant, off-chain payments.  The networks would use the block chain for settlement, but use chained micropayment channels for payment clearing.  I used constructs invented/described by Mike Hearn, hashcoin, cjp, Meni Rosenfeld, retep and others in the idea.  The network would utilize two-phase commit of a payment across a chain of micropayment channels through multiple intermediary nodes.

The write-up is here, as a draft under my Wiki user page:

https://en.bitcoin.it/wiki/User:Aakselrod/Draft

UPDATE

Proof-of-concept here:

https://github.com/aakselrod/libtxchain-java

[jim618]

I must admit I don't understand all the details fully, but this looks pretty interesting.

At some point we are going to want to 'tally up' smaller transactions and only commit to the blockchain the totals. The space in each block is just too valuable to have every last transaction in.

I will have to go through it a couple of times with a strong cup of coffee !

:-)

P.S like the way you clearly credit other authors for what they've done previously.

[blueadept]

Thanks for reading it!  I apologize if anything is unclear; this is a very rough draft.  Hopefully discussion on the forum will help me refine it.  Please give me any thoughts you have or ask any questions as this will help me refine both the ideas and my writing.

None of the ideas are mine originally.  I pulled together lots of other peoples ideas into a somewhat cohesive system.  Notably, I needed to pull together examples 5 and 7 from the contracts page (there's no 6, by the way!) to allow for two-phase commit across a chain of micropayment channels.

[markm]

On first read I don't see any obvious problems with it.

Hopefully Mike Hearn will give some feedback on it.

-MarkM-

[jgarzik]

Good stuff.  Let's see a demo

[grau]

https://en.bitcoin.it/wiki/User:Aakselrod/Draft

Great stuff! I need time to digest, but already see it is worth of the effort.

[cjp]

Thanks for giving me credit. 

I've only given your concept a very quick look and I don't know exactly yet what you propose. Can you give a summary of the differences with my concept?

I'm currently implementing my own concept, in a very simplified form so I can show a prototype as soon as possible (I think it'll take a couple of months). I want to know whether it's worth to include your ideas. Right now, my code (it's on GitHub) contains little more than low-level stuff like sending cryptographically signed messages between nodes, so there's still some room for design changes.

[blueadept]

cjp, the main difference between my proposal and yours is how commits are done across shared property links.  I've proposed a way to commit atomically across a chain of participants while relying on Bitcoin-based constructs for trust-free (or trust-minimized) consensus about whether a payment has been committed or not.  The payment is fully committed only when the preimage of its commitment hash is published.  The preimage of the hash is necessary to redeem any outputs signed for the payment throughout the whole chain.

One of the things that makes my solution scale worse than yours is the unidirectionality of micropayment channels.  However, in reading over your proposal again, I've come up with a simple way to reverse them, which should make my proposal closer to yours (still with the improvement of atomic commit) in terms of both functionality and scalability.  I'll write it up below and, when I get a chance, update the draft.

The directionality of the micropayment channel means that transaction replacement is simple:  the sender signs over ever-increasing amounts to the recipient.  This means the initial, fully-signed anti-DoS transaction (initial version of T2) as in Mike's wireless AP example is fully signed by both sender and recipient with a locktime set in the future, and the recipient has incentive to sign and broadcast the latest version of the transaction.  This is implementable on the network as soon as most of the network, and especially most of the hash power, is using 0.8 code which treats non-final transactions as non-standard.  Only one locktime is used and only one final transaction is ever signed by the recipient and broadcast.

Now imagine a more complicated situation, where the AP is replaced with your bank.  You want to be able to receive your paycheck, tax refund, what have you.  You also want to make payments.  And you don't want to pay blockchain fees every time you get a paycheck.  However, imagine the bank signs a version of T2 decrementing how much you're sending to the bank and incrementing how much you get back by the amount of your paycheck.  You can't take advantage of this yet; however, as time goes on and you sign over more and more money back to the bank with each purchase, you have ever-increasing incentive to just sign and broadcast the earlier version of T2, taking back your paycheck from the bank after you've spent it.

By design, transaction replacement is intended to make this happen; however, the original transaction replacement design doesn't have the appropriate incentives for miners to only accept the latest version of a transaction.  The way to fix that is when one of the parties has an incentive to cheat, that party's preferred transaction version's nLockTime should be later than the most recent version's.  The fees could also be increased, but this is less important than lowering nLockTime so that the most recent transaction version has longer to get into the block chain than previous versions.

While transaction replacement as designed isn't fully enabled, nodes using 0.8 code have enabled de facto transaction replacement by treating non-final transactions as non-standard, which keeps them out of the miners' memory pools.  So the solution is not to enable actual transaction replacement on the network, but to do the following three things for newer versions of transactions where the incentive for another party is to use an older version, in descending order of importance:

• Reduce nLockTime
• Increase the per-KB fee
• Increment the transaction version in case by-design transaction replacement is enabled between now and the closest nLockTime

So imagine Alice is an end-user that gets salary and spends money on rent and groceries and Bob is her bank.  Alice's typical salary payment is 50 BTC per week.  Alice gets her first payment through the blockchain, and sets up a micropayment channel as in the example AP scheme with Bob.  The nLockTime for the initial version of T2 is set to a block number expected to be a year (52 weeks) in the future.

Alice then proceeds to spend all of her money on rent and groceries (she lives in an expensive city) using the scheme proposed in my proposal draft.  However, a slight adjustment is that the nLockTime on all of the transactions Alice signs over is a block number 51 weeks in the future.  In the end, Bob has a version of T2 signed by Alice with an output to Alice for 0 BTC (or no output to Alice at all) and an output to Bob for 50 BTC, with nLockTime 51 weeks in the future.

Now it's pay day.  Bob sends Alice a new version of T2 with nLockTime set to a block expected to be 50 weeks in the future, 50 BTC going to Alice and 0 BTC going to Bob.  Then Alice can once again spend that money through the week, continuing to sign over ever-increasing amounts of money to Bob with versions of T2 having nLockTime of a block expected to be 49 weeks in the future.  This way, Bob is sure he can get his most recent versions of T2 confirmed before Alice can redeem the older version more favorable to her.  Alice spends all her money, and hits another pay day.  Bob now signs another version of T2 to her with nLockTime 48 weeks in the future; Alice can now spend through Bob using an nLockTime 47 weeks in the future.

The concept can be extended to a fully bi-directional payment channel, where each transaction version has an earlier nLockTime; however, it's more efficient (fewer nLockTime changes means the channel can live longer) to make the channel reversible only as necessary.

This is the basic concept, though not necessarily well-worded.  It can greatly reduce the need for micropayment channel setup transactions in the block chain for end users; it also makes decentralization cheaper by reducing the need to renew micropayment channels between intermediaries.  I'll describe it a little bit more clearly and integrate it fully into the draft with new scalability calculations for easier reading.

[cjp]

The payment is fully committed only when the preimage of its commitment hash is published.  The preimage of the hash is necessary to redeem any outputs signed for the payment throughout the whole chain.

What do you do when the preimage is never published? Do you consider it "undecided" forever? Then the expiring of nLockTime is your only escape, which is a long time, especially if you have a lot of bitcoins stored in a "micropayment channel". This risk applies to all participants in the payment chain, so in order to minimize their own risk, people won't be prepared to route others' transactions, except for high transaction fees or some form of "insurance". I doubt whether "minimum trust" insurance is possible without messing up something else.

I don't know whether you were considering "aborting" a transaction after some time-out, long before nLockTime, but that is typically vulnerable to abuse. For instance:

Mallory creates a "sending" and a "receiving" micropayment channel with different parties, who he expects have only very indirect contacts through the network. He then creates a payment to himself, but doesn't send the preimage until the very last moment before the time-out. On the receiving side he receives the payment, since that link was not yet timed out, but due to network delays the preimage doesn't reach him on his paying side before the time-out happens. So, on that link, he can claim that the payment was aborted because of a time-out. The result: Mallory receives, but doesn't have to pay. For some unlucky random other person in the chain it's the other way around. This won't always work, but Mallory can try this as often as he likes, so even a very small success rate is good enough to make this feasible.

If, on the other hand, you really want to wait for nLockTime, then this really allows for an easy DoS mode: make lots of transactions where you never publish the preimage. This is especially true since in your concept an "undecided" transaction locks an entire micropayment channel: you can not have multiple "undecided" transactions in progress on the same link.

[blueadept]

cjp, thanks, this is exactly the kind of discussion I was hoping for.

Obviously I'd considered rollback, but not deeply enough.  I also didn't think to include rollback mechanisms in the draft I wrote, despite having thought about them.  And you're right:  in a scenario where a payment gets stuck, not only does a micropayment channel get locked until nLockTime expires but the entire chain of micropayment channels involved in the payment gets locked.

Since we now have reversible micropayment channels, we can roll back fairly simply: in reverse order to the payment flow (from the payee node all the way back to the payer node), each micropayment channel is reversed for one payment back to the sender.

For example, Alice wants to pay Bob.  Alice has a micropayment channel to Carol and Carol has one to Bob.  Bob generates a random number, hashes it to get the payment's commitment hash and gives the commitment hash to Alice.  Alice signs a new transaction version, with nLockTime 50 weeks in the future, to Carol.  Carol signs a new transaction version, with nLockTime 50 weeks in the future, to Bob.

For whatever reason, Bob changes his mind and says "Alice, I'd rather get paid in silver dime cards, so I'm going to roll back this transaction instead of fully committing it."  Bob reverses his micropayment channel to Carol by signing and sending her a new version of T2 in which the amounts allocated to Carol and Bob are the same as they were prior to the transaction Bob is rolling back; however, the nLockTime is set to 49 weeks in the future.  Carol then does the same to Alice, and the transaction is considered rolled back.  Even if Bob at some point publishes the preimage, nothing bad can happen as the new version of T2 for each micropayment channel can be committed to the block chain a week before the version of T2 that has the preimage.

I believe this mechanism would stop Mallory from being able to take someone else's money in a scenario like yours, where she generates the preimage and tries to trick intermediaries into halfway rolling back a payment flow in order to extract money from one of them.  Since Mallory would initiate the payment, if one of Mallory's nodes refuses to roll back to an earlier node in the path hoping to profit from a half-rolled-back transaction, the initial micropayment channel through which she initiated the payment would also not be rolled back and she'd be paying herself when she eventually published the preimage.

If Mallory is just after DoS and wants to lock micropayment channels, she would need only a node that participates in a payment flow.  If Alice tries to pay Bob through Carol, which is really Mallory, and Mallory doesn't forward the payment to Bob, then Mallory has locked the micropayment channel between her and Alice.  Mallory can't redeem the money, nor her risk deposit, without the preimage of the payment's commitment hash.  She can either publish the transaction after nLockTime expires and lock Alice's - but also her own - money permanently, or she can wait until Alice publishes the initial version of T2 and lose whatever money was previously spent through the micropayment channel that should be hers.  The solution is to have risk deposits on both sides of the micropayment channel to provide disincentive to locking money permanently, and never spend so much in one direction on a micropayment channel that it reduces the other peer's risk deposit.  This way, it's expensive to perform DoS.  Beyond the risk deposit loss, Mallory would have to spend enough time and money on establishing connections that would put her in the middle of payment flows to even make a DoS possible, and then she would have to sacrifice her risk deposits to actually perform it.

One more possibility is to make each output of T2 redeemable EITHER with the recipient's key AND the preimage of the payment commitment hash, OR with BOTH of the keys for the micropayment channel.  This would make it possible to unlock money that would otherwise have been permanently locked, but may open the concept to ransom-driven DoS.  I'm not sure it's a great solution, but it could be useful depending on the desired trade-offs.  In either case, there's nothing wrong with implementing it as an option and letting individual nodes decide whether they want to use it or not.  In such a case, it'd be possible to tell whether an output was redeemed with both keys or with a key and a hash preimage, so that data could be used for reputation purposes.  Note that rollback versions of T2 transactions wouldn't need payment commitment hashes in them as the rollback doesn't need to happen atomically, so we can tell post-rollback versions of T2 from post-payment versions of T2 in the block chain and use that for reputation as well.

One more thought:  if this concept stands up to further analysis, it'd be best to implement it for a distributed instant micropayment solution first.  This way, each micropayment channel could be about 1 BTC in size, which could handle hundreds of nickel-sized (in USD terms) transactions before having to switch directions, and thousands before having to roll over on the blockchain.  Instead of using bigger channels between peers, we should use more channels between more peers so that we can route around DoS attempts and other bottlenecks.  As the value of a BTC grows and the block size's upward pressure on transaction fees increases, the network could evolve from a micropayment network to a retail payment network without having to increase the channel size.

Good stuff.  Let's see a demo

jgarzik, I won't have any time to code one until at least June.  If no one else does it before I do, I will do my best this summer to come up with something.

[Peter Todd]

Cool! Also I'm seconding jgarzik's demand to see a demo. 

[jgarzik]

FWIW, I've been talking on IRC about a decentralized network of bots (numbering 3, 5, or 7, not large numbers) that would facilitate off-chain transactions, escrow, auctions, etc.

Check out the #bitcoin-dev logs from last night.

[Mike Hearn]

This is great work. I think a network of nodes with channels between them has been proposed before, or at least I remember talking about it, but nobody has gone into as much depth as you have. The 2-phase commit is a neat extension.

I was a bit confused by your description of channels as "uni-directional". You realize that the amount of value transferred from Alice to Bob can go down as well as up, right? I don't see why you need to create them in pairs.

The main issue I see is the need to constantly have some coins allocated to the intermediaries - regular Bitcoin payments require no such pre-commitments. Of course this is an issue with the entire concept of payment channels (they are not necessarily micropayment sized), but for most micropayment applications the amount of money you lock up isn't that big and the channel can close fairly quickly. Deciding how much to allocate could be rather tricky. For routing of micropayments around it wouldn't matter so much and that may be the most optimal application.

I wouldn't bother trying to come up with ways to work around the networks current limitations. We know what we need to do to reactivate transaction replacement and make non-final transactions standard again. If you don't want to do that, you can (and should) always prototype on the testnet where I think IsStandard is disabled and tx replacement is enabled.

You would need to consider how peers can discover each other. Even if routing data can be extracted from the block chain, the protocol requires direct communication between all parties (ie, TCP connections). IP addresses change. One possibility is to require all participants to use Tor and then embed your hidden service key in a transaction. That way you get authentication, encryption and privacy for free. This boils down to using (abusing?) the Tor HSDir servers as a secure rendezvous mechanism. The short key hash (onion address) can be added to the channel transactions using OP_DROP. Note that whilst the Tor protocol is very slow/heavy for connecting, there is a proposed optimization for the case where participants don't actually care about being hidden:

https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/ideas/xxx-encrypted-services.txt

In many cases these intermediaries wouldn't care about being hidden, so that can make things faster.

[jgarzik]

You would need to consider how peers can discover each other. Even if routing data can be extracted from the block chain, the protocol requires direct communication between all parties (ie, TCP connections). IP addresses change. One possibility is to require all participants to use Tor and then embed your hidden service key in a transaction. That way you get authentication, encryption and privacy for free. This boils down to using (abusing?) the Tor HSDir servers as a secure rendezvous mechanism. The short key hash (onion address) can be added to the channel transactions using OP_DROP. Note that whilst the Tor protocol is very slow/heavy for connecting, there is a proposed optimization for the case where participants don't actually care about being hidden:

My idea was a separate P2P network, where the cost of the identity and cost of the message transmission could be expressed and verified (either directly by bitcoin payment, or indirectly by burning coins).

[cjp]

Wow! I can't find an attack mode anymore! Thank you so much, Aakselrod! I'm so enthusiastic now; this might just work!! Some comments:

Is this a correct summary of your proposal?:

Code:

m is initially only known by final payee
hash(m) is sent together with promise

Promise = T2 update signed by payer; requires m for spending
Commit = publication of m
Abort = T2 update signed by payee

Every T2 update decreases nLockTime (unless it is not necessary, but generally it is)

Communication direction:
Promise: payer->payee ('against interest' direction)
Commit: final payee->all (broadcast)
Abort: payee->payer ('against interest' direction)

Channel status:
m unknown and no abort -> undecided (effectively ...? see below)
m known and no abort -> committed   (promise T2 is more recent than old T2)
m unknown and abort -> aborted      (abort T2 is more recent than promise T2 and old T2)
m known and abort -> aborted        (abort T2 is more recent than promise T2 and old T2)

New idea 1: if a transaction stays undecided for too long, any node can put a bounty on publication of m, by making an (in-blockchain) Bitcoin transaction that can be spent with m; I think the scriptPubKey will be something like this:

Code:

SHA256 Hashm EQUALVERIFY

New idea 2: you don't have to put all bitcoins of a link at stake when performing a transaction. You can also make a "promise T2" with outputs like this:

Code:

1. 89.99 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 00.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
3. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

This can be generalized to allow multiple transactions happening simultaneously on the same channel, even in opposite directions.

Possible problem: What happens when nLockTime is reached on a channel that is in "undecided" state?
Scenario:

T2_old = (1BTC to payer, 0BTC to payee)
T2_promise = (0BTC to (payer,m), 1BTC to (payee,m), nLockTime = T2_old.nLockTime - 1 week)
m is not published
T2_promise.nLockTime is reached
payee broadcasts T2_promise
T2_promise is included into block chain

Result: link remains "undecided" forever, unless m is published
Disincentive: never let payee have 0BTC (so he would risk losing his own BTC by doing this)

Question to think about: What happens when nLockTime is different for different channels in a payment? What will be the incentive for different participants when it comes to commit/rollback/keep things undecided until nLockTime?

[cjp]

I have a question about the rollback mechanism:

Suppose the links are set up as Alice-Carol-Mallory-Dave-Bob.

Alice wants to send BTC to Bob.
Bob makes the commit hash and sends it to Alice.
Alice updates the Alice-Carol link, using the commit hash
Carol updates the Carol-Mallory link, using the commit hash
Mallory does nothing

...now what?
Bob can not roll back the transaction, since it hasn't even reached him.
Committing the transaction would allow Mallory to steal the coins.
Waiting for nLockTime? OK, that would work. But this would only reduce the impact from "theft" to "DoS" on Alice and Carol.

What to do in the mean time?
Try again to send coins?
If they end up being routed through Mallory, you'll end up with even more locked coins.
What algorithm can you use to avoid routing again through a misbehaving node? How does Alice know whether or not Carol is misbehaving?
How do you know whether Bob is secretly acting as Mallory? He could end up collecting several "failed" transaction attempts before Alice gives up (or before Bob allows her a successful transaction), after which he could broadcast all the transaction data and collect all transactions.

[blueadept]

...now what?
Bob can not roll back the transaction, since it hasn't even reached him.
Committing the transaction would allow Mallory to steal the coins.
Waiting for nLockTime? OK, that would work. But this would only reduce the impact from "theft" to "DoS" on Alice and Carol.

Yes, you wait for nLockTime.  However, you can also discourage Mallory from trying to perform temporary DoS by means of risk deposits and reputation checks.

When Carol establishes the channel between her and Mallory, each of them puts up a risk deposit in the transaction that's a large multiple of the maximum payment allowed through the channel, and preferably even at least as much as the total size of the channel.  This limits the amount of money malicious nodes can lock up at one time assuming that as an aggregate, honest nodes control more money than dishonest nodes.

In order to perform DoS, Mallory would also have to be well connected in order for enough payments to flow through her node to make it worthwhile.  To be well connected, she'd have to lock up a lot of her own money in payment channels as well as spend a lot of time with that money locked up in well-behaving payment channels to gain a reputation that would allow her to get more connections.

What to do in the mean time?
Try again to send coins?
If they end up being routed through Mallory, you'll end up with even more locked coins.

Payers should have multiple open payment channels to their intermediary (or even to multiple intermediaries) to avoid all coins being locked up at once.  Intermediaries should also have multiple channels open to each of their neighbors to help route around such issues.  When your node's trust in a neighbor goes up, instead of increasing the maximum channel size, add another payment channel to that neighbor.  This both avoids locking up too much money due to such misbehavior, and signals greater trust in the blockchain in a prunable fashion.  This also allows the payer to attempt another payment while waiting for their coins to be unlocked.

I would suggest not using an experimental system that can lock coins for a long time as anything other than a micropayment solution until all the bugs are worked out, too.  I'm sure there will be other attack modes discovered once test nodes go live, and it would be wise not to put too much money at risk to start.  The great thing is, assuming you agree with the idea that bitcoins will continue to rise over the long term, the micropayment network will become a retail payment network without having to increase the channel size as denominated in bitcoins.

What algorithm can you use to avoid routing again through a misbehaving node? How does Alice know whether or not Carol is misbehaving?
How do you know whether Bob is secretly acting as Mallory? He could end up collecting several "failed" transaction attempts before Alice gives up (or before Bob allows her a successful transaction), after which he could broadcast all the transaction data and collect all transactions.

One way to avoid such problems is to be well-connected.  This means using more channels rather than bigger channels, and to more independent intermediaries.  You can somewhat judge the independence of inermediaries based on graph analysis of the payment network via the information available in the blockchain.  Payers, payees and intermediaries can all use such strategies.

Another way to avoid such problems is to have the payer and payee connect to all of the intermediate nodes, and monitor that the messages that are expected to pass actually pass.  For example, Alice could connect to Bob, Carol, Mallory and Dave.  When Alice sends money through Carol and Bob doesn't receive it, she could ask Carol for the transaction that was sent to Mallory.  If she gets it, she can send it on to Mallory herself and see if Bob gets paid then.  If not, she can repeat the same with the connection between Mallory and Dave.  It should generally be a simple task to find where the snag is; however, to prove that there IS a snag, the entire channel may need to be replayed in front of Alice or Bob between Carol and Mallory before Mallory's bad behavior is proven.  Your node can assume that any noncompliance is evidence of either unreliability or bad behavior on the part of the intermediary.

If Bob is secretly acting as Mallory, that's no different than Bob just not delivering goods after payment.  It's like buying something on eBay, paying for it, and not getting it in the mail.  However, with the idea above, you can have proof of where the chain breaks down, and you can always use an escrow-like transaction where the preimage of the commit hash is known by the payer rather than the payee.  The source of the preimage depends on the exact use case for the payment.  If the payer trusts the payee (like a vending machine at her employer's office or a grocery store she frequents), the payee can generate the preimage.  If the payer is transacting with someone she doesn't trust, the payer can create an escrow-like payment by generating the preimage herself and refusing to publish it/requesting a rollback if the payee doesn't deliver.

[blueadept]

Cool! Also I'm seconding jgarzik's demand to see a demo. 

If cjp decides not to include this method in his project, I will try to write a demo this summer after some major obligations are finished up in early June.

FWIW, I've been talking on IRC about a decentralized network of bots (numbering 3, 5, or 7, not large numbers) that would facilitate off-chain transactions, escrow, auctions, etc.

With the network you mentioned on IRC (I did read the logs) or even a decentralized node with intermediaries which forward funds, I think that would mean the intermediary nodes would need to register under the clarified FinCEN rules in the US.  Since I live in the US, that would preclude me from being able to run a node such as this anywhere but on testnet.  However, as I understand it, this wouldn't prevent US residents from using such a network through intermediary nodes based in another jurisdiction.

This is great work. I think a network of nodes with channels between them has been proposed before, or at least I remember talking about it, but nobody has gone into as much depth as you have. The 2-phase commit is a neat extension.

Yes, it was proposed before by cjp here and by Meni Rosenfeld here.

I was a bit confused by your description of channels as "uni-directional". You realize that the amount of value transferred from Alice to Bob can go down as well as up, right? I don't see why you need to create them in pairs.

You're correct; I corrected myself in a previous post in this thread after a comment by cjp.  It's still more efficient to treat them as reversible rather than bidirectional, IMO, due to my preferred tx versioning method including bringing nLockTime closer (see farther down in my reply).

The main issue I see is the need to constantly have some coins allocated to the intermediaries - regular Bitcoin payments require no such pre-commitments. Of course this is an issue with the entire concept of payment channels (they are not necessarily micropayment sized), but for most micropayment applications the amount of money you lock up isn't that big and the channel can close fairly quickly. Deciding how much to allocate could be rather tricky. For routing of micropayments around it wouldn't matter so much and that may be the most optimal application.

I would agree that, at least to start, this should be a micropayment application.  I'm personally interested in using Bitcoin as a means of allocating resources in a peer-to-peer computation network (so instead of mining, people can put their GPUs and FPGAs to work folding proteins for profit, for example, and a researcher can just pay peers in the network when they happen upon a solution with an energy level that's a certain amount lower than a previous solution rather than building his own compute cluster or relying on volunteers running Folding@Home).  In addition, I wouldn't trust large amounts of money to a node on such a network until the software has proven itself in micropayments.  Also, if the price continues to go up, the micropayment network can become a retail payment network without increasing the amount of money in the payment channels between nodes as denominated in bitcoins.

I wouldn't bother trying to come up with ways to work around the networks current limitations. We know what we need to do to reactivate transaction replacement and make non-final transactions standard again. If you don't want to do that, you can (and should) always prototype on the testnet where I think IsStandard is disabled and tx replacement is enabled.

Even with a full re-enabling of non-final transactions as standard and transaction replacement, you can't force any of these changes on miners.  The discussion in the previously-mentioned thread Meni started had a mention of decreasing nLockTime starting here.  Decreasing nLockTime can be combined with increasing fees, if necessary, but also with incremental transaction version numbers so that the mechanism works no matter how transaction replacement is implemented.

You would need to consider how peers can discover each other. Even if routing data can be extracted from the block chain, the protocol requires direct communication between all parties (ie, TCP connections). IP addresses change. One possibility is to require all participants to use Tor and then embed your hidden service key in a transaction. That way you get authentication, encryption and privacy for free. This boils down to using (abusing?) the Tor HSDir servers as a secure rendezvous mechanism. The short key hash (onion address) can be added to the channel transactions using OP_DROP. Note that whilst the Tor protocol is very slow/heavy for connecting, there is a proposed optimization for the case where participants don't actually care about being hidden:

https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/ideas/xxx-encrypted-services.txt

In many cases these intermediaries wouldn't care about being hidden, so that can make things faster.

Yes, this was outside the scope of what I was trying to write.  My initial demo would probably have whitelisted keys and manual connections and go for node discovery from there.  I would probably do node discovery in a broadcast network or even a DHT.  To advertise its presence, a node would sign a statement with its key that contains the several last seen block hashes, the number of blocks for which the statement is valid, and the IP address(es)/eepsites/Tor hidden services at which the node can be contacted.  The node would then either broadcast it through the P2P broadcast network or write it to the DHT, associated with a hash of its key.  Other nodes trying to contact the signing node would be able to compare the age and validity of signed statements.

Is this a correct summary of your proposal?:

Code:

m is initially only known by final payee
hash(m) is sent together with promise
...

Yes, except the part I pasted above. m can be known only by the payer, instead, and used for escrow.

New idea 1: if a transaction stays undecided for too long, any node can put a bounty on publication of m, by making an (in-blockchain) Bitcoin transaction that can be spent with m; I think the scriptPubKey will be something like this:

Code:

SHA256 Hashm EQUALVERIFY

True, and neat!  However, the incentives may not line up:  the intermediary node wouldn't want to spend more than it would gain from m's publication, and the only person who knows m wouldn't want to publish m without getting at least the amount she stands to lose by the publication in return.

New idea 2: you don't have to put all bitcoins of a link at stake when performing a transaction. You can also make a "promise T2" with outputs like this:

Code:

1. 89.99 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 00.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
3. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

This can be generalized to allow multiple transactions happening simultaneously on the same channel, even in opposite directions.

I'm not sure I understand what you're proposing.  If you have time and are still interested in developing this new idea further, I'd love it if you could explain it in more detail.

Possible problem: What happens when nLockTime is reached on a channel that is in "undecided" state?
Scenario:

T2_old = (1BTC to payer, 0BTC to payee)
T2_promise = (0BTC to (payer,m), 1BTC to (payee,m), nLockTime = T2_old.nLockTime - 1 week)
m is not published
T2_promise.nLockTime is reached
payee broadcasts T2_promise
T2_promise is included into block chain

Result: link remains "undecided" forever, unless m is published
Disincentive: never let payee have 0BTC (so he would risk losing his own BTC by doing this)

This is the risk deposit concept mentioned earlier.

Question to think about: What happens when nLockTime is different for different channels in a payment? What will be the incentive for different participants when it comes to commit/rollback/keep things undecided until nLockTime?

I don't believe this would be a problem as long as there's enough risk deposit from both side of each channel and channels are finalized well before the closest nLockTime hits.  It would be in each node's interest to do this to avoid exactly the scenario where nLockTime hits an undecided transaction.  Having a risk deposit that's a large multiple of the maximum payment size allowed through a channel prevents any party from wanting to lock up the coins in a payment because it costs them a much bigger risk deposit.

[cjp]

This is going to take me multiple posts to reply to everything. First the easy parts:

If cjp decides not to include this method in his project, I will try to write a demo this summer after some major obligations are finished up in early June.

I think, at this stage, the "global" transaction mechanism (through the entire chain) is relatively independent from the exact concept choice of the "local" mechanism (between two neighbors). I'll first make a "stupid" implementation which doesn't provide any guarantees (basically it's only bookkeeping between neighbors who fully trust each other). Then I'll add some shared wallet, possibly with the decreasing-nLockTime concept: this should reduce the need for trust as far as no transactions are happening. Finally, I'll choose one or more concepts for making the transactions themselves trust-free. So I'll save the most difficult decisions for the last.

Is this a correct summary of your proposal?:

Code:

m is initially only known by final payee
hash(m) is sent together with promise
...

Yes, except the part I pasted above. m can be known only by the payer, instead, and used for escrow.

In your Wiki page, Bob is the payee and Bob generates the hash. AFAICS it doesn't really make a difference, but if you think it does, you should update your Wiki page.

New idea 1: if a transaction stays undecided for too long, any node can put a bounty on publication of m, by making an (in-blockchain) Bitcoin transaction that can be spent with m; I think the scriptPubKey will be something like this:

Code:

SHA256 Hashm EQUALVERIFY

True, and neat!  However, the incentives may not line up:  the intermediary node wouldn't want to spend more than it would gain from m's publication, and the only person who knows m wouldn't want to publish m without getting at least the amount she stands to lose by the publication in return.

Heh, you are right about the incentive, and I should have known: I mentioned it in my paper. In my own concept, this kind of transaction is still useful to enforce either commit or rollback, but it doesn't work as a bounty.

[cjp]

Next, a detailed explanation:

New idea 2: you don't have to put all bitcoins of a link at stake when performing a transaction. You can also make a "promise T2" with outputs like this:

Code:

1. 89.99 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 00.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
3. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

This can be generalized to allow multiple transactions happening simultaneously on the same channel, even in opposite directions.

I'm not sure I understand what you're proposing.  If you have time and are still interested in developing this new idea further, I'd love it if you could explain it in more detail.

Take the same scenario as on your Wiki page with Alice-Carol-Bob.
Alice and Carol have previously set up a micropayment channel. T2 contains the following:

Code:

1. 90.00 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

Next, Alice wants to pay 0.01 BTC through the channel, using the hash value "Hashm". To do this, she signs the following T2 update and sends it to Carol:

Code:

1. 89.99 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 00.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
3. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

If the transaction is committed, m becomes known to Carol, so she can redeem both 2 and 3. If the transaction is aborted, Carol signs the following T2 update and sends it to Alice:

Code:

1. 90.00 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

(note: this equals the original T2, but the sequence number is higher and (if necessary) nLockTime has been decreased as well.)

Note: I'm not sure, but it might be necessary to also give Alice a stake in making the transaction committed. In that case, the T2 containing the undecided transaction could look like this:

Code:

1. 89.98 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 00.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyAlice CHECKSIGVERIFY
3. 00.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
4. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

In the rest of this post I'll assume this is not necessary.

Now imagine, while transaction "m" is still undecided, Alice (or someone else on her side of the network) wants to make another payment "n" through Carol (this time 0.02 BTC). This can be done with the following T2 update:

Code:

1. 89.97 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 00.01 BTC to: SHA256 Hashm EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
3. 00.02 BTC to: SHA256 Hashn EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
4. 10.00 BTC to: PubkeyCarol CHECKSIGVERIFY

Now suppose that "m" finishes but "n" is still undecided. Nothing needs to be updated for that. Suppose that, after "m" finishes, a new transaction "p" (0.03 BTC) is started through this link, this time from Carol to Alice. Carol can make the following update:

Code:

1. 89.97 BTC to: PubkeyAlice CHECKSIGVERIFY
2. 00.02 BTC to: SHA256 Hashn EQUALVERIFY PubkeyCarol CHECKSIGVERIFY
3. 00.03 BTC to: SHA256 Hashp EQUALVERIFY PubkeyAlice CHECKSIGVERIFY
4. 09.98 BTC to: PubkeyCarol CHECKSIGVERIFY

Note that, since "m" is finished, its amount is merged with the "inactive" output of Carol. If Alice knows that "m" is finished, she should accept this; otherwise, she should not accept the update, and abort "p" until Carol sends either "m" or a T2 update where "m" is still undecided.

The advantages of this approach are:

• You can do multiple transactions over the same link simultaneously
• If a single transaction doesn't commit, it only locks up that transaction's amount of BTC, and not the entire link

Note that this can also be applied to my own original concept, except that it would either require an extension to the Bitcoin scripting language (trust-free solution), or it would require the "undecided" part to be held under a 2-of-2 or 2-of-3(*) script, and have the two parties cooperatively figure out whether they consider it committed or rolled back. For that last concept I think it is useful to let both parties have a stake in agreeing on the commit state.
My own concept has the disadvantage of having a quite complicated way of reaching commit consensus, but the advantage is still that consensus (between parties who follow the protocol) is guaranteed within a couple of hours, even if nLockTime is a year ahead. Luckily, the differences are quite small, so I think both concepts can be combined in the same software without too much effort.

(*) with escrow to prevent a "hijacking" attack between neighbors. This would be an extra protection besides letting both parties have a stake in agreeing with each other.