OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding

Lefteris Kokoris-Kogias (@LefKok)
Decentralized and Distributed Systems Lab (DEDIS)
EPFL, IBM PhD Fellow, IC3

Scaling Bitcoin
2018-10-07, TokyoAcknowledgements

Philipp Jovanovic(EPFL, CH)

Linus Gasser(EPFL, CH)

Nicolas Gailly(EPFL, CH)

Ewa Syta(Trinity College, USA)

Bryan Ford
(EPFL, CH)2

Talk Outline•

Motivation•

OmniLedger•

Evaluation•

Conclusion

3

Talk Outline•

Motivation•

OmniLedger•

Evaluation•

Conclusion

4

Scaling Blockchains is More Important Than Ever …

5

Bitcoin vs OmniLedger
Bitcoin

OmniLedger*

Throughput~4 TPS~20.000 TPS

1-st Confirmation~10 minutes~1 second

Full Security~60 minutes~42 second

More Available
Resources

No performance
Gain

Linear Increase inThroughput* Configuration with 1120 validators against a 12.5% adversary
6Bitcoin vs OmniLedger
Bitcoin

OmniLedger*

Throughput~4 TPS~20.000 TPS

1-st Confirmation~10 minutes~1 second

Full Security~60 minutes~42 second

More Available
Resources

No performance
Gain

Linear Increase inThroughput* Configuration with 1120 validators against a 12.5% adversary

Scale-Out7

What we Want: Scale-Out Performance
Throughput [tx/sec]

Ideal system
Bitcoinn2n3n4n5n6n

Number of Validators

Scale-out: Throughput increases linearly with the available resources.
8

… But Scaling Blockchains is Not Easy

9

Distributed Ledger Landscape
Decentralization

RSCoinEln

OmniLedgeroi

Scale-OutzC

astic

ByoL. Luu et al., A Secure Sharding
Protocol for Open Blockchains,CCS 2016

E. Kokoris Kogias et al., Enhancing
Bitcoin Security and Performance with
Strong Consistency via Collective Signing,
USENIX Security 2016

Security

G. Danezis and S. Meiklejohn, Centrally Banked Cryptocurrencies, NDSS 201610

No Scale-Out (Bitcoin)

Blockchain

11

Scale-Out (OmniLedger)• How do validators choose which blockchain to work on?
• How can I pay a yellow vendor with greencoins?

ShardShard

Double Throughput

12

Random Validator Assignment•

Let validators choose? —> All malicious validators can choose thesame chain•Randomly assign validators? —> Preserve security for adequately
large shard size13

Bootstraping Identies••

Key blocks:•

PoW & share value•

Leader election

Microblocks:•

Validating clienttransactions•

Issued by the leader

1

12Keyblock2

3

Microblock45

Collective Signature

14

Strawman: SimpleLedger
Overview•

rnde

Trusted randomness
beaconEvolves in epochs e•

Trusted randomness beacon emits random value rnde•

Validators:‣Use rnde to compute shard assignment(ensures shard security)‣

Process tx using consensus
within one shard (ByzCoin)

Validators

Shardledgers

Shard 1

Shard 2

Shard 3(ByzCoin group)(ByzCoin group)(ByzCoin group)
15

Strawman: SimpleLedger
Security Drawbacks•

Randomness beacon: trusted third party•

No tx processing during validator re-assignment•

No cross-shard tx support

Performance Drawbacks•

ByzCoin failure mode•

High storage and bootstrapping cost•

Throughput vs. latency trade-off
16

Talk Outline•

Motivation•

OmniLedger•

Evaluation•

Conclusion

17

Roadmap
SimpleLedger
Sharding via distributed randomness

Security

Smooth epoch transitions
Atomix: Atomic cross-shard txs

ByzCoinX: Robust BFT consensus

Performance

Shard ledger pruning
Trust-but-verify validation: Throughput / Latency trade-oﬀ

OmniLedger

18Roadmap
SimpleLedger
Sharding via distributed randomness

Security

Smooth epoch transitions
Atomix: Atomic cross-shard txs

ByzCoinX: Robust BFT consensus

Performance

Shard ledger pruning
Trust-but-verify validation: Throughput / Latency trade-oﬀ

OmniLedger

19

Roadmap
SimpleLedger
Sharding via distributed randomness

Security

Smooth epoch transitions
Atomix: Atomic cross-shard txs

ByzCoinX: Robust BFT consensus

Performance

Shard ledger pruningTrust-but-verify validation: Throughput / Latency trade-oﬀ

OmniLedger

20

Shard Validator Assignment
1. Temp. leader election(Can be biased)

2. Randomness generation(Output is unbiasable)

3. Shard assignment(using rnde)

Temp. leader
Verifiablerandomness rnde

RandHound*Validators

Validators(sharded)* Syta, Ewa, et al. "Scalable bias-resistant distributed randomness." Oakland ‘1721

Roadmap
SimpleLedger
Sharding via distributed randomness

Security

Smooth epoch transitions
Atomix: Atomic cross-shard txs

ByzCoinX: Robust BFT consensus

Performance

Shard ledger pruning
Trust-but-verify validation: Throughput / Latency trade-oﬀ

OmniLedger

22

Two-Phase Commit
Coordinator

ServerQuery to commit
prepare / abort
Commit / Rollback
commit / abort

23

Atomix: Cross-Shard Transactions
Challenge:•

Cross-shard tx commit atomically or abort
eventually(1) Initialize(2) Lock
accept1(3a) Unlock to Commit

clientclient

accept2

committx

cross-shard transaction tx

Solution: Atomix•inputs
shard1
shard2

Client-managed protocol
1. Client sends cross-shard tx to input
shardsoutputs
shard3
shard1shard2

clienttx

shard3(2) Locktx
accept1(a) If all input shards accept, commit tooutput shard, otherwise(b) abort and reclaim input funds

shard1

shard2clientshard3
shard1

shard2

shard2

shard3(3b) Unlock to Abort

reject2

2. Collect ACK/ERR proofs from input
shardsshard1

shard3clientreclaimtx inputs

shard1

shard2

shard3The Atomix protocol for secure cross-shard transactions

24

Roadmap
SimpleLedger
Sharding via distributed randomness

Security

Smooth epoch transitions
Atomix: Atomic cross-shard txs

ByzCoinX: Robust BFT consensusPerformance

Shard ledger pruning
Trust-but-verify validation: Throughput / Latency trade-oﬀ

OmniLedger

25

Trust-but-Verify Transaction Validation
Challenge:•

optimisticallyvalidatedblocks

Latency vs. throughput trade-off

Solution:•

Two-level “trust-but-verify” validation•Low latency:‣•tx

clients

Optimistically validate transactions by“insecure” shards

sbj,e-1
shard ledger(with state block)tx

High throughput:‣

finalized blocktx

optimisticvalidators

corevalidators

Batch optimistically validated blocks andaudit by “secure” shards26

Talk Outline•

Motivation•

OmniLedger•

Evaluation•

Conclusion

27

Implementation & Experimental Setup
Implementation•••

OmniLedger and its subprotocols(ByzCoinX, Atomix, etc.) implementedin GoDeterLab Setup•

Based on DEDIS code‣

Kyber crypto library‣

Onet network library‣

Cothority framework

https://github.com/dedis•

48 physical machines up
to 1800 clients‣Intel Xeon E5-2420 v2(6 cores @ 2.2 GHz)

‣24 GB RAM‣

10 Gbps network link

Network restrictions (perclient)‣

20 Mbps bandwidth‣

200 ms round-trip latency
28

Evaluation: Scale-Out#validators (#shards)

70 (1) 140 (2) 280 (4) 560 (8) 1120 (16)OmniLedger (tx/sec)

439

869

1674

3240

5850

Bitcoin (tx/sec)~4~4~4~4~4

Scale-out throughput for 12.5%-adversary
and shard size 70 and 1200 validators

29

Evaluation: Throughput

Results for 1800 validators

30

Evaluation: Latency
Transaction confirmation latency in seconds for regular and mutli-level validation#shards, adversary

4, 1%

25, 5%

70, 12.5%

600, 25%

regular validation

1.38

5.99

8.04

14.52

1 MB blocks

1st lvl. validation

1.38

1.38

1.38

4.48

500 KB blocks

2nd lvl. validation

1.38

55.89

41.89

62.96

Bitcoin

600

600

600

600

16 MB blocks

latency increase since optimisticallyvalidated blocks are batched intolarger blocks for final validation toget better throughput
31

Talk Outline•

Motivation•

OmniLedger•

Experimental Results•

Conclusion

32

Conclusion

Epoch randomness rnde(RandHound)

Validators•

OmniLedger – Secure scale-out distributed ledger
framework‣

Atomix: Client-managed cross-shard tx‣ByzCoinX: Robust intra-shard BFT consensus‣

Sharding: Visa-level throughput and beyond‣‣

Trust-but-verify validation: No latency vs.
throughput tradeoff

Shardledgers

Shard 1

Shard 2

Shard 3

(ByzCoinX group)(ByzCoinX group)(ByzCoinX group)

For PoW, PoS, permissioned, etc.

•

Code: https://github.com/dedis•

Contact: eleftherios.kokoriskogias@epfl.ch , @LefKok

tx2,intx1,intx3,out
Client(Atomix coordinator)
33