RDF [RDF11-CONCEPTS] describes a graph-based data model for making claims
about the world and provides the foundation for reasoning upon that graph
of information. At times, it becomes necessary to compare the differences
between sets of graphs, digitally sign them, or generate short identifiers
for graphs via hashing algorithms. This document outlines an algorithm for
normalizing RDF datasets such that these operations can be
performed.
Status of This Document
This section describes the status of this
document at the time of its publication. A list of current W3C
publications and the latest revision of this technical report can be found
in the W3C technical reports index at
https://www.w3.org/TR/.
At the time of publication, [RDF11-CONCEPTS] is the most recent recommendation
defining RDF datasets and [N-QUADS],
however work on an updated specification
is ongoing within the W3C RDF-star Working Group.
Some dependencies from relevant updated specifications are provided
normatively in this specification with the expectation
that a future update to this specification will replace those with normative
references to updated RDF specifications.
Publication as a Working Draft does not
imply endorsement by W3C and its Members.
This is a draft document and may be updated, replaced or obsoleted by other
documents at any time. It is inappropriate to cite this document as other
than work in progress.
This document was produced by a group
operating under the
W3C Patent
Policy.
W3C maintains a
public list of any patent disclosures
made in connection with the deliverables of
the group; that page also includes
instructions for disclosing a patent. An individual who has actual
knowledge of a patent which the individual believes contains
Essential Claim(s)
must disclose the information in accordance with
section 6 of the W3C Patent Policy.
When data scientists discuss canonicalization,
they do so in the context of achieving a particular set of goals.
Since the same information may sometimes be expressed in a variety of different ways,
it often becomes necessary to transform each of these
different ways into a single, standard representation.
With a standard representation, the differences between
two different sets of data can be easily determined,
a cryptographically-strong hash identifier can be generated for a particular
set of data,
and a particular set of data may be digitally-signed for later
verification.
In particular, this specification is about normalizing
RDF datasets, which are collections of graphs. Since
a directed graph can express the same information in more than one
way, it requires canonicalization to achieve the aforementioned goals
and any others that may arise via serendipity.
Most RDF datasets can be canonicalized fairly quickly, in terms
of algorithmic time complexity. However, those that contain nodes that do
not have globally unique identifiers pose a greater challenge. Normalizing
these datasets presents the graph isomorphism problem, a
problem that is believed to be difficult to solve quickly in the worst
case. Fortunately, existing real world data is rarely, if ever, modeled in
a way that manifests as the worst case and new data can be modeled to avoid
it. In fact, software systems that detect a problematic dataset
(see 7.1 Dataset Poisoning) can choose
to assume it's an attempted denial of service attack, rather than a
real input, and abort.
This document outlines an algorithm for generating a canonical
serialization of an RDF dataset given an RDF dataset as input.
The algorithm is called the
RDF Canonicalization algorithm version 1.0 or
RDFC-1.0.
The Canonicalization algorithm is based on the RDF 1.1 definition,
in the sense that the language tagxx-YY
is case insensitive, which might lead to different canonicalizations if the user is not aware of this problem.
User communities ought to agree to use lower case
language tags,
while being aware that some implementations might normalize language tags,
affecting hash values.
Future evolution of RDF might regulate this issue, which RDF environments might have to adapt to,
and this might lead to an update of RDFC-1.0.
There are different use cases where graph or dataset canonicalization are important:
Determining if one serialization is isomorphic to another.
Digital signing of graphs (datasets) independent of serialization or format.
Comparing two graphs (datasets) to find differences.
Communicating change sets when remotely updating an RDF source.
A canonicalization algorithm is necessary, but not necessarily sufficient, to handle many of these use cases. The use of blank nodes in RDF graphs and datasets has a long history and creates inevitable complexities. Blank nodes are used for different purposes:
when a well known identifier for a node is not known, or the author of a document chooses not to unambiguously name that node,
when a node is used to stitch together parts of a graph and the nodes themselves are not interesting (e.g., RDF Collections in [RDF11-MT]),
when someone is trying to create an intentionally difficult graph topology.
Furthermore,
RDF semantics dictate that deserializing an RDF document
results in the creation of unique blank nodes,
unless it can be determined that on each occasion,
the blank node identifies the same resource.
This is due to the fact that blank node identifiers
are an aspect of a concrete RDF syntax
and are not intended to be persistent or portable.
Within the abstract RDF model,
blank nodes do not have identifiers
(although some
RDF store
implementations may use stable identifiers and may choose to make them portable).
See Blank Nodes
in [RDF11-CONCEPTS] for more information.
RDF does have a provision for allowing blank nodes
to be published in an externally identifiable way through the use of
Skolem IRIs,
which allow a given RDF store to replace the use of blank nodes
in a concrete syntax with IRIs,
which then serve to repeatably identify that blank node within that particular RDF store;
however, this is not generally useful for talking about the
same graph in different RDF stores,
or other concrete representations.
In any case, a stable blank node identifier defined for one
RDF store or serialization is arbitrary,
and typically not relatable to the context within which it is used.
This specification defines an algorithm for creating stable
blank node identifiers repeatably for different serializations
possibly using individualized blank node identifiers
of the same RDF graph (dataset) by grounding each blank node
through the nodes to which it is connected.
As a result, a graph signature can be obtained by hashing a canonical serialization
of the resulting canonicalized dataset,
allowing for the isomorphism and digital signing use cases.
As blank node identifiers can be stable even with other changes to a graph (dataset),
in some cases it is possible to compute the difference between two graphs (datasets),
for example if changes are made only to ground triples,
or if new blank nodes are introduced which do not create an automorphic confusion
with other existing blank nodes.
If any information which would change the generated blank node identifier,
a resulting diff might indicate a greater set of changes than actually exists.
Additionally, if the starting dataset is an N-Quads document,
it may be possible to correlate the original blank node identifiers
used within that N-Quads document with those issued in the
canonicalized dataset.
1.2 How to Read this Document
This document is a detailed specification for an RDF dataset
canonicalization algorithm. The document is primarily intended for the
following audiences:
Software developers that want to implement an RDF dataset
canonicalization algorithm.
Masochists.
To understand the basics in this specification you must be familiar with
basic RDF concepts [RDF11-CONCEPTS]. A working knowledge of
graph theory and
graph isomorphism
is also recommended.
1.3 Typographical conventions
This section is non-normative.
The following typographic conventions are used in this specification:
markup
Markup (elements, attributes, properties),
machine processable values (string, characters, media types),
property names,
and file names are in red-orange monospace font.
variable
A variable in pseudo-code or in an algorithm description is italicized.
definition
A definition of a term, to be used elsewhere in this or other specifications,
is italicized and in bold.
References to a definition in this document,
when the reference itself is also a markup, is underlined,
in a red-orange monospace font, and is also an active link to the definition itself.
A reference to a definition in another document,
when the reference itself is also a markup,
is underlined and italicized in a red-orange monospace font,
and is also an active link to the definition itself.
A document reference (normative or informative) is enclosed in square brackets
and links to the references section.
Explanation
An expandable area to find a more detailed, non-normative explanation of a
particular algorithmic step.
Explanation
This area would provide more information about the step involved.
Logging
An expandable area to find suggestions for implementations to log
information about processing,
which may be useful in comparing with other implementations,
or with logs provided with each test case.
Logging
For example, the following output snippet might
describe the operation of an implementation using the [YAML] format.
Examples are in light khaki boxes, with khaki left border,
and with a numbered "Example" header in khaki.
Examples are always informative. The content of the example is in monospace font and may be
syntax colored.
Examples may have tabbed navigation buttons
to show the results of transforming an example into other representations.
Code examples are generally given in a Turtle or TriG format for brevity,
where each line represents a single triple or quad.
Additionally, have the following implied directives:
BASE <http://example.com/>
PREFIX : <#>
Following the Turtle/TriG syntax rules, blank nodes always appear in the
`_:xyz` format.
2. Conformance
As well as sections marked as non-normative, all authoring guidelines, diagrams, examples, and notes in this specification are non-normative. Everything else in this specification is normative.
The key words MUST, MUST NOT, and SHOULD in this document
are to be interpreted as described in
BCP 14
[RFC2119] [RFC8174]
when, and only when, they appear in all capitals, as shown here.
A conforming processor is a system which can generate
the canonical n-quads form of an input dataset
consistent with the algorithms defined in this specification.
The algorithms in this specification are normative,
because to consistently reproduce the same canonical identifiers,
implementations MUST strictly conform to the steps outlined in these algorithms.
Note
Implementers can partially check their level of conformance with
this specification by successfully passing the test cases of the
RDF Dataset Canonicalization test suite.
Note, however, that passing all the tests in the test
suite does not imply complete conformance to this specification. It only implies
that the implementation conforms to the aspects tested by the test suite.
A particular enumeration of every incident mention emanating
from a blank node. This recursively includes transitively related
mentions until any named node or blank node already labeled by
a particular identifier issuer is reached. Gossip paths are
encoded and operated on in the RDFC-1.0 algorithm as strings. (See
4.8 Hash N-Degree Quads for more information
on the construction of gossip paths.)
hash
The lowercase, hexadecimal representation of a message digest.
hash algorithm
The default hash algorithm used by RDFC-1.0, namely, SHA-256 [FIPS-180-4].
Implementations MUST support a parameter to define the hash algorithm,
MUST support SHA-256 and SHA-384 [FIPS-180-4],
and SHOULD support the ability to specify other hash algorithms.
Using a different hash algorithm will generally result in different output than
using the default.
Records any blank node identifiers already assigned to the
input dataset.
If the input dataset is provided as an N-Quads document,
the map relates blank nodes in the abstract input dataset
to the blank node identifiers used within the N-Quads document,
otherwise, identifiers are assigned arbitrarily for
each blank node in the input dataset not previously identified.
Note
Implementations or environments might deal with blank
node identifiers more directly; for example, some implementations might
retain blank node identifiers in the parsed or abstract dataset. Implementations
are expected to reuse these to enable usable mappings between input blank node
identifiers and output blank node identifiers outside of the algorithm.
input dataset
The abstract RDF dataset that is provided as input to
the algorithm.
A blank node identifier
as specified by [RDF11-CONCEPTS]. In short, it is a string that begins
with _: that is used as an identifier for a
blank node. Blank node identifiers
are typically implementation-specific local identifiers; this document
specifies an algorithm for deterministically specifying them.
Concrete syntaxes, like [Turtle] or [N-Quads], prepend blank node identifiers with the _: string
to differentiate them from other nodes in the graph. This affects the
canonicalization algorithm, which is based on calculating a hash over the representations of quads in this format.
Canonicalization is the process of transforming an
input dataset to its serialized canonical form.
That is, any two input datasets that contain the same information,
regardless of their arrangement,
will be transformed into the same serialized canonical form.
The problem requires directed
graphs to be deterministically ordered into sets of nodes and edges. This
is easy to do when all of the nodes have globally-unique identifiers, but
can be difficult to do when some of the nodes do not. Any nodes without
globally-unique identifiers must be issued deterministic identifiers.
Note
This specification defines a canonicalized dataset to include stable identifiers for blank nodes,
practical uses of which will always generate a canonical serialization of such a dataset.
In time, there may be more than one canonicalization algorithm and,
therefore, for identification purposes, this algorithm is named the
"RDF Canonicalization algorithm version 1.0"
(RDFC-1.0).
Figure 1 provides an overview of RDFC-1.0,
with steps 1 through 7 corresponding to the various steps described in
4.4.3 Algorithm.
To determine a canonical labeling, RDFC-1.0 considers the
information connected to each blank node.
Nodes with unique first degree information can immediately be issued a canonical identifier
via the Issue Identifier algorithm.
When a node has non-unique first degree information,
it is necessary to determine all information that is transitively connected
to it throughout the entire dataset.
4.6 Hash First Degree Quads defines a
node’s first degree information via its first degree hash.
Hashes are computed from the information of each blank node.
These hashes encode the mentions incident to each blank node.
The hash of a string s, is the lower-case,
hexadecimal representation of the result of passing s
through a cryptographic hash function.
By default, RDFC-1.0 uses the SHA-256 hash algorithm [FIPS-180-4].
Note
The "degree" terminology is used within this specification
as colloquial way of describing
the eccentricity or
radius
of any two nodes within a dataset.
This concept is also related to "degrees of separation",
as in, for example, "six degrees of separation".
Nodes with unique first degree information can be considered nodes with a radius of one.
4.2 Canonicalization State
When performing the steps required by the canonicalization algorithm,
it is helpful to track state in a data structure called the
canonicalization state. The information contained in the
canonicalization state is described below.
Mapping all blank nodes to use this
identifier spec means that an RDF dataset composed of two
different RDF graphs will issue different
identifiers than that for the graphs taken independently. This may
happen anyway, due to automorphisms,
or overlapping statements, but an identifier based on the resulting
hash along with an issue sequence number specific to that hash would
stand a better chance of surviving such minor changes, and allow the
resulting information to be useful for RDF Diff.
The identifier prefix is a string that is used at the beginning of an
blank node identifier. It should be initialized to a
string that is specified by the canonicalization algorithm. When
generating a new blank node identifier, the prefix
is concatenated with a identifier counter. For example,
c14n is a proper initial value for the
identifier prefix that would produce
blank node identifiers like c14n1.
An ordered map that relates blank node identifiers to issued identifiers,
to prevent issuance of more than one new identifier per existing identifier,
and to allow blank nodes to
be assigned identifiers some time after issuance.
RDFC-1.0 canonically labels an RDF dataset
by assigning each blank node a canonical identifier.
In RDFC-1.0, an RDF dataset D
is represented as a set of quads of the form < s, p, o, g >
where the graph component g is empty if and only if the
triple< s, p, o > is in the default graph.
It is expected that, for two RDF datasets,
RDFC-1.0 returns the same canonically labeled list of quads
if and only if the two datasets are isomorphic (i.e., the same modulo blank node identifiers).
RDFC-1.0 consists of several sub-algorithms.
These sub-algorithms are introduced in the following sub-sections.
First, we give a high level summary of RDFC-1.0.
Compute N-degree hashes for non-unique nodes.
For each repeated first degree hash (proceeding in Unicode code point order),
compute the N-degree hash via 4.8 Hash N-Degree Quads
of every unlabeled blank node that corresponds to the given repeated hash.
Canonically label remaining nodes.
In Unicode code point order of the N-degree hashes,
issue canonical identifiers to each corresponding blank node using
4.5 Issue Identifier Algorithm.
If more than one node produces the same N-degree hash,
the order in which these nodes receive a canonical identifier does not matter.
The following algorithm will run with a minimal number of iterations in each step
for typical input datasets.
In some extreme cases, the algorithm can behave poorly, particularly in Step 5.
Implementations MUST prevent against potential denial-of-service attacks.
See 7.1 Dataset Poisoning for further information.
Note
Implementations can consider placing limits on the number of
calls to 4.8 Hash N-Degree Quads based on the number
of blank nodes in the hash to blank nodes map.
For most typical datasets, more than a couple
of iterations on 4.8 Hash N-Degree Quads per blank node would be unusual.
This establishes the blank node to quads map,
relating each blank node with the set of quads
of which it is a component,
via the map for each blank node in the input dataset to its assigned identifier.
This step creates a hash for every blank node in the input document.
Some blank nodes will lead to a unique hash,
while other blank nodes may share a common hash.
This step establishes the canonical identifier for blank nodes having
a shared hash.
This is done by creating unique blank node identifiers for all
blank nodes traversed by the Hash N-Degree Quads algorithm,
running through each blank node without a canonical identifier in the order
of the hashes established in the previous step.
Logging
Log hash and identifier list for this iteration.
# Hash and Identifier List for each iteration of step 5 using shared hashes example
ca:
...
ca.5:
log point: Calculate hashes for identifiers with shared hashes (4.4.3 (5)).
with:
- hash: 3b26142829b8887d011d779079a243bd61ab53c3990d550320a17b59ade6ba36
identifier list: [ "e0", "e1"]
......
# Logs from calls to Hash N-Degree Quads algorithm for shared hashes example
ca:
...
ca.5:
log point: Calculate hashes for identifiers with shared hashes (4.4.3 (5)).
with:
- hash: 3b26142829b8887d011d779079a243bd61ab53c3990d550320a17b59ade6ba36
identifier list: [ "e0", "e1"]
ca.5.2:
log point: Calculate hashes for identifiers with shared hashes (4.4.3 (5.2)).
with:
- identifier: e0
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
............
For each result in the hash path list,
code point ordered by the hash in result:
Explanation
The previous step created temporary identifiers for the
blank nodes sharing a common first degree hash,
which is now used to generate their canonical identifiers.
For each blank node identifier,
existing identifier, that was issued a temporary
identifier by identifier issuer in result,
issue a canonical identifier,
in the same order,
using the Issue Identifier algorithm,
passing canonical issuer and existing identifier.
Explanation
In Step 5.2,
hash path list was created with an ordered
set of results.
Each result contained a temporary issuer
which recorded temporary identifiers associated with
a particular blank node identifier in
identifier list.
This step processes each returned temporary issuer,
in order, and allocates canonical identifiers
to the temporary identifier mappings contained
within each temporary issuer,
creating a full order on the remaining blank nodes
with unissued canonical identifiers.
Technically speaking, one implementation
might return a canonicalized dataset that maps
particular blank nodes to different identifiers than another
implementation, however, this only occurs when there are
isomorphisms in the dataset such that a canonically serialized
expression of the dataset would appear the same from either
implementation.
Explanation
The serialized canonical form is an N-Quads
document where the blank node identifiers are taken
from the canonical identifiers associated with each blank node.
This algorithm issues a new blank node identifier for
a given existing blank node identifier. It also updates
state information that tracks the order in which new
blank node identifiers were issued. The order of issuance is
important for canonically labeling blank nodes that are isomorphic
to others in the dataset.
This algorithm calculates a hash for a given blank node
across the quads in a dataset in which that blank node
is a component.
If the hash uniquely identifies that blank node,
no further examination is necessary.
Otherwise, a hash will be created for the blank node using
the algorithm in 4.8 Hash N-Degree Quads
invoked via 4.4 Canonicalization Algorithm.
4.6.1 Overview
This section is non-normative.
To determine whether the first degree information of a node n is unique,
a hash is assigned to its mention set,
Qn.
The first degree hash of a blank node n,
denoted hf(n),
is the hash that results from 4.6 Hash First Degree Quads
when passing n.
Nodes with unique first degree hashes have unique first degree information.
For consistency, blank node identifiers used in Qn
are replaced with placeholders in a canonical n-quads serialization of that quad.
Every blank node component is replaced with either a or z,
depending on if that component is n or not.
The resulting serialized quads are then code point ordered,
concatenated, and hashed.
This hash is the first degree hash of n, hf(n).
4.6.2 Examples
This section is non-normative.
4.6.3 Algorithm
This algorithm takes the canonicalization state and a
reference blank node identifier as inputs.
Return the hash that results from passing the sorted
and concatenated nquads through the
hash algorithm.
Logging
Log the inputs and result of running this algorithm.
# Inputs and hash result for the Hash First Degree Hash algorithm for unique hashes example
h1dq:
log point: Hash First Degree Quads function (4.6.3).
nquads:
- <http://example.com/#p> <http://example.com/#q> _:a .
- _:a <http://example.com/#s> <http://example.com/#u> .
hash: 21d1dd5ba21f3dee9d76c0c00c260fa6f5d5d65315099e553026f4828d0dc77a
4.7 Hash Related Blank Node
This algorithm generates a hash for some
blank node component of a quad,
considering its position within that quad.
This is used as part of the
Hash N-Degree Quads algorithm
to characterize the blank nodes related to some particular blank node
within their mention sets.
4.7.1 Overview
This section is non-normative.
An identifier for a blank node, related,
which is a component of some quad, is used along
with information describing its position within the quad to create
a representation of that blank node within the quad,
which is then hashed.
The identifier is first found from the following:
Initialize a stringinput to the value of
position.
If position is not g, append
<, the value of the predicate in
quad, and > to input.
If there is a canonical identifier for related,
or an identifier issued by issuer,
append the string _:, followed by that identifier (using the canonical
identifier if present, otherwise the one issued by issuer) to
input.
Explanation
If a canonical identifier was already issued for related,
it will be in the canonical issuer contained within
canonicalization state.
Otherwise, the temporary issuer instance may already
have a mapping for related.
Return the hash that results from passing input
through the hash algorithm.
Explanation
This resulting string is used to generate a hash; in this respect, it is similar to
the Hash First Degree Quads algorithm which
uses the serialization of quads in nquads for hashing. For the sake of consistency, the
nquad representation of identifier is used in this step, hence the
appearance of the _: string.
Logging
Log the inputs and result of running this algorithm.
# Inputs and hash result for the Hash Related Blank algorithm for shared hashes example
hndq3.1:
log point: Hash related bnode component (4.8.3 (3.1))
with:
- position: o
related: e2
input: "o<http://example.com/#p>_:c14n0"
hash: 29cf7e22790bc2ed395b81b3933e5329fc7b25390486085cac31ce7252ca60fa
4.8 Hash N-Degree Quads
This algorithm calculates a hash for a given blank node
across the quads in a dataset in which that blank node
is a component for which the hash does not uniquely identify that blank node.
This is done by expanding the search from quads directly referencing that
blank node (the mention set), to those quads
which contain nodes which are also components of quads in the mention set,
called the gossip path.
This process proceeds in every greater degrees of indirection until
a unique hash is obtained.
4.8.1 Overview
This section is non-normative.
Usually, when trying to determine if two nodes in a graph are
equivalent, you simply compare their identifiers. However, what if the
nodes don't have identifiers? Then you must determine if the two nodes
have equivalent connections to equivalent nodes all throughout the
whole graph. This is called the graph isomorphism problem. This
algorithm approaches this problem by considering how one might draw
a graph on paper. You can test to see if two nodes are equivalent
by drawing the graph twice. The first time you draw the graph the
first node is drawn in the center of the page. If you can draw the
graph a second time such that it looks just like the first, except
the second node is in the center of the page, then the nodes are
equivalent. This algorithm essentially defines a deterministic way to
draw a graph where, if you begin with a particular node, the graph
will always be drawn the same way. If two graphs are drawn the same way
with two different nodes, then the nodes are equivalent. A
hash is used to indicate a particular way that the graph
has been drawn and can be used to compare nodes.
When two blank nodes have the same first degree hash,
extra steps must be taken to detect global,
or N-degree, distinctions.
All information that is in any way connected to the blank node n
through other blank nodes, even transitively, must be considered.
To consider all transitive information,
the algorithm traverses and encodes all possible paths of incident
mentions emanating from n, called gossip paths,
that reach every unlabeled blank node connected to n.
Each unlabeled blank node is assigned a temporary identifier
in the order in which it is reached in the
gossip path being explored.
The mentions that are traversed to reach
connected blank nodes are encoded in these paths via related hashes.
This provides a deterministic way to order all paths coming from n that
reach all blank nodes connected to n without relying on input blank
node identifiers.
This algorithm works in concert with the main canonicalization algorithm
to produce a unique, deterministic identifier for a particular blank
node. This hash incorporates all of the information that
is connected to the blank node as well as how it is connected. It does
this by creating deterministic paths that emanate out from the blank
node through any other adjacent blank nodes.
Ultimately, the algorithm selects the shortest gossip path
(based on its encoding as a string), distributing canonical
identifiers to the unlabeled blank nodes in the order in which they
appear in this path.
The hash of this encoded shortest path,
called the N-degree hash of n,
distinguishes n from other blank nodes in the dataset.
For clarity, we consider a gossip path encoded via the string s
to be shortest provided that:
The length of s is less than or equal to the length
of any other gossip path string s′.
If s and s′ have the same length (as strings),
then s is code point ordered less than or equal to s′.
For example, abc is shorter than bbc,
whereas abcd is longer than bcd.
The following provides a high level outline for how the N-degree hash of n
is computed along the shortest gossip path.
Note that the full algorithm considers all gossip paths,
ultimately returning the hash of the shortest encoded path.
Compute related hashes.
Compute the related hash Hn set for n,
i.e., all first degree mentions between n and another blank node.
Note that this includes both unlabeled blank nodes and those
already issued a canonical identifier (labeled blank nodes).
Explore mentions.
Given the related hash x in Hn,
record x in the data to hash Dn.
Determine whether each blank node reachable via the mention with related hash x
has already received an identifier.
Record the identifiers of labeled nodes.
If a blank node already has an identifier,
record its identifier in Dn once for every
mention with related hash x.
Skip to the next related hash in Hn
and repeat step 2.
Distribute and record temporary identifiers to unlabeled nodes.
For each unlabeled blank node,
assign it a temporary identifier according to the order in which it is reached in the gossip path,
recording its given identifier in Dn (including repetitions).
Add each unlabeled node to the recursion list Rn(x)
in this same order (omitting repetitions).
Recurse on newly labeled nodes.
For each ni in Rn(x)
Record its identifier in Dn
Append < r(i) > to Dn
where r(i) is the data to hash that results from returning to
step 1,
replacing n with ni.
Compute the N-degree hash of n.
Hash Dn to return the N-degree hash of n,
namely hN(n).
Return the updated issuer In
that has now distributed temporary identifiers to all unlabeled blank nodes connected to n.
As described above in step 2.3,
HN recurses on each unlabeled blank node
when it is first reached along the gossip path being explored.
This recursion can be visualized as moving along the path from n
to the blank node ni that is receiving a temporary identifier.
If, when recursing on ni,
another unlabeled blank node nj is discovered,
the algorithm again recurses.
Such a recursion traces out the gossip path from n
to nj via ni.
The recursive hash r(i) is the hash returned from
the completed recursion on the node ni
when computing hN(n).
Just as hN(n) is the hash of Dn,
we denote the data to hash in the recursion on ni
as Di.
So, r(i) = h(Di).
For each related hash x ∈ Hn,
Rn(x) is called the recursion list on
which the algorithm recurses.
# Inputs for the Hash N-Degree Quads algorithm for double circle example
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
Create a new mapHn
for relating hashes to related blank nodes.
For each related hash to blank node list mapping in
Hn, code point ordered
by related hash:
Explanation
This loop explores the gossip paths for each
related blank node sharing a common hash to identifier
finding the shortest such path (chosen path).
This determines how canonical identifiers for
otherwise commonly hashed blank nodes are chosen.
Each path is represented by the concatenation of the
identifiers for each related blank node
– either the issued identifier,
or a temporary identifier created using a copy of issuer.
Those for which temporary identifiers were issued are later
recursed over using this algorithm.
Logging
Log the value of related hash
and state of data to hash.
# Log related hash and data to hash in each iteration of step 5 for double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
...
Create a recursion list, to store
blank node identifiers that must be
recursively processed by this algorithm.
For each related in p:
If a canonical identifier has been issued for
related by canonical issuer, append the string _:, followed by
the canonical identifier for related, to path.
Explanation
A canonical identifier may have been generated before calling this algorithm,
if it was issued from an earlier call to Hash First Degree Quads algorithm.
There is no reason to recurse and apply the algorithm to any related blank node that has already been assigned a canonical identifier.
Furthermore, using the canonical identifier also further distinguishes it from any temporary identifier, allowing for even greater efficiency in finding the chosen path.
Otherwise:
If issuer copy has not issued
an identifier for related, append
related to recursion list.
Explanation
Temporarily labeled nodes have identifiers recorded
in issuer copy,
which is later used to recursively call this algorithm,
so that eventually all nodes are given canonical identifiers.
Use the
Issue Identifier algorithm,
passing issuer copy and the related, and
append the string _:, followed by the result, to path.
If chosen path is not empty and the length
of path is greater than or equal to the length
of chosen path and path is
greater than chosen path when
considering code point order,
then skip to the next
permutationp.
Explanation
If path is already longer than
the prospective chosen path,
we can terminate this iteration early.
Explanation
path is used to generate a hash at a later step; in this respect, it is similar to
the Hash First Degree Quads algorithm which
uses the serialization of quads in nquads for hashing. For the sake of consistency, the
nquad representation of blank node identifiers is used in these steps, hence the
usage of the _: string.
Logging
Log related and path.
# Log related and path of step 5.4.4 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
hndq.5.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4)), entering loop.
with:
- perm: [ "e1"]
hndq.5.4.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4.4)), entering loop.
with:
- related: e1
path: ""
...
For each related in recursion list:
Explanation
The prospective path is extended with
the hash resulting from recursively calling this algorithm
on each related blank node issued a temporary identifier.
Logging
Log recursion list and path.
# Log related and path of step 5.4.5 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
hndq.5.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4)), entering loop.
with:
- perm: [ "e1"]
...
hndq.5.4.5:
log point: Hash N-Degree Quads function (4.8.3 (5.4.5)), before possible recursion.
recursion list: [ "e1"]
path: "_:b1"
...
If chosen path is not empty and the length
of path is greater than or equal to the length
of chosen path and path is
greater than chosen path when considering code point order,
then skip to the next p.
Explanation
If path is already longer than
the prospective chosen path,
we can terminate this iteration early.
If chosen path is empty or path is
less than chosen path when considering code point order,
set chosen path to path and chosen issuer
to issuer copy.
Append chosen path to data to hash.
Logging
Log chosen path and data to hash.
# Log chosen path and data to hash logs of step 5.5 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
...
hndq.5.5:
log point: Hash N-Degree Quads function (4.8.3 (5.5). End of current loop with Hn hashes.
chosen path: "_:b1_:b1<1ae899f76e760eb7caf6656437aaef845b50887aff7baeb3531add85ec02ed35>"
data to hash: "1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d_:b1_:b1<1ae899f76e760eb7caf6656437aaef845b50887aff7baeb3531add85ec02ed35>"
...
Replace issuer, by reference, withchosen issuer.
Return issuer and the hash that results from
passing data to hash through the
hash algorithm.
Logging
Log issuer and results from passing data to hash
through the hash algorithm.
# Log issuer and resulting hash of step 6 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.6:
log point: Leaving Hash N-Degree Quads function (4.8.3).
hash: e332b4b59e1c4794ee72a4df0f63723326ffb6d6a5c0d0cb4d2dd8d8d5ebf5a4
issuer: {e0: b0, e1: b1}
5. Serialization
This section describes the process of creating a serialized [N-Quads] representation
of a canonicalized dataset.
The nature of the canonicalization algorithm inherently correlates its output,
i.e., the canonical labels and the sorted order of quads, with the input dataset.
This could pose issues, particularly when dealing with datasets containing personal information.
For example, even if certain information is removed from the canonicalized dataset
for some privacy-respecting reason, there remains the possibility that a third party
could infer the omitted data by analyzing the canonicalized dataset.
If it is necessary to decouple the canonicalization algorithm's input and output,
some suitable post-processing methods for the output of the canonicalization should be performed.
This specification has been designed to help make additional processing easier, but
other specifications that build on top of this one are responsible for providing any
specific details.
See Selective Disclosure
in Verifiable Credential Data Integrity 1.0 [VC-DATA-INTEGRITY] for more details about such
post-processing methods.
7. Security Considerations
This section is non-normative.
7.1 Dataset Poisoning
This section is non-normative.
The canonicalization algorithm examines every difference in the
information connected to blank nodes in order to ensure that each will
properly receive its own canonical identifier. This process can be
exploited by attackers to construct datasets which are known to take
large amounts of computing time to canonicalize, but that do not express
useful information or express it using unnecessary complexity.
Implementers of the algorithm are expected to add mitigations that will,
by default, abort canonicalizing problematic inputs.
Suggested mitigations include, but are not limited to:
providing a configurable timeout with a default value applicable to
an implementation's common use
providing a configurable limit on the number of iterations of steps
performed in the algorithm, particularly recursive steps
and permutations of long lists
Additionally, software that uses implementations of the algorithm can
employ best-practice schema validation to reject data that does not meet
application requirements, thereby preventing useless poison datasets from
being processed. However, such mitigations are application specific and
not directly applicable to implementers of the canonicalization algorithm
itself.
7.2 Insecure Hash Algorithms
This section is non-normative.
It is possible that the default hash algorithm used by RDFC-1.0 might become
insecure at some point in the future. To mitigate this, this algorithm
and implementations of it can be parameterized to use a different
hash function, without the need to make any changes to the
canonicalization algorithm itself.
However, using a different hash algorithm will generally lead to different results.
The Explainer document provides a good basis for the WG's work. However, during the evolution of the c14n spec, we have recognized further features that need to be documented. Therefore, the use cases section of the spec can usefully be filled with a reference to the explainer doc plus some text around the features around output formats and mappings.
9. Examples
This section is non-normative.
9.1 Duplicate Paths
This example illustrates a more complicated example where the same paths
through blank nodes are duplicated in a graph, but use different
blank node identifiers.
Figure 7An illustration of a graph with duplicated paths.
Image available in
SVG
.
The example is not explored in detail, but the
execution log found here
shows examples of more complicated
pathways through the algorithm
9.3 Dataset with Blank Node Named Graph
This example illustrates an example of a dataset,
where one graph is named using a blank node,
which is also the object of a triple in the default graph.
Figure 9An illustration of a dataset containing a graph named with a blank node.
Image available in
SVG
.
While the N-Quads syntax [N-QUADS] allows choices for the representation and layout of RDF data,
the canonical form of N-Quads provides a unique syntactic representation of any quad.
Each code point
can be represented by only one of
UCHAR,
ECHAR,
or unencoded character,
where the relevant production allows for a choice in representation.
Each quad is represented entirely on a single line with specified white space.
Canonical N-Quads has the following additional constraints on layout:
White space MUST NOT be used except after
subject,
predicate,
object,
and graphLabel,
each of which MUST be a single space (code point U+0020).
Literals with the
datatype http://www.w3.org/2001/XMLSchema#stringMUST NOT use the datatype IRI part of the literal,
and are represented using only STRING_LITERAL_QUOTE.
HEXMUST use only digits ([0-9]) and uppercase letters ([A-F]).
Characters
BS (backspace, code point U+0008),
HT (horizontal tab, code point U+0009),
LF (line feed, code point U+000A),
FF (form feed, code point U+000C),
CR (carriage return, code point U+000D),
" (quotation mark, code point U+0022), and
\ (backslash, code point U+005C)
MUST be encoded using ECHAR.
Characters in the range from U+0000 to U+0007,
VT (vertical tab, code point U+000B),
characters in the range from U+000E to U+001F,
DEL (delete, code point U+007F),
and characters not matching the Char production from [XML11]
MUST be represented by UCHAR
using a lowercase \u with 4 HEXes.
All characters not required to be represented by
ECHAR or
UCHARMUST be represented by their native [UNICODE] representation.
The token EOLMUST be a single LF (line feed, code point U+000A).
RDF Dataset Canonicalization [CCG-RDC-FINAL] describes
"Universal RDF Dataset Normalization Algorithm 2015"
(URDNA2015),
essentially the same algorithm
as RDFC-1.0, and generally implementations implementing URDNA2015
should be compatible with this specification.
The minor change is in the canonical n-quads form where
some control characters were previously represented without escaping.
The version of the algorithm defined in A. A Canonical form of N-Quads
clarifies the representation of simple literals and the characters
within STRING_LITERAL_QUOTE
that are encoded using ECHAR.
C. URGNA2012
This section is non-normative.
A previous version of this algorithm has light deployment. For purposes of identification,
the algorithm is called the
"Universal RDF Graph Canonicalization Algorithm 2012"
(URGNA2012),
and differs from the stated algorithm in the following ways:
In 4.8 Hash N-Degree Quads, the position parameter passed to
the Hash Related Blank Node algorithm
was instead modeled as a direction parameter, where it could have
the value p, for property, when the related blank node was a
subject and the value r, for reverse or reference, when
the related blank node was an object. Since URGNA2012 only canonicalized
graphs, not datasets, there was no use of the graph name position.
E. Changes since the First Public Working Draft of 24 November 2022
This section is non-normative.
The algorithm, and the examples, have been changed to systematically
use the xyz format for blank node identifiers, instead of
_:xyz. See Issue 46
for the discussion.
4.6 Hash First Degree Quads
was simplified to remove the simple flag,
which was unused in existing implementations.
The original design of the algorithm was to use the
assigned canonical blank node identifier,
if available, instead of _:a or _:z,
similar to how it is used in
the related hash algorithm, but this text never made it into the spec
before implementations moved forward.
Therefore, the hashes never change,
making the loop based on the simple
flag that calls this algorithm unnecessary.
See Issue 23 for the discussion.
Removed issue marker for
Issue 15
in 4.4 Canonicalization Algorithm,
adding a note that
literal
components of quads are not normalized,
and two literals with different syntactic representations
remain distinct resources.
Changed the way Blank Node identifiers are described
(see Issue 46),
generally omitting the leading _: which is a serialization artifact.
This is still required in the algorithms, but the distinction
between what is an identifier, and the serialization form
is clarified.
Changed the name of the algorithm from URDNA2015 to RDFC-1.0.
The editors would like to thank Jeremy Carroll for his work on the
graph canonicalization problem,
Andy Seaborne and Gavin Carothers for providing valuable feedback and testing input
for the algorithm defined in this specification,
Sir Tim Berners-Lee for his thoughts on graph canonicalization over the years,
Jesús Arias Fisteus for his work on a similar algorithm, and Aiden Hogan, whose
publication [Hogan-Canonical-RDF] provided an important contemporary
analysis of the canonicalization problem and served as an independent
justification of the development of RDFC-1.0.
Members of the RDF Dataset Canonicalization and Hash Working Group Group included Ahamed Azeem, Ahmad Alobaid, Andy Seaborne, Benjamin Goering, Brent Zundel, Damien Graux, Dan Brickley, Dan Yamamoto, Dave Longley, David Lehn, Gregg Kellogg, Ivan Herman, Jesse Wright, Kazue Sako, Leonard Rosenthol, Mahmoud Alkhraishi, Manu Sporny, Markus Sabadello, Michael Prorock, Phil Archer, Pierre-Antoine Champin, Sebastian Crane, Ted Thibodeau, Timothée Haudebourg, and Tobias Kuhn.
This specification is based on work done in the
W3C Credentials Community Group
published as [CCG-RDC-FINAL].
Contributors to the Community Group Final Report include:
Blake Regalia,
Dave Longley,
David Lehn,
David Lozano Jarque,
Gregg Kellogg,
Manu Sporny,
Markus Sabadello,
Matt Collier, and
Sebastian Schmittner.
Portions of the work on this specification have been funded by the European
Union's StandICT.eu 2023 program under sub-grantee contract numbers No. 08/12
and 09/25. The
content of this specification does not necessarily reflect the position or the
policy of the European Union and no official endorsement should be inferred.
Portions of the work on this specification have also been funded by the U.S.
Department of Homeland Security's Silicon Valley Innovation Program under contracts
70RSAT21T00000020 and 70RSAT23T00000006. The content of this specification does
not necessarily reflect the position or the policy of the U.S. Government and no
official endorsement should be inferred.