Hyrax Primitives

We go over various sigma protocols (interactive proofs with just 3 rounds of interaction) that allow the prover to prove various statements on its committed messages without having to open the commitment. For all of these protocols, let $g_i\in \mathbb{G}$ be the message commitment generators, and $h\in \mathbb{G}$ be the blinding generator. Let ${\mathbb{F}}_p$ be the scalar field of $\mathbb{G}$. Assume the prover produces the blinding factor $r\in {\mathbb{F}}_p$ using a cryptographic PRNG.

Proof of Opening

In a Proof of Opening, $\mathcal{P}$ shows that given a commitment $C_0=xg+rh$, $\mathcal{P}$ knows the message $x$ and blinding factor $r$ used to generate this commitment.

1. $\mathcal{P}\to \mathcal{V}:$ $\mathcal{P}$ samples $t_1,t_2\stackrel{\$}{\leftarrow }{\mathbb{F}}_p$ uniformly from the scalar field. $\mathcal{P}$ computes and sends over $\alpha =t_{1}g+t_{2}h.$
2. $\mathcal{V}\to \mathcal{P}:$ A random challenge $c$ from ${\mathbb{F}}_p$.
3. $\mathcal{P}\to \mathcal{V}:$ $z_1=x\cdot c+t_1$, and $z_2=r\cdot c+t_2$.
4. $\mathcal{V}$ checks: $z_{1}g+z_{2}h\stackrel{?}{=}c{C}_0+\alpha .$

Proof of Equality

In a Proof of Equality, $\mathcal{P}$ convinces $\mathcal{V}$ that two commitments $C_0=v_{0}g+s_{0}h$ and $C_1=v_{1}g+s_{1}h$ commit to the same value, i.e. $v_0=v_1$. In other words $\mathcal{P}$ knows that $v_0=v_1$, but $\mathcal{V}$ only has the blinded commitments, which look uniformly random (since $s_{0}h,s_{1}h$ are uniformly randomly distributed in $\mathbb{G}$ for uniformly random $s_0,s_1\in {\mathbb{F}}_p$).

1. $\mathcal{P}\to \mathcal{V}:$ $\mathcal{P}$ first uniformly samples a random value $r$ from ${\mathbb{F}}_p$. $\mathcal{P}$ computes $\alpha =rh$ and sends to $\mathcal{V}$.
2. $\mathcal{V}\to \mathcal{P}:$ A random challenge $c$ from ${\mathbb{F}}_p$.
3. $\mathcal{P}\to \mathcal{V}:$ $z=c\cdot (s_0-s_1)+r$
4. $\mathcal{V}$ checks: $zh\stackrel{?}{=}c(C_0-C_1)+\alpha .$

Proof of Product

Proof of product shows that a commitment $Z=zg+r_{Z}h$ is a commitment to the product of the messages committed to in $X=xg+r_{X}h$ and $Y=yg+r_{Y}h.$ In other words, $\mathcal{P}$ knows that $x\cdot y=z$ and wants to prove this to $\mathcal{V}$ without revealing the messages and just using the commitments.

1. $\mathcal{P}\to \mathcal{V}:$ $\mathcal{P}$ uniformly samples $b_1,\dots ,b_5$ from ${\mathbb{F}}_p$ and computes and sends over $\alpha =b_{1}g+b_{2}h,\beta =b_{3}g+b_{4}h,\delta =b_{3}X+b_{5}h.$
2. $\mathcal{V}\to \mathcal{P}:$ A random challenge $c$ from ${\mathbb{F}}_p$.
3. $\mathcal{P}\to \mathcal{V}:$ $$\begin{gathered} z_1=b_1+c\cdot x \\ {z}_2=b_2+c\cdot r_X \\ {z}_3=b_3+c\cdot y \\ {z}_4=b_4+c\cdot r_Y \\ {z}_5=b_5+c\cdot (r_Z-r_{X}y) \end{gathered}$$
4. $\mathcal{V}$ checks: $$\begin{gathered} \alpha +cX\stackrel{?}{=}{z}_{1}g+z_{2}h \\ \beta +cY\stackrel{?}{=}{z}_{3}g+z_{4}h \\ \delta +cZ\stackrel{?}{=}{z}_{3}X+z_{5}h \end{gathered}$$

Proof of Dot Product

Given $\mathcal{P}$'s commitment to a vector $\vec{x}\in {\mathbb{F}}_p^n$, $C_0=x_1{g}_1+x_2{g}_2+\cdots +x_n{g}_n+r_{0}h,$ and a public vector $\vec{a}$ (known to both $\mathcal{V}$ and $\mathcal{P}$), and $\mathcal{P}$'s commitment to the claimed dot product $⟨x,a⟩=y$, which is $C_1=y{g}_1+r_{1}h,$ $\mathcal{P}$ shows $\mathcal{V}$ that they know a vector $\vec{x}$ and blinding $r_0$ such that $⟨\vec{x},\vec{a}⟩$ is equal to the message committed to in $C_1$, and $C_0$ is a vector commitment for $\vec{x}$ with blinding factor $r_0$.

1. $\mathcal{P}\to \mathcal{V}:$ $\mathcal{P}$ samples a random vector in ${\mathbb{F}}_p^n$, $\vec{d}$. $\mathcal{P}$ samples $r_{\delta },r_{\beta }$ and computes and sends

$$\begin{gathered} \delta =d_1{g}_1+\cdots +d_n{g}_n+r_{\delta }h \\ \beta =y{g}_1+r_{\beta }h \end{gathered}$$

2. $\mathcal{V}\to \mathcal{P}:$ A random challenge $c$ from ${\mathbb{F}}_p$.
3. $\mathcal{P}\to \mathcal{V}:$

$$\begin{gathered} \vec{z}=c\cdot \vec{x}+\vec{d} \\ {z}_{\delta }=c\cdot r_0+r_{\delta } \\ {z}_{\beta }=c\cdot r_1+r_{\beta } \end{gathered}$$ 4. $\mathcal{V}$ checks:

$$\begin{gathered} c{C}_0+\delta \stackrel{?}{=}{z}_1{g}_1+\cdots +z_n{g}_n+z_{\delta }h \\ c{C}_1+\beta \stackrel{?}{=}⟨z,a⟩g_1+z_{\beta }h \end{gathered}$$