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)\)