Skip to main content
Version: 4.0.0

FRI API Documentation

Overview​

The Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI) protocol is used to efficiently verify that a given polynomial has a bounded degree.

The Prover asserts that they know a low-degree polynomial F(x) of degree d, and they provide oracle access to a Reed-Solomon (RS) codeword representing evaluations of this polynomial over a domain L:

RS(F(x),L,n)={F(1),F(α),F(α2),...,F(αn−1)}RS(F(x), L, n) = \{F(1), F(\alpha), F(\alpha^2), ..., F(\alpha^{n-1})\}

where α is a primitive root of unity, and n=2ln = 2^l (for l∈Zl ∈ Z) is the domain size.

How it works​

The proof construction consists of three phases: the Commit and Fold Phase, the Proof of Work Phase (optional), and the Query Phase. Using a Fiat-Shamir (FS) scheme, the proof is generated in a non-interactive manner, enabling the Prover to generate the entire proof and send it to the Verifier for validation. The polynomial size must be a power of 2 and is passed to the protocol in evaluation form.

Prover​

Commit and Fold Phase​

  • The prover commits to the polynomial evaluations by constructing a Merkle tree.
  • A folding step is performed iteratively to reduce the polynomial degree.
  • In each step, the polynomial is rewritten using random coefficients derived from Fiat-Shamir hashing, and a new Merkle tree is built for the reduced polynomial.
  • This process continues recursively until the polynomial reaches a minimal length.
  • Currently, only a folding factor of 2 is supported.

Proof of Work Phase (Optional)​

  • If enabled, the prover is required to find a nonce such that, when hashed with the final Merkle tree root, the result meets a certain number of leading zero bits.

Query Phase​

  • Using the Fiat-Shamir transform, the prover determines the random query indices based on the previously committed Merkle roots.
  • For each sampled index, the prover provides the corresponding Merkle proof, showing that the value is part of the committed Merkle tree.
  • The prover returns all required data as the FriProof, which is then verified by the verifier.

Verifier​

  • The verifier checks the Merkle proofs to ensure the sampled values were indeed committed to in the commit phase.
  • The verifier reconstructs the Fiat-Shamir challenges from the prover's commitments and verifies that the prover followed the protocol honestly.
  • The folding relation is checked for each sampled query.
  • If all checks pass, the proof is accepted as valid.

C++ API​

Configuration structs​

There are two key configuration structs related to the Fri protocol.

FriConfig​

The FriConfig struct is used to specify parameters for the FRI protocol. It contains the following fields:

  • stream: icicleStreamHandle: The CUDA stream for asynchronous execution. If nullptr, the default stream is used.
  • folding_factor: size_t: The factor by which the codeword is folded in each round.
  • stopping_degree: size_t: The minimal polynomial degree at which folding stops.
  • pow_bits: size_t: Number of leading zeros required for proof-of-work. If set, the optional proof-of-work phase is executed.
  • nof_queries: size_t: Number of queries computed for each folded layer of FRI.
  • are_inputs_on_device: bool: If true, the input polynomials are stored on the device (e.g., GPU); otherwise, they remain on the host (e.g., CPU).
  • is_async: bool: If true, it runs the hash asynchronously.
  • ext: ConfigExtension*: Backend-specific extensions.

The default values are:

// icicle/fri/fri_config.h
struct FriConfig {
icicleStreamHandle stream = nullptr;
size_t folding_factor = 2;
size_t stopping_degree = 0;
size_t pow_bits = 16;
size_t nof_queries = 100;
bool are_inputs_on_device = false;
bool is_async = false;
ConfigExtension* ext = nullptr;
};
note

Currently, only a folding factor of 2 is supported.

FriTranscriptConfig​

The FriTranscriptConfig<TypeParam> class is used to specify parameters for the Fiat-Shamir scheme used by the FRI protocol. It contains the following fields:

  • hasher: Hash: The hash function used to generate randomness for Fiat-Shamir.
  • domain_separator_label: std::vector<std::byte>
  • round_challenge_label: std::vector<std::byte>
  • commit_phase_label: std::vector<std::byte>
  • nonce_label: std::vector<std::byte>
  • public_state: std::vector<std::byte>
  • seed_rng: TypeParam: The seed for initializing the RNG.
note

The encoding is little endian.

There are three constructors for FriTranscriptConfig<TypeParam>:

  • Default constructor:
// icicle/fri/fri_transcript_config.h
FriTranscriptConfig()
: m_hasher(create_keccak_256_hash()), m_domain_separator_label({}), m_commit_phase_label({}), m_nonce_label({}),
m_public({}), m_seed_rng(F::zero())
  • Constructor with byte vector for labels:
FriTranscriptConfig(
Hash hasher,
std::vector<std::byte>&& domain_separator_label,
std::vector<std::byte>&& round_challenge_label,
std::vector<std::byte>&& commit_phase_label,
std::vector<std::byte>&& nonce_label,
std::vector<std::byte>&& public_state,
F seed_rng)
: m_hasher(std::move(hasher)), m_domain_separator_label(std::move(domain_separator_label)),
m_round_challenge_label(std::move(round_challenge_label)),
m_commit_phase_label(std::move(commit_phase_label)), m_nonce_label(std::move(nonce_label)),
m_public(std::move(public_state)), m_seed_rng(seed_rng)
  • Constructor with const char* arguments for labels:
    FriTranscriptConfig(
Hash hasher,
const char* domain_separator_label,
const char* round_challenge_label,
const char* commit_phase_label,
const char* nonce_label,
std::vector<std::byte>&& public_state,
F seed_rng)
: m_hasher(std::move(hasher)), m_domain_separator_label(cstr_to_bytes(domain_separator_label)),
m_round_challenge_label(cstr_to_bytes(round_challenge_label)),
m_commit_phase_label(cstr_to_bytes(commit_phase_label)), m_nonce_label(cstr_to_bytes(nonce_label)),
m_public(std::move(public_state)), m_seed_rng(seed_rng)

Generating FRI Proofs​

To generate a proof, first, an empty proof needs to be created. The FRI proof is represented by the FriProof<TypeParam> class:

// icicle/fri/fri_proof.h
template <typename F>
class FriProof

The class has a default constructor FriProof() that takes no arguments.

To generate a FRI proof using the Merkle Tree commit scheme, use one of the following functions:

  1. Directly call prove_fri_merkle_tree:
    template <typename F>
    eIcicleError prove_fri_merkle_tree(
    const FriConfig& fri_config,
    const FriTranscriptConfig<F>& fri_transcript_config,
    const F* input_data,
    const size_t input_size,
    Hash merkle_tree_leaves_hash,
    Hash merkle_tree_compress_hash,
    const uint64_t output_store_min_layer,
    FriProof<F>& fri_proof /* OUT */);
  2. Use the fri_merkle_tree namespace, which internally calls prove_fri_merkle_tree:
    fri_merkle_tree::prove<TypeParam>( ... );
    This approach calls prove_fri_merkle_tree internally but provides a more structured way to access it.
  • input_data: const F*: Evaluations of The input polynomial.
  • fri_proof: FriProof<F>&: The output FriProof object containing the generated proof.
  • merkle_tree_leaves_hash, merkle_tree_compress_hash and output_store_min_layer refer to the hashes used in the Merkle Trees built in each round of the folding. For further information about ICICLE's Merkle Trees, see Merkle-Tree documentation and Hash documentation.
note

folding_factor must be divisible by merkle_tree_compress_hash.

note

An NTT domain is used for proof generation, so before generating a proof, an NTT domain of at least the input_data size must be initialized. For more information see NTT documentation.

NTTInitDomainConfig init_domain_config = default_ntt_init_domain_config();
ntt_init_domain(scalar_t::omega(log_input_size), init_domain_config)

:::

Example: Generating a Proof​

// Initialize ntt domain
NTTInitDomainConfig init_domain_config = default_ntt_init_domain_config();
ntt_init_domain(scalar_t::omega(log_input_size), init_domain_config);

// Define hashers for merkle tree
uint64_t merkle_tree_arity = 2;
Hash hash = Keccak256::create(sizeof(TypeParam)); // hash element -> 32B
Hash compress = Keccak256::create(merkle_tree_arity * hash.output_size()); // hash every 64B to 32B

// set transcript config
const char* domain_separator_label = "domain_separator_label";
const char* round_challenge_label = "round_challenge_label";
const char* commit_phase_label = "commit_phase_label";
const char* nonce_label = "nonce_label";
std::vector<std::byte>&& public_state = {};
TypeParam seed_rng = TypeParam::one();

FriTranscriptConfig<TypeParam> transcript_config(
hash, domain_separator_label, round_challenge_label, commit_phase_label, nonce_label, std::move(public_state),
seed_rng);

// set fri config
FriConfig fri_config;
fri_config.nof_queries = 100;
fri_config.pow_bits = 16;
fri_config.folding_factor = 2;
fri_config.stopping_degree = 0;

FriProof<TypeParam> fri_proof;

// get fri proof
eIcicleError err = fri_merkle_tree::prove<TypeParam>(
fri_config, transcript_config, scalars.get(), input_size, hash, compress, output_store_min_layer, fri_proof);
ICICLE_CHECK(err);

// Release ntt domain
ntt_release_domain<scalar_t>();

Verifying Fri Proofs​

To verify the FRI proof using the Merkle Tree commit scheme, use one of the following functions:

  1. Directly call verify_fri_merkle_tree:
// icicle/fri/fri.h
template <typename F>
eIcicleError verify_fri_merkle_tree(
const FriConfig& fri_config,
const FriTranscriptConfig<F>& fri_transcript_config,
FriProof<F>& fri_proof,
Hash merkle_tree_leaves_hash,
Hash merkle_tree_compress_hash,
bool& valid /* OUT */);
  1. Use the fri_merkle_tree namespac, which internally calls verify_fri_merkle_tree:
fri_merkle_tree::verify<TypeParam>( ... );
note

FriConfig and FriTranscriptConfig used for generating the proof must be identical to the one used for verification.

Example: Verifying a Proof​

bool valid = false;
eIcicleError err = fri_merkle_tree::verify<TypeParam>(
fri_config, transcript_config, fri_proof, hash, compress, valid);
ICICLE_CHECK(err);
ASSERT_EQ(true, valid); // Ensure proof verification succeeds

After calling fri_merkle_tree::verify, the variable valid will be set to true if the proof is valid, and false otherwise.