Fiat-Shamir Transformation

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 30 December 2025.¶

Copyright Notice

Copyright (c) 2025 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

The Fiat-Shamir transformation is a technique that uses a hash function to convert a public-coin interactive protocol between a prover and a verifier into a corresponding non-interactive protocol.¶

We specify a variant of the Fiat-Shamir transformation, where the hash-function is obtained from a duplex sponge.¶

A duplex sponge is a stateful hash object that can absorb inputs incrementally and squeeze variable-length unpredictable messages. The duplex sponge is defined over a base alphabet (typically bytes) which might not match the domain over which the prover and verifier messages are defined.¶

A codec is a stateful object that can absorb inputs incrementally and squeeze unpredictable challenges. A codec is compatible with a given interactive protocol if the domain of the inputs that the codec can absorb matches the domain of the prover messages and the challenges matches the domain of the verifier messages of the specified protocol. Internally, a codec uses a duplex sponge and performs the appropriate conversion.¶

The Fiat-Shamir transformation combines the following ingredients to construct a non-interactive protocol:¶

• An initialization vector (IV) uniquely identifying the protocol.¶

• A interactive protocol.¶

• A codec compatible with the interactive protocol.¶

2. The Duplex Sponge Interface

A duplex sponge operates over an abstract Unit type and provides the following interface.¶

class DuplexSponge:
  def new(iv: bytes) -> DuplexSponge
  def absorb(self, x: list[Unit])
  def squeeze(self, length: int) -> list[Unit]

Where:¶

• The type Unit MUST have fixed size in memory, partial ordering, and at least two elements.¶

• init(iv: bytes) -> DuplexSponge denotes the initialization function. This function takes as input a 32-byte initialization vector iv and initializes the state of the duplex sponge.¶

• absorb(self, values: list[Unit]) denotes the absorb operation of the sponge. This function takes as input a list of Unit elements and mutates the DuplexSponge internal state;¶

• squeeze(self, length: int) denotes the squeeze operation of the sponge. This function takes as input a integral length and squeezes a list of Unit elements of length length.¶

3. The Codec interface

A codec provides the following interface.¶

class Codec:
    def new(iv: bytes) -> Codec
    def prover_message(self, prover_message)
    def verifier_challenge(self) -> verifier_challenge

Where:¶

• init(iv: bytes) -> DuplexSponge denotes the initialization function. This function takes as input a 32-byte initialization vector iv and initializes the state of the codec.¶

• prover_message(self, prover_message) -> self denotes the absorb operation of the codec. This function takes as input a prover message prover_message and mutates the codec's internal state.¶

• verifier_challenge(self) -> verifier_challenge denotes the squeeze operation of the codec. This function takes no inputs and uses the codec's internal state to produce an unpredictable verifier challenge verifier_challenge.¶

4. Fiat-Shamir transformation for Sigma Protocols

We describe how to construct non-interactive proofs for sigma protocols. The Fiat-Shamir transformation is parametrized by:¶

• a Codec, which specifies how to absorb prover messages and how to squeeze verifier challenges;¶

• a SigmaProtocol, which specifies an interactive 3-message protocol.¶

Upon initialization, the protocol receives as input an iv of 32-bytes which uniquely identifies the protocol and the session being proven and (optionally) pre-processes some information about the protocol using the instance.¶

class NISigmaProtocol:
    Protocol: SigmaProtocol
    Codec: Codec

    def init(self, iv: bytes, instance):
        self.hash_state = self.Codec(iv)
        self.ip = self.Protocol(instance)

    def prove(self, witness, rng):
        (prover_state, commitment) = self.ip.prover_commit(witness, rng)
        challenge = self.hash_state.prover_message(commitment).verifier_challenge()
        response = self.ip.prover_response(prover_state, challenge)

        assert self.ip.verifier(commitment, challenge, response)
        return self.ip.serialize_commitment(commitment) + self.ip.serialize_response(response)

    def verify(self, proof):
        commitment_bytes = proof[:self.ip.instance.commit_bytes_len]
        response_bytes = proof[self.ip.instance.commit_bytes_len:]
        commitment = self.ip.deserialize_commitment(commitment_bytes)
        response = self.ip.deserialize_response(response_bytes)
        challenge = self.hash_state.prover_message(commitment).verifier_challenge()
        return self.ip.verifier(commitment, challenge, response)

class LinearMapCodec:
    Group: groups.Group = None
    DuplexSponge: DuplexSpongeInterface = None

    def init(self, iv: bytes):
        self.hash_state = self.DuplexSponge(iv)

    def prover_message(self, elements: list):
        self.hash_state.absorb(self.Group.serialize(elements))
        # calls can be chained
        return self

    def verifier_challenge(self):
        uniform_bytes = self.hash_state.squeeze(
            self.Group.ScalarField.scalar_byte_length() + 16
        )
        scalar = OS2IP(uniform_bytes) % self.Group.ScalarField.order
        return scalar

5. Ciphersuites

new(self, iv)

Inputs:

- iv, a byte array

Outputs:

-  a hash state interface

1. h = shake_128(iv)
2. return h

absorb(hash_state, x)

Inputs:

- hash_state, a hash state
- x, a byte array

1. h.update(x)

squeeze(hash_state, length)

Inputs:

- hash_state, the hash state
- length, the number of elements to be squeezed

1. h.copy().digest(length)

new(iv)

Inputs:
- iv, a 32-byte initialization vector

Procedure:
1. self.absorb_index = 0
2. self.squeeze_index = self.permutation_state.R
3. self.rate = self.permutation_state.R
4. self.capacity = self.permutation_state.N - self.permutation_state.R

absorb(self, input)

Inputs:
- self, the current duplex sponge object
- input, the input bytes to be absorbed

Procedure:
1. self.squeeze_index = self.rate
2. while len(input) != 0:
3.     if self.absorb_index == self.rate:
4.         self.permutation_state.permute()
5.         self.absorb_index = 0
6.     chunk_size = min(self.rate - self.absorb_index, len(input))
7.     next_chunk = input[:chunk_size]
8.     self.permutation_state[self.absorb_index:self.absorb_index + chunk_size] = next_chunk
9.     self.absorb_index += chunk_size
10.    input = input[chunk_size:]

squeeze(self, length)

Inputs:
- self, the current duplex sponge object
- length, the number of bytes to be squeezed out of the sponge

Outputs:
- digest, a byte array of `length` elements uniformly distributed

Procedure:
1. output = b''
2. while length != 0:
3.     if self.squeeze_index == self.rate:
4.         self.permutation_state.permute()
5.         self.squeeze_index = 0
6.         self.absorb_index = 0
7.     chunk_size = min(self.rate - self.squeeze_index, length)
8.     output += bytes(self.permutation_state[self.squeeze_index:self.squeeze_index+chunk_size])
9.     self.squeeze_index += chunk_size
10.    length -= chunk_size
11. return output

6. Codecs registry

absorb_scalars(hash_state, scalars)

Inputs:

- hash_state, the hash state
- scalars, a list of elements of the elliptic curve's scalar field

Constants:

- scalar_byte_length = ceil(384/8)

1. for scalar in scalars:
2.     hash_state.absorb(scalar_to_bytes(scalar))

absorb_elements(hash_state, elements)

Inputs:

- hash_state, the hash state
- elements, a list of group elements

1. for element in elements:
2.     hash_state.absorb(ecpoint_to_bytes(element))

squeeze_scalars(hash_state, length)

Inputs:

- hash_state, the hash state
- length, an unsiged integer of 64 bits determining the output length.

1. for i in range(length):
2.     scalar_bytes = hash_state.squeeze(field_bytes_length + 16)
3.     scalars.append(bytes_to_scalar_mod_order(scalar_bytes))

7. Generation of the initialization vector

As of now, it is responsibility of the user to pick a unique initialization vector that identifies the proof system and the session being used. This will be expanded in future versions of this specification.¶

8. References

Authors' Addresses