Lec3: HashCash and Proof-of-work in Blockchain

HashCash

Hashcash CPU cost-function computes a token which can be used as a proof-of-work.

Cost-functions

• Cost-function should be efficiently verifiable, but parameterisably expensive to copute

MINT()

• Client must compute a token(denoted T) using a cost-function MINT() which is used to create tokens to participate in a protocol with a server

VALUE()

• Server will check the value of the token using an evaluation function VALUE()

 

Interactive and Non-Interactive Cost-function

Interactive Cost-function

CHAL()

• Server issues a challenge to the client - uses the CHAL() function to compute the challenge
• w = amount of work has to be done

 

Non-Interactive Cost-function

• Client choses its own challenge or random start value in the MINT() function
• There is no CHAL() function

 

Properties of Cost-functions

Publicly auditable cost-function

• can be efficiently verified by any third party without access to any trapdoor or secret information
• Cost for verification <<< Cost for minting a token

Fixed cost cost-function

• takes a fixed amount of resources to compute.
• The fastest algorithm to mint a fixed cost token is deterministic.

Probabilistic cost cost-fundtion

• cost to the client has a predictable expected time (but not guaranteed)
  • unbounded probabilistic cost: no limit, can take forever to compute in theory
  • bounded probablistic cost: has a limit

Trapdoor-free

• disadvantage of known solution cost-functions: challenger can ceaply create tokens of arbitrary value
• Trapdoor-free: there is no shortcut = no solution = server has no advantage in minting tokens.

Hashcash is a non-interactive, publicly auditable, trapdoor-free cost function with unbounded probabilistic cost.

 

Hashcash Cost-function

Notation

 

Hashcash is computed relative to a service-name s

• servers only accept tokens minted using their own service-name
• service-name can be any bit-string which uniquely identifies the service

• fatest algorithm for computing is brute force and there is no challenge -> trapdoor-free, non-interactive
• anyone can efficiently verify any published token -> publicly auditable

Hashcash example

w = k - log2L where k = size of bits

---

Proof-of-work in Blockchain

• Nonce is a counter in hashcash
• Summary of a payload contains a hash value of payload in a current block and other information
• Version, Hash of previous block, Summary of Payloads is fixed -> calculate Nonce

 

Proof-of-work (aka. Longest chain rule)

Blockchain can resolve disagreements using Proof-of-work (Longest chain rule)

• When chain forks, Blockchain takes the fork with most work(i.e. longest chain). When there's a tie, keeps working until one of the chains has the most work.
• All chains are valid
  • Fork chains don't affect to transactions. All transactions are recorded in both chains, but their ordering may be different because they are just added by the other miner.
• Incentive is going to the miner who computes the chain in the longest chain
  • In Bitcoin, miner can use the coin it receives after 100 maturation times (10min * 100 = 1000min)
  • transaction is recorded in a chain within a 10 min and reach in an immutable depth of chains after a few hours later.

Incentive System

• It is loss to one if it spends a time and effort for the shorter chain
  • make miners to select the block with the most work automatically
• PoW discourages people trying to add invalid blocks to chain
  • Miners spend a significant money to add a block to chain but if it's not valid, nobody accepts it

 

Disadvantage of Proof-of-work

Expensive: lots of energy used to generate proofs done by miners in Bitcoin

• use special-purpose mining devices (FPGA or GPU) which are optimized for PoW
• harmful to the environment

Slow: put a limit on transaction speed

• Even more than 10 min if you consider the potential disagreements, which must be resolved.
• Bitcoin rule of thumb is waiting for 6 blocks (about an hour) to be sure of transactions

 

Summary

How untrusted, self-interested miners keep the system working

• miners verify and spread out a new block to get a benefit
• each node needs to verify a new block to decide whether it starts to mine the next block or keep on current mining
• miners have a big incentive (BTCs) and have substantial capital invested in Bitcoin. -> So, they also have an incentive to avoid any attack that would undermine their investment.
• This works because Bitcoin is all about moving money around.
  • Other blockchain applications have to find alternative incentivising system.