### Proof-of-Spacetime (PoSt)- State
`reliable`

- Theory Audit
`wip`

- Edit this section
`section-algorithms.pos.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.

is used to prove that the miner has a replica of the data at the specific time when they were asked. A*WinningPoSt**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.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*WindowPoSt**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`

- 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`

- 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 (up to five, currently) are elected to mine new blocks, by Filecoin’s
Expected Consensus algorithm. Recall that the Filecoin blockchain operates on the basis of *tipsets*, which are groups of up to five blocks. This means that multiple blocks (up to five) 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`

- 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`

- 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:

Name | Distance from `Open` | Description |
---|---|---|

`Open` | `0` | Epoch from which a PoSt Proof for this deadline can be submitted. |

`Close` | `WPoStChallengeWindow` | Epoch after which a PoSt Proof for this deadline will be rejected. |

`FaultCutoff` | `-FaultDeclarationCutoff` | Epoch after which a `miner.DeclareFault` and `miner.DeclareFaultRecovered` for sectors in the upcoming deadline are rejected. |

`Challenge` | `-WPoStChallengeLookback` | Epoch at which the randomness for the challenges is available. |