Scaling Bitcoin 2016 "Retarget" • October 9th Milan, Italy

ENHANCING BITCOIN SECURITY AND PERFORMANCEWITH STRONG CONSISTENCY VIA COLLECTIVE SIGNING
Lefteris Kokoris-Kogias, Philipp Jovanovic, Nicolas
Gailly, Ismail Khoffi, Linus Gasser and Bryan FordEPFL@LefKokSwiss Federal Institute of Technology LausanneBitcoin Blockchain
2o What we have now:o Real-time verification is not safe (1 hour of delay)o Throughput is low (4 tx/sec)

Byzcoin Blockchain
3o What can Byzcoin do:o Irrevocable transaction commitment in 20-90 seco Throughput up to 974 TPS
o Robust against double-spending, eclipsing, selfish
miningo Light-weight client verification (suitable for mobilephones)

How?
4o Use Practical Byzantine Fault Tolerance protocol toprovide non-probabilsitic strong consistencyo Use Collective Signing to scale PBFT and decrease
latencyo Use PoW to create hybrid permissionless BFT
o Use Bitcoin-NG to increase throughput

Talk Outline
5Bitcoin and its limitationso Strawman design: PBFTCoin
o Opening the consensus groupo From MACs to Collective Signingo Decoupling transaction verification from leader electiono Performance Evaluationo Future work and conclusionsoThe Blockchain
6

Problem Statement
7In Bitcoin there is no verifiable commitment of the systemthat a block will persist

1.
ooClients rely on probabilities to gain confidence.
Probability of successful fork-attack decreases exponentiallyTalk Outline
8Bitcoin and its limitationso Strawman design: PBFTCoin
o Opening the consensus groupo From MACs to Collective Signingo Decoupling transaction verification from leader electiono Performance Evaluationo Future work and conclusionsoStrawman Design: PBFTCoin63f+1 fixed “trustees” running PBFT* to withstand ffailureso Non-probabilistic strong consistency
oo Low latency
oblockchain

No forks/inconsistencies
o No double-spending*Practical Byzantine Fault Tolerance [Castro/Liskov]

blocktrustees
L leaderLStrawman Design: PBFTCoin
7Problem: Needs a static consensus groupo Problem: Scalability
ooDense communication pattern (limits consensus group size)oHigh client-side verification cost (excludes mobile phones/IoT clients)oAbsence of third-party verifiable proofs (limits number of clients)

Client Request Pre-Prepare PreparePrimary
Replica 2
Replica 3
Replica 4

CommitReplyTalk Outline
11Bitcoin and its limitationso Strawman design: PBFTCoin
o Opening the consensus groupo From MACs to Collective Signingo Decoupling transaction verification from leader electiono Performance Evaluationo Future work and conclusionsoOpening the Consensus Group12

PoW against Sybil attacks
o One share per blockoblockchaino % of shares ∝ hash-power
oshare window of size w

Window mechanism
o Protect from inactive minersblockshareminerL leaderLTalk Outline
13Bitcoin and its limitationso Strawman design: PBFTCoin
o Opening the consensus groupo From MACs to Collective Signingo Decoupling transaction verification from leader electiono Performance Evaluationo Future work and conclusionsoFrom MACs to Signing
14o

Substitute MAC-based authentication (symmetric crypto)
with public-key cryptographyo ECDSA provides more efficiency
o Third-party verifiable
o PoW Blockchain as PKI
o Enables sparser communication patterns (ring or star

topologies)From MACs to Collective Signing
15

oCan we get better communication patterns?
o Multicast protocols transmit information in sub-linear steps
o Use trees!!

oCan we allow for lightweight verification?
o Schnorr multisignatures could be verified in constant timeo Use signature aggregation!!

oSchnorr multisignatures + communication trees= Collective Signing [Syta et all, IEEE S&P ’16]

CoSi
16

Efficient collective signature, verifiable as asimple signature
o For the Ed25519 curveooo

82 bytes instead of 9KB for 144* co-signers
190 bytes instead of 63KB for 1008* co-signers* Numberof ~10minuteblocks in 1day/weektime window16Discussion
17CoSi is not a BFT protocolo PBFT can be implemented over two subsequent CoSi rounds
blockchaino Prepare roundshare window of size w
o Commit roundoblockshareminerL leader

LProblem Statement
18

In Bitcoin ByzCoin there is no a verifiable commitmentof the system that a block will persist
2. Throughput is limited by forks
1.

Increasing block size increases fork probability
o Liveness exacerbationoTalk Outline
19

Bitcoin and its limitationso Strawman design: PBFTCoin
o Opening the consensus groupoFrom MACs to Collective Signingo Decoupling transaction verification from leader electiono Performance Evaluationo Future work and conclusionsoBitcoin-NG [Eyal et all, NSDI ’16]
20

oMakes the observation that block mining implement twodistinct functionalitiesTransaction verificationo Leader electionoo

We enhance Bitcoin-NG with Byzantine consensus
No double-spendingo Non-propabilstic securityo Leader cannot misbehaveo21

Decoupling Transaction Verificationfrom Leader Electiono Key blocks:

12

o PoW & share valueo Leader electiono Microblocks:
o Validating client transactionso Issued by the leader

12Keyblock

3Microblock45

Collective Signature

Talk Outline
22Bitcoin and its limitationso Strawman design: PBFTCoin
o Opening the consensus groupo From MACs to Collective Signingo Decoupling transaction verification from leader electiono Performance Evaluationo Future work and conclusionsoPerformance Evaluation
23

oExperiments run on DeterLab network testbedo Up to 1,008* miners multiplexed atop 36 machineso Impose 200 ms latencies between all servers
o Impose 35 Mbps bandwidth per miner* 1008 = # of ~10-minute key-blocks in 1-week time window

Performance Evaluation24

oKey questions to evaluate:o What size consensus groups can ByzCoin scale to?
o What transaction throughput can it handle?

Consensus Latency
25

Throughput
26

Talk Outline
27

Bitcoin and its limitationso Strawman design: PBFTCoin
o Opening the consensus groupo From MACs to Collective Signingo Decoupling transaction verification from leader electiono Performance Evaluationo Future work and conclusionsoChallenges for Ongoing Work28

oAttacker with >= 1/3 of the shareso Switch to probabilistic consistency?

oCan currently only scale-up not scale-outo Split the state between different groups?

oLeader can exclude miners from the consensus
o Instead of burning the bitcoins, donate them?

FAQ
29

What happens when an attacker gets more than
1/3?
o Does selfish mining occur in the key-block chain?
o How is the consensus group size selected?
o How do the miners make money?
oSurviving 34% attacks
30

o Key-blocks keep being collectively signed with aneeded margin of 51%
o Strong consistency is not immediate
Blocks will commit after 6 confirmationso Window starts from the last committed blockoo Micro-blocks forfeit liveness, if 66% is not achieved

Defend Against Selfish Mining
31

The PoW chain is (almost) fair even under 34% attacks.

?

Choosing Window Size
32

Random sampling
experimento Probability that the system
picks less than c = ⌊ w/3 ⌋o P>0.99oHow do the miners make money?
33

And why participate?
o Coinbase profit is distributed among the active signers
o Same for microblock feeso Miner profits more when available the full windowo Miner keeps mining to get more shares that correspondto more revenue.

Future Work34

Alternatives to PoW
o Sharding to enable scaling-out
o Incremental deployment to existing cryptocurrencies
oo Model the system on Bitcoin’s adversary*?
o How do miners discover each other?
o Robustness against 34% attacks?
*Analysis of the Blockchain Protocol in Asynchronous Networks [Pass, Seeman, Shelat]

Conclusion
35

Use Collective Signing to scale BFT protocols
o Use PoW to create hybrid permissionless BFT
o Combine the above with Bitcoin-NG
o Demonstrate experimentally its practicality
oo 1MB blocks commit in ~24sec achieve ~150TPS
o 32MB blocks commit in ~90sec achieve ~1000TPSoByzCoin increases the robustness of Bitcoin.

Thank you
36

eleftherios.kokoriskogias@epfl.chpeople.epfl.ch/eleftherios.kokoriskogias@LefKokByzcoin: Bringing it all Together
37