Threshold ScriptlessScripts

Omer Shlomovits
1Scriptless Scripts"Magicking digital signatures so that they can only be created by faithfulexecution of a smart contract”.
Andrew Poelstra!2

In This Talk…
• Intro to Schnorr Scriptless Scripts (SSS)• The road to ECDSA Scriptless Scripts (ESS)• Rebuttal ECDSA known security issues• Discussing 2P-ECDSA as main tool
• Expending the Tool Box with Threshold ECDSA• Experimenting with ESS!3Schnorr Signature
EC public parameters : q,G• Choose random k• Compute R = k • G• Compute s = k + H(R, P, m) • x mod q
where x is the private key, R = x • G• Output (R,s)!4The Shtik
Adaptor Signature: Main building block is a tweak to Schnorr signature (R,s)

s’ = s + t

Schnorr Sig

Adaptor (t, T)

ElementsProject/scriptless-scripts!5

SS Atomic Swap
Wallet A

PKA + PKB

Wallet B

PKA + PKB!6

SS Atomic Swap
Wallet A

PKA + PKB

Wallet B

T, s’A, s’A

PKA + PKB

!7

SS Atomic Swap
Wallet B

Wallet A

PKA + PKB

T, s’A, s’A

PKA + PKBsB!8

SS Atomic Swap
Wallet A

PKA + PKB

Wallet B

T, s’A, s’A

PKA + PKBsB

Publish sA!9

SS Atomic Swap
Wallet A

PKA + PKB

Wallet B

T, s’A, s’A

PKA + PKBsB

Publish sA
t = s’A - sA
sA = s’A - t!10

Scriptless Scripts

Q1 = decom(Q1)

ElementsProject/scriptless-scripts!11

ECDSA SS - The HardQuestions• Why we needed Schnorr in the first place?
• What are the challenges in using ECDSA for SS!12

Why Schnorr ?
EC public parameters : q,GECDSASchnorr• Choose random k• Choose random k• Compute R = k • G• Compute R = k • G• Compute r = rx mod q where R = (rx,ry)• Compute s = k-1 • (H(m)+ r • x) mod q
where x is the private key• Compute s = k + H(R, P, m) • x mod q
where x is the private key, R = x • G• Output (r,s)• Output (R,s)!13

Why Schnorr #2!14

Why Schnorr #2

ECDSA is a NO-GO?

!15

ECDSA: No security
proof?

!16

ECDSA: No security
proof?

• 2003, Generic Group Model!17

ECDSA: No security
proof?

• 2016, Bijective Random Oracle (BRO) model!18

ECDSA: No security
proof?
• ECDSA is one of the widelyused signature schemes: TLS,PGP, S/MIME, multiple
cryptocurrencies etc..

• ECDSA is widely standardized:

IEEE P1363, ANSI X9.62, FIPS
186-4

• It was subject to massive

cryptanalytic efforts with zeroknown attacks!19

ECDSA: Malleable ?
• Known malleability:• (r,s) and (r, q - s) are both valid signatures on message m!20

ECDSA: Malleable ?
• Known malleability:• (r,s) and (r, q - s) are both valid signatures on message m• Define ECDSA’ as ECDSA that fix this malleability• ECDSA’ is strong unforgeable!21

ECDSA: Malleable ?
• Known malleability:• (r,s) and (r, q - s) are both valid signatures on message m• Define ECDSA’ as ECDSA that fix this malleability• ECDSA’ is strong unforgeable• BIP62 (WIP):!22

ECDSA: Malleable ?
• Known malleability:• (r,s) and (r, q - s) are both valid signatures on message m• Define ECDSA’ as ECDSA that fix this malleability• ECDSA’ is strong unforgeable• BIP62 (WIP):• Segwit!23

Schnorr: Malleable ?
Q:A:!24

Linearity• Valid point!
• Deal breaker?

!25Linearity• Valid point!
• Deal breaker?

• Given the non-linearity of ECDSA, Are ECDSA Scriptless Scripts• Possible ?
• Possible but Inefficient ?
• Possible but with compromise on Security ?

!26

Linearity: Observation• Threshold ECDSA has struggled with the same problem.
• Not surprisingly• Existing works for ECDSA-SS are based on threshold ECDSA
protocol!27

Scaling Bitcoin 2018 #1!28

Scaling Bitcoin 2018 #2!29

Scaling Bitcoin 2018 #2!30

Previous Work• Common to both is 2P-ECDSA:!31

Threshold Signatures(t,n)-threshold signature scheme distributes signing power to n parties
such that any group of at least t parties can generate a signature(2,3) - Keygen

xs,Qxc,Qxi,Q!32

Threshold Signatures(t,n)-threshold signature scheme distributes signing power to n parties
such that any group of at least t parties can generate a signature(2,3) - Signing

xc,Q, tx
xs,Q

xi,Q, tx

!33

2P-Keygen [L17]Q1 = x1 • G
Party1Q1Q2 = x2 • G
Party2Q2
Q = x2 • Q1

Q = x1 • Q2

Ence(x1)

The protocol promises: (1) Privacy, (2) Correctness
KZen-networks/multi-party-ecdsa!34

2P-Signing [L17]
Signing message m: m’ = Hash(m)R 1 = k1 • G
Party1R1

R 2 = k2 • G
Party2R2
R = k1 • R

R = k2 • R1

s*s = Decd(s*)/k1s*=
Ence(m’ / k2) ⊞Ence(x1)⊙Ence(x2 •r / k2)

Output: 𝞂 = (s, r), s.t. Verify(𝞂, Q, m’) = 1
The protocol promises: Unforgeability

KZen-networks/multi-party-ecdsa!35

2P-ECDSA Lock
[MMSKM18]
message m’ = Hash(m), Adaptor (t, T)

R 1 = k1 • T
Party1R1

R 2 = k2 • T
Party2R2
R = k1 • R

R = k2 • R1

s*s’ = Decd(s*)/k1

s* =Ence(m’ / k2) ⊞Ence(x1)⊙Ence(x2 •r / k2)

Output: 𝞂’ = (s’ = s•t, r), s.t. Verify(s’•t-1, r, Q, m’) = 1
KZen-networks/multi-hop-locks!36Possible Issues• Given the non-linearity of ECDSA, Are ECDSA Scriptless Scripts• Possible ? YES, using Lindell 2P-ECDSA• Possible but Inefficient ? MAYBE• Possible but with compromise on Security ? YES!37

Possible Issues #2!38

Bad News?

!39

Threshold ECDSAPapers Circa 2017-Today
ParamsAssumptions

SigningRoundsSigning Time

[L17]

2/2

ECDSA, Paillier

4

milliseconds[GG18]t/n

ECDSA, Strong RSA

9milliseconds[LNR18]t/n

ECDSA, DDH

8

milliseconds[DKLS18]

2/n

ECDSA

2

milliseconds[DKLS19]

t/n

ECDSA

[CCLST19]

2/2

ECDSA, Class groups

4[SA19]n/n

ECDSA1[DKOSS19]

t/n

ECDSA

1Log(t) + 6 milliseconds
milliseconds
sub millisecond!40

Threshold ECDSAPapers Circa 2017-Today
ParamsAssumptions

SigningRoundsSigning Time

[L17]

2/2

ECDSA, Paillier

4milliseconds[GG18]t/n

ECDSA, Strong RSA

9milliseconds[LNR18]t/n

ECDSA, DDH

8milliseconds[DKLS18]

2/n

ECDSA

2milliseconds[DKLS19]

t/n

ECDSA

[CCLST19]

2/2

ECDSA, Class groups

4[SA19]

n/n

ECDSA

1[DKOSS19]

t/n

ECDSA

1Log(t) + 6 milliseconds
milliseconds
sub millisecond!41Experiments!42

Use Case #1: Scriptless
Script MultiSig• Access policy privacy• Cost: one standard transaction• Max number of parties

KZen-networks/multi-party-ecdsa!43Use Case #2: ThresholdWallet• Distributed key generation (DKG)• Distributed Signing• Secret Share Recovery• Deterministic Child Address Derivation• Rotation

KZen-networks/gotham-city
unbound-tech/blockchain-crypto-mpc!44Use Case #3: Coin JoinMixer• Pubkey is equal to a sum of locally generated public keys:• Pk = Pk1 + Pk2 + … + Pkn• Basically a constructed way for parties to reach off-chain
consensus on output addresses like Chaumian coin-join• No need for central coordinator

KZen-networks/ShareLock!45

Use Case #4: Atomic Swaps• Option 1: Use the scriptless script construction• Locking using Adaptor signatures.
• Option 2: Depends on access structure secret shares can beswapped using “gradual release of secrets”

scriptless-scripts/atomic-swap
KZen-networks/centipede/!46

skB1

skB2

skL1

skL2

Wallet A

Wallet BWallet A

Wallet B
!47

skB1

skB2

skL1

skL2

Wallet A

Wallet B

Wallet A

Wallet B
!48

skB1

skB2

skL1

skL2

Wallet A

Wallet B

Wallet A

Wallet B
!49

skB1

skB2

skL1

skL2

!50

skB1

skB2

skL1

skL2

Wallet A

Wallet B

Wallet A

Wallet B!51

Use Case #6: Payment
Channel Network

KZen-networks/multi-hop-locks/!52Use Case #7: Zero Knowledge
Contingent Payments

SellWitness/ZKFactorization

!53

ZKCP
Prover / Seller
Knows xRun threshold KeyGen

Verifier / Buyer

Generate TX1, TX2:
TX1,in : Buyer
TX1,out : threshold-Sig
TX2,in : TX1

𝞂Sign TX2

TX2,out : Seller

ZK Prove x is encrypted by 𝞂Broadcast TX1Broadcast TX2Extract x

!54

R&D
Still long way to go!

!55

R&D
Still long way to go!

• Threshold cryptography - In standardisation process by NIST (*)(*)https://csrc.nist.gov/Projects/Threshold-Cryptography

!56

R&D
Still long way to go!

• Threshold cryptography - In standardisation process by NIST (*)• Network layer : authenticated secure p2p communication, Broadcast
channel• Idea: use a blockchain/ consensus layer for the communication

KZen-networks/white-city/

!57

R&D
Still long way to go!

• Threshold cryptography - In standardisation process by NIST (*)• Network layer : authenticated secure p2p communication, Broadcast
channel• Idea: use a blockchain/ consensus layer for the communication• Improvements: Accountability , Batch signing and verification

KZen-networks/white-city/!58Summary• Threshold ECDSA based Scriptless Scripts / systems• Are possible now• Are practical to use in real life
• Hold strong security guarantees and the focus of active research inthe cryptography community!59Summary• Threshold ECDSA based Scriptless Scripts / systems• Are possible now• Are practical to use in real life
• Hold strong security guarantees and the focus of active research inthe cryptography community

Questions?
ZenGo/researchSpecial thanks: Oded Leiba, Jonas Nick,
Elichai Turkel, Pedro Moreno Sanchez

https://t.me/kzen_researchhttps://github.com/KZen-networks!60