From aj at erisian.com.au  Sat Nov  3 04:43:32 2018
From: aj at erisian.com.au (Anthony Towns)
Date: Sat, 3 Nov 2018 14:43:32 +1000
Subject: [Lightning-dev] BOLT11 In the World of Scriptless Scripts
In-Reply-To: <87d0rodppt.fsf@rustcorp.com.au>
References: <87sh0ke4rt.fsf@rustcorp.com.au>
	<20181102031945.uyf74qr73wspsktb@erisian.com.au>
	<87d0rodppt.fsf@rustcorp.com.au>
Message-ID: <20181103044332.el2ro3sso3rcmwpg@erisian.com.au>

On Fri, Nov 02, 2018 at 03:45:58PM +1030, Rusty Russell wrote:
> Anthony Towns <aj at erisian.com.au> writes:
> > On Fri, Nov 02, 2018 at 10:20:46AM +1030, Rusty Russell wrote:
> >>         There's been some discussion of what the lightning payment flow
> >> might look like in the future, and I thought I'd try to look forwards so
> >> we can avoid painting ourselves into a corner now.  I haven't spent time
> >> on concrete design and implementation to be sure this is correct,
> >> however.
> > I think I'd like to see v1.1 of the lightning spec include
> > experimental/optional support for using secp256k1 public/private keys
> > for payment hashes/preimages. That assumes using either 2-party ECDSA
> > magic or script magic until it's viable to do it via Schnorr scriptless
> > scripts, but that seems like it's not totally infeasible?
> Not totally infeasible, but since every intermediary needs to support
> it, I think we'd need considerable buy-in before we commit to it in 1.1.

"every intermediary" just means "you have to find a path where every
channel supports it"; nodes/channels that aren't in the route you choose
aren't a problem, and can still pass on the gossiped announcements,
I think?

> > I think the
> > components would need to be:
> >  - invoices: will the preimage for the hash be a secp256k1 private key
> >    or a sha256 preimage? (or payer's choice?)
> From BOLT11:
>    The `p` field supports the current 256-bit payment hash, but future
>    specs could add a new variant of different length, in which case
>    writers could support both old and new, and old readers would ignore
>    the one not the correct length.
> So the plan would be you provide two `p` fields in transition.

Yeah, that sounds workable.

> >  - channel announcements: do you support secp256k1 for hashes or just
> >    sha256?
> Worse, it becomes "I support secp256k1 with ECDSA" then a new "I support
> secp256k1 with Schnorr".  You need a continuous path of channels with
> the same feature.

I don't think that's correct: whether it's 2p-ecdsa, Schnorr or script
magic only matters for the two nodes directly involved in the channel
(who need to be able to understand the commitment transactions they're
signing, and extract the private key from the on-chain tx if the channel
gets unilaterally closed). For everyone else, they just need to know that
they can put in a public key based HTLC, and get back the corresponding
private key when the HTLC goes through.

It's also (theoretically) upgradable afaics: if two nodes have a channel
that supports 2p-ecdsa, and eventually both upgrade to support segwit
v1 scriptless schnorr sigs or whatever, they just need to change the
addresses they use in new commitment txs, even for existing HTLCs.

> > Even if you calculate r differently, I don't think you can do this
> > without Bob and Alice interacting to get the nonce R prior to sending
> > the transaction, which seems effectively the same as having dynamic
> > invoice hashes, though.
> I know Andrew Poelstra thought it was possible, so I'm going to leave a
> response to him :)

AFAICT, in general, if you're going to have n signatures with a public
key P, you need to generate the n R=r*G values from n*32B worth of random data,
that's previously unknown to the signature recipients. If you've got
less than that, then you will have calculated each R by doing something
like based on <n*32B of data you've been given:

    R = a*R1 + b*R2 + ..

and the n signatures you eventually receive will give you n simultaneous
linear equations along the lines of:

    s = (a*r1 + b*r2 + c*r3 + ..) + H(..)*p

with <= n unknowns (p and less than n r1,r2,.. values). (If you don't
known the values a,b,c you won't be able to calculate the R values for
your signatures in the first place)

Willing to be surprised by a different approach, but I'm pretty
skeptical...


I think it makes sense to think of proof-of-payment in terms of a
verification algorithm (that a third party court could use), that takes:

  m - the invoice details, eg
      "aj paid $11 for stickers to be delivered to Australia"
  P - the pubkey of the vendor
  sig - some signature

With the current SHA256 preimages, you can make sig=(R,s,pre)
where the sig is valid if:

  s*G = R + H(P,R,m+SHA256(pre))*P

If you share R,s,SHA256(pre) beforehand, the payer can tell they'll have
a valid signature if they pay to SHA256(pre). That's a 96B signature,
and it requires "pre" be different for each sale, and needs pre-payment
interactivity to agree on m and communicate R,s back to the payer.

With seckp256k1 preimages, it's easy to reduce that to sig=(R,s),
and needing to communicate an R to the payer initially, who can then
calculate S and send "m" along with the payment.


Maybe it makes sense to disambiguate the term "invoice" -- when you don't
know who you might be giving the goods/service to, call it an "offer",
which can be a write-once/accept-by-anyone deal that you just leave on
a webpage or your email signature; but an "invoice" should be specific
to each individual payment, with a "receipt" provided once an invoice
is paid.


AMP:

> I think a general scheme is: payer creates a random group-marker, sends
> <group-marker><32-byte-randomness>[encrypted data...] in each payment.
> Receipient collects payments by <group-marker>, xoring the
> <32-byte-randomness>; if that xor successfully decrypts the data, you've
> got all the pieces.
> 
> (For low-AMP, you use payment_hash as <group-marker>, and just use
> SHA256(<xor-of-all-randomness><32-byte-randomness>) as the per-payment
> preimage so no [encrypted data] needed).

Hmm, right, I've got decorrelation and AMP combined in my head. I'm also
a bit confused about what exactly you mean by "low-AMP"...

Rereading through the AMP threads, Christian's post makes a lot of sense
to me:

https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-February/001023.html

I'm not really seeing the benefits in complicated AMP schemes without
decorrelation...

It seems to me like there are three levels that could be implemented:

 - laolu/conner: ("low AMP" ?)
    works with sha256
    some privacy improvement
    loses proof-of-payment
    can't claim unless all payments arrive

 - just send multiple payments with the same hash:
    works with sha256
    privacy not improved much (some intermediary nodes no longer know
      full invoice value)
    can claim partial payments as soon as they arrive
    accepting any partial payment provides proof-of-payment

 - secp256k1: ("high AMP" ?)
    needs secp256k1 preimages
    works fine with decorrelation improving privacy at every step
    can set it up so can only claim once all partial payments arrive
    accepting partial payment provides proof-of-payment

In theory, both "just send multiple payments" and "secp256k1" could have
splitting and joining at any hop, if we could encode the instructions
on how to do that in the onion message; joining is probably easy, but
splitting seems like it might be hard?

Cheers,
aj