# Fiat-Shamir specification

## Introduction

Our proof system is designed to perform signature aggregation of the Beam Chain efficiently. The underlying protocols are interactive, requiring a prover and verifier to exchange a sequence of messages. However, in a high-throughput, decentralized environment like ours, interactive rounds are impractical and introduce unnecessary overhead.

The Fiat-Shamir (FS) transform provides an elegant and rigorous way to eliminate this interaction. By replacing the verifier’s random challenges with the output of a cryptographic hash function, the prover can simulate the entire protocol transcript in a non-interactive way. This enables the construction of compact, self-contained proofs that can be verified without back-and-forth communication.

## Why Fiat-Shamir works

In a public-coin protocol, the verifier’s messages consist only of random challenges. Instead of requiring the verifier to generate these challenges interactively, the FS transform derives them deterministically by hashing the current transcript. Specifically, at each step, the prover computes:

\begin{equation}
c_i = H(x, m_1, m_2, \dots, m_{i-1})
\end{equation}

where $x$ is the input, $m_1, m_2, \dots$ are the previous messages, and $H$ is a hash function.

This approach ensures two crucial properties:
1. The challenges are unpredictable before the prover commits to earlier messages.
2. The verifier can recompute the challenges independently, ensuring consistency.

## The role of Random Oracles

The security of the FS transform is typically analyzed in the random oracle model. A random oracle is an idealized function that, for each new input, outputs a uniformly random value and remembers it for future queries. Formally, it behaves as:
- For any input $q$ not seen before, choose $R \leftarrow \text{Uniform}(\{0,1\}^n)$ and store $(q, R)$.
- For any repeated input $q$, return the previously stored $R$.

In practice, we cannot implement a true random oracle. Instead, we instantiate it using cryptographic hash functions. This substitution is part of the random oracle methodology: we prove security assuming ideal oracles, then use hash functions heuristically in real-world systems.

## The Fiat-Shamir Heuristic

Because real hash functions are not perfect random oracles, the FS transform is formally a heuristic. We assume that if the hash function has strong properties (such as collision resistance and preimage resistance), then the non-interactive scheme produced by the FS transform will remain secure.

## Importance of correct Fiat-Shamir specification

While the Fiat-Shamir transform is conceptually simple, incorrect implementations can introduce subtle and catastrophic vulnerabilities. In the context of Beam Chain’s signature aggregation for Ethereum consensus, a flawed Fiat-Shamir design can break critical security guarantees, including soundness for example.

Let us give a simple example. If the hashing context is incomplete or insufficient — meaning that not all necessary protocol inputs, commitments, and prior messages are fed into the hash — the prover may forge transcripts or bypass security checks. This directly undermines the soundness of the proof system.

To avoid these risks, we must define a simple, reliable, and consistent Fiat-Shamir specification tailored to our protocol. Every input, message, and domain separation step must be carefully documented. We must ensure that the prover and verifier compute challenges in exactly the same way, over exactly the same inputs, with no ambiguities or hidden assumptions.

This specification serves not just as a guide for implementation, but as a defense against entire classes of dangerous bugs that have historically appeared in cryptographic systems. Careful adherence to it is critical for the security and robustness of the Beam Chain.

## The transcript

The transcript system organizes the sequence of prover-verifier interactions. It consists of structured building blocks, each strongly typed and labeled. Here’s an overview of the key components.

### `Interaction`

Represents a single step in the transcript between prover and verifier.
Each interaction carries:
* where it sits in the transcript hierarchy,
* what type of action it is,
* how it should be interpreted and validated.

@dataclass
class Interaction:
    # Where in the transcript this step sits: standalone or part of a block.
    hierarchy: InteractionHierarchy  
    
    # What kind of action is happening.
    kind: InteractionKind 
    
    # Descriptive name (e.g., "random_challenge") used to identify the purpose of this step.
    label: str    
    
    # String name of the data type (e.g., "Scalar", "Digest"). Used for type checking and debugging.
    type_name: str   
    
    # How much data is attached: none, single value, fixed block, or dynamic size.
    length: Length                   

### `InteractionHierarchy`

Defines where in the transcript the interaction sits relative to other actions.

from enum import Enum

class InteractionHierarchy(Enum):
    # A single, standalone action (not part of any multi-interaction block).
    ATOMIC

    # Marks the start of a nested block or sub-protocol section.
    BEGIN

    # Marks the end of a nested block, closing the most recent BEGIN.
    END

This enum helps the system:
* Track when a nested section begins and ends.
* Validate that nested sections are properly matched (BEGIN → END).
* Recognize standalone (atomic) actions that are outside any nesting.

### `InteractionKind`

Specifies what kind of action or data is exchanged between prover and verifier. This tells the transcript how to interpret the interaction.

from enum import Enum

class InteractionKind(Enum):
    # Prover → Verifier message.
    # Used for in-band messages that are part of the protocol flow.
    MESSAGE

    # Out-of-band helper data.
    # For example, additional hints or merkle proofs included in the proof.
    HINT

    # Verifier → Prover challenge.
    # Random values or challenges that drive the proof’s randomness.
    CHALLENGE

    # High-level protocol container.
    # Allows grouping together mixed kinds (message, hint, challenge) under one named block.
    # 
    # TODO: Not sure we need this at the end
    PROTOCOL

This enum allows:
* Separating who initiates the interaction (prover vs verifier).
* Classifying special-purpose interactions like hints or challenges.
* Grouping related actions under larger protocol sections for clean organization.

### `Length`

Describes how much data is attached to an interaction. This tells the system how to interpret the size and layout of the data.

from enum import Enum

class Length(Enum):
    # No attached data.
    # Used for markers or empty actions (e.g., BEGIN, END).
    NONE

    # Exactly one item.
    # For example, a single scalar or challenge value.
    SCALAR

    # A fixed-size block of items.
    # The exact count is provided separately in the interaction.
    FIXED

    # A variable-size block.
    # The size is determined dynamically during execution.
    # 
    # TODO: Not sure we need this at the end (simpler if we don't need it)
    DYNAMIC

This enum helps:
* Distinguish single values from blocks of data.
* Support both fixed and dynamic interaction sizes.
* Clearly separate cases where no data is involved (like BEGIN/END markers).

### `TranscriptPattern`

Represents the full sequence of interactions between prover and verifier. It acts as a formal recipe or pattern that defines how the transcript unfolds.

from dataclasses import dataclass
from typing import List

@dataclass
class TranscriptPattern:
    # Ordered list of all interactions in the transcript.
    # Each entry defines one action (e.g., absorb, squeeze, challenge).
    interactions: List[Interaction]

This structure ensures:
* All `BEGIN` and `END` pairs are properly matched (no dangling or mismatched sections).
* The sequence of operations follows logical and protocol-correct ordering.
* Nested or grouped sections respect type and hierarchy constraints.

This is the top-level specification object. It describes the shape and rules of a protocol transcript before any prover or verifier runs it.

### `TranscriptRecorder`

This component records interactions as they happen in real time. It lets you build up a `TranscriptPattern` dynamically from a live prover-verifier session.

from dataclasses import dataclass

@dataclass
class TranscriptRecorder:
    # The accumulated pattern of interactions recorded so far.
    pattern: TranscriptPattern

Key methods:
* `interact(interaction)` → records a new interaction step.
* `finalize()` → validates the full pattern (checking correct nesting, kinds, etc.) and seals it into a finalized `TranscriptPattern`.

In short, `TranscriptRecorder` is the builder. It creates a verified interaction pattern from a live session.

### `TranscriptPlayer`

This component replays a fixed interaction pattern and ensures that an execution strictly follows it.

from dataclasses import dataclass

@dataclass
class TranscriptPlayer:
    # The reference pattern to follow.
    pattern: TranscriptPattern

    # The current position in the pattern (tracking progress).
    position: int

Key methods:

* `interact(interaction)` → verifies that the next interaction matches the expected pattern step.
* `finalize()` → confirms that all steps in the pattern were consumed without leftovers.

In short, `TranscriptPlayer` is the checker. It enforces that a session execution exactly matches a known-good `TranscriptPattern`.

:::success

## `CanObserve` and `CanSample`

These two core interfaces define how the Fiat-Shamir transcript evolves:

* **`CanObserve`**: for *absorbing* values into the transcript (e.g., scalars, digests).
* **`CanSample`**: for *sampling* values (e.g., challenge scalars) deterministically from the transcript state.

This abstraction allows the protocol to remain agnostic to the underlying cryptographic construction (e.g., Keccak, Poseidon, multi-field algebra), while enforcing consistency and correctness.

### `CanObserve`

from abc import ABC, abstractmethod
from typing import Generic, TypeVar, Sequence

T = TypeVar("T")  # Type of values absorbed into the transcript

class CanObserve(ABC, Generic[T]):
    """
    Interface for absorbing elements into a Fiat-Shamir transcript.

    Observed values are added to the internal sponge state,
    which affects future challenge generation.
    """

    @abstractmethod
    def observe(self, value: T) -> None:
        """
        Absorb a single value into the transcript.
        """
        pass

    def observe_slice(self, values: Sequence[T]) -> None:
        """
        Absorb a sequence of values into the transcript.

        Default implementation calls `observe` on each item.
        """
        for value in values:
            self.observe(value)

### `CanSample`

from abc import ABC, abstractmethod
from typing import Generic, TypeVar, List
import random

T = TypeVar("T")  # Type of challenge values sampled from the transcript

class CanSample(ABC, Generic[T]):
    """
    Interface for sampling challenge values from a Fiat-Shamir transcript.

    Sampled values must be deterministically derived from previously
    observed inputs and the internal sponge state.
    """

    @abstractmethod
    def sample(self) -> T:
        """
        Sample a single challenge value from the transcript.
        """
        pass

    def sample_array(self, n: int) -> List[T]:
        """
        Sample an array of `n` challenge values.
        """
        return [self.sample() for _ in range(n)]

### Key points

* `CanObserve` and `CanSample` cleanly separate the transcript into:
* input absorption (`observe`)
* challenge derivation (`sample`)
:::

## `ChallengerWithInstructions`

This component wraps a duplex sponge and directly uses the `TranscriptPattern` to enforce the secure sequence of observe, sample, and hint operations.

It serves as a stateful executor:
* ensuring each cryptographic sponge call matches the next expected `Interaction` from the pattern,
* preventing protocol misuse, skipped steps, or transcript mismatches,
* and securely zeroizing state on exit.

from dataclasses import dataclass, field
from typing import TypeVar, Generic

T = TypeVar("T")  # Type of values in the transcript (e.g., Scalar, byte)
C = TypeVar("C", bound="CanObserve[T] & CanSample[T]")  # Challenger type

@dataclass
class ChallengerWithInstructions(Generic[H]):
    # The underlying challenger.
    challenger: C

    # Transcript player that enforces the pattern sequence.
    stack: TranscriptPlayer

    # Phantom marker for value type; no runtime data.
    _type: T = field(default_factory=lambda: None)

### Operation enforcement

At each step:

* `observe(...)` → is used to record transcript data, and expects the next `Interaction.kind` to be `MESSAGE` or `HINT`.
* `sample(...)` → is used to derive challenges, and expects the next `Interaction.kind` to be `CHALLENGE`.
* `hint()` → is used to record a hint marker, and expects the next `Interaction.kind` to be `HINT`.

If the `InteractionKind` mismatches, or the `Length` mismatches, the system raises a protocol error and clears the stack to prevent unsafe or inconsistent transcript state.

### Supported operations

class ChallengerWithInstructions:
    def observe(self, input: List[T]) -> Result:
        """
        Observe input data into the transcript, advancing the interaction stack.

        Only allowed if the next Interaction is MESSAGE or HINT.
        Fails if the InteractionKind or Length mismatches.
        """
        ...

    def sample(self, count: int) -> Result[List[T]]:
        """
        Sample `count` challenge values from the transcript, advancing the interaction stack.

        Only allowed if the next Interaction is CHALLENGE.
        Fails if the InteractionKind or Length mismatches.
        """
        ...

    def hint(self) -> Result:
        """
        Register a hint marker, advancing the interaction stack.

        Only allowed if the next Interaction is HINT.
        """
        ...

### Construction from `TranscriptPattern`

class ChallengerWithInstructions:
    @classmethod
    def from_transcript(cls, pattern: TranscriptPattern) -> 'HashStateWithInstructions':
        """
        Creates a new hash state:
        - generates a deterministic tag,
        - seeds the sponge with the tag,
        - loads the pattern's interactions as a queue.
        """
        ...

This ensures:
- the hash state exactly mirrors the transcript pattern,
- no operations can be performed out of order,
- BEGIN/END blocks and atomic actions are fully respected.

## `ProverState`

The `ProverState` encapsulates the prover-side state during a Fiat-Shamir transformed interactive proof. It manages:
* the prover’s secret coins (private randomness),
* the public transcript state (used to derive verifier challenges),
* the connection to the underlying duplex sponge,
* and the consistent construction of the protocol’s byte-level transcript.

from dataclasses import dataclass, field
from typing import TypeVar, Generic, List

# Type of transcript elements (e.g., scalars, bytes)
T = TypeVar("T")  
# Challenger type
C = TypeVar("C", bound="CanObserve[T] & CanSample[T]")  

@dataclass
class ProverState(Generic[C, T]):
    # The internal challenger used for private randomness.
    challenger: C

    # The public transcript state, enforcing the interaction pattern.
    hash_state: ChallengerWithInstructions[C, T]

    # The byte-level transcript (prover’s message log).
    narg_string: List[T] = field(default_factory=list)

### Core operations

class ProverState:
    def add_bytes(self, input: List[U]) -> Result:
        """
        Absorb a batch of prover message bytes into both the public transcript and the private sponge.
        """
        ...

    def add_scalars(self, input: List[EF]) -> Result:
        """
        Serialize and absorb extension field scalars into the transcript.
        """
        ...

    def public_bytes(self, input: List[U]) -> Result:
        """
        Absorb public (non-binding) messages into the public transcript without affecting the prover log.
        """
        ...

    def hint(self, hint_obj: T) -> Result:
        """
        Serialize and absorb an auxiliary hint object into the prover transcript.
        """
        ...

    def challenge_bytes(self, N: int) -> Result[List[U]]:
        """
        Sample N Fiat-Shamir challenge bytes from the transcript state.
        """
        ...

    def challenge_scalars(self, N: int) -> Result[List[EF]]:
        """
        Sample N extension field scalars as Fiat-Shamir challenges.
        """
        ...

    def challenge_pow(self, bits: float, strategy: PowStrategy) -> Result:
        """
        Perform a Fiat-Shamir proof-of-work challenge and append the result to the transcript.
        """
        ...

### Construction

class ProverState:
    @classmethod
    def from_transcript(cls, pattern: TranscriptPattern) -> 'ProverState':
        """
        Create a new ProverState:
        - initialize public transcript from the pattern,
        - initialize private sponge seeded by the pattern tag,
        - start with an empty prover message log.
        """
        ...

This ensures the prover state is fully aligned with the declared transcript pattern, with no hidden or out-of-band inputs.

## `VerifierState`

The `VerifierState` encapsulates the verifier-side state in a Fiat-Shamir transformed interactive proof. It manages:
* the public transcript state (used to derive challenges and absorb prover data),
* the replay of prover-supplied data (from the NARG string),
* the enforcement of protocol consistency (via the transcript pattern),
* and the deserialization of structured hints and scalars.

This allows the verifier to:
- deterministically recompute challenges,
- read prover commitments and auxiliary data,
- enforce the declared interaction pattern,
- and validate all transcript operations without needing secret coins.

from dataclasses import dataclass, field
from typing import TypeVar, Generic, List

# Type of transcript elements
T = TypeVar("T")  
# Challenger type
C = TypeVar("C", bound="CanObserve[T] & CanSample[T]")  

@dataclass
class VerifierState(Generic[C, T]):
    # The public transcript state, enforcing Fiat-Shamir pattern.
    hash_state: ChallengerWithInstructions[C, T]

    # The raw prover-supplied data (the NARG string).
    narg_string: List[T]

    # Phantom type markers (no runtime data).
    _field: object = field(default_factory=lambda: None)
    _extension_field: object = field(default_factory=lambda: None)

### Key design points

#### Stateless verifier

- The verifier does not maintain private coins; it operates purely over public data.
- All randomness comes from the public sponge (`hash_state`) seeded by the declared domain separator.

This ensures that:
* prover and verifier can independently derive identical challenges,
* the verifier can enforce soundness without interactive randomness.

#### Replayable transcript

The `narg_string` is the prover-supplied serialized message log:
* It contains only prover-originating data (scalars, digests, hints, etc.).
* It is deserialized and verified in strict protocol order.
* It does not store verifier-side challenges (those are recomputed).

### Core operations

class VerifierState:
    def fill_next_bytes(self, output: List[U]) -> Result:
        """
        Read the next chunk of prover data from the NARG string and absorb it.
        """
        ...

    def next_bytes(self, N: int) -> Result[List[U]]:
        """
        Read a fixed-size block of prover data.
        """
        ...

    def fill_next_scalars(self, output: List[EF]) -> Result:
        """
        Deserialize the next extension scalars from the transcript.
        """
        ...

    def next_scalars(self, N: int) -> Result[List[EF]]:
        """
        Read a fixed-size block of extension scalars.
        """
        ...

    def challenge_bytes(self, N: int) -> Result[List[U]]:
        """
        Sample a fresh Fiat-Shamir challenge of N bytes.
        """
        ...

    def challenge_scalars(self, N: int) -> Result[List[EF]]:
        """
        Sample a fresh Fiat-Shamir challenge of N extension scalars.
        """
        ...

    def challenge_pow(self, bits: float, strategy: PowStrategy) -> Result:
        """
        Perform a proof-of-work challenge check on prover-supplied nonce.
        """
        ...

    def hint_bytes(self) -> Result[bytes]:
        """
        Read the next prover-supplied hint as raw bytes.
        """
        ...

    def hint(self, T) -> Result[T]:
        """
        Deserialize the next prover-supplied structured hint.
        """
        ...

    def public_bytes(self, input: List[U]) -> Result:
        """
        Absorb additional public data into the sponge.
        """
        ...

    def public_scalars(self, input: List[EF]) -> Result[bytes]:
        """
        Serialize and absorb public scalar values into the sponge.
        """
        ...

### Construction

class VerifierState:
    @classmethod
    def from_transcript(cls, pattern: TranscriptPattern, narg_string: bytes) -> 'VerifierState':
        """
        Create a new VerifierState:
        - initialize public transcript from the pattern,
        - preload the prover-supplied NARG string,
        - start with no mutable state.
        """
        ...

This guarantees that the verifier state perfectly mirrors the declared transcript pattern, with no deviations or hidden dependencies.