sigma.tex

\documentclass[11pt]{article}
\usepackage{fullpage}
\newif\ifanonymous
\anonymousfalse
\usepackage[T1]{fontenc}
\usepackage{tgbonum}

\usepackage{adjustbox}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{authblk}
\usepackage[advantage,
            adversary,
            asymptotics,
            complexity,
            ff,
            lambda,
            mm,
            operators,
            primitives,
            probability,
            sets]{cryptocode}
\usepackage{enumitem}
\usepackage{mathtools}
\usepackage{todonotes}
\usepackage{csquotes}
\usepackage[most]{tcolorbox}
\usepackage[binary-units]{siunitx}
\tcbuselibrary{theorems}

\usepackage[%dvips,
    pdftex,
    pdftitle={Proposal: Sigma-protocols},
    pdfauthor={Stephan Krenn and Michele Orrù}, pdfpagelabels=true, %linktocpage=true,     backref=page,
    bookmarks,bookmarksopen,bookmarksdepth=3,
    breaklinks,colorlinks,citecolor=blue,linkcolor=blue,urlcolor=blue
   ]{hyperref}
\usepackage[capitalize,nameinlink,sort]{cleveref}
\crefformat{equation}{(#2#1#3)}

\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{pifont}

\input{macros}

\usepackage{fancyhdr}
\usepackage[left=2.55cm,right=2.55cm,top=2.25cm,bottom=3.35cm,headheight=20pt,headsep=10pt]{geometry}
\newcommand{\version}{{v 0.2}}
\fancypagestyle{plain}{
  \fancyhf{}% Clear header/footer
  \fancyhead[R]{\includegraphics[height=0.75cm]{assets/img/zkproof.png}}% Right header
	\fancyhead[L]{\leftmark\\[-0.6em]}
  \fancyfoot[L]{\documentTitle\ \version}% Left footer
  \fancyfoot[R]{\thepage}% Right footer
}
\headheight 40pt              %% put this outside
\headsep 10pt                 %% put this outside


\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}

\newtcbtheorem[auto counter, %number within = section,
  crefname={remark}{remarks},
  Crefname={Remark}{Remarks}]{remark}{Remark}{
    breakable,
		colback=green!5,
    colframe=green!35!black,
    fonttitle=\bfseries}{rem} %cite as \cref{rem:<label>}

\newtcbtheorem[auto counter, % use counter from=remark,
  crefname={warning}{warnings},
  Crefname={Warning}{Warnings}]{warning}{Warning}{
    breakable,
		colback=red!25,
    colframe=red!70!black,
    fonttitle=\bfseries}{war} %cite as \cref{war:<label>}

\newtcbtheorem[auto counter, % use counter from=remark,
  crefname={ex}{ex},
  Crefname={Example}{Examples}]{example}{Example}{
    breakable,
    colback=blue!5,
    colframe=blue!35!black,
    fonttitle=\bfseries}{exa} %cite as \cref{exa:<label>}


\newcommand{\documentTitle}{A Spec for $\Sigma$-Protocols}

\begin{document}
% =========== TITLE PAGE ===========

\pagenumbering{roman}
\begin{titlepage}
   \begin{center}
       \vspace*{1cm}
       \textbf{\Huge{\documentTitle}}

       \vspace{2.0cm}
       \textbf{Authors: Michele Orrù, Stephan Krenn}

       \vspace{1.0cm}
			 \textbf{Contributors:}\\[1em]
       \begin{tabular}{c@{\hspace{5em}}c@{\hspace{5em}}c}
        Jan Bobolz & Mary Maller & Ivan Visconti \\[.3em]
        Yuwen  Zhang \\
       \end{tabular}
       \vfill
       Version: \version\\
       \vspace{0.5cm}
       Date: \today\\
       \vspace{1.3cm}
       \includegraphics[width=0.4\textwidth]{assets/img/zkproof.png}
   \end{center}
\end{titlepage}
\pagestyle{plain}% Set page style to plain.

% =========== TABLE OF CONTENTS ===========

{
  \hypersetup{hidelinks}
  \tableofcontents
}
\vfill
\begin{center}
  \includegraphics[width=.9\textwidth]{assets/img/Dinner_Party.png}
\end{center}

\clearpage
\pagenumbering{arabic}
\setcounter{page}{1}

% =========== CONTENT ===========


\section{Introduction}

Zero-knowledge~\cite{GolMicRac89} proofs of knowledge~\cite{C:BelGol92} allow a prover to convince a verifier that he knows a secret piece of information, without revealing anything except what the claim itself already reveals.
Many practically relevant proof goals can be realized using so-called $\Sigma$-protocols.
%, or their non-interactive counterparts, which can be proven secure in the random oracle model. %without the need for a common reference string.
Introduced by Schnorr~\cite{JC:Schnorr91} over 30 years ago, they play an essential component in the building of a number of cryptographic
constructions,
such as anonymous credentials~\cite{CCS:ChaMeiZav14}, password-authenticated key exchange~\cite{jpake}, signatures~\cite{C:Schnorr89},
ring signatures~\cite{borromeansig}, blind signatures~\cite{CCS:PoiSte97}, multi signatures~\cite{CCS:NRSW20}, threshold signatures~\cite{EPRINT:KomGol20} and more. This spec provides guidelines for correctly implementing $\Sigma$-protocols.

\subsection{Notation}
\label{sec:notation}

For the purpose of this document, the following notation will be used:

\begin{tabular}{r@{\hspace{1em}}p{11cm}}
    $\secpar$ & main security parameter\\
    $\CS$ & challenge set. A challenge is a vector of 32 bytes (octets).\\
    $\statement$ & the statement, i.e., the public information in a zero-knowledge proof \\
    $\witness$ & the witness, i.e., the secret information in a zero-knowledge proof \\
    $\commitment$ & the first message, called commitment \\
    $\challenge$ & the second message, called challenge \\
    $\response$ & the third message, called response \\
    $x \defeq 1$ & assignment of the value 1 to $x$\\
    $x\sample\someset$ & assignment of a uniformly random element in $\someset$ to $x$\\
    $x\gets\alg(in)$ & assign to $x$ the output of the randomized procedure on input $in$\\
    $\relation$ & binary relation\\
    $|y|$ & bit-length of a string \\
    $\oplus$ & binary operator denoting the bitwise XOR of two strings of equal length
%    $\NN,\ZZ$ & non-negative natural numbers and integers, respectively
\end{tabular}

Additional notation will be introduced when describing specific algebraic objects.
\subsection{Terminology}
Given sets $\Set{Y}$ and $\Set{W}$,
a \emph{binary relation} $\relation \subseteq \Set{Y} \times \Set{W}$ associates elements from $\Set{Y}$ with elements from $\Set{W}$.
For $(\statement,\witness)\in\relation$, we refer to $\statement$ as a \emph{statement}, and to $\witness$ as a \emph{witness} (for $\statement$).
The statement is public information shared between prover and verifier.
The witness is secret information solely known by the prover.
Note there may be multiple witnesses for a given $\statement$.

\begin{example}{Discrete logarithm equality}{R_DLEQ}
  Let $\GG$ be a cyclic group of prime order $p$, and let $G$ and $H$ be generators of $\GG$.
	Then the following relation $\relation[dleq]$ contains as statements all pairs of elements having the same discrete logarithm with respect to $G$ and $H$, with the corresponding witness being their discrete logarithm:
  \[
	  \relation[dleq] = \set{\left((\statement_1,\statement_2),\witness\right) \in \GG^2\times \FF_p~:~\statement_1=\witness G ~\land~ \statement_2=\witness H}\,.
	\]
\end{example}

\begin{example}{Representation}{R_REP}
  Let $\GG$ be a cyclic group of prime order $p$, and let $G$ and $H$ be generators of $\GG$.
	Then the following relation $\relation[rep]$ contains as statements all valid Perdersen commitments, with the corresponding witnesses being their openings:
  \[
	  \relation[rep] = \set{\left(\statement,(\witness_1,\witness_2)\right)\in \GG \times \FF_p^2~:~\statement=\witness_1G + \witness_2H}\,.
	\]
	Note that in this case, each statement has $p$ valid witnesses.
\end{example}

In a zero-knowledge proof, the \emph{witness} is secret information, while the \emph{statement} is public.
A \emph{proof} is a sequence of bytes\footnote{Throughout this work, a byte is defined as a vector of 8 bits.} attesting that a witness is in some relation with the statement.

Proofs described in this spec are zero-knowledge and sound.
Zero knowledge means that the protocol does not leak any information about the prover's witness beyond what the attacker may infer from the proven statement or from other sources~\cite[1.6.4]{zkproof-reference}.
Soundness means that it is not possible to make the verifier accept for statements for which no valid witness exists~\cite[1.6.2]{zkproof-reference}.

In particular we will focus on non-malleable extractable proofs, that is, proofs where the witness does not only exist but is also precisely known by the prover.
These protocols are also known as proofs of knowledge~\cite{STOC:GolMicRac85,STOC:FeiFiaSha87,C:BelGol92} and are said to satisfy \emph{knowledge soundness}~\cite{damgard04}. Non-malleability means that, in addition, the proof is secure against man-in-the middle attacks, and attackers cannot produce a new valid proof by tampering
another valid proof.

\subsection{Guarantees}
\minote{\underline{Question for the community}: Should we require implementations to be constant-time? It is not immediate to build OR composition in constant-time. It is possible to double the cost and run prover and simulator for each branch, but at the end we still need the ternary operator to select the correct transcript. This is the only place where we are incurring in non non-constant-time operations (assuming the algebraic operations are already solved). All other algorithms are constant-time.}
\minote{\underline{Question for the community}: Who is the recipient of this standard? Are they meant to know already what extraction, or simulation means? Should we employ terms like \emph{simulation-extractability} or \emph{non-malleability} (the latter being different from the former and more imprecise, yet also more self-explainatory). Side-note: OR-composition is not simulation-extractable.}
\subsection{Scope of this document}

This document provides guidelines for secure implementations of $\Sigma$-protocols and is addressed to applied cryptographers and cryptographic engineers that are looking to implement a generic
$\Sigma$-protocol or provide an ad-hoc instantiation as part of a larger protocol.

We consider the problem of having a high-quality
entropy source well-suited for crypto\-graphic purposes outside of the scope of this document.
We will not talk about implementation of cryptographic primitives such as hash functions, or elliptic-curve algebra, but we will provide references for where to find them.
We won't provide any guidance for securely storing secrets or producing constant-time code.

% \minote{People interested in the development of a specific $\Sigma$ protocol should implement the template from 2 using the algorithm from XX and XX and then refer to section XX}

\begin{figure}[t]
  \begin{tcolorbox}
    \centering
      ~\textbf{Prover} \hfill \textbf{Verifier}~ \\[1em]
      \tcblower
      \tcbox[title=Inputs, halign title=flush center]{
        \begin{tabular*}{.92\textwidth}{l@{\extracolsep{\fill}}r}
          \textbf{statement}~(\statement), & \textbf{statement}~(\statement), \\
          \textbf{context}~(\ctx), & \textbf{context}~(\ctx),\\
          \underline{\textbf{witness}}~(\witness) &
        \end{tabular*}
      }
      \tcbox[title=Protocol flow, halign title=flush center]{
        \procedure{}{
           \textbf{commitment}~(\commitment)~~~~~~~~ \< \sendmessageright*[19.5em]{\commitment} \< \\
    \< \sendmessageleft*[19.5em]{\challenge}  \< ~~~\textbf{challenge}~(\challenge)\\
    \textbf{response}~(\response)~~~~~~ \< \sendmessageright*[19.5em]{\response}\\
        }
      }
      \begin{center}\tcbox{\textbf{transcript}: $(\commitment, \challenge, \response)$}\end{center}
  \end{tcolorbox}
  \caption{Overview of the steps composing a generic $\Sigma$-protocol. Underlined, the secrets in the protocol. In practice, the challenge is computed deterministically and the protocol is non-interactive. See \cref{sec:fs} for more information.}
\end{figure}

\section{Generic $\Sigma$-Protocols}
In the following, we describe a generic interface for $\Sigma$-protocols.
Such protocols can be used to prove that, for some binary relation $\relation$ and a public value $\statement$, a witness $\witness$ such that $(\statement,\witness)\in\relation$ is known.
Basic statements include proofs of knowledge of a secret key, openings of commitments and, more generically, of representations.
The type of these elements depends on the specific relation being implemented.

An important property of $\Sigma$-protocols is that they are composable: it is possible to prove conjunction and disjunctions of statements in zero-knowledge.
Composition of $\Sigma$-protocols is dealt in \cref{sec:composition}; for an in-depth discussion of the underlying theory we refer to Cramer~\cite{cramer97}.

% \minote{nitpick: the interacive or is not zk?}


\subsection{Overview}
Any $\Sigma$-protocol is structured as follows:
\begin{itemize}
  \item the prover computes a fresh \textbf{commitment}, denoted $\commitment$. This element is sometimes also called \emph{nonce}.
  \item the verifier computes, using the so-called Fiat-Shamir transform (cf.~\cref{sec:fs}), a random \textbf{challenge}, denoted $\challenge$.
  \item the prover computes a \textbf{response}, denoted $\response$, that depends on the commitment and the challenge.
\end{itemize}
The final proof is constituted of the three-elements above $(\commitment, \challenge, \response)$, and is also referred to as the \textbf{transcript}.


\subsection{An abstract class for generic $\Sigma$-protocols}
We define a template class for $\Sigma$-protocols denoted $\sigmaprotocol$. This is the basic interface that will be implemented in the remainder of this document.
The methods composing $\sigmaprotocol$ should be considered \emph{private} and \emph{should not} be exposed externally. The public API is described later in \cref{sec:fs}.
Instances are created via the $\new$ function, which is a class method, while all other functions act on a particular instance.
A $\sigmaprotocol$ consists of the following methods:
      \begin{itemize}
        \item $\sigmaprotocol.\new(\ctx, \statement)$,
        denoting the initialization function. This function takes as input a label identifying local context information $\ctx$ (such as: session identifiers, to avoid replay attacks; protocol metadata, to avoid hijacking; optionally, a timestamp and some pre-shared randomness, to guarantee freshness of the proof) and a statement $\statement$,  the public information shared between prover and verifier.
        This function \emph{should} pre-compute parts of the statement, or initialize the state of the hash function.
        \item
          $(\commitment, \proverstatett)\gets \sigmaprotocol.\provercommitment(\witness)$,
          denoting the \emph{commitment phase}, that is, the computation of the first message sent by the prover in a $\Sigma$-protocol. This method outputs a new commitment together with its associated prover state, depending on the witness known to the prover and the statement to be proven.
          This step generally requires access to a high-quality entropy source.
          Leakage of even just of a few bits of the nonce could allow for the complete recovery of the witness~\cite{lattice-attack,bleichenbacher,CCS:ANTTY20}.
					The value $\commitment$ is meant to be shared, while $\proverstatett$ must be kept secret.

          In particular, we assume that there exists a function $\serialize(\commitment)$ that serializes the commitment $\commitment$ and that its size is fixed and implicitly determined by the statement $\statement$.

        \item
          $\response \gets \sigmaprotocol.\proverresponse(\proverstatett, \challenge)$,
          denoting the \emph{response phase}, that is, the computation of the second message sent by the prover, depending on the witness, the statement, the challenge received from the verifier, and the internal state generated by $\provercommitment$.
          The value $\response$ is meant to be shared.
        \item $\texttt{yesno} \gets \sigmaprotocol.\verifiertt(\commitment, \challenge, \response)$,
          denoting the \emph{verifier algorithm}. This method checks that
          the \emph{protocol transcript} is valid for the given statement.
          The verifier algorithm outputs nothing if verification succeeds,
          or an error if verification fails.
          \item $\texttt{label} \gets\sigmaprotocol.\labeltt()$,
          returning a string of $\seedlen$ uniquely identifying the relation being proven.
          Implementing this function correctly is vital for security, and it must include all data available in the statement, as well as the parameters and the relation being proven. The label will be used for computing the challenge in the Fiat-Shamir transform (see ~\cref{sec:fs}).
          Precise indications on how to implement this function will be given in the following sections (see e.g.\ \cref{sec:and-comp,sec:instantiations}).

          If the label is \emph{not} tied to the relation, then it may be possible to produce another proof for a different relation without knowing its witness.
          Similarly, if the statement is not tied to the label, then it may be possible to produce proofs for another statement whose witness is related to the original proof.
      \end{itemize}
      The final two algorithms describe the \emph{zero-knowledge simulator}.
      The simulator is primarily an efficient algorithm for proving zero-knowledge in a theoretical construction~\cite{becafi19}, but it is also needed for verifying short proofs (cf.~\cref{sec:shortproof}) and for or-composition (cf.~\cref{sec:or-comp}), where a witness is not known and thus has to be simulated. We have:
      \begin{itemize}
        \item $\response \gets \sigmaprotocol.\simresponsett()$,
        denoting the first stage of the \emph{simulator}. It is an algorithm drawing a random response that follows the same output distribution of the algorithm $\proverresponse$.
        \item $\commitment \gets \sigmaprotocol.\simcommitmenttt(\challenge, \response)$, denoting the second stage of the \emph{simulator}, returning a commitment that follows the same output distribution of the algorithm $\provercommitment$.
      \end{itemize}

\subsection{The Fiat-Shamir Transform}\label{sec:fs}

The interactive versions of the $\Sigma$-protocols presented in this document are not fit for practical applications, due to subtle yet impactful details in their security guarantees.
In practice, public-coin protocols such as $\Sigma$-protocols can be converted into non-interactive ones through the
Fiat and Shamir heuristic~\cite{C:FiaSha86} and subsequent work, e.g., by Bernhard, Pereira and Warinschi~\cite{AC:BerPerWar12}.

The underlying idea is to replace the verifier with a cryptographically secure hash function, hashing the context from the protocol and the previous message sent by the prover.

\begin{warning}{Interactive $\Sigma$-protocols}{} $\Sigma$-protocols illustrated in this spec \textbf{must not} be used interactively.
\end{warning}

\subsubsection{Syntax}

When using a hash function we will employ comma-separated values to indicate values that are concatenated.
To mitigate attacks and allow for state cloning, we also separate values with a vertical bar
to indicate that they must appear in a subsequent block and that the previous is padded with zeros. For instance, $\hash(a \concat b \concatblock c)$ denotes the hash of $a$ concatenated to $b$, then padded with the null byte until reaching the closest multiple of $\blocklen$, and finally concatenating the resulting bit string to $c$.

\minote{\underline{Question for the community}: how should padding be implemented? \texttt{10*1} used in sha3 would be straightforward but perhaps just filling with zeros is simpler and sufficient for our use-case?}

\paragraph{Constants.} 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.

\begin{center}
\begin{tabular}{cl}
  Const name & Notes \\
  \hline
  $\domsep$ & Domain separator for this standard. Fixed to $\domsepctx$.   \\
  % $\ctx$ & Application name, as provided by the application layer. \\
  $\blocklen$ & Length of a hash block \\
  $\digestlen$ & Digest length
\end{tabular}
\end{center}
\minote{\underline{Question for the community}: this spec assumes that the hash function takes as input a bit-string and returns a bit-string. This is however not the case for all hash functions that we would like to support. For instance, Poseidon~\cite{EPRINT:GKKRRS19}'s core function is a map $\FF_p^* \to \FF_p^\ell$ with $\ell$ fixed.}

\subsubsection{Hash Registry}
\label{sec:hash-registry}

This is the set of all supported hash functions. They take an arbitrary length sequence of bytes as input, and output $\seedlen$ of entropy.

\begin{center}
  \begin{tabular}{lllcc}
  Hash  & Source & $\blocklen$ & $\digestlen$ \\
  \hline
  blake2b &  \cite{ACNS:ANWW13} & 128 & 64 \\
  sha3-256 & \cite{EC:BDPA13} & 136 & 32 \\
  % \unsure{Poseidon} &  \cite{EPRINT:GKKRRS19}\\
  \end{tabular}
\end{center}
Supported hash functions must all have $\blocklen \geq 32$. We define labels and constant strings so that their length is always at most $\seedlen$.
If $\digestlen \ge 32$, we implicitly assume that the implementation considers only the least significant bytes and discards the remainder of the hash output when exactly $\seedlen$ bytes are needed.
\subsubsection{Computing the challenge and seeding the commitment}
\label{sec:fs-challenge}

Relying on a hash function allows us to both compute the challenge and generate the commitment securely.
We define the following auxiliary variables that may be pre-computed during the call of $\sigmaprotocol.\new(\ctx, \statement)$. All variables will have fixed length $\digestlen$ so to avoid
canonicalization attacks.

\[
  \begin{aligned}
   & \hd \defeq \hash(\domsep) \\
   & \hstatement \defeq \sigmaprotocol.\labeltt() \\
   & \hctx \defeq \hash(\ctx)
  \end{aligned}
\]
\paragraph{Seeding the commitment.} The method $\sigmaprotocol.\provercommitment()$ is a randomized function that generates a random element, unique per each execution. The commitment \emph{should} be seeded as follows:
\[
    \begin{aligned}
     & \hz \defeq \randombytes(32) \\
    & \pcreturn  \hash(\hd \concat \hctx \concat \hstatement \concatblock \hz\concat \witness).
    \end{aligned}
    \]
If the output length $\digestlen$ of the hash function is not sufficient to provide enough entropy for the commitment, the seed may be expanded with a PRNG to provide the quantity of random bytes desired.
\minote{\underline{Question for the community}: This must be more formal. What are we expecting the PRNG to be? It seems a waste not to use variable-length hash output from from supported hash functions. Should we opt for replacing sha3 with shake? How is the implementor supposed to know what is \emph{enough entropy}? This could be misleading: there must be enough bytes to fill the domain of the morphism (which could be more than the security parameter!). Finally, the hash function used here may be different from the hash function to compute the challenge (this might make sense in the case of algebraic hashing). Should we support it?}
\paragraph{Computing the challenge.}
The method $\sigmaprotocol.\challengett(\msg, \commitment)$ is implemented as follows in order to produce a random challenge.

  \[
    \begin{aligned}
     & \hmsg \defeq \hash(\msg) \\
    & \pcreturn  \hash(\hd \concat \hctx \concat \hstatement \concatblock \hmsg \concatblock  \serialize(\commitment)).
    \end{aligned}
  \]

If no message is being set, i.e. if $\msg = \none$, then the implementation may decide to skip the computation of $\hmsg$ and consider it empty.
This method is fixed for all implementations of $\sigmaprotocol$. Note that the state of the hash function is partially shared between the commitment seed inputs and the challenge computation. Implementors may choose to store the partial hash state before generating the commitment, and reuse it when computing the challenge.

% commit = SHO(L1: HD,HA,HM,Z | a ^)
% challenge = SHO(L2: HD,HA,HM,commit ^)

% # D - Description
% # A = statement
% # a = witness for statement A, e.g. A=G^a
% # Z = randomness
% # M = message to be signed

% SCHNORR_1HASH (pre-hash style):
%   H = SHO(M ^)
%   commit    = SHO(L1; D,A,H > Z > a ^)
%   challenge = SHO(L2; D,A,H > commit ^)

% SCHNORR_2HASH (EdDSA style):
%   commit = SHO(L1; D,A > Z > a > M ^)
%   challenge = SHO(L2; D,A > commit > M ^)


\subsubsection{Non-interactive proofs}

We define two \emph{public methods} for generating proofs, meant to be exposed externally: $\shortproof$, and $\batchableproof$.
Since the challenge is computed deterministically from the commitment and the statement, it is not necessary to include the full transcript in a proof, as it can be deduced in the verification phase.

Short proofs are the most efficient if the protocol contains at least an \emph{AND} composition (see \cref{sec:and-comp} for a proper definition), and the gain in size is measured as $|\vec \commitment| - \digestlen$.
(Note: the length of the commitment is the length of the statement.)
Batchable proofs are the canonical forms of proofs.
Provers in the batchable form may raise an exception if the statement is not valid.
Proofs are seen as fixed-length bit strings, whose exact length can be inferred from the statement during initialization of the $\Sigma$-protocol.

\begin{remark}{Witness validation}{}
  In the following we assume correctness of the witness $\witness$ for the given statement $\statement$.
	This can be ensured, e.g., by a higher-level application, or by running $\sigmaprotocol.\verifiertt(\commitment, \challenge, \response)$ before sending the resulting proof.
\end{remark}

\subsubsection{Batchable Proofs}

\begin{description}
\item[Prover algorithm.]
The public function $\sigmaprotocol.\batchableproof( \witness, \msg)$ computes:
\begin{enumerate}
\item
   $(\commitment,\proverstatett)\gets\sigmaprotocol.\provercommitment( \witness)$.
\item
$c \gets \sigmaprotocol.\challengett(\msg,\commitment)$
\item
   $\response\gets\sigmaprotocol.\proverresponse(\proverstatett,  \challenge)$.
\item Return $\serialize(\commitment)$ concatenated to $\serialize(\vec \response)$
\end{enumerate}
The challenge $\challenge$ is not provided within a batchable proof since it can be re-computed from the commitment.
\item[Verifier algorithm.] The verifier's algorithm $\sigmaprotocol.\batchverifier(\pi, \msg)$ works as follows:
\begin{enumerate}
  \item $(\commitment,s) \defeq \deserialize(\pi)$
  \item
    $c \gets \sigmaprotocol.\challengett(\msg, \commitment)$
  \item
    Return the result of $\sigmaprotocol.\verifiertt(\commitment,\challenge, \response)$.
\end{enumerate}
\begin{warning}{Input validation}{}
The case of batched verification must include an input validation sub-routine that asserts the statement and commitments are in question.
In the case of elliptic curves described in~\Cref{sec:instantiations}, this boils down to point validation.
Failure to properly check that a commitment is in the group could lead to subgroup attacks~\cite{EC:VanWie96,C:LimLee97} or invalid curve attacks~\cite{C:BieMeyMul00,RSA:BBPV12}.
\end{warning}

\end{description}

\subsubsection{Short Proofs}\label{sec:shortproof}
\begin{description}
\item[Prover algorithm.]
A new proof $\sigmaprotocol.\shortproof(\witness, \msg)$ is built as follows:
\begin{enumerate}
  \item
     $(\commitment,\proverstatett)\gets\sigmaprotocol.\provercommitment(\witness)$.
  \item
   $c \gets \sigmaprotocol.\challengett(\msg,  \commitment)$
  \item
     $\vec \response\gets\sigmaprotocol.\proverresponse(\proverstatett,\challenge)$.
%    \item Check that the witness is valid. This can (for instance) be done running \[\sigmaprotocol.\verifiertt(\commitment, \challenge, \response)\]
  \item
  Return $\serialize(\challenge)$ concatenated to $\serialize(\response)$.
\end{enumerate}
The commitment $\commitment$ is not provided within a short proof since it can be calculated again.
\item[Verifier algorithm.] The verifier's algorithm $\sigmaprotocol.\shortverifier(\pi, \msg)$ works as follows:
\begin{enumerate}
  \item $(\challenge, \response) \defeq \deserialize(\pi)$
  \item $\commitment \gets \sigmaprotocol.\simcommitmenttt(\challenge, \response)\,.$
  \item $c^* \gets \sigmaprotocol.\challengett(\msg, \commitment)$
  \item
  Check whether $\challenge=\challenge^*$.
  Output $\accept$ if this is the case, and $\reject$ otherwise.
\end{enumerate}
\end{description}

If input parsing fails, an exception should be raised.
If verification fails, an exception should be raised.
Otherwise, the verifier outputs $\pctrue$. Optionally, the implementation can choose to return the parsed statement.

\begin{remark}{Availability of the short form}{}
  While the short form as described here is applicable to all $\Sigma$-protocols currently covered by this document, it cannot be used for protocols where $\commitment$ is not uniquely determined by $\challenge$ and $\response$, as is the case, e.g., for ZKBoo~\cite{USENIX:GiaMadOrl16}, one-out-of-many proofs~\cite{EC:GroKoh15}, or protocols, where a randomized signature is sent and proven correct subsequently, e.g., \cite{RSA:PoiSan16,AC:CamChaShe08}.

  A trade-off is presented, e.g., by Bobolz et al.~\cite{EPRINT:BEHF21}, requiring an additional algorithm to shorten a full transcript to a compressed form which still allows for unique reconstruction of the transcript.
\end{remark}



\subsection{Input validation}
\minote{TODO: validation of the statement, validation of the witness, validation of a short proof, and valdidation of batchable proof. can the challenge be zero; can the commitment be the point at infinity}

\subsection{Composition of $\Sigma$-Protocols}
\label{sec:composition}
\label{sec:or-comp}
\label{sec:and-comp}
  $\Sigma$-protocols can be composed to prove knowledge of multiple independent witnesses (\emph{AND composition}), and for proving knowledge for one out of a set of witnesses (\emph{OR composition}). An object $\sigmaprotocol$ can be seen as a recursive enumeration

  \begin{verbatim}
    enum SigmaProtocol {
      AndComposition {left: SigmaProtocol, right: SigmaProtocol},
      OrComposition  {left: SigmaProtocol, right: SigmaProtocol},
      [...]
    }
  \end{verbatim}
whose instances expose the methods described above.
The dots \texttt{[...]} denote (optional) $\Sigma$-protocols instantiations that will be covered in \cref{sec:sigma-dlog}.
  Without loss of generality, the techniques presented in the following focus on the composition of two protocols.
  Composition of multiple protocols (e.g., proving knowledge of a witness for one out of many statements) can be achieved by recursively applying composition of two protocols.

  \subsubsection{AND Composition}
  In this section we show how to construct a $\Sigma$-protocol proving knowledge of multiple independent witnesses, e.g., knowledge of multiple secret keys, or openings to multiple commitments.
  That is, a $\Sigma$-protocol for the following relation:
\[
  \relation[and] = \set{
    ((\statement_0,\statement_1),(\witness_0,\witness_1) : (\statement_0,\witness_0)\in \relation_0 ~\land~ (\statement_1,\witness_1)\in\relation_1}
\]
For the rest of this section, the witness $\witness$ for the $\Sigma$-protocol will now be a pair $(\witness_0, \witness_1)$ of witnesses, and the associated statement $\statement$ will be a pair $(\statement_0, \statement_1)$ of statements, where $\witness_0$ is the witness for the statement $\statement_0$, and $\witness_1$ is the witness for $\statement_1$.
%\minote{say explicitly that now the witness is a pair of witnesses valid for the respective relation. Same goes for the statement}

  Intuitively, the AND composition simply runs the instances of the different protocols to be composed in parallel, using the same challenge $\challenge$ for both instances.
  The verifier will then accept the protocol run if and only if all instances of the partial protocols output $\accept$.


The resulting $\Sigma$-protocol is specified by the following algorithms:
\begin{itemize}
  \item
  $\andcomposition.\new(\ctx, \leftbranch, \rightbranch)$: internally store $\leftbranch$ and $\rightbranch$.
  \item
  $(\vec \commitment, \proverstatett)\gets \andcomposition.\provercommitment(\vec \witness)$
    \begin{enumerate}
      \item
        $(\witness_0,\witness_1)\defeq \vec \witness$
      \item
        $(\commitment_0,\proverstatett_0)\gets\leftbranch.\provercommitment(\witness_0)$
      \item $(\commitment_1,\proverstatett_1)\gets\rightbranch.\provercommitment(\witness_1)$
      \item
	Return $(\vec \commitment,\proverstatett) \defeq ((\commitment_0,  \commitment_1),(\proverstatett_0,\proverstatett_1))$
    \end{enumerate}
  \item
  $\vec \response \gets \andcomposition.\proverresponse(\proverstatett, \challenge)$
  \begin{enumerate}
      \item
	    $(\proverstatett_0,\proverstatett_1)\defeq \proverstatett$
      \item
      $\response_0\gets\leftbranch.\proverresponse(\proverstatett_0, \challenge)$
      \item
      $\response_1\gets\rightbranch.\proverresponse(\proverstatett_1, \challenge)$
      \item
      Return $\vec \response\defeq(\response_0,\response_1)$
    \end{enumerate}
  \item
  $\andcomposition.\verifiertt(\vec \commitment, \challenge, \vec \response)$
  \begin{enumerate}
      \item
        $(\response_0,\response_1)\defeq \vec \response$.
      \item
	Return $\accept$ if both $\leftbranch.\verifiertt(\commitment_0,\challenge, \response_0)$ and $\rightbranch.\verifiertt(\commitment_1,\challenge, \response_1)$ return $\accept$. Otherwise, return $\reject$.
    \end{enumerate}
  \item  $\andcomposition.\labeltt()$ is computed as:
    \[
     \hash(\andlabel \concatblock \leftbranch.\labeltt() \concat \rightbranch.\labeltt())
   \]
   The supported hash functions are described in \cref{sec:hash-registry}.
  \item
  $\vec \response \gets \andcomposition.\simresponsett()$
   generates a simulated response as follows:
    \begin{enumerate}
      \item
        $\response_0\gets\leftbranch.\simresponsett()$
        \item $\response_1\gets\rightbranch.\simresponsett()$
      \item
        Return $\vec \response\defeq(\response_0,\response_1)$.
    \end{enumerate}
  \item
  $\vec \commitment \gets \andcomposition.\simcommitmenttt(\challenge, \vec \response)$ works as follows:
    \begin{enumerate}
      \item
        $(\response_0,\response_1)\defeq\vec\response$.
      \item
        $\commitment_0\gets\leftbranch.\simcommitmenttt(\challenge,\response_0)$
        \item $\commitment_1\gets\rightbranch.\simcommitmenttt(\challenge,\response_1)$
      \item
        Return $\vec \commitment\defeq(\commitment_0, \commitment_1)$.
      \end{enumerate}
\end{itemize}

\begin{warning}{Witness equality}{}
  Note that the AND-composition defined in the following gives no guarantee about equality of the witnesses: if the same witness is used across different clauses of the AND-composition, the protocol will not guarantee that they are indeed the same.
	How to achieve such claims is discussed in \cref{sec:linear_relations}.
  \end{warning}

\subsubsection{OR Composition}

  In the following we explain how to construct a $\Sigma$-protocol proving knowledge of one out of a set of witnesses, for instance one of a set of secret keys (like ring signatures).
  That is, the algorithms specified below constitute a $\Sigma$-protocol for the following relation:
\[
  \relation[or] = \set{
    ((\statement_0,\statement_1),(\witness_0,\witness_1) :
    (\statement_0,\witness_0)\in \relation_0 ~\lor~ (\statement_1,\witness_1)\in\relation_1}\,.
\]

The statement $\statement$ is the pair $(\statement_0, \statement_1)$ of the composing statements, and the witness $\witness$ is the pair $(\witness_0, \witness_1)$ of the witnesses for the respective relation. One of the witness can be set to $\none$.
  In the following protocol specification, let $j$ be such that $w_j$ is known to the prover, whereas without loss of generality $\witness_{1-j}$ is assumed to be unknown to the prover.

	On a high level, the protocol works as follows.
	Using the simulator, the prover first simulates a transcript for the unknown witness (keeping the challenge and response of this transcript temporarily secret), and generates an honest commitment for the known witness.
	Having received the challenge, the prover then computes a challenge for the known witness, depending on the received challenge and the one from the simulated transcript.
	Having computed the response, the prover transfers the responses of both transcripts, as well as the partial challenges to the verifier, who accepts if and only if both instances of the partial protocols output $\accept$ and the partial challenges correctly add up to the random challenge.

The main procedures of the resulting $\Sigma$-protocol are specified by the following algorithms:
\begin{itemize}
  \item
  $\orcomposition.\new(\ctx, \leftbranch, \rightbranch)$: internally store $\leftbranch$ and $\rightbranch$.
  \item
  $(\vec \commitment, \proverstatett)\gets \orcomposition.\provercommitment(\vec \witness)$:
    \begin{enumerate}
      \item $\provertt = [\leftbranch, \rightbranch]$
      \item
        $(\witness_0,\witness_1)\defeq \vec \witness$, and let $j \in \bin$ be the first index for which $\witness_{j}\neq\none$
      \item
        $(\commitment_j,\proverstatett_j)\gets\provertt[j].\provercommitment(\statement_j,\witness_j)$
      \item
			   $\response_{1-j}\gets\provertt[1-j].\simresponsett()$
			\item
        Choose a random $\challenge_{1-j}$ in $\CS$
      \item
        $\commitment_{1-j}\gets\provertt[1-j].\simcommitmenttt(\challenge_{1-j},\response_{1-j})$
      \item
	Return $(\vec \commitment,\proverstatett) \defeq ((\commitment_0,\commitment_1),(\proverstatett_j,\challenge_{1-j},\response_{1-j}))$
    \end{enumerate}
  \item
  $\vec \response \gets \orcomposition.\proverresponse(\proverstatett, \challenge)$:
    \begin{enumerate}
      \item  $(\proverstatett_j,\challenge_{1-j},\response_{1-j})\defeq\proverstatett$
      \item
         $\challenge_j\defeq \challenge\oplus \challenge_{1-j}$
         \item $\response_j\gets\provertt[j].\proverresponse(\proverstatett_j, \challenge_j)$
      \item
        Return $\vec \response\defeq(\response_0,\response_1, \challenge_0)$.
    \end{enumerate}
  \item
  $\orcomposition.\verifiertt(\vec \commitment, \challenge, \vec \response)$,
    \begin{enumerate}
      \item
         $(\response_0, \response_1, \challenge_0)\defeq \vec \response$.
      \item
         $\challenge_1\defeq \challenge \oplus \challenge_0$.
      \item
	    Return $\pctrue$ if both $\leftbranch.\verifiertt(\commitment_0,\challenge_0,\response_0)$ and $\rightbranch.\verifiertt(\commitment_1,\challenge_1,\response_1)$ return $\pctrue$. Otherwise, return $\pcfalse$.
    \end{enumerate}
  \item  $\orcomposition.\labeltt()$ is computed as:
    \[
     \hash(\orlabel \concatblock \leftbranch.\labeltt() \concat \rightbranch.\labeltt())
   \]
   The supported hash functions are described in \cref{sec:hash-registry}.
  \item
  $\vec \response \gets \orcomposition.\simresponsett()$
    \begin{enumerate}
      \item
         $(\statement_0,\statement_1)\defeq \vec \statement$.
      \item
         $\response_0\gets\leftbranch.\simresponsett()$
      \item $\response_1\gets\rightbranch.\simresponsett()$
      \item
        Choose a random $\challenge_0$ in $\CS$.
			\item
        Return $\vec \response \defeq (\response_0,\response_1,\challenge_0)$.
    \end{enumerate}
\item
$\vec \commitment \gets \orcomposition.\simcommitmenttt(\challenge, \vec \response)$
\begin{enumerate}
      \item
        $(\response_0,\response_1,\challenge_0)\defeq\vec\response$.
      \item
        $\challenge_1\defeq \challenge \oplus \challenge_0$.
      \item
        $\commitment_0 \gets\leftbranch.\simcommitmenttt(\challenge_0,\response_0)$
    \item $\commitment_1\gets\rightbranch.\simcommitmenttt(\challenge_1,\response_1)$
      \item
        Return $\vec \commitment \defeq (\commitment_0,\commitment_1)$.
    \end{enumerate}
\end{itemize}


\section{$\Sigma$-protocols on elliptic curves}
\label{sec:instantiation}

The following section presents concrete instantiations of $\Sigma$-protocols over elliptic curves.

\begin{remark}{Protocols for residue classes}{}
  Because of their dominance, the presentation in the following focuses on proof goals over elliptic curves, therefore leveraging additive notation.
	For prime-order subgroups of residue classes, all notation needs to be changed to multiplicative, and references to elliptic curves (e.g., $\curvectx$) need to be replaced by their respective counterparts over residue classes.
\end{remark}

\subsection{Ciphersuite Registry}
 We advise for the use of prime-order elliptic curves of size either 256 or 512 bits, depending on the desired security of the upper layers in the protocol\footnote{For instance, proving a DH relation with one fixed group element such as a public key, might expose the protocol to cryptanalytic attacks such as Brown-Gallant~\cite{EPRINT:BroGal04} and Cheon's attack~\cite{EC:Cheon06}, and some implementations might opt for larger curve sizes. We consider these attacks out of scope for this standardization effort, and believe this analysis should be deferred to the concrete security study of the larger protocol.}.

 \vspace{1em}
 \begin{center}
 \begin{tabular}{llcc}
  \hline
  Curve  & Identifier &  Security Level & Sources \\
  \hline
 P-521 & \verb|'-p-521'|     & 256& \cite{fips2} \\
 P-256 & \verb|'-p-256'|     & 128 & \cite{fips2}  \\
 secp256k1 & \verb|'-secp256k1'| & 128 & \cite{SECG} \\
 Ristretto & \verb|'-ristretto'| & 128 & \cite{cfrg-ristretto-decaf} \\
 BLS12-381 & \verb|'-bls12-381'| & 128 & \cite{bls12} \\
 \end{tabular}
\end{center}
We denote with $\GG$ the prime-order group of the elliptic curve, with $\FF_p$ the scalar field, and with $G$ the generator of $\GG$ chosen as per the curve parameters.
We assume that all above curve parameters also provide the following group operations: check for equality, identity, addition, and scalar multiplication. Optionally, implementation might implement Pippenger's algorithm~\cite{pippenger} for multi-scalar multiplication. In addition, we consider:

\begin{itemize}
  \item an identifier for the curve, chosen from the table above, and denoted $\curvectx$;
  \item a deterministic sub-procedure $a \defeq \frombytes(b)$, taking as input a bit string $b$ of length $\seedlen$, and mapping it into an element $a \sample \FF_p$;
  \item a deterministic sub-procedure $s \defeq \serialize(P)$, taking as input a group element $P \in \GG$ and returning a fixed-length sequence of bits.
  For elliptic curve groups, $\serialize$ must provide a compressed representation of the \emph{affine} representation, such as the $x$-coordinate of $P$ and one bit determining the sign of $y$.
  \item a deterministic sub-procedure $P \defeq \deserialize(s)$, taking a (fixed-length and curve-dependent) sequence of bits and returning an elliptic curve point. This procedure may raise an exception or output $\none$ if the conversion fails.
\end{itemize}

\subsection{Basic $\Sigma$-Protocols in prime-order groups}\label{sec:basic_sigma}
  We describe an abstract class for proving knowledge of a preimage under an arbitrary \emph{group homomorphism}, which is a mapping between two groups respecting the structure of the groups.
In particular, as will be discussed in \cref{sec:instantiations}, many statements related to discrete logarithms or representations in groups of prime order, can be expressed as statements over group homomorphisms.
For an in-depth discussion of the underlying theory we refer to Cramer~\cite{cramer97}.

\begin{definition}
  For two groups $\GG_1,\GG_2$, a function $\varphi:\GG_1\to\GG_2:x\mapsto\varphi(x)$ is a \emph{(group) homomorphism}, if and only if for all $a,b\in\GG_1$ it holds that $\varphi(a+b)=\varphi(a)+\varphi(b)$.
\end{definition}
Readers not familiar with the notation of group homomorphism may think of $\varphi$ as a linear function from $n$ elements into $m$ elements.

\begin{example}{Discrete logarithm equality}{phi_DLEQ}
  Looking at the relation $\relation[dleq]$ from \cref{exa:R_DLEQ}, the relevant homomorphism is given by:
	$$
	  \varphi_{\operatorname{dleq}} : \FF_p\to\GG^2 : \witness\mapsto (\witness G,\witness H)\,.
	$$
	If equality of discrete logarithms within \emph{different} groups of the same prime order $p$ is to be proven, the homomorphism to be considered would be:
	$$
	  \varphi_{\operatorname{dleq}}' : \FF_p\to\GG_1\times\GG_2 : \witness\mapsto (\witness G,\witness H)\,,
	$$
	where $G$ and $H$ would now be generators for $\GG_1$ and $\GG_2$, respectively.
	All the techniques discussed in the remainder of this spec equally apply to both cases.
\end{example}

\begin{example}{Representation}{phi_REP}
  Looking at the relation $\relation[rep]$ from \cref{exa:R_REP}, the relevant homomorphism is given by:
	$$
	  \varphi_{\operatorname{rep}} : \FF_p^2\to\GG : (\witness_1,\witness_2)\mapsto \witness_1 G + \witness_2 H\,.
	$$
\end{example}


\label{sec:sigma-dlog}
We provide a generic template for all $\Sigma$-protocols for statements of the following form over DLOG groups:
\[
  \relation[dlog]=\set{((\statement_1,\dots,\statement_m),(\witness_1,\dots,\witness_n)) \in \GG^m \times \FF_p^n: (\statement_1,\dots,\statement_m)=\varphi(\witness_1,\dots,\witness_n)}
\]
where $\varphi:\FF_p^n\to\GG^m$ is a group homomorphism.

\begin{remark}{Selective disclosure of witnesses}{}
  Note that in the following descriptions, all witnesses are assumed to be kept secret, i.e., none of them is disclosed to the verifier.
	In case it is required to disclose $\witness_j$, as is the case, e.g., in the context of attribute-based credential systems, the relation to be proven can be rewritten as follows:
$$
  \relation[dlog]'=\set{
	\begin{array}{r}
	((\statement_1',\dots,\statement_m')),(\witness_1,\dots,\witness_{j-1},\witness_{j+1},\dots,\witness_n)) \in \GG^m \times \FF_p^{n-1}: ~~~~~~~~~~~~\\
	(\statement_1',\dots,\statement_m')=\psi(\witness_1,\dots,\witness_{j-1},\witness_{j+1},\dots,\witness_n)
	\end{array}
	}
$$
  where
	\begin{align*}
    (\statement_1',\dots,\statement_m')                                   &:= (\statement_1,\dots,\statement_m)-\varphi(0,\dots,0,\witness_j,0,\dots,0)\,\text{ and}\\
	  \psi(\witness_1,\dots,\witness_{j-1},\witness_{j+1},\dots,\witness_n) &:= \varphi(\witness_1,\dots,\witness_{j-1},0,\witness_{j+1},\dots,\witness_n)\,.
	\end{align*}

\end{remark}

However, the following \emph{defines neither the morphism nor the label associated to the protocol}.
These will be defined later in the specific protocols.

\begin{itemize}
  \item $\dlogsigmaprotocol.\new(\ctx, \vec\statement)$ internally stores $\vec\statement$ and $\ctx$.
  \item\label{item:basic:p1}
   $(\vec \commitment, \proverstatett) \gets \dlogsigmaprotocol.\provercommitment(\vec \witness)$ consists of the following steps:
    \begin{enumerate}
      \item\label{item:basic:p1:randomness}
        Sample random elements $\randomness_1,\dots,\randomness_n\sample\FF_p$
      \item
         $\vec \commitment \defeq (\commitment_1,\dots,\commitment_m)\defeq\varphi(\randomness_1,\dots,\randomness_n)$
      \item $\proverstatett\defeq (\randomness_1,\dots,\randomness_n)$
      \item
        Return $(\vec \commitment,\proverstatett)$
    \end{enumerate}
  \item\label{item:basic:p2}
    $\vec \response \gets \dlogsigmaprotocol.\proverresponse(\proverstatett,\challenge)$ proceeds as follows:
    \begin{enumerate}
      \item  $(\randomness_1,\dots,\randomness_n)\defeq \proverstatett$
      \item  $(\witness_1,\dots,\witness_n)\defeq \vec \witness$
      \item  $e \defeq \frombytes(\challenge)$.
      \item For $i=1,\dots,n$: $\response_i\defeq \randomness_i+e \witness_i$
			\item Return $\vec\response \defeq (\response_1,\dots,\response_n)$.
    \end{enumerate}
  \item $\dlogsigmaprotocol.\labeltt()$ return $\morphismlabel()$.
  \item\label{item:basic:v}
     $\dlogsigmaprotocol.\verifiertt(\vec \commitment,\challenge,\vec \response)$ proceeds as follows:
    \begin{enumerate}
      \item  $(\response_1, \dots, \response_n) \defeq \vec \response$
      \item $(\commitment_1, \dots, \commitment_m) \defeq \vec \commitment$
      \item  $e \defeq \frombytes(\challenge)$.
      \item\label{item:basic:v:checks}
      For $i=1,\dots,n$: check $\response_i\in\FF_p$
      \item
      For $j=1,\dots,m$: check $\commitment_j\in\GG$
      \item Return $\accept$ if $(\commitment_1 + e\statement_1,\dots,\commitment_m + e\statement_m) = \varphi(\response_1,\dots,\response_n)$; $\reject$ otherwise
    \end{enumerate}
  \item $\vec \response \gets \dlogsigmaprotocol.\simresponsett()$:
  \begin{enumerate}
    \item Sample random elements $\response_1,\dots,\response_n\sample\FF_p$
    \item Return $(\response_1, \dots, \response_n)$
  \end{enumerate}
  \item\label{item:basic:sim}
     $\vec \commitment \gets \dlogsigmaprotocol.\simcommitmenttt(c, \vec s)$:
    \begin{enumerate}
      \item
       $(\statement_1,\dots,\statement_m)\defeq \vec \statement$.
      \item\label{item:basic:sim:s}
       $(\response_1,\dots,\response_n) \defeq \vec \response$.
       \item  $e \defeq \frombytes(\challenge)$.
      \item
         $(\commitment_1,\dots,\commitment_m) \defeq \varphi(\response_1,\dots,\response_n) - e\cdot(\statement_1,\dots,\statement_m)$.
      \item
        Output $\vec \commitment \defeq(\response_1,\dots,\response_n)$.
    \end{enumerate}
\end{itemize}

\subsection{Advanced: proving linear relations}\label{sec:linear_relations}

While the above protocol allows one to efficiently prove knowledge of a pre-image under a homomorphism, many protocols found in the literature require one to prove relations among witnesses.
  Specifically, they require to prove relations like the following:
\begin{equation*}
\relation[lin]=\set{((\statement_1,\dots,\statement_m),(\witness_1,\dots,\witness_n)) :
\begin{array}{c} (\statement_1,\dots,\statement_m)=\varphi(\witness_1,\dots,\witness_n) \\
                  A\cdot(\witness_1,\dots,\witness_n)^\intercal = (b_1,\dots,b_k)^\intercal\end{array}}\,,
\end{equation*}
where the matrix $A\in\FF_p^{k\times n}$ and vector $(b_1,\dots,b_k)\in\FF_p^k$ specify the system of linear equations.

In the following, we sketch how such relations can be translated into relations of the form discussed in \cref{sec:basic_sigma}.
We assume that $A$ is of the following form:
\begin{equation*}
A = \left(\begin{array}{cccccccc}
      a_{11}     & \dots       & a_{1k}    & 1         & 0       & 0     & \dots    & 0\\
      a_{21}     & \dots       & a_{2k}    & 0         & 1       & 0     & \dots    & \vdots\\
      \vdots     &             & \vdots    & \vdots    &         & \vdots&          & 0\\
      \vdots     &             & \vdots    & \vdots    &         & 0     & 1        & 0\\
      a_{k1}     & \dots       & a_{kk}    & 0         & \dots   & \dots & 0        & 1\\
    \end{array}\right)
\end{equation*}
Note that this is without loss of generality.
If the system of linear equations has a different form, the above form can always be achieved using Gaussian elimination \cite[Sec.~14.4]{shoup08} and re-ordering of the witnesses.
Note that we only need to consider the case where $k<n$, as otherwise the linear equations would uniquely determine the witnesses, which is not desirable in our context.

The following relation $\relation[lin]'$ is now equivalent to that specified by $\relation[lin]$:
\begin{equation*}
\relation[lin]'=\set{((\statement_1,\dots,\statement_m),(\witness_1,\dots,\witness_{n-k})) :
(\statement_1,\dots,\statement_m)=\psi(\witness_1,\dots,\witness_{n-k})}
\end{equation*}
where
\begin{align*}
  \psi(\witness_1,\dots,\witness_{n-k}) &:= \varphi(\witness_1,\dots,\witness_{n-k},-\sum_{i=1}^{n-k}a_{1i}\witness_i,\dots,-\sum_{i=1}^{n-k}a_{ki}\witness_i)\,\text{ and}\\
  (\statement_1',\dots,\statement_m')   &:= (\statement_1,\dots,\statement_m) - \varphi(0,\dots,0,b_1,\dots,b_k)\,.
\end{align*}


\subsection{Instantiations}\label{sec:instantiations}
Let $\GG$ be a group over an elliptic curve with prime order $p$. Denote with $G \in \GG$ a generator of $\GG$.

\subsubsection{Schnorr signatures}\label{sec:instantiations:schnorr}
Schnorr signatures, also known as Schnorr proofs or DLOG proofs, prove knowledge of the discrete logarithm $\witness \in \FF_p$ of a point $\statement=\witness G$ in base $G$.

\begin{itemize}
  \item $\varphi:\FF_p\to\GG:w\mapsto wG$
  \item $\schnorr.\morphismlabel()$: return:
  \[
    \hash(\schnorrlabel \concat \curvectx \concatblock \serialize(G) \concat \serialize(\statement))
  \]
\end{itemize}

For a description of this proof goal in the general case of residue classes, we also refer to~\cite[1.4.1]{zkproof-reference}.

    % \begin{protocol}{Proving knowledge of a discrete logarithm.\\[-2.25em]}{fig:dlog}{bpt}
    %   \begin{tabular}{@{}l@{\hspace{2em}}c@{\hspace{-3em}}r@{}}
    %     $\prover\left(\witness,\statement,G\right)$ & & $\verifier\left(\statement,G\right)$  \\
    %     \hline  \\
    %   % -----------------------------P1-------------------------------
    %     $ r\sample\FF_p$ & &\\
    %     $ T \defeq rG$ & & \\
    %     & $\sendr{T}{100}$ \\[2 ex]
    %   % -----------------------------CHALLENGE-------------------------------
    %     & & $c \sample \FF_p$ \\
    %     & $\sendl{c}{100}$ & \\[2 ex]
    %   % -----------------------------P2-------------------------------
    %     $ s \defeq r + cw$\\
    %     & $\sendr{s}{100}$ \\[2 ex]
    %   % -----------------------------V-------------------------------
    %     & & Return $\accept$ iff \\
    %     & & $T + cY = sG$ \\
    %   \end{tabular}
    % \end{protocol}

% For a given challenge $c\in\FF_p$, the simulator chooses $s\sample\FF_p$, and sets $T\gets sG-cY$.
% It then outputs the simulated transcript $(\commitment,\challenge,s)$.

\subsubsection{Discrete logarithm equality}
So-called DLEQ proofs prove equality of the discrete logarithm, that is: $\statement_1 = wG$ and $\statement_2 = wH$.

\begin{itemize}
  \item $\varphi:\FF_p\to\GG^2:w\mapsto (wG,wH)$
  \item $\dleq.\morphismlabel()$: return
  \[
    \hash(\dleqlabel \concat \curvectx \concatblock \serialize(G) \concat \serialize(H) \concat \serialize(\statement_1) \concat \serialize(\statement_2))
  \]
\end{itemize}
    % \begin{protocol}{Proving knowledge of equality of two discrete logarithms (alternative).\\[-2.25em]}{fig:dleq_2}{t}
    %   \begin{tabular}{@{}l@{\hspace{2em}}c@{\hspace{-3em}}r@{}}
    %     $\prover \left(\witness,(\statement_1,\statement_2),(G,H) \right)$ & & $\verifier \left((\statement_1,\statement_2),(G,H)\right)$  \\
    %     \hline  \\
    %   % -----------------------------P1-------------------------------
    %     $ r\sample\FF_p$ & &\\
    %     $ \commitment_1 \defeq rG$ & & \\
    %     $ \commitment_2 \defeq rH$ & & \\
    %     & $\sendr{\commitment_1,\commitment_2}{100}$ \\[2 ex]
    %   % -----------------------------CHALLENGE-------------------------------
    %     & & $c \sample \FF_p$ \\
    %     & $\sendl{c}{100}$ & \\[2 ex]
    %   % -----------------------------P2-------------------------------
    %   $s \defeq r + cw $& & \\
    %   & $\sendr{s}{100}$\\[2ex]
    %   % -----------------------------V-------------------------------
    %     & & Return $\accept$ iff \\
    %     & & $\commitment_1 + c\statement_1 = sG$ \\
    %     & & and $\commitment_2 + c\statement_2 = sH$. \\
    %   \end{tabular}
    % \end{protocol}

\subsubsection{Diffie-Hellman}
Let $\GG$ be a group over an elliptic curve with prime order $p$.
Proving knowledge of the exponents of a valid Diffie-Hellman triple means proving knowledge of $\witness_1,\witness_2\in\FF_p$ such that $\statement_1=\witness_1G$, $\statement_2=\witness_2G$, and $\statement_3=\witness_1 \witness_2 G$.
The mapping $\FF_p^2\to\GG^3:(\witness_1,\witness_2)\mapsto (\witness_1G,\witness_2G,\witness_1\witness_2G)$ is not a homomorphism, and consequently the basic protocol presented before cannot be deployed directly.
However, the required multiplicative relation can be proven by observing that the proof goal is equivalent to $\statement_1=\witness_1G$, $\statement_2=\witness_2G$, and $\statement_3=\witness_2\statement_1$, leading the homomorphism

\begin{itemize}
  \item  $\varphi:\FF_p^2\to\GG^3:(\witness_1,\witness_2)\mapsto(\witness_1G,\witness_2G,\witness_2\statement_1)$
  \item $\dhtt.\morphismlabel()$ return:
  \[
    \hash(\dhlabel \concat \curvectx \concatblock \serialize(G) \concat \serialize(\statement_1) \concat \serialize(\statement_2))
  \]
\end{itemize}

    % \begin{protocol}{Proving knowledge of representation.\\[-2.25em]}{fig:dh}{t}
    %   \begin{tabular}{@{}l@{\hspace{-3em}}c@{\hspace{-2em}}r@{}}
    %     $\prover\left( (\witness_1,\witness_2),(\statement_1,\statement_2,\statement_3),G)\right)$ & & $\verifier\left((\statement_1,\statement_2,\statement_3),G \right)$  \\
    %     \hline  \\
    %   % -----------------------------P1-------------------------------
    %     $ \randomness_1\sample\FF_p$ & &\\
    %     $ \randomness_2\sample\FF_p$ & &\\
    %     $ \commitment_1 \defeq \randomness_1G$ & & \\
    %     $ \commitment_2 \defeq \randomness_2G$ & & \\
    %     $ \commitment_3 \defeq \randomness_2\statement_1$ & & \\
    %     & $\sendr{\commitment_1,\commitment_2,\commitment_3}{100}$ \\[2 ex]
    %   % -----------------------------CHALLENGE-------------------------------
    %     & & $c \sample \FF_p$ \\
    %     & $\sendl{c}{100}$ & \\[2 ex]
    %   % -----------------------------P2-------------------------------
    %     $ s_1 \defeq \randomness_1 + c\witness_1$\\
    %     $ s_2 \defeq \randomness_2 + c\witness_2$\\
    %     & $\sendr{s_1,s_2}{100}$ \\[2 ex]
    %   % -----------------------------V-------------------------------
    %     & & Return $\accept$ iff \\
    %     & & $\commitment_1 + c\statement_1 = s_1G$ \\
    %     & & $\commitment_2 + c\statement_2 = s_2G$ \\
    %     & & and $\commitment_3 + c\statement_3 = s_2\statement_1$ \\
    %   \end{tabular}
    % \end{protocol}

% For a given challenge $c\in\FF_p$, the simulator chooses $s_1,s_2\sample\FF_p$, and sets $\commitment_1\defeq s_1G -c\statement_1$, $\commitment_2\defeq s_2G-c\statement_2$, and $\commitment_3\defeq s_2\statement_1-c\statement_3$.
% It then outputs the simulated transcript $((\commitment_1,\commitment_2,\commitment_3),\challenge,(s_1,s_2))$.

As shown in this example, and in contrast to linear relations, multiplicative relations among witnesses typically require a reformulation of the proof goal.


\subsubsection{Representation}\label{sec:instantiations:representation}
Let $\GG$ be a group over an elliptic curve of prime order $p$, and let $G_1, \dots, G_m$ be generators of $\GG$.
Proving knowledge of a valid opening of a Pedersen commitment means proving knowledge of $\witness_1,\witness_2, \dots, \witness_m\in\FF_p$ such that $Y=\witness_1G_1 + \witness_2G_2 + \dots + \witness_m G_m$.


\begin{itemize}
  \item $\varphi:\FF_p^m\to\GG:(\witness_1,\witness_2, \dots, \witness_m)\mapsto \sum_i \witness_iG_i$
  \item $\rep.\morphismlabel()$ returns
  \[
    \hash(\replabel \concat \curvectx \concatblock \serialize(G_1) \concat \cdots \concat \serialize(G_m) \concat \serialize(\statement))
  \]
\end{itemize}
    % \begin{protocol}{Proving knowledge of representation.\\[-2.25em]}{fig:rep}{hbpt}
    %   \begin{tabular}{@{}l@{\hspace{2em}}c@{\hspace{-3em}}r@{}}
    %     $\prover \left( (w_1,w_2),Y,(G,H)\right)$ & & $\verifier \left(Y,(G,H)\right)$  \\
    %     \hline  \\
    %   % -----------------------------P1-------------------------------
    %     $ \randomness_1\sample\FF_p$ & &\\
    %     $ \randomness_2\sample\FF_p$ & &\\
    %     $ T \defeq \randomness_1G + \randomness_2H$ & & \\
    %     & $\sendr{T}{100}$ \\[2 ex]
    %   % -----------------------------CHALLENGE-------------------------------
    %     & & $c \sample \FF_p$ \\
    %     & $\sendl{c}{100}$ & \\[2 ex]
    %   % -----------------------------P2-------------------------------
    %     $ s_1 \defeq \randomness_1 + cw_1$\\
    %     $ s_2 \defeq \randomness_2 + cw_2$\\
    %     & $\sendr{s_1,s_2}{100}$ \\[2 ex]
    %   % -----------------------------V-------------------------------
    %     & & Return $\accept$ iff \\
    %     & & $T + cY = s_1G + s_2H$ \\
    %   \end{tabular}
    % \end{protocol}


\begin{example}{Range proofs via bit decomposition}{}
  Let $\GG$ be a cyclic group of prime order $p$, and let $G$ and $H$ be generators of $\GG$, and let $\ell$ be a non-negative integer satisfying $\ell<\log_2 p$.
	Consider the following relation:
  $$
	  \relation[range] = \set{\left(\statement,(\witness_1,\witness_2))\right)~:~\statement=\witness_1 G +\witness_2 H ~\land~ \witness_1\in[0,2^\ell)}\,.
	$$
	Multiple techniques for proving that a secret witness lies within a certain range, cf. Morais et al.~\cite{range-proof-survey} for a survey.
	We will use the so-called \emph{bit decomposition} approach.

	To do so, the prover computes $\witness_{1,i}\in\set{0,1}$ for $i=0,\dots,\ell-1$ such that $\witness_1=\sum_{i=0}^{\ell-1}2^i\witness_{1,i}$, and computes commitments to those individual bits, i.e., $\statement_i=\witness_{1,i}G+\witness_{2,i}H$ for $\witness_{2,i}\sample\FF_p$.
	Furthermore, it sets $\witness^*=\witness_2-\sum_{i=0}^{\ell-1}2^i\witness_{2,i}$.

  Assuming that the discrete logarithm problem is hard in $\GG$, the above relation is now equivalent to the following relation:
  \begin{align}
	  \relation[range]' = \bigg\{\left((\statement,(\statement_i)_{i=0}^{\ell-1}),(\witness_1,\witness_2,(\witness_{2,i})_{i=0}^{\ell-1}),\witness^*)\right)~:~ 		\statement=\witness_1 G +\witness_2 H ~\land~ \label{ex:range:preimage}\\
		\statement-\sum_{i=0}^{\ell-1} 2^i\statement_i = \witness^* H ~\land~  \label{ex:range:equality}\\
		\bigwedge_{i=0}^{\ell-1} \left(\statement_i=\witness_{2,i}H ~\lor~ \statement_i-G=\witness_{2,i}H\right)\bigg\}\,.\label{ex:range:bits}
	\end{align}

	It can now be seen that \cref{ex:range:preimage} ensures knowledge of the witnesses $\witness_1$ hidden within $\statement$.
	Furthermore, \cref{ex:range:equality} guarantees that the values hidden within $\statement_i$ correctly add up to $\witness_1$, i.e., that $\witness_1-\sum_{i=0}^{\ell-1}2^i\witness_{1,i}=0$.
  Finally, the two clauses in \cref{ex:range:bits} ensure that each $\statement_i$ is a commitment to either $0$ or $1$, thus implying the bound on $\witness_1$.

	While \cref{ex:range:preimage} can be proven using the protocol from \cref{sec:instantiations:representation}, \cref{ex:range:equality} and \cref{ex:range:bits} can be proven using those from \cref{sec:instantiations:schnorr}.
	The different clauses can finally be composed using nested protocol compositions from \cref{sec:composition}.
\end{example}




\subsection{Batch verification}

The batchable form can take advantage of the following fact.
Given $\ell$ verification equations of the form:
\[
   \commitment_i + \challenge_i Y_i = \sum_j \response_j G_{i,j}
\]
for $i=1, \dots,\ell$,
%(So, $T \in \GG^\ell$, $c \in \FF_p^\ell$ and $s \in \FF_p^{\ell \times m}$ and $\mat G \in \GG^{m \times \ell}$.)
the verifier can sample a random vector of coefficients $\vec a \in \FF_p^\ell$ and instead test:
\[
  \left(\sum_{i=1}^{\ell} a_i \commitment_i\right) + \left(\sum_{i=1}^{\ell} a_i \cdot  \challenge_i \statement_i \right) = \left(\sum_{i=1}^{\ell} a_i \cdot \sum_j \response_j G_{i,j}\right).
\]
If the matrix $G_{i, j}$ of generators has identical rows, by linearity the right-hand side can be computed as a single scalar product.
If the statements $\statement_i$'s have identical rows, by linearity the second term in the equation can be computed as a single scalar product.

In any case, the test can be efficiently implemented as a single multiscalar multiplication, minimizing the number of group operations needed:
\[
  \left(\sum_{i=1}^{\ell} a_i \commitment_i\right) + \left(\sum_{i=1}^{\ell} (a_i \cdot  \challenge_i) \statement_i \right) + \left(\sum_{i=1}^{\ell}\sum_j (-a_i \cdot  \response_j) G_{i,j}\right) = 0.
\]

The random vector $\vec a$ can be \emph{deterministically} generated by fixing $a_1 \defeq 1$ and setting $(a_2, \dots, a_{\ell}) \defeq \prg(\hash(\challenge \concat \vec s))$~\cite{bip-schnorr}.

\section{Encoding the statement}

Statements in $\Sigma$-protocols take the form of a labeled binary tree:
$\statementnode$ is either:
\begin{itemize}
  \item a label \textsf{AND}, or \textsf{OR}, and two children \textsf{left} and \textsf{right} of type $\statementnode$
  \item a $\statementleaf$ instance. Objects of this type depend on the specific algebraic setting used, and will be treated in \cref{sec:sigma-dlog}.
\end{itemize}
Statements are serialized depth-first.
  There are many different options for serialization that could be considered:
  \begin{itemize}
  \item Concise Binary Object Representation (CBOR) \href{https://datatracker.ietf.org/doc/html/rfc7049}{RFC7049}
    \item The zk proof Reference document provides a serialization document for r1cs~\cite[3.4.2]{zkproof-reference}, but there is nothing in it.
\end{itemize}
\minote{
  \underline{Question for the community}: what kind of serialization format should we pick? It seems that no clear choice has been taken already for r1cs and CBOR seems to be the most reasonable choice?
}

\section{Additional proof types}

Other protocols are not included here and are not part of the scope of the current version of this spec.
\begin{itemize}
\item mpc-in-the-head protocol such as ZKBoo~\cite{USENIX:GiaMadOrl16}
\item one-out-of-many proofs such as~\cite{EC:GroKoh15}
\item lwe-based sigma protocol~\cite{C:AttCraKoh21}
\item syndrome decoding and LPN~\cite{C:Stern93,AC:JKPT12}
\end{itemize}

\bibliographystyle{alpha}
\bibliography{cryptobib/abbrev3,cryptobib/crypto,additional}

\end{document}