---
# System prepended metadata

title: Sigma-protocol-based proof of inequality

---


Let $C_w$ be a Pedersen commitment which $P$ knows $x, r$ such that 
$$
C_w = g^x \cdot h^c
$$  Given $x_v$,  $P$ wants to show to $V$ that $x \neq x_v$ without revealing $x$ or $r$. 

**Construction**
1. $P$ picks $t_1, t_2 \leftarrow _R\{1,.., q\}$ where $|g| = q$, and sends
$$
u_1 = g^{t_1}, u_2 = h^{t_2}
$$ to $V$.

3. $V$ sends a challenge $c \leftarrow _R\{1,..,q\}$ to $P$
4. $P$ sends
$$
z_1 = c(x - x_v) + t_1,  \\
z_2 = cr + t_2
$$
to $V$
5. $V$ checks that the followings hold
    1. $g^{z_1} \cdot h^{z_2} = (\frac{C_w}{g^{x_v}})^c \cdot u_1 \cdot u_1$
    2. $u_1 \neq g^{z_1}$


**Completeness**
First check in step 4.
lhs:
$$
g^{z_1} \cdot h^{z_2} \\
g^{c(x - x_v) + t_1} \cdot h^{cr + t_2} \\
\frac{g^{cx} \cdot g^{t_1}\cdot h^{cr} \cdot h^{t_2}}{g^{cx_v}}
$$

rhs:
$$
 (\frac{C_w}{g^{x_v}})^c \cdot u_1 \cdot u_1 \\
= \frac{g^{cx} \cdot h^{cr}}{g^{cx_v}} \cdot g^{t_1} \cdot  h^{t_2} \\
= \frac{g^{cx} \cdot g^{t_1} \cdot h^{cr}\cdot  h^{t_2}}{g^{cx_v}} \\
$$

Second check in step 4.
Implicit


**Special soundness**

Let $(c, z_1, z_2)$ and $(c', z_1', z_2')$ be two transcripts of the above construction which the check in step 4 has been passed, and $c \neq c'$. 

We have
$$
g^{z_1 - z_1'} \\
= g^{c(x - x_v) + t_1 - (c'(x - x_v) + t_1)} \\
= g^{c(x - x_v) - c'(x - x_v)} \\
$$

Since $c(x - x_v) - c'(x - x_v) = z_1 - z_1'$  is a linear equation with a single unknown variable, we can uniquely determine $x$.

And $x \neq x_v$, since if $x = x_v$ then $z_1 = c(x - x_v) + t_1 = t_1$, which contradicts the second check in step 4. ($u_1 \neq g^{z_1}$).

**Honest-verifier zero-knowledge**
Folklore