Adaptor Signatures and Atomic Swaps from Scriptless Scripts
===========================

This document describes adaptor signatures and multisignatures, which are the
original building blocks of scriptless scripts. It also describes an atomic
swap protocol using these building blocks.

### Motivation

On a high level the scheme works as follows. Suppose A is trying to send coins
to B on one chain, while B is sending coins to A on the other.

1. Both parties A and B put their coins into multisignature outputs on each chain
   which require both parties' signatures to be spent.
2. A gives B auxiliary data "adaptor signatures" which allow A to extract a
   discrete logarithm from a signature on one chain, and conversely to extract a
   signature from the same discrete logarithm on the other chain.
3. B then signs to give A her coins on one chain.
4. When A signs to take her coins, B is able to extract a discrete logarithm
   from her signature.
5. He uses this to form a signature on the other chain, giving him A's coins.

We see that this executes an atomic exchange: if A signs, then both transactions
execute; if A does not sign, then the protocol times out and neither transaction
executes.

However, if each chain requires signatures which use different curves, it is
impossible to use the same discrete logarithm in steps 4 and 5. To see this,
we need to look at the adaptor signature protocol in more detail.

#### Adaptor Signatures

Consider a fixed prime-order group generated by a fixed generator `G`. Let `H`
be a hash function mapping from the space of bitstrings to the scalar group (of
integers modulo the order of `G`). Then a _Schnorr signature_ on a message `m`
with public key `P` is a pair `(s, R)` satisfying the equation

```
sG = R + H(P || R || m)P
```
Closely related, an _adaptor signature_ is a triplet `(s', R, T)` satisfying
```
s'G = T + R + H(P || R || m)P
```
It is easy to see that given a Schnorr signature `(s, R)` and adaptor signature
`(s', R, T)` (notice both `R`s are the same) that the discrete logarithm of `T`
can be computed as `s' - s`, since subtracting the above equations reveals
`(s' - s)G = T`.

Similarly, given an adaptor signature `(s', R, T)` and `t` such that `T = tG`,
it is easy to compute a Schnorr signature `(s, R)` by the equation `s = s' - t`.

We conclude that given an adaptor signature `(s', R, T)` with public key `P`,
knowledge of a Schnorr signature with same `P` and same `R` is equivalent to
knowledge of the discrete logarithm of `T`.

#### Schnorr Multisignatures

It is possible for two parties with public keys `P` and `Q` to interactively
create a multisignature on key `P` and `Q`. The components `(s, R)` of the
signature are each the sum of both parties' contributions. Importantly, in
the first step of the interaction the two parties agree on `R`, and in the
second step each party reveals their contribution to `s`.

#### Atomic Swaps Using Adaptor Signatures

On a lower level, the above scheme works as follows. We assume first that both
blockchains use the same group generated by the same fixed generator `G`, and
that both blockchains support Schnorr signatures.

1. Each party puts their coins into a multisignature output. They agree on an
   `R` for each signature that they'll eventually use to move the coins to their
   final destinations.
2. A chooses a random `t`, sets `T = tG`, and produces adaptor signatures in place
   of her contributions to `s`. Each signature uses the same `T`. She sends these
   to B.
3. B reveals his contribution to `s` for the signature that sends his coins to A.
4. A reveals her contribution to `s` for that signature, completing it, and
   publishes it to take her coins.
5. Using the adaptor signature, B learns `t` from the output of step (4), and uses
   it to compute A's contribution to `s` for the signature that sends her coins to
   him.
6. B adds his contribution to `s`, completing the signature, and publishes it to
   take his coins.

### Compatibility

Adaptor signatures are *not* compatible with non-interactive signature
aggregation techniques such as [Schnorr
"half-aggregation"](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014272.html).
This is because with aggregation the `s`-part in a signature can be
re-randomized while staying valid, such that knowledge of a corresponding
adaptor signature does not allow to compute the adaptor secret `t` as `s' - s`.
