owned this note
owned this note
Published
Linked with GitHub
# Union sigs bulletproofs
See https://hackmd.io/@nibnalin/bls-multiplicity#Bulletproofing for the high-level description of the protocol
## Notation
$\textbf{b}$ is the public final bitfield (e.g. if $\textbf{v} = \{3, 6, 0, 8\}$ then $\textbf{b} = \{1, 1, 0, 1\}$)
$\textbf{P}$ is the list of public keys
$A$ is the aggregate public key $A = v_1 * P_1 + v_2 * P_2 + ...$
$\textbf{v}$ is the actual coefficients of the public keys in the aggregate public key
$V$ is the Pedersen commitment to $\textbf{v}$
$\textbf{w}$ is a vector where $w_i = u_i^{-1}$
$W$ is the Pedersen commitment to $\textbf{w}$
## Variant 1) Naive (separate commitments for v and w)
### Union Sig relation
$$
R_{union} =
\left\{
\begin{array}{l l |l}
(\textbf{b}, \textbf{P}, A, V, W);
&
(\textbf{v}, \textbf{w})
&
A = \textbf{v} \times \textbf{P}
\\
& &
V = \textbf{v} \times \textbf{G}
\\
& &
W = \textbf{w} \times \textbf{H}
\\
& &
\textbf{b} = \textbf{v} \circ \textbf{w}
\end{array}
\right\}
$$
### Proof for aggregate pubkey
$$
R_{A} =
\left\{
\begin{array}{l l |l}
(\textbf{P}, A, V);
&
(\textbf{v})
&
A = \textbf{v} \times \textbf{P}
\\
& &
V = \textbf{v} \times \textbf{G}
\end{array}
\right\}
$$
Proof size: $4log(n) + 1$
### Prover
**Step 1**
while $1 \leq j \leq \log(n):$
$\quad$ $n \gets \frac{n}{2}$
$\quad$ $L_{A,j} \gets \textbf{v}_{[:n]} \times \textbf{P}_{[n:]}$
$\quad$ $L_{V,j} \gets \textbf{v}_{[n:]} \times \textbf{G}_{[:n]}$
$\quad$ $R_{A,j} \gets \textbf{v}_{[n:]} \times \textbf{P}_{[:n]}$
$\quad$ $R_{V,j} \gets \textbf{v}_{[:n]} \times \textbf{G}_{[n:]}$
$\quad$ $\pi_{ j} \gets (L_{A,j}, L_{V,j}, R_{A,j}, R_{V,j})$
$\quad$ $\gamma_j \gets H( \pi_{ j} )$
$\quad$ $\textbf{v} \gets \textbf{v}_{[:n]} + \gamma_j^{-1} \textbf{v}_{[n:]}$
$\quad$ $\textbf{P} \gets \textbf{P}_{[:n]} + \gamma_j \textbf{P}_{[n:]}$
$\quad$ $\textbf{G} \gets \textbf{G}_{[:n]} + \gamma_j \textbf{G}_{[n:]}$
**Step 2**
$\nu \gets \textbf{v}_1$
return $(\pi, \nu)$
### Verifier
**Step 1**
while $1 \leq j \leq \log(n):$
$\quad$ $n \gets \frac{n}{2}$
$\quad$ $\gamma_j \gets H( \pi_{ j} )$
$\quad$ $A \gets \gamma_j L_{A,j} + A + \gamma_j^{-1} R_{A,j}$
$\quad$ $V \gets \gamma_j L_{V,j} + V + \gamma_j^{-1} R_{V,j}$
$\quad$ $\textbf{P} \gets \textbf{P}_{[:n]} + \gamma_j \textbf{P}_{[n:]}$
$\quad$ $\textbf{G} \gets \textbf{G}_{[:n]} + \gamma_j \textbf{G}_{[n:]}$
**Step 2**
check $A = \nu P_1$
check $V = \nu G_1$
### Proof for binarification
#### Reasoning
We want to prove that $\textbf{b} = \textbf{v} \circ \textbf{w}$. We will turn this to an IP using a random linear combination.
For random $\textbf{x}$, we want to prove the equivalent: $\textbf{x} \circ \textbf{b} = \textbf{x} \circ \textbf{v} \circ \textbf{w}$.
This can be proved with the following IPA: $\textbf{x} \times \textbf{b} = (\textbf{x} \circ \textbf{v}) \times \textbf{w}$
#### Relation
Get $\textbf{x}$ from Verifier.
Let $\textbf{a} = \textbf{x} \circ \textbf{v}$
Let $\textbf{G'} = \textbf{x}^{-1} \circ \textbf{G}$
Let $b' = \textbf{x} \times \textbf{b}$ (which the verifier can compute)
$$
R_{b} =
\left\{
\begin{array}{l l |l}
(b', V, W);
&
(\textbf{a}, \textbf{w})
&
b' = \textbf{a} \times \textbf{w}
\\
& &
V = \textbf{a} \times \textbf{G'}
\\
& &
W = \textbf{w} \times \textbf{H}
\end{array}
\right\}
$$
Proof size: $4log(n) + 2$
### Prover
**Step 1**
while $1 \leq j \leq \log(n):$
$\quad$ $n \gets \frac{n}{2}$
$\quad$ $L_{V,j} \gets \textbf{a}_{[:n]} \times \textbf{G'}_{[n:]} + (\textbf{a}_{[:n]} \times \textbf{w}_{[n:]})Q$
$\quad$ $L_{W,j} \gets \textbf{w}_{[n:]} \times \textbf{H}_{[:n]}$
$\quad$ $R_{V,j} \gets \textbf{a}_{[n:]} \times \textbf{G'}_{[:n]} + (\textbf{a}_{[n:]} \times \textbf{w}_{[:n]})Q$
$\quad$ $R_{W,j} \gets \textbf{w}_{[:n]} \times \textbf{H}_{[n:]}$
$\quad$ $\pi_{ j} \gets (L_{V,j}, L_{W,j}, R_{V,j}, R_{W,j})$
$\quad$ $\gamma_j \gets H( \pi_{ j} )$
$\quad$ $\textbf{a} \gets \textbf{a}_{[:n]} + \gamma_j^{-1} \textbf{a}_{[n:]}$
$\quad$ $\textbf{w} \gets \textbf{w}_{[:n]} + \gamma_j \textbf{w}_{[n:]}$
$\quad$ $\textbf{G'} \gets \textbf{G'}_{[:n]} + \gamma_j \textbf{G'}_{[n:]}$
$\quad$ $\textbf{H} \gets \textbf{H}_{[:n]} + \gamma_j^{-1} \textbf{H}_{[n:]}$
**Step 2**
$a \gets \textbf{a}_1$
$w \gets \textbf{w}_1$
return $(\pi, a, w)$
### Verifier
**Step 1**
XXX add \beta from Verifier
$V \gets V + b'Q$
while $1 \leq j \leq \log(n):$
$\quad$ $n \gets \frac{n}{2}$
$\quad$ $\gamma_j \gets H( \pi_{ j} )$
$\quad$ $V \gets \gamma_j L_{V,j} + V + \gamma_j^{-1} R_{V,j}$
$\quad$ $W \gets \gamma_j L_{W,j} + W + \gamma_j^{-1} R_{W,j}$
$\quad$ $\textbf{G'} \gets \textbf{G'}_{[:n]} + \gamma_j \textbf{G'}_{[n:]}$
$\quad$ $\textbf{H} \gets \textbf{H}_{[:n]} + \gamma_j^{-1} \textbf{H}_{[n:]}$
**Step 2**
check $V = a G'_1 + a w Q$
check $W = w H_1$
----
----
----
## Variant 2) Merged commitments for v and w
### Union Sig relation
$$
R_{union} =
\left\{
\begin{array}{l l |l}
(\textbf{b}, \textbf{P}, A, C);
&
(\textbf{v}, \textbf{w})
&
A = \textbf{v} \times \textbf{P}
\\
& &
C = \textbf{v} \times \textbf{G} + \textbf{w} \times \textbf{H}
\\
& &
\textbf{b} = \textbf{v} \circ \textbf{w}
\end{array}
\right\}
$$
### Proof for aggregate pubkey (w/ merged commitments)
We want to prove that:
$$
R_{A} =
\left\{
\begin{array}{l l |l}
(\textbf{P}, A, C);
&
(\textbf{v})
&
A = \textbf{v} \times \textbf{P}
\\
& &
C = \textbf{v} \times \textbf{G} + \textbf{w} \times \textbf{H}
\end{array}
\right\}
$$
which is equivalent to:
$$
R_{A} =
\left\{
\begin{array}{l l |l}
(\textbf{P}, A, C);
&
(\textbf{v})
&
A = \textbf{v} \times \textbf{P} + \textbf{w} \times \textbf{0}
\\
& &
C = \textbf{v} \times \textbf{G} + \textbf{w} \times \textbf{H}
\end{array}
\right\}
$$
Let $\textbf{P} = \textbf{P || 0}$
Let $\textbf{G} = \textbf{G || H}$
Let $\textbf{v}$ = $\textbf{v || w}$
and prove the following relation:
$$
R_{A} =
\left\{
\begin{array}{l l |l}
(\textbf{P}, A, C);
&
(\textbf{v})
&
A = \textbf{v} \times \textbf{P}
\\
& &
C = \textbf{v} \times \textbf{G}
\end{array}
\right\}
$$
which gets proven in the same way as *Variant 1*.
Proof size: $4log(2n)$
### Proof for binarification (w/ merged commitments)
#### Relation
Get $\textbf{x}$ from Verifier.
Let $\textbf{a} = \textbf{x} \circ \textbf{v}$
Let $\textbf{G'} = \textbf{x}^{-1} \circ \textbf{G}$
Let $b' = \textbf{x} \times \textbf{b}$ (which the verifier can compute)
$$
R_{b} =
\left\{
\begin{array}{l l |l}
(b', C);
&
(\textbf{a}, \textbf{w})
&
b' = \textbf{a} \times \textbf{w}
\\
& &
C = \textbf{a} \times \textbf{G'} + \textbf{w} \times \textbf{H}
\end{array}
\right\}
$$
Proof size: $2log(n)$
### Prover
**Step 1**
while $1 \leq j \leq \log(n):$
$\quad$ $n \gets \frac{n}{2}$
$\quad$ $L_{C,j} \gets \textbf{a}_{[:n]} \times \textbf{G'}_{[n:]} + \textbf{w}_{[n:]} \times \textbf{H}_{[:n]} + (\textbf{a}_{[:n]} \times \textbf{w}_{[n:]})Q$
$\quad$ $R_{C,j} \gets \textbf{a}_{[n:]} \times \textbf{G'}_{[:n]} + \textbf{w}_{[:n]} \times \textbf{H}_{[n:]} + (\textbf{a}_{[n:]} \times \textbf{w}_{[:n]})Q$
$\quad$ $\pi_{ j} \gets (L_{C,j}, R_{C,j})$
$\quad$ $\gamma_j \gets H( \pi_{ j} )$
$\quad$ $\textbf{a} \gets \textbf{a}_{[:n]} + \gamma_j^{-1} \textbf{a}_{[n:]}$
$\quad$ $\textbf{w} \gets \textbf{w}_{[:n]} + \gamma_j \textbf{w}_{[n:]}$
$\quad$ $\textbf{G'} \gets \textbf{G'}_{[:n]} + \gamma_j \textbf{G'}_{[n:]}$
$\quad$ $\textbf{H} \gets \textbf{H}_{[:n]} + \gamma_j^{-1} \textbf{H}_{[n:]}$
**Step 2**
$a \gets \textbf{a}_1$
$w \gets \textbf{w}_1$
return $(\pi, a, w)$
### Verifier
**Step 1**
XXX add \beta from Verifier
$C \gets C + b'Q$
while $1 \leq j \leq \log(n):$
$\quad$ $n \gets \frac{n}{2}$
$\quad$ $\gamma_j \gets H( \pi_{ j} )$
$\quad$ $C \gets \gamma_j L_{C,j} + C + \gamma_j^{-1} R_{C,j}$
$\quad$ $\textbf{G'} \gets \textbf{G'}_{[:n]} + \gamma_j \textbf{G'}_{[n:]}$
$\quad$ $\textbf{H} \gets \textbf{H}_{[:n]} + \gamma_j^{-1} \textbf{H}_{[n:]}$
**Step 2**
check $C = a G'_1 + w H_1 + a w Q$
----
----
----
## Protocol overview
$$
R_{union} =
\left\{
\begin{array}{l l |l}
(\textbf{b}, \textbf{P}, A, C);
&
(\textbf{v}, \textbf{w})
&
A = \textbf{v} \times \textbf{P}
\\
& &
C = \textbf{v} \times \textbf{G} + \textbf{w} \times \textbf{H}
\\
& &
\textbf{b} = \textbf{v} \circ \textbf{w}
\end{array}
\right\}
$$
$\textbf{P'} \gets \textbf{P || 0}$
$\textbf{GH} \gets \textbf{G || H}$
$\textbf{vw} \gets \textbf{v || w}$
$$
R_{A} =
\left\{
\begin{array}{l l |l}
(\textbf{P'}, A, C);
&
(\textbf{vw})
&
A = \textbf{vw} \times \textbf{P'}
\\
& &
C = \textbf{vw} \times \textbf{GH}
\end{array}
\right\}
$$
$\textbf{x} \gets Verifier$
$\textbf{a} \gets \textbf{x} \circ \textbf{v}$
$\textbf{G'} \gets \textbf{x}^{-1} \circ \textbf{G}$
$b' \gets \textbf{x} \times \textbf{b}$\
$$
R_{b} =
\left\{
\begin{array}{l l |l}
(b', C);
&
(\textbf{a}, \textbf{w})
&
b' = \textbf{a} \times \textbf{w}
\\
& &
C = \textbf{a} \times \textbf{G'} + \textbf{w} \times \textbf{H}
\end{array}
\right\}
$$
### Prover
$\textbf{P} \gets \textbf{P || 0}$
$\textbf{G'} \gets \textbf{G || H}$
$\textbf{v'} \gets \textbf{v || w}$
$\pi_a = prove_a((\textbf{G'}), (\textbf{P}, A, C), (\textbf{v'}))$
$\textbf{x} \gets Verifier$
$\textbf{a} \gets \textbf{x} \circ \textbf{v}$
$\textbf{G'} \gets \textbf{x}^{-1} \circ \textbf{G}$
$b' \gets \textbf{x} \times \textbf{b}$\
$\pi_b = prove_b((\textbf{G', H}), (b', C), (\textbf{a}, \textbf{w}))$
return $(\pi_a, \pi_b)$
### Verifier
$\textbf{P} \gets \textbf{P || 0}$
$\textbf{G'} \gets \textbf{G || H}$
assert $verify_a((\textbf{G'}), (\textbf{P}, A, C), \pi_a)$
$\textbf{x} \gets Verifier$
$\textbf{G'} \gets \textbf{x}^{-1} \circ \textbf{G}$
$b' \gets \textbf{x} \times \textbf{b}$\
assert $verify_b((\textbf{G', H}, Q), (b', C), \pi_b)$
----
----
----
## Variant 3) Seen as one relation (no need to prove C twice)
$$
R_{union} =
\left\{
\begin{array}{l l |l}
(\textbf{b}, \textbf{P}, A, C);
&
(\textbf{v}, \textbf{w})
&
A = \textbf{v} \times \textbf{P}
\\
& &
C = \textbf{v} \times \textbf{G} + \textbf{w} \times \textbf{H}
\\
& &
\textbf{b} = \textbf{v} \circ \textbf{w}
\end{array}
\right\}
$$
$\textbf{x} \gets Verifier$
$\textbf{a} \gets \textbf{x} \circ \textbf{v}$
$b' \gets \textbf{x} \times \textbf{b}$
$\textbf{P'} \gets \textbf{x}^{-1} \textbf{P}$
$\textbf{G'} \gets \textbf{x}^{-1} \textbf{G}$
$$
R_{union} =
\left\{
\begin{array}{l l |l}
(\textbf{b}, \textbf{P'}, A, C);
&
(\textbf{a}, \textbf{w})
&
A = \textbf{a} \times \textbf{P'}
\\
& &
C = \textbf{a} \times \textbf{G'} + \textbf{w} \times \textbf{H}
\\
& &
\textbf{b'} = \textbf{a} \circ \textbf{w}
\end{array}
\right\}
$$
Proof size: $2log(2n) + 2log(n) = 2 + 2logn + 2logn = 2 + 4logn$
### Prover
**Step 1**
while $1 \leq j \leq \log(n):$
$\quad$ $L_{C,j} \gets \textbf{a}_{[:n]} \times \textbf{G'}_{[n:]} + \textbf{w}_{[n:]} \times \textbf{H}_{[:n]} + (\textbf{a}_{[:n]} \times \textbf{w}_{[n:]})Q$
$\quad$ $R_{C,j} \gets \textbf{a}_{[n:]} \times \textbf{G'}_{[:n]} + \textbf{w}_{[:n]} \times \textbf{H}_{[n:]} + (\textbf{a}_{[n:]} \times \textbf{w}_{[:n]})Q$
$\quad$ $L_{A,j} \gets \textbf{a}_{[:n]} \times \textbf{P'}_{[n:]}$
$\quad$ $R_{A,j} \gets \textbf{a}_{[n:]} \times \textbf{P'}_{[:n]}$
$\quad$ $\pi_{ j} \gets (L_{C,j}, R_{C,j}, L_{A,j}, R_{A,j})$
$\quad$ $\gamma_j \gets H( \pi_{ j} )$
$\quad$ $\textbf{a} \gets \textbf{a}_{[:n]} + \gamma_j^{-1} \textbf{a}_{[n:]}$
$\quad$ $\textbf{w} \gets \textbf{w}_{[:n]} + \gamma_j \textbf{w}_{[n:]}$
$\quad$ $\textbf{P'} \gets \textbf{P'}_{[:n]} + \gamma_j \textbf{P'}_{[n:]}$
$\quad$ $\textbf{G'} \gets \textbf{G'}_{[:n]} + \gamma_j \textbf{G'}_{[n:]}$
$\quad$ $\textbf{H} \gets \textbf{H}_{[:n]} + \gamma_j^{-1} \textbf{H}_{[n:]}$
**Step 2**
$a \gets \textbf{a}_1$
$w \gets \textbf{w}_1$
return $(\pi, a, w)$