Cryptographic Hash Functions and Blockchain Technology

Lecture 2: Basic Cryptography Lecture 2: Basic Cryptography Cryptographic Hash Functions Centralized Blockchain Centralized Blockchain Hash Accumulators Merkle trees Decentralized Blockchain Decentralized Blockchain Digital Signatures

Example: Hash Functions Example: Hash Functions Uniform output Division hashing Simple deterministic function Collision resistant

Cryptographic Hash Functions Cryptographic Hash Functions Canonical applications: Canonical applications: Extra Properties: Extra Properties: Message digest Adversarial Adversarial collision resistance birthday paradox Commitments One way function Puzzle generation mining process Specialized one way function

Hash Functions Hash Functions Defining Properties: Defining Properties: Canonical application: Canonical application: Arbitrary sized inputs Hash Tables Fixed size deterministic output Store and retrieve data records Efficiently computable Minimize collisions

SHA SHA- -256 256 Used by Bitcoin altcoins Considered secure No provable security Compression function: 768 bits -> 256 bits Random oracle model Random oracle model: ideal hash function assumption in security analysis. Merkle-Damgard transform to handle arbitrary sized inputs

Cryptographic Hash Function Cryptographic Hash Function Extra Property: Extra Property: Canonical application: Canonical application: Puzzle generation mining process Specialized one way function Hash Hash(nonce, (nonce, block block- -hash) < Threshold hash) < Threshold

Hash Pointer Hash Pointer Hash of the information acts as Hash of the information acts as pointer to location of information pointer to location of information Regular pointers can be used to build data structures: linked lists, binary trees. Regular pointer Regular pointer: retrieve information Hash pointers can also be used to build related data structures. Crucially useful for blockchains. In fact, blockchain itself is a hash pointer based data structure. Hash pointer Hash pointer: retrieve information and verify the information has not changed

Blockchain: a linked list via hash pointers Blockchain: a linked list via hash pointers Block Block: Header + Data Application Application: tamper evident information log Header: Header: Pointer to previous block = hash of the previous block Head of the chain being known is enough to find tamper evidence in any internal block Data Data: information specific to the block Hence the phrase: block chain blockchain block chain blockchain

Merkle tree Merkle tree Proof of Membership Proof of Membership Binary tree of hash pointers Binary tree of hash pointers Proof of Non Proof of Non- -membership membership Retain only the root of the tree Tamper of any data in the bottom of the tree is evident

Blockchain with Merkle Trees Blockchain with Merkle Trees Block Block: Header + Data Application Application: Centralized tamper evident information log with efficient proof of membership of any data entry Header: Header: Pointer to previous block = hash of the previous block header and Merkle root of data of previous block Head of the chain being known is enough to find tamper evidence in any internal block Data Data: information specific to the block

Decentralizing the Blockchain Decentralizing the Blockchain Digital Signatures Decentralized Identity Management Elements of a cryptocurrency

Digital Signatures Digital Signatures Signature Signature Key generation Key generation Sig = sign(secretkey, message) (secretkey, publickey) = Generatekeys(keysize) Randomized function Verification Verification verify(publickey, Sig, message)

Unforgeable Signatures Unforgeable Signatures ECDSA ECDSA Unforgeable Unforgeable Elliptic Curve Digital Signature Algorithms Computationally hard to generate a verifiable signature without knowing the secret key Cryptographicaly secure against an adaptive adversary

Signatures in Practice Signatures in Practice Elliptic Curve Digital Signature Algorithm (ECDSA) Standard part of crypto libraries Public key: 512 bits Secret key: 256 bits Message: Note: can sign hash of message 256 bits Signature: 512 bits

Decentralized Identity Management Decentralized Identity Management Public keys are your identity address in Bitcoin terminology Can create multiple identities (publickey, secretkey) pairs publish publickey sign using secretkey Can create oneself verifiable by others

Cryptocurrency: Coin Management Cryptocurrency: Coin Management Cryptocurrency: data = transactions involving coins : data = transactions involving coins Createcoins Createcoins Paycoins Paycoins Creation signed by a user (identified via public key) each coin has a recipient (identified via public key) Transaction signed by a user consumed coins (list) coins created (list) Total wealth consumed = total wealth created

Cryptocurrency: Coin Management Cryptocurrency: Coin Management Cryptocurrency: data = transactions involving coins : data = transactions involving coins Coin Coin: (coinID, signature of Creator) Creator creates coins Transaction Transaction: Transfer of coin ownership This: This: hash pointer to coin Alice: Alice: public key of Alice Pay this this to Alice Alice Signed by owner of coin

Decentralized Blockchain Decentralized Blockchain Block Block: Header + Data + Signature List of signatures known ahead of time: permissioned permissioned blockchains Header: Header: Pointer to previous block = hash of the previous block header and Merkle root of data of previous block Questions Questions: 1. How is this list known ahead of time? 2. Which user in this list gets to add which block? 3. Who polices this? Data Data: information specific to the block Signature: Signature: one of the users signs the block (header+data) This is the topic of next lecture This is the topic of next lecture