Is there a hash tree scheme designed for complex data structures?

Question

I have a JSON object with private data. It has the following (complex!) structure:

{
    name: "JB",
    age: 35,
    children: 
        [ {
           name: "Alice", 
           age: "5",
           favColor: "pink"
          },
          {
           name: "Bob", 
           age: "8",
           favColor: "blue"
          },
          {
           name: "Charlie", 
           age: "9",
           favColor: "green"
          },
       ]
}

I want to create a hash tree (or similar) that allows others to verify pieces of the data I send them - e.g. by declaring the root on public blockchain. The data structure is arbitrary - it could be anything.

For instance, I'd like to be able to share my age ONLY, and have the receiver be able to compute the hash and check that it is correct. Later, I may want to disclose to a different user that my first child is named "Alice" and her favorite color is "pink".

My understanding is that Merkle Trees are binary - each node has two leaves only - this seems to be the case in the npm libraries I’ve seen. Is there a fixed schema or method for 'flattening' complex structures like the one above into a merkle tree consistently?

Alternatively, is there another type of hash tree structure that provides this kind of complexity innately for data?

For example:

       Root ( = hash of name + age + children)
     /  |  \
    /   |   \
 name  age  children  (= hash of all children in array)
           /      | \
          /       |  \
         /        |   \
      [0]        [1]  [n]
     / | \        
    /  |  \      
 name age favC 

It seems that however the tree is constructed, it is important that the original data's structure is somehow preserved and is can be scrutinised by the validator.

• e.g. to prevent me from providing a child's age instead of my own.
• In the case of a binary merkle tree: to account for the fact that a leaf index may represent entirely different data depending on the number of children they have.

What is the best way to approach this problem? I'm using Node.JS, and the neat Merkle Tools package, but I'm not sure the merkle tree is the right tool for the job.

Another way of phrasing this question is to ask: is there a hashing schema that allows us to consistently render an arbitrary Json object into a hash tree-like structure consistently? And which facilitates validation by sharing the data + the other hashes. Should I just combine a hash table with trees? Or a hash list with certain nodes being trees?

If I've missed anything important out, or you have any clarifying questions, I will do my best to improve the question. I have redirected the question here, on the advice of the S.O main site.

Many thanks.

Answer 1

The general technique for tree hashing (independently of the issue of partially revealing content) is to define the hash of nodes as the hash of the concatenation of the hash of their leaves, with a suffix (or prefix) that makes the input of the hash different for leaves and nodes. Demonstrably, this inherits from the cryptographic hash it's properties of collision-resistance, preimage-resistance, and security in the Random Oracle Model. Proof is left as an exercise to the reader.

The devil is in the details, in particular in

• defining a canonical form of things that must have identical hashes;
• defining if the order of leaves matters;
• if nodes are typed or/and named beyond being a leaf or not (in which case that type/name extension must be hashed);
• making sure that the format of the input of hashes used for such extensions can not lead to collision (perhaps deliberately).

---

I know no ready-made hash standard for JSON, aka ECMA-404. I hereby semi-seriously propose to pick a cryptographic hash such as SHA-512, and define SHA-512-JSON-V1 as:

• The hash of a JSON array is the hash of the concatenation of the hash(es) of its value(s), ordered as they occur in the array; and a final octet 41_h (ASCII A).
• The hash of a JSON object is the hash of the concatenation of an even number of hashe(s), with the first hash of a pair the hash of the name of a member of the object, and the second the hash of the corresponding value, with the pair(s) ordered in lexicographic order of the concatenation of the two hashes of that pair; and a final octet 4F_h (ASCII O).
• The hash of any other JSON value (that is string including a name, number, the special values true, false, null, and anything else not defined by ECMA-404) is the hash of the concatenation of their UTF8 character representation (excluding leading and ending " for strings that came with that, and with conversion to lowercase for the three special values); and a final octet
• 53_h (ASCII S) for string including name
• 4E_h (ASCII N) for number
• 56_h (ASCII V) for yet other value.

---

Notes on object:

• Order of leaves never matters to the hash, since (quoting ECMA-404)

JSON syntax (..) does not assign any significance to the ordering of name/value pairs

• Case matters including in names. Doing otherwise would be a nightmare with unicode, unless we restricted case normalization to ASCII letters.
• Multiple occurrences of the same name in the leaves of an object can be tolerated (as in ECMA-404), or not, without changing the hashing scheme.
• Update per comment: the proposal orders the pairs of hashes (one per per name:value pair in an object) per the concatenation of the two hashes (one for name, the other for value). That ensures the hash result is identical regardless of the order of nodes. If we ordered per the hash of the name only, or per the name, this would not be insured for multiple occurrences of the same name in an object (which is possible, see above bullet). Further, ordering directly per what's hashed allows to substitute ordering with any order-independent hash, enabling a sizable optimization for large objects; see last section of this answer.

Notes on coding of value:

• UTF8 has the advantage that it is compact, endian-neutral, and assigns each unicode point a single representation as octet string (including if it has no UTF-16 representation).
• For example, the hash of JSON's "4\u00e9\u144E\uD834\uDD1E" (the four-character string "4éᑎ𝄞" , with the last character represented by the last two hexadecimal escape sequences), is the hash of the 11 octets
    34_h C3_h A9_h E1_h 91_h 8E_h F0_h 9D_h 84_h 9E_h 53_h
  with 1 (resp. 2, 3, 4 and 1) octet(s) for the first character (resp. second character, third character, fourth character, and suffix octet).
• The question uses a JSON relaxation in which a string used as the name of a field needs not be quoted. It is thus intentionally specified that in an object, age: 35, false:0, True:true, 1e0:42,{}:{},[0]:{} (if accepted by a parser) hashes the same as "age":35, "false":0, "True":true, "1e0":42, "{}":{}, "[0]":{} even though some of the derogatory names could otherwise be of type value, number, object, array.
• Specifying that special value true is hashed in lowercase leaves unspecified if and where True is valid and its type, but specifies that if it is a special value assimilated to JSON's true, then it must hash as the later does.
• More generally, freedom is left for parsing relaxation/extensions: for example, an extra ',' can be allowed before ] or } at the end of an array or object as in the question, or alternatively it can be allowed to omits null after a ','. The hash will follow whatever convention the parser uses.

Notes on coding of number:

• As is, numbers that are equal (in some sense unspecified by JSON) can still have different hashes. For example zero can be (among an infinity of possibilites)
    0   -0   0.0   0e0   0E0   0e+0   0e-0   0e00314
• If we wanted to fix this, there are choices to be made, and they are not easy. For a C compiler, 0.0 and 0 are not the same. For an experimental physicist, 1.2e4 and 1.20e4 are not the same.

Note: It is used a suffix rather than a prefix because that nicely aligns data for object and array, especially for hash algorithms which internal data block size is twice the output size, such as SHA-512.

---

Efficiency: SHA-512-JSON-V1 allow computation of the hash of any JSON of length $n$ in time $\mathcal O(n\log n)$. The $\log n$ term is only due to sorting of the hashes of a large object. We could get rid of this term, and often considerably reduce the memory used, with the technique in the second section of this answer, which outlines how to make an order-independent hash with an online algorithm using constant memory beyond input. We leave this for future extension!

---

Update: There is now an effort to canonicalize JSON, I think solving some of the issues. See RFC 8785.