Skip to content

Instantly share code, notes, and snippets.

@Haseeb-Qureshi

Haseeb-Qureshi/spacemesh.md

Created October 10, 2018 18:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Haseeb-Qureshi/dc95fae064c5c040d635d5804cdbb597 to your computer and use it in GitHub Desktop.
Save Haseeb-Qureshi/dc95fae064c5c040d635d5804cdbb597 to your computer and use it in GitHub Desktop.
Download ZIP
Spacemesh talk @ CESC
Raw
spacemesh.md

Spacemesh

Tal Moran

What goes into a cryptocurrency?

  • Distributed consensus
    • Everyone agrees on the current state
    • State evolves according to agreed rules
  • Incentive mechanisms
    • Running a cryptocurrency protocol has costs (CPU, storage, network)
    • Should incentivize honest behavior

Consensus is hard

  • Classic problem in distributed computing
    • Still lots of study today
    • Challenge: hard to know who to trust
  • Permissionless consensus is impossible in the traditional model
    • Adversaries can create unlimited sybil identities
    • Proven fact: without an honest majority, it's impossible to get consensus

Nakamoto's Magic Trick

  • Instead of counting people / votes, let's count computational work
  • Easy to measure, hard to fake
  • Leads to a new assumption: honest parties control majority of CPU power

From PoW to Consensus (Nakamoto style)

  • Elect a "leader" by lottery (solving PoW)
  • Leader determines next block
    • Most of the time, only one leader is elected (no fork)
    • We have consensus!
  • If multiple leaders are elected in close probability (multiple blocks)
    • Then we have a race...
      • In a race, only one of the blocks will be rewarded, and the other will be discarded

The problem with races

  • Races are time-sensitive
    • High competitive cost for large blocks (smaller blocks propagate faster)
  • Leads to perverse incentives
    • Sometimes better to withhold blocks (selfish mining)
  • Unfair reward distribution
    • Previous leader gets a head start, since they see their newest block first

Downsides of PoW

  • Computational power is an expensive, limited resource
  • Honest miners must use as much CPU power as they can
    • Otherwise, honest majority assumption is violated
  • High mining costs -> higher transaction costs
    • Must reimburse miners to ensure they participate

Spacemesh Motivations

  • Replace PoW with another environmentally-friendly resource
  • Remove leader-election requirement
    • Fair reward distribution
    • High throughput
    • Incentive-compatibility
      • I.e., people act honestly in accordance with their incentives, no trickiness like block withholding
  • Formally analyze and prove security
    • Big goal for Spacemesh

Alternatives to PoW?

  • "Money": proofs of stake
    • Very cheap (only need signatures)
  • Storage: proofs of space-time
    • Keeping your disk full for a period of time
    • "Proofs of space" also satisfy proofs of space-time, but proof of space-time is the preferred definition.
    • Much cheaper than PoW (but not quite as cheap as PoS)
    • Negligible environmental cost

Why not Proofs of Stake?

  • Very cheap to simulate / construct new forked chains
    • Therefore requires additional assumptions for security
  • Not (quite) permissionless / decentralized
    • Owners of current stake must agree to sell
    • High minimum stake in many existing systems
      • E.g., Ethereum may cost 100s of Ether to join as stakers
  • Hard to solve "circularity" problem
    • Security depends on the integrity of the stake, which depends on... the integrity of the stake...

Spacemesh Consensus Overview

  • Note: will be sparse on technical details. Based on Meshcash paper from 2017
  • First there's a lottery to pick "block generators"
    • An individual is eligible to participate only if they possess a valid Proof of Spacetime
    • Average size of sample is fixed
  • Accept all valid blocks
    • Anyone who is a "winning" eligible party gets to generate a block
    • If you're a little bit slow it's fine, so long as you're within reasonable bounds
  • Organize blocks into "layers"
    • Layer starts every clock "tick"
    • Blocks explicitly declare their own layer (I'm in layer 5, i.e. block height of 5)
  • Total order on blocks
    • Ordered first by layer number (between layers)
    • Second ordering on hash of block
  • But there's a problem! Honest parties don't agree on the exact time for each block.
    • We can't accept blocks that come too late
    • If we accepted blocks regardless of when they claim to have been generated, then accepting late blocks would break immutability of the blockchain history (since they can go back and change early history)
  • We have each block vote on the validity of previous blocks
    • To decide whether a block is valid, we look not at timing, but use the majority of votes from other blocks
    • We assume the majority of blocks are generated honestly (this is due to our majority honest assumption)
    • When we sample randomly, almost always we'll get a majority-honest sample
  • If all honest blocks vote the same way, the we'll achieve consensus
    • Basically analogous to Bitcoin—this guarantees irreversibility, since honest blocks grow at a faster rate than dishonest blocks
  • This protocol is known as the Tortoise protocol. It goes kind of slowly though. Not the whole story...

Introducing the Hare

  • The tortoise protocol in a nutshell:
    • Achieves consensus on blocks if all honest parties agree on validity.
    • "Irreversible" consensus after enough votes have been cast
      • One layer is enough!
  • But honest parties might not agree on new blocks!
  • Hare protocol: a BFT agreement protocol on recent blocks
    • Can choose different hare protocols for different security / efficiency tradeoffs
    • Can use a synchronous protocol here to get a better security threshold (50%)
    • This let's all honest parties agree on validity of recent blocks
  • Honest parties can determine the validity of recent blocks using the hare protocol (but these blocks don't have enough votes yet to solidify in the tortoise protocol). For older history, we can determine their validity using the tortoise protocol.

From block order to a cryptocurrency

  • So now we have a total order on blocks
  • But a cryptocurrency cares about a total ordering on transactions
  • Of course, a total ordering on blocks implies a total transaction order
    • Order by blocks first, then by hash within each block.
    • We don't care if there are conflicting transactions, or transactions repeated in each block. If there's a conflict, we just accept the first instance.

PoST vs PoW challenges

  • In Proofs of work, effort is spent to "vote"
    • Easy to set up robust lotteries, hard to cheat
    • Non-interactive (self-certifying)
  • Proofs of spacetime is based on storage
    • Stored data can't depend on vote: i.e., there's "nothing at stake." You don't expend significant energy to vote.
    • Time is subjective—requires some interaction to prove historicity.
      • Providing a proof of storage in and of itself does not prove storage over time.

Dealing with "Nothing at Stake"

  • Space is bound to a specific ID
    • Creating new IDs is costly
    • By honest majority assumption, adversary can't create too many fake IDs
  • Reuse of an ID for two different "votes" is easily detected
    • Will "cancel" that vote
    • Punishments / slashing is not necessary for security
  • Analysis does not depend on economic assumptions

Dealing with Costless History Extension (proving historicity)

  • Non-interactive proofs of space time
    • Contains Proof of Elapsed Time
    • Proof of Space is bound with Proof of Elapsed Time to produce Proof of Spacetime
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment