WindowPoSt Grindability Fix

[cryptonemo]

Simple Summary

This proposal fixes a potential security issue related to sector ordering during WindowPoSt, with no impact on performance.

Abstract

It's been recognised that Window PoSt challenge generation depends on the order of the provided sectors. This is inherent to the specified challenge generation algorithm, which had been audited but can be viewed as a bug in the protocol. If exploited by a Storage Provider, it would reduce the security guarantees of WindowPoSt.

This proposal eliminates this concern by making the generation of WindowPoSt challenges independent of the order of the provided sectors.

Motivation

In short, challenge generation is the process by which node (i.e. sector data) challenges are selected for each sector. Ideally, the challenges are random and equally distributed (both across sector data and across all sealed sectors), so that each sector is challenged uniquely to ensure that all sector data has integrity over time.

Given that there is a relationship between challenge generation and the sector order provided in WindowPoSt, it is feasible for malicious Storage Providers to gain influence over the challenges during WindowPoSt by re-ordering the provided sectors in a way that provides benefits beyond what is allowed in the protocol.

While we believe the issue cannot be successfully exploited for gain due to limits in other parts of the Filecoin system, the security of each component is important to maintain a secure network.

Specification

This proposal aims to change WindowPoSt challenge generation so that challenges for each sector no longer depend on other sectors in the same partition.

This prevents all avenues of grinding WindowPoSt challenges as long as the sector stays within one deadline.

New WindowPoSt proof type

Changes to Challenge Generation

Differences between the currently deployed WindowPoSt challenge generation and the proposed updated challenge generation are as follows:

Current challenge_index algorithm:

 let sector_index = chunk_index * num_sectors_per_chunk + sector_index_in_chunk;

 // Problem: Uses 'sector_index' in calculation
 let selected_challenge_index = sector_index * challenge_count_per_sector + challenge_index;

Updated challenge_index algorithm:

 let sector_index = chunk_index * num_sectors_per_chunk + sector_index_in_chunk;

 // Solution: Does not use 'sector_index' in calculation
 let selected_challenge_index = challenge_index;

Actor changes

The new WindowPoSt proof will be accepted beginning with network version 19.
The old WindowPoSt proof will continue to be accepted until network version 20 to give Storage Providers ample time to update their storage maintenance systems.

Proof changes

The ability to prove and verify WindowPoSt with the new challenge generation algorithm will be exposed. Since this is a breaking change, a new ApiVersion flag is introduced to specify which challenge generation algorithm is used. A new WindowPost proof type will be defined at the proofs API layer, which will use the new challenge generation.

Design Rationale

This is a subtractive change, removing information about where the sector is placed within the proof from challenge generation and thus removing a degree of freedom. This additional degree of freedom is what allows for possible grinding on challenges for a given sector.

As it is a subtractive change, it is necessary to explore why sector_index_in_chunk was introduced. The initial design goal of sector_index_in_chunk most likely was to guarantee the uniqueness of challenges across all sectors within a given WindowPoSt partition. Other inputs into the challenge generation are chain randomness and SectorID. The SectorID is guaranteed unique within the scope of one storage provider and consequently within the scope of WindowPoSt. Thus we can rely on SectorID to guarantee the uniqueness of challenges.

Backwards Compatibility

This change would introduce a way to specify which challenge generation method is to be used and accepted on chain. For some time, the old algorithm would be used and at some point it will no longer be accepted.

Test Cases

Test cases of proofs are included in the Proofs code.
Test cases for Actors are TBD.

Security Considerations

Incentive Considerations

This proposal does not affect the current incentive system of the Filecoin network.

Product Considerations

This proposal has no product implications.

Implementations

TODO

Copyright Waiver

Copyright and related rights waived via CC0.

[magik6k]

From lotus perspective this will simplify / improve many aspects of PoSt:

• When there are failed sectors, they will be possible to just skip - today if we fail to read challenges for one sector, we need to re-read new challenges for all sectors in the partition
• On lotus/actors side it will be possible to remove the "substitute sector" logic (which doesn't work either way due to a subtle, afaict consensus-impacting proofs bug which ignores those substitutes)
  • Even if the substitute logic did work, it would still require re-reading challenges from the substitute sector, which introduces lots of complexity to the lotus proving code.