# Are there conventions for signing JSON as a tree, to allow proofs of signed subtrees?

Given some JSON with a chosen encoding, you can obviously cryptographically-sign the whole thing as a binary blob.

However, it might be useful if the logical structure of the JSON-compatible object were leveraged to control what is signed, in such a way that you could later provide compact proofs that some subtree of the JSON object was signed (without necessarily providing the full JSON object).

For the purposes of illustration, assume the JSON object is a large dictionary, mapping short names to longer blobs, as might be constructed by the following Javascript.

json = { 'A': 'rfhserusliurslierfsieursiuebr',
'B': '384ur3984hfe98r9e8hjf8ej4fj04',
...
'Z': 'xcvubxudgoxduhf9xd88hxd9fybdf',
}


I'm hoping for some robust deterministic convention, already hammered out in a mature spec, for providing a "signature" of this object that does more than a plain signature-of-its-JSON-serialization.

Then, consider a 3rd party that has that signature, plus the full JSON, but only wants/needs to show that the original signer signed something containing:

subset = { 'B': '384ur3984hfe98r9e8hjf8ej4fj04', }


I'm hoping the convention also specifies how this 3rd party can construct a combination of that subset, the signature, and something else about the elided ranges – that still proves the original signer committed to just that subset.

It seems this might already exist – if not already for JSON, then for some other similar hierarchical object model.

One natural approach that 1st comes to mind would involve composing the keys/values/slots of the entire object into a hash tree, and then signing the root. With suitable tricks, this might allow the 3rd party to prove any subset, like the one above, in a compact (or even fixed-size) way. (But maybe there are other techniques, involving composable signatures, zk-proofs, redactable-hashing, etc - the goal is more important than the mechanism.)

Does anyone know of applicable conventions/standards/published-techniques? Just names or references of related prior work, for further searching/reading, would be great answers.

• How is this question different from this one ? When I looked at it, I found nothing existing, and concluded that the difficulty of the exercise is defining exactly what two JSON with the same content are.This is especially hairy for numbers. – fgrieu Feb 24 '19 at 7:50
• Both questions give examples that are not strictly conforming JSON. Both allow to end enumerations with ,} or ,] where there should be no ,. The present one quotes with ' where that should be ". The other did not quote object tags. There is no indication that it is intentional in either. This raises the issue of if two object differing by the aforementioned details should have identical hash. I wish the question would be trimmed to specify purely standard JSON. It's complex enough ! – fgrieu Feb 24 '19 at 8:16
• While the other Q is related, & the @fgrieu sketch-of-a-possible-approach is interesting, they're not quite the same. Here, I'm requesting info about potentially-applicable existing conventions/standards. And while I suspect a hash tree might be involved, I'd be open to other constructions. (Accumulators? New combinable signature schemes?) Maybe there are none yet (given few responses so far), maybe they're just too obscure, or maybe they'll arrive soon. But for this question, a bespoke-in-another-StackExchange-answer rough-approach-outline wouldn't earn the same 'accepted' check that Q got. – gojomo Feb 26 '19 at 6:06
• Also, while JSON is the motivating/concrete case, as I mentioned, I'd be equally interested in conventions on other similar data structures. That is, this is a matter of data-structures & what cryptography might deliver the desired results, not really JS/JSON. By closing it as if "duplicate" or "answered", there's much less chance for someone who does know an applicable existing practice – perhaps even one that's novel since the question was asked, or since @fgrieu's research/attempt – to give a responsive answer. – gojomo Feb 26 '19 at 6:10
• Is the question about signing an abstract tree so that it can be later provided compact proofs that some subtree is part of what's signed, without providing the rest of the tree? It can be a fine new question, or an edit of this one (and not a dupe of the linked Q). Does leaf order matter? Are labeled leafs essential? I know no standard or reference (only asking for one is off-topic). "Given some JSON with a chosen encoding" ruined my reading of the question, making me focus on the difficulty of defining part of a JSON tree, and discrepancies of the examples w.r.t. JSON syntax. – fgrieu Feb 26 '19 at 7:39