WIXLIB

1. Introduction ofBitcoin and BlockchainIERG5590/IEMS5709 “Advanced Blockchain”Spring 2020Sherman S. M. Chowbased on the slides byFoteini Baldimtsi (George Mason University)http://www.baldimtsi.com/teaching/cs795 sp17which in turns used the slides byStefan Dziembowski (University of Warsaw)https://www.crypto.edu.pl/dziembowski-talks

What is this lecture about? How are bitcoins generated? Can I mine my own?How does bitcoin transaction work? orHow the blockchain works for recording your transaction?It’s “electronic money.” How to prevent double-spending?What if we have different views of the blockchain state?Any other mechanism to maintain the distributed ledger?

Why Blockchain Technologies?

Common types of paymentsCommon characteristic?Trust to a financial institution

Common types of payments.

The Bitcoin Revolution.

The Bitcoin RevolutionDecentralized peer-to-peer payment system- which works as currency: has units of value- which can be exchanged for “real money”.Proposed by “Satoshi Nakamoto” in 2008

Why should I care about bitcoin?1) Very small fees ( USD 0.1)2) Fast transactions (10 - 60 minutes)3) Accepted in thousands of businesses

Some numbersBitcoin market capital: 14 billion USD (Jan 2017)Current exchange rate: 1BTC 921 USD (23 Jan. 2017)Highest price: 1216 USD (17 Nov. 2013) and 1150 Dec 2016

Overview of Bitcoin TechnologyA combination of techniques from Security Distributed Systems Economicsand Cryptography: This lecture keeps it to “minimal”.(We’ll devote a few weeks to talk about those :)

Bitcoin UsersPermissionless: Everyone can join – just generates a key pairAddresspublic keyPK: hUK67H9fyg(secret)private keySK: z4Pxc2kKn3Alice“Unspent transaction”: A user can have multiple such key pairs, each is “unspent”PK: p2Pknb7frTSK: n52Hb9KlpBobWhy not just call it money? 1) It’s created by a transaction. 2) It’s not your “account”.The difference will be clearer when we talk about the account model of Ethernum.

Bitcoin TransactionsTransactions use digital signatures (in turns use hash function)BobAlicePK: hUK67H9fygSK: z4Pxc2kKn3PK: p2Pknb7frThUK67H9fyg sends 1to p2Pknb7frTSK: n52Hb9KlpTransaction TPK served as the AddressT signed under Alice’s SKA transaction is valid only if thesignature verifies

Main problem with the digital moneyDouble spending 16fab13fc689016fab13fc6890Bits are easier to copy than paper!

How bitcoin prevents double-spendingThe users emulate a public write-only bulletin-board containing alist of transactions.A transaction is of a form:“User P1 transfers a coin #16fab13fc6890 to user P2”This prevents double spending.you’vealreadyspent thiscoin!16fab13fc6890

Transaction table: the Bitcoin BlockchainTime tAlice sends 1to BobAlice sends 0.7to ChrisAlice sends 0.3to Alice’Bob sends 1.2to DaveDave sends 0.2to Chris.Time t 1Stores every transaction(transferring to others and yourself)example:Time tTime t 125AliceBob0.3AliceRequired properties: Append only Cannot revise existing blocks Distributed4.8Bob

Who maintains the Bitcoin Blockchain?In traditional payment systems thatwould a financial institution.Time tAlice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisTime t 1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto Chris.Miners:specialtype of userpeer-to-peer

Bulletin-board “Emulation”the “ideal” worlda protocol that“emulates” theideal worldMain difficulty: Some parties can cheat.Classical result: emulation is possible if the "majority is honest.”e.g., for 5 players, we can tolerate at most 2 "cheaters."

Who maintains the Bitcoin Blockchain?Every transaction isbroadcasted to all users.Is this the right view of the blockchain?Time tAlice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisVoting - Majority winsYesNoYesYesYesTime t 1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2.to Bobto Christo Daveto ChrisWorks well if users are all honestbut this is not the case in practicebecause “Sybil” can appear “for free” in a permissionless network

We have a problem!What does majority mean in a system that everyone is free to participate?Sybils: Multiple identities belonging to the same(malicious) user

How to check majority of comp. power?Majority is defined as the majority of computational power!Sybil creation doesn’t increase attackers computational power ;)“Measures” a user’s computational powerby how much time is needed for solving a “puzzle” the puzzle should be difficult to solve but, a solution should be easily verifiableIn Bitcoin, it is based on thecryptographic hash functionsH(x) DPuzzle: Given D find x!

How to add a block to the blockchain?.Time tAlice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisTime t 1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2.to Bobto Christo Daveto Chris1 blockA block is added every 10 minutes andhas size 1MB

How to add a block to the blockchain?.Time tAlice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisTime t 1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2.to Bobto Christo Daveto Chris1 blockA block is added every 10 minutes andhas size 1MB

How to add a block to the blockchain?Alice sends 1Aliceto BobBroadcastMiners

How to post to the blockchain?Just broadcast (over the Internet) your transaction to the miners.transaction TAnd hope they will add it to the next block.Important:They never add an invalidtransaction (e.g. double spending)the miners are incentivizedto do it.a chain with an invalid transactionis itself not valid, so no rationalminer would do it.

How to post to the blockchain?Alice sends 1to BobAliceBroadcastMinersMiners compete on who will make the next blockAlice sends 1Time tto BobAlice sends 1.Alice sends 0.7Bob sends 1.2Dave sends 1.to Bob solve a proof-of-work puzzleTransactions not yet onblockchainDave sends 0.2to Bobto Christo Daveto ChrisNew block

Main Principles1. It is computationally hard to extendthe chain.2. Once a miner finds an extension hebroadcasts it to everybody.3. The users will always accept “thelongest chain” as the valid one.the systemincentivizesthem to do it

Creating a new blockAlice sends 1Time tto BobAlice sends 1.Alice sends 0.7Bob sends 1.2Dave sends 1.to Bob solve a proof-of-work puzzleTransactions not yet onblockchainI found a new block!Block BDave sends 0.2to Bobto Christo Daveto ChrisNew block

Creating a new blockI found a new block!Block B.Time t-1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisTime tAlice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisTime t 1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisNew block

Creating a new blockI found a new block!Block BBlock B’.Time t-1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisTime tAlice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisTime t 1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto ChrisNew block

What if there is a “fork”?The “longest” chain counts.But how long? A few slides later “We have 2 different views”blockiblocki 1forkblocki 2block’i 2blocki 3block’i 3blocki 4this chain is valid

Does it make sense to “work” onthe shorter chain?blocki 1No!blocki 2block’i 2blocki 3block’i 3blocki 4Because everybody else is working onextending the longest chain.Recall: we assumed that the majorityfollows the protocol.

Longest chain winsTime t 1Alice sends 1Alice sends 0.7Bob sends 1.2.Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo Daveto Chris.Time tTime t-1Alice sends 1Alice sends 0.7Bob sends 1.2.Dave sends 0.2Dave sends 0.2to Bobto Christo Bobto Christo Daveto ChrisNew blockto Daveto ChrisTime t 1Alice sends 1ForkAlice sends 0.7Bob sends 1.2.Dave sends 0.2to Bobto Christo DaveTime t 2Alice sends 1Alice sends 0.7Bob sends 1.2.to ChrisNew blockDave sends 0.2to Bobto Christo Daveto Chris

ConsequencesThe system should quickly self-stabilize.If there is a fork then one branch will quickly die.Problem: what if your transaction ends up in a “deadbranch”?Recommendation: to be sure that it doesn’t happen wait6 blocks.

Can transactions be “reversed”?TTo reverse transactions., an adversary has to create a “fork in the past”.This looks very hard if she/he just has a minority of computing power(the honest miners will always be ahead of him).It gives the security, but also a “shortcoming” of decentralization.

How are the miners incentivized toparticipate in this game?Short answer: they are paid (in Bitcoins) for this.Can you mine bitcoin? Short answer: Yes SpecialhardwareHuge miningpools

Where does the money come from?we are here since July 2016https://www.bitcoinblockhalf.com

More detailsEach block contains a transaction that transfers thereward to the miner.Advantages:1. It provides incentives to be a miner.2. It also makes the miners interested in broadcastingnew block asap.this view was challenged in a recent paper:Ittay Eyal, Emin Gun SirerMajority is not Enough: Bitcoin Mining is Vulnerable

Problem with Bitcoin’s PoW1. high energy consumptioncosts moneybad forenvironment2. advantageous for people withdedicated hardware

Alternatives to PoWProof-of-stakeProof-of-knowledgeProof-of-space*

Proofs of StakeThe “voting power” depends on how much money one has. shares of coins“voting power”Justification: people who have the money are naturally interested in thestability of the currency.Currencies: BlackCoin, Peercoin, NXT, etc. Problem:1. How to distribute initial money?2. How to force coin owners to mine?

Proof of Knowledge (e.g., of a Private Key)I found a new block!Block BBlock BProof that I havethe right key!

Permissioned Blockchainfrom Proof-of-Knowledgefor example:

A couple of slides belong to Stefan Dziembowski and are free to distribute under thefollowing copyright. 2016 by Stefan Dziembowski. Permission to make digital or hard copies of part or all of thismaterial is currently granted without fee provided that copies are made only for personal orclassroom use, are not distributed for profit or commercial advantage, and that new copiesbear this notice and the full citation.

Bitcoin and Blockchain IERG5590/IEMS5709 “Advanced Blockchain” . The Bitcoin Revolution. Why should I care about bitcoin? 1) Very small fees ( USD 0.1) 2) Fast transactions (1