Adaptor Signature

Table of contents

What it is

An adaptor signature scheme is a two-step signing algorithm that’s bound to a secret. During signature creation, a partial signature is generated which can be adapted with the secret to turn it into a valid full signature. The secret can then be extracted using the partial- and full signature.

Adaptor signatures are a useful primitive in the Blockchain space as they tie together the authorization of a transaction with the leakage of a secret. In fact, adaptor signatures are the core building blocks used in Blockchain protocols to implement ”Scriptless Scripts” which are rules that can solely be implemented and enforced with digital signatures.

One such protocol implementation is that of an ”Atomic Swap”, in which two parties who don’t trust each other exchange digital currencies with one another on (potentially different) Blockchains. In this case, the secret that’s leaked by posting a valid transaction to move funds on Blockchain #1 can be used to finalize another, partial signature which moves funds on Blockchain #2.

How it works

An adaptor signature scheme is characterized by four different operations:

1. PreSign
2. PreVerify
3. Adapt
4. Extract

Furthermore, a statement / witness pair for a hard relation $R$ needs to be defined such that it’s computationally infeasible to extract the witness $t$ given the statement $T$.

In practice, such a hard relation can be that of a discrete logarithm which is also used in cryptosystems such as Elliptic Curve Cryptography.

Given a generator $G$ of an Elliptic Curve $E$ with order $q$ we can define the statement / witness pair as follows:

Conceptually one can think of the statement / witness pair along the same lines as a public / private key pair, in which the statement $T$ can be publicly shared, while the witness $t$ needs to be kept secret.

PreSign

The PreSign operation creates a partial signature $\sigma'$ for a message $m$. It takes as input a private key $x$, the message $m$ as well as the statement $T$.

The partial signature $\sigma'$ is an incomplete signature according to the signature scheme’s verification method. However it can be checked for correctness with the help of the PreVerify operation.

PreVerify

PreVerify can be used to check if a partial signature $\sigma'$ was generated correctly. Its inputs are the public key $X$, the message $m$, the partial signature $\sigma'$ as well as the statement $T$.

Adapt

The Adapt operation turns a partial signature $\sigma'$ into a full signature $\sigma$ with the help of the witness $t$. It takes as input the partial signature $\sigma'$ as well as the witness $t$.

Extract

Extract operates on the full signature $\sigma$ and its partial signature $\sigma'$ to reveal the witness $t$.

Example

To illustrate how an adaptor signature scheme can be used in practice, we’ll walk through an example in which Alice, who knows the statement $T$ and witness $t$ wants Bob to generate a signature over her message $m$ with his private key $x$ of which the public key is $X$.

Bob however doesn’t want to create a valid signature which Alice can use right away. He wants to generate a partial signature $\sigma'$ that can be turned into a full signature $\sigma$ by Alice using her secret witness $t$. In doing so, Bob wants to be able to learn the witness $t$ once Alice shares the full signature $\sigma$ publicly.

While this setup might sound fabricated, it’s in fact the foundation to implement an ”Atomic Swap” without the reliance on a Blockchain’s scripting capabilities.

Throughout this example we’ll use an Elliptic Curve $E$ that is of order $q$ and has a generator $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

As a first step, Alice generates her statement / witness pair by randomly sampling the witness $t$ from $\mathbb{Z}_q$ to then multiply it by the generator $G$ to derive the statement $T$:

Bob generates his private- and public key pair similarly by randomly sampling a value $x$ from $\mathbb{Z}_q$ for the private key which is then multiplied by the generator $G$ to derive the public key $X$.

Next up, Alice sends the message $m$ she wants Bob to sign alongside the statement $T$ to Bob. Bob in turn uses the PreSign operation to generate an incomplete, partial signature $\sigma'$ over the message $m$ using his private key $x$ and Alice’s statement $T$:

Bob then sends this partial signature $\sigma'$ to Alice alongside his public key $X$.

Given that $\sigma'$ is incomplete, it won’t verify using the signature scheme’s verification method. However Alice can check if what Bob sent her is in fact a correct partial signature $\sigma'$ over her message $m$. She does this by using PreVerify with the inputs of Bob’s public key $X$, her message $m$, the partial signature $\sigma'$ as well as her statement $T$.

Upon successful verification, she uses the Adapt operation which takes as inputs the partial signature $\sigma'$ and the witness $t$ to generate a full signature $\sigma$.

Once the fill signature $\sigma$ is publicly accessible (e.g. by posting it on a public Blockchain) Bob can learn Alice’s witness $t$ using both, the full signature $\sigma$ Alice derived as well as the partial signature $\sigma'$ he generated. He does this by using the Extract operation with the two signatures as input.

Why it works

While this is more of a conceptual writeup about adaptor signatures which are implemented differently for individual signature schemes, they all have the same high-level idea in common.

The intuition behind the inner-workings of adaptor signature is that of hiding the witness $t$, which is necessary to turn a partial signature into a full signature, into the randomness that’s used for signing.

If you’re curious how an adaptor signature scheme can be implemented for signature schemes that are used in the real world, you can check out the writeups on Schnorr Adaptor Signatures as well as ECDSA Adaptor Signatures.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Andrew Poelstra - Lightning in Scriptless Scripts
• Bitcoin Optech - Adaptor Signatures
• Conduition - The Riddles of Adaptor Signatures
• Aumayr et al. - Generalized Channels from Limited Blockchain Scripts and Adaptor Signatures
• Thyagarajan et al. - Universal Atomic Swaps: Secure Exchange of Coins Across All Blockchains
• YouTube - Generalized Channels from Limited Blockchain Scripts and Adaptor Signatures
• YouTube - Universal Atomic Swaps: Secure Exchange of Coins Across All Blockchains