Skip to content

Instantly share code, notes, and snippets.

@Haseeb-Qureshi
Created February 4, 2019 00:58
Show Gist options
  • Save Haseeb-Qureshi/a62e33e8872954277840ceff5a3bb43b to your computer and use it in GitHub Desktop.
Save Haseeb-Qureshi/a62e33e8872954277840ceff5a3bb43b to your computer and use it in GitHub Desktop.
Betting on Blockchain Consensus with Fantômette (SBC19)

Betting on Blockchain Consensus with Fantômette

Speaker: Sarah Azouvi

  • Bitcoin vs Traditional Consensus
    • Bitcoin is open memberships, participants unknown
    • One message broadcast per round
    • Incentives are at the core of its security
    • High energy consumption!
    • Slow...
  • Blockchain without PoW?
    • Proof of stake?
      • Stake instead of computation
    • Can we get the same guarantees?
    • Problems: nothing at stake, grinding, long-range attacks
    • Proposed solutions: PBFT style (e.g. Algorand), cryptographic (e.g., Ouroboros, Snow White)
    • PBFT-style has large overhead for large committee sizes though...
    • Can we use incentives to move away from PBFT-style consensus?
  • Incentives are very tricky in blockchain!
    • See: selfish mining, instability of Bitcoin without block rewards, bribery attacks
  • Created a new incentive model including...
    • Rational players
    • Byzantine players
    • Coalitions / cartels
  • Using BAR Model, which was first introduced by Jean-Philippe Martin (2005)
    • BAR = Byzantine Altruistic Rational
      • Three types of players:
        • Byzantine players (malicious)
        • Rational players (self-interested)
        • Altruistic players (honest)
    • Also want robustness, a property introduced by Ittai Abraham et al
      • Robustness = even if there are coalitions, individuals are incentivized to be honest
      • I.e., coalition-resistant Nash Equilibrium
    • And finally, immunity: a malicious player will not affect the utility of other players
  • We also want more traditional security properties (from Bitcoin Backbone Protocol):
    • Chain growth (liveness)
    • Chain quality (blocks mined are distributed roughly according to CPU power)
    • Common prefix (all miners should agree on view of prior blocks)
  • Now, to present Fantômette, which satisfies all these properties!
    • Has two phases:
      • Leader election
        • Instead of PoW
        • Publicly verifiable
        • Unpredictable (we don't want future leaders to be DoSed)
        • Each block should elect at least one leader
        • Liveness would be nice
      • Betting scheme
        • Use incentives to move away from PBFT-style protocols
          • You can kind of see PoW as a betting protocol
          • Essentially, by building on a chain, you are betting that it will be the longest
  • Leader election is accomplished by a random beacon
    • Inspired by the random beacon in Algorand
      • In short, we first initialize a random beacon
      • Then we use a VRF (verifiable random function) to the random beacon
        • This generates a random number
        • If random number is less than a target, then you get to mine a block
      • Verifiable delay function guarantees liveness
        • If no one is elected leader, a VRF is computed, then a new election is kicked off
    • High level: each block elects at least one leader
  • Core protocol of Fantômette:
    • blockDAG (inspired by PHANTOM of Sompolinski et al)
    • A block "bets" on its parent block
    • Each block references other blocks
    • In Fantômette, the more connections/references you have, the higher the score
      • I.e., reward connectivity
    • Break ties using the random beacon (adds determinism)
    • Can only reference blocks with a smaller score
      • This makes it that the dominant fork can reference a losing fork
      • But not vice versa
  • Incentive compatibility
    • Incentive to reference other blocks, since it increases your score
    • More likely to win when following the protocol
    • You want to publish your block as fast as possible to maximize references to you
  • Security properties
    • Chain growth & common prefix = convergence
      • Does this happen?
      • Yes, because the score of the main chain grows faster than forks
    • What about chain quality?
      • Yep, because of the fair leader election, we get a good distribution of stake
  • How to stop long range attacks?
    • Decentralized checkpointing!
      • After 2/3rds of participants have placed a bet on two blocks at height N
        • We can consider them "justified" such that no other blocks can be created at height N
        • From that point on, it is safe to checkpoint
  • Also performed simulations
    • Coalitions can improve their profits, but only in a limited way
    • It's normal to have some forks, but chain quality is achieved
    • Comparison with other PoS protocols:
      • Algorand has T * Tau messages per round
      • Snow White, Ouroboros Praos, and Fantômette all have O(1) messages / round
      • Algorand, Snow White, and Ouroboros Praos all depend on synchronized clocks for liveness
      • Fantômette depends on VDF for liveness
      • Algorand has no incentive model, Snow White and Ouroboros Praos have coalition Nash Equilibria
      • Fantômette has robust incentive model
  • Conclusion
    • BlockDAG is used to enforce accountability
    • Incentivize rational players to follow the protocol
    • Leverage incentives to create blockchain-based PoS consensus
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment