I'd like to store a large amount of objects, all authenticated using something like a Merkle tree. The root will be published, and I'd like to make sure there is no way to enumerate these objects from the root of the tree, or even prove a document is in the tree, unless this information has been published by me.

Is there an existing variant of Merkle tree to do so, or should I invent something myself? I came up with the following scheme, but it is most probably utterly broken:

  • A root is a hash(first-level nodes + salt).
  • Every node is a hash(next-level nodes/documents + salt).
  • A separate salt is stored for every document and for every node
  • In order to reveal a document I publish the path in the tree with all the salts along the way.

Merkel trees already allow you to decide how much you reveal. To prove presence of one leaf, you reveal it and the commits along its copath.

If your documents contain enough entropy then you do not need salts. If the documents do not, then you may prepend each document with a salt I.e. $\text{hmac}(\text{secret} \| \text{index}, \text{message})$.

The intermediate nodes do not need salts.

To avoid leaking the number of documents you can fix the copaths length to $\lceil\log_b(N)\rceil$. This adds an additional $N - b^{\lceil\log_b(N)\rceil}$ zero-sized documents as additional noise. $b$ is the number of branches per depth (usually $2$). The padding should be uniformly shuffled with all documents, not ordered or appended to the end. The $\text{index}$ identifier is the position from root-to-leaf left-to-right after flattening the tree. I.e. $[0], [1, 2], [3, 4, 5, 6]$.

  • $\begingroup$ I suppose I need a salt, otherwise revealing a path makes it possible to match (admittedly, small number of) documents referenced from the last node in the path. I wonder how to create it by not assigning indices to documents centrally. Is salt = hash(secret||message) a bad idea? $\endgroup$ – dottedmag Mar 10 '18 at 7:57
  • $\begingroup$ Could you please elaborate on adding entropy in the leaf positions? I'm not terribly concerned about revealing the approximate number of documents though. $\endgroup$ – dottedmag Mar 10 '18 at 7:59
  • $\begingroup$ I was thinking about altering the depth (variable length copath) but this obfuscation is weaker than just expanding the set to some arbitrary fixed length, kinda like padding. So think zero-sized documents that are never revealed and are in a uniform position as with all other documents. $\endgroup$ – cypherfox Mar 10 '18 at 9:07
  • $\begingroup$ @dottedmag I've updated my answer accordingly. You may take this another step further by adding another depth or two at the cost of $b$ times more leaves per depth. $\endgroup$ – cypherfox Mar 10 '18 at 9:34
  • $\begingroup$ @dottedmag What is wrong with the indices? Your suggested $\text{salt} = \text{hash}(\text{secret} \| \text{message})$ will collide on duplicate documents. If duplicate documents aren't a thing, then yes it should be fine. $\endgroup$ – cypherfox Mar 10 '18 at 9:37

The concept already exists, at the very least, within hash based signatures.

The closest to your idea would be in the Merkle tree in LMS; see section 5.

In fact, the only differences between that level of LMS, and your idea is:

  • In LMS, the salts are publicly computable (as there's no reason for them not to be)

  • In LMS, the "documents" are actually the public keys to one time signatures, and not arbitrary texts.

Now, in LMS, they're not actually concerned about the privacy of the nodes in the tree (as they assume that the forger has access to all the valid signed messages, and so can see the entire tree); you do have that concern, and so that's probably why you make the salts secret (until you publish the proof). On the other hand, you really only care about the privacy of the documents (and not the internal nodes themselves); you could consider making only the salts you add to the document secret.


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.