Flipping the scriptless script on Schnorr

Outline

It's by now very well known in the community of Bitcoin enthusiasts that the Schnorr signature may have great significance; and "everyone knows" that its significance is that it will enable signatures to be aggregated, which could be great for scalability, and nice for privacy too. This has been elucidated quite nicely in a Bitcoin Core blog post.

This is very true.

There are more fundamental reasons to like Schnorr too; it can be shown with a simple proof that Schnorr signatures are secure if the elliptic curve crypto that prevents someone stealing your coins (basically the "Elliptic Curve Discrete Logarithm Problem" or ECDLP for short) is secure, and assuming the hash function you're using is secure (see this deep dive into the random oracle model if you're interested in such things). ECDSA doesn't have the same level of mathematical surety.

Perhaps most importantly of all Schnorr signatures are linear in the keys you're using (while ECDSA is not).

Which brings me to my lame pun-title : another way that Schnorr signatures may matter is to do with, in a sense, the opposite of Schnorr aggregation - Schnorr subtraction. The rest of this very long blog post is intended to lead you through the steps to showing how clever use of signature subtraction can lead to one very excellent outcome (there are others!) - a private Coinswap that's simpler and better than the private Coinswap outlined in my previous blog post.

The ideas being laid out in the rest of this post are an attempt to concretize work that, as far as I know, is primarily that of Andrew Poelstra, who has coined the term "scriptless scripts" to describe a whole set of applications, usually but not exclusively leveraging the linearity of Schnorr signatures to achieve goals that otherwise are not possible without a system like Bitcoin's Script. This was partly motivated by Mimblewimble (another separate, huge topic), but it certainly isn't limited to that. The broad overview of these ideas can be found in these slides from Poelstra's Milan presentation last May.

So what follows is a series of constructions, starting with Schnorr itself, that will (hopefully) achieve a goal: an on-chain atomic coinswap where the swap of a secret occurs, on chain, inside the signatures - but the secret remains entirely invisible to outside observers; only the two parties can see it.

If you and I agree between ourselves that the number to subtract is 7, you can publish "100" on the blockchain and nobody except me will know that our secret is "93". Something similar (but more powerful) is happening here; remember signatures are actually just numbers; the reason it's "more powerful" is that we can enforce the revealing of the secret by the other party if the signature is valid, and coins successfully spent.

Before we therefore dive into how it works, I wanted to mention why this idea struck me as so important; after talking to Andrew and seeing the slides and talk referenced above, I tweeted about it:

If we can take the semantics of transactions off-chain in this kind of way, it will more and more improve what Bitcoin (or any other blockchain) can do - we can transact securely without exposing our contracts to the world, and we can reduce blockchain bloat by using secrets embedded in data that is already present. The long term vision would be to allow the blockchain itself to be a *very* lean contract enforcement mechanism, with all the "rich statefulness" .. client-side ;)

Preliminaries: the Schnorr signature itself

(Notation: We'll use || for concatenation and capitals for elliptic curve points and lower case letters for scalars.)

If you want to understand the construction of a Schnorr signature well, I can recommend Oleg Andreev's compact and clear description ; also nice is Section 1 in the Maxwell/Poelstra Borromean Ring Signatures paper, although there are of course tons of other descriptions out there. We'll write it in basic form as:

s = r + e * x
e = H(P||R||m)

Note: we can hash, as "challenge" a la sigma protocol, just R||m in some cases, and more complex things than just P||R||m, too; this is just the most fundamental case, fixing the signature to a specific pubkey; the nonce point R is always required).

For clarity, in the above, x is the private key, m is the message, r is the "nonce" and s is the signature. The signature is published as either (s, R) or (s, e), the former will be used here if necessary.

Apologies if people are more used to s = r - ex, for some reason it's always + to me!

Note the linearity, in hand-wavy terms we can say:

s_1 = r_1 + e * x_1
s_2 = r_2 + e * x_2
e = H(P_1 + P2 || R_1 + R_2 || m)
=>
s_1 + s_2 is a valid signature for public key (P_1 + P_2) on m.

But this is NOT a useable construction as-is: we'll discuss how aggregation of signatures is achieved properly later, briefly.

Construction of an "adaptor" signature

This is the particular aspect of Poelstra's "scriptless script" concept that gets us started leveraging the Schnorr signature's linearity to do fun things. In words, an "adaptor signature" is a not a full, valid signature on a message with your key, but functions as a kind of "promise" that a signature you agree to publish will reveal a secret, or equivalently, allows creation of a valid signature on your key for anyone possessing that secret.

Since this is the core idea, it's worth taking a step back here to see how the idea arises: you want to do a similar trick to what's already been done in atomic swaps: to enforce the atomicity of (spending a coin: revealing a secret); but without Script, you can't just appeal to something like OP_HASH160; if you're stuck in ECC land, all you have is scalar multiplication of elliptic curve points; but luckily that function operates similar to a hash function in being one-way; so you simply share an elliptic curve point (in this case it will be T), and the secret will be its corresponding private key. The beatiful thing is, it is possible to achieve that goal directly in the ECC Schnorr signing operation.

Here's how Alice would give such an adaptor signature to Bob:

Alice (P = xG), constructs for Bob:

• Calculate T = tG, R = rG
• Calculate s = r + t + H(P || R+T || m) * x
• Publish (to Bob, others): (s', R, T) with s' = s - t (so s' should be "adaptor signature"; this notation is retained for the rest of the document).

Bob can verify the adaptor sig s' for T,m:

s' * G ?= R + H(P || R+T || m) * P

This is not a valid sig: hashed nonce point is R+T not R;

Bob cannot retrieve a valid sig : to recover s'+t requires ECDLP solving.

After validation of adaptor sig by Bob, though, he knows:

Receipt of t <=> receipt of valid sig s = s' + t

Deniability:

This is a way of concretizing the concept that all of this will be indistinguishable to an observer of the blockchain, that is to say, an observer only of the final fully valid signatures:

Given any (s, R) on chain, create (t, T), and assert that the adaptor signature was: s' = s - t, with R' = R - T, so adaptor verify eqn was: s'G = R' + H(P || R'+T || m)P

Moving to the 2-of-2 case, with Schnorr

For the remainder, we're considering the matter of signing off transactions from outpoints jointly owned (2 of 2) by Alice and Bob.

Start by assuming Alice has keypair (x_A, P_A), and Bob (x_B, P_B). Each chooses a random nonce point r_A, r_B and exchanges the curve points with each other (P_A, R_A, P_B, R_B) to create a scriptPubKey/destination address.

2-of-2 Schnorr without adaptor sig

To avoid related-key attacks (if you don't know what that means see e.g. the "Cancelation" section in https://diyhpl.us/wiki/transcripts/scalingbitcoin/milan/schnorr-signatures/), the "hash challenge" is made more complex here, as was noted in the first section on Schnorr signatures. The two parties Alice and Bob, starting with pubkeys P_A, P_B, construct for themselves a "joint key" thusly:

P_A' = H(H(P_A||P_B) || P_A) * P_A ,
P_B' = H(H(P_A||P_B) || P_B) * P_B ,
joint_key = P_A' + P_B'

Note that Alice possesses the private key for P_A' (it's H(H(P_A||P_B) || P_A) * x_A, we call it x_A' for brevity), and likewise does Bob. From now on, we'll call this "joint_key" J(A, B) to save space.

Common hash challenge:

H(J(A, B) || R_A + R_B || m) = e
s_agg = = r_A + r_B + e(x_A' + x_B')
-> s_agg * G = R_A + R_B + e * J(A, B)

Alice's sig: s_A = r_A + e * x_A', Bob's sig: s_B = r_B + e * x_B' and of course: s_agg = s_A + s_B.

There is, as I understand it, more to say on this topic, see e.g.here, but it's outside my zone of knowledge, and is somewhat orthogonal to the topic here.

2-of-2 with adaptor sig

Now suppose Bob chooses t s.t. T = t * G, and Bob is going to provide an adaptor signature for his half of the 2-of-2.

Then:

1. Alice, Bob share P_A, P_B, R_A, R_B as above; Bob gives T to Alice
2. Alice and Bob therefore agree on e = H(J(A, B) || R_A + R_B + T || m) (note difference, T)
3. Bob provides adaptor s' = r_B + e * x_B' (as in previous section, not a valid signature, but verifiable)
4. Alice verifies: s' * G ?= R_B + e * P_B'
5. If OK, Alice sends to Bob her sig: s_A = r_A + e * x_A'
6. Bob completes, atomically releasing t: first, construct s_B = r_B + t + e * x_B', then combine: s_agg = s_A + s_B and broadcast, then Alice sees s_agg
7. Alice subtracts: s_agg - s_A - s' = (r_B + t + e * x_B') - (r_B + e * x_B') = t

Thus the desired property is achieved: t is revealed by a validating "completion" of the adaptor signature.

Note, however that this has no timing control, Bob can jam the protocol indefinitely at step 6, forcing Alice to wait (assuming that what we're signing here is a transaction out of a shared-control outpoint); this is addressed in the fleshed out protocol in the next section, though.

For the remainder, we'll call the above 7 steps the 22AS protocol, so 22AS(Bob,t, Alice) for Bob, secret t, and Alice. Bob is listed first because he holds t.

Since this is the most important part of the construction, we'll summarize it with a schematic diagram:

So this 22AS was a protocol to swap a coin for a secret, to do atomic swaps we need to extend it slightly: have two transactions atomic via the same secret t.

The Atomic Swap construct, using 2-of-2 schnorr + adaptor signatures

This is now fairly straightforward, inheriting the main design from the existing "atomic swap" protocol.

A. Alice and Bob agree on a pair of scriptPubkeys which are based on 2 of 2 pubkeys using Schnorr, let's name them using D for destination address (A is taken by Alice): D_1 being 2-2 on (P_A1, P_B1) and D_2 being 2-2 on (P_A2, P_B2). Note that these pubkeys, and therefore destination addresses, are not dependent in any way on "adaptor" feature (which is a property only of nonces/sigs, not keys).

B. Alice prepares a transaction TX1 paying 1 coin into D_1, shares txid_1, and requires backout transaction signature from Bob. Backout transaction pays from txid_1 to Alice's destination but has locktime L1.

C. Bob does the (nearly) exact mirror image of the above: prepares TX2 paying 1 coin into D_2, shares txid_2, requires backout transaction signature from Alice. Backout transaction pays from txid_2 to Bob's destination with locktime L2 which is significantly later than L1.

D. Then Alice and Bob broadcast TX1 and TX2 respectively and both sides wait until both confirmed. If one party fails to broadcast, the other uses their backout to refund.

E. If both txs confirmed (N blocks), Alice and Bob follow steps 1-4 of 22AS(Bob, t, Alice) (described in previous section) for some t, for both the scriptPubkeys D_1 and D_2, in parallel, but with the same secret t in each case (a fact which Alice verifies by ensuring use of same T in both cases). For the first (D_1) case, they are signing a transaction spending 1 coin to Bob. For the second, D_2, they are signing a transaction spending 1 coin to Alice. Note that at the end of these steps Alice will possess a verified adaptor sig s' for both of the spend-outs from D_1, D_2.

E(a). Any communication or verification failure in those 1-4 steps (x2), both sides must fall back to timelocked refunds.

F. The parties then complete (steps 5-7) the first 22AS(Bob, t, Alice) for the first transaction TX1, spending to D_1 to give Bob 1 coin. Alice receives t as per step 7.

F(a). As was mentioned in the previous section, Bob can jam the above protocol at step 6: if he does, Alice can extract her coins from her timelocked refund from D_1 in the period between L1 and L2. The fact that L2 is (significantly) later is what prevents Bob from backing out his own spend into D_2 and claiming Alice's coins from D_1 using the signature provided in step 5. (Note this time asymmetry is common to all atomic swap variants).

G. (Optionally Bob may transmit t directly over the private channel, else Alice has to read it from the blockchain (as per above 22AS protocol) when Bob publishes his spend out of D_1).

H. Alice can now complete the equivalent of steps 5-7 without Bob's involvement for the second parallel run for D_2: she has t, and adds it to the already provided s' adaptor sig for the transaction paying her 1 coin from D_2 as per first 4 steps. This s' + t is guaranteed to be a valid s_B, so she adds it to her own s_A to get a valid s_agg for this spend to her of 1 coin, and broadcasts.

Summing up

Privacy implications

In absence of backouts being published (i.e. in cooperative case), these scriptPubkeys will be the same as any other Schnorr type ones (N of N multisig will not be distinguishable from 1 of 1). The signatures will not reveal anything about the shared secret t, or the protocol carried out, so the 2 transaction pairs (pay-in to D_1,D_2, pay out from same) will not be tied together in that regard.

This construction, then, will (at least attempt to) gain the anonymity set of all Schnorr sig based transactions. The nice thing about Schnorr's aggregation win is, even perhaps more than segwit, the economic incentive to use it will be strong due to the size compaction, so this anonymity set should be big (although this is all a bit pie in the sky for now; we're a way off from it being concrete).

The issue of amount correlation, however, has not been in any way addressed by this, of course. It's a sidebar, but one interesting idea about amount correlation breaking was brought up by Chris Belcher here ; this may be a fruitful avenue whatever the flavour of Coinswap we're discussing.

Comparison with other swaps

Since we've now, in this blog post and the previous, seen 3 distinct ways to do an atomic coin swap, the reader is forgiven for being confused. This table summarizes the 3 different cases:

The reason that there are "3 + 3" transactions in the non-cooperative case for CoinSwap is, in that case, both sides pay into a 2-of-2, then in non-cooperation, they must  both spend into the custom "HTLC" (IF hash, pub, ELSE CLTV, pub), and then redeem *out* of it.

A fundamental difference for the latter 2 cases, compared with the first, is they must pay into shared-ownership 2 of 2 outputs in the pay-in transaction; this is to allow backout transactions to be arranged (a two-party multi-transaction contract requires this; see e.g. Lightning for the same thing). The first, bare atomic swap is a single transaction contract, with the contract condtions embedded entirely in that one transaction(for each side)'s scriptPubKey.

Finally, size on-chain of the transactions is boiled down to hand-waving, because it's a bit of a complex analysis; the first type always uses a large redeem script but one signature on the pay-out, whether cooperative or non-cooperative; the second uses 2 or 3 signatures (assuming something about how we attack the anonymity set problem) but no big redeem script in cooperative case, while takes up a *lot* of room in the non-cooperative case, the third is always compact (even non-cooperative backouts take no extra room). Schnorr-sig-scriptless-scripts are the big winner on space.

Extending to multi-hop; Lightning, Mimblewimble

The first time I think this was discussed was in the mailing list post here, which discusses how conceivably one could achieve the same setup as HTLC for Mimblewimble lightning, using this scriptless-script-atomic-swap. Doubtless these ideas are a long way from being fleshed out, and I certainly haven't kept up with what's going on there :)

Other applications of the scriptless script concept

As a reminder, this document was just about fleshing out how the atomic swap gets done in a Schnorr-signature-scriptless-script world; the slides give several other ideas that are related. Multisignature via aggregation is of course part of it, and is already included even in the above protocol (for 2 of 2 as a subset of N of N); earlier ideas like pay-to-contract-hash and sign-to-contract-hash already exist, and don't require Schnorr, but share a conceptual basis; same for ZKCP, etc.

Cross chain swap

I admit to not sharing quite the same breathless excitement about cross-chain swaps as some people, but it is no doubt very interesting, if somewhat more challenging (not least because of different "clocks" (block arrivals) affecting any locktime analysis and confirmation depth). Poelstra has however also made the very intriguing point that it is not actually required for the two blockchains to be operating on the same elliptic curve group for the construction to work.