I'm trying to solve a problem that goes as follow. There is a set of item and that set is very large. Several actors needs to exchange information about this set, such as adding and removing element from the set and querying if an element is in the set. These actors do not trust each others so they need solid proof. Because the set is very large, actors need to be able to operate with partial knowledge of the set.

So I've been able to find scheme that solve some of the constraints, but not all of them. Here are the direction I explored:

ECMH: https://arxiv.org/pdf/1601.06502.pdf

This allows to commit to a set of items and recompute the commitment easily when items are added/removed, even when the content of the set is unknown.

Sorted Merkle tree: This satisfy the ability to prove membership, however, adding and removing elements from the set require knowledge of the whole set.

  • $\begingroup$ Is there a question? $\endgroup$
    – Elias
    Jun 24 '17 at 20:38
  • $\begingroup$ Is there a solution to this problem ? $\endgroup$
    – deadalnix
    Jun 25 '17 at 10:24
  • $\begingroup$ May I ask what this is for? Just curious, slightly OT. $\endgroup$
    – Elias
    Jun 25 '17 at 15:22
  • $\begingroup$ I'm researching way to scale blockchains techs. Right now, doing something as described above is done using patricia trees ( github.com/ethereum/wiki/wiki/Patricia-Tree ), Sparse Merkle tree ( eprint.iacr.org/2016/683.pdf ) or alike. All these structures scale very poorly, as you can't cache anything (you are literally feeding entropy to the datastructure). Holomorphic hashing scales well, but you lose the membership proof with the techniques I know of, which is a problem is some use cases. $\endgroup$
    – deadalnix
    Jun 25 '17 at 19:46
  • $\begingroup$ I think the object you want can be described as a "cryptographic accumulator" with membership and nonmembership proofs. If one could find such a construction with O(1) proofs it could revolutionize blockchains. I've been searching for something myself. AFAICT existing accumulator constructions require a trusted setup and a trusted key that creates the accumulator. Probably not something that will fly in the blockchain world. diyhpl.us/~bryan/papers2/security/cryptography/accumulators $\endgroup$ Jun 25 '17 at 21:47

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.