Filecoin — What’s Window PoST?
There are two scenarios for the PoSt algorithm from Lotus: Winning PoSt and Window PoSt. In Winning PoSt, we are proving the Sector data that has already been submitted when the block generates. The submitted Sector data is being proved periodically to make sure the data is saved correctly. Refer to the previous blog
https://medium.com/@starli/filecoin-whats-winning-post-4e460fc84fc7
for more details on Winning PoSt logic.
This article will cover Window PoSt logic in details. To understand Window PoSt, we need to start from managing Sector in smart contracts. Below is information in the last submission of smart contract(specs-actors) used in this article:
commit 382017dd33e9e818a51503893433628fab643dd3
Author: Alex North <445306+anorth@users.noreply.github.com>
Date: Wed May 6 10:08:31 2020 +1000Set ConsensusMinerMinPower to 10TiB (#344)
1 Miner’s State
Miner’s property information, mortgage information and Sector state are saved in Miner’s State. We pick out the code snippet related to WindowPoSt:
type State struct {
...
ProvingPeriodStart abi.ChainEpoch
NewSectors *abi.BitField
Deadlines cid.Cid
...
}ProvingPeriodStart — the beginning time for each proving period.
NewSectors — information for new block
Deadlines — each challenge window is divided into multiple windows. Each window has a Deadline. This is where WindowPoSt got its name from.
1.1 Proving Period
Configuration spec for WindowPoSt is defined in specs-actors/actors/builtin/miner/policy.go.
const EpochDurationSeconds = 25
const SecondsInYear = 31556925
const SecondsInDay = 86400
const WPoStProvingPeriod = abi.ChainEpoch(SecondsInDay / EpochDurationSeconds)const WPoStChallengeWindow = abi.ChainEpoch(1800 / EpochDurationSeconds) // Half an hour (=48 per day)
const WPoStPeriodDeadlines = uint64(WPoStProvingPeriod / WPoStChallengeWindow)
const WPoStChallengeLookback = abi.ChainEpoch(20)
WPoStProvingPeriod — proving period. Required proving once every day.
WPoStChallengeWindow — A ChallengeWindow is half an hour. Each proving period is divided into 47 ChallegeWindow.
WPoStPeriodDeadlines — The end of a ChallengeWindow.
WPoStChallengeLookback — Time for obtaining random amount of data from the chain and looking back on previous blocks in each ChallegeWindow.
To conclude, the period for WindowPoSt is one day, and each WindowPoSt is divided into 48 Windows. Sector information varies in different time period of a Window. Each Window requires proof from WindowPoSt, and the amount of Sector in a Window decided how many proof is needed. The detailed logic will come later.
1.2 Deadline
Deadline is difined in specs-actors/actors/builtin/miner/deadlines.go:
type DeadlineInfo struct {
CurrentEpoch abi.ChainEpoch // Epoch at which this info was calculated.
PeriodStart abi.ChainEpoch // First epoch of the proving period (<= CurrentEpoch).
Index uint64 // Current deadline index, in [0..WPoStProvingPeriodDeadlines), or WPoStProvingPeriodDeadlines if period elapsed.
Open abi.ChainEpoch // First epoch from which a proof may be submitted, inclusive (>= CurrentEpoch).
Close abi.ChainEpoch // First epoch from which a proof may no longer be submitted, exclusive (>= Open).
Challenge abi.ChainEpoch // Epoch at which to sample the chain for challenge (< Open).
FaultCutoff abi.ChainEpoch // First epoch at which a fault declaration is rejected (< Open).
}CurrentEpoch — current block time.
PeriodStart — beginning block time for each proof.
Index — index for Deadline, aka window. Range from 0 to 47.
Open — The earliest time allowed for submitting proof in this window.
Close — The latest time allowed or submitting proof in this window.
Challenge — The range for random number in this window.
FaultCutoff — Error block can only be determined before this cut off block time.
Function ComputeProvingPeriodDeadline calculates Deadline given proving start time and current block time:
func ComputeProvingPeriodDeadline(periodStart, currEpoch abi.ChainEpoch) *DeadlineInfo {
periodProgress := currEpoch - periodStart
...
deadlineIdx := uint64(periodProgress / WPoStChallengeWindow)
if periodProgress < 0 { // Period not yet started.
deadlineIdx = 0
}
deadlineOpen := periodStart + (abi.ChainEpoch(deadlineIdx) * WPoStChallengeWindow)
return &DeadlineInfo{
CurrentEpoch: currEpoch,
PeriodStart: periodStart,
Index: deadlineIdx,
Open: deadlineOpen,
Close: deadlineOpen + WPoStChallengeWindow,
Challenge: deadlineOpen - WPoStChallengeLookback,
FaultCutoff: deadlineOpen - FaultDeclarationCutoff,
}
}We can get deadlienIdx from current block time and start time. With this index, it will be easier to get other variables.
2 State Change Logic
There are two parts in the WindowPoSt state logic: adjustment on the start time of each windowPoSt proof, and update on the Sector information that requires proving.
2.1 Adjustment on the Proving Start Time
The start time for proof is initialized when miner’s smart contract is created.
offset, err := assignProvingPeriodOffset(rt.Message().Receiver(), currEpoch, rt.Syscalls().HashBlake2b)
periodStart := nextProvingPeriodStart(currEpoch, offset)assignProvingPeriodOffset, randomly generates offset in [0, WPoStProvingPeriod] through function HashBlake2b.
Function nextProvingPeriodStart as shown below:
func nextProvingPeriodStart(currEpoch abi.ChainEpoch, offset abi.ChainEpoch) abi.ChainEpoch {
currModulus := currEpoch % WPoStProvingPeriod
var periodProgress abi.ChainEpoch // How far ahead is currEpoch from previous offset boundary.
if currModulus >= offset {
periodProgress = currModulus - offset
} else {
periodProgress = WPoStProvingPeriod - (offset - currModulus)
}
periodStart := currEpoch - periodProgress + WPoStProvingPeriod
Assert(periodStart > currEpoch)
return periodStart
}To put it in a simple way, the function finds next proving start time with the given offset.
After we know the proving start time, minor’s smart contract checks proving state at the end of each proving period, as well as updates the proving start time.
func handleProvingPeriod(rt Runtime) {
...
if deadline.PeriodStarted() {
st.ProvingPeriodStart = st.ProvingPeriodStart + WPoStProvingPeriod
}
...
err = st.ClearPoStSubmissions()
...
}2.2 Update Sector Information
In a Miner’s smart contract, NewSectors update through three interfaces:
proveCommitSector: add new sector information to NewSectors while submitting the PoREP commi.
terminateSector: remove Sector information from NewSectors.
handleProvingPeriod: periodically “assign” NewSectors information to Deadlines. In another word, this function maintains a list of all Sectors that require proving in a miner’s smart contract. It assigns the Sectors to different Windows at beginning of each windowPoSt.
3 Sector Assignment
Using function AssignNewSectors, we assign the Sectors that need proving to different Windows (Deadline):
func AssignNewSectors(deadlines *Deadlines, partitionSize uint64, newSectors []uint64, seed abi.Randomness) error {Note that partitionSize is the amount of Sectors in one Partition:
func (p RegisteredProof) WindowPoStPartitionSectors() (uint64, error) {
...
case RegisteredProof_StackedDRG32GiBSeal:
return 2349, nil
case RegisteredProof_StackedDRG2KiBSeal:
return 2, nil
case RegisteredProof_StackedDRG8MiBSeal:
return 2, nil
case RegisteredProof_StackedDRG512MiBSeal:
return 2, nil
default:
return 0, errors.Errorf("unsupported proof type: %v", p)
...
}Partition size would be 2349 for a 32-gigabyte Sector.
There are 2 steps in AssignNewSectors:
1/ Fill each Window until the the number of Sector reaches partitionSize.
2/ if there is remainder Sectors after step 1/, assign them accordingly to each Window based on partitionSize.
To summarize sector assignment, take partitionSize as one unit and distribute them into each Window. That means there could be multiple partitionSize units of Sectors in one Window. Pay special attention to the input variable seed. Although the function attempts to randomize sector assignment, but this has not been achieved.
4 WindowPoSt Proof Dispatch
The logic for proof dispatch of WindowPoSt in Lotus project. Below is information in the last submission of Lotus source code used in this article:
commit 10fe6084f1374891a6666fad61b9c3aa448b4554
Merge: 1d887b55 1831613f
Author: Łukasz Magiera <magik6k@users.noreply.github.com>
Date: Wed May 6 01:45:33 2020 +0200Merge pull request #1670 from filecoin-project/feat/update-markets-0.2.0
Update go-fil-markets
The complete WindowPoSt dispatch logic flow diagram follows:
WindowPoStScheduler: listens to states on the chain。It attempts to doPoSt at a new block height. doPoSt breaks down to two portions: the WindowPoSt proof generated at wunPoSt runtime(outputs from rust-fil-proofs), and submitPoSt that pushes proof to the chain. All Proofs in one proving period will be recorded in the chain. handleProvingPeriod: browse all proving state in all Windows at the end of each period.
As a summary of what we have covered so far in this lesson:
1/ One proving period takes one day. One period is divided into 48 Windows. Each window takes 30 minutes.
2/ Each Window has its Deadline (cut off for correctly submitting proof).
3/ Existing Sectors will be assigned based on the partitionSize(2349 Sectors) to fill in each Window. If there is remaining Sector after the assignment, continue filling up the Windows with units of partitionSize.
If the Sector size is 32 gigabytes, that is 2349 Sectors, or 73T. If each window contains one partition of Sectors, the total storage space would be: 73T*48 = 2.25P. That is to say, for a 4.5P storage space, each window will contain 2 partitions of Sectors. The more storage data there is, the more Sectors there will be, and the more occupied Windows. Hence it leads to more time complexity for such calculation.
5 Generate WindowPoSt Proofs
With a basic understanding of proceeding logics, eventually we get to take a look at how proofs are generated in WindowPoSt. These logics are implemented in rust-fil-proofs, or written in rust. We encounter lots of interfaces from go to rust-fil-proofs:
Here we skip the intermediate interfaces and go straight to the interface functions in rust-fil-proofs.
pub fn generate_window_post<Tree: 'static + MerkleTreeTrait>(
post_config: &PoStConfig,
randomness: &ChallengeSeed,
replicas: &BTreeMap<SectorId, PrivateReplicaInfo<Tree>>,
prover_id: ProverId,
) -> Result<SnarkProof> {Here post_config means PoStConfig(configuration). randomness is random information, used to generate leaf data of a challenge on a Sector. replicas is the corresponding replica data to all Sectors generated in WindowPoSt proving.
5.1 PoStConfig
PoStConfig is defined in rust-filecoin-proofs-api/src/registry.rs:
pub fn as_v1_config(self) -> PoStConfig {
match self {
...
StackedDrgWindow2KiBV1
| StackedDrgWindow8MiBV1
| StackedDrgWindow512MiBV1
| StackedDrgWindow32GiBV1 => PoStConfig {
typ: self.typ(),
sector_size: self.sector_size(),
sector_count: self.sector_count(),
challenge_count: constants::WINDOW_POST_CHALLENGE_COUNT,
priority: true,
}, // _ => panic!("Can only be called on V1 configs"),
}
}Note that sector_count and challenge_count are defined in rust-fil-proofs/filecoin-proofs/src/constants.rs:
pub const WINDOW_POST_CHALLENGE_COUNT: usize = 10;pub static ref WINDOW_POST_SECTOR_COUNT: RwLock<HashMap<u64, usize>> = RwLock::new(
[
(SECTOR_SIZE_2_KIB, 2),
(SECTOR_SIZE_4_KIB, 2),
(SECTOR_SIZE_16_KIB, 2),
(SECTOR_SIZE_32_KIB, 2),
(SECTOR_SIZE_8_MIB, 2),
(SECTOR_SIZE_16_MIB, 2),
(SECTOR_SIZE_512_MIB, 2),
(SECTOR_SIZE_1_GIB, 2),
(SECTOR_SIZE_32_GIB, 2349), // this gives 133,977,564 constraints, fitting just in a single partition
(SECTOR_SIZE_64_GIB, 2300), // this gives 131,182,800 constraints, fitting just in a single partition
]
.iter()
.copied()
.collect()
);
i.e. when number of challenge is 10, a Partition consists of 2349 Sectors given each Sector size is 32 gigabytes.
5.2 Generate Challenge
Each Sector contains 10 challenge leaves. Here is how it is calculated (function prove_all_partitions in storage-proofs/post/src/fallback/vanilla.rs):
let inclusion_proofs = (0..pub_params.challenge_count)
.into_par_iter()
.map(|n| {
let challenge_index = ((j * num_sectors_per_chunk + i)
* pub_params.challenge_count
+ n) as u64;
let challenged_leaf_start = generate_leaf_challenge(
pub_params,
pub_inputs.randomness,
sector_id.into(),
challenge_index,
)?;tree.gen_cached_proof(challenged_leaf_start as usize, levels)
})
.collect::<Result<Vec<_>>>()?;
challenge_index is the index for the challenge in all the Sectors need proving. generate_leaf_challenge generates leaf index based on random information, sector index and challenge index.
let mut hasher = Sha256::new();
hasher.input(AsRef::<[u8]>::as_ref(&randomness));
hasher.input(§or_id.to_le_bytes()[..]);
hasher.input(&leaf_challenge_index.to_le_bytes()[..]);
let hash = hasher.result();let leaf_challenge = LittleEndian::read_u64(&hash.as_ref()[..8]);let challenged_range_index = leaf_challenge % (pub_params.sector_size / NODE_SIZE as u64);
Then we use hash function on the randomized data, sector id and challenge leaf index. Take mod on the result and total number of leaves. For 32 gigabypes of Sector, we get 16 gigabytes of leaves.
5.3 Zero-Knowledge Proof Circuit
The circuit logic mentioned here is identical to the WinningPoSt circuit, besides different variables.
Pay special attention to the count of partition size in WindowPoSt is not one. Here is how it is calculated:
let partitions = get_partitions_for_window_post(replicas.len(), &post_config);fn get_partitions_for_window_post(
total_sector_count: usize,
post_config: &PoStConfig,
) -> Option<usize> {
let partitions = (total_sector_count as f32 / post_config.sector_count as f32).ceil() as usize;if partitions > 1 {
Some(partitions)
} else {
None
}
}
In short, partition count is count of replica divided by count of Sector in each Partition (2349).
To summarize on circuit, number of proofs(partition) is relational to count of Sectors that need proving and is equal to count of replica divided by 2349. 10 leaf nodes will be drawn from each Sector within proofs of each partition.
Summary
WindowPoSt periodically proves the existence on the submitted Sector data. Each proving period takes one day. One period consists of 48 Windows. Each Window takes 30 minutes. All Windows require WindowPoSt proving calculation. Count of proofs is equal to count of Sector in the Window divided by count of Sector in a Partition. To prove a Partition, we draw 10 leaf nodes from each Sector in the Partition.
