Grinding Fix FIP by Nemo

Authors

nemo

Creator

Undefined

Created

Mar 8, 2023 4:34 PM

Stage

Graduated from Notebook

fip	title	author	discussion-to	status	type	category	created
00??	WindowPoSt Grindability Fix	@cryptonemo @Nicola @porcuquin @Kubuxu @DrPeterVanNostrand @vmx	https://github.com/filecoin-project/FIPs/discussions/???	draft	technical	core	2023-03-08

Simple Summary

This proposal fixes a potential security issue ~~raised some time ago~~ 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

Given that there is a relationship between challenge generation and the sector order, it is feasible for malicious Storage Providers to gain influence over the challenges during WindowPoSt by re-ordering the provided sectors in a way providing 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 + challnge_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 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 new challenge generation.

Design Rationale

~~It is not clear that this issue has ever been exploited on mainnet, but potentially may be active.~~

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

If this has been explored on mainnet, it likely would not become clear until after deployment. If it had been utilized and segments are missing of sectors currently being PoSt'ed over, we would expect to see a higher number of failing WindowPoSts on chain.

Incentive Considerations

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