# Is it possible to build a compact proof of the sum of all even numbers of a dataset?

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.

• According to eprint.iacr.org/2016/260.pdf, proof is of fixed size. – Vadym Fedyukovych Dec 14 '17 at 0:47
• 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. – fgrieu Jan 11 '18 at 6:40

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.

• 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. – Geoffroy Couteau Oct 14 '17 at 7:16
• Please elaborate on your claim. You are essentially saying "your wrong" without motivation. – Meir Maor Oct 14 '17 at 7:48
• 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. – Geoffroy Couteau Oct 14 '17 at 8:04
• 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? – MaiaVictor Oct 14 '17 at 12:29
• Geoffroy, would love that promised explanation. – Meir Maor Oct 16 '17 at 6:30

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.