**Schnorr signatures for Bitcoin**

**Pieter Wuille**

**Scaling Bitcoin, Milan, 10 october 2016**

**Thank you**

History:

* In 1988, Schnorr proposed and patented a signature system.

* In 1993, an alternative signature system (DSA) was standardized.

* In 2005, ECDSA (DSA for elliptic curves) was standardized.

* In 2008, Schnorr's patent expires.

* In 2009, Bitcoin appears, using ECDSA.

* In 2011, Ed25519 is proposed.

Schnorr signatures are just a method, not a standard.

Advantages:

* Provably secure under standard assumptions.

* Provably non-malleable

* Batch validatable for a 2-3x speedup.

* Native k-of-k multisignatures.

* And more!

**Applications?**

Drop in?

Multisig?

Aggregation?

* Existentially unforgable under standard assumptions.

Given a

fixed

pubkey, you can't create signature without the key, for any message.

* Interaction with BIP32.

Solution: make the hash commit to the public key.

Q = x * G

sig = (R,s) = (k * G, k - H(R || m))

Q = x * G

sig = (R,s) = (k * G, k - H(R || Q || m))

Standard recommendation for multi key security

* Downside: no naive key recovery

* Group can create a signature valid for the sum of keys.

U1 k1, R1

U2 k2, R2

U3 k3, R3

R

U1 (R,s1)

U2 (R,s2)

U3 (R,s3)

(R,s)

* Use: compact multisig, key tree signatures

Cancellation

133E AC17 9436 F14A 5CF1

B794 860F EB80 4E66 9320

User 1

User 2

x1

Q1 = x1 * G

x2

Q2 = x2 * G - Q1

Q = Q1 + Q2 = x2 * G

Certify keys?

Delinearize!

annoying...

Proof?

x1 * H(Q1)

x2 * H(Q2)

x3 * H(Q3)

Multiple chosen keys

Chosen key

Wagner

Q = H(Q1)*Q1 + H(Q2)*Q2 + H(Q3)*Q3

C = H(Q1, Q2, Q3)

Q = H(C,Q1)*Q1 + H(C,Q2)*Q2 + H(C,Q3)*Q3

Inefficient for key trees

C = H(Q1, Q2, Q3, ...)

With multiple chosen keys fixed, we can do more.

One signature per transaction!

Multiple pubkeys, one signature

Incentive for coinjoin

* OP_SCHNORR

* OP_MULTISCHNORR

* above + Merkle check

* Signature aggregation

2 out of 4 (k1, k2, k3, k4)

k1,k2 k1,k3 k1,k4 k2,k3 k2,k4 k3,k4

A B C

D E

Root

O(~1) verification time

O(log n) signature size

O(n) signing time

only k-of-k; 1 key, 1 signature

k-of-n; n keys, 1 signature

any; 1 signature per input

any; 1 signature per transaction

Old:

<sig1,ALL> <sig2,ALL>

<sig3,SINGLE>

<sig4,SINGLE>

2 <key1> <key2> 2 OP_CMS

<key3> OP_CHECKSIG

<key4> OP_CHECKSIG

New:

<ALL> <ALL>

<SINGLE>

<sig,SINGLE>

2 <key1> <key2> 2 OP_CMS

<key3> OP_CHECKSIG

<key4> OP_CHECKSIG

Aggregated validation after script validation

Future work

* Write about delinearization scheme

* Wait for segwit rollout

* Write BIP

* ???

* Profit!

**Acknowledgements:**

* Gregory Maxwell

* Andrew Poelstra

* Adam Back

* Gregory Maxwell

* Andrew Poelstra

* Adam Back

Can we find a single standard for all?