Intro To Cryptography And Cryptocurrencies

Cryptocurrency TechnologiesCryptography and CryptocurrenciesIntro to Cryptography and Cryptocurrencies Cryptographic Hash Functions Hash Pointers and Data Structures– Block Chains– Merkle Trees Digital Signatures Public Keys and Identities Let’s design us some Digital Cash!Intro to Cryptography and Cryptocurrencies Cryptographic Hash Functions Hash Pointers and Data Structures– Block Chains– Merkle Trees Digital Signatures Public Keys and Identities Let’s design us some Digital Cash!1

Cryptocurrency TechnologiesCryptography and CryptocurrenciesCryptographic Hash FunctionHash Function: Mathematical Function with following 3properties:The input can be any string of any size.It produces a fixed-size output. (say, 256-bit long)Is efficiently computable. (say, O(n) for n-bit string)Such general hash function can be used to build hashtables, but they are not of much use in cryptocurrencies.What we need are cryptographic hash functions.Cryptographic Hash FunctionsA Hash Function is cryptographically secure if itsatisfies the following 3 security properties:Property 1: Collision ResistanceProperty 2: HidingProperty 3: “Puzzle Friendliness”2

Cryptocurrency TechnologiesCryptography and CryptocurrenciesCryptographic Hash FunctionsA Hash Function is cryptographically secure if itsatisfies the following 3 security properties:Property 1: Collision ResistanceProperty 2: HidingProperty 3: “Puzzle Friendliness”Crypto Hash Property 1: Collision ResistanceCollision Resistance: A hash function H is said to becollision resistant if it is infeasible to find twovalues, x and y, such that x ! y, yet H(x) H(y).xH(x) H(y)yIn other words: If we have x and H(x), we can “never”find an y with a matching H(y).3

Cryptocurrency TechnologiesCryptography and CryptocurrenciesCollision Resistance ?!Collisions do exist .possible outputspossible inputs but can anyone find them?Collision Resistance ?! (2)How to find a collisiontry 2130 randomly chosen inputs99.8% chance that two of them will collideThis works no matter what H is but it takes too long to matter4

Cryptocurrency TechnologiesCryptography and CryptocurrenciesCollision Resistance ?! (3)Q: Is there a faster way to find collisions?A: For some possible H’s, yes.For others, we don’t know of one.No H has been proven collision-free.Collision ResistanceApplication: Hash as a Message DigestIf we know that H(x) H(y), it is safe toassume that x y.Example: To recognize a file that we sawbefore, just remember its hash.This works because hash is small.5

Cryptocurrency TechnologiesCryptography and CryptocurrenciesCryptographic Hash FunctionsA Hash Function is cryptographically secure if itsatisfies the following 3 security properties:Property 1: Collision ResistanceProperty 2: HidingProperty 3: “Puzzle Friendliness”Crypto Hash Property 2: HidingWe want something like this:Given H(x), it is infeasible to find x.Example:H(“heads”)easy to find x!H(“tails”)The value for x is easy to find because thedistribution is not “spread out” (only two values!)6

Cryptocurrency TechnologiesCryptography and CryptocurrenciesCrypto Hash Property 2: Hiding (cont)Hiding: A hash function H is said to be hiding if when asecret value r is chosen from a probabilitydistribution that has high min-entropy, then, givenH(r x), it is infeasible to find x.“r x” stands for “r concatenated with x”“High min-entropy” means that the distribution is “veryspread out”, so that no particular value is chosen withmore than negligible probability.Application of Hiding Property: CommitmentWant to “seal a value in an envelope”, and“open the envelope” later.Commit to a value, reveal it later.7

Cryptocurrency TechnologiesCryptography and CryptocurrenciesApplication of Hiding Property: CommitmentCommitment Scheme consists of two algorithms: com : commit(msg,key) takes message and secret key, andreturns commitment verify(com,msg,key) returns true if com commit(msg,key)and false otherwise.We require two security properties: Hiding: Given com, it is infeasible to find msg. Binding: It is infeasible to find two pairs (msg,key) and(msg’,key’) s.t. msg ! msg’and commit(msg,key) commit (msg’,key’).Implementation of Commitment commit(msg,key) : H(key msg) verify(com,msg,key) : (H(key msg) com)Proof of security properties: Hiding: Given H(key msg), it is infeasible to find msg. Binding: It is infeasible to find msg ! msg’such that H(key msg) H(key msg’)8

Cryptocurrency TechnologiesCryptography and CryptocurrenciesCryptographic Hash FunctionsA Hash Function is cryptographically secure if itsatisfies the following 3 security properties:Property 1: Collision ResistanceProperty 2: HidingProperty 3: “Puzzle Friendliness”Crypto Hash Property 3: “Puzzle Friendliness”Puzzle Friendliness: A hash function H is said to bepuzzle friendly if for every possible n-bit outputvalue y, if k is chosen from a distribution with highmin-entropy, then it is infeasible to find x suchthat H(k x) y, in time significantly less than 2n.If a hash function is puzzle friendly, then there is nosolving strategy for this type of puzzle that is muchbetter than trying random values of x.Bitcoin mining is just such a computational puzzle.9

Cryptocurrency TechnologiesCryptography and CryptocurrenciesIntro to Cryptography and Cryptocurrencies Cryptographic Hash Functions Hash Pointers and Data Structures– Block Chains– Merkle Trees Digital Signatures Public Keys and Identities Let’s design us some Digital Cash!Hash PointersHash Pointer is: pointer to where some info is stored, and (cryptographic) hash of the infoGiven a Hash Pointer, we can ask to get the info back, and verify that it hasn’t changed10

Cryptocurrency TechnologiesCryptography and CryptocurrenciesHash PointersH( )(data)will draw hashpointers like thisHash PointersKey Idea:Build data structures with hash pointers.11

Cryptocurrency TechnologiesCryptography and CryptocurrenciesLinked List with Hash Pointers: “Block Chain”H( )prev: H( )prev: H( )prev: H( )datadatadatause case: tamper-evident logDetecting Tampering in Block ChainsH( )prev: H( )prev: H( )prev: H( )datadatadatause case: tamper-evident log12

Cryptocurrency TechnologiesCryptography and CryptocurrenciesBinary Trees with Hash Pointers: “Merkle Tree”H( )H( )H( )H( )H( )(data)H( )H( )H( )(data)H( )(data)(data)H( )(data)H( )(data)H( )H( )(data)H( )(data)Used in file systems (IPFS, Btrfs, ZFS), BitTorrent, Apache Wave, Git,various backup systems, Bitcoin, Ethereum, and database systems.Proving Membership in a Merkle TreeH( )H( )H( )H( )H( )H( )Single branches of the treecan be downloaded at a time.To prove that a data block isincluded in the treeonly requires showing blocksin the path from that datablock to the root.(data)13

Cryptocurrency TechnologiesCryptography and CryptocurrenciesBenefits of Merkle TreesTree holds many items . . . . . but just need to remember the root hashCan verify membership in O(log n) time/spaceVariant: sorted Merkle treecan verify non-membership in O(log n)(show items before, after the missing one)Beyond Merkle Trees .We can use hash pointer in any pointer-baseddata structure that has no cycles.14

Cryptocurrency TechnologiesCryptography and CryptocurrenciesIntro to Cryptography and Cryptocurrencies Cryptographic Hash Functions Hash Pointers and Data Structures– Block Chains– Merkle Trees Digital Signatures Public Keys and Identities Let’s design us some Digital Cash!Digital SignaturesQ: What do we want from signatures?Only you can sign, but anyone can verify.Signature is tied to a particular document,i.e., cannot be cut-and-pasted to anotherdocument.15

Cryptocurrency TechnologiesCryptography and CryptocurrenciesDigital Signature SchemeDigital Signature Scheme consists of 3 algorithms: (sk,pk) : generateKeys(keysize) generates a key pair– sk is secret key, used to sign messages– pk is public verification key, given to anybody sig : sign(sk, msg) outputs signature for msg with key sk. verify(pk,msg,sig) returns true if signature is valid andfalse otherwise.Requirements for Digital Signature SchemeValid signatures must verify!verify(pk, msg, sign(sk, msg)) trueSignatures must be unforgeable!An adversary who knows pk has seen signatures on messages ofher choicecannot produce a verifiable signature on anew message.16

Cryptocurrency TechnologiesCryptography and CryptocurrenciesThe “Unforgeability Game”(sk, pk)challengerattackerm0sign(sk, m0)m1sign(sk, m1).M, sigverify(pk, M, sig)M not in { m0, m1, }if true, attacker winsDigital Signatures in PracticeKey generation algorithms must be randomized. need good source of randomnessSign and verify are expensive operations forlarge messages.Fix: use H(msg) rather than msg.Check this out:Signing a hash pointer “covers” the whole datastructure!17

Cryptocurrency TechnologiesCryptography and CryptocurrenciesIntro to Cryptography and Cryptocurrencies Cryptographic Hash Functions Hash Pointers and Data Structures– Block Chains– Merkle Trees Digital Signatures Public Keys and Identities Let’s design us some Digital Cash!Signatures, Public Keys, and IdentitiesIf you see a signature sig such thatverify(pk, msg, sig) true,think of it aspk says, “[msg]”.Why?Because to “speak for” pk, you must know thematching secret key sk.18

Cryptocurrency TechnologiesCryptography and CryptocurrenciesHow to Create a new IdentityCreate a new, random key-pair (sk, pk)– pk is the public “name” you can use[usually better to use Hash(pk)]– sk lets you “speak for” the identityYou control the identity,because only you know sk.If pk “looks random”, nobody needs to know whoyou are.Decentralized Identity ManagementBy creating a key-pair,anybody can make a new identity at any time.Make as many as you want!No central point of coordination.These identities are called addresses in Bitcoin.19

Cryptocurrency TechnologiesCryptography and CryptocurrenciesIdentities and PrivacyAddresses are not directly connected to realworld identity.But observer can link together an address’activity over time, and make inferences aboutreal identity.We will talk later about privacy in Bitcoin . . .Intro to Cryptography and Cryptocurrencies Cryptographic Hash Functions Hash Pointers and Data Structures– Block Chains– Merkle Trees Digital Signatures Public Keys and Identities Let’s design us some Digital Cash!20

Cryptocurrency TechnologiesCryptography and CryptocurrenciesVanilla Cryptocurrency Ver. 0.0GoofyCoinGoofy can create new CoinsNew coin belong to me.signed by pkGoofyCreateCoin [uniqueCoinID]21

Cryptocurrency TechnologiesCryptography and CryptocurrenciesGoofy can spend the CoinsAlice owns it now.signed by pkGoofyPay to pkAlice : H( )signed by pkGoofyCreateCoin [uniqueCoinID]The Recipient can pass on the Coin againsigned by pkAlicePay to pkBob : H( )Bob owns it now.signed by pkGoofyPay to pkAlice : H( )signed by pkGoofyCreateCoin [uniqueCoinID]22

Cryptocurrency TechnologiesCryptography and CryptocurrenciesThe Recipient can also double-spend the coin!signed by pkAlicesigned by pkAlicePay to pkCharles : H( )Pay to pkBob : H( )Let’s use the coin again.signed by pkGoofyPay to pkAlice : H( )signed by pkGoofyCreateCoin [uniqueCoinID]Double-SpendingMain design challenge in all digital currencies23

Cryptocurrency TechnologiesCryptography and CryptocurrenciesVanilla Cryptocurrency Ver. 1.0ScroogeCoinRecord Transactions in central Block ChainScrooge publishes a history of all transactions(a block chain, signed by Scrooge)H( )prev: H( )transID:71prev: H( )transID:72prev: H( )transID:73transtranstransoptimization: put multiple transactions in the same block24