Expected Consensus #


Algorithm #

Expected Consensus (EC) is a probabilistic Byzantine fault-tolerant consensus protocol. At a high level, it operates by running a leader election every round in which, on expectation, one participant may be eligible to submit a block. EC guarantees that this winner will be anonymous until they reveal themselves by submitting a proof of their election. The miner can submit a number of such proofs per round and will be rewarded proportionally. Each proof can be derived from a Challenge Ticket produced by the Election PoSt. All valid blocks submitted in a given round form a Tipset. Every block in a Tipset adds weight to its chain. The ‘best’ chain is the one with the highest weight, which is to say that the fork choice rule is to choose the heaviest known chain. For more details on how to select the heaviest chain, see Chain Selection.

At a very high level, with every new block generated, a miner will craft a new ticket from the prior one in the chain appended with the current epoch number (i.e. parentTipset.epoch + 1 to start). While on expectation at least one block will be generated at every round, in cases where no one finds a block in a given round, a miner will increment the round number and attempt a new leader election (using the new input) thereby ensuring liveness in the protocol.

The Storage Power Consensus subsystem uses access to EC to use the following facilities:

  • Access to verifiable randomness for the protocol, derived from Tickets.
  • Running and verifying Secret Leader Election for block generation.
  • Access to a weighting function enabling Chain Selection by the chain manager.
  • Access to the most recently finalized tipset (see Finality in EC) available to all protocol participants.

import abi "github.com/filecoin-project/specs-actors/actors/abi"
import block "github.com/filecoin-project/specs/systems/filecoin_blockchain/struct/block"
import chain "github.com/filecoin-project/specs/systems/filecoin_blockchain/struct/chain"
import spowact "github.com/filecoin-project/specs-actors/actors/builtin/storage_power"

type ExpectedConsensus struct {
    expectedLeadersPerEpoch  UVarint
    expectedRewardPerEpoch   UVarint

    ComputeChainWeight(tipset chain.Tipset) block.ChainWeight
    IsValidConsensusFault(faults spowact.ConsensusFaultType, blocks [block.Block]) bool
    IsWinningChallengeTicket(
        challengeTicket    util.Bytes
        sectorPower        abi.StoragePower
        networkPower       abi.StoragePower
        numSectorsSampled  util.UVarint
        numSectorsMiner    util.UVarint
    ) bool

    log2b(x UVarint) UVarint
    wParams weightFunctionParameters
}

type weightFunctionParameters struct {
    wRatio_num  UVarint
    wRatio_den  UVarint
    wPrecision  UVarint
}
package storage_power_consensus

import (
	"math/big"

	abi "github.com/filecoin-project/specs-actors/actors/abi"
	spowact "github.com/filecoin-project/specs-actors/actors/builtin/storage_power"
	block "github.com/filecoin-project/specs/systems/filecoin_blockchain/struct/block"
	chain "github.com/filecoin-project/specs/systems/filecoin_blockchain/struct/chain"
	util "github.com/filecoin-project/specs/util"
)

func (self *ExpectedConsensus_I) ComputeChainWeight(tipset chain.Tipset) block.ChainWeight {
	util.IMPL_FINISH()
	return block.ChainWeight(0)
	// see expected_consensus.md for detail

	// numTickets := 0
	// for _, bl := range tipset.Blocks {
	//		numTickets += bl.ElectionPoSt.Candidates
	// }
	// wPowerFactor := self.log2b(spa.GetTotalPower())
	// wBlocksFactor_num := (wPowerFactor * numTickets * self.wParams.wRatio_num)
	// wBlocksFactor_den := self.expectedLeadersPerEpoch * self.wParams.wRatio_den
	// return tipset.ParentTipset.ChainWeight
	// 	+wPowerFactor * self.wParams.wPrecision
	// 	+(wBlocksFactor_num * self.wParams.wPrecision / wBlocksFactor_den)
}

func (self *ExpectedConsensus_I) IsValidConsensusFault(faults spowact.ConsensusFaultType, blocks []block.Block) bool {
	util.IMPL_FINISH()
	return false

	// validation checks before calling this method
	// - there should be exactly two block headers in proof
	// - block1 and block2 are two different blocks
	// - both blocks are mined by the same miner
	// - block1 is of the same or lower block height as block2

	// 1. double-fork mining fault
	// return block1.Epoch == block2.Epoch

	// 2. time-offset mining fault
	// return block1.Epoch != block2.Epoch
	// && block1.Parents == block2.Parents

	// 3. parent grinding fault
	// return block2.Epoch - block1.Epoch == 1
	// && !block2.Parents.include(block1)
}

func (self *ExpectedConsensus_I) IsWinningChallengeTicket(challengeTicket util.Bytes, sectorPower abi.StoragePower, networkPower abi.StoragePower, numSectorsSampled util.UVarint, numSectorsMiner util.UVarint) bool {
	// Conceptually we are mapping the pseudorandom, deterministic hash output of the challenge ticket onto [0,1]
	// by dividing by 2^HashLen and comparing that to the sector's target.
	// if the challenge ticket hash / max hash val < sectorPower / totalPower * ec.ExpectedLeaders * numSectorsMiner / numSectorsSampled
	// it is a winning challenge ticket.
	// note that the sectorPower may differ based on the challenged sector

	// lhs := challengeTicket * totalPower * numSectorsSampled
	// rhs := maxTicket * activeSectorPower * numSectorsMiner * self.ExpectedLeaders
	lhs := util.BigFromBytes(challengeTicket[:])
	lhs = lhs.Mul(lhs, util.BigFromUint64(uint64(networkPower)))
	lhs = lhs.Mul(lhs, util.BigFromUint64(uint64(numSectorsSampled)))

	// TODO: remove const here
	SHA256Len := 256
	// sectorPower * 2^len(H)
	rhs := new(big.Int).Lsh(util.BigFromUint64(uint64(sectorPower)), uint(SHA256Len))
	rhs = rhs.Mul(rhs, util.BigFromUint64(uint64(numSectorsMiner)))
	rhs = rhs.Mul(rhs, big.NewInt(int64(self.expectedLeadersPerEpoch())))

	// lhs < rhs?
	return lhs.Cmp(rhs) == -1
}

Tickets in EC #

Within SPC, a miner generates a new ticket in their block for every ticket they use running leader election, thereby ensuring the ticket chain is always as long as the block chain.

Tickets are used to achieve the following:

  • Ensure leader secrecy – meaning a block producer will not be known until they release their block to the network.
  • Prove leader election – meaning a block producer can be verified by any participant in the network.

In practice, EC defines two different fields within a block:

  • A Ticket field — this stores the new ticket generated during this block generation attempt. It is from this ticket that miners will sample randomness to run leader election in K rounds (see Tickets).
  • A set of winning ChallengeTickets — this stores a proof that a given miner has won a leader election using the appropriate ticket generated by the election PoSt process with randomness K rounds back. It proves that the leader was validly elected in this epoch.

import abi "github.com/filecoin-project/specs-actors/actors/abi"
import filcrypto "github.com/filecoin-project/specs/algorithms/crypto"
import addr "github.com/filecoin-project/go-address"

type Ticket struct {
    VRFResult  filcrypto.VRFResult

    Output     Bytes                @(cached)
    DrawRandomness(round abi.ChainEpoch) Bytes
    ValidateSyntax() bool
    Verify(
        input           Bytes
        pk              filcrypto.VRFPublicKey
        minerActorAddr  addr.Address
    ) bool
}
package block

import (
	addr "github.com/filecoin-project/go-address"
	abi "github.com/filecoin-project/specs-actors/actors/abi"
	acrypto "github.com/filecoin-project/specs-actors/actors/crypto"
	filcrypto "github.com/filecoin-project/specs/algorithms/crypto"
	util "github.com/filecoin-project/specs/util"
)

func (tix *Ticket_I) ValidateSyntax() bool {
	return tix.VRFResult_.ValidateSyntax()
}

//func (tix *Ticket_I) Verify(proof util.Bytes, digest util.Bytes, pk filcrypto.VRFPublicKey) bool {
//p := blake2b.Sum256(proof)
//return tix.VRFResult_.Verify(proof, pk) && bytes.Compare(digest, p[:]) == 0
//}

func (tix *Ticket_I) Verify(randomness util.Bytes, pk filcrypto.VRFPublicKey, minerActorAddr addr.Address) bool {
	input := acrypto.DeriveRandWithMinerAddr(acrypto.DomainSeparationTag_TicketProduction, randomness, minerActorAddr)
	return tix.VRFResult_.Verify(input, pk)
}

func (tix *Ticket_I) DrawRandomness(epoch abi.ChainEpoch) util.Bytes {
	return acrypto.DeriveRandWithEpoch(acrypto.DomainSeparationTag_TicketDrawing, tix.Output(), int(epoch))
}

But why the randomness lookback?

The randomness lookback helps turn independent ticket generation from a block one round back into a global ticket generation game instead. Rather than having a distinct chance of winning or losing for each potential fork in a given round, a miner will either win on all or lose on all forks descended from the block in which the ticket is sampled.

This is useful as it reduces opportunities for grinding, across forks or sybil identities.

However this introduces a tradeoff:

  • The randomness lookback means that a miner can know K rounds in advance that they will win, decreasing the cost of running a targeted attack (given they have local predictability).

How is K selected?

  • On the one end, there is no advantage to picking K larger than finality.
  • On the other, making K smaller reduces adversarial power to grind.

Secret Leader Election #

Expected Consensus is a consensus protocol that works by electing a miner from a weighted set in proportion to their power. In the case of Filecoin, participants and powers are drawn from the The Power Table, where power is equivalent to storage provided through time.

Leader Election in Expected Consensus must be Secret, Fair and Verifiable. This is achieved through the use of randomness used to run the election. In the case of Filecoin’s EC, the blockchain tracks an independent ticket chain. These tickets are used as randomness inputs for Leader Election. Every block generated references winning ChallengeTickets generated using a past ticket. The ticket chain is extended by the miner who generates a new block for each successful leader election.

Running a leader election #

Now, a miner must also check whether they are eligible to mine a block in this round.

Design goals here include:

  • Miners should be rewarded proportional to their power in the system
  • The system should be able to tune how many blocks are put out per epoch on expectation (hence “expected consensus”).

As discussed in Election PoSt, a miner will use the challenge ticket of an ElectionPoSt to uniformly draw a value from 0 to 1 when crafting a block.

The miner gets to draw one such challenge ticket per sector they have committed and must then compare the value derived from the challenge ticket against a target to determine whether they are eligible to mine. This is called finding a winning ticket.

The target is set as follows, for each sector sampled for a ticket from the miner’s ProvingSet and the number of sectors in the set:

target = activePowerInSector/networkPower * EC.ExpectedLeadersPerEpoch * numSectorsMiner / numSectorsSampled

The target ensures that the miner can express the power across all of their sectors through the tickets they have sampled. Specifically, on expectation, checking numSectorsSampled (with numSectorsSampled = ceil(len(provingSet) * EPoStSampleRate)) challenge tickets in every epoch, a miner will find minerPower/networkPower * EC.ExpectedLeadersPerEpoch winning tickets per epoch on expectation. Note that while the sectorPower may differ based on the challenged sector, i.e. in any given epoch a miner may have an advantage (if picking sectors with more than the average across all their sectors) or a disadvantage (conversely) in their election; but over multiple epochs, on expectation the election will be fair.

We elaborate on the above claim:

We want the miner's expected wins over time to be equal to w = minerPower/networkPower * EC.ExpectedLeadersPerEpoch

Take P to be the average miner power over the N sectors in their ProvingSet.
We have P = SUM_{i=0}^N P_i / N

The miner's likelihood of winning an election in any epoch is, for C tickets randomly drawn
W = C * target = C * P_i/networkPower * EC.ExpectedLeadersPerEpoch * N/C = N * P_i/networkPower * EC.ExpectedLeadersPerEpoch

with N * P_i ~= minerPower on expectation over enough epochs. That is to say: W = minerPower/networkPower * EC.ExpectedLeadersPerEpoch as wanted.

We show this below, removing division for ease of implementation:

const maxChallengeTicketSize = 2^len(H)

def TicketIsWinner(challengeTicket):
    // Check that `ChallengeTicket < Target`
    return challengeTicket * networkPower * numSectorsSampled < activePowerInSector * EC.ExpectedLeadersPerEpoch * maxChallengeTicketSize * numSectorsMiner

If the miner finds any winning ticket in this round, it can use it, along with a new randomness ticket to generate and publish a new block. Otherwise, it waits to hear of another block generated in this round.

We also use the Verifiable Random Function to draw randomness as part of crafting the Challenge Tickets in order to ensure leader election is secret (a miner cannot be known to win until they publish their ticket on the chain).

It is important to note that every block contains three artifacts: one, a ticket derived from last block’s ticket to extend the ticket-chain, two, a challenge ticket array PoSt process run in this epoch, and three a PoStProof to prove each ChallengeTicket was derived correctly.

Election Validation #

In order to determine that the mined block was generated by an eligible miner, one must check its ChallengeTickets’ validity and that they were generated appropriately by the PoSt generator. Thereafter, for each ticket the miner must check that it is a winning challenge ticket, per the above definition.

Chain Selection #

Just as there can be 0 miners win in a round, multiple miners can be elected in a given round. This in turn means multiple blocks can be created in a round, as seen above. In order to avoid wasting valid work done by miners, EC makes use of all valid blocks generated in a round.

Chain Weighting #

It is possible for forks to emerge naturally in Expected Consensus. EC relies on weighted chains in order to quickly converge on ‘one true chain’, with every block adding to the chain’s weight. This means the heaviest chain should reflect the most amount of work performed, or in Filecoin’s case, the most storage provided.

In short, the weight at each block is equal to its ParentWeight plus that block’s delta weight. Details of Filecoin’s chain weighting function are included here.

Delta weight is a term composed of a few elements:

  • wPowerFactor: which adds weight to the chain proportional to the total power backing the chain, i.e. accounted for in the chain’s power table.
  • wBlocksFactor: which adds weight to the chain proportional to the number of tickets mined in a given epoch. It rewards miner cooperation (which will yield more blocks per round on expectation).

The weight should be calculated using big integer arithmetic with order of operations defined above. We use brackets instead of parentheses below for legibility. We have:

w[r+1] = w[r] + (wPowerFactor[r+1] + wBlocksFactor[r+1]) * 2^8

For a given tipset ts in round r+1, we define:

  • wPowerFactor[r+1] = wFunction(totalPowerAtTipset(ts))
  • wBlocksFactor[r+1] = wPowerFactor[r+1] * wRatio * t / e
    • with t = |ticketsInTipset(ts)|
    • e = expected number of tickets per round in the protocol
    • and wRatio in ]0, 1[ Thus, for stability of weight across implementations, we take:
  • wBlocksFactor[r+1] = (wPowerFactor[r+1] * b * wRatio_num) / (e * wRatio_den)

We get:

w[r+1] = w[r] + wFunction(totalPowerAtTipset(ts)) * 2^8 + (wFunction(totalPowerAtTipset(ts)) * len(ts.tickets) * wRatio_num * 2^8) / (e * wRatio_den)

Using the 2^8 here to prevent precision loss ahead of the division in the wBlocksFactor.

The exact value for these parameters remain to be determined, but for testing purposes, you may use:

  • e = 5
  • wRatio = .5, or wRatio_num = 1, wRatio_den = 2
  • wFunction = log2b with
    • log2b(X) = floor(log2(x)) = (binary length of X) - 1 and log2b(0) = 0. Note that that special case should never be used (given it would mean an empty power table).
Note that if your implementation does not allow for rounding to the fourth decimal, miners should apply the tie-breaker below. Weight changes will be on the order of single digit numbers on expectation, so this should not have an outsized impact on chain consensus across implementations.

ParentWeight is the aggregate chain weight of a given block’s parent set. It is calculated as the ParentWeight of any of its parent blocks (all blocks in a given Tipset should have the same ParentWeight value) plus the delta weight of each parent. To make the computation a bit easier, a block’s ParentWeight is stored in the block itself (otherwise potentially long chain scans would be required to compute a given block’s weight).

Selecting between Tipsets with equal weight #

When selecting between Tipsets of equal weight, a miner chooses the one with the smallest final ticket.

In the case where two Tipsets of equal weight have the same min ticket, the miner will compare the next smallest ticket (and select the Tipset with the next smaller ticket). This continues until one Tipset is selected.

The above case may happen in situations under certain block propagation conditions. Assume three blocks B, C, and D have been mined (by miners 1, 2, and 3 respectively) off of block A, with minTicket(B) < minTicket(C) < minTicket(D).

Miner 1 outputs their block B and shuts down. Miners 2 and 3 both receive B but not each others’ blocks. We have miner 2 mining a Tipset made of B and C and miner 3 mining a Tipset made of B and D. If both succesfully mine blocks now, other miners in the network will receive new blocks built off of Tipsets with equal weight and the same smallest ticket (that of block B). They should select the block mined atop [B, C] since minTicket(C) < minTicket(D).

The probability that two Tipsets with different blocks would have all the same tickets can be considered negligible: this would amount to finding a collision between two 256-bit (or more) collision-resistant hashes.

Finality in EC #

EC enforces a version of soft finality whereby all miners at round N will reject all blocks that fork off prior to round N-F. For illustrative purposes, we can take F to be 500. While strictly speaking EC is a probabilistically final protocol, choosing such an F simplifies miner implementations and enforces a macroeconomically-enforced finality at no cost to liveness in the chain.

Consensus Faults #

Due to the existence of potential forks in EC, a miner can try to unduly influence protocol fairness. This means they may choose to disregard the protocol in order to gain an advantage over the power they should normally get from their storage on the network. A miner should be slashed if they are provably deviating from the honest protocol.

This is detectable when a given miner submits two blocks that satisfy any of the following “consensus faults”. In all cases, we must have:

  • both blocks were mined by the same miner
  • both blocks have valid signatures
  • first block’s epoch is smaller or equal than second block

Types of faults #

  1. Double-Fork Mining Fault: two blocks mined at the same epoch (even if they have the same tipset).

    • B4.Epoch == B5.Epoch
      GB1B1MinerAnyB2B2MinerAnyB2->B1B3B3MinerAnyB3->B1B4B4MinerEB4->B2B5B5MinerEB5->B3
      Double-Fork Mining Fault #
  2. Time-Offset Mining Fault: two blocks mined off of the same Tipset at different epochs.

    • B3.Parents == B4.Parents && B3.Epoch != B4.Epoch
      GB1B1MinerAnyB2B2MinerAnyB2->B1B3B3MinerEB3->B2B4B4MinerEB4->B2
      Time-Offset Mining Fault #
  3. Parent-Grinding Fault: one block’s parent is a Tipset that provably should have included a given block but does not. While it cannot be proven that a missing block was willfully omitted in general (i.e. network latency could simply mean the miner did not receive a particular block), it can when a miner has successfully mined a block two epochs in a row and omitted one. That is, this condition should be evoked when a miner omits their own prior block. Specifically, this can be proven with a “witness” block, that is by submitting blocks B2, B3, B4 where B2 is B4’s parent and B3’s sibling but B3 is not B4’s parent.

    • !B4.Parents.Include(B3) && B4.Parents.Include(B2) && B3.Parents == B2.Parents && B3.Epoch == B2.Epoch
      GB1B1MinerAnyB2B2MinerAnyB2->B1B3B3MinerEB3->B1B4B4MinerEB4NullB4->B4NullB5B5MinerAnyB5->B2B5->B3B4Null->B2
      Parent-Grinding fault #

Penalization for faults #

A single consensus fault results into:

  • miner termination and removal of power from the power table,
  • loss of all pledge collateral (which includes the initial pledge and blocks rewards yet to be vested)

Detection and Reporting #

A node that detects and report a consensus fault is called “slasher”, any user in Filecoin can be a slasher. They can report consensus faults by calling the ReportConsensusFault on the StorageMinerActor of the faulty miner. The slasher is rewarded with a portion of the offending miner’s Pledge Collateral for notifying the network of the consensu fault.

The reward give to the slasher is a function of some initial share (SLASHER_INITIAL_SHARE) and growth rate (SLASHER_SHARE_GROWTH_RATE) and it has a maximum maxReporterShare. Slasher’s share increases exponentially as epoch elapses since the block when the fault is committed (see RewardForConsensusSlashReport). Only the first slasher gets their share of the pledge collateral and the remaining pledge collateral is burned. The longer a slasher waits, the higher the likelihood that the slashed collateral will be claimed by another slasher.