FAKULTÄT FÜR!NFORMATIK
Faculty of Informatics

S&P

SECURITY &PRIVACY
GROUP

A2L: Anonymous Atomic Locks for Scalability andInteroperability in Payment-Channel Hubs
Erkan Tairi1, Pedro Moreno-Sanchez1, Matteo Maffei1@erkantairi@pedrorechez
1TU Vienna

Scaling Bitcoin
Tel Aviv, Sep12th 2019

@matteo_maffei

Scalability Issues‣ Decentralized data structure recording eachtransaction in order to provide public verifiability‣ Global consensus: everyone checks the wholeblockchain
Bitcoin’s transaction rate: ~10 tx/sec
Visa’s transaction rate: ~10K tx/sec
2

Scalability Solutions?
‣ On-chain (tweak consensus)
e.g., DAG Blockchain, sharding, ...

‣ Off-chain (use blockchain only for disputes)
e.g., Payment Channel Networks
Lightning Network(Bitcoin)

Raiden Network(Ethereum)

Many other projects (Bolt, Perun, Liquidity Network…)

3

Scalability Solutions?
‣ On-chain (tweak consensus)
e.g., DAG Blockchain, sharding, ...

‣ Off-chain (use blockchain only for disputes)
e.g., Payment Channel Networks
Lightning Network(Bitcoin)

Raiden Network(Ethereum)

Many other projects (Bolt, Perun, Liquidity Network…)

3

Background onPayment Channels

4101 Payment Channels

5101 Payment Channels‣ A protocol to perform payments off-chain between twousers

5

101 Payment Channels‣ A protocol to perform payments off-chain between twousers‣ Divided in three phases:• Open channel: Deposit coins in the channel• Analogy: get a gift card5

101 Payment Channels‣ A protocol to perform payments off-chain between twousers‣ Divided in three phases:• Open channel: Deposit coins in the channel• Analogy: get a gift card
• Pay: Send coins off-chain by exchanging
authenticated messages in a peer-to-peer fashion• Analogy: pay with the gift card5

101 Payment Channels‣ A protocol to perform payments off-chain between twousers‣ Divided in three phases:• Open channel: Deposit coins in the channel• Analogy: get a gift card
• Pay: Send coins off-chain by exchanging
authenticated messages in a peer-to-peer fashion• Analogy: pay with the gift card
• Close channel: Redeem coins according to the last
agreed state (or dispute resolution)• Analogy: redeem remaining coins at the gift card5101 Payment Channels‣ Key point for scalability:• Only open and close channel are on-chain• Rest are off-chain operations‣ For more technical description:• See talk: Pedro Moreno-Sanchez, “Atomic MultiChannel Updates with Constant Collateral in BitcoinCompatible Payment-Channel Networks”,
ScalingBitcoin 20196

Payment Channel Hubs (PCHs)
One cannot open channels with everyone...
⇒ exploit gateway channels!

32

2

3

BobCarol…

…
Gateway
4Alice123Dave7

Payment Channel Hubs (PCHs)
One cannot open channels with everyone...
⇒ exploit gateway channels!

3223Bob

Carol

…

…
Gateway
4Alice123DaveSend
1 BTC to Carol
7

Payment Channel Hubs (PCHs)

32

Alice

2Gateway1.

3CarolSend 1 BTC

8

Payment Channel Hubs (PCHs)

32

Alice

Carol

Gateway1.

Send 1 BTC

3Alice32

12Gateway

4Carol
2. Forward 1 BTC toCarol

8

Payment Channel Hubs (PCHs)

33-feefee

2

Alice
1.

1. Send 1 BTC + fee
Send 1 BTC
to gateway

3-fee
3fee

1Gateway
Fee acts as an incentive forgateway to participate inthe paymentCarolGateway

2Alice324Carol
2. Forward 1 BTC toCarol

8

Security, Privacy
and Interoperability in PCHs
UnderSubmission9

Security in PCHs: Atomicity

32Alice

2Gateway1.

3CarolSend 1 BTC

10

Security in PCHs: Atomicity

32

Alice

Carol

Gateway1.

Send 1 BTC

3Alice3221Gateway

4Carol
2. Forward 1 BTC toCarol

10

Security in PCHs: Atomicity

33-feefee

2

Alice
1.

1. Send 1 BTC + fee
Send 1 BTC
to gateway

3-fee
3

Alicefee

32Carol

Gateway

21Gateway

4Carol
2. Forward 1 BTC toCarol

10

Security in PCHs: Atomicity
Should happen atomically
33-feefee

2

Alice
1.

1. Send 1 BTC + fee
Send 1 BTCto gateway

3-fee
3Alicefee

32Carol

Gateway

21Gateway

4Carol
2. Forward 1 BTC toCarol10

Privacy in PCHs: Unlinkability

AC

EA’C’

11

Privacy in PCHs: Unlinkability

AC

EA’

C’

pays topays to≈pays topays to11

Interoperability in PCHs
‣ Create a PCH payment protocol backwards compatible withBitcoin (and as many cryptocurrencies as possible)‣ Not an easy task:• Perun, Liquidity Network: Ethereum-based solutions• BOLT: Requires opcodes not available in Bitcoin• TeeChain: Requires trusted execution environment (e.g.,intel SGX)

• Blind Swaps: Requires Schnorr signatures• TumbleBit: Compatible with Bitcoin• Requires HTLC: Not possible in cryptocurrencies
without scripting language (e.g., Monero)• Efficiency can be improved
12

Our Approach: Building Block‣ Based on adaptor signatures (AS)
Adaptor: (pkC, skC)

(pkA, skA)

(pkB, skB)

13Our Approach: Building Block‣ Based on adaptor signatures (AS)
Adaptor: (pkC, skC)

(pkA, skA)

(pkB, skB)

‣ Goals:‣ Alice can create a “half-signature” that Bob can only
finish by knowing the adaptor skC‣ If Bob finishes the signature, Alice learns skC
13

Our Approach: Building Block‣ Based on adaptor signatures (AS)
Adaptor: (pkC, skC)

(pkA, skA)

txA: Alice pays 1 coin to Bob(pkB, skB)

14

Our Approach: Building Block‣ Based on adaptor signatures (AS)
Adaptor: (pkC, skC)

(pkA, skA)

txA: Alice pays 1 coin to Bob
txA, skA(pkB, skB)

skB
σB
2Party AS

14

Our Approach: Building Block‣ Based on adaptor signatures (AS)
Adaptor: (pkC, skC)

(pkA, skA)

txA: Alice pays 1 coin to Bob
txA, skA(pkB, skB)

skB
σB

Lock

2Party AS

14

Our Approach: Building Block‣ Based on adaptor signatures (AS)
Adaptor: (pkC, skC)

(pkA, skA)

txA: Alice pays 1 coin to Bob
txA, skA(pkB, skB)

skB
σBLock2Party AS

skC
σ, skCσ
14

Our Approach: Building Block‣ Based on adaptor signatures (AS)
Adaptor: (pkC, skC)

(pkA, skA)

txA: Alice pays 1 coin to Bob
txA, skA(pkB, skB)

skB
σB

Lock

2Party ASskC
σ, skCσ

Release14

2Party AS: Instantiation‣ See talk: Omer Shlomovits, “Threshold ScriptlessScripts”, ScalingBitcoin 2019

‣ See talk: Andrew Poelstra, “Workshop on ScriptlessScripts”, ScalingBitcoin 2018

‣ More details, see paper: Malavolta et al., “AnonymousMulti-Hop Locks for Blockchain Scalability andInteroperability”, NDSS 2019. Constructions with:• One-way homomorphic functions• Schnorr signatures• ECDSA (building on 2p-ECDSA of Lindell)15

Our Approach: First Attempt
Adaptor: pkC(pkA, skA)

(pkG, skG, skC )Adaptor: pkC(pkB, skB)

16

Our Approach: First Attempt
Adaptor: pkC(pkA, skA)

2Party AS

Adaptor: pkC(pkB, skB)

(pkG, skG, skC )2Party AS

16

Our Approach: First Attempt
Adaptor: pkC(pkA, skA)

Adaptor: pkC(pkB, skB)

(pkG, skG, skC )txG, skG

skB
σB

2Party AS

2Party AS16

Our Approach: First Attempt
Adaptor: pkC(pkA, skA)

Adaptor: pkC(pkB, skB)

(pkG, skG, skC )txG, skG

skB
σB

txA, skA

skG
σG
2Party AS

2Party AS

16

Our Approach: First Attempt
Adaptor: pkC(pkA, skA)

Adaptor: pkC(pkB, skB)

(pkG, skG, skC )txG, skG

skB
σB

txA, skA

skG
σG2Party AS

σ, skCskC

2Party ASσ16

Our Approach: First AttemptAdaptor: pkC(pkA, skA)

Adaptor: pkC(pkB, skB)

(pkG, skG, skC )txG, skG

skB
σB

txA, skA

skG
σG2Party ASσ, skC

2Party AS

skC
σ

skC
σ, skCσ
16

Our Approach: First Attempt
Adaptor: pkC(pkA, skA)

Adaptor: pkC(pkB, skB)

(pkG, skG, skC )txG, skG

skB
σB

txA, skA

skG
σG
2Party ASσ, skC

2Party AS

skC
σ

skC
σ, skCσ
16

Our Approach: First Attempt
Adaptor: pkC(pkA, skA)

Adaptor: pkC(pkB, skB)

(pkG, skG, skC )txG, skG

skB
σB

txA, skA

skG
σG
2Party ASσ, skC

2Party AS

skC
σ

skC
σ, skCσ
16

Privacy in PCHs: Unlinkability
pkpk

A

C

pk’

E

pk’

A’

C’

pays topays to≈pays topays to17

Privacy in PCHs: Unlinkability
pkpk

A

Cpk’

Epk’

A’

C’

pays topays to≈pays topays to17

A2L: Protocol Overview
Adaptor: pkC(pkA, skA, rA)

2Party AS(pkG, skG, skC )(pkB, skB, rB)

2Party AS

18

A2L: Protocol Overview
Adaptor: pkC(pkA, skA, rA)(pkG, skG, skC )(pkB, skB, rB)

txG, skG EncG(skC)

skB
σB EncG(skC)

2Party AS

2Party AS18

A2L: Protocol Overview
Adaptor:(pkC) rB * rA
(pkA, skA, rA)

Adaptor: pkC(pkG, skG, skC )(pkB, skB, rB)

txG, skG EncG(skC)

skB
σB EncG(skC)

2Party AS

2Party AS

18

A2L: Protocol Overview
Adaptor:(pkC) rB * rA
(pkA, skA, rA)

Adaptor: pkC(pkG, skG, skC )(pkB, skB, rB)

txG, skG EncG(skC)

txA, skA,skB
σB EncG(skC)

EncG(skC *rB * rA)

skG
σG EncG(skC * rB * rA)
2Party AS

2Party AS

18

A2L: Protocol Overview
Adaptor:(pkC) rB * rA

Adaptor: pkC(pkA, skA, rA)(pkG, skG, skC )(pkB, skB, rB)

txG, skG EncG(skC)

txA, skA,skB
σB EncG(skC)

EncG(skC *rB * rA)

skG
σG EncG(skC * rB * rA)
2Party ASσ,skC * rB * rA

skC * rB * rA

2Party ASσ18

A2L: Protocol Overview
Adaptor:(pkC) rB * rA

Adaptor: pkC(pkA, skA, rA)(pkG, skG, skC )(pkB, skB, rB)

txG, skG EncG(skC)

txA, skA,skB
σB EncG(skC)

EncG(skC *rB * rA)

skG
σG EncG(skC * rB * rA)
2Party ASσ,skC * rB * rA

2Party AS

skC * rB * rAσ

skCσ, skCσ
18

A2L: Protocol OverviewAdaptor:(pkC) rB * rA

Adaptor: pkC(pkA, skA, rA)(pkG, skG, skC )(pkB, skB, rB)

txG, skG EncG(skC)

txA, skA,skB
σB EncG(skC)

EncG(skC *rB * rA)

skG
σG EncG(skC * rB * rA)
2Party ASσ,
skC * rB * rA

2Party AS

skC * rB * rAσskCσ, skCσ18

A2L: Protocol Overview
Adaptor:(pkC) rB * rA

Adaptor: pkC(pkA, skA, rA)(pkG, skG, skC )(pkB, skB, rB)

txG, skG EncG(skC)

txA, skA,skB
σB EncG(skC)

EncG(skC *rB * rA)

skG
σG EncG(skC * rB * rA)
2Party ASσ,skC * rB * rA

2Party AS

skC * rB * rAσ

skCσ, skCσ
18

Discussion

19

Discussion‣ A2L achieves atomicity and unlinkability• Formally proven in the UC framework

19

Discussion‣ A2L achieves atomicity and unlinkability• Formally proven in the UC framework‣ 2Party AS can be instantiated with One-way homomorphic
functions, Schnorr or ECDSA• Backwards compatible with Bitcoin• Also compatible if Bitcoin adopts Schnorr

19Discussion‣ A2L achieves atomicity and unlinkability• Formally proven in the UC framework‣ 2Party AS can be instantiated with One-way homomorphic
functions, Schnorr or ECDSA• Backwards compatible with Bitcoin• Also compatible if Bitcoin adopts Schnorr‣ It requires only signature verification and timelocks (instead ofHTLC):• Interoperability with scriptless currencies (e.g., Monero)

19

Discussion‣ A2L achieves atomicity and unlinkability• Formally proven in the UC framework‣ 2Party AS can be instantiated with One-way homomorphic
functions, Schnorr or ECDSA• Backwards compatible with Bitcoin• Also compatible if Bitcoin adopts Schnorr‣ It requires only signature verification and timelocks (instead ofHTLC):• Interoperability with scriptless currencies (e.g., Monero)‣ Good for fungibility• Protocol results in a valid signature similar to any othertransaction• Other information (e.g., encryptions) are not included
19Evaluation‣ Prototype implementation in C
‣ We evaluate the computation and communication
overhead in LAN network• Comparison with TumbleBit
TumbleBit

A2L (Schnorr)

A2L (ECDSA)

Computation Overhead

600 ms

70 ms;
8x faster

110 ms;
5x fasterCommunication Overhead

326 KB

3.5 KB;
95x reduction

5 KB;
65x reduction‣ Number of operations and communication overhead are asymptoticallyreduced‣ TumbleBit uses cut-and-choose‣ Size of exchanged messages grow non-linearly in the security parameter
20

Take Home...
‣ A2L is a cryptographic protocol for PCHs that achieves security,unsinkability and interoperability‣ Formally specified and proven secure in the UC Framework‣ Advantages:• Fully backwards compatible with Bitcoin (and Schnorr if adopted
in Bitcoin), and scriptless cryptocurrencies (e.g., Monero)• The most efficient Bitcoin-compatible PCH‣ Paper available at https://eprint.iacr.org/2019/589.pdf‣ Implementation available at https://github.com/etairi/A2L

21

Take Home...
‣ A2L is a cryptographic protocol for PCHs that achieves security,unsinkability and interoperability‣ Formally specified and proven secure in the UC Framework‣ Advantages:• Fully backwards compatible with Bitcoin (and Schnorr if adopted
in Bitcoin), and scriptless cryptocurrencies (e.g., Monero)• The most efficient Bitcoin-compatible PCH‣ Paper available at https://eprint.iacr.org/2019/589.pdf‣ Implementation available at https://github.com/etairi/A2L
THANKS!

@pedrorechez21