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
Replace PoW with another environmentally-friendly resource
Remove leader-election requirement
Fair reward distribution
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
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