1 / 25

Elliptic Curve Cryptography
EC crypto consists of geometric points with an addition
operator.
Such a set is a group.
Any group element G can be “multiplied” by an integer n byadding G to itself repeatedly.
|G + G +{z· · · + G}
n times

The multiples of G form a cyclic group that we say isgenerated by G .

2 / 25

Elliptic Curve Cryptography
Suppose we have a group with n ∼ 2256 elements generated
by some point G .
We can efficiently map integers into the group by x 7→ xG .
This is a homomorphism: xG + yG = (x + y )G .
In theory we can map xG 7→ x, but in practice it is an open
problem to do this efficiently with only a classical computer.
This is the discrete logarithm problem.
We can think of x as a secret key and xG as a public key.

3 / 25

Elliptic Curve Cryptography

4 / 25

Elliptic Curve Commitments

Let H be some cryptographic hash function, c some message,and (x 0 , P 0 ) a keypair.
Then P = P 0 + H(P 0 kc)G is a commitment to c.
Further, if x = x 0 + H(P 0 kc), then (x, P) is a keypair andsomebody who knows x 0 definitely knows x.
Further, somebody who knows (P 0 , c) can verify thecommitment, while somebody who knows neither cannot learn
anything about them from P.

5 / 25Taproot and Pay-to-Contract

Consider a hypothetical Bitcoin output labelled by a key P,
such that it may be spent by a signature with this key.
Validators who see this output cannot determine how P wasgenerated, and an ordinary transaction does not reveal
anything about it.
Suppose, however, that there exists some script c andalternate point P 0 such that P = P 0 + H(P 0 kc)G .

6 / 25Taproot and Pay-to-Contract
This construction is called pay-to-contract and has been
floating around in some form or another since 2014 at least.
(A 2012 paper by Gerhardt and Hanke described a similar but
broken scheme.)
This is used in Liquid and Elements: the script c is actually
the scriptPubkey of an output on the sidechain.
But on Bitcoin itself, we could allow a second way to spendthese coins: reveal (P, c) and satisfy the script c. Validators
would check the commitment and check the witness for c.
This is Taproot.

7 / 25ECDSA and EC-Schnorr
Suppose we have a keypair (x, P) with P = xG .
To sign a message m, first generate an ephemeral keypair ornonce, (k, R).
Compute r = Rx and e = H(m) (ECDSA) or e = H(PkRkm)(Schnorr).
Compute s such thatsk = e + rx(ECDSA)

s = k + ex(Schnorr)

The signature is (s, R).
8 / 25

Sign-to-Contract

By the way, we can do the pay-to-contract/Taproot
construction on R.
The result is called sign-to-contract and allows committing
things to the blockchain in ordinary transactions with noadditional space.

9 / 25ECDSA and EC-Schnorr

Verification is basically the same as signingskG = eG + rxG(ECDSA)sG = kG + exG(Schnorr)

10 / 25ECDSA and EC-Schnorr

Verification is basically the same as signingskG = eG + rxG(ECDSA)sG = kG + exG(Schnorr)

11 / 25ECDSA and EC-Schnorr

Verification is basically the same as signing
ksR = eG + r xP(ECDSA)sG = kR + exP(Schnorr)

12 / 25ECDSA and EC-Schnorr
From this equation we can see that Schnorr signatures arelinear in the components of the signature (s, R) and cantherefore be added:
s1 G = R1 + eP1
s2 G = R2 + eP2(s1 + s2 )G = (R1 + R2 ) + e(P1 + P2 )Notice same e in both equations — this requires interaction
to achieve.
vs ECDSA
s1 R1 = eG + rP1
s2 R2 = eG + rP2

13 / 25

Multisignatures
Suppose n parties with keys {P1 , . . . , Pn } want to jointly signa message m.
They could create n nonces {R1 , . . . , Rn } and compute
P = P1 + · · · + Pn
R = R1 + · · · + Rne = H(PkRkm)
Pthen each compute si = ki + xi e. Writing si =si , we thenhave
X 
X XsG =si G =Ri + e
Pi = R + eP

14 / 25

Multisignatures

This is a valid signature with P, but it does not prove thateach party Pi participated in the production of the signature.
Suppose that the nth party chose Pn = P −key P that xe knows the secret key to.

Pi<n Pi for someP
Then P =Pi is actually entirely controlled by the nthparty, who can produce signatures without anyone else’sinvolvement.

15 / 25

Multisignatures

We could prevent this by using knowledge-of-secret-key(KOSK), i.e. having the participants refuse to participate
unless every other participant had proven control over theirindividual key.
This is a bad fit for Bitcoin where the signers don’t necessarilychoose the public key (the sender does).
But also, it doesn’t work with Taproot! Suppose our attacker
chooses Pn by first choosing some Pn0 andPa script c which
gives xir all the coins. Xe computes P = i<n Pi + Pn0 andpublishes Pn = Pn0 + H(Pkc)G .

16 / 25

Multisignatures
Instead, we use a key-combining technique called MuSig1 .
In MuSig, rather than taking P = P1 + · · · + Pn , we firstcomputeC = H(P1 k · · · kPn )µi = H(C ki)
XP=µ i Pifor each ii

Now every party must choose their public key Pi before
learning any µi or P, so it is impossible to cancel others’contributions or add Taproot commitments.
1Well, technically MuSig refers to the full signing scheme. But I spent a lotof time mixing keys and basically no time signing anything, so I’ve started using“MuSig” to refer to just the key-combination part.
17 / 25

Multisignatures — 2-of-2 MuSig Example
1

Key Setup. Suppose Alice and Bob choose public keys PAand PB , and send these to each other. They can bothcompute C = H(PA kPB ), µA = H(C k1), µB = H(C k2) andP = µ A PA + µ B PB .

2Signing (1). They agree on a message m. The parties
compute nonces (kA , RA ) and (kB , RB ) and exchange thepublic halves. They both compute R = RA + RB ande = H(PkRkm)2

3Signing (2). They each computesA = kA + µA xA esB = kB + µB xB eand add these together.

2Edit 2018-10-07 you must add a “exchange precommits to RA , RB round,cf https://eprint.iacr.org/2018/417
18 / 25

Sign-to-Contract Redox

Each partial signature should have the form si = ki + eµi xi ,where e is a commitment to, among other things, the total
nonce R.
If one party wants the signature to sign some auxillary data —for example, a detailed invoice or audit log in a Lightning
payment — they can require that R has the form
R = R 0 + H(R 0 kc)G , where c is the auxillary data.
It can be shown that if the underlying signature scheme issecure, then the extended scheme where (R 0 , c) are revealed isalso a secure signature on c.

19 / 25

Adaptor Signatures

Suppose that in the MuSig protocol some party gave an
invalid si so that the final signature did not validate. Could
the guilty party be identified?
Yes – just as for complete signatures, the “partial signatures”
si have a verification equationsi = ki + eµi xi
si G = ki G + eµi xi G
si G = Ri + eµi Pi

20 / 25

Adaptor Signatures
We can extend this verification equation to make these partialsignatures more powerful.
Suppose that party i chooses yet another ephemeral keypair(ti , Ti ), called an adaptor, and offsets the signature as
si0 = ki + eµi xi + ti
This is verifiable; it’s equivalent tosi0 G = Ri + eµi Pi + Ti
and anyone who knows si0 will learn a valid signature si on thesame hash e if and only if they learn ti .

21 / 25

Adaptor Signatures

Suppose Bob sends coins to an output controlled by the key
P = µA PA + µB PB 3 , with the intention of sending these coins toAlice.
1

Like a standard multisignature, they start by exchanging
nonces RA and RB and computing the messagehash e.
However Alice also provides a second public key TA .

2Alice provides an adaptor signature sA0 = kA + µA xA + tA .

3

Bob provides an ordinary partial signature sB = kB + µB xB .

4

Alice computes sA = kA + µA xA , adds this to sB to get acomplete signature, and uses this to take her coins. In doingso, she reveals tA to Bob.

3

And suppose that he adds a Taproot commitment to a timelocked refund.
22 / 25

Adaptor Signatures and ZKCPIn the previous protocol, Bob “bought” the discrete log tA ofTA from Alice, in a trustless way.
The obvious application of this is a zero-knowledge contingentpayment.
Here ti is the (encryption key to) a witness to some NP
problem, and Alice proves beforehand that this is the case.
Some useful examples exist that are naturally expressed as
discrete logs. e.g. Pedersen commitment openings, blind sigs.
(Jonas Nick has adaptor-signature-based protocols for both.)23 / 25

Adaptor Signatures and Atomic Swaps
Finally we get to the point of this workshop: atomic swaps
using adaptor signatures.
On a high level, this works by doing the “sell ti ” protocol
twice in parallel.
More specifically, both Alice and Bob put coins into jointly
controlled outputs. They start to sign transactions that send
Alice’s coins to Bob and Bob’s coins to Alice, but once again
Alice first provides adaptor signatures in place of real partial
signatures.
Specifically, she provides adaptor signatures with the same
adaptor TA . Then when she completes the transaction thatgives her coins, Bob learns tA , which he uses to take his coins.
24 / 25

Thank You
Andrew Poelstra <scriptless@wpsoftware.net>

25 / 25