Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

A limitation on most existing micropayment channel ideas is that payments can only flow in one direction. This is because the payment receiver can sign -any- transaction you send them, not just the most recent one, and so it's possible to just sign the transaction transferring the largest amount into their control. This is easily remedied by opening a second payment channel in the opposite direction, but now both parties have to deposit funds over the lifetime of the two channels. If one party doesn't know ahead of time whether or not the other party will go into credit, having only one channel may save the use of a deposit.

I propose a way of using CHECKLOCKTIMEVERIFY to allow a reversible payment channel, introducing at most one additional broadcast transaction, with a waiting period before the payment receiver can access deposited funds. The extra transaction and waiting period apply only when the depositor doesn't co-operate with the receiver.

In this protocol, the setup is identical, with a deposit made to a P2SH address matching a script allowing either single-party+CHECKLOCKTIME or 2-of-2. In this case, however, payments made by the depositor occur in the form of unbroadcast transactions to special -holding addresses-.

These holding addresses are themselves P2SH addresses, with scripts known to both parties. Each script may be redeemed in one of two ways: by the payment receiver, using their signature with a CHECKLOCKTIME restriction that expires some period of time after the restriction on the depositor's refund transaction, or by the depositor, using their own signature, together with a hashlock.

In the second case, we actually use a double hashlock, i.e. the depositor must provide a value which when SHA256-hashed twice produces the value in the script.

The receiver generates these values according to the following algorithm:
Beginning with a secret S_0, they double hash S_0 to make the hashlock
value for the first payment, D_0 =H(H(S_0)). Then to make S_i+1 given S_i,
they create a public nonce, N_i, and let S_i+1 = H(N_i | H(S_i)), where a|b
denotes the string a followed by the string b. The hashlock values D_i are
not secret, and can be disclosed in advance or as part of the process of
receiving the associated payment.

When the receiver wants to refund some amount to the depositor, the receiver finds the last payment which left the depositor with a balance -greater- than the desired balance, and negotiates a rewind of the payment sequence to that point, with an additional payment of the remainder by the depositor. Suppose the last payment that will remain valid was the i-th payment, counting from zero. The receiver creates a new nonce, N'_i, creates the associated new secret value S'_i+1 by S'_i+1 = H(N'_i | H(S_i)), and sends D'_i+1 to the depositor with a request for payment of the right amount. This amount will be greater than that associated to D_i, but less than that associated to D_i+1, so the depositor does not need to trust the receiver in order to honour the request. The payment chain is now forked at D_i, with a branch D_i+1, D_i+2... and a branch that only has D'_i+1. The receiver now unwinds the old branch, back to D_i, by revealing S_i+1 to the depositor. The depositor can now generate - and check - the secrets S_i+1, S_i+2..., and so knows that if the receiver attempts to sign and broadcast a transaction to an address using one of those secrets, the depositor can take back all their funds before the receiver is able to put their own (CHECKLOCKTIME restricted) transaction from that address on the blockchain. Now the best usable payment to the receiver is the one associated to D'_i+1.

When the two parties want to close the payment channel, one party signs a transaction from the deposit address to whatever addresses are desired, and sends the transaction to the other party to add their own signature and publish. This avoids either party having to wait for CHECKLOCKTIME restrictions to expire. If either party abandons the protocol at this point, the other can use the CHECKLOCKTIME restrictions to ensure they get at least as much as they would if both cooperated. Note that the holding addresses are only used on the blockchain when the protocol is abandoned.

This protocol does not deal with the case of malicious attacks on a party's network connection, which could keep them offline until CHECKLOCKTIME has expired. This is something that each party should consider when choosing how long the restrictions should be in place for. The protocol improves on blueadept's use of a new nLockTime for each reverse payment[1], by keeping the wait time independent of the number of payments, and not requiring either party to predict ahead of time how many payments will occur.

A note on generating hashlock secrets: the protocol works perfectly well without generating them deterministically. Using an HMAC-style derivation is more of a convenience than anything else - it saves storing and transmitting all the secrets when a chain needs to be invalidated - but it does encode the fact that the addresses form a chain into the addresses' scripts, which is a nice property to have.

[1] https://bitcointalk.org/index.php?topic=814770.msg9185225#msg9185225

I first posted this at https://bitcointalk.org/index.php?topic=918018.0 and have edited it slightly for posting on this list. Thanks to Peter Todd for the suggestion to submit it here for review.

Nathan Cook

>
> A limitation on most existing micropayment channel ideas is that payments
> can only flow in one direction.
>

It's worth noting that the original protocol as designed by Satoshi did not have this limitation. It has evolved this way because of ad-hoc DoS fixes over time (btw I'm not saying they were the wrong thing to do, as non "ad hoc" solutions are significantly more work). But it seems like eventually a different approach to handling DoS attacks based on resource prioritisation and scheduling will become needed / implemented, and at that point the original design could be safely brought back to life.

Mike, Can you be more specific? You reference "original design" without saying how it was different/better.

On Fri, Jan 9, 2015 at 8:20 AM, Mike Hearn <mike@plan99•net> wrote:

> A limitation on most existing micropayment channel ideas is that payments
>> can only flow in one direction.
>>
>
> It's worth noting that the original protocol as designed by Satoshi did
> not have this limitation. It has evolved this way because of ad-hoc DoS
> fixes over time (btw I'm not saying they were the wrong thing to do, as non
> "ad hoc" solutions are significantly more work). But it seems like
> eventually a different approach to handling DoS attacks based on resource
> prioritisation and scheduling will become needed / implemented, and at that
> point the original design could be safely brought back to life.
>
>
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming! The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is
> your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

On Fri, Jan 9, 2015 at 1:20 PM, Mike Hearn <mike@plan99•net> wrote:

>> A limitation on most existing micropayment channel ideas is that payments
>> can only flow in one direction.
> It's worth noting that the original protocol as designed by Satoshi did not
> have this limitation. It has evolved this way because of ad-hoc DoS fixes
> over time (btw I'm not saying they were the wrong thing to do, as non "ad
> hoc" solutions are significantly more work). But it seems like eventually a
> different approach to handling DoS attacks based on resource prioritisation
> and scheduling will become needed / implemented, and at that point the
> original design could be safely brought back to life.

I don't agree with your understanding. Expecting replacement to work and be enforced is completely unsafe. People (sanely) refuse to use protocols which are broken by refund malleability, which is a much narrower expectation for miners than expecting the sequence ratchet to go one way.

The original design is documented at the bottom of here:

https://en.bitcoin.it/wiki/Contracts#Example_7:_Rapidly-adjusted_.28micro.29payments_to_a_pre-determined_party

In this design, time locked transactions can be broadcast across the network and replaced by broadcasting a new transaction that uses higher sequence numbers. That's what the sequence number field is for. It was intended to allow arbitrary high frequency trading between a set of parties, though the "channel" notion is a simple way to think about the two party case.

The issue is that you can broadcast transactions with a lock time far in the future to fill up memory, and keep broadcasting replacements to use up CPU time and bandwidth.

Additionally, there is a school of thought that says Bitcoin must work even if lots of miners are malicious and willing to break arbitrary things in order to try and get more money. I don't think Bitcoin can really be a mainstream success under such a threat model, for a whole bunch of reasons (e.g. the economy relies pretty heavily on unconfirmed transactions), but under such a threat model there's nothing that forces miners to actually include the latest version in the block chain. They could pick any version. In the 2-of-2 channel model it takes both parties to sign, so clients can enforce that all versions have the same fee attached.

I disagree with Gregory that people refuse to use protocols that are affected by malleability. There aren't any user-friendly apps that use refunds currently, so we have no idea whether people would refuse to use them or not. It's an open question. The answer would probably depend on the real prevalence of attacks, which is currently unknowable and likely application specific.

On Fri, Jan 9, 2015 at 1:42 PM, Mike Hearn <mike@plan99•net> wrote:

> Additionally, there is a school of thought that says Bitcoin must work even
> if lots of miners are malicious and willing to break arbitrary things in
> order to try and get more money. I don't think Bitcoin can really be a

This being unsafe doesn't require "a lot" though, if 1% of the hashpower is naughty, an attacker will have a 1% success rate. Naughty can also just mean broken in various ways, like mining while somewhat partitioned (didn't hear the update) potentially due to a DOS attack, or because of some garbage collection policy made it forget the transaction to conserve resources. An unkind user can simply run software that automatically attempts (by sending naughty miners an earlier conflict right before the locktime expires). "Use Blue Rewards wallet for 2% cash back for all the Bitcoin purchases you make online!" :P

Of course, all the miners who don't play along will very much see how much income they're missing.

> so clients can enforce that all versions have the same fee attached

Sadly, they cannot. This is why I specifically mentioned child pays for parent.

In any case, sometimes a 1% fault rate is acceptable. But generally for cases that they are, even weaker constructs (e.g. no payment channel at all, just accept an IOU) are also often acceptable, and cannot be modulated in their success by resource starvation attacks on the network.

We have objective proof of substantial miners behaving maliciously, that much isn't a speculative concern.

The school of thought view is a bit too black and white. My perspective is that absolute soundness is best (rules which cannot be broken at all), followed by cryptographic soundness (rules that breaking requires P=NP, theft of a secret, or insane luck), followed by economic soundness (rules that cannot be profitably broken), followed by honesty soundness (rules that hold when the participants follow the rules and aren't faulty). We should try to move up that stack as far towards absolutely soundness as possible; and be increasingly cautious about compromises as we move down it espeically because the last two are unstable and difficult to reason about because they strongly import the vulgarities of humanity into the security model. If we could make the whole system absolutely sound or cryptographically sound, I would think we should (and would) even if it implied other compromises. But we can't and so users of Bitcoin must navigate this risk stack.

One thing that I think you miss in this argument is that one man's integrity is another man's malice. The history of security and privacy is filled with instances where someone's trust was violated because there someone was, rightly or wrongly, convinced that Some Reason was Good Enough to justify it. Because of this a risk analysis has to import the clarity of judgement, morality, coerceability, personal values, etc. of everyone in the trust chain; and many of these things are unknowable; this greatly increases the costs of transacting, and the efforts to mitigate those costs (and the failures to remove the harms) result in an unequitable enviroment where some people get unjust rewards and unequal access to justice. The gain from cryptographic tools is being able to make some level of stronger assurances which cut out most of that trust, they're predictable, 'cheap' on a marginal basis, and fair in a fundamental sense (in theory everyone has equal access to math). So, while I could even buy the argument that miners will never believe themselves to be "actually malicious", history shows that people's ability to convince themselves of the justification of something is basically unbounded, even outright thieves often believe they're owed their spoils-- and there are a lot of ways to misbehave in Bitcoin that stop short of theft. And so, where we cannot have cryptographic security enforce the rules, we-- those who use and depend on Bitcoin-- _generally_ ought to behave in ways that cannot be harmed by a failure to follow the rules so that we don't _invite_ failures to follow the rules and thereby create an institution of it.

Of course, all things equal I don't want to choose for other people what tools they can use and what risks they take. But in the case of relaying locked transactions this isn't an otherwise neutral choice: A straight forward "relay and store any locked spend" policy has unbounded space and communications complexity. It's not clear to me that if any real degree of "you can take your risks, it'll probably work, but maybe not" can be supported without a very large resource cost to the network, and without creating incentives to DOS attack the network (e.g. to make it forget previous spends). It may be that there is some set of constraints that actually do make it workable and don't create the incentives though... meaning that it may _merely_ be unsafe for people who choose to use it. If so, then it might be reasonable but we also cannot ignore the incentives it creates in a wider ecosystem and what their ultimate conclusion might be. E.g. If you put a bounty for miners to behave 'wrong' in a way the system cannot prevent, some will. Is the next step to try to say that only "good" miners can mine? If so, how many more steps until every transaction is being tested against a set of system external goodness criteria? In that state, is Bitcoin any better than a very computationally and bandwidth inefficient version of Paypal?

Slipper slope arguments can be a bit slippery. I don't have any clear answers. I do know that ignoring the risks we know about isn't a good path.

Please comment if possible on some of the techno-cultural implications of ongoing development of bi-directional micropayment channels?

For example, consider zakat example(s): www[dot]hidaya[dot]org/publications/zakat-information/10-what-is-zakat-obligatory-charity That involves a system based on trust and which is somewhat circular in nature (such funds as are going in one direction may also be going simultaneously on balance in another direction somewhere else), where the trustless bitcoin utilizes math, rather than personal trust in order to keep the system going. Here is some more on zakat: en[dot]wikipedia[dot]org/wiki/Zakat en[dot]wikipedia[dot]org/wiki/Ridda_wars (Discusses in depth some differences between Sunni and Shiite on the subject of Zakat)

A sort of traditional philanthropic historic overview in the USA from the 1900s forward is seen here, but it is fairly minimal and not too revealing: www[dot]nptrust[dot]org/history-of-giving/timeline/1900s/

A general microgiving example(s) (not yet fully modeled but for which some prototype software ideas and concepts are in process today): abis[dot]io

Cheers,

- -O

Mike Hearn:

> The original design is documented at the bottom of here:
>
> https://en.bitcoin.it/wiki/Contracts#Example_7:_Rapidly-adjusted_.28micro.29payments_to_a_pre-determined_party
>
>
>
>

In this design, time locked transactions can be broadcast across

> the network and replaced by broadcasting a new transaction that
> uses higher sequence numbers. That's what the sequence number field
> is for. It was intended to allow arbitrary high frequency trading
> between a set of parties, though the "channel" notion is a simple
> way to think about the two party case.
>
> The issue is that you can broadcast transactions with a lock time
> far in the future to fill up memory, and keep broadcasting
> replacements to use up CPU time and bandwidth.
>
> Additionally, there is a school of thought that says Bitcoin must
> work even if lots of miners are malicious and willing to break
> arbitrary things in order to try and get more money. I don't think
>  Bitcoin can really be a mainstream success under such a threat
> model, for a whole bunch of reasons (e.g. the economy relies pretty
> heavily on unconfirmed transactions), but under such a threat model
> there's nothing that forces miners to actually include the latest
> version in the block chain. They could pick any version. In the
> 2-of-2 channel model it takes both parties to sign, so clients can
> enforce that all versions have the same fee attached.
>
> I disagree with Gregory that people refuse to use protocols that
> are affected by malleability. There aren't any user-friendly apps
> that use refunds currently, so we have no idea whether people would
> refuse to use them or not. It's an open question. The answer would
> probably depend on the real prevalence of attacks, which is
> currently unknowable and likely application specific.
>
>
>
> ------------------------------------------------------------------------------
>
>
>
>

Dive into the World of Parallel Programming! The Go Parallel Website,

> sponsored by Intel and developed in partnership with Slashdot
> Media, is your hub for all things parallel software development,
> from weekly thought leadership blogs to news, videos, case studies,
> tutorials and more. Take a look and join the conversation now.
> http://goparallel.sourceforge.net
>
>
>
> _______________________________________________ Bitcoin-development
> mailing list Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

- -- http://abis.io ~ "a protocol concept to enable decentralization and expansion of a giving economy, and a new social good" https://keybase.io/odinn

Firstly, apologies to Nathan for not actually providing feedback on his protocol. I've put pondering it onto my mental todo list. The notion of a payment tree is interesting but complicated - I would need to think about it and maybe draw myself some diagrams before having useful feedback here. If you wanted to implement it, you could fork the existing code in bitcoinj and extend it with the new functionality.

I raised the original Satoshi design mainly to inform and so the approaches can be compared. It may well be that this proposed protocol is superior in every way, in which case the nSequence approach would be of no further use, assuming Nathan's protocol generalises to n-party HFT.

Replying now to Gregory:

I think we agree, and are just phrasing things differently (or slowly groping towards consensus at the speed of email threads :-).

It's likely that over time Bitcoin will end up being multi-layered, with the block chain being the base layer that syncs everyone up, and higher layers doing things that miners either can't do or can't be trusted to do. Like the proposal from GreenAddress to be a well known signer who is trusted to not double spend.

From miners perspective, there are multiple schemes where they are viable if cost(fraud) < benefit, at the moment unconfirmed transactions appear to be an example of that, and putting resource control considerations to one side, it's possible that tx replacement would be the same. Or not. The calculation for miners isn't easy, because if they play by the rules then they may have a long term and reliable income stream, but if they break the rules then that payment traffic will migrate to other solutions and they end up with nothing. Whether it's worth it depends on how long term they're thinking.

If we imagine a hypothetical future where lots of economic activity is being done over Satoshi-style replaceable contracts, and suddenly a new big short-termist miner comes along who decides that just breaking the rules will give him more profit before the business dries up, what would happen? If fraud costs get too extreme the old fallback of a purely centralised solution is always there - for software compatibility purposes this would look like a trusted node who doesn't broadcast the transactions at all and just keeps them centrally, then mines or broadcasts the final version themselves. Client apps would just be configured to connect directly to that node.

Making that more competitive means having more such nodes/miners, until eventually you have a network of miners that are regulated by identity and bannable and don't share the tx's outside their network. That probably gets you 95% of the benefit of the old model with maybe 150% (wild ass guess) of the costs. "Identity" in this case can mean lots of fancy crypto things beyond old-fashioned govt name+address style.

I don't think that'd be just an expensive and inefficient PayPal, as you'd still have the key difference that simplifies so much - the trusted third party doesn't hold any funds on deposit and can't directly steal/lend/gamble with any funds. To earn money by being corrupt requires complicated schemes where they strike secret deals to favour one party or another, and that corruption can then be easily detected and published, so it seems like the risk is much lower.

Bitcoin is already a pretty complex ecosystem with different kinds of trust and decentralisation models in use. I see the next 5-10 years as a giant cost optimisation experiment .... where are the best settings of the various decentralisation/speed/fees/complexity/identity knobs for different kinds of people?

On Fri, Jan 09, 2015 at 01:40:53PM +0200, Nathan Cook wrote:

Would you mind doing up some actual scriptPubKeys/transactions using this idea as an example? I think it'd make the review process a lot easier for everyone if there was something more concrete. (equally, sorry I haven't had a chance to look at this, very busy for the rest of the month)

You may find my CLTV-using micropayment channel demo useful reference material too:

https://github.com/petertodd/checklocktimeverify-demos/blob/master/micropayment-channel.py

> A limitation on most existing micropayment channel ideas is that payments
> can only flow in one direction. This is because the payment receiver can
> sign -any- transaction you send them, not just the most recent one, and so
> it's possible to just sign the transaction transferring the largest amount
> into their control. This is easily remedied by opening a second payment
> channel in the opposite direction, but now both parties have to deposit
> funds over the lifetime of the two channels. If one party doesn't know
> ahead of time whether or not the other party will go into credit, having
> only one channel may save the use of a deposit.