[Lightning-dev] Scriptless Scripts with ECDSA

Thu May 24 16:20:57 UTC 2018

Hello,

I know it is kind of a late reply, but my co-authors and I have been
working hard to get ready an extended version of the paper for this
work. The paper is now available at https://eprint.iacr.org/2018/472

In this paper, we describe in detail the scriptless script (SS) ECDSA
construction and formally prove its security and privacy guarantees.
Additionally, we describe several other constructions of interest for
the LN:

 - The SS Schnorr, initially proposed by A. Poelstra. We formally
describe the protocol and prove its security and privacy guarantees

 - Interestingly, we show that it is possible to combine SS ECDSA and SS
Schnorr without losing security or privacy. This allows interoperability
between different implementations.

 - A framework to combine script-based cryptographic locks using
partially homomorphic one-way functions.

 - Possible applications. For instance, SS ECDSA could be used today in
Bitcoin to perform atomic swaps where the resulting transaction no
longer reveals the cryptographic condition. Instead, it is embedded in a
regular ECDSA signature. This provides several advantages such as
reduced transaction size and better privacy/fungibility among others.

Please, let us know any comment/feedback that you might have.

Thanks,
Pedro.

On 5/8/18 11:59 PM, ZmnSCPxj via Lightning-dev wrote:
> 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 degrades functionality and privacy (but
> only to the level that we have today!).  Hashlocking can have the exact
> hash function changed reasonably easily, modulo blockchain-layer
> infrastructure change (i.e. the base layer needs to implement the
> replacement before upper layers can use them), plus the need to update
> invoice formats to use a different hash function.
> 
>> If this is just a toy, then never mind. If we don't expect the world
>> to ever depend on this for anything important, then there is no need
>> to fret over the finite lifespan of primitives. Or maybe we can just
>> hope, that this time will be unlike all the others in the history of
>> cryptography.
>>
>> Otherwise, consider for example the history of DES, or SHA-1. Those
>> are scenarios where we saw the problems coming far enough in advance
>> to transition. Sure, it would be better if we had redundant primitives
>> for every function in the actual code itself - just in case of either
>> a sudden, or else a secret, break. In fact, we should aim to one day
>> get there. But for now, let's at least have functionally equivalent
>> backups for every function, even if only on paper. When exciting new
>> functionality is invented but based on a mathematically unproven
>> assumption, then let's wait to build on it until after at least one or
>> two mathematically dissimilar assumptions have been found as
>> alternative backup foundation. The global economy deserves such
>> careful hands, I think, or else we do not deserve it.
> 
> Naively, it seems to me that there are already multiple ways to do
> Scriptless.
> 
> (I am not a mathematician and not a cryptographer; I am merely a
> dilettante, and probably massively misunderstand this)
> 
> 1.  The classic one which takes advantage of Bellare-Neven signature
> linearity, where you provide an adaptor signature that can have magical
> mathematic operations with the actual signature to reveal the private key.
> 2.  Nonce reuse, where you provide a different message signed using the
> private key and a specific nonce, and commit that the actual transaction
> gets signed with the same private key and the same nonce used in the
> first message, which in combination with magical mathematic operations
> will reveal the private key.
> 3.  The Paillier cryptosystem thing that the ECDSA Scriptless Script
> uses, where you encrypt the private key in the Paillier cryptosystem,
> provide it, and you can have magical mathematic operations reveal the
> private key when you sign with it.
> 
> All of the above still depend on the Discrete Log Problem being Hard.  I
> am uncertain if they can be adapted in a Lattice-based signing
> algorithm; the first one almost certainly cannot, I am unsure for the
> second and third.
> 
> Regards,
> ZmnSCPxj
> 
> 
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180524/01971226/attachment.sig>