Skip to content

Latest commit

 

History

History
96 lines (77 loc) · 4.58 KB

atomic-swap.md

File metadata and controls

96 lines (77 loc) · 4.58 KB
Raw

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 B 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 validates, that knowing the discrete logarithm would actually allow him to obtain a valid signature from the adaptor signature he got from A.
  4. B then signs to give A her coins on one chain.
  5. When A signs to take her coins, B is able to extract a discrete logarithm from her signature.
  6. 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 Rs 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 verifies, that with the knowledge of t he could actually produce a valid signature from step (2).
  4. B reveals his contribution to s for the signature that sends his coins to A.
  5. A reveals her contribution to s for that signature, completing it, and publishes it to take her coins.
  6. 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.
  7. 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". 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.