2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thans. I understand. In this case, the proof size for all commitments $C_{i, j}$ be $O (\log (n \cdot s))$ with Bulletproofs? $\endgroup$ Commented Feb 24, 2022 at 6:36
  • $\begingroup$ @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. $\endgroup$
    – knaccc
    Commented Feb 24, 2022 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.