[Lightning-dev] Theory: Proofs of Payment are Signatures

[ZmnSCPxj via Lightning-dev]

Introduction


Lightning provides proof-of-payment for standard forms of payment, but does not 
provide it for keysend or non-high hash-based AMP.

Let us consider, then, what exactly a proof-of-payment even *is*.

Lamport Signatures
==

One of the earliest cryptographic digital signing schemes is the Lamport 
Signature Scheme.

With Lamport signatures, you need to define:

* A trapdoor/one-way hash function, which has output bits `n`.
* A number of bits in the message, `m`.

Then, to generate a private key:

* Generate 2 * `m` random `n`-bit numbers, which are preimages.

Then, to derive a public key from the private key:

* Hash the above 2 * `m` preimages.

To sign a message:

* For each bit `b` of the message:
  * If the bit is clear, send the `b` * 2 + 0 preimage (this is 0-indexed, by 
the way).
  * If the bit is set, send the `b` * 2 + 1 preimage.

To validate, simply check that the received preimage hashes to the 
corresponding hash in the public key.

Hash-based Lightning Payments
=

In current Lightning, a BOLT11 invoice provides a single hash.
Then the payer creates an outgoing HTLC, which is transported over the network 
and reaches the payee, who then provides the preimage to that hash.

>From a certain point of view, one can consider that the preimage revelation is 
>a Lamport signature with a 0-bit message.
Instead of signing a message, it is the *existence* of a signature that 
matters, and that is what proof-of-payment is.
In that degenerate case of a 0-bit message, a preimage and its hash can serve 
as a Lamport signature.

A BOLT11 invoice is signed with ECDSA secp256k1.
One can consider that the hash embedded in the BOLT11 invoice is a delegated 
key, and that the BOLT11 mechanism is really a key delegation mechanism.
The payee signs the BOLT11 invoice using ECDSA secp256k1 using its node id as 
pubkey, specifying a 0-bit Lamport public key (the hash in the BOLT11), and 
delegating responsibility for that particular invoice to that key.
Then, when the payee (or its representative on the network) gets paid, it signs 
the Lamport signature using the delegated key by revealing the preimage.

>From this point-of-view, as well, keysend and base AMP do provide a 
>proof-of-payment, it is just the proof-of-payment is the "wrong" direction: 
>the payee gets a proof-of-payment that it got paid, as it is provided the 
>public key (the hash) and the preimage (the 0-bit Lamport signature).
The payee gets proof that it got paid, but typically we expect that people will 
charge (i.e. demand to get paid) for their autographs, so a payee getting a 
signature from the payer does not quite fit the expected economics.

A Scheme For Point-based Payments?
==

Given the above idea, would it be useful to consider that a PTLC-based LN 
should explicitly use Schnorr signatures for proof-of-payment?

Schnorr signatures are `(R, s)`, and once `R` has been established, we do know 
that we can implement a pay-for-signature to acquire the `s` using PTLCs, which 
can be transported across the network.

>From this point of view, then, proof-of-payments are signatures `(R, s)`, with 
>`s` being acquired using PTLCs over the network.
What is needed then is to somehow transport `R`.

For example, a PTLC-based invoice scheme might commit to a specific `R` in the 
invoice.
Then the public key is "really" the payee node public key, *and* this specific 
`R`, which forms a one-time signature scheme (as reuse of `R` is unsafe).
This is similar to the current BOLT11 scheme in that the hash is "really" a 
0-bit Lamport public key, which is similarly one-time-use.
Then the invoice represents a delegation of the node public key to the 
augmented node id + `R` public key.

Additionally, we may provide a mechanism to request for an `R` from the payee, 
together with a message to be signed.
The payee may then use some determinstic `R` generation scheme to provide `R` 
to the payer.

*How* these mechanisms might actually be *used*, I am significantly less 
certain about, but perhaps application developers on top of Lightning may have 
some ideas that can be shoehorned into this.

At its minimum, even a simple scalar-behind-this-point PTLC payment scheme 
could still work for proof-of-payment, as the function `f(x) = x * G` is a 
perfectly fine trapdoor function for the purposes of Lamport signing, so there 
is no real need to have "full" signatures as the basic mechanism in a 
PTLC-based Lightning Network.

Forwarding nodes, of course, need not know about this, but we do need to 
consider whether support for this would be useful at the payer and payee, and 
in our APIs exposed to applications built on top of Lightning.

___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] Stateless invoices with proof-of-payment

[Joost Jager]

>
> > The conventional approach is to create a lightning invoice on a node and
> > store the invoice together with order details in a database. If the order
> > then goes unfulfilled, cleaning processes remove the data from the node
> > and database again.
>
> > The problem with this setup is that it needs protection against unbounded
> > generation of payment requests. There are solutions for that such as rate
> > limiting, but wouldn't it be nice if invoices can be generated without
> the
> > need to keep any state at all?
>
> Isn't this ultimately an engineering issue? How much exactly is "too much"
> in this case? Invoices are relatively small, and also don't even
> necessarily
> need to be ever written to disk assuming a slim expiration window. It's
> likely the case that a service can just throw everything in Redis and call
> it a day. In terms of rate limiting a service would likely already need to
> implement that on the API/service level to mitigate app level DoS attacks.
>

It is an engineering issue and indeed, you can use something like Redis to
solve it. Today's internet is probably doing the same thing and it seems to
work so far. With lightning though, there is another option. And it could
be an engineering advantage to not have to keep that state. I can also
imagine that slim expiration windows aren't always desirable. Thinking of
personalized payment requests in mass mailings for example.

So yes, this is not about new functionality, but I still think it is worth
exploring the path.

As far as pre-images go, this can already be "stateless" by generating a
> single random seed (storing that somewhere w/ a counter likely) and then
> using shachain or elkrem to deterministically generate payment hashes. You
> can then either use the payment_addr/secret to index into the hash chain,
> or
> have the user send some counter extracted from the invoice as a custom
> record. Similar schemes have been proposed in the past to support "offline"
> vending machine payments.
>

What would be the advantage of using elkrem or shachain compared to just
using `H(receiver_node_secret | payment_secret)` as the preimage? The
sender knows all the preimages already anyway, they aren't revealed one by
one by another party.

Also I think it could be beneficial to add more data into that hash
function such as the payment amount and the order details. With that, the
receiver knows that they received a payment for something that they offered
in the past, without having the actual record of that stored somewhere.


> Taking it one step further, the service could maintain a unique
> elkrem/shachain state for each unique user, which would then allow them to
> also collapse the pre-image into the hash chain, which lets them save space
> and be able to reproduce a given "proof that someone in the world paid"
> (that no service/wallet seems to accept/generate in an
> automated/standardized manner) statement dynamically
>

Can you provide an example to clarify this idea a bit more? If I read it
correctly, the goal is for the receiver to produce a proof that someone in
the world paid. But how can this be proven if the receiver can generate all
the preimages that they want?

Joost
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev