Skip to content

Latest commit

 

History

History
245 lines (194 loc) · 14.5 KB

fip-0079.md

File metadata and controls

245 lines (194 loc) · 14.5 KB
fip title author discussions-to status type category created
0079
Add BLS Aggregate Signatures to FVM
Jake (@drpetervannostrand)
Final
Technical (Core)
Core
2023-09-27

FIP-0079: Add BLS Aggregate Signatures to FVM

Simple Summary

This FIP proposes the following changes to FVM:

  1. Addition of a syscall for BLS aggregate signature verification (by definition, this also supports non-aggregate BLS signatures).
  2. Removal of the syscall currently used for generic signature (i.e. Secp256k1 and non-aggregate BLS) validation, and refactoring of its associated SDK function in terms of existing Secp256k1 signature syscalls and the added aggregate BLS syscall.

Abstract

Non-aggregate signature schemes allow one signer to sign one message, whereas aggregate signatures allow multiple parties to sign multiple messages via a single signature. Currently, FVM supports non-aggregate signature verification for Secp256k1 (ECDSA) and BLS (using curve BLS12-381) schemes. This FIP proposes adding support for BLS aggregate signature validation to FVM.

Change Motivation

Currenty, FVM exclusively supports non-aggregate signatures via its verify_signature syscall. The motivation for this FIP is for FVM to additionally support aggregate signatures. The benefits of BLS aggregate signatures are that they allow multiple parties to sign multiple messages via a single constant-sized signature (i.e. the size of an aggregate signature is the same as a non-aggregate) and that verification of an aggregate signature is more efficient than verification of each aggregated signature individually.

Specification

Interfaces

This FIP proposes the following changes to FVM's syscalls:

  • Addition of a syscall verify_bls_aggregate for verifying a BLS aggregate signature; because the verification algorithm for non-aggregate BLS signatures is identical to that for aggregations of one signature, verify_bls_aggregate supports both aggregate and non-aggregate verification.

The syscall's low-level FFI API is:

/// # Arguments
///
/// - `num_signers` - the number of signatures aggregated; for non-aggregate signatures `num_signers = 1`.
/// - `sig_off` - a pointer to the first byte of the signature being verified.
/// - `pub_keys_off` - a pointer to the first public key in an array containing each signer's public
/// key.
/// - `plaintexts_off` - a pointer to the first byte in an array containing each plaintext's bytes,
/// i.e. plaintexts must be allocated contiguously in memory (equivalent to the memory layout of an
/// array containing the concatenated plaintexts' bytes).
/// - `plaintext_lens_off` - a pointer to the first element of an array containing each plaintext's
/// byte length (each plaintexrt's byte length is represented as a `u32`).
///
/// # Returns
///
/// - `Err(IllegalArgument)`:
///     - any pointer and byte length pair are an invalid location in their Wasm module's memory.
///
/// - `Ok(-1)`:
///     - the signature is an invalid G2 compressed curve point.
///     - any public key is an invalid G1 compressed curve point.
///     - there are duplicate plaintexts.
///     - any public key in is the G1 identity/zero point.
///     - the signature is invalid for the provided public keys and plaintexts.
///
/// - `Ok(0)`:
///    - the provided signature is valid for the provided signers' public keys and plaintexts.
///    - the number of signers is zero
///
pub fn verify_bls_aggregate(
    num_signers: u32,
    sig_off: *const u8,
    pub_keys_off: *const [u8; BLS_PUB_LEN],
    plaintexts_off: *const u8,
    plaintext_lens_off: *const u32,
) -> Result<i32>;

The syscall's high-level SDK API is:

/// # Arguments
///
/// - `sig` - the BLS signature (aggregate or non-aggregate) to be verified.
/// - `pub_keys` - the signers' BLS public keys.
/// - `plaintexts` - the signed plaintexts.
///
/// # Returns
///
/// - `SyscallResult::Err(IllegalArgument)`:
///     - unequal numbers of public keys and plaintexts.
///     - plaintexts are large enough to not fit within a Wasm module instance's memory.
///
/// - `Ok(false)`:
///     - the signature is an invalid G2 compressed curve point.
///     - any public key is an invalid G1 compressed curve point.
///     - there are duplicate plaintexts.
///     - any public key in is the G1 identity/zero point.
///     - the signature is invalid for the provided public keys and plaintexts.
///
/// - `Ok(true)`:
///    - the signature is valid for the provided public keys and plaintexts.
///    - `pub_keys` and `plaintexts` are empty.
///
fn verify_bls_aggregate(
    sig: &[u8; 96],
    pub_keys: &[[u8; 48]],
    plaintexts: &[&[u8]],
) -> SyscallResult<bool>;
  • Removal of the syscall verify_signature, used for generic signature (i.e. Secp256k1 and non-aggregate BLS) verification.

Actor changes

Due to the addition of a syscall in this FIP, a corresponding FVM SDK function verify_bls_aggregate is added to expose the new syscall. The SDK function's API is the same as that of the syscall:

fn verify_bls_aggregate(
    aggregate_signature: &[u8; 96],
    pub_keys: &[[u8; 48]],
    plaintexts: &[&[u8]],
) -> bool;

Due to this FIP's removal of the verify_signature syscall, the removed syscall's corresponding FVM SDK function verify_signature is refactored in terms of two existing Secp256k1 syscalls (hash and recover_secp_public_key) and the new aggregate BLS syscall (verify_bls_aggregate). Note that this refactor does not change the SDK function's current API, and consequently, the verify_signature SDK function is used only for non-aggregate signature.

// Signature and signer's address (i.e. signing public key) may be either Secp256k1 or BLS.
fn verify_signature(
    signature: &Signature,
    signer: &Address,
    plaintext: &[u8],
) -> bool;

Gas #

The gas # for verify_bls_aggregate is dependent upon the number of signatures aggregated and the total size (in bytes) of the signed plaintexts. The number of signatures aggregated determines the number of elliptic curve pairing operations performed by the signature verifier, and the total size of plaintexts determines the amount of hashing that a verifier must perform when mapping each plaintext to a curve point.

The gas cost of BLS aggregate signature verification is computed via:

const BLS_GAS_PER_PLAINTEXT_BYTE: usize = 7;
// The gas required to compute one elliptic curve pairing operation for curve BLS12-381.
const BLS_GAS_PER_PAIRING: usize = 8299302;

fn verify_bls_aggregate_gas(plaintexts: &[&[u8]]) -> usize {
    let total_plaintext_len = plaintexts.iter().map(|plaintext| plaintext.len()).sum();
    // A BLS verifier must perform one pairing operation per signature aggregated and an additional
    // pairing to map the aggregate signature to the group `Gt` of curve BLS12-381.
    let num_pairings = plaintexts.len() + 1;
    BLS_GAS_PER_PLAINTEXT_BYTE * total_plaintext_len + BLS_GAS_PER_PAIRING * num_pairings
}

Design Rationale

The motivation for using BLS aggregate signatures over an alternative aggregate signature scheme is that (non-aggregate) BLS are already supported in FVM, the changes required in FVM to support aggregate BLS are minimal, and BLS is a widely used and well audited signature scheme. Additionally, Filecoin's BLS signatures library bls-signatures was audited by the NCC Group prior to Filecoin's Mainnet launch.

Backwards Compatibility

As this FIP proposes the removal of a syscall from FVM, the changes are internally breaking (with respect to FVM), however as all current user-facing interfaces are unchanged; from the perspective of FVM users, the changes are non-breaking and additive (in that one additional syscall and SDK function are added to FVM).

Test Cases

The core implementation of FVM's BLS aggregate signature verification is tested in ref-fvm/shared/src/crypto/signature.rs and the syscall SDK in FVM's syscall actor integration tests.

Security Considerations

As FVM currently supports non-aggregate BLS signatures, this FIP does not affect FVM security.

One security consideration in using BLS aggregate signatures is that plaintexts signed by a single aggregate signature are required to be unique (i.e. multiple BLS private keys cannot sign the same plaintext, then proceed to aggregate those signatures).

Product Considerations

This FIP affects the product in the following ways:

  1. It paves the way to allow more general BLS signature validation in smart contracts.
  2. It makes the FVM less Filecoin specific.

Implementation

Using Rust-like pseudocode, the core implementation of FVM's BLS aggregate signature verification is:

fn verify_bls_aggregate(
    aggregate_signature: &[u8; 96],
    pub_keys: &[[u8; 48]],
    plaintexts: &[&[u8]],
) -> bool {
    if pub_keys.len() != plaintexts.len() {
        return false;
    }

    // Enforce uniqueness of the signed plaintexts.
    for (i, plaintext) in plaintexts.iter().take(plaintexts.len() - 1).enumerate() {
        for other_plaintext in &plaintexts[i + 1..] {
            if plaintext == other_plaintext {
                return false;
            }
        }
    }

    // Deserialize public keys and aggregate signature bytes into BLS12-381 G1 and G2 points.
    let pub_keys: Vec<G1> = pub_keys.iter().map(G1::from_bytes).collect();
    let aggregate_sig = G2::from_bytes(aggregate_signature);

    // Enforce that no public key is the G1 identity/zero point of curve BLS12-381.
    if pub_keys.iter().any(|pub_key| pub_key == G1::zero()) {
        return false;
    }

    // Hash each signed plaintext to a G2 point of curve BLS12-381.
    let digests: Vec<G2> = plaintexts.iter().map(|msg| hash_to_g2(msg)).collect();

    // Verify the aggregate signature by checking an equality of pairings (`e`):
    // `e(G1::generator(), aggregate_signature) == e(pub_key_1, digest_1) * ... * e(pub_key_n, digest_n)`.
    let mut miller_loop: Fp12 = pub_keys
        .iter()
        .zip(&digests)
        .map(|(pub_key, digest)| miller_loop(pub_key, digest))
        .product();
    miller_loop *= miller_loop(-G1::generator(), aggregate_signature);
    miller_loop.final_exponentiation() == Gt::one()
}

FVM uses the Rust crates bls-signatures for making and verifying BLS signatures, and blstrs for functionality specific to elliptic curve BLS12-381, which FVM uses for BLS signatures.

Copyright

Copyright and related rights waived via CC0.