FIP-0082 Source

TitleAdd support for aggregated replica update proofs
Authornemo, Jake, @anorth
Discussions-Tohttps://github.com/filecoin-project/FIPs/discussions/752
StatusAccepted
TypeTechnical
CategoryCore
Created2023-09-26

Spec Sections

FIP-0082: Add support for aggregated replica update proofs

Simple Summary

This FIP proposes adding functionality for submitting several sector update proofs (as a single Groth16 aggregate proof) using a single message, thus allowing many sectors to have data updates in them activated simultaneously when the message is posted to the chain.

Abstract

This proposal adds a way for miners to post multiple ProveReplicaUpdatess at once, in the form of an aggregate Groth16 proof, using the ProveReplicaUpdates3 method described in FIP-0076. The miner actor method ProveReplicaUpdates3 currently provisions an interface for, but does not implement, aggregate sector update proof verification. This FIP proposes ProveReplicaUpdates3 be modified to handle aggregate proof verification.

Change Motivation

Adding aggregate proof verification to the method ProveReplicaUpdates3 amortizes some of the costs associated with multiple sector updates, in the same way that FIP-0013’s ProveCommitAggregate method has done for sealing proofs. While ProveReplicaUpdate is not one of the most frequent message on chain, it is believed to be too expensive to use in its current form.

Aggregate proof verification allows for more sector update commitments to be proven in less time, which will reduce the processing time and, thus, the gas cost, per proven sector update. Verification time and size of an aggregated proof scales logarithmically with the number of proofs included in the aggregate proof.

Specification

Actor changes

This change reuses the miner actor method ProveReplicaUpdates3 (method 35) introduced in FIP-0076 and the method’s existing call parameters ProveReplicaUpdates3Params. The ProveReplicaUpdates3 method and parameters already provision for aggregate proof handling, however the method currently returns an error when an aggregate replica update proof is provided for verification. This FIP proposes replacing the method’s current aggregate proof handling (i.e. an error) with proper aggregate proof verification functionality.

The following shows how the method’s existing call parameters ProveReplicaUpdates3Params accommodate for aggregate proof verification.

pub struct ProveReplicaUpdates3Params {
    // A list of identifiers for the sector's updated in the aggregate proof.
    pub sector_updates: Vec<SectorUpdateManifest>,
    // An empty vector.
    pub sector_proofs: Vec<RawBytes>,
    // A non-empty vector of bytes representing the aggregate replica update proof (for all updated sectors).
    pub aggregate_proof: RawBytes,
    // The replica update proof type; this is the same for all sector updates included in the aggregate proof.
    pub update_proofs_type: RegisteredUpdateProof,
    // The aggregate proof type.
    pub aggregate_proof_type: RegisteredAggregateProof,
    // Whether to abort if any sector update activation fails.
    pub require_activation_success: bool,
    // Whether to abort if any notification returns a non-zero exit code.
    pub require_notification_success: bool,
}

Scale and limits

The minimum of number of sector update proofs that may be aggregated is 3, and the maximum is 512.

Gas calculations

Similar to existing PoRep gas charges, gas values are determined from empirical measurements of aggregate proof validation on representative hardware.

Aggregate proofs must be generated for a power of two number of Groth16 proofs; because each sector update proof contains sixteen Groth16 proofs, aggregated sector update proofs are padded to contain the nearest power of two number of Groth16 proofs. See the “Proof scheme changes” section in FIP-0013 for a discussion on aggregate proof padding.

The gas cost of aggregate proof verification grows both linearly and step-wise in the number of sector update proofs aggregated (counted prior to proof padding). The linear growth occurs for each sector update proof aggregated and the step-wise growth occurs when the number of Groth16 proofs aggregated exceeds a power of two.

The gas table below associates ranges of aggregated sector update proofs with their total step-wise gas cost. The total gas cost for verifying an aggregate proof of n sector update proofs is the sum of n’s linear and step-wise gas costs: n * gas_per_proof + gas_table(n).

32 GiB Gas Cost

Gas cost per sector update proof aggregated: 80,000 gas

Total step-wise gas cost for ranges of sector update proofs aggregated:

SnapDeals Proofs Groth16 Proofs Gas
3-8 48-128 86,500,000
11-128 144-2048 91,300,000
129-256 2064-4096 92,500,000
257-512 4112-8192 99,000,000

Plot of observed and computed gas costs

64 GiB Gas Cost

Gas cost per sector update proof aggregated: 80,000 gas

Total step-wise gas cost for ranges of sector update proofs aggregated:

SnapDeals Proofs Groth16 Proofs Gas
3-8 48-128 86,500,000
9-128 144-2048 92,500,000
129-256 2064-4096 94,000,000
257-512 4112-8192 99,500,000

Plot of observed and computed gas costs

Batch Gas Charge

Currently, GasUsed * BaseFee is burned for every message. We can achieve the requirements described in Incentive Considerations by charging an additional proportional fee to an aggregated batch of proofs, and by balancing their gas costs with a minimum fee. The additional charge for each aggregate replica update proof (an aggregate Groth16 proof) is computed in the same manner as that for aggregate seal proofs; see FIP-0013’s Batch Gas Charge for further discussion.

func PayBatchGasCharge(numProofsBatched, BaseFee) {
    // Cryptoecon Params (need to be updated if verification benchmarks change)
    BatchDiscount = 1/20 unitless
    BatchBalancer = 5 nanoFIL
    SingleProofGasUsage = 36316136

    // Calculating BatchGasCharge
    numProofsBatched = <# of proofs in this batched operation>
    BatchGasFee = Max(BatchBalancer, BaseFee)
    BatchGasCharge = BatchGasFee * SingleProofGasUsage * numProofsBatched * BatchDiscount

    // Pay for the batch
    PayNetFee(BatchGasCharge) // this can be a msg.Send to f99. Does not affect BaseFee
    // normal gas for the verification computation is paid as usual (using & affecting BaseFee)
}

Implications and rough estimates for this function are described in Batch Incentive Alignment.

The SingleProofGasUsage estimate above is based on FVM’s (value)[https://github.com/filecoin-project/ref-fvm/blob/4f2c73e96346cfa7364a51e133ffa906807df7c1/fvm/src/gas/price_list.rs#L193] for verifying a single replica update proof.

State Migrations

Neither changes to the state schema of any actors nor changes to the fields of existing actors are required to make this change. Therefore a state migration is not needed.

Proof scheme changes

This FIP does not introduce new proof scheme changes, but utilizes those changes introduced in FIP-0013 for aggregate seal proofs.

Proofs API

Aggregation

The proofs aggregation procedure expects the following inputs:

pub fn aggregate_empty_sector_update_proofs(
    registered_proof: RegisteredEmptySectorUpdateProof,
    registered_aggregation: RegisteredAggregationProof,
    sector_update_proofs: &[EmptySectorUpdateProof],
    sector_update_inputs: &[SectorUpdateProofInputs],
) -> Result<AggregateSnarkProof>;

The registered_aggregation inputs is required to be RegisteredAggregationProof::SnarkPackV2 at this time, as RegisteredAggregationProof::SnarkPackV1 is not supported for this method.

The sector_update_inputs are a slice of structs logically appearing like this in the rust language.

pub struct SectorUpdateProofInputs {
    pub comm_r_old: Commitment,
    pub comm_r_new: Commitment,
    pub comm_d_new: Commitment,
}

The fields within struct SectorUpdateProofInputs are:

The comm_r_old is the commitment to the sector’s previous replica. The comm_r_new is the commitment to the sector’s current replica. The comm_d_new is the commitment to the sector’s current data.

Since the sector_update_inputs are a slice, they are ordered to match the order of the sector_update_proofs slice provided. However, this does NOT mean that they are required to be vectors of the same length. For test sector sizes, they may end up being the same length because they are proven in a single partition – but for production sector sizes, the partition count will not be one. Instead, the number of elements in the sector_update_inputs vector will be the partitions per sector update * the number of sector update proofs aggregated.

Requirements: The scheme can only aggregate a power of two number of proofs currently. Although there might be some ways to alleviate that requirement, we currently pad the number of input proofs to match a power of two. Thanks to the logarithmic nature of the scheme, performance is still very much acceptable.

Padding is currently naive in the sense that if the passed in count of sector update proofs aggregated is not a power of 2 (greater than 1), we pad the sector update proofs to the nearest power of two using a duplicate of the last sector update proof provided. The minimum number of Groth16 proofs that can be aggregated is 2, thus in the case where a single Groth16 proof is provided for aggregation, the single proof is duplicated in order to pad the number of Groth16 proofs to 2.

Verification

The proofs verification procedure expects the following inputs:

pub fn verify_aggregate_sector_update_proofs(
    registered_proof: RegisteredEmptySectorUpdateProof,
    registered_aggregation: RegisteredAggregationProof,
    aggregate_proof_bytes: AggregateSnarkProof,
    inputs: &[SectorUpdateProofInputs],
    sector_update_inputs: Vec<Vec<Fr>>,
    aggregate_version: groth16::aggregate::AggregateVersion,
) -> Result<bool>;

The registered_aggregation inputs is required to be RegisteredAggregationProof::SnarkPackV2 at this time, as RegisteredAggregationProof::SnarkPackV1 is not supported for this method.

The inputs are an ordered list of SectorUpdateProofInputs (as described above).

The sector_update_inputs are an ordered list of inputs which must match the order of the sector_update_inputs passed into aggregate_empty_sector_update_proofs, but in a flattened manner. First, to retrieve the sector_update_inputs for a single sector, you can call this:

pub fn get_sector_update_inputs(
    registered_proof: RegisteredEmptySectorUpdateProof,
    registered_aggregation: RegisteredAggregationProof,
    comm_r_old: Commitment,
    comm_r_new: Commitment,
    comm_d_new: Commitment,
) -> Result<Vec<Vec<Fr>>> {

As an example, if aggregate_empty_sector_update_proofs is called with the sector_update_inputs of Sector 1 and Sector 2 (where that order is important), we would want to compile the sector_update_inputs for verification as follows (pseudo-code for readability):

let sector_update_inputs: Vec<Vec<Fr>> = Vec::new();
sector_update_inputs.extend(get_sector_update_inputs(..., comm_r_old_sector_one, ...));
sector_update_inputs.extend(get_sector_update_inputs(..., comm_r_old_sector_two, ...));

What this example code does is flatten all of the individual proof sector update inputs into a single list, while properly maintaining the exact ordering matching the sector_update_inputs order going into aggregate_empty_sector_update_proofs. When compiled like this, the sector_update_inputs will be in the exact format required for the verify_aggregate_sector_update_proofs API call.

Similar to aggregation, padding for verification is currently also naive. If the passed-in count of proof input sets (while noting that the inputs are a linear list of equally sized input sets) is not a power of 2, we arbitrarily take the last set of inputs and duplicate it until the count is the next power of 2. Again, the single exception is when the input count is 1. In this case, we duplicate it since the verification algorithm cannot work with a single proof or input.

Proofs format

This FIP uses the same aggregate proof format introduced in FIP-0013’s Proofs Format.

Design Rationale

The existing ProveReplicaUpdates method (method 27) will not become redundant, since aggregation of smaller batches may not be efficient in terms of gas cost (proofs may be too big or too expensive to verify). The method is left intact to support smooth operation through the upgrade period.

Failure handling

Aborting on any precondition failure is chosen for simplicity.

Scale and limits

Each aggregated proof is bounded at 512 sector updates. The motivation for the bound on aggregation size is as follows:

  • to limit the impact of potentially mistaken or malicious behaviour.
  • to gradually increase the scalability, to have time to observe how the network is growing with this new method.
  • to ensure the gas savings are equally accessible to small miners with a sealing rate as low as 1TB/day

A miner may submit multiple batches in a single epoch to grow faster.

Backwards Compatibility

This FIP reuses the miner actor interface proposed and accepted in FIP-0076, however this FIP does change the actor’s currently implemented behavior (from erroring on aggregate proof verification to proper handling of an aggregate proof), thus will require a network upgrade.

This proposal retains the existing non-batch ProveReplicaUpdates (method 27) method, so mining operations need not change workflows due to this proposal (but should in order to enjoy the reduced gas costs).

Test Cases

Test cases will accompany implementation. Suggested scenarios include:

TBD

Security Considerations

All significant implementation changes carry risk.

The core cryptographic techniques come from the Bunz et al. paper from 2019 with strong security proofs. Our protocol is a derivation of this paper that is able to use the already existing powers of tau and with increased performance. The paper is also accompanied by formal security proofs in the same framework as the original paper. The trusted setup used is the Filecoin Powers of Tau and the ZCash Powers of Tau: the full key is generated thanks to this tool. The cryptographic implementation is being audited and a report will be made available soon.

It should be noted that all use of SnarkPack aggregation referenced is limited to SnarkPack V2 and not the initial implementation of SnarkPack. SnarkPack V2 is the only version of SnarkPack still used in the protocol today.

Incentive Considerations

The cryptoeconomics of this FIP are similar to that of FIP-0013.

Implementation

  • The cryptographic implementation for aggregate proving/verifying (i.e. SnarkPack) is currently located in the bellperson Rust crate.
  • Integration between Lotus and crypto-land can be found in rust-fil-proofs and the FFI here.
  • Actors changes are in progress here
  • Lotus integration putting everything together is in progress here: TBD

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

nemo, Jake, @anorth, "FIP-0082: Add support for aggregated replica update proofs," Filecoin Improvement Proposals, no. 0082, September 2023. [Online serial]. Available: https://fips.filecoin.io/fips/fip-0082.