I am looking for something like hash tree in a sense that leaves node can be verified to be part of the tree but the tree has to be able to built top down (from top node to leaves).

I'm not sure exactly what I am looking for, but here's the application:

  • Suppose there are users of a certain type of data storage.
  • User can create new data and edit or remove any data they created.
  • User can also create user accounts and also manipulate data of all users created by them (unlimited levels of user).

When a user creates something in the data storage I plan to store something along with the file created so I can verify which user can modify which file and I want to do it with fixed length metadata and with fixed or at least faster than linear verification time (compared to maximum levels of user).

Is this possible? How? Is there any other existing solutions for this application?

  • 1
    Do you have trusted storage? Who is doing the verification? – mikeazo Mar 8 '17 at 16:32
  • The storage can be accessed only by trusted writer/reader. And the verification will be done by the writer. – Curious Sam Mar 8 '17 at 16:35
  • 1
    Having "fixed length metadata" seems to be a difficult requirement since you can have unlimited levels of users. You might be able to store a bloom filter for each file. In the bloom filter you store the user's ID, to state that they have access. When they try to access, you check again. Bloom filters have no false negatives, but do have false positives (you will grant access when they don't really have access). The false positive rate is configurable. – mikeazo Mar 8 '17 at 17:31

Well, I think your question is more related to data structure and algorithm design. I would suggest that you move it to stack overflow

However, if I understood your question correctly you are trying to build an access control list using a tree data structure which really a nice idea :). If that what you are looking for then Yes it is possible and I suggest reading the paper An Access Control Model for Tree Data Structures

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.