1 of 21

An introduction to proof of stake

2 of 21

Functions of proof of work

  • Availability: produce blocks, where those blocks contain transactions sent by users
  • Convergence: ensure that the network eventually agrees on the order of them (with overwhelmingly high probability)
  • Finality: once a chain is sufficiently agreed upon, it cannot be reverted

3 of 21

  • Problem 1: PoW consumes lots of electricity
  • Bitcoin: block rewards = $2.3m per day, economics suggests cost approaches this
  • Ethereum: $400k per day
  • Also hardware costs

4 of 21

  • Problem 2: mining centralization
  • Returns to scale in ASIC mining lead to a few companies controlling the network
  • “ASIC-resistant” mining area of research but effectiveness not clear

5 of 21

  • Problem 3: weak finality guarantees
  • Problem 4: selfish mining and other attacks
  • Problem 5: suboptimal light client support

…...

6 of 21

Proof of stake

  • Newer kind of consensus algorithm
  • Pioneered by Peercoin (2011), now many versions exist (NXT, Tendermint, Flying Fox, etc)

7 of 21

My intuition: “Virtual mining”

  • PoW: $1000 -> miner -> stochastically generate blocks
  • PoS: $1000 -> 83 ETH -> virtual miner (convert in protocol) -> protocol lets you stochastically generate blocks

8 of 21

The NXT approach

  • Every block has a “generation signature”

GS(genesis) = 0

GS(block) = sha256(GS(parent), parent.validator)

  • The GS of a block is used to randomly sample the validator for the next block
  • Samples taken from a “validator set”, which you can join by depositing NXT + waiting 1440 blocks

9 of 21

The NXT approach

  • The GS actually generates a sequence of validators
  • If validator 0 doesn’t show up for a minute, then validator 1 has a chance, etc
  • Note: a boundary condition is possible: validator 0 shows up at the last second, two blocks in conflict
    • “Longest chain” mechanism resolves, as in PoW

10 of 21

The NXT approach

  • Possible to predict validator sequence ~1/f blocks ahead of time (where f is the percentage that fail to show up)
  • This opens up an attack: you can manipulate randomness by failing to make a block, and predict when this would be profitable
  • http://vitalik.ca/files/randomness.html
  • Predictability also opens DDoS attacks

11 of 21

Nothing at stake

12 of 21

Solution 1: “original Slasher”

  • Pre-determine validators for X blocks (eg. X = 500)
  • Validators must post a deposit before signing a block, if they double-sign they get penalized
  • Bentov et al: use multi-block-sourced randomness (eg. per-bit majority vote) to reduce exploitation vulnerability http://arxiv.org/pdf/1406.5694.pdf
  • Medium-range collusion attacks and DDoS attacks possible

13 of 21

Solution 2: “Slasher 2.0”

  • A block gives you reward +R if on the main chain, penalty -R if off the main chain
  • Replicates economics of proof of work
  • Can be combined with stronger randomness

14 of 21

More secure randomness: RANDAO-style

  • Validators, when placing deposits, commit to sha3^100000(x)
  • Creating each block requires “unwrapping a layer of the onion”
    • Protocol can check revealed sha3^n(x) against previously revealed sha3^(n+1)(x)
  • Sum of all revealed hashes used as random seed
  • Future validators only “visible” one block in advance

15 of 21

More secure randomness: private randomness

  • Say the current random seed (from prior slide mechanism) is S
  • Any validator can make next block after X seconds where X depends on sha3(r + S), where r is the hash that validator will be revealing
  • Only the validator knows they will make the next block, opaque to everyone else - PoW-equivalent DoS resistance

16 of 21

BFT-based proof of stake

  • Randomness selects N validators, those N validators must use a BFT algorithm (PBFT, HoneyBadger, etc) to agree on the next block
  • Dominic Williams: use a deterministic threshold signature created in round N consensus to select round N+1 consensus (perfect unexploitability assuming ⅔+ε honesty assumption)

17 of 21

Economic finality

  • Validators can make stronger “claims” about previous blocks
  • Get higher rewards if correct, but very high penalties if false
  • Can use scoring rules to determine rewards+penalties

18 of 21

Economic finality

  • Goal 1: make reverts very expensive even for colluding majority
  • Goal 2: O(1) light client syncing
  • Goal 3: offline light client verification

19 of 21

Light client syncing

20 of 21

Weak subjectivity

  • Problem: deposits last finite amount of time
  • If an attacker can acquire 51%+ of very old keys (after deposits withdrawn), they can make a blockchain that looks convincing to an offline observer
  • Hence, security model must be adjusted: nodes must log on and sync up every X days (X = length of deposit); reverting finalized blocks impossible

21 of 21

Stuff to think about