$\newcommand{\coinheads}{\mathsf{HEADS}}$ $\newcommand{\cointails}{\mathsf{TAILS}}$ $\newcommand{\varalice}{\class{var var_Alice}{\text{Alice}}}$ $\newcommand{\varbob}{\class{var var_Bob}{\text{Bob}}}$ $\newcommand{\alicebob}[3]{#1 & \ra{#2} & #3\\[-5pt]}$ $\newcommand{\bobalice}[3]{#1 & \la{#2} & #3\\[-5pt]}$ $\newcommand{\alicework}[1]{#1 & &\\[-5pt]}$ $\newcommand{\bobwork}[1]{ & & #1\\[-5pt]}$ $\newcommand{\work}[2]{#1 & & #2\\}$ $\newcommand{\allwork}[1]{ & #1 & \\}$ $\newcommand{\dupwork}[1]{#1 & & #1\\}$ $\newcommand{\aliceseparator}{-------&&\\}$ $\newcommand{\bobseparator}{&&-------\\}$ $\newcommand{\foo}{\phantom{\text{bigarrowfitsallthis}}}$ $\newcommand{\ra}[1]{% \vphantom{\xrightarrow{asd}}% \smash{\xrightarrow[\foo]{#1}}% }$ $\newcommand{\la}[1]{% \vphantom{\xleftarrow{asd}}% \smash{\xleftarrow[\foo]{#1}}% }$ $\newcommand{\z}[1]{\mathbb{Z}_{#1}}$ $\newcommand{\zq}{\mathbb{Z}_\varq}$ $\newcommand{\zqs}{\mathbb{Z}_q^\ast}$ $\newcommand{\zps}{\mathbb{Z}_p^\ast}$ $\newcommand{\zns}[1]{\mathbb{Z}_{#1}^\ast}$ $\require{action} \newcommand{\sampleSymb}{ {\overset{\$}{\leftarrow}} }$ $\newcommand{\field}[1]{\mathbb{F}_{#1}}$ $\newcommand{\sample}[1]{#1\sampleSymb\zq}$ $\newcommand{\sampleGeneric}[2]{#1\sampleSymb#2}$ $\newcommand{\sampleInterval}[2]{#1\sampleSymb\interval{#2}}$ $\newcommand{\sampleRange}[2]{#1\sampleSymb\range{#2}}$ $\newcommand{\sampleCgroup}[1]{#1\sampleSymb\cgroup}$ $\newcommand{\samplezqs}[1]{\class{hover}{#1\sampleSymb\zqs}}$ $\newcommand{\sampleN}[2]{\class{hover}{#1\sampleSymb\z{#2}}}$ $\newcommand{\sampleNs}[2]{\class{hover}{#1\sampleSymb\z{#2}^\ast}}$ $\newcommand{\equalQ}{\overset{?}{=}}$ $\newcommand{\gQ}{\overset{?}{>}}$ $\newcommand{\inQ}{\overset{?}{\in}}$ $\newcommand{\cgroup}{\mathbb{G}}$ $\newcommand{\Hash}{\mathsf{Hash}}$ $\newcommand{\hash}[1]{\Hash({#1})}$ $\newcommand{\HashToField}{\mathsf{HashToField}}$ $\newcommand{\hashtofield}[1]{\HashToField({#1})}$ $\newcommand{\HashToGroup}{\mathsf{HashToGroup}}$ $\newcommand{\hashtogroup}[1]{\HashToGroup({#1})}$ $\newcommand{\hashbit}[2]{\mathsf{Hash}({#1})\verb+[0:#2]+}$ $\newcommand{\hmac}[2]{\mathsf{HMAC}_{#1}\left(#2\right)}$ $\newcommand{\naturals}{\mathbb{N}}$ $\newcommand{\sqfree}{L_\mathsf{square-free}}$ $\newcommand{\ceil}[1]{\lceil #1 \rceil}$ $\newcommand{\sampleSet}[2]{\class{hover}{#1\sampleSymb#2}}$ $\newcommand{\bunch}[1]{\{ #1_i\}_{i=1}^m}$ $\newcommand{\bunchi}[1]{\{ #1\}_{i=1}^m}$ $\newcommand{\forb}{\text{ for }i=1,\ldots,m}$ $\newcommand{\interval}[1]{[0, #1[}$ $\newcommand{\range}[1]{[#1]}$ $\newcommand{\rangeone}[1]{\{1, \dots,#1 -1 \}}$ $\newcommand{\vara}{\class{var var_a}{a}}$ $\newcommand{\varb}{\class{var var_b}{b}}$ $\newcommand{\varc}{\class{var var_c}{c}}$ $\newcommand{\vard}{\class{var var_d}{d}}$ $\newcommand{\varh}{\class{var var_h}{h}}$ $\newcommand{\varH}{\class{var var_H}{H}}$ $\newcommand{\varg}{\class{var var_g}{g}}$ $\newcommand{\varG}{\class{var var_G}{G}}$ $\newcommand{\vari}{\class{var var_i}{i}}$ $\newcommand{\varj}{\class{var var_j}{j}}$ $\newcommand{\vars}{\class{var var_s}{s}}$ $\newcommand{\vart}{\class{var var_t}{t}}$ $\newcommand{\varu}{\class{var var_u}{u}}$ $\newcommand{\varU}{\class{var var_U}{U}}$ $\newcommand{\varl}{\class{var var_l}{l}}$ $\newcommand{\varm}{\class{var var_m}{m}}$ $\newcommand{\varn}{\class{var var_n}{n}}$ $\newcommand{\varx}{\class{var var_x}{x}}$ $\newcommand{\varX}{\class{var var_X}{X}}$ $\newcommand{\varz}{\class{var var_z}{z}}$ $\newcommand{\varr}{\class{var var_r}{r}}$ $\newcommand{\varq}{\class{var var_q}{q}}$ $\newcommand{\varp}{\class{var var_p}{p}}$ $\newcommand{\vare}{\class{var var_e}{e}}$ $\newcommand{\vary}{\class{var var_y}{y}}$ $\newcommand{\varv}{\class{var var_v}{v}}$ $\newcommand{\varw}{\class{var var_w}{w}}$ $\newcommand{\varC}{\class{var var_C}{C}}$ $\newcommand{\varf}{\class{var var_f}{f}}$ $\newcommand{\varA}{\class{var var_A}{A}}$ $\newcommand{\varB}{\class{var var_B}{B}}$ $\newcommand{\varC}{\class{var var_C}{C}}$ $\newcommand{\varL}{\class{var var_L}{L}}$ $\newcommand{\varP}{\class{var var_P}{P}}$ $\newcommand{\varR}{\class{var var_R}{R}}$ $\newcommand{\varT}{\class{var var_T}{T}}$ $\newcommand{\varX}{\class{var var_X}{X}}$ $\newcommand{\varalpha}{\class{var var_alpha}{\alpha}}$ $\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}$ $\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}$ $\newcommand{\varverifier}{\class{var var_Verifier}{\text{Verifier}}}$ $\newcommand{\varN}{\class{var var_N}{N}}$ $\newcommand{\rhovar}{\class{var var_ρ}{\rho}}$ $\newcommand{\sigmavar}{\class{var var_σ}{\sigma}}$ $\newcommand{\thetavar}{\class{var var_θ}{\theta}}$ $\newcommand{\muvar}{\class{var var_μ}{\mu}}$ $\renewcommand{\vec}[1]{\mathbf{#1}}$ $\newcommand{\veca}{\vec{\class{var var_vec_a}{a}}}$ $\newcommand{\vecb}{\vec{\class{var var_vec_b}{b}}}$ $\newcommand{\vecc}{\vec{\class{var var_vec_c}{c}}}$ $\newcommand{\vecs}{\vec{\class{var var_vec_s}{s}}}$ $\newcommand{\vecG}{\vec{\class{var var_vec_G}{G}}}$ $\newcommand{\vecH}{\vec{\class{var var_vec_H}{H}}}$ $\newcommand{\vecg}{\vec{\class{var var_vec_g}{g}}}$ $\newcommand{\vech}{\vec{\class{var var_vec_h}{h}}}$ $\newcommand{\true}{\mathsf{true}}$ $\newcommand{\false}{\mathsf{false}}$ $\newcommand{\ctx}{\mathsf{ctx}}$ $\newcommand{\coloneqq}{≔}$ $\newcommand{\ip}[2]{\left\langle #1, #2 \right\rangle}$ $\newcommand{\uwork}[2]{\underline{#1} & & \underline{#2}\\}$ $\newcommand{\aliceworks}[1]{#1 & &\\[-2pt]}$ $\newcommand{\bobworks}[1]{ & & #1\\[-2pt]}$ $\newcommand{\Halving}{\text{Halving}}$ $\newcommand{\HalveProof}{\text{HalveProof}}$ $\newcommand{\HalveVerify}{\text{HalveVerify}}$ $\newcommand{\indent}{\qquad}$ $\newcommand{\append}{\mathrm{append}}$ $\newcommand{\schnorrvalidate}{\mathsf{schnorr}\_\mathsf{validate}}$
Commitment Schemes

Commitment Schemes Generally #

Commitment schemes were introduced by Blum in 1981. Blum posed the following problem:

Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say “Here goes… I’m flipping the coin…. You lost!”

Blum’s solution was a commitment scheme: a way for Bob to send his call of HEADS or TAILS ahead of time, but in a way that makes it impossible to change his mind later, and not to reveal his choice until Alice has flipped the coin. Once Alice has flipped the coin, Bob can reveal his call to Alice to see who won the coin toss.

A commitment scheme has two phases:

  • A commit phase, in which the committer generates the commitment value and shares it with others, and

  • An open phase, when the committer reveals the committed value, and the commitment is verified by others

It’s very important that Bob can’t cheat Alice by revealing a fake call. It’s also very important that Alice can’t gain any information about Bob’s call from his commitment. These are the two major features of a good commitment scheme:

  • Hiding: a commitment doesn’t reveal anything about the committed value

  • Binding: it is not feasible to find two or more distinct values with the same commitment

Informally, you can think of hiding as what keeps Alice from cheating (since she can’t get any information about Bob’s call to use against him), and binding as what keeps Bob from cheating (since he can’t “change his mind” and send a valid opening for $call’\neq call$ if Alice announces a coin toss result he doesn’t like).

Lots of cryptographic protocols rely on this sort of exchange. For instance, this type of behavior is used in threshold signature schemes to allow a group of parties to securely generate an unbiased, uniformly random signing key.

To see an example of how this might be done using cryptography, consider the following process. Bob randomly selects $\sampleGeneric{call}{{\coinheads,\cointails}}$ as his call. Then he selects a 256-bit random value $r$ and computes, $c=\hmac{r}{call}$, then sends $c$ to Alice. Alice flips her coin, and announces either $\coinheads$ or $\cointails$. Bob then sends Alice $\left(r,call\right)$. Alice verifies that $c=\hmac{r}{call}$. If the two match, she accepts Bob’s call as valid; otherwise, she rejects Bob’s call as invalid.

We call $c$ Bobs’s commitment to his call, and we call $\left(r,call\right)$ the opening of $c$.

In protocol terms, we have:

$$ \begin{array}{c} \work{\varalice}{\varbob} \bobwork{\sampleGeneric{call}{\{\coinheads, \cointails\}}} \bobwork{\sampleGeneric{r}{\{0, 1\}^{256}}} \bobwork{c_{A}=\hmac{r}{call}} \bobalice{}{c_{A}}{} \alicework{\sampleGeneric{toss}{\{\coinheads, \cointails\}}} \alicebob{}{toss}{} \bobalice{}{\left(call,r\right)}{} \alicework{\hmac{r}{call}\equalQ c_{A} } \end{array} $$

It’s worth noting that simply setting $C=\hash{call}$ is problematic as a commitment mechanism. In our example, it would be trivial for Alice to compute $c_{\coinheads}=\hash{\coinheads}$ and $c_{\cointails}=\hash{\cointails}$ and compare them to Bob’s value for $C$.

Similarly, in our $\mathsf{HMAC}$ scheme, if Bob doesn’t select a fresh $r$ for each commitment, Alice can detect when Bob commits to the same value in different contexts.

Of course, the $\mathsf{HMAC}$ scheme isn’t limited to simple $\coinheads/\cointails$ calls; it can be used for an arbitrary message $m$: $c=\hmac{r}{m}$.

This scheme will be both hiding and binding due to the properties of the $\mathsf{HMAC}$ function. Without $r$, Alice has no way of checking if $c$ commits to $\coinheads$ or $\cointails$, and it’s computationally infeasible for Bob to find $r’$ such that $c=\hmac{r’}{call’}$ (where $call’\neq call$).

It’s possible to create a commitment scheme that is hiding but not binding. Suppose the commitment $c_{A}$ above only included the lowest 16 bits of the HMAC output. It would take a fraction of a second for Bob to find $r’\neq r$ such that $c=\hmac{r’}{call’}$.

Conversely, it’s possible to have a commitment scheme that is binding but not hiding. The easiest example would be for Bob to simply send $call$ to Alice, as in the original, insecure coin flip protocol. Bob can’t change his mind after sending $c$, but nothing is hidden from Alice.

Some specialized commitment schemes provide features beyond simple binding and hiding. The KZG polynomial commitment scheme, for instance, enables Bob to commit to a polynomial $f$ while allowing him to prove that a pair $\left(x, y=f\left(x\right)\right)$ represents a correct evaluation of $f$.

Pedersen Commitments
An overview of the Pedersen commitment scheme and its applications
KZG Polynomial Commitments
Kate et. al’s Pairing-Based Polynomial Commitments
IPA Polynomial Commitment
An overview of the Inner Product Argument polynomial commitment scheme

References #