Create merkle-tree based RDF canonicalization spec

[aaronc]

Context

Most commonly used data formats like JSON or protobuf allow multiple binary representations of the same data. For instance JSON or protobuf fields can occur in any order and JSON allows any amount of white space.

Canonicalization refers to a process by which a single binary representation is created for any semantically equivalent document.

URDNA2015 defines such a canonicalization algorithm for the RDF data model.

Proposal

My design is to do something both simpler and more powerful than URDNA2015 using this approach:

• start with an acyclic RDF graph (or dataset) consisting only of blank nodes
• replace blank nodes with IRI's by depth-first traversal using this algorithm:
  • create an empty IAVL merkle tree (or set)
  • take the list of triples (or quads) with this node as its subject
  • map each triple onto a string which is the canonical string serialization of that triples predicate and object concatenated together
  • sort this list
  • insert each item in the list as a key in the IAVL merkle tree (with an empty value)
  • the resulting universally unique IRI for this node is xrn:g/<hash> where <hash> is the hash of this merkle tree (will blake2b 256 hash algorithm work?)

What this approach allows is:

• universally unique, content addressable nodes
• graphs where a subset of the triples can be revealed and their membership in the graph can be proved via a merkle proof

Consequences

References

• https://json-ld.github.io/normalization/spec/
• https://w3c-dvcg.github.io/ld-proofs/#dfn-canonicalization-algorithm