Bitcoin Forum

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

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.

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.

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

Hopefully Mike Hearn will give some feedback on it.

-MarkM-

Good stuff.  Let's see a demo :)

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

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 (https://github.com/cornwarecjp/amiko-pay)) contains little more than low-level stuff like sending cryptographically signed messages between nodes, so there's still some room for design changes.

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 (https://bitcointalk.org/index.php?topic=91732.msg1030328#msg1030328).  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 (https://bitcointalk.org/index.php?topic=145496.0) 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.

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.

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.

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

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.

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.

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

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

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:

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

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.

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.


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.


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.

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 (https://bitcointalk.org/index.php?topic=94674.0) and by Meni Rosenfeld here (https://bitcointalk.org/index.php?topic=91732.0).


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 (https://bitcointalk.org/index.php?topic=91732.msg1028651#msg1028651).  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.

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

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.

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.


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.

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.

Can you describe in simple terms, how double-spend is prevented?

Finally, a response to some of your own concepts:

I've read the threads you linked to about risk deposits. If I understand correctly, they work very similar to the "shared property" in my concept: I even hinted in my paper that, if one neighbor doesn't trust the other, he should make sure that the other keeps a significant fraction of the shared account, to make "hijacking"/"blackmailing" expensive. Using a 3rd party as escrow is a an interesting possibility; I didn't think of that yet. The difference with my concept is that, in your proposal, a failure somewhere in the middle of the chain can lead to blocked transactions, loss of reputation and possibly locked up risk deposits throughout the half of the chain, while in my concept the damage of misbehavior remains limited to the direct neighbor of the misbehaving node, and the misbehaving node itself.

Ah, I was actually planning to use a different routing method than you, to improve privacy. People typically don't want others to know who they are connected to. The downside of my routing method would be that the above "debugging" wouldn't be possible. But you are right: if routing is based on a publicly known network shape, and you can communicate directly with any node in the network, you have a good chance of identifying misbehaving / defunct nodes.

Basically, there is a fixed amount of BTC in each "micropayment channel", and there's always a part that belongs to one side and a part that belongs to the other side. Added together, the two parts will always be the same fixed amount.

Spending from one side to the other basically comes down to changing the amounts. For instance, if the amounts are initially 90BTC for Alice and 10BTC for Carol, Alice can spend 0.01 BTC by changing the amounts to 89.99BTC for Alice and 10.01BTC for Carol.

What would "double spending" look like? Maybe it would be changing to "89.99BTC for Alice and 10.01BTC for Carol" and then changing again to "89.99BTC for Alice and 10.01BTC for Carol"? That would be detected immediately by Carol, and she would refuse it, since that would make her receive less than she should. She will just ignore the update, and send an error message back to Alice.

Does that answer your question?

Well, no.
Consider there are three parties:
Alice, Bob and Carol.
Alice spends 0.01 BTC to Bob and the same 0.01 BTC to Carol. Which transaction will be accepted?

No, that can't happen. A "microtransaction channel" is always between two parties, not three or more.

So, if Alice and Carol share a channel, then Alice can use that channel to spend to Carol.
However, if Alice wants to spend to Bob, another channel is needed. There are two possibilities:

• Alice sets up a channel directly with Bob, and uses it to Spend to Bob.
• Carol sets up a channel with Bob. Now Alice can spend to Bob indirectly through Carol:
  
  • Alice spends to Carol, through the Alice-Carol channel
  • Carol spends the same amount to Bob, through the Carol-Bob channel

Naturally, the second one is a bit more complicated (e.g. you need to make sure that Carol honestly forwards the same amount to Bob), but basically that's the idea.

Each channel prevents double-spending internally. Also, since regular Bitcoin transactions are required for setting up the microtransaction channel, you can not use the same bitcoins for setting up multiple channels.

Is it clear now?

I understand it better now, but still not get what "microtransaction channel" is? Is it special bitcoin transaction? Does it need to be opened long before microtransactions can be made? Is it pre-paid? Does it need to be recorded on blockchain and confirmed?

It's similar to what's described here (https://en.bitcoin.it/wiki/Contracts#Example_7:_Rapidly-adjusted_.28micro.29payments_to_a_pre-determined_party). For more details, see also the first post in this thread.

Basically, yes, it's prepaid. Setting up the channel and dismantling it have to be recorded on blockchain (and confirmed). In-between, transactions can happen in both directions through the channel; these transactions don't need to be recorded in the blockchain.

The two parties operate the channel by continuously making new versions of a special Bitcoin transaction, without publishing that transaction on the Bitcoin network. The transaction is such that it only becomes valid at a certain time ("nLockTime"); as soon as this time is reached, the participants can publish the transaction (typically the latest version) on the Bitcoin network; as soon as that happens, the channel can no longer be used for "off-blockchain" transactions, and the bitcoins become available to the two participants for normal "on-blockchain" Bitcoin transactions.

Opening a microtransaction channel should take a similar amount of time as making a normal Bitcoin transaction (e.g. 6 confirmations = approx. 1 hour). After that, it can be used immediately for making "off-blockchain" transactions. These "off-blockchain" transactions don't need to wait for confirmations, so they typically take less than a second. The channel itself has a limited lifetime (determined by "nLockTime"); this is primarily useful to allow you to get your bitcoins back even in case the other side of the channel starts misbehaving / disappears / has other problems. For instance, if you set nLockTime to a year in the future, you can use the channel for approximately a year; if, during that year, the other side of the channel causes unsolvable problems,
you can get your bitcoins back at the end of the year.

Naturally, you can only get the bitcoins back that really belong to you; the other party can only get his own coins back. For instance, if you use 100BTC to set up a channel, then spend 40BTC through the channel with "off-blockchain" transactions, you can only get 60BTC back when the channel expires (or whenever both parties agree to end the channel sooner). The other side can then get his 40BTC.

Thanks for explanation, I understand basic idea now.

The term micropayment channel is misleading, I wish I had called it something else now. If/when I implement this I'll be calling them just payment channels, or perhaps high-frequency trades. They don't have to be micropayments. That just happens to be an obvious use case.

A channel can be between an arbitrary number of parties. There is no need for them to be between just two. My example of buying wifi happened to use two, but you can have more. Consider the 3 party case. Each party adds an input to the contract connected to some value they are putting in. They all sign using SIGHASH_NONE. Any party can now write a new version of the transaction that re-allocates the value in arbitrary ways. That's probably not a very useful construct if you don't trust the other parties, but SIGHASH_SINGLE works in the same way (anyone can update the transaction and change any output except yours). You can use a n-of-3 multisignature input if you want a subset of the parties to have to agree before the outputs can change.

Demo is available now:

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

It depends on BitcoinJ 0.10-SNAPSHOT from about a month ago (hopefully not too much in terms of API has changed since then).  It requires bitcoind running locally in regtest mode, with the snapshot from here:

https://github.com/aakselrod/bitcoin/tree/stdpreimage

The only change I've committed is permitting three new templates as standard transaction types (only one of them is used in this demo, though).

This demo is a proof of concept only - it has lots of bugs that need fixing, it doesn't support any kind of communication between nodes other than within the same process, it does no error checking or input validation whatsoever, etc.  It just sets up two payment channels (between an intermediary and two endpoints), and sends some payments between the endpoints by way of the intermediary.

I'm releasing this code into the public domain.  I've timestamped the file, info at the following URL:

https://www.proofofexistence.com/detail/44020f041501aea0d01ed3e0a7dd822732e5c9945dfedc9271d19890b4a3592d

(Although now that I look at it, it looks like they haven't actually sent any transactions to the blockchain in a while... hrm...)

Cool!

I compiled it against current 0.10 (which is about to be released, modulo a couple of last minute bugfixes), and it compiled fine. I haven't tried running it yet.

I was surprised to see it doesn't actually use the payment channels API at all, it seems instead to reimplement parts of it. Is there a reason for that? Does the API need some other features for it to be usable by you?

Here are some other tips from a quick review of the code:

Take a read through the ListenableFuture (https://code.google.com/p/guava-libraries/wiki/ListenableFutureExplained) docs. In many places where in RunTest where you have busy-wait loops, you can replace them with a simpler and cleaner construct. For example, instead of this:


You can write this:


which does a fan-in on the futures.

Likewise, instead of doing a busy-wait loop on the balances of each test node:


you can do this instead:


If you use IntelliJ or another good refactoring IDE, you can just select an expression that is repeated redundantly and select "Extract constant" from the refactoring menu. Give it a name and it'll find all the cases where that expression is repeated and replace them for you (inline).

In git master there is a WalletAppKit.connectToLocalHost() method which simplifies some more boilerplate.

ScriptBuilder has some static methods that simplify the code you have to create scriptSigs.

This code looks wrong:


But in 0.10 your listener already runs on a dedicated background thread (the "user thread"). There's no need to create your own dedicated thread for each one. Indeed, this code looks buggy as you could get peerGroup.checkChannelStates() being run in parallel and that method doesn't look thread safe. If you rely on the default behaviour of running on the user thread, your callbacks won't be invoked in parallel so you can just delete the new Thread() {} and get the correct result.

It's better to use the wallet(), etc accessors if you're going to subclass WalletAppKit.

Overall though, it's great to see people playing with these ideas and building on bitcoinj. If you reuse the standard payment channels API then you get network connectivity, persistence to the wallet and many other things for free.

Awesome, thanks for looking at it!  I'll update it to 0.10 when that's out.


I actually started working on this before 0.9 was published, so a lot of what you see is a mishmash of code based on 0.9-SNAPSHOT that was refactored (but not fully) to 0.10-SNAPSHOT.  I had already had a lot of it written (the bottleneck, aside from my limited time due to how busy my paid job and family make me, was testing on testnet before I realized you'd added regtest mode) prior to the BitcoinJ payment channel API.  As I was going to release it to the public domain, I figured I wouldn't spend much time looking at the payment channel code in BitcoinJ until I was ready to do so; that would avoid contaminating public domain code with Apache licensed code.

There are a couple of things that would be needed in the BItcoinJ payment channel code to be able to do this:

• The hash preimage part of the SriptPubKey/ScriptSig needs to be supported in order to send payments through chained channels atomically, and is what made the addition of the templates I wrote necessary in bitcoind
• Risk deposits are necessary for the chaining as well, and as far as I can tell, your code doesn't yet support them
• Reversing a payment channel is also useful, and I haven't yet looked to see if your code supports that, though it's probably not too difficult to add

It's definitely my intent to replace any polling with futures as appropriate, but there are lots of APIs I'm as yet unfamiliar with.  This was almost a braindump into code, and I'll clean this part up.


I intend to move away from using WalletAppKit and use discrete components instead, but this was good for a starting point.  I didn't see you add that method before I wrote the code that connects to the local regtest-mode bitcoind, or I would've used it, thanks!


I've already started using some of them (in particular, the multisig-related static methods, which I switched away from manually building those scripts opcode-by-opcode), but I'll look at it again and see what else I'm missing.  You've been working on ScriptBuilder as I've been working on this, so I probably haven't yet caught up with all the improvements.


You're right, concurrency is one of the things I haven't yet worked on in this context.  In using regtest, I was setting up an environment where this wouldn't matter much, but I need to fix this prior to the code being ready for pre-alpha.  The TODO list specifies this.  The reason I'm starting a new thread in this context is that when I wrote this code, BitcoinJ was still in 0.9-SNAPSHOT, and I wasn't thinking about thread safety yet.


I'm planning on moving away from that and using discrete components of BitcoinJ as I continue development.  There are lots of inconsitencies and things done wrong in my code... I've taken a note on a lot of them in the TODO file, but I have missed some, so thank you for looking over the code!  I hope to have time to improve on it in the near future and get it closer to a working model.


Now that I've published this, I'm planning on taking a closer look and seeing if I can use the standard payment channels API instead of what I wrote.  Thanks for providing such a great library to build on!

Great. Yeah, I realise that the code evolved in parallel with the current release. I know how hard it is to find time for personal projects :)

By "reversing a payment channel" what do you mean exactly? If tx replacement worked, we could reduce a channel as well as increase it, but unfortunately due to the lack of that you'd have to establish a channel in both directions. Really, there are lots of things we could do better once tx replacement is fixed.

By reversing, I mean exactly what you mean:  reducing the value to the responder and increasing it to the initiator.

In the PaymentChannel.pay() method in my code, I keep track of a boolean called iSentLast.  If this boolean is false, I do the following things:

• Increase the fee by feeStep
• Decrease the locktime by locktimeStep
• Increment the contract input's sequence number by 1

This reduces the lifetime of the payment channel (I use blocks rather than time to count lifetime), and ensures that payments in the new direction become standard before payments in the old direction.  When transaction replacement is enabled, the increase in fee and sequence number will also help ensure that the new direction is prioritized over the old direction.

When a payment is sent in the same direction as the last payment, these steps don't need to be taken.  The recipient of the payment is the only party in possession of the fully-signed transaction for both payments, so the fact that the transaction for the latest payment contains the biggest take for the recipient should be enough motivation for the recipient to publish it.  My code doesn't yet handle the case where the recipient doesn't publish the latest transaction, but does handle the case where the recipient is offline and does not publish the transaction at all (in that case, the sender publishes the last fully-signed transaction s/he has when it becomes standard, stealing money from the recipient).

Unfortunately, peers need to be online in my scheme in order to process payments and tear down payment channels at the right time, and this highlights the locktimeStep-based trade-off between payment security and the need to tear down/rebuild channels.  I think in most cases, people will want to have a pair of channels and a large locktimeStep (at least 12 blocks probably), and only reverse them when they get fully used up, and I'll add methods to do that to the code when I get there.  For proof of concept purposes, this wasn't as important.

There is bug in the current code that prevents the fee from being incremented in at least one instance where it should (when making the first payment after the channel is established), but it's one of many bugs I know about and know how to fix, so I left it for a future update.

By the way, I meant to respond to your mention of IntelliJ - I am using Eclipse and it also has similar refactor functionality, though I've made very little use of it thus far.  I apologize in advance for my code being clunky/awkward, I'm still getting back up to speed on any sort of serious programming (and enjoying it immensely).

What is the state of this project? I consider this or anything like this the most important improvement since Bitcoin itself as I would expect from it:

• instant payment solved once and for all
• truly free-ish transactions (for a long time to come: if 8billion people want to participate with just one one-year-channel each, we would still have to process 300k transactions per block)
• arbitrarily small payments (down to 1 Satoshi until we introduce more decimals)
• increased anonymity (if done as described here and not with just a small set of entities providing nodes like email providers)
• closely related: an end to services actually holding users' money with all the risks that brings with it

As the server/node part of this should be completely trust free, it could even be run by a company closed source with huge profit potential as currently every bitcoin transaction is worth $0.08US.


I find this concern rather funny. One – although not the only – reason to give money transmitter high scrutiny is to protect users from the money transmitters spending their money. Paypal is holding gigantic amounts of money at any given moment. The point of the proposed tools here is to remove that trust completely so I would consider it worth arguing if you are a money transmitter by these laws at all. Sprint and AT&T also transmit banking messages via their networks and they also charge for transmitting these messages.

The other point is that the project proposed here is meant to be available to everybody as open source (right?) although a trust free node could be used even if only the client was open source. How will FinCEN possibly police all the kids that aptitude install a payment node to "mine" some mɃ?

Your list of advantages is right, and I'm even more interested in the use of this technology to monetize other P2P services and meshnets without needing to create new currencies.

Unfortunately, I've been busy with paying work and family obligations. After the next one or two bubbles, I'm hoping to be able to quit my job and/or hire a freelancer to finish this, but I can't do that as things currently stand. I've written a prototype in case anyone with time feels like working on this in the meantime, and it's public domain and published on Github.

May I quote you on saying that this could be "the most important improvement since Bitcoin itself?" Maybe it would help me line up some resources to be able to work on this.


Because a node accepts money in one payment channel and sends it out another, I wouldn't bet on FinCEN not seeing the running of such a node as money transmission. I have no doubt this would quickly become impossible to police, but I'm not willing to stick my neck out personally to run such a node in production in the US. I have a family to care for. Still, running a node with connections only to people you trust not to rat you out is easy enough to do without giving away your activities.

Usually I mean what I say and only barely post stuff I'd rather not have people quote me with, so yeah, please, go ahead. I deeply mean what I said.

Why would you want a third party in-between you and the person you are paying or being paid by?

Or is the main assumption here that middle-persons always go out of their way to revent people finding each other directly thus that most likely an given Alice would have little chance of happening upon a Bob without some Middleperson (Mallory?) regusing to introduce them but offering to get in between any thing they attempt to do together?

Presumably only these Mallory people - the middlepersons - would be money transmitters, since Alice and Bob are merely two people who happen to chose to transact with each other?

Maybe a desire to save the Mallories the expense of having to become moen transmitters, which expense they will doubtless try to pass on to as many Alices and Bobs as they can, with markups on it too, would be a good incentive to try to find ways to eliminate Mallories in general?

-MarkM-

code is gone? the fileswap link is broken.

Very interesting stuff. Projects with this kind of quality should be highlighted somehow.

markm: the point is to enable instantaneous payments with lower fees, but to multiple parties. This is just an expansion of Mike Hearn's micropayment scheme that permits payments.  It's friend to friend rather than fully peer to peer, but it's faster and more scalable than Bitcoin on its own because not everyone need to be aware of every payment. Everyone just knows about every payment channel that's established or torn down, as on chain transactions.

coinrevo: sorry, my signature contains a link to the code on GitHub. I'll update my posts.

interesting. could you elaborate on this point? I think cryptocurrencies and meshnets have several overlaps as you indicate.

I wrote a blog post (http://alexonbitcoin.blogspot.com/2013/08/announcing-proof-of-concept-for.html) about this back in August.

I've got a busy week at work and then I'm giving a Bitcoin talk to a local LUG but after that, I'm going to write up a new way to use this same contract structure for both decentralized inter-currency off-chain payments and for decentralized derivatives markets.