I have a large number of items with a unique serial number and a score (score isn't always unique).

There is a list which contains all of the serial numbers and their respective scores.

I select 3 items at random, and have to prove:

  1. That all three items are in the list
  2. The total of the scores exceeds a predefined global number X

This has to be done without revealing what the original serial numbers or scores were.

All the answers I've seen haven't been applicable to this scenario because they all seem to rely on the fact that a list is a group that has generators, but my list isn't.

  • $\begingroup$ You can split this into two proofs and compose them together. Use a merkle tree for your large lists, then prove set membership in that list. The second proof would be to prove that your scores-GLOBALNUMBER > 0 so essentially a range proof. Gluing them together would require that the second proof, takes auxiliary inputs or the other way around $\endgroup$ – user69644 Jul 16 '19 at 23:50
  • $\begingroup$ can you explain what you mean in each of those points? i have no idea how to impliment what you just told me, also the list isnt large, only contains about 100 items. $\endgroup$ – aidan byrne Jul 17 '19 at 1:43
  • $\begingroup$ Essentially, you need two set membership proofs. One to show your items are amongst some list. The other to show your scores-GLOBALNUM > 0. How you implement each one is up to you, however you must make the output of proof 1 feed into proof2, so they are connected. You want to prove that “the items are in a list (proof1) AND these same items have a score that is greater than GLOBALNUM $\endgroup$ – user69644 Jul 17 '19 at 10:47
  • $\begingroup$ okay that makes sense, but how do i actually do the proofs? all the proofs ive tried either requrire the items in a set to be related in some way (form a group) or can easily be bute forced because there are only 100 items in the list $\endgroup$ – aidan byrne Jul 18 '19 at 0:32

Your Answer

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

Browse other questions tagged or ask your own question.