Score:1

Many-out-of-many proofs

mz flag

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.

poncho avatar
my flag
is the value of $x$ publicly known?
Seed Barret avatar
mz flag
x is not public, it's unknown to the verifier
poncho avatar
my flag
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)
knaccc avatar
es flag
@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.
Score:1
es flag

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.

Seed Barret avatar
mz flag
Did you mean G instead of H here: (∑)− and −?
knaccc avatar
es flag
@SeedBarret oops, thanks, updated :)
Seed Barret avatar
mz flag
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)?
knaccc avatar
es flag
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](https://web.getmonero.org/library/Zero-to-Monero-1-0-0.pdf) for an alternative explanation of how it works
Seed Barret avatar
mz flag
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.
knaccc avatar
es flag
@SeedBarret the only way I could see that it would be possible to prove "exactly 0 for N-1 out of N commitments" was to prove statements 1 and 2 together. I can't think of a simpler way to do it
knaccc avatar
es flag
@SeedBarret I found a much simpler approach, and updated the answer
Seed Barret avatar
mz flag
Thanks for your reply, new approach seems to be secure
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.