Proof-of-Spacetime (PoSt)

• State reliable
• Theory Audit wip
• Edit this section
• section-algorithms.pos.post

From this point onwards, miners have to prove that they continuously store the data they pledged to store. Proof-of-Spacetime (PoSt) is a procedure during which miners are given cryptographic challenges that can only be correctly answered if the miner is actually storing a copy of the sealed data.

There are two types of challenges (and their corresponding mechanisms) that are realised as part of the PoSt process, namely, WinningPoSt and WindowPoSt, each of which serve a different purpose.

• WinningPoSt is used to prove that the miner has a replica of the data at the specific time when they were asked. A WinningPoSt challenge is issued to a miner only if the miner has been selected by (i.e., wins in) the Secret Leader Election algorithm (of Expected Consensus) to mine the next block. The answer to the WinningPoSt challenge has to be submitted within a short deadline, making it impossible for the miner to seal and find the answer to the challenge on demand. This guarantees that at the time of the challenge the miner maintains a copy of the data.
• WindowPoSt is used as a proof that a copy of the data has been continuously maintained over time. This involves submitting proofs regularly (see details below) and makes it irrational for a miner to not keep a sealed copy of the data (i.e., it is more expensive to seal a copy of the data every time they are asked to submit a WindowPoSt challenge).

In summary, WinningPoSt guarantees that the miner maintains a copy of the data at some specific point in time (i.e., when chosen by the Expected Consensus algorithm to mine the next block), while WindowPoSt guarantees that the miner continuously maintains a copy of the data over time.

Constants & Terminology

• State reliable
• Theory Audit wip
• Edit this section
• section-algorithms.pos.post.constants--terminology

Before continuing into more details of the WinnningPoSt and WindowPoSt algorithms, it is worth clarifying the following terms.

• partition: a group of 2349 sectors proven simultaneously.
• proving period: average period for proving all sectors maintained by a miner (currently set to 24 hours).
• deadline: one of multiple points during a proving period when the proofs for some partitions are due.
• challenge window: the period immediately before a deadline during which a challenge can be generated by the chain and the requisite proofs computed.
• miner size: the amount of proven storage maintained by a single miner actor.

WinningPoSt

• State reliable
• Theory Audit wip
• Edit this section
• section-algorithms.pos.post.winningpost

At the beginning of each epoch, a small number of storage miners are elected to mine new blocks, by Filecoin’s Expected Consensus algorithm. Recall that the Filecoin blockchain operates on the basis of tipsets, therefore multiple blocks can be mined at the same height.

Each of the miners that are elected to mine a block have to submit a proof that they keep a sealed copy of the data which they have included in their proposed block, before the end of the current epoch. Successful submission of this proof is the WinningPoSt, which in turn grants the miner the Filecoin Block Reward, as well as the opportunity to charge other nodes fees in order to include their messages in the block. If a miner misses the epoch-end deadline, then the miner misses the opportunity to mine a block and get a Block Reward. No penalty is incurred in this case.

Recall, that the probability of a storage miner being elected to mine a block is governed by Filecoin’s Expected Consensus algorithm and guarantees that miners will be chosen (on expectation) proportionally to their Quality Adjusted Power in the network, as reported in the power table WinningPoStSectorLookback epochs before the election.

WindowPoSt

• State reliable
• Theory Audit wip
• Edit this section
• section-algorithms.pos.post.windowpost

WindowPoSt is the mechanism by which the commitments made by storage miners are audited. In WindowPoSt every 24-hour period is called a “proving period” and is broken down into a series of 30min, non-overlapping deadlines, making a total of 48 deadlines within any given 24-hour proving period. Every miner must demonstrate availability of all claimed sectors on a 24hr basis. Constraints on individual proof computations limit a single proof to 2349 sectors (a partition), with 10 challenges each.

In particular, the sectors that a miner has pledged to store are: i) assigned to deadlines, and ii) grouped in partitions. It is important to highlight that although sectors are assigned to deadlines, sectors are proven in partitions - not individually. In other words, upon every deadline, a miner has to prove a whole partition.

For each partition, the miner will have to produce a SNARK-compressed proof and publish it to the blockchain as a message in a block. This proves that the miner has indeed stored the pledged sector. In this way, every sector of pledged storage is audited (as part of the partition it belongs to) at least once in any 24-hour period, and a permanent, verifiable, and public record attesting to each storage miner’s continued commitment is kept.

It naturally follows that the more the sectors a miner has pledged to store, the more the partitions of sectors that the miner will need to prove per deadline. This requires ready access to sealed copies of each of the challenged sectors and makes it irrational for the miner to seal data every time they need to provide a WindowPoSt proof.

The Filecoin network expects constant availability of stored files. Failing to submit WindowPoSt for a sector will result in a fault, and the storage miner supplying the sector will be slashed – that is, a portion of their pledge collateral will be forfeited, and their storage power will be reduced (see Storage Power Consensus.

Design

• State reliable
• Theory Audit wip
• Edit this section
• section-algorithms.pos.post.design

Each miner actor is allocated a 24-hr proving period at random upon creation. This proving period is divided into 48 non-overlapping half-hour deadlines. Each sector is assigned to one of these deadlines when proven to the chain, i.e., when ProveCommit completes and never changes deadline. The sets of sectors due at each deadline is recorded in a collection of 48 bitfields.

Generally, sectors are first allocated to fill any deadline up to the next whole-partition multiple of (2349) sectors; next a new partition is started on the deadline with the fewest partitions. If all deadlines have the same number of sectors, a new partition is opened at deadline 0.

The per-deadline sector sets are set at the beginning of each proving period as proving set bitfields and never change. The sector IDs are then (logically) divided sequentially into partitions, and the partitions across all deadlines for the miner logically numbered sequentially. Thus, a sector may move between partitions at the same deadline as other sectors fault or expire, but never changes deadline.

If a miner adds 48 partitions worth of sectors (~3.8 PiB), they will have one partition due for each deadline. When a miner has more than 48 partitions, some deadlines will have multiple partitions due at the same deadline. The proofs (i.e., one SNARK proof per partition) for these simultaneous partitions are expected to be computed and submitted together in a single message, at least up to 10-20 partitions per message, but can be split arbitrarily between messages (which, however, will cost more gas).

A WindowPoSt proof submission must indicate which deadline it targets and which partition indices the proofs represent for that particular deadline. The actor code receiving a submission maps the partition numbers through the deadline’s proving set bitfields to obtain the sector numbers. Faulty sectors are masked from the proving set by substituting a non-faulty sector number. The actor records successful proof verification for each of the partitions in a bitfield of partition indices (or records nothing if verification fails).

There are currently three types of Faults, the Declared Fault, the Detected Fault and the Skipped Fault. They are discussed in more detail as part of the Storage Mining subystem.

Summarising:

• A miner maintains its sectors active by generating Proofs-of-Spacetime (PoSt) and submit miner.SubmitWindowedPoSt for their sectors in a timely manner.
• A WindowPoSt proves that sectors are persistently stored through time.
• Each miner proves all of its sectors once per proving period; each sector must be proven by a particular time called deadline.
• A proving period is a period of WPoStProvingPeriod epochs in which a Miner actor is scheduled to prove its storage.
• A proving period is evenly divided in WPoStPeriodDeadlines deadlines.
• Each miner has a different start of proving period ProvingPeriodStart that is assigned at Power.CreateMiner.
• A deadline is a period of WPoStChallengeWindow epochs that divides a proving period.
• Sectors are assigned to a deadline at ProveCommit, either a call to miner.ProveCommitSector or miner.ProveCommitAggregate, and will remain assigned to it throughout their lifetime.
• In order to prove that they continuously store a sector, a miner must submit a miner.SubmitWindowedPoSt for each deadline.
• Sectors are assigned to partitions. A partition is a set of sectors that is not larger than the Seal Proof allowed number of sectors sp.WindowPoStPartitionSectors.
• Sectors are assigned to a partition at ProveCommit, through a call to miner.ProveCommitSector or miner.ProveCommitAggregate, and they can be re-arranged via CompactPartitions.
• Partitions are a by-product of our current proof mechanism. There is a limit in the number of sectors (sp.WindowPoStPartitionSectors) that can be proven in a single SNARK proof. If more than this amount is required to be proven, more than one SNARK proof is required, given that each SNARK proof represents a partition.

There are four relevant epochs associated to a deadline, shown in the table below: