use std::collections::BTreeSet;
use std::marker::PhantomData;
use anyhow::ensure;
use blstrs::Scalar as Fr;
use byteorder::{ByteOrder, LittleEndian};
use filecoin_hashers::{Domain, HashFunction, Hasher};
use generic_array::typenum::Unsigned;
use log::{error, trace};
use rayon::prelude::{
IndexedParallelIterator, IntoParallelIterator, IntoParallelRefIterator, ParallelIterator,
};
use serde::{de::DeserializeOwned, Deserialize, Serialize};
use sha2::{Digest, Sha256};
use storage_proofs_core::{
api_version::ApiVersion,
error::{Error, Result},
merkle::{MerkleProof, MerkleProofTrait, MerkleTreeTrait, MerkleTreeWrapper},
parameter_cache::ParameterSetMetadata,
proof::ProofScheme,
sector::SectorId,
util::{default_rows_to_discard, NODE_SIZE},
};
use super::utils::get_challenge_index;
#[derive(Debug, Clone)]
pub struct SetupParams {
pub sector_size: u64,
pub challenge_count: usize,
pub sector_count: usize,
pub api_version: ApiVersion,
}
#[derive(Debug, Clone)]
pub struct PublicParams {
pub sector_size: u64,
pub challenge_count: usize,
pub sector_count: usize,
pub api_version: ApiVersion,
}
#[derive(Debug, Default)]
pub struct ChallengeRequirements {
pub minimum_challenge_count: usize,
}
impl ParameterSetMetadata for PublicParams {
fn identifier(&self) -> String {
format!(
"FallbackPoSt::PublicParams{{sector_size: {}, challenge_count: {}, sector_count: {}}}",
self.sector_size(),
self.challenge_count,
self.sector_count,
)
}
fn sector_size(&self) -> u64 {
self.sector_size
}
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct PublicInputs<T: Domain> {
#[serde(bound = "")]
pub randomness: T,
#[serde(bound = "")]
pub prover_id: T,
#[serde(bound = "")]
pub sectors: Vec<PublicSector<T>>,
pub k: Option<usize>,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct PublicSector<T: Domain> {
pub id: SectorId,
#[serde(bound = "")]
pub comm_r: T,
}
#[derive(Debug)]
pub struct PrivateSector<'a, Tree: MerkleTreeTrait> {
pub tree: &'a MerkleTreeWrapper<
Tree::Hasher,
Tree::Store,
Tree::Arity,
Tree::SubTreeArity,
Tree::TopTreeArity,
>,
pub comm_c: <Tree::Hasher as Hasher>::Domain,
pub comm_r_last: <Tree::Hasher as Hasher>::Domain,
}
#[derive(Debug)]
pub struct PrivateInputs<'a, Tree: MerkleTreeTrait> {
pub sectors: &'a [PrivateSector<'a, Tree>],
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Proof<P: MerkleProofTrait> {
#[serde(bound(
serialize = "SectorProof<P>: Serialize",
deserialize = "SectorProof<P>: Deserialize<'de>"
))]
pub sectors: Vec<SectorProof<P>>,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct SectorProof<Proof: MerkleProofTrait> {
#[serde(bound(
serialize = "MerkleProof<Proof::Hasher, Proof::Arity, Proof::SubTreeArity, Proof::TopTreeArity>: Serialize",
deserialize = "MerkleProof<Proof::Hasher, Proof::Arity, Proof::SubTreeArity, Proof::TopTreeArity>: DeserializeOwned"
))]
pub inclusion_proofs:
Vec<MerkleProof<Proof::Hasher, Proof::Arity, Proof::SubTreeArity, Proof::TopTreeArity>>,
pub comm_c: <Proof::Hasher as Hasher>::Domain,
pub comm_r_last: <Proof::Hasher as Hasher>::Domain,
}
impl<P: MerkleProofTrait> SectorProof<P> {
pub fn leafs(&self) -> Vec<<P::Hasher as Hasher>::Domain> {
self.inclusion_proofs
.iter()
.map(MerkleProofTrait::leaf)
.collect()
}
pub fn comm_r_last(&self) -> <P::Hasher as Hasher>::Domain {
self.inclusion_proofs[0].root()
}
pub fn commitments(&self) -> Vec<<P::Hasher as Hasher>::Domain> {
self.inclusion_proofs
.iter()
.map(MerkleProofTrait::root)
.collect()
}
#[allow(clippy::type_complexity)]
pub fn paths(&self) -> Vec<Vec<(Vec<<P::Hasher as Hasher>::Domain>, usize)>> {
self.inclusion_proofs
.iter()
.map(MerkleProofTrait::path)
.collect()
}
pub fn as_options(&self) -> Vec<Vec<(Vec<Option<Fr>>, Option<usize>)>> {
self.inclusion_proofs
.iter()
.map(MerkleProofTrait::as_options)
.collect()
}
pub fn inclusion_proofs(
&self,
) -> &Vec<MerkleProof<P::Hasher, P::Arity, P::SubTreeArity, P::TopTreeArity>> {
&self.inclusion_proofs
}
}
#[derive(Debug, Clone)]
pub struct FallbackPoSt<'a, Tree>
where
Tree: MerkleTreeTrait,
{
_t: PhantomData<&'a Tree>,
}
pub fn generate_sector_challenges<T: Domain>(
randomness: T,
challenge_count: usize,
sector_set_len: u64,
prover_id: T,
) -> Result<Vec<u64>> {
(0..challenge_count)
.map(|n| generate_sector_challenge(randomness, n, sector_set_len, prover_id))
.collect()
}
pub fn generate_sector_challenge<T: Domain>(
randomness: T,
n: usize,
sector_set_len: u64,
prover_id: T,
) -> Result<u64> {
let mut hasher = Sha256::new();
hasher.update(AsRef::<[u8]>::as_ref(&prover_id));
hasher.update(AsRef::<[u8]>::as_ref(&randomness));
hasher.update(&n.to_le_bytes()[..]);
let hash = hasher.finalize();
let sector_challenge = LittleEndian::read_u64(&hash[..8]);
let sector_index = sector_challenge % sector_set_len;
Ok(sector_index)
}
pub fn generate_leaf_challenges<T: Domain>(
pub_params: &PublicParams,
randomness: T,
sector_id: u64,
challenge_count: usize,
) -> Vec<u64> {
let mut challenges = Vec::with_capacity(challenge_count);
let mut hasher = Sha256::new();
hasher.update(AsRef::<[u8]>::as_ref(&randomness));
hasher.update(§or_id.to_le_bytes()[..]);
for challenge_index in 0..challenge_count {
let challenge =
generate_leaf_challenge_inner::<T>(hasher.clone(), pub_params, challenge_index as u64);
challenges.push(challenge)
}
challenges
}
pub fn generate_leaf_challenge<T: Domain>(
pub_params: &PublicParams,
randomness: T,
sector_id: u64,
leaf_challenge_index: u64,
) -> u64 {
let mut hasher = Sha256::new();
hasher.update(AsRef::<[u8]>::as_ref(&randomness));
hasher.update(§or_id.to_le_bytes()[..]);
generate_leaf_challenge_inner::<T>(hasher, pub_params, leaf_challenge_index)
}
pub fn generate_leaf_challenge_inner<T: Domain>(
mut hasher: Sha256,
pub_params: &PublicParams,
leaf_challenge_index: u64,
) -> u64 {
hasher.update(&leaf_challenge_index.to_le_bytes()[..]);
let hash = hasher.finalize();
let leaf_challenge = LittleEndian::read_u64(&hash[..8]);
leaf_challenge % (pub_params.sector_size / NODE_SIZE as u64)
}
pub fn vanilla_proof<Tree: MerkleTreeTrait>(
sector_id: SectorId,
priv_inputs: &PrivateInputs<'_, Tree>,
challenges: &[u64],
) -> Result<Proof<Tree::Proof>> {
ensure!(
priv_inputs.sectors.len() == 1,
"vanilla_proof called with multiple sector proofs"
);
let priv_sector = &priv_inputs.sectors[0];
let comm_c = priv_sector.comm_c;
let comm_r_last = priv_sector.comm_r_last;
let tree = priv_sector.tree;
let tree_leafs = tree.leafs();
let rows_to_discard = default_rows_to_discard(tree_leafs, Tree::Arity::to_usize());
trace!(
"Generating proof for tree leafs {} and arity {} for sector {}",
tree_leafs,
Tree::Arity::to_usize(),
sector_id,
);
let inclusion_proofs = (0..challenges.len())
.into_par_iter()
.map(|challenged_leaf_index| {
let challenged_leaf = challenges[challenged_leaf_index];
let proof = tree.gen_cached_proof(challenged_leaf as usize, Some(rows_to_discard))?;
ensure!(
proof.validate(challenged_leaf as usize) && proof.root() == priv_sector.comm_r_last,
"Generated vanilla proof for sector {} is invalid",
sector_id
);
Ok(proof)
})
.collect::<Result<Vec<_>>>()?;
Ok(Proof {
sectors: vec![SectorProof {
inclusion_proofs,
comm_c,
comm_r_last,
}],
})
}
impl<'a, Tree: 'a + MerkleTreeTrait> ProofScheme<'a> for FallbackPoSt<'a, Tree> {
type PublicParams = PublicParams;
type SetupParams = SetupParams;
type PublicInputs = PublicInputs<<Tree::Hasher as Hasher>::Domain>;
type PrivateInputs = PrivateInputs<'a, Tree>;
type Proof = Proof<Tree::Proof>;
type Requirements = ChallengeRequirements;
fn setup(sp: &Self::SetupParams) -> Result<Self::PublicParams> {
Ok(PublicParams {
sector_size: sp.sector_size,
challenge_count: sp.challenge_count,
sector_count: sp.sector_count,
api_version: sp.api_version,
})
}
fn prove<'b>(
pub_params: &'b Self::PublicParams,
pub_inputs: &'b Self::PublicInputs,
priv_inputs: &'b Self::PrivateInputs,
) -> Result<Self::Proof> {
let proofs = Self::prove_all_partitions(pub_params, pub_inputs, priv_inputs, 1)?;
let k = pub_inputs.k.unwrap_or(0);
assert!(
k < 1,
"It is a programmer error to call StackedDrg::prove with more than one partition."
);
Ok(proofs[k].to_owned())
}
fn prove_all_partitions<'b>(
pub_params: &'b Self::PublicParams,
pub_inputs: &'b Self::PublicInputs,
priv_inputs: &'b Self::PrivateInputs,
partition_count: usize,
) -> Result<Vec<Self::Proof>> {
ensure!(
priv_inputs.sectors.len() == pub_inputs.sectors.len(),
"inconsistent number of private and public sectors {} != {}",
priv_inputs.sectors.len(),
pub_inputs.sectors.len(),
);
let num_sectors_per_chunk = pub_params.sector_count;
let num_sectors = pub_inputs.sectors.len();
ensure!(
num_sectors <= partition_count * num_sectors_per_chunk,
"cannot prove the provided number of sectors: {} > {} * {}",
num_sectors,
partition_count,
num_sectors_per_chunk,
);
let mut partition_proofs = Vec::new();
let mut faulty_sectors = BTreeSet::new();
for (j, (pub_sectors_chunk, priv_sectors_chunk)) in pub_inputs
.sectors
.chunks(num_sectors_per_chunk)
.zip(priv_inputs.sectors.chunks(num_sectors_per_chunk))
.enumerate()
{
let (mut proofs, mut faults) = pub_sectors_chunk
.par_iter()
.zip(priv_sectors_chunk.par_iter())
.enumerate()
.map(|(i, (pub_sector, priv_sector))| {
let sector_id = pub_sector.id;
let tree = priv_sector.tree;
let tree_leafs = tree.leafs();
let rows_to_discard =
default_rows_to_discard(tree_leafs, Tree::Arity::to_usize());
trace!(
"Generating proof for tree leafs {} and arity {} for sector {}",
tree_leafs,
Tree::Arity::to_usize(),
sector_id,
);
let mut challenge_hasher = Sha256::new();
challenge_hasher.update(AsRef::<[u8]>::as_ref(&pub_inputs.randomness));
challenge_hasher.update(&u64::from(sector_id).to_le_bytes()[..]);
let (inclusion_proofs, faults) = (0..pub_params.challenge_count)
.into_par_iter()
.fold(
|| (Vec::new(), BTreeSet::new()),
|(mut inclusion_proofs, mut faults), n| {
let sector_index = j * num_sectors_per_chunk + i;
let challenge_index = get_challenge_index(
pub_params.api_version,
sector_index,
pub_params.challenge_count,
n,
);
let challenged_leaf = generate_leaf_challenge_inner::<
<Tree::Hasher as Hasher>::Domain,
>(
challenge_hasher.clone(),
pub_params,
challenge_index,
);
let proof = tree.gen_cached_proof(
challenged_leaf as usize,
Some(rows_to_discard),
);
match proof {
Ok(proof) => {
if proof.validate(challenged_leaf as usize)
&& proof.root() == priv_sector.comm_r_last
&& pub_sector.comm_r
== <Tree::Hasher as Hasher>::Function::hash2(
&priv_sector.comm_c,
&priv_sector.comm_r_last,
)
{
inclusion_proofs.push(proof);
} else {
error!("Found faulty sector: {:?}", sector_id);
faults.insert(sector_id);
}
}
Err(err) => {
error!("Found faulty sector: {:?}: {:?}", sector_id, err);
faults.insert(sector_id);
}
}
(inclusion_proofs, faults)
},
)
.reduce(
|| (Vec::new(), BTreeSet::new()),
|(mut inclusion_proofs, mut faults), (p, f)| {
inclusion_proofs.extend(p);
faults.extend(f);
(inclusion_proofs, faults)
},
);
(
SectorProof {
inclusion_proofs,
comm_c: priv_sector.comm_c,
comm_r_last: priv_sector.comm_r_last,
},
faults,
)
})
.fold(
|| (Vec::new(), BTreeSet::new()),
|(mut sector_proofs, mut sector_faults), (sector_proof, mut faults)| {
sector_faults.append(&mut faults);
sector_proofs.push(sector_proof);
(sector_proofs, sector_faults)
},
)
.reduce(
|| (Vec::new(), BTreeSet::new()),
|(mut sector_proofs, mut sector_faults), (proofs, mut faults)| {
sector_proofs.extend(proofs);
sector_faults.append(&mut faults);
(sector_proofs, sector_faults)
},
);
while proofs.len() < num_sectors_per_chunk {
proofs.push(proofs[proofs.len() - 1].clone());
}
partition_proofs.push(Proof { sectors: proofs });
faulty_sectors.append(&mut faults);
}
if faulty_sectors.is_empty() {
Ok(partition_proofs)
} else {
trace!("Faulty sectors being reported {:?}", faulty_sectors);
Err(Error::FaultySectors(faulty_sectors.into_iter().collect()).into())
}
}
fn verify_all_partitions(
pub_params: &Self::PublicParams,
pub_inputs: &Self::PublicInputs,
partition_proofs: &[Self::Proof],
) -> Result<bool> {
let num_sectors_per_chunk = pub_params.sector_count;
let num_sectors = pub_inputs.sectors.len();
ensure!(
num_sectors <= num_sectors_per_chunk * partition_proofs.len(),
"inconsistent number of sectors: {} > {} * {}",
num_sectors,
num_sectors_per_chunk,
partition_proofs.len(),
);
for (j, (proof, pub_sectors_chunk)) in partition_proofs
.iter()
.zip(pub_inputs.sectors.chunks(num_sectors_per_chunk))
.enumerate()
{
let is_valid = Self::verify(
pub_params,
&PublicInputs {
randomness: pub_inputs.randomness,
prover_id: pub_inputs.prover_id,
sectors: pub_sectors_chunk.to_vec(),
k: Some(j),
},
proof,
)?;
if !is_valid {
return Ok(false);
}
}
Ok(true)
}
fn with_partition(mut pub_in: Self::PublicInputs, k: Option<usize>) -> Self::PublicInputs {
pub_in.k = k;
pub_in
}
fn satisfies_requirements(
public_params: &Self::PublicParams,
requirements: &Self::Requirements,
partitions: usize,
) -> bool {
let checked = partitions * public_params.sector_count;
assert_eq!(
partitions.checked_mul(public_params.sector_count),
Some(checked)
);
assert_eq!(
checked.checked_mul(public_params.challenge_count),
Some(checked * public_params.challenge_count)
);
checked * public_params.challenge_count >= requirements.minimum_challenge_count
}
fn verify(
pub_params: &Self::PublicParams,
pub_inputs: &Self::PublicInputs,
partition_proof: &Self::Proof,
) -> Result<bool> {
ensure!(
pub_inputs.k.is_some(),
"must be called with a partition index"
);
let partition_index = pub_inputs.k.expect("prechecked");
let challenge_count = pub_params.challenge_count;
let num_sectors_per_chunk = pub_params.sector_count;
let j = partition_index;
let proof = partition_proof;
let pub_sectors_chunk = &pub_inputs.sectors;
ensure!(
pub_sectors_chunk.len() <= num_sectors_per_chunk,
"inconsistent number of public sectors: {} > {}",
pub_sectors_chunk.len(),
num_sectors_per_chunk,
);
ensure!(
proof.sectors.len() == num_sectors_per_chunk,
"invalid number of sectors in the partition proof {}: {} != {}",
j,
proof.sectors.len(),
num_sectors_per_chunk,
);
let is_valid = pub_sectors_chunk
.par_iter()
.zip(proof.sectors.par_iter())
.enumerate()
.map(|(i, (pub_sector, sector_proof))| {
let sector_id = pub_sector.id;
let comm_r = &pub_sector.comm_r;
let comm_c = sector_proof.comm_c;
let inclusion_proofs = §or_proof.inclusion_proofs;
trace!("Verifying inclusion proofs for sector {}", sector_id);
let comm_r_last = inclusion_proofs[0].root();
if AsRef::<[u8]>::as_ref(&<Tree::Hasher as Hasher>::Function::hash2(
&comm_c,
&comm_r_last,
)) != AsRef::<[u8]>::as_ref(comm_r)
{
error!("hash(comm_c || comm_r_last) != comm_r: {:?}", sector_id);
return Ok(false);
}
ensure!(
challenge_count == inclusion_proofs.len(),
"unexpected number of inclusion proofs: {} != {}",
challenge_count,
inclusion_proofs.len()
);
let mut challenge_hasher = Sha256::new();
challenge_hasher.update(AsRef::<[u8]>::as_ref(&pub_inputs.randomness));
challenge_hasher.update(&u64::from(sector_id).to_le_bytes()[..]);
let is_valid_list = inclusion_proofs
.par_iter()
.enumerate()
.map(|(n, inclusion_proof)| -> Result<bool> {
let sector_index = j * num_sectors_per_chunk + i;
let challenge_index = get_challenge_index(
pub_params.api_version,
sector_index,
pub_params.challenge_count,
n,
);
let challenged_leaf =
generate_leaf_challenge_inner::<<Tree::Hasher as Hasher>::Domain>(
challenge_hasher.clone(),
pub_params,
challenge_index,
);
if inclusion_proof.root() != comm_r_last {
error!("inclusion proof root != comm_r_last: {:?}", sector_id);
return Ok(false);
}
let expected_path_length = inclusion_proof
.expected_len(pub_params.sector_size as usize / NODE_SIZE);
if expected_path_length != inclusion_proof.path().len() {
error!("wrong path length: {:?}", sector_id);
return Ok(false);
}
if !inclusion_proof.validate(challenged_leaf as usize) {
error!("invalid inclusion proof: {:?}", sector_id);
return Ok(false);
}
Ok(true)
})
.collect::<Result<Vec<bool>>>()?;
Ok(is_valid_list.into_iter().all(|v| v))
})
.reduce(
|| Ok(true),
|all_valid, is_valid| Ok(all_valid? && is_valid?),
)?;
if !is_valid {
return Ok(false);
}
Ok(true)
}
}