[Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Nathan Cook]

[-- Attachment #1: Type: text/plain, Size: 5467 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 6160 bytes --]

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 616 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 959 bytes --]

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Jeff Garzik]

[-- Attachment #1: Type: text/plain, Size: 1579 bytes --]

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


-- 
Jeff Garzik
Bitcoin core developer and open source evangelist
BitPay, Inc.      https://bitpay.com/

[-- Attachment #2: Type: text/html, Size: 2602 bytes --]

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1739 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 2055 bytes --]

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 3648 bytes --]

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?

[-- Attachment #2: Type: text/html, Size: 4045 bytes --]

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[odinn]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

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
-----BEGIN PGP SIGNATURE-----

iQEcBAEBCgAGBQJUsj9+AAoJEGxwq/inSG8Cvu8H/RutYcVPdN+GrtAYxNkm2x7n
v/NtBIZwGs7iN6g14Te/ynEfBQRzYwVABL+d1nEuNdlYl6IB4mCXkFrz7hlFJNgK
2WOq4iKApS1tV9MFAcaxnYy6W8z5T8VpQRqxNbbFEG145cGP2l/5CYwXOmPOBdp7
qTnLs9oVyhixcfb/piFhd/4xRvlvwxVyvCamrAXBUIpgpW/VB/kfG8ikCazvcJB6
lSY+CogSGqObjlO7PhKcsZz/gTNrSIp40upyktfqZvQxWLp4WR7+GYz7vUXoofQO
Obt3ya6lZBLLL0EHYkJzAiKRy4aoIgIUzyshIHTdiQIwZC6HWnv2++sJdneng8g=
=+e6h
-----END PGP SIGNATURE-----

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Bi-directional micropayment channels with CHECKLOCKTIMEVERIFY

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1302 bytes --]

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.

-- 
'peter'[:-1]@petertodd.org
00000000000000000d41f9ac3e2a4a621769f4f077c490bf2b2a967ebfd04e42

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]