Re: [Lightning-dev] Scriptless Scripts with ECDSA

[ZmnSCPxj via Lightning-dev]

Good morning Benjamin,

Your caution is laudable, I think.

> Yes, bitcoin is wise to at least hash the pub key until use. Granted, 
> lightning (necessarily?) risks public key exposure, but in a pinch there are 
> other signature algorithms for lightning to move to.

Lightning cannot *quickly* move to a new signature algorithm.  At the minimum 
you need to wait for the signature algorithm to get widely deployed in the 
base-layer blockchain, then LN implementations will need to scramble to 
implement the new signature algorithm.  Then all LN users need to update, close 
existing channels, and reopen new ones.

Another issue is that the message transport is encrypted using a shared key 
derived from the node-identity public keys.  If a break lets attackers derive 
private keys from public keys, then it is possible for any LN node to have its 
communications spoofed, meaning any mitigation may very well be obviated: 
channels need to be re-anchored cooperatively, but how do you know you are 
cooperating with the other node in the channel rather than the attacker, if the 
attacker can derive the private key from the other node public key?

The sudden influx of close followed by open transactions will probably 
massively load the blockchain layer, too.

In that case, perhaps a concrete proposal would be to prepare a new message 
protocol for reanchoring transactions:

1.  A new "signing algo" concept, which is effectively an enumeration that will 
be extended later, e.g. 0 => ECDSA on secp256k1, 1->255 => reserved.
2.  `open_channel` would need to provide a `signing_algo` that underlies the 
commitment structure at a lower level.
3.  A new `reopen_channel` to move a channel from one signing algorithm to 
another, plus a reply to accept the switch and provide new commitment 
transactions for both sides.  This is effectively a `shutdown` followed by the 
`closing_signed` negotiation followed by a new `open_channel`, but with the 
resulting transaction cutting through a close and a funding transaction (in 
order to reduce blockspace competition).
4.  A new `reopen_channel_rbf`, possibly including a proof that an existing 
reopen channel has replaced (e.g. sending the actual transaction that spends 
the funding outpoint and bids a higher feerate than the last re-open 
transaction), to RBF the re-open transaction that moves from one signing 
algorithm to another; better to lose the channel to miners as fees then to let 
a thief succeed (i.e. scorched earth). This is complicated by the fact that the 
re-open has to be signed cooperatively by two parties whereas a thief can be 
singular and thus faster in replacing transactions.  But at least better to 
make an effort than to just give up!

>
>
>> In the case of Lightning, the attack scenario on scriptless scripts is that 
>> a peer is going to use a quantum computer to steal all live payments routed 
>> through them from their senders before they get to the recipient. This would 
>> be bad, but not catastrophic, and once it is recognized that the attack is 
>> possible, insecure channels could be closed.
>
> All channels would become insecure, the very premise of lightning would thus 
> break, which is only a problem if the world came to depend on it. But then 
> why try a thing, unless you plan to maybe succeed? Also, we don't know that a 
> quantum computer is necessary. SHA-1 was secure, until it wasn't, no quantum 
> computer was needed to break it.
>
>> But furthermore, an attacker with a quantum computer could just steal the 
>> multisig funding output directly instead of attacking scriptless scripts.
>
> Absolutely, and today there is no redundant signature of different algorithm, 
> in the code. (That would be better.) But even so, how hard would it be to 
> swap one signature algorithm for another? Then users "just" move their funds 
> to multisig addresses under the new algorithm.
>
>> So additional protocol changes relying on the DL assumption don't bother me 
>> in the least.
>
> I don't follow the logic. If today we would have a frantic scramble in event 
> of sudden DL weakness, as indeed seems probable, it does not then follow that 
> we might as well design DL weakness to become a fundamentally unsurvivable 
> problem. DL signatures bother me less because lattice cryptography can serve 
> as backup. Scriptless scripts worry me because I just don't know what the 
> backup is, when (not if) DL falls. Perhaps scriptless scripts can be done 
> with lattices(?), in which case I am simply unaware - but some such backup 
> should be identified, at least at a conceptual level, prior to use.

At least on Lightning, Scriptless Script can only be used for payment 
forwarding.  Thus the vulnerability is time-bounded.  Further, while Scriptless 
Script enables new applications such as within-path decorrelation (privacy 
boost) and multi-path payments with proof-of-payment (functionality boost), we 
*can* fall back to the simple hashlocking we use now, which 

Re: [Lightning-dev] Scriptless Scripts with ECDSA

[Benjamin Mord]

If I'm not mistaken, the scriptless scripts concept (as currently
formulated) falls to Schor's algorithm, and at present there is no
alternative implementation of the concept to fall back on. Correct? Lest we
build a house of cards, I'd strongly urge everyone to not depend on
functional concepts whose underlying cryptographic primitives cannot be
swapped in an emergency.

Sure, we use ecdsa for example (which is also vulnerable to Schor's
algorithm), but in contrast to scriptless scripts we have a variety of
backup primitives at our disposal that fulfill the same functional
objective.

If scriptless scripts are found possible under lattice-based cryptography
for example, that would be something I suppose. The functional concept of
scriptless scripts is indeed very awesome - we just need to add some
cryptographic conservatism before we build on it.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] Scriptless Scripts with ECDSA

[Olaoluwa Osuntokun]

FWIW, Conner pointed out that the initial ZK Proof for the correctness of
the
Paillier params (even w/ usage of bulletproofs) has multiple rounds of
interaction,
iirc up to 5+ (with additional pipelining) rounds of interaction.

-- Laolu

On Mon, May 7, 2018 at 5:14 PM Olaoluwa Osuntokun  wrote:

> Actually, just thought about this a bit more and I think it's possible to
> deploy this in unison with (or after) any sort of SS based on schnorr
> becomes
> possible in Bitcoin. My observation is that since both techniques are
> based on
> the same underlying technique (revealing a secret value in a signature) and
> they center around leveraging the onion payload to drop off a payment point
> (G*a, or G*a_1*a_2*a_3, etc), then the disclosure within the _links_ can be
> heterogeneous, as the same secret is still revealed in an end-to-end
> matter.
>
> As an illustration, consider: A <-> B <-> C. The A <-> B link could use
> the 2pc
> pailier technique, while the B <-> C link could use the OG SS technique
> based
> on schnorr. If i'm correct, then this would mean that we can deploy both
> techniques, without worrying about fragmenting the network due to the
> existence
> of two similar but incompatible e2e payment routing schemes!
>
> -- Laolu
>
>
> On Mon, May 7, 2018 at 4:57 PM Olaoluwa Osuntokun 
> wrote:
>
>> Hi Pedro,
>>
>> Very cool stuff! When I originally discovered the Lindell's technique, my
>> immediate thought was the we could phase this in as a way to
>> _immediately_ (no
>> additional Script upgrades required), replace the regular 2-of-2
>> mulit-sig with
>> a single p2wkh. The immediate advantages of this would: be lower fees for
>> opening/closing channels (as the public key script, and witness are
>> smaller),
>> openings and cooperative close transactions would blend in with the
>> anonymity
>> set of regular p2wkh transactions, and finally the htlc timeout+success
>> transactions can be made smaller as we can remove the multi-sig. The
>> second
>> benefit is nerfed a bit if the channel are advertised, but non-advertised
>> channels would be able to take advantage of this "stealth" feature.
>>
>> The upside of the original application I hand in mind is that it wouldn't
>> require any end-to-end changes, as it would only be a link level change
>> (diff
>> output for the funding transaction). If we wanted to allow these styles of
>> channels to be used outside of non-advertised channels, then we would
>> need to
>> update the way channels are verified in the gossip layer.
>>
>> Applying this to the realm of allowing us to use randomized payment
>> identifiers
>> across the route is obviously much, much doper. So then the question
>> would be
>> what the process of integrating the scheme into the existing protocol
>> would
>> look like. The primary thing we'd need to account for is the additional
>> cryptographic overhead this scheme would add if integrated. Re-reviewing
>> the
>> paper, there's an initial setup and verification phase (which was omitted
>> from
>> y'alls note for brevity) where both parties need to complete before the
>> actually signing process can take place. Ideally, we can piggy-back this
>> setup
>> on top of the existing accept_channel/open_channel dance both sides need
>> to go
>> through in order to advance the channel negotiation process today.
>>
>> Conner actually started to implement this when we first discovered the
>> scheme,
>> so we have a pretty good feel w.r.t the implementation of the initial set
>> of
>> proofs. The three proofs required for the set up phase are:
>>
>>   1. A proof that that the Paillier public key is well formed. In the
>> paper
>>   they only execute this step for the party that wishes to _obtain_ the
>>   signature. In our case, since we'll need to sign for HTLCs in both
>>   directions, but parties will need to execute this step.
>>
>>   2. A dlog proof for the signing keys themselves. We already do this
>> more or
>>   less, as if the remote party isn't able to sign with their target key,
>> then
>>   we won't be able to update the channel, or even create a valid
>> commitment in
>>   the first place.
>>
>>   3. A proof that value encrypted (the Paillier ciphertext) is actually
>> the
>>   dlog of the public key to be used for signing. (as an aside this is the
>> part
>>   of the protocol that made me do a double take when first reading it:
>> using one
>>   cryptosystem to encrypt the private key of another cryptosystem in
>> order to
>>   construct a 2pc to allow signing in the latter cryptosystem! soo
>> clever!)
>>
>> First, we'll examine the initial proof. This only needs to be done once
>> by both
>> parties AFAICT. As a result, we may be able to piggyback this onto the
>> initial
>> channel funding steps. Reviewing the paper cited on the Lindell paper
>> [1], it
>> appears this would take 1 RTT, so this shouldn't result in any additional
>> round
>> trips during the funding process. We should be 

Re: [Lightning-dev] Scriptless Scripts with ECDSA

[Olaoluwa Osuntokun]

Hi Pedro,

Very cool stuff! When I originally discovered the Lindell's technique, my
immediate thought was the we could phase this in as a way to _immediately_
(no
additional Script upgrades required), replace the regular 2-of-2 mulit-sig
with
a single p2wkh. The immediate advantages of this would: be lower fees for
opening/closing channels (as the public key script, and witness are
smaller),
openings and cooperative close transactions would blend in with the
anonymity
set of regular p2wkh transactions, and finally the htlc timeout+success
transactions can be made smaller as we can remove the multi-sig. The second
benefit is nerfed a bit if the channel are advertised, but non-advertised
channels would be able to take advantage of this "stealth" feature.

The upside of the original application I hand in mind is that it wouldn't
require any end-to-end changes, as it would only be a link level change
(diff
output for the funding transaction). If we wanted to allow these styles of
channels to be used outside of non-advertised channels, then we would need
to
update the way channels are verified in the gossip layer.

Applying this to the realm of allowing us to use randomized payment
identifiers
across the route is obviously much, much doper. So then the question would
be
what the process of integrating the scheme into the existing protocol would
look like. The primary thing we'd need to account for is the additional
cryptographic overhead this scheme would add if integrated. Re-reviewing the
paper, there's an initial setup and verification phase (which was omitted
from
y'alls note for brevity) where both parties need to complete before the
actually signing process can take place. Ideally, we can piggy-back this
setup
on top of the existing accept_channel/open_channel dance both sides need to
go
through in order to advance the channel negotiation process today.

Conner actually started to implement this when we first discovered the
scheme,
so we have a pretty good feel w.r.t the implementation of the initial set of
proofs. The three proofs required for the set up phase are:

  1. A proof that that the Paillier public key is well formed. In the paper
  they only execute this step for the party that wishes to _obtain_ the
  signature. In our case, since we'll need to sign for HTLCs in both
  directions, but parties will need to execute this step.

  2. A dlog proof for the signing keys themselves. We already do this more
or
  less, as if the remote party isn't able to sign with their target key,
then
  we won't be able to update the channel, or even create a valid commitment
in
  the first place.

  3. A proof that value encrypted (the Paillier ciphertext) is actually the
  dlog of the public key to be used for signing. (as an aside this is the
part
  of the protocol that made me do a double take when first reading it:
using one
  cryptosystem to encrypt the private key of another cryptosystem in order
to
  construct a 2pc to allow signing in the latter cryptosystem! soo clever!)

First, we'll examine the initial proof. This only needs to be done once by
both
parties AFAICT. As a result, we may be able to piggyback this onto the
initial
channel funding steps. Reviewing the paper cited on the Lindell paper [1],
it
appears this would take 1 RTT, so this shouldn't result in any additional
round
trips during the funding process. We should be able to use a Paillier
modulos
of 2048 bits, so nothing too crazy. This would just result in a slightly
bigger
opening message.

Skipping the second proofs as it's pretty standard.

The third proof as described (Section 6 of the Lindell paper) is
interactive.
It also contains a ZK range proof as a sub-protocol which as described in
Appendix A is also interactive. However, it was pointed out to us by Omer
Shlomovits on the lnd slack, that we can actually replace their custom range
proofs with Bulletproofs. This would make this section non-interactive,
allowing the proof itself to take 1.5 RTT AFAICT. Additionally, this would
only
need to be done once at the start, as AFIACT, we can re-use the encryption
of
the secp256k1 private key of both parties.

The current channel opening process requires 2 RTT, so it seems that we'd be
able to easily piggy back all the opening proofs on top of the existing
funding
protocol. The main cost would be the increased size of these opening
messages,
and also the additional computational cost of operations within the Paillier
modulus and the new range proof.

The additional components that would need to be modified are the process of
adding+settling an HTLC, and also the onion payload that drops off the point
whose dlog is r_1*alpha. Within the current protocol, adding and settling an
HTLC are more or less non-interactive, we have a single message for each,
which
is then staged to be committed in new commitments for both parties. With
this
new scheme (if I follow it correctly), adding an HTLC now requires N RTT:
  1. Alice sends A = G*alpha to Bob.