SAFE - Sponge API for Field Elements

A generic API for sponge functions.

This is a minimal, no_std, pure Rust implementation of a sponge function, based on SAFE (Sponge API for Field Elements), to be used in permutation-based symmetric primitives' design, such as hash functions, MACs, authenticated encryption schemes, PRNGs, and other. The sponge is designed to be usable in zero-knowledge proving systems (ZKPs) as well as natively, operating on types implementing Default, Copy, and Zeroize. The backend must provide a suitable field, permutation, tag hash, arithmetic and equality semantics; the Rust representation size alone does not establish cryptographic security.

Introduction

Sponge functions are the basis of permutation-based symmetric primitives’ design. They can be seen as a stateful object that can ingest input (“absorb”) and produce output (“squeeze”) at any time and in arbitrary order.

As its main features, this sponge API:

• Does not use any padding, thus not wasting an extra call to the sponge permutation in any circumstances
• Is independent of an underlying permutation and thus can be used with almost every design on the market (including Poseidon’s).
• Eliminates a number of misuse patterns by limiting the set of operations callable at sponge and by binding a protocol designer to a specific order of these operations.
• Is provably secure in the random permutation model in a number of settings, including the overlooked but frequently required cross-protocol security.
• Is among the first constructions to store the protocol’s metadata in the sponge inner part, provably losing no security

This sponge construction in itself does not support variable-length hashing, i.e. hashing where the length of data hashed is unknown in advance. However, this behavior can be achieved by wrapping the sponge in a hasher, that only starts the sponge upon finalizing the hash, thus at a time when the length of the input is known (example implementation of this wrapper can be found in dusk-poseidon).

Construction

The sponge constructed in this library is defined by:

• a state [T; W] with type T: Default + Copy and width W
• a permutation function that permutes the state
• a capacity of 1
• a rate R with R = W - 1
• an input-output (IO) pattern that defines the sequence to ingest len items of input (absorb(len)) and pruduce output (squeeze(len)) (eg. [absorb(4), absorb(1), squeeze(3)])
• a domain separator to distinguish between equivalent sponges with different usecases.

With capacity fixed to one field element, security depends on the actual field cardinality and the chosen permutation and tag hash, not size_of::<T>(). The backend must provide the additive identity and field arithmetic, use constant-time native operations on secrets, and properly constrain circuit operations. In a circuit, an equality callback may add a constraint and return true; authentication is not established until the resulting proof is successfully verified. Secrets retained in the backend require its own cleanup.

Abstract API

start

1. Verify IO pattern:
   • IO pattern has at least two calls.
   • First call is to absorb.
   • Last call is to squeeze.
   • The width is at least two.
   • Individual calls and aggregated consecutive runs have lengths from 1 through 2^31 - 1.
2. Compute the tag using the IO pattern and a domain separator.
   1. Encode the IO pattern as a list of 32-bit words whose MSB is set to 1 for absorb and to 0 for squeeze, and the length is added to the lower bits. Any contiguous calls to absorb and squeeze will be aggregated, e.g. the above example of an IO pattern of [absorb(4), absorb(1), squeeze(3)] will have the same encoding as [absorb(5), squeeze(3)]: [0x8000_0005, 0x0000_0003].
   2. Serialize the words in big-endian order and append the eight-byte big-endian u64 domain separator. With separator 0x4142, the example above yields 0x80000005000000030000000000004142.
   3. Hash the byte string into the tag, an element of type T.
3. Initialize first element of the state to the tag and set the remaining elements to the default value of T.
4. Set both absorb and squeeze positions to zero.
5. Set the IO count to zero.

finish

1. Return the output vector only if the IO count equals the pattern length and the instance has never failed or been explicitly zeroized; otherwise return an error.
2. Erase the state and its variables.

Every operation error and explicit zeroization permanently invalidates that sponge. Subsequent absorb, squeeze and finish calls reject it; cloning a failed sponge does not restore validity. Debug formatting omits state, buffered output and the backend.

absorb(len, input)

1. Check that the call to absorb matches the entry of in the IO pattern at the IO count, and check that the input yields sufficient elements (erase state and return error if not).
2. For the first len elements of input:
   1. Call the permutation function if pos_absorb == rate and set pos_absorb = 0.
   2. Add the element to the state at pos_absort + 1 (we skip the first element which is the capacity).
   3. Increment pos_absorb by one.
3. Increment the IO count.
4. Set the pos_squeeze to the rate to force a call to the permutation function at the start of the next call to squeeze.

squeeze(len)

1. Check that the call to absorb matches the entry of in the IO pattern at the IO count (erase state and return error if not).
2. len times:
   1. Call the permutation function if pos_squeeze == rate and set pos_squeeze = 0
   2. Append the element of the state at position pos_squeeze + 1 (also here we skip the first element due to the capacity) to the output vector.
3. Increment the IO count.

Note that we do not set the pos_absorb to the rate as we do with the pos_squeeze in the call to absorb, this is because we may want the state to absorb at the same positions that have been squeezed.

Output storage and resource limits

Output storage grows only for actual squeeze requests, not for the entire declared pattern at construction. Growth allocates a replacement, copies live output, and zeroizes the old allocation before releasing it; the same rule protects continued clones. Failed output-growth allocations return InvalidIOPattern and permanently invalidate the sponge; other allocations retain the platform's allocation-failure behavior. Callers must bound pattern sizes and output requests to their own memory budget: allocator success does not guarantee that an operating system can back an arbitrarily large allocation. Growth temporarily keeps old and new buffers live. Encryption/decryption temporary vectors are zeroized on error or unwinding; returned vectors are owned by the caller. This does not erase copies retained by a backend, compiler, or a process that aborts.

Example

use dusk_bls12_381::BlsScalar;
use ff::Field;
use rand::rngs::StdRng;
use rand::SeedableRng;
use dusk_safe::{Error, Call, Safe, Sponge};

const W: usize = 7;

#[derive(Default, Debug, Clone, Copy, PartialEq)]
struct Rotate();

impl Safe<BlsScalar, W> for Rotate {
    // Rotate every item one item to the left, first item becomes last.
    // Note: This permutation is just an example and *should not* be used for a
    // sponge construction for cryptographically safe hash functions.
    fn permute(&mut self, state: &mut [BlsScalar; W]) {
        let tmp = state[0];
        for i in 1..W {
            state[i - 1] = state[i];
        }
        state[W - 1] = tmp;
    }

    // Define the hasher used to generate the tag from the encoding of the
    // io-pattern and domain-separator.
    fn tag(&mut self, input: &[u8]) -> BlsScalar {
        BlsScalar::hash_to_scalar(input)
    }

    fn add(&mut self, right: &BlsScalar, left: &BlsScalar) -> BlsScalar {
        right + left
    }
}

impl Rotate {
    pub fn new() -> Self {
        Self()
    }
}

// pick a domain-separator
let domain_sep = 0;

// generate random input
let mut rng = StdRng::seed_from_u64(0x42424242);
let mut input = [BlsScalar::zero(); 8];
input.iter_mut().for_each(|s| *s = BlsScalar::random(&mut rng));

// build the io-pattern
let iopattern = vec![
    Call::Absorb(6),
    Call::Absorb(2),
    Call::Squeeze(1),
    Call::Squeeze(2),
];

// start the sponge
let mut sponge = Sponge::start(
    Rotate::new(),
    iopattern,
    domain_sep,
)
.expect("io-pattern should be valid");

// absorb 6 elements
sponge.absorb(6, &input).expect("absorbing should not fail");
// absorb 2 elements
sponge.absorb(2, &input[6..]).expect("absorbing should not fail");

// squeeze 1 element
sponge.squeeze(1).expect("squeezing should not fail");
// squeeze 2 elements
sponge.squeeze(2).expect("squeezing should not fail");

// generate the hash output
let output1 = sponge.finish().expect("Finishing should not fail");


// Generate another hash output from the same input and aggregated IO pattern:
// build the io-pattern
let iopattern = vec![
    Call::Absorb(8),
    Call::Squeeze(3),
];

// start the sponge
let mut sponge = Sponge::start(
    Rotate::new(),
    iopattern,
    domain_sep,
)
.expect("io-pattern should be valid");

// absorb 8 elements
sponge.absorb(8, &input).expect("absorbing should not fail");

// squeeze 3 elements
sponge.squeeze(3).expect("squeezing should not fail");

// generate the hash output
let output2 = sponge.finish().expect("Finishing should not fail");

assert_eq!(output1, output2);