2
$\begingroup$

Suppose I have a set of numbers:

[1, 7, 6, 4, 8, 9, 4, 6, 3, 3, 1, 5, 4]

Suppose also that a verifier knows the merkle root of that set, R, but he doesn't know the set itself. Is it possible to convince him that the sum of all even numbers - i.e., 6 + 4 + 8 + 4 + 6 + 4 is 32 with a string of a small, constant size (i.e., not depending on the length of the array)?

I thought that was possible with zk-snarks, but now I'm under the impression even a zk-snark proof would be of linear size w.r.t the number of elements.

$\endgroup$
  • $\begingroup$ According to eprint.iacr.org/2016/260.pdf, proof is of fixed size. $\endgroup$ – Vadym Fedyukovych Dec 14 '17 at 0:47
  • $\begingroup$ What's considered does not seem to be a set, where identical elements are aggregated, which would be equivalent to{1, 3, 4, 6, 7, 8, 9 }. Perhaps it is a multiset, which would be equivalent to {1, 1, 3, 3, 4, 4, 4, 5, 6, 6, 7, 8, 9}. Or perhaps it is a tuple, where order matters. $\endgroup$ – fgrieu Jan 11 '18 at 6:40
2
$\begingroup$

Let's ignore the zk requirement. And focus on compactness. If we have a merkel tree and I swap just one element at random so one of the hashes is invalid and doesn't match the data. We get a merkel tree with almost all valid hashes. Someone would have to verify all of them to catch the foegery. If you only sampled a few paths you would gain little confidence. Any extra calculations you require on the tree could be done onhe forged version. I'm afraid your request is impossible.

$\endgroup$
  • 1
    $\begingroup$ That's not true, what you mention does not constitute an obstacle, rather a difficulty to take care of. What OP wants can indeed be done with a zk-snark. $\endgroup$ – Geoffroy Couteau Oct 14 '17 at 7:16
  • 2
    $\begingroup$ Please elaborate on your claim. You are essentially saying "your wrong" without motivation. $\endgroup$ – Meir Maor Oct 14 '17 at 7:48
  • 1
    $\begingroup$ Sorry if it seemed rude - being on my phone from the train, I cannot elaborate right now, but I will later on. Just wanted to mention my disagreement for OP to get an alternative point of view to your answer and not see it as definitive - but for sure, it'll be more useful when I'll have time to develop a bit. $\endgroup$ – Geoffroy Couteau Oct 14 '17 at 8:04
  • 1
    $\begingroup$ I don't get the issue / proposed attack, though. If you change any bit of anything at all the root hash changes, so how is that a problem? $\endgroup$ – MaiaVictor Oct 14 '17 at 12:29
  • 2
    $\begingroup$ Geoffroy, would love that promised explanation. $\endgroup$ – Meir Maor Oct 16 '17 at 6:30
1
$\begingroup$

Please let me focus on linear (in number of elements) vs. fixed-size proof.

For a specific relation to be verified/proved, with varying input and the same circuit, one may split proof calculation into circuit-specific preprocessing and input-specific proof. This might result in some confusion while comparing with older better-known proofs (like Sigma protocols), unless explicitly defined in the context of SNARKs.

So, a common reference string is generated, to amortize costs by reuse. This CRS is usually huge, and is basically a large number of group elements. This way fixed proof size is achieved, at the cost of CRS.

For original question about sum of even elements, I would introduce a witness as ($e_j$ for even and $o_j$ for odd elements $a_j$) and an arithmetic circuit like $a_j = 2 e_j \lor a_j = 2 o_j + 1$, followed by $s = 2 \sum e_j$. Please note this question sounds somewhat like a homework and not too much own research was demonstrated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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