Schnorrless Scriptless Scripts

Posted by: Adam Gibson | in Bitcoin, Cryptography | 1 month, 3 weeks ago | 0 comments

Introduction

The weekend of April 4th-5th 2020 we had a remote "Lightning Hacksprint" organized by the ever-excellent Fulmo, one Challenge was related to "Payment Points" (see here; see lots more info about the hacksprint at that wiki) and was based around a new innovation recently seen in the world of adaptor signatures. Work was led by Nadav Kohen of Suredbits and Jonas Nick of Blockstream; the latter's API for the tech described below can be seen currently as a PR to the secp256k1 project here. The output from Suredbits was a demo as show here on their youtube, a PTLC (point time locked contract, see their blog for more details on that).

I will not focus here on either the proof of concept code, nor the potential applications of this tech (which are actually many, not only LN, but also Discreet Log contracts, various design of tumbler and others), but entirely on the cryptography.

What you can do with Schnorr adaptors

Previous blog posts have covered in some detail the concept of adaptor signatures, how they are simply realizable using the Schnorr signature primitive. Also noted here and elsewhere is that there are techniques to create the same effect using ECDSA signature, but involving considerable additional crypto machinery (Paillier homomorphic encryption and certain zero knowledge (range) proofs). This technique is laid out in this brief note, fleshed out fully in this cryptographic construction from Lindell, paired with this paper on multihop locks (which represents a very important theoretical step forward for Lightning channel construction). The problem with that "tech stack" is the complexity in the Lindell construction, as mentioned.

A recent paper by Lloyd Fournier represents a very interesting step forward, at least in a certain direction: it allows "single signer" ECDSA adaptor signatures. The scare quotes in the previous sentence represent the fact that the use of such adaptor signatures would not literally be single signer - it would be in the context of Bitcoin's OP_CHECKMULTISIG, most typically 2 of 2 multisig, so the same as the current implementation of the Lightning network, in which a contract is enforced by having funds controlled by both parties in the contract. Here, what is envisaged is not a cooperative process to construct a single signature (aggregated), but each party can individually create adaptor signatures with signing keys they completely control. That this is possible was a big surprise to me, and I think others will be unclear on it too, hence this blog post after a week or so of study on my part.

Let's remember that the Schnorr adaptor signature construction is:

\(\sigma'(T, m, x) = k + H(kG+T||xG||m)x\)

where \(k\) is the nonce, \(x\) is the private (signing) key and \(T\) is the 'adaptor point' or just adaptor. The left-hand-side parentheses are important: notice that you don't need the discrete log of the point T to construct the adaptor signature. But you do need the signing key \(x\). Or wait .. do you?

As I explained last year here it's technically not the case: you can construct an adaptor signature for signing pubkey \(P\) for which you don't know \(x\) s.t. \(P=xG\), with a fly in the ointment: you won't be able to predict the adaptor \(T\) or know its discrete log either (this makes it un-dangerous, but still an important insight; I was calling this "forgeability" but more on that later).

How you ask? To summarize the mastodon post:

\(\stackrel{$}{\leftarrow} q, Q=qG, \quad \mathrm{assume}\quad R+T =Q\)

\(\Rightarrow \sigma' G= R + H(P,Q,m)P\)

\(\stackrel{$}{\leftarrow} \sigma' \quad \implies R = s'G - H(P,Q,m)P \implies T = Q-R\)

Thus anyone can publish an adaptor signature \((T, \sigma')\) on any message \(m\) for any pubkey \(P\) at any time. It really isn't a signature.

And equally obvious is that this does not allow the "forger" to complete the adaptor into a full signature (\(\sigma = \sigma' + t\)) - because if he could, this would be a way to forge arbitrary Schnorr signatures!

With the caveat in the above little mathematical vignette aside, we note that the bolded phrase above is the crucial point: adaptors can be created by non-secret owners, for secret owners to complete.

Adaptors in ECDSA with less wizardry

I was alerted to this trick via this mailing list post and the work of the Suredbits guys, in particular Nadav Kohen, who blogs on payment points, DLCs and related topics here. The idea can be summarised as "tweak the nonce multiplicatively instead of linearly". Take the following notation for the base (complete) ECDSA signature:

\(\sigma = k^{-1}\left(\mathbb{H}(m) + R_{\mathrm{x}}x\right) \)

Here we're using the most common, if sometimes confusing notation. As usual \(k\) is the nonce (generated deterministically usually), \(R=kG\), \(m\) is the message and \(x\) is the private signing key whose public key by convention is \(P\). Meanwhile \(R_{\mathrm{x}}\) indicates the x-coordinate of the curve point \(R\), with the usual caveats about the difference between the curve order and the order of the finite field from which the coordinates are drawn (feel free to ignore that last part if it's not your thing!).

Now clearly you cannot just add a secret value \(t\) to the nonce and expect the signature \(\sigma\) to be shifted by some simple factor. Multiplication looks to make more sense, since after all the nonce is a multiplicative factor on the RHS. But it's not so simple, because the nonce-point appears as the term \(R_{\mathrm{x}}\) inside the multiplied factor. The clever idea is how to get around this problem. We start by defining a sort-of "pre-tweaked" nonce:

\(R' = kG\)

and then the real nonce that will be used will be multiplied by the adaptor secret \(t\):

\(R = kT = ktG\)

Then the adaptor signature will be published as:

\(\sigma' = k^{-1}\left(\mathbb{H}(m) + R_{\mathrm{x}}x\right) \)

... which may look strange as here the RHS is identical to what we previously had for the complete signature \(\sigma\). The difference of course is that here, the terms \(k\) and \(R\) don't match up; \(R\) has private key \(kt\) not \(k\). And hence we can easily see that:

\(\sigma = t^{-1} \sigma'\)

will be a valid signature, whose nonce is \(kt\).

However, we do not operate in a world without adversaries, so to be sure of the statement "if I get given the discrete log of \(T\), I will be able to construct a fully valid \(\sigma\)", we need a proof of that claim. This is the key innovation, because this can be done very simply with a proof-of-discrete-log, or a "PoDLE" as was described in one of the first blog posts here. To prove that \(R'/G = R/T = k\), where we somewhat abuse / to mean "elliptic curve discrete log", you just create an AND of two \(\Sigma\)-protocols, using the same commitment (i.e., nonce), let's call it \(k_2\) and output a schnorr style response \(s = k_2 + ek\), where the hash e covers both points \(k_2 G\ ,\ k_2 T\) as has been explained in the just-mentioned PoDLE blog post and also in a bit more generality in the post on ring signatures.

It's thus intuitive, though not entirely obvious, that an "adaptor signature" in this context is really a combination of the same idea as in Schnorr, but with additionally a PoDLE tacked-on:

Input:

an adaptor point \(T\), a message \(m\), a signing key \(x\)

Output:

adaptor signature \((\sigma', R, R')\), adaptor signature PoDLE: \((s, e)\)

Verification for non-owner of adaptor secret \(T\):

1. Verify the PoDLE - proves that \(R, R'\) have same (unknown) discrete log w.r.t. \(T, G\) respectively.

2. Verify \(\sigma' R' \stackrel{?}{=} \mathbb{H}(m) + R_{\mathrm{x}} P\)

Swapping ECDSA coins with this method

Fundamentally, if not exclusively, adaptor signatures as originally conceived, and still here, allow the swap of a coin for a secret (in that broadcast of a spending transaction necessarily implies broadcast of a signature which can be combined with a pre-existing adaptor signature to reveal a secret), and the crudest example of how that can be used is the coinswap or atomic swap, see these previous blog posts for a lot of detail on pre-existing schemes to do this, both with and without the Schnorr signature primitive that was previously thought to be near-required to do adaptor signatures.

The ECDSA scheme above can be used in a slightly different way than I had originally described for Schnorr adaptor signatures, but it appears that was partly just oversight on my part: the technique described below can be used with Schnorr too. So the advantage here is principally that we can do it right now.

1. Alice spends into a 2/2 A1 B1 after first negotiating a timelocked refund transaction with Bob, so she doesn't risk losing funds.

2. Bob does the same, spending into a 2/2 A2 B2 after negotiating a a timelocked refund tranasction with Alice, so he also doesn't risk, but his timelock is closer.

3. Alice creates an adaptor \(\sigma_{1}^{'}\) spending with key A1 to Bob's destination and adaptor point \(T\) for which she knows discrete log \(t\).

4. Bob verifies \(\sigma_{1}^{'}\) and the associated data mentioned above, including crucially the PoDLE provided.

5. Bob creates an adaptor \(\sigma_{2}^{'}\) spending with key B2 to Alice's destination and adaptor point \(T\) for which he does not know the \(t\).

6. Alice can now safely complete the adaptor she receives: \(\sigma_2 = t^{-1}\sigma_{2}^{'}\) and co-sign with A2 and broadcast, receiving her funds.

7. Bob can see on the blockchain (or communicated directly for convenience): \(t = \sigma_{2}^{'}\sigma_{2}^{-1}\) and use it to complete: \(\sigma_{1} = t^{-1}\sigma_{1}^{'}\), and co-sign with B1 and broadcast, receiving his funds.

Comparisons to other coinswaps:

This requires 2/2 P1 P2 type scriptPubKeys; these can be p2sh multisig or p2wsh multisig using, as mentioned, OP_CHECKMULTISIG. Notice that in a future Taproot/Schnorr world, this will still be possible, using the linear style adaptor signatures previously described. However in that case a musig-style combination of keys will almost certainly be preferred, as it will create transaction styles that look indistinguishable from single or any other script types. For now, the system above does share one very valuable anonymity set: the set of Lightning channel opens/closes, but doesn't share an anonymity set with the full set of general single-owner ECDSA coins (which includes both legacy and segwit).

For now, this method has the principal advantage that the only failure mode is the timelocked backout, which can be a transaction that looks entirely normal - having a non-zero nLockTime somewhere around the current block is actually very normal. While the atomic enforcement part is, just like Schnorr adaptors, entirely invisible. So apart from the smaller anonymity set (2-2, so mostly LN), it has excellent privacy properties.

Reframing adaptors \(\rightarrow\) otVES

The aforementioned paper of 2019 by Lloyd Fournier is titled "One Time Verifiably Encrypted Signatures A.K.A. Adaptor Signatures" - at first this new name (henceforth otVES) seemed a bit strange, but after reading the paper I came away pretty convinced. Both the conceptual framework is very clean, but also, this links back to earlier work on the general concept of Verifiably Encrypted Signatures. Most particularly the work of the same guys that brought us BLS signatures from bilinear pairing crypto, in this paper (namely, Boneh, Lynn, Shacham but also Gentry of FHE fame). The context considered there was wildly different, as Fournier helpfully explains: this earlier work imagined that Alice and Bob wanted to fairly exchange signatures that might be useful as authorization for some purpose. To achieve that goal, they imagined trusted third party acting between them, and that an encrypted-to-third-party-adjudicator but still verifiable signature could serve as the first step of a fair protocol, assuming honesty of that third party. However what makes the Bitcoin use-case special is that signatures are useable if and only if broadcastAll of this coinswap/HTLC/second layer stuff relies on that property. In this scenario, having not only a VES but an otVES is exactly desirable.

Why is one-time desirable here? It's a little obtuse. For those familiar with cryptography 101 it'll make sense to think about the one time pad. The absolutely most basic concept of encryption (which also happens to be perfectly secure, when considered in the most spherical cow kind of way): take a plaintext \(p\) and a key \(k\), bitstrings of the exact same length. Then make the ciphertext \(c\):

\(c = p \oplus k\)

and the thing about this that makes it perfect is exactly also something that can be considered a "bug": the symmetry of the \(\oplus\) (xor) operation is such that, given both the plaintext and the ciphertext, the key can be derived: \(k = c \oplus p\). So any broadcast of \(p\), after an earlier transfer of \(c\) (to Bob, let's say), means that the secret key is revealed.

The same is true in our adaptor signature or VES scenario: the adaptor signature \(\sigma'\) is an "encrypted signature", and is verifiable using the verification algorithm already discussed, by anyone who has that encrypted signature and the adaptor "public key" which we called \(T\). Notice how this is analogous to public key encryption, in that you only need a public key to encrypt; but also notice that the one-time pad is secret key encryption, which is why the plaintext and ciphertext are enough to reveal the key (note: more developed secret key algorithms than OTP handle this problem). This is some kind of hybrid of those cases. Once the "plaintext" signature \(\sigma\) is revealed, the holder of the "encrypted" signature \(\sigma'\) can derive the private key: \(t\).

So hopefully this makes clear why "one-time-ness" is not so much in itself desirable, as what is implied by it: that the "private key" (the encryption key, not the signing key, note!) is revealed on one usage.

Security properties - deniability, forgeability, validity, recoverability ...

At a high level, what security properties do we want from these "encrypted signatures''? I think there's a strong argument to focus on two properties:

  • Handing over such encrypted signatures should not leak any information to any adversary, including the recipient (it may or may not be needed to keep the transfer private, that is not considered in the model).
  • Given an encrypted signature for a message and key, I should be able to convince myself that when the plaintext signature is revealed, I will get the secret key \(t\), or complementary: when the secret key \(t\) is revealed, I should be able to recover the plaintext signature.

We'll deal with both of these points in the following subsections.

Deniability

The Schnorr version of the otVES is deniable in the specific sense that given an unencrypted signature, a corresponding encrypted signature for any chosen key (\(t\)) can be claimed, as was explained here ("Deniability" subsection). For anyone familiar with the basic construction of zero knowledge proofs, this will be immediately recognized as being the definition of a "Simulator", and therefore proves that such an adaptor signature/encrypted signature leaks zero information to recipients.

It is interesting to observe that the same trick does not work with the ECDSA variant explained above:

Given \(\sigma, R\) satisfying \(\sigma R = \mathbb{H}(m)G + R_{\mathrm{x}}P\) for the verifying pubkey \(P\), you can try to assert that \(k = tk_2\) but you have no way to generate a PoDLE for \(R, R'\) if you don't know k - this means that such a "retrofitted" encrypted signature (which by definition includes the PoDLE) is not possible for a party not knowing the original secret nonce, and thus the simulator argument (the argument that an external observer not knowing the secret can create fake transcripts with a distribution indistinguishable from the real transcripts) is not available, hence we cannot claim that such encrypted signatures are fully zero knowledge. More on this shortly.

Forgeability

I am abusing terms here, because unforgeability is the central property of a valid signature scheme, but here let's talk about the forgeability of an encrypted signature, so perhaps "adaptor forgeability". Here I mean the ability to create arbitrary encrypted signatures without the signing key. This was demonstrated as possible for Schnorr in the first section of this blog post (noting the obvious caveat!). For ECDSA, we hit the same snag as for 'Deniability'. Without possessing the signing key \(x\), you want to make the verification \(\sigma' R' = \mathbb{H}(m)G + R_{\mathrm{x}}P\) pass for some \(R, R', T, R = tR'\) such that you can prove DLOG equivalence w.r.t. \(G, T\). You can do this by "back-solving" the same way as for Schnorr:

\(\stackrel{$}{\leftarrow} k^{*}, R=k^{*}G, \quad Q = \mathbb{H}(m)G + R_{\mathrm{x}}P\)

\(\stackrel{$}{\leftarrow} \sigma', \quad \Rightarrow \sigma' R' = Q \Rightarrow R' = (\sigma')^{-1}Q\)

But since this process did not allow you to deduce the scalar \(q\) s.t. \(Q = qG\), it did not allow you to deduce the corresponding scalar for \(R'\). Thus you can output a set \(\sigma', R, R'\) but you cannot also know, and thus prove equivalence of, the discrete logs of \(R\) and \(R'\).

The previous two sections demonstrate clearly that the otVES construction for ECDSA is fundamentally different from that for Schnorr in that it requires providing, and proving a relationship between two nonces, and this also impacts quite significantly the security arguments that follow.

Validity, Recoverability

These are aspects of the same thing, so grouped together, and they talk about the most central and unique property for an otVES scheme, but fortunately it is almost tautological to see that they hold for these schemes.

The concern it addresses: what if Alice gave Bob an encrypted signature to a key \(T\) but it turned out that when decrypted with the corresponding key \(t\), a valid signature wasn't actually revealed. That this is impossible is called validity. The flip side is recoverability: if Alice gave Bob an encrypted signature and then published the corresponding decrypted signature ("plaintext"), the secret key for the encryption (\(t\)) must be revealed.

The Schnorr case illustrates the point clearly, see Lemma 4.1 in Fournier's paper; \(\sigma' = \sigma -t\) in our notation and we can see by the definition of Schnorr signature verification that this must hold, given there cannot be another \(t' \ne t\) s.t. \(t'G = T\) (there is a one-one mapping between scalars mod n and group points). Recoverability is also unconditionally true in the same way.

For the ECDSA case, it is nearly the same, except: we rely on the PoDLE between \(R, R'\), which has the same properties itself as a Schnorr signature, and so the properties hold conditional on the inability to break ECDLP (because that would allow Schnorr forgery, and thus PoDLE forgery).

Note how a ECDLP break can obviously destroy the usefulness of all these schemes, in particular the underlying signature schemes, but even that does not alter the fact that the Schnorr encrypted signature is valid and recoverable (though it becomes a mere technicality in that case).

EUF-CMA for otVES using Schnorr

EUF-CMA was discussed in the previous blogs on the Schnorr signature and on ring signatures, in brief it is a technical term for "this signature scheme is secure in that signatures cannot be forged by non-secret-key-owners under this specific set of (fairly general) assumptions".

Proving this for the Schnorr otVES turns out to be a fairly standard handle-cranking exercise. This is essentially what I have focused on in previous work as "proving soundness by running an extractor", including patching up the random oracle. See the above linked post on the Schnorr signature for more detail.

Note that unforgeability referred to here is not the same as "adaptor forgeability" discussed above. Here we are specifically trying to prove that access to such encrypted signatures does not help the adversary in his pre-existing goal of forging real signatures.

So the handle-cranking simply involves adding an "encrypted signature oracle" to the attacker's toolchest. EUF-CMA[VES] basically refers to the inability to create signatures on new messages even when you have access to arbitrary encrypted signatures, as well as arbitrary earlier complete signatures, again, on different messages.

As Fournier points out here:

EUF-CMA[VES] says nothing about the unforgeability of signature encryptions. In fact, an adversary who can produce valid VES ciphertexts without the secret signing key is perfectly compatible. Of course, they will never be able to forge a VES ciphertext under a particular encryption key. If they could do that, then they could trivially forge an encrypted signature under a key for which they know the decryption key and decrypt it.

... which is the reason for my (I hope not too confusing) earlier section on "adaptor forgeability". It is actually possible, for Schnorr, but not ECDSA, to do what is mentioned in the second sentence above.

EUF-CMA[VES] for ECDSA

Here is the most technical, but the most important and difficult point about all this. In producing an encrypted ECDSA signature you output:

\((\sigma', R, R', m, P), \quad \textrm{DLEQ}(R, R')\)

(while \(m, P\) may be implicit of course), and this means you output one piece of information in addition to the signature: that two nonce points are related in a specific way. It turns out that this can be expressed differently as the Diffie Hellman key of the key pair \((P, T)\) (or, in Fournier's parlance, the signing key and the encryption key). That DH key would be \(tP = xT = xtG\). Here's how; starting from the verification equation for a published encrypted signature, using the notation that we've used so far:

\(s'R' = \mathbb{H}(m) + R_{\mathrm{x}}P\)

isolate the public key P (this is basically "pubkey recovery"):

\(P = R_{\mathrm{x}}^{-1}\left(s'R' - \mathbb{H}(m)G\right)\)

\(\Rightarrow tP = R_{\mathrm{x}}^{-1}\left(s'tR' - \mathbb{H}(m)tG\right)\)

\(\Rightarrow xT = tP = R_{\mathrm{x}}^{-1}\left(s'R - \mathbb{H}(m)T\right)\)

Notice how we - a verifier, not possessing either the nonce \(k\) nor the secret \(t\) - were able to deduce this DH key because we knew the DH key of the key pair \((R', T)\) - it's \(R\), which we were explicitly given. So this, in some sense "breaks" the CDH assumption: that given only points on the curve \(A=aG, B=bG\) you should not be able to calculate the third point \(abG\) (but "breaks" - because actually we were given a related DH key to start with).

Fournier addresses this point in two ways. First, he argues that requirement of the CDH problem being hard is not part of the protocols for which this scheme is useful and that keys are by design one-time-use in these applications. The more important point though, is that an attempt is made to show the scheme secure if the CDH problem is easy. A classic example of backwards cryptography logic ;)

The framework for this is non-trivial, and it is exactly the framework developed by Fersch et al that was discussed in the section on ECDSA in this earlier blog post (subsection "What about ECDSA?"). I have not studied this framework in any detail, only cursorily, and would encourage anyone interested to at least watch the linked video of Fersch's talk on it, which was quite interesting. With the addition of the assumption "CDH is easy", Fournier claims that ECDSA can be said to have this EUF-CMA[VES] security guarantee, which is intended to prove, basically, that the leak of the DH key is the only leak of information and that the scheme is secure against forgery. I can't claim to be able to validate this; I can only say the argument appears plausible.

Current rating: 5

Comments

There are currently no comments

New Comment

required

required (not published)

optional