Re: Exclusive C14N, constraint implementation?

Pratik Datta wrote:
> 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.

And I suspect many XML DSig C14N implementations have already been enhanced to 
do the subtree optimizations above. At least Apache's implementation is.

--Sean