Re: Exclusive C14N, constraint implementation?

Yes this is better than a vanilla exclusive C14N, but it is possible to 
do even better, if we limit to complete subtrees, or subtrees with 
exclusions of complete subtrees.

In the original algorithm you start with a nodeset, and sort the nodeset 
by document order.  This sorting is a very expensive operation, the 
nodeset can have thousands of nodes, especially if you expand out all 
namespace nodes as well, and the "document order compare function" is 
not cheap.

But in this algorithm, you start with the DOM tree, which is already in 
a sorted order. Now for each element of the tree you need to check if it 
exists in the XPath nodeset.

However this algorithm has two problems
a) It asks to you iterate over the entire tree. If you are signing only 
a small part of the DOM tree, why iterate over the entire tree and 
reject most of the nodes?  Instead just limit to only those subtrees 
that are being signed.
b) It asks you compare each node with an XPath subset. Note this XPath 
nodeset has all nodes expanded out so it is a large data structure that 
you need to create.

For simple ID based references (which by definition select a single 
complete subtree), you can bypass both these issues, and just iterate 
over that particular subtree, and not check against any XPath nodeset, 
because you know that all of the subtree is being signed.

This simple algorithm can be extended to the case where there are 
multiple  subtrees being signed - just sign the trees one by one.And 
also to the case of subtree exclusions - just prune your traversal 
whenever you come to an exclusion subtree.  The Enveloped Signature 
Transform, which is very commonly used can be assumed to be such kind of 
exclusion.

With this simple algorithm, the speed of canonicalization is almost the 
same as XML serialization.

Pratik





Thomas Roessler wrote:
> Looking through Exclusive C14N...
>
>   http://www.w3.org/TR/xml-exc-c14n/#sec-Implementation
>
> ... is a non-normative "constrained implementation."
>
> Does anybody here have a clue to what extent this constrained 
> implementation might be more efficient than vanilla exclusive C14N, 
> and whether it might actually be a good starting point for a single 
> next-generation canonicalization algorithm?
>
> Implementors to the rescue!
>
> Cheers,
> -- 
> Thomas Roessler, W3C  <tlr@w3.org>
>
>

Received on Monday, 20 April 2009 16:55:22 UTC