# Range proof for elements in Vector Pedersen commitment

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?

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 and $$0\leq j . 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.

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