Extensible Markup Language (XML) is possibly one of the most powerful technologies to hit computing in years, providing a way to save and transfer many forms of data in a format that is vendor neutral, easy to generate, and easy to read. So far, so good. But as XML becomes more widely used, in different and more interesting ways, it raises all kinds of new questions, some of which are quite thorny.

One difficult problem is that of authenticating XML documents. While it is relatively easy to authenticate a complete document, it is very difficult to authenticate a partial document, especially when the document may be produced by a dynamic search process. This difficulty is compounded by several factors: the complexity of the possible searches, the fact that the document may be held for distribution by a third party, the fact that the client might not have permission to view the entire XML document, and the fact that the document might be quite large.

Given an XML document, it is not that difficult to see how to authenticate a given part of it using a Merkle hash tree construction (essentially constructing a hash at each node of the tree that hashes its subtree hashes together). Furthermore, if each node of the tree contains its hash value, it is clear that the entire tree of hashes need not be sent, only the hashes for the subtree, and from the parent node for that subtree up to the root of the document, and all the siblings of those nodes.

The complexity arises when there is a large XML tree and a dynamic (XPath or XQuery style) query on the tree generated by a client. How can you convince the client that the results for the query are authentic, and (even trickier) complete?

This paper proposes one possible solution to this problem. It is based on the idea of an “xtrie,” a tree that provides a canonical representation of all the possible paths generated by a document type definition (DTD) (or other XML definition). If the DTD is not recursive, there will only be a finite number of such paths (the paper proposes ways to cope with recursive DTDs that have an infinite number of paths as well). The xtrie may be much smaller than a document, and hence can be used as a verifier for the result of (limited) XPath queries. The paper focuses on the construction and size of the xtries, and so the mechanism of actually doing the verification is only suggested in the paper (as it depends on a large body of previous and concurrent work).

The intent is clearly that communicating the xtrie as a verifier to a client will be less expensive than the cost of communicating other verification methods. But the efficacy of this solution depends more on the soundness of the authentication algorithms, and this paper does not offer more than a sketchy argument on this topic.

There are other potential solutions to this problem, and varying factors against which to evaluate them. In all likelihood, the winner will depend most on who gets a working implementation out and available for consideration by the security community. Given the aptitude of cryptography experts in finding problems, and recent discoveries that make the current state of cryptographic hash functions look a bit more dubious, judgment should be reserved on how good such a solution might be.