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.

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

Hopefully Mike Hearn will give some feedback on it.

-MarkM-

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

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


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.

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.

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

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.

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.


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.


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


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


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.


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.


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.


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


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.


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.


This is the risk deposit concept mentioned earlier.


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.

Next, a detailed explanation:


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:

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:

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:
(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:
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:

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