Score:0

Given pedersen commitments of some elements, how to prove that the sum of only one subset of these elements is equal to the given element θ?

gn flag

Assume that Prover have $n$ pedersen commitments ($V_{a_1},V_{a_2},\cdots,V_{a_n}$ where $V_{a_i}=G \cdot a_i + H \cdot r_{a_i}$) of $n$ elements $a_1,a_2,\cdots,a_n$. The Prover have another element $\theta$.

The verifier is provided with these $n$ pedersen commitments ($V_{a_1},V_{a_2},\cdots,V_{a_n}$) and $\theta$.

How can the Prover prove that the sum of $\textbf{only one}$ subset of these elements $a_1,a_2,\cdots,a_n$ can equal to $\theta$ and don't reveal these elements to verifier? (the size of this set is a constant witch smaller than $n$)

Richard Thiessen avatar
mx flag
Ignoring the cryptography part, this sounds like the [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem) but in reverse. Proving a specific subset satisfies the sum is straightforward, proving no other subsets do will depend on how you would prove this in the non-zero-knowledge case. This depends on how you choose $a_n$ values to guarantee this property. If the values are powers of 2, it's obvious that your condition holds (only one sum possible) and there are approaches to doing the proof. Arbitrary sets will be harder.
Richard Thiessen avatar
mx flag
If you're trying to do this for arbitrary sets, you might need to ask on https://math.stackexchange.com/ what the non-zero knowledge proof would look like.
user105684 avatar
gn flag
@Richard Thiessen:Thankyou!How can I proof only one sum possible if the values are powers of 2?
Richard Thiessen avatar
mx flag
If you don't care about revealing what values are in the original list, You can something like [mental poker](https://en.wikipedia.org/wiki/Mental_poker) to show the list is a set of non-repeated `2^i` powers but shuffled. Then just do a sigma-or proof to accumulate some number of the shuffled commitments and that's that.
Richard Thiessen avatar
mx flag
For an arbitrary list, if the list is small and proof size can be `O(2^n)`, you can do 2^n inequality proofs with a single backdoor to allow falsifying one of them and something ring signature like to ensure one of them is actually false.
Score:0
sa flag

Let $a_i=2^{u_i}$ $i=1,\ldots,n$ with $u_i$ nonnegative integers. If the values $u_i$ are distinct, and $$ \theta=\sum_{i \in J} 2^{u_i} $$ then the subset $J\in \{1,\ldots,n\}$ is uniquely determined by $\theta$ by the uniqueness of writing $\theta$ in base $2.$

If they are not unique, then the decomposition is not necessarily unique since e.g., the repeated values $u_i,u_i$ could be replaced by $u_j=u_i+1.$

So if $u_i$ appears twice in the list then the list should not contain $u_i+1.$ This is because $2^3+2^3=2^4,$ for example. Define the condition $$ \textrm{Do}~u_i,u_i,u_{i}+1~ \textrm{appear in the list?}\quad (*) $$ If (*) does not hold the expression is unique. If it does hold then a new list with $n-1$ members should be formed with $u_i+1$ replacing the pair $u_i,u_i$ in the original list and the condition checked again recursively. Obviously if $u_i$ appeared $f_i\geq 2$ times in the original list it would appear $f_i-2$ times in the new list.

Then the condition $(*)$ needs to be applied to the new list, and this needs to be repeated again and again if $(*)$ holds until it no longer holds finally confirming uniqueness.

user105684 avatar
gn flag
Thanks for your reply!I still have a problem because prover cannot reveal all values. Given pedersen commitments of all values, how can the prover prove they are powers of 2?
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.