Score:2

Range proof for elements in Vector Pedersen commitment

ru flag

If I construct a vector pedersen commitment $c = a_1G_1 + a_2G_2 + ... + a_nG_n$ with an arbitrary scalar vector $(a_1, a_2, ..., a_n)$ and group elements $(G_1, G_2, ..., G_n)$, is it possible to create a range proof that proves that each element in this commitment is non-negative?

I understand that it is possible to create a range proof using Bulletproofs for cases like $c=aG+bH$, but is it possible to create a range proof for vectors like the one above as well?

Score:1
es flag

Your vector commitment does not have a blinding factor, which means it does not hide whether two different commitments are to the same list of $a_i$ components. Depending on the nature of the $a_i$ components, it may also be possible to brute-force the commitment to determine the components it represents.

We can easily fix this by adding a blinding factor $b$:

$C = a_0G_0 + a_1G_1 + ... + a_{n-1}G_{n-1} + bH$

We wish to demonstrate that each component $a_i$ is a positive integer less than $2^s$.

To do this, we create and declare $(n\cdot s)$ commitments each with their own uniformly random blinding factor $b_{i,j}$, where $0\leq i <n$ and $0\leq j <s$. Each commitment $C_{i,j}$ is calculated as $C_{i,j} = (z_{i,j}\cdot 2^j)G_i + b_{i,j}H$, where $z_{i,j}$ is $0$ or $1$ and represents the $j$th bit of the component $a_i$.

A verifier can calculate $C'=\sum C_{i,j}$. We can demonstrate that $C$ represents the same list of $a_i$ components as $C'$ by providing a signature for the public key $(C-C')$ on the base point $H$. The private key for the point $(C-C')$ will be the value $b-\sum b_{i,j}$.

We've now demonstrated two things: $C$ is a commitment to the same list of components as $C'$, and that each component $a_i$ is created as a list of no more than $s$ bits (and thus must be a positive integer).

All that is left is to demonstrate is that each of the declared commitments $C_{i,j}$ really is a commitment either to $0$ or to $2^jG_i$.

This can be achieved with any kind of ring signature that proves the private key for either $C_{i,j}$ or $(C_{i,j} - 2^jG_i)$ on the base point $H$ is known. You can use bulletproofs or the simpler to understand Borromean ring signatures to achieve this.

ru flag
Thans. I understand. In this case, the proof size for all commitments $C_{i, j}$ be $O (\log (n \cdot s))$ with Bulletproofs?
knaccc avatar
es flag
@ShigeyukiAzuchi I'm not an expert on bulletproofs, I only have experience implementing Schnorr-based ring signatures. It may or may not complicate things that there are multiple base points $G_i$ involved.
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.