# Many-out-of-many proofs

I need to prove that given vector of commitments of length N contains N-1 commitments to zero (and one to an arbitrary number). More formally, given vector: $$\textbf{a} = \begin{bmatrix} C(0, r_1) & C(0, r_2) & C(x, r_3) & ... & C(0, r_N) \end{bmatrix}$$ I want to prove that there is exactly one such commitment, that commits to x, rather than 0. Note that x is also private.
I've seen the opposite to what I need to prove in One-out-of-Many Proofs paper, but still can't come up with what I need.

• is the value of $x$ publicly known? Commented Aug 13, 2023 at 1:15
• x is not public, it's unknown to the verifier Commented Aug 13, 2023 at 4:47
• I remember seeing a zero proof of knowledge that 'all know the discrete log of all but one of these values'; it is straight-forward to see how to use that with Pedersen commitments to directly solve your problem. However, I can't find that zero knowledge proof again, nor could I reconstruct it from memory (hence this is not an answer) Commented Aug 13, 2023 at 22:47
• @poncho I've just devised a much simpler answer. I wonder if it jogs your memory, and if it is anything like what you distantly recall. Commented Aug 14, 2023 at 0:08

Each of the $$n$$ commitments are of the form $$C_i=a_iG+b_iH$$, where $$a_i$$ is the value being committed to, and $$b_i$$ is the uniformly random blinding factor.

$$G$$ and $$H$$ are generator points, arbitrarily and fairly chosen so that $$g$$ such that $$G=gH$$ is unknowable (the EC discrete log assumption).

This means that if you treat $$C_i$$ as a public key on the generator $$H$$, the corresponding private key will be $$a_ig+b_i$$. Since $$g$$ is unknowable, the private key is only known if $$a_i\overset{?}{=} 0$$, i.e. the commitment is to the value zero.

Therefore, being able to provide a signature (such as a Schnorr signature) proving knowledge of the private key is equivalent to proving that the commitment is to the value zero. The same applies to knowledge of the private key of a sum of commitments.

First, calculate a challenge scalar $$r_i$$ for each commitment $$C_i$$. This can be done using an extendable-output function or HKDF, using the concatenation of all commitment EC-point bit strings as the initial keying material.

Calculate $$S$$ and $$S'$$ as follows:

$$S=\sum\limits_{i=0}^{n-1}{C_i}$$

$$S'=\sum\limits_{i=0}^{n-1}{r_iC_i}$$

Now, create $$n$$ public keys, as follows:

$$P_i=S'-r_iS$$

If the commitment to the value $$x$$ is at index $$\pi$$, then it will only be possible for $$P_{\pi}$$ to be a commitment to zero if all other commitments are commitments to zero (because multiplying zero by a random number is still zero). The private key will be $$\sum\limits_{i=0}^{n-1}{r_ib_i}-r_{\pi}b_{\pi}$$

If we provided a signature on the generator $$H$$ proving that $$P_{\pi}$$ is a commitment to zero, we would disclose $$\pi$$. To avoid disclosing the index $$\pi$$, we simply generate a ring signature instead.

Essentially, this approach is creating a ring, where each member of the ring contains the sum of $$n-1$$ commitments. Each ring position excludes a different commitment. The ring can only be signed if in at least one ring position, every commitment involved in the sum is a commitment to zero.

• Did you mean G instead of H here: (∑𝐶)−𝑥𝐻 and 𝐶−𝑥𝐻? Commented Aug 13, 2023 at 5:36
• @SeedBarret oops, thanks, updated :) Commented Aug 13, 2023 at 14:04
• How to combine all ring signatures (ones that are for commitments to 0) into one borromean ring signature? I've seen that in borromean ring signature you prove that for different rings you have exactly one private key for exactly one public key in that specific ring, am i right? If yes, then how use borromean ring sig in my case, where I have only one ring, for which i want to prove knowledge of N-1 secret keys (i.e. openings ag+b, where a = 0 and b is secret key)? Commented Aug 13, 2023 at 16:00
• Ring signatures prove you know at least one of the private keys. The Borromean ring signature is just a clever way of combining multiple ring signatures to reduce the overall size. Each "loop" in the Borromean ring signature will apply to only one particular commitment, and will prove it is either a commitment to zero or $x$. See page 27 here for an alternative explanation of how it works Commented Aug 13, 2023 at 16:11
• What if instead of proving "either x or 0", prover proves "exactly 0" for N-1 out of N commitments? This should be enough for my initial statement. Commented Aug 13, 2023 at 17:17