### 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:

- Alice, Bob share
`P_A, P_B, R_A, R_B`

as above; Bob gives`T`

to Alice - Alice and Bob therefore agree on
`e = H(J(A, B) || R_A + R_B + T || m)`

(note difference,`T`

) - Bob provides adaptor
`s' = r_B + e * x_B'`

(as in previous section, not a valid signature, but verifiable) - Alice verifies:
`s' * G ?= R_B + e * P_B'`

- If OK, Alice sends to Bob her sig:
`s_A = r_A + e * x_A'`

- 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`

- 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:

Type |
Privacy on-chain |
Separate "backout/refund" transactions for non-cooperation |
Requires segwit |
Requires Schnorr |
Number of transactions in cooperative case |
Number of transactions in non-cooperative case |
Space on chain |
---|---|---|---|---|---|---|---|

Atomic swap | None; trivially linkable | None; backout is directly in script | No | No | 2 + 2 | 2 + 2 | Medium |

CoinSwap | Anonymity set: 2 of 2 transactions (+2 of 3 depending on setup) | Presigned backouts using H(X) and CLTV, break privacy if used | Yes | No | 2 + 2 | 3 + 3 | Large-ish |

Scriptless script | Anonymity set: all Schnorr transactions | Presigned backouts uslng locktime; semi-break privacy (other txs may use locktime) | Yes | Yes | 2 + 2 | 2 + 2 | Small |

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.