Filecoin — What’s winning PoST?

3 min readMay 24, 2020

The part of Lotus PoSt has changed from electionPoSt to two new PoSt, one is winningPoSt and the other is windowPoSt. Let ’s talk about winningPoSt first. winningPoSt, as the name suggests, is PoSt when it is winning. The so-called winning is to obtain the block right.

To put it simply, winningPoSt is a sector randomly checked, and the 66 randomly selected merkle paths in this sector can be correct. Then talk about code logic. Speaking from the code of Lotus go. It all starts from the block-the mineOne function of the Miner structure of lotus / miner / miner.go.

func (m *Miner) mineOne(ctx context.Context, addr address.Address, base *MiningBase) (*types.BlockMsg, error) {mbi, err := m.api.MinerGetBaseInfo(ctx, addr, round, base.TipSet.Key())rand, err := m.api.ChainGetRandomness(ctx, base.TipSet.Key(), crypto.DomainSeparationTag_WinningPoStChallengeSeed, base.TipSet.Height()+base.NullRounds, nil)
     prand := abi.PoStRandomness(rand)
     postProof, err := m.epp.ComputeProof(ctx, mbi.Sectors, prand)

Among them, the MinerGetBaseInfo function is to obtain some basic information, including the sector information that needs to be extracted. The ComputeProof function is to calculate the winningPoSt proof.

Because the specific implementation of these logics is implemented in rust-fil-proofs, which is the rust language. From go to rust-fil-proofs, many interfaces are crossed:

The interface in the middle will not be introduced, just look at the two API functions provided by rust-fil-proofs.

Challenge Leaf Numbers

The number of sectors and the total number of leaves for challenge are defined in rust-fil-proofs / filecoin-proofs / src / constants.rs:

pub const WINNING_POST_CHALLENGE_COUNT: usize = 66;
pub const WINNING_POST_SECTOR_COUNT: usize = 1;

That is to say, to extract a sector from the effective sector, and select challenged 66 leaf nodes on this sector.

Challenged Sector Selection Logic

The generate_winning_post_sector_challenge function implements the challenge logic of the Sector. How does the core logic spot check the Sector? The specific logic is in the function of fallback :: generate_sector_challenges:

let mut hasher = Sha256::new();
hasher.input(AsRef::<[u8]>::as_ref(&prover_id));
hasher.input(AsRef::<[u8]>::as_ref(&randomness));
hasher.input(&n.to_le_bytes()[..]);let hash = hasher.result();let sector_challenge = LittleEndian::read_u64(&hash.as_ref()[..8]);
let sector_index = sector_challenge % sector_set_len;

To put it simply, it is to calculate the hash of sha256 by using the random_information of random_provider_id and the random number of the sector. The calculation result and the current limited number of sectors are modulo. That is, sector_index is the sector ID of the final challenge.

Challenged Leaf Selection Logic

generate_winning_post checks the leaf nodes on the merkle tree (replica_r_last) formed by the selected sectors. The calculation logic of the challenged leaf nodes is in the function of fallback :: generate_leaf_challenge:

let mut hasher = Sha256::new();
hasher.input(AsRef::<[u8]>::as_ref(&randomness));
hasher.input(&sector_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);

Hash the random information, sector id and challenge leaf number. The result of the calculation and the total number of leaves are modulo. The 32G Sector has 1G leaves.

zk-SNARK circuit

The calculation part of zero-knowledge proof can be viewed in the rust-fil-proofs / post / fallback directory.

Talk about the Sector structure in rust-fil-proofs / post / fallback / circuit.rs. This structure represents a challenge. It can be seen from the synthesize function:

// 1. Verify comm_r
        let comm_r_last_num = num::AllocatedNum::alloc(cs.namespace(|| "comm_r_last"), || {
            comm_r_last
                .map(Into::into)
                .ok_or_else(|| SynthesisError::AssignmentMissing)
        })?;let comm_c_num = num::AllocatedNum::alloc(cs.namespace(|| "comm_c"), || {
            comm_c
                .map(Into::into)
                .ok_or_else(|| SynthesisError::AssignmentMissing)
        })?;let comm_r_num = num::AllocatedNum::alloc(cs.namespace(|| "comm_r"), || {
            comm_r
                .map(Into::into)
                .ok_or_else(|| SynthesisError::AssignmentMissing)
        })?;comm_r_num.inputize(cs.namespace(|| "comm_r_input"))?;

comm_r as public input, other comm_r_last and comm_c as private input.

// 1. Verify H(Comm_C || comm_r_last) == comm_r
        {
            let hash_num = <Tree::Hasher as Hasher>::Function::hash2_circuit(
                cs.namespace(|| "H_comm_c_comm_r_last"),
                &comm_c_num,
                &comm_r_last_num,
            )?;// Check actual equality
            constraint::equal(
                cs,
                || "enforce_comm_c_comm_r_last_hash_comm_r",
                &comm_r_num,
                &hash_num,
            );
        }

Verify that comm_r is calculated by comm_c and comm_r_last.

// 2. Verify Inclusion Paths
for (i, (leaf, path)) in leafs.iter().zip(paths.iter()).enumerate() {
    PoRCircuit::<Tree>::synthesize(
        cs.namespace(|| format!("challenge_inclusion_{}", i)),
        Root::Val(*leaf),
        path.clone(),
        Root::from_allocated::<CS>(comm_r_last_num.clone()),
        true,
    )?;
}

Verify that the leaf node can correctly calculate the root of the Merkle tree.

Summary:

Lotus PoSt includes two parts: winningPoSt and windowPoSt. winningPoSt is the PoSt certificate that needs to be provided when obtaining the block right. From all valid sectors, extract a sector and challenge the 66 leaves on the sector.