Fiat-Shamir Heuristic

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 20 October 2024.¶

Copyright Notice

Copyright (c) 2024 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

We show how to perform Fiat-Shamir on any public-coin protocol, providing randomness for the prover and secure generation of random coins for the verifier. Informally, a non-interactive zero-knowledge proof constructed via the Fiat-Shamir heuristic, the verifier (random oracle) is replaced with a duplex sponge. Messages from the prover are treated as Absorb calls, while challenges are treated as Squeeze calls. We will see this in detail below. Core features are:¶

• Support custom hash function, including algebraic hashes in a unified generic way.¶

• Retro-compatibility with the NIST API.¶

• Efficiency: minimizing the number of hash invocations while maintaining security, and (whenever possible) preprocessing information that is public or carried across protocols.¶

• Private randomness generation.¶

• The API makes it impossible to provide two different challenges for the same prover message. The prover's zk randomness is bound to the protocol transcript, without making the proof deterministic.¶

2. Ciphersuites

Different hash functions may rely on different constants. We define some of the parameters associated to the hash function that will be used throughout this spec.¶

DOMSEP

Domain separator for this standard. Fixed to zkpstd/0.1¶

3. IO Pattern

An IO pattern is a utf8-encoded string that specifies the protocol in a simple, non-ambiguous, human-readable format. A typical example is the following:¶

domain-separator A32generator A32public-key R A32commitment S32challenge A32response

The domain-separator is a user-specified string uniquely identifying the end-user application (to avoid cross-protocol attacks).¶

The letter A indicates the absorption of a public input (an Absorb), while the letter S indicates the squeezing (a Squeeze) of a challenge. The letter R indicates a ratcheting operation: ratcheting means invoking the hash function even on an incomplete block. It provides forward secrecy and allows it to start from a clean rate.¶

After the operation type, is the number of elements in base 10 that are being absorbed/squeezed.¶

Then, follows the label associated with the element being absorbed/squeezed. This often comes from the underlying description of the protocol. The label cannot start with a digit or contain the NULL byte.¶

Each operation is separated by the NULL byte.¶

The IO pattern string can be parsed as a queue of the form (Operation, Length), where consecutive Operations must be merged into one adding the length, and the length of ratchet operations is conventionally set to 0. The IO pattern above translated to the queue:¶

(A, 64) (R, 0) (A, 32) (S, 32) (A, 32)

4. Duplex Hash

In addition to the IO pattern, the protocol must also designate a hash function.¶

We focus here on permutation functions, but already dispose of a generic bridging interface for the NIST API that we omit for now here. Fix a permutation function P (a valid choice here is keccak-f[1600]) acting on on R+C elements (called native elements), where R is called rate (for keccak-f[1600] this would be R=136), and C is the capacity (for keccak-f[1600] this would be C=64).¶

More specifically, we build a duplex sponge in overwrite mode placing the rate in the least significant indices. Note that this definition is generic over bytes or arbitrary fields and that the definition below is tail-recursive, and State is a mutable reference to the hash state.¶

START(IV) -> State

State = [0; C + R]
for i = R .. R+C: State[i] = IV[i]
squeeze_pos=absorb_pos=0

-¶

Absorb(State, Input[])

If Input is empty, set squeeze_pos=R
If absorb_pos==R, let State=P(state); set absorb_pos=0 and run Absorb(State, Input[]).
Else, State[absorb_pos]=Input[0]; absorb_pos+=1, recursively run
Absorb(State, Input[1..]).

-¶

Squeeze(State, Output[])

If squeeze_pos==R, let State=P(State); set absorb_pos=0 and run Squeeze(State, Output[]).
Else, Output[0]=State[squeeze_pos]; squeeze_pos+=1, recursively run Squeeze(State, Output[1..])

-¶

RATCHET(State)

Permute the state: State = P(State); zero the rate part of the state
State[..R] = 0, set the counters squeeze_pos=absorb_pos=0.

-¶

FINISH(State)

Safely delete State

START(IO, Transcript) -> State
Store the IO Pattern as a queue.
Hash the IO pattern IO into 32 bytes ( `Absorb` and `Squeeze`); use the
result to initialize a duplex hash State.

READ(State, N) -> Input[N]
Read the Transcript deserializing N elements until Input[] is filled.
Absorb Input[]into the duplex hash.
Pop (or decrease) the head of the queue, throwing an error if
Operation is not `A` or Length\<0.

Squeeze(State, N) -> Output[N]
Squeeze Output[] elements from the duplex hash and return them
Pop (or decrease) the head of the queue, throwing an error if
Operation is not `S` or Length\<0.

RATCHET(State)
Invoke ratchet from the duplex hash and clear any additional state.
Pop the head of the queue, throwing an error if Operation is not R.

FINISH(State)
Throw an error if the queue is not empty or Transcript is not fully read.
Delete the state.

5. Serialization and conversion of Elements

The above API only covers actions over native elements. Oftentimes, we want to send more complex structures. Note that it's important the encoding size of the elements is fixed and can be statically determined.¶

In the case of integers mod N to be encoded as bytes, the element is seen as an integer between 0 and N-1 encoded in big endian. Elliptic curve elements are encoded serializing the x coordinate with two bits to encode whether y is positive, negative, or infinity.¶

When squeezing bits from native elements mod N, the lowest L bits are guaranteed to be indistinguishable from uniformly random if¶

L + 1 + N.bit_length() - (alpha := N % 2 ** n).bit_length() -(2 ** N - alpha).bit_length() >= 128

We require a potential function Squeeze_BITS to return the above number of bits and discard the remaining elements of the native squeezed elements.¶

6. Additional Material

Reference implementation (with examples), Proofs of security.¶

Author's Address