Skip to content

Latest commit

 

History

History
203 lines (164 loc) · 13.3 KB

proofs.md

File metadata and controls

203 lines (164 loc) · 13.3 KB

Filecoin Proofs

The Filecoin protocol requires a means of generating and verifying the following cryptographic proofs:

  • Proof of Replication proves that a unique copy of a given sector has been created. The Seal operation creates this unique copy and generates a corresponding Proof of Replication.
  • Proof of Space-Time proves that an arbitrary number of sealed sectors existed over a specified period of time in their own dedicated storage — as opposed to being generated on-the-fly at proof time.
  • Piece Inclusion Proof proves that a given piece is contained within a specified sealed sector.
  • Proof of Retrievability is a merkle proof that a given challenged leaf is present in an extant sealed sector.

Throughout this document, the following definitions are used:

  • sector: a fixed-size block of data of SECTOR_SIZE bytes.
  • piece: a block of data of at most SECTOR_SIZE bytes.
  • original data: the concatenation of a sector's constitutent pieces, all piece padding, and any terminal padding.
  • unsealed sector: a concrete representation (on disk or in memory) of a sector's original data.
  • sealed sector: a concrete representation (on disk or in memory) of the unique replica generated by Seal from an unsealed sector.
  • piece padding: a block of zero or more 'zero bytes' inserted between pieces to ensure they are positioned within the containing sector in a way compatible with the Piece Inclusion Proof.
  • terminal padding: a block of zero or more 'zero bytes' inserted after a sector's final piece, ensuring that the length of the original data is SECTOR_BYTES.
  • preprocessing: a transformation applied to an unsealed sector as the first stage of sealing and which may increase the size of the data.
  • preprocessed data: the result of preprocessing the original data.
  • preprocessed sector: a concrete representation (on disk or in memory) of a sector's preprocessed data.
  • SNARK proof: a block of bytes which proves that the creator is in possession of a satisfying assignment to a quadratic arithmetic program (circuit).
  • Multi-SNARK proof: a block of one or more SNARK proofs, each proving partition of the total set of challenges to be proved.
  • merkle inclusion proof: a proof (whose format is unspecified here) that a given leaf block is contained within a merkle tree whose root is the commitment associated with the proof.
  • commitment: an opaque block of data to which a prover 'commits', enabling subsequent proofs which cannot be validly constructed unless the commitment itself was validly constructed. For example: the output of a suitable pseudorandom collision-resistant hash function may serve as a commitment to the data which is the preimage of that hash. Publication of the commitment proves that the creator was in possession of the preimage at the time the commitment was generated.
  • prover: the party who generates a proof.
  • verifier: the party who verifies a proof generated by a prover.
  • sectors count: the number of sectors over which a proof-of-spacetime is performed (POST_SECTORS_COUNT).

Filecoin Proof of Replication

Filecoin Proof of Replication generates a unique copy (sealed sector) of a sector's original data, a Multi-SNARK proof, and a set of commitments identifying the sealed sector and linking it to the corresponding unsealed sector.

Seal

Seal has the side effect of generating a sealed sector from an unsealed sector, and returns identifying commitments and a Multi-SNARK proof. The proof returned is a Multi-SNARK proof.

The commitments are used to verify that the correct original data was sealed, and that the correct sealed data is the subject of later Proofs of Space-Time, proving that this data is being stored continuously.

Seal operates by performing a slow encoding of the unsealed sector — such that it is infeasible for a dishonest prover to computationally regenerate the sealed sector quickly enough to satisfy subsequent required Proofs of Space-Time — thus ensuring that the sealed sector remains manifest as a unique, concrete representation of the original data.

Seal
 (
  // request represents a request to seal a sector.
  partitions     uint64,      // influences the size of the output proof; using less partitions requires more hardware but produces shorter proofs
  sectorSize     uint64,      // the number of bytes in the sealed sector
  unsealedPath   string,      // path of unsealed sector (regular file, ramdisk, etc.) from which a unique replica will be created
  sealedPath     string,      // path to which sealed sector will be written
  proverID       [31]byte,    // uniquely identifies miner
  ticket         [32]byte,    // ticket to which miner commits when sealing begins
  sectorID       [31]byte,    // uniquely identifies sector
 ) err Error | (
  // response contains the commitments resulting from a successful Seal().
  commD          [32]byte,    // data commitment: merkle root of original data
  commR          [32]byte,    // replica commitment: merkle root of replicated data [will be removed in future iteration]
  commRStar      [32]byte,    // a hash of intermediate layers
  proof          []byte, 
 )

VerifySeal

VerifySeal is the functional counterpart to Seal's proof component. It takes all of Seal's outputs, along with those of Seal's inputs which are required to uniquely identify the created sealed sector. This allows a verifier to determine whether a given proof is valid. All inputs are required because verification requires sufficient context to determine not only that a proof is valid but also that the proof indeed corresponds to what it purports to prove.


VerifySeal
 (
  // request represents a request to verify the output of a Seal() operation.
  commD       [32]byte, // returned from Seal
  commR       [32]byte, // returned from Seal [will be removed in future iteration]
  commRStar   [32]byte, // returned from Seal
  proof       []byte,   // returned from Seal
  proverID    [31]byte, // uniquely identifies miner
  ticket      [32]byte, // ticket to which miner committed when sealing began
  sectorID    [31]byte, // uniquely identifies sector
) err Error | 
  IsValid bool          // true iff the provided proof-of-replication os valid

Unseal

Unseal is the counterpart to Seal's encoding side-effect. It reverses the 'slow encoding' and creates an unsealed sector from a sealed sector as a special case of its more general function. In general, it allows extraction of a range of bytes (specified in terms of the layout of the original data).

Unseal
 (
  // request represents a request to unseal a sector.
  sectorSize    uint64,   // the number of bytes in the sealed sector
  sealedPath    string,   // path from which sealed bytes will be read
  outputPath    string,   // path to which unsealed bytes will be written (regular file, ramdisk, etc.)
  proverID      [31]byte, // uniquely identifies miner
  sectorID      [31]byte, // uniquely identifies sector
  startOffset   uint64,   // zero-based byte offset in original, unsealed sector-file
  numBytes      uint64,   // number of bytes to unseal (corresponds to contents of unsealed sector-file)
 ) err Error |
  NumBytesWritten uint64  // the number of bytes unsealed (and written) by Unseal()

Security Notes

Guaranteeing sector uniqueness

Every sealed sector is unique, even if the unsealed data is identical. This prevents a malicious miner from storing the same sector twice without dedicating twice the amount of storage, or two malicious miners pretending to store the same sector, but only storing one copy. Sector uniqueness is guaranteed by having unique proverId and sectorId. Each miner has a unique proverID, and each sector has a unique sectorIDwithin that miner's sectors. Taken together, proverID and sectorID are globally unique . Both the proverId and the sectorId are used to encode the sealed data.

The Filecoin node verifies that the correct proverId and sectorId is used when verifying the proof.

Proof of Space-Time

NOTE: Proof of Space-Time is in transition. Current implementations are mocked, and the final design has not been implemented. Consumers may refer to the below for reference, but nothing should be implemented until the spec is updated and synchronized with what will be the canonical construction.

GeneratePost

GeneratePoSt generates a Proof of Space-Time over POST_SECTORS_COUNT sealed sectors — identified by their commR commitments. This is accomplished by performing a series of merkle inclusion proofs (Proofs of Retrievability). Each proof is of a challenged node in a challenged sector. The challenges are generated pseudo-randomly, based on the provided challengeSeed. At each time step, a number of Proofs of Retrievability are performed. The result of each such set of Proofs of Retrievability is used to seed challenge generation for another iteration. Repeated and necessarily sequential generation of these Proofs of Retrievability proves that the claimed sealed sectors existed during the time required to generate them.

Since many sealed sectors may be proved at once, it may be the case that one or more sealed sectors has been lost, damaged, or otherwise become impossible to validly prove. In this case, a fault is recorded and returned in an array of faults. This allows provers to selectively default on individual sealed sector proofs while still providing a verifiable proof of their aggregate Proof of Space-Time claims.

GeneratePoSt
 (
  // request represents a request to generate a proof-of-spacetime.
  commRs         [POST_SECTORS_COUNT][32]byte,  // the commR commitments corresponding to the sealed sectors to prove
  challengeSeed  [32]byte,    // a pseudo-random value to be used in challenge generation
) err Error | (
  // response contains PoST proof and any faults that may have occurred.
  faults        []uint64,    // faults encountered while proving (by index of associated commR in the input) 
  proof         []byte
)

VerifyPoSt

VerifyPoSt is the functional counterpart to GeneratePoSt. It takes all of GeneratePoSt's output, along with those of GeneratePost's inputs required to identify the claimed proof. All inputs are required because verification requires sufficient context to determine not only that a proof is valid but also that the proof indeed corresponds to what it purports to prove.

VerifyPoSt
 (
  // request represents a request to generate verify a proof-of-spacetime.
  commRs        [POST_SECTORS_COUNT][32]byte,        // the commRs provided to GeneratePoSt
  challengeSeed [32]byte,
  faults        []uint64
  proof         []byte,            // Multi-SNARK proof returned by GeneratePoSt 
 ) err Error | 
  isValid bool                     // true iff the provided Proof of Space-Time is valid

Piece Inclusion Proof

PieceInclusionProof

A PieceInclusionProof contains a potentially complex merkle inclusion proof that all leaves included in commP (the piece commitment) are also included in commD (the sector data commitment).

struct PieceInclusionProof {
    Position uint,
    ProofElements [32]byte
}

GeneratePieceInclusionProofs

GeneratePieceInclusionProofs takes a merkle tree and a slice of piece start positions and lengths (in nodes), and returns a vector of PieceInclusionProofs corresponding to the pieces. For this method to work, the piece data used to validate pieces will need to be padded as necessary, and pieces will need to be aligned (to 128-byte chunks due to details of preprocessing) when written. This assumes that pieces have been packed and padded according to the assumptions of the algorithm. For this reason, practical implementations should also provide a function to assist in correct packing of pieces.

GeneratePieceInclusionProofs
 (
  Tree MerkleTree,
  PieceStarts []uint
  PieceLengths uint,
 ) []PieceInclusionProof

GeneratePieceInclusionProof takes a merkle tree and the index positions of the first and last nodes of the piece whose inclusion should be proved. It returns a corresponding PieceInclusionProof. For the resulting proof to be valid, first_node must be <= last_node.

GeneratePieceInclusionProof
 (
  tree          MerkleTree,
  firstNode     uint,
  pieceLength   uint,
 ) err Error |  proof PieceInclusionProof

VerifyPieceInclusionProof takes a sector data commitment (commD), piece commitment (commP), sector size, and piece size. Iff it returns true, then PieceInclusionProof indeed proves that all of piece's bytes were included in the merkle tree corresponding to commD of a sector of sectorSize. The size inputs are necessary to prevent malicious provers from claiming to store the entire piece but actually storing only the piece commitment.

VerifyPieceInclusionProof
 (
  proof PieceInclusionProof,  
  commD  [32]byte,
  commP [32]byte,
  sectorSize uint,
  pieceSize uint,
 ) err Error | IsValid bool // true iff the provided PieceInclusionProof is valid.