Proof of Work (continued) and Proof of Stake ============================================ What are the properties we want from Blockchain (from Dan's first lecture)? "Persistence" - The blockchain is append-only T-consistency: honest players agree on all but last T blocks of chain Self-consistency: a single player's at two times differs only in T blocks "Liveness" - Anyone can publish a transaction g-chain-growth: After T time, chain grows by T/g blocks mu-chain-quality: After T time mu fraction of blocks from honest players Want these things to happen with overwhelming probability as T grows Suppose chain propagation Delta << block-interval Will get a *convergence opportunity* if: 1) Delta time with no new blocks mined (so everyone at same length) 2) One block mined 3) Delta time with no new blocks mined Say Delta = 10s (~ 1 MiB block over 1 Mbps link), avg. block time 10min Turns out system survives attacker with 49.57% hashing power So Nakamoto picked a good block time target At 1 minute propagation, survive 47.2% attack See Orphan blocks represent wasted work Uncle blocks - orphans as part of history [Ethereum] Represent work invested in history, so give small reward to uncle miner DAGs - don't require blocks to be in a chain DAG provides partial order - allows parallel mining But must determinstically sort concurrent blocks for execution order Danger: Attackers work on parallel chain, disclose much later Might change outcome of transactions if introduces earlier spends Example: DAG labs PHANTOM Goal: prioritize blocks from good miners, then sort by hash Computes (approximates) Maximum k-cluster SubDAG on blocks Corresponds to those mined by honest majority of hashing power Do topological sort on these good blocks, add missing "bad" blocks Settlement finality: once an operation completed, will never be undone Does proof-of-work offer settlement finality? Under certain assumptions: 1. Attackers have less hashing power than honest players 2. After your transaction reaches a certain block depth Generally, cryptography tries to avoid assumptions like #1 Want constructs secure against arbitrarily powerful attacker E.g., every grain of sand a supercomputer trying to forge a signature? Should take >100 years to succeed [128-bit security] Want 10^20 years years, double your security parameter [key size] PoW problematic because: - We don't know how much power attacker has (can build up, rent) - We don't have a security parameter, just a block count to increase (once attacker has 51% power, increasing block count doesn't help) Partial solution: incentives Hope bad guys are greedy and mining shenanigans will cost them - lost mining rewards - lost value of current & future coins by tanking currency Sunk costs in mining equipment will dissuade from losing money (But beware hash algorithms conducive to rentals like GPU mining) Another problem with PoW: incredible energy wastage One recent study: 2.6-7.7 GW total, 300kWh per transaction Idea: cost of mining equipment makes people care about blockchain health Why not use cryptocurrency itself instead of equipment? Proof-of-Stake Alternative view: PoW solves consensus by electing one leader Maybe randomly select one coin to determine new block One approach: Scale proof-of-work by stake [peercoin] Define Coin-age as #coins * #blocks they've been sitting in same account If you have lots of coin age, means you are tying up wealth in coins So have vested interest in not tanking cryptocurrency Allow miners to spend coin-age (reset to 0) to reduce block difficulty Idea: make coin investment much bigger than equipment + power Problem: what if miner cashes in coins, then tries to rewrite history? At block n had lots of coins, at block n+1 have lots of dollars Now go back and fork block chain at block n--you have *nothing at stake* Note peercoin founder occasionally published PGP-signed checkpoint Coarser-grained centralized consensus prevented long-term rollback attacks Recall PBFT consensus from second lecture Solution to consensus in closed system with 3f+1 nodes, <=f malicious f bad nodes might be silent, so must work when only hear from 2f+1 nodes Key idea: Any set of Q of 2f+1 nodes contains a majority of honest nodes Worst case: Q contains all f bad nodes, still has (f+1)/(2f+1) honest Hence, any set Q of 2f+1 nodes is a *quorum* Any quorums Q, Q' will always intersect at >=1 honest node PBFT security as strong as digital signatures--no incentives required Why not just run PBFT for consensus on a blockchain? Problem: who are the 3f+1 nodes and how do we know 2f+1 are honest? Can't just enumerate the Bitcoin users Idea: have the coin owners be nodes in PBFT Instead of trusting hashing power owners to mine coins, trust coin owners But will PBFT scale to 10,000+ nodes? With difficulty Will coin owners even be online to participate? Mostly not--have a lot of coins, want them in cold storage Idea 2: coin owners elect council to run PBFT Known as Delegated Proof of Stake, or DPOS Examples: Tendermint, EOS, BitShares, Steemit, Lisk, Ark How are we doing with respect to persistence and liveness? Persistence: depends on council, maybe for blockchain health Liveness: more problematic What if council censors your attempts to vote for someone else? Might need hard fork to recover DPOS in practice: Why do you vote for someone? Council members agree to share mining revenue with their voters vote buying/bribery? market forces / serving constituents? People vote for highest expected payout: m*r/v m = mining reward, r = fraction returned to voters, v = #voters At same r, want candidate with least #voters still likely to win Why doesn't r reach 99.9%? mining cartels get monopoly Voting outside cartel carries risk of candidate losing or getting too many votes (making denominator v big) Note Bitshares has approval voting (everyone vote for as many as you want) So everyone votes for everyone What if we increase mining incentives by penalizing bad miners? No longer just motivate miners by blockchain health and coin value Take away ("slash") coins automatically if miners provably misbehaved Partially addresses nothing at stake if coins locked up when miners quit E.g., lock up coins to participate in BFT consensus protocol Get mining rewards for participating Withdraw coins at time T and immediately lose vote in BFT At time T + 4 months, you can withdraw your coins Now a nothing at stake attack must create a 4-month-deep fork If no one is offline more than a month, people won't accept fork Self-consistency trumps fork Ethereum proposes Casper, a finality gadget Doesn't replace PoW, instead runs every 100 PoW blocks to provide finality "Validators" deposit stake and send following vote every 100 blocks: v = validator identity (entity that deposited stake) s = hash of a *justified* checkpoint block (source) t = hash of a descendant block of s (target) h(s) = height of block s h(t) = height of block t A link s->t is a *supermajority link* if >2/3 voted for it (by stake) Two blocks s1 and s2 are *conflicting* if neither is in the other's history A block t is *justified* if - t is the genesis block, or - s->t is supermajority for some justified block s A block s is *finalized* if - s is justified, and - s->t is a supermajority link A validator gets slashed if it signs links s1->t1, s2->t2 such that 1. t1 != t2 && h(t1) = h(t2) (different targets at same height), or 2. h(s1) < h(s2) < h(t2) < h(t1) (nested links) Theorem: if >2/3 (by stake) honest, can't finalize conflicting blocks Let a_m -> a_{m+1} and b_n -> b_{n+1} finalize two conflicting blocks where a_1, a_2, ... and b_1, b_2, ... are the chains justifying them Note h(a_m) != h(b_n) or >=1/3 validators would get slashed (rule 1) Assume w.l.o.g. that m < n By same reasoning, no i such that h(b_i) \in { h(a_m), h(a_{m-1}) } So b's chain must have a link spanning a_{m-1}->a_m, violating 2 Subtlety when adding and removing validators Supermajority requires 2/3 of old and 2/3 of new validators What if validators disappear? Leak away their stake if not voting, to recover eventually But conflicting blocks if leak stake on one branch but not other Initially, Casper will just be a finality gadget Doesn't replace proof-of-work, just provides finality Only runs every 100 blocks, so can be slow Have many more voters exchanging messages than DPOS Ultimately Ethereum wants to be pure proof-of-stake, but not there yet Can PoS give us mining with no hashing work whatsoever w/o DPOS? New cryptograhpic tool: VRF (verifiable random function) Generate() -> (pk, sk) VRF(sk, x) -> (pi, r) where w/o pi or sk, r looks like random function of x Verify(pk, r, pi, x) -> Bool (true if r was valid) Key property: pk holder can't predict, sk holder can't manipulate Example implementation: Hash(UniqueSig(sk, x)) UniqeSig is digital signature with only one valid sig per pk and message E.g., RSA w. full-domain hash, or BLS signatures (B = Boneh) Does not work with randomized signatures such as ECDSA or Schnorr Leader election idea: Use VRF to pick a node Each coin gets associated with a VRF key pair (pk, sk) At each block, compute: x = seed || PROPOSAL || block-number proof, sorthash = VRF(sk, x) Everyone broadcasts signed Wait for a while, then take block with lowest sorthash If >2/3 of coins owned by honest party, best sorthash will often be honest Everyone will see same best proposed-block if wait long enough If best sorthash is bad node, or network delays longer than wait time Bad node could propose multiple conflicting blocks Algorand: use voting to agree on block Nodes relay all messages to each other So if one honest node sees a message all will eventually Proceed through a series of rounds, issuing three kinds of vote messages propose(v, VRF(sk, seed||round)): If only one value is safe from previous round, must use this for v Otherwise, use consensus input value (any block you think is good) soft-vote(v): tentatively want output value v (if honest leader) Each node must soft-vote exactly one value v in each round In rounds >=2, v must be "safe" according to previous round If only one safe value v, just soft-vote(v) Otherwise, chose proposal from node with lowest VRF sorthash cert-vote(v): certify that v received >2/3 quorum soft-votes in this round Don't send any cert-vote if no v received a quorum of soft-votes All honest nodes that cert-vote will chose same value v (otherwise >1/3 of nodes bad and sent multiple soft-votes) Consensus succeeds on value v if >2/3 cert-vote(v) received in round next-vote(V): state that V is a safe value for the next round V might be block hash v, or special value \bot meaning any value safe v is safe if guaranteed no 2/3 cert-vote(v') for v' != v in this round You can double-vote: next-vote(v) and next-vote(\bot) in same round Safety rules for next-vote: If you issued cert-vote(v), then only V=v is safe Otherwise, if you *didn't* issue a cert-vote this round: Whatever V received >2/3 in previous round is safe (including \bot) Any v with >2/3 soft-vote(v) in this round is safe Even soft-votes that trickle in after too late for cert-vote Only proceed to next round when >2/3 next-vote(V) for same V Some invariants for intuition: If <= 1/3 honest nodes cert-vote(v), won't terminate and output v If >1/3 honest nodes cert-vote(v), only v gets >2/3 next-vote, not \bot Once \bot does not get next vote, all future rounds will only have v Can we scale this by selecting DPOS-like council without voting? Straw man: select council by lowest Hash(prev-block, node-pubkey) What's wrong? attacker can predict how block affects council membership If attacker ever controls council, can manipulate next block to keep power Solution? Use VRFs Algorand uses *Sortition* to select committee: Users commit to pk (associate with stake coins) before knowing x E.g., x = seed||round||previous-block||role Choose the "best" \tau values of r for different nodes' VRF output Best could just be lowest value of x Slight optimization--get j shots at being best if you have j coins Saves you from having j different public keys Important sortition parameters \tau = target expected number of committee members (>1 because of failure) T = fraction of expected committee size required for quorum (> 2/3) Complications for permissionless Keep changing council with each sortition, could fork blockchain But if only one vote (terminate in first round), won't happen Mark consensus "tentative" if terminate in multiple rounds Otherwise, hold extra confirmation vote that consensus is "final" Transactions only finalized after final consensus Could have fork, but will not get final consensus Hold periodic meta-instance of algorand to choose between forks