Schnorr Adaptor Signature

Open Table of contents

What it is
How it works
- Setup
- PreSign
- PreVerify
- Adapt
- Extract
Why it works
- PreVerify
- Adapt
- Extract
References

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:

PreSign which generates a partial signature that’s bound to a secret
PreVerify which allows one to verify that a partial signature was computed correctly
Adapt which turns a partial signature into a valid, full signature
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.

Adapt

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'

Schnorr Adaptor Signature

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}

Adapt

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.