## What it is

An adaptor signature scheme is a signing algorithm that’s bound to a secret value and carried out in two steps. While creating the signature, an incomplete, partial signature is generated which can be adapted into a full, valid signature by incorporating a secret value. The secret value can be recovered by getting access to the partial- and full signature.

Adaptor signatures are useful in the Blockchain space as they allow for the implementation of ”Scriptless Scripts”. Those “scripts” are a set of rules that can be implemented by solely relying on the existence of a digital signature verification mechanism which is a fundamental requirement for any Blockchain.

As an example, one can use adaptor signatures to implement ”Atomic Swaps”, a mechanism by which two parties who don’t trust each other can exchange digital currencies with one another. The way this would work is that the secret value that turns a partial signature into a full signature is leaked when Party A posts a valid transaction on Blockchain #1 to move funds from Party B to Party A. Party B can then use the leaked secret to turn a partial signature to move funds on Blockchain #2 from Party A to Party B into a full, valid signature.

## How it works

Given that this post describes adaptor signatures based on Schnorr Signatures, it’s useful to have a basic understanding of those two concepts before continuing.

As a quick recap, an adaptor signature is characterized by four different operations:

1. PreSign which generates a partial signature that’s bound to a secret
2. PreVerify which allows one to verify that a partial signature was computed correctly
3. Adapt which turns a partial signature into a valid, full signature
4. Extract which allows for the recovery of the secret value given the partial- and full signature

An adaptor signature scheme also requires a statement / witness pair for a hard relation $R$ which in our case is that of the discrete logarithm on Elliptic Curves (ECDLP). Given a value $T = tG$ it’s computationally infeasible to recover $t$ from $T$. In this case the witness that needs to be kept secret would be $t$ whereas the statement that can be shared publicly is $T = tG$.

As alluded to above, we’ll be working with an Elliptic Curve $E$ that is of order $q$ and has a generator $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

The scenario described here is that Alice who knows the statement $T$ and witness $t$ wants Bob to sign her message $m$. Bob on the other hand doesn’t just simply want to sign Alice’s message $m$ with his private key $x$. He wants to be able to learn Alice’s witness $t$ which might be useful for him in future interactions (e.g. when both of them engage in an ”Atomic Swap” protocol as briefly described above).

### Setup

As a first step, Alice generates her statement / witness pair by randomly sampling a value for her witness $t$ from $\mathbb{Z}_q$. She then multiplies $t$ by the generator $G$ to derive the statement $T$.

$t \overset{{\scriptscriptstyle\}}{\leftarrow} \mathbb{Z}_q$ $T = tG$

Bob follows similar steps to generate his private- and public key pair. He samples a random value $x$ from $\mathbb{Z}_q$ which is his private key. He then multiplies $x$ by the generator $G$ to derive the public key.

$x \overset{{\scriptscriptstyle\}}{\leftarrow} \mathbb{Z}_q$ $X = xG$

Alice then sends the message $m$ she wants to get a signature for alongside her statement $T$ to Bob.

### PreSign

Bob now generates an incomplete, partial signature that’s not valid according to the Schnorr Signature verification algorithm but can be verified for correctness by Alice.

As a first step, he generates a random, secret nonce value $r$ which he then multiplies by the generator $G$ to derive a publicly shareable nonce value $R$. It’s important that $r$ is kept private and is never reused.

$r \overset{{\scriptscriptstyle\}}{\leftarrow} \mathbb{Z}_q$ $R = rG$

In a regular Schnorr Signature Bob would now create a commitment to his public key $X$, the nonce $R$ and the message $m$ by computing $c = H(X \mathbin\Vert R \mathbin\Vert m)$ (where $H$ is a cryptographic hash function).

This however would already be a part of a valid Schnorr Signature. To it into an incomplete, partial signature Bob adds Alice’s statement $T$ to $R$.

$c = H(X \mathbin\Vert R + T \mathbin\Vert m)$

He also computes the second part of the Schnorr Signature as the challenge $c$ he just generated multiplied by his private key $x$ which is added to the nonce $r$.

$e' = r + cx$

Bob now obtained an incomplete, partial signature comprised of the values $c$ and $e'$ which he sends to Alice alongside his public key $X$.

### PreVerify

Once Alice received $c$, $e'$ and $X$ she calculates $R'$ and $c'$ as follows.

$R' = e'G - cX$ $c' = H(X \mathbin\Vert R' + T \mathbin\Vert m)$

She then validates if the partial signature she received from Bob was correctly computed by comparing his value $c$ to the $c'$ she calculated herself.

$c' \overset{?}{=} c$

The partial signature was correctly computed if both values are the same.

If the partial signature is valid, Alice can turn it into a full signature by adding her witness $t$ to $e'$.

$e = e' + t$

### Extract

Once Alice shares the full, valid signature publicly Bob can extract Alice’s witness $t$ using the partial signature he generated and the full signature Alice just shared.

$t = e - e'$

## Why it works

The key ingredient that turns a regular Schnorr Signature into an adaptor signature is the usage of the statement $T$ and its witness $t$ in the calculation of $c$ and $e$.

### PreVerify

To create a partial signature that only verifies if the witness $t$ is incorporated, we adapted the generation of $c$ to include the statement $T$ by adding it to the public nonce value $R$.

$c = H(X \mathbin\Vert R + T \mathbin\Vert m)$

Also remember that we defined $e'$ to be the multiplication of the challenge $c$ with the private key $x$ added to the nonce $r$.

$e' = r + cx$

Note that according to the regular Schnorr Signature verification algorithm this partial signature is invalid (due to the usage of $T$).

\begin{aligned} e'G &\overset{?}{=} R + T + cX \\ (r + cx)G &\overset{?}{=} \\ rG + cxG &\overset{?}{=} \\ R + cX &\ne \end{aligned}

However, there’s a way to verify that the partial signature was computed correctly. As a first step, the value $R'$ is calculated as the multiplication of $e'$ with the generator $G$ subtracted from the multiplication of the challenge $c$ with the public key $X$.

$R' = e'G - cX$

Next up, the value for the challenge $c'$ is calculated as follows.

$c' = H(X \mathbin\Vert R' + T \mathbin\Vert m)$

We can then check if $c' \overset{?}{=} c$.

To see that this equality holds for correctly computed partial signatures we have to expand $R'$.

\begin{aligned} R' &= e'G - cX \\ &= (r + cx)G - cX \\ &= rG + cxG - cX \\ &= R + cX - cX \\ &= R + \cancel{cX} - \cancel{cX} \\ &= R \end{aligned}

As can be seen, the $R'$ value equals the $R$ value that was derived while computing the partial signature.

Given that $c' = H(X \mathbin\Vert R' + T \mathbin\Vert m)$ and $R' = R$ we can see that $c' = c$.

\begin{aligned} c' &\overset{?}{=} c \\ H(X \mathbin\Vert R' + T \mathbin\Vert m) &= H(X \mathbin\Vert R + T \mathbin\Vert m) \\ H(X \mathbin\Vert R + T \mathbin\Vert m) &= \end{aligned}

A partial signature can be adapted by adding the witness $t$ to $e'$.

\begin{aligned} e &= e' + t \\ &= r + cx + t \end{aligned}

By doing so, this turns the partial signature into a full signature that verifies according to the Schnorr Signature verification algorithm.

\begin{aligned} eG &\overset{?}{=} R + T + cX \\ (r + cx + t)G &= \\ rG + cxG + tG &= \\ R + cX + T &= \\ R + T + cX &= \end{aligned}

### Extract

Once the full signature is publicly shared, one can use the partial- and full signature to extract the witness $t$.

\begin{aligned} t &= e - e' \\ &= e' + t - e' \\ &= \cancel{e'} + t - \cancel{e'} \\ &= t \end{aligned}

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