Crate spongefish

Expand description

The Fiat–Shamir transformation for public-coin protocols.

Implements the DSFS transformation from [CO25], wire-compatible with draft-irtf-cfrg-fiat-shamir.

§Examples

A ProverState and a VerifierState can be built via a DomainSeparator, which is composed of a protocol identifier, an optional session identifier, and the public instance. The snippets below illustrate three typical situations.

use spongefish::domain_separator;

// In this example, we prove knowledge of x such that 2^x mod M31 is Y
const P: u64 = (1 << 31) - 1;
fn language(x: u32) -> u32 { (2u64.pow(x) % P) as u32 }
let witness = 42;
let instance = [2, language(witness)];

let domsep = domain_separator!("simplest proof system mod {{P}}"; "{{module_path!()}}")
             .instance(&instance);

// non-interactive prover
let mut prover_state = domsep.std_prover();
prover_state.prover_message(&witness);
let nizk = prover_state.narg_string();
assert!(nizk.len() > 0);

// non-interactive verifier
let mut verifier_state = domsep.std_verifier(nizk);
let claimed_witness = verifier_state.prover_message::<u32>().expect("unable to read a u32");
assert_eq!(language(claimed_witness), language(witness));
// a proof is malleable if we don't check we read everything
assert!(verifier_state.check_eof().is_ok())

The above code will fail to compile if no instance is given. The implementor has full responsibility in providing the correct instance of the proof system.

§Building on external libraries

Spongefish only depends on digest and rand. Support for common SNARK libraries is available optional feature flags. For instance p3-koala-bear provides allows to encode/decode p3_koala_bear::KoalaBear field elements, and can be used to build a sumcheck round. For other algebraic types, see below.

// Requires the `p3-baby-bear` feature.
use p3_koala_bear::KoalaBear;
use p3_field::PrimeCharacteristicRing;
use spongefish::{VerificationError, VerificationResult};

let witness = [KoalaBear::new(5), KoalaBear::new(9)];

let domain = spongefish::domain_separator!("sumcheck"; "{{module_path!()}}").instance(&witness);
let mut prover = domain.std_prover();
let challenge = prover.verifier_message::<KoalaBear>();
let response = witness[0] * challenge + witness[1];
prover.prover_message(&response);
let narg_string = prover.narg_string();

let mut verifier = domain.std_verifier(narg_string);
let challenge = verifier.verifier_message::<KoalaBear>();
let response = verifier.prover_message::<KoalaBear>().unwrap();
assert_eq!(response, witness[0] * challenge + witness[1]);
// a proof is malleable if we don't check we read everything
assert!(verifier.check_eof().is_ok())

§Deriving your own encoding and decoding

A prover message must implement:

Encoding<T>, where T is the relative hash domain (by default [u8]). The encoding must be injective and prefix-free;
NargSerialize, to serialize the message in a NARG string.
NargDeserialize, to read from a NARG string.

A verifier message must implement Decoding to allow for sampling of uniformly random elements from a hash output.

The interface Codec is a shorthand for all of the above.

// Requires the `derive` and `curve25519-dalek` features.
use spongefish::{Codec, domain_separator};
use curve25519_dalek::{RistrettoPoint, Scalar};

#[derive(Clone, Copy, Codec)]
struct PublicKey(RistrettoPoint);

let generator = curve25519_dalek::constants::RISTRETTO_BASEPOINT_POINT;
let domain = spongefish::domain_separator!("challenge-response"; "example")
             .instance(&generator);

let pk = PublicKey(generator * Scalar::from(42u64));
let mut prover = domain.std_prover();
prover.public_message(&pk);
assert_ne!(prover.verifier_message::<[u8; 32]>(), [0; 32]);

§Supported types

Unsigned integers and byte arrays have codecs attached to them. Popular algebraic types are also implemented:

arkworks field elements (including Fp and extension Fp2, Fp3, Fp4, Fp6, Fp12) are available via the ark-ff feature flag;
arkworks elliptic curve elements are available via the ark-ec feature flag;
Ristretto points of curve25519_dalek are available via the curve25519-dalek feature flag;
Plonky3’s BabyBear, KoalaBear, and Mersenne31 field elements are available via (respectively) p3-baby-bear, p3-koala-bear, p3-mersenne-31 feature flags.
p256 field and elliptic curve elements are available via the p256 feature flag.

§Supported hash functions

All hash functions are available in instantiations:

Keccak, the duplex sponge construction [CO25, Section 3.3] for the keccak::f1600 permutation Keccak-f. Available with the keccak feature flag;
Ascon12, the duplex sponge construction [CO25, Section 3.3] for the ascon permutation Ascon, used in overwrite mode. Available with the ascon feature flag;
Shake128, based on the extensible output function sha3::Shake128. Available with the sha3 feature flag (enabled by default);
Blake3, based on the extensible output function blake3::Hasher. Available with the sha3 feature flag (enabled by default);
SHA256, based on sha2::Sha256 used as a stateful hash object. Available with the sha2 feature flag;
SHA512, based on sha2::Sha512 used as a stateful hash object. Available with the sha2 feature flag.

§Implementing your own hash functions

The duplex sponge construction DuplexSponge is described in [CO25, Section 3.3].

The extensible output function instantiations::XOF wraps an object implementing digest::ExtendableOutput and implements the duplex sponge interface with little-to-no code. This covers digest-based XOFs such as SHAKE, KangarooTwelve, and BLAKE3.

The hash bridge Hash wraps an object implementing the digest::Digest trait, and implements the DuplexSpongeInterface

§Security considerations

Only Constructions (1) and (2) are proven secure, in the ideal permutation model; all other constructions are built using heuristics.

Previous version of this library were audited by Radically Open Security.

The user has full responsibility in instantiating DomainSeparator in a secure way, but the library requiring three elements on initialization:

a mandatory 64-bytes protocol identifier, uniquely identifying the non-interactive protocol being built.
a 64-bytes session identifier, corresponding to session and sub-session identifiers in universal composability lingo.
a mandatory instance that will be used in the proof system.

The developer is in charge of making sure they are chosen appropriately. In particular, the instance encoding function prefix-free.

Modules§

instantiations: Instantiations of the DuplexSpongeInterface.

Macros§

domain_separator: Build a DomainSeparator from a formatted string.
session: Attaches a 64-byte session identifier to the domain separator.

Structs§

DomainSeparator: Domain separator for a Fiat–Shamir transformation.
DuplexSponge: The duplex sponge construction from [CO25, Construction 3.3].
ProverState: ProverState is the prover state in the non-interactive transformation.
VerificationError: An error signaling that verification failed.
VerifierState: VerifierState is the verifier state.

Traits§

Codec: Marker trait for types that have encoding and decoding maps.
Decoding: The interface for all types that can be turned into verifier messages.
DuplexSpongeInterface: A DuplexSpongeInterface is an abstract interface for absorbing and squeezing elements implementing Unit.
Encoding: Interface for turning a type into a duplex sponge input.
NargDeserialize: Trait for reading an object from a NARG string.
NargSerialize: Trait for serialization of an object as a NARG string.
Permutation: A permutation over operating over an array of WIDTH Units.
Unit: A trait denoting the requirements for the elements of the alphabet.

Type Aliases§

StdHash: The default hash function provided by the library.
VerificationResult: A Result wrapper that can either return T or a VerificationError.

Derive Macros§

Codec: Derive macro that generates Encoding, Decoding, and NargDeserialize in one go.
Decoding: Derive macro for the Decoding trait.
Encoding: Derive Encoding for structs.
NargDeserialize: Derive macro for the NargDeserialize trait.
Unit: Derive Units for structs.