Window PoSt challenge generation should not depend on sector order

[porcuquine]

Description

Window PoSt challenge generation currently depends on the ordering of provided sectors.

This is considered to be a 'protocol bug' in that this is the behavior which has been specified and audited. However, it allows for miners to influence challenges by shuffling their sectors. One possible (and probably cleanest) solution is to make challenge-generation independent of sector ordering — at the cost of a breaking change (so extant Window PoSts would not verify with the new code, requiring a network reset or proofs upgrade).

In the current code, the function generate_leaf_challenges appears to do the right thing, but this function is only called from Election PoSt so is not actually used.

rust-fil-proofs/storage-proofs/post/src/fallback/vanilla.rs

Lines 192 to 211 in 4a07a86

	pub fn generate_leaf_challenges<T: Domain>(
	pub_params: &PublicParams,
	randomness: T,
	sector_id: u64,
	challenge_count: usize,
	) -> Result<Vec<u64>> {
	let mut challenges = Vec::with_capacity(challenge_count);
	for leaf_challenge_index in 0..challenge_count {
	let challenge = generate_leaf_challenge(
	pub_params,
	randomness,
	sector_id,
	leaf_challenge_index as u64,
	)?;
	challenges.push(challenge)
	}
	Ok(challenges)
	}

Notice, however, that in generate_public_input for Fallback PoSt, challenge_index depends on i (the sector's index within the submitted partition). This must not be the case.

rust-fil-proofs/storage-proofs/post/src/fallback/compound.rs

Lines 68 to 76 in 4a07a86

	let challenge_index = ((partition_index * pub_params.sector_count + i)
	* pub_params.challenge_count
	+ n) as u64;
	let challenged_leaf_start = fallback::generate_leaf_challenge(
	&pub_params,
	pub_inputs.randomness,
	sector.id.into(),
	challenge_index,
	)?;

Instead, the challenge_index can just be n. Each sector's challenge indexes should range from 0 to challenge_count.

The same can be seen in the vanilla proof:

rust-fil-proofs/storage-proofs/post/src/fallback/vanilla.rs

Lines 324 to 333 in 4a07a86

	.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,
	)?;

Acceptance criteria

Window PoSt challenge generation does not depend on the ordering of provided sectors.

Risks + pitfalls

This will be a breaking change to proofs: a proof generated with the previous Window PoSt will not verify. Therefore, we will either:

• need a network reset; or
• need a proofs upgrade (with new RegisteredProof for modified Window PoSt).

This decision must be made at the project level, and we can support either path. If the proofs upgrade is selected, a new issue should be created; and both that new issue and the current should be addressed in the PR realizing this work.

Note that because Winning PoSt uses only a single partition, this change should not affect Winning PoSt challenge generation. Therefore, we don't technically need a new RegisteredProof. We should at least verify that this is true if we opt for a proofs upgrade.

In that case, we must either actually upgrade Winning PoSt also (which may be simplest) — or else explicitly verify that old Winning PoSt proofs still pass (and that challenge generation is unaffected).

Where to begin

• vanilla proof:

  rust-fil-proofs/storage-proofs/post/src/fallback/vanilla.rs

  Lines 324 to 333 in 4a07a86

  	.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,
  	)?;

• circuit input generation:

  rust-fil-proofs/storage-proofs/post/src/fallback/compound.rs

  Lines 68 to 76 in 4a07a86

  	let challenge_index = ((partition_index * pub_params.sector_count + i)
  	* pub_params.challenge_count
  	+ n) as u64;
  	let challenged_leaf_start = fallback::generate_leaf_challenge(
  	&pub_params,
  	pub_inputs.randomness,
  	sector.id.into(),
  	challenge_index,
  	)?;

[porcuquine]

cc: @nicola @cryptonemo @magik6k @whyrusleeping @daviddias @momack2.

[porcuquine]

@cryptonemo I think this is the one we considered as a good candidate for a proofs-upgrade test. Will obviously have to think about branching strategy so we don't introduce a breaking change elsewhere until ready to actually upgrade.

[cryptonemo]

This was addressed in 2 PRs in different ways that didn't land:

#1284
#1286

Re-open if this remains an issue.