Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Schnorr signatures in Bitcoin

No description
by

Pieter Wuille

on 9 October 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Schnorr signatures in Bitcoin

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

Can we find a single standard for all?
Full transcript