Decentralized networks for instant, off-chain payments

[r.willis]

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

[cjp]

Finally, a response to some of your own concepts:

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

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.

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.

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.

[cjp]

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

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?

[r.willis]

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?

[cjp]

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?

[r.willis]

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?

[cjp]

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

[r.willis]

Thanks for explanation, I understand basic idea now.

[Mike Hearn]

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.

[blueadept]

Good stuff.  Let's see a demo

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

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

[Mike Hearn]

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

Code:

ep1.start();
ep2.start();
im.start();

do {
    Thread.sleep(1000);
} while ((ep1.isRunning() == false) || (ep2.isRunning() == false) || (im.isRunning() == false));

You can write this:

Code:

Futures.allAsList(ep1.start(), ep2.start(), im.start()).get();

which does a fan-in on the futures.

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

Code:

    	while (
    			(ep1.wallet().getBalance().compareTo(BigInteger.valueOf(5000000)) < 0) ||
    			(ep2.wallet().getBalance().compareTo(BigInteger.valueOf(5000000)) < 0) ||
    			(im.wallet().getBalance().compareTo(BigInteger.valueOf(10000000)) < 0)
    			) {
    		Thread.sleep(1000);
    	}

you can do this instead:

Code:

BigInteger amount1 = BigInteger.valueOf(5000000);
BigInteger amount2 = amount1.multiply(BigInteger.valueOf(2));
Futures.allAsList(
  ep1.wallet().getBalanceFuture(amount1), 
  ep2.wallet().getBalanceFuture(amount1), 
  im.wallet().getBalanceFuture(amount2)
).get();

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:

Code:

		this.vChain.addListener(new AbstractBlockChainListener() {
			@Override
			public void notifyNewBestBlock(StoredBlock block) {
				new Thread() {
					@Override
					public void run() {
						for (PaymentChannelGroup peerGroup : connections
								.values()) {
							peerGroup.checkChannelStates();
						}
					}
				}.start();
			}
		});

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.

[blueadept]

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.

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

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?

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

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

Take a read through the ListenableFuture docs. In many places where in RunTest where you have busy-wait loops, you can replace them with a simpler and cleaner construct.

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.

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

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!

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

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.

This code looks wrong:

Code:

		this.vChain.addListener(new AbstractBlockChainListener() {
			@Override
			public void notifyNewBestBlock(StoredBlock block) {
				new Thread() {
					@Override
					public void run() {
						for (PaymentChannelGroup peerGroup : connections
								.values()) {
							peerGroup.checkChannelStates();
						}
					}
				}.start();
			}
		});

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.

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.

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

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.

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.

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!

[Mike Hearn]

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.

[blueadept]

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

[giszmo]

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.

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.

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

[blueadept]

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:

...

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.

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.

I think that would mean the intermediary nodes would need to register under the clarified FinCEN rules in the US.

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

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.

[giszmo]

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.

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.

[markm]

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-

[coinrevo]

code is gone? the fileswap link is broken.

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

[blueadept]

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.