ERS and alternative ReducedHashtree/PartialHashtree constructs

["Bernd R. Fix" <Bernd.Fix@xxxxxxxxxxxx>]

Hi all.

I am currently reviewing open issues of an LTANS application (productive
since end of 2005, ~10 million documents per day) that I have designed
some years ago and that is therefore using its own format for Evidence
Records.

To keep the system at the "state-of-the-art" I certainly want to switch
to the Evidence Record Syntax defined by RFC 4998. But the strict
procedures regarding computation of reduced hashtrees is giving me some
trouble:

I am using binary hash trees (they have a number of leaves = 2^n). In
this tree two hash values (a left and a right one) are combined
(reduced) to the next higher level.

While it is possible to map the binary structure to the hash tree
concept presented in RFC 4998, the described combination procedure
requires the binary *ordering* of hash values. This is not the case in
my hash trees, where the combination sequence is defined by the position
of the hash values in the tree.

So my question: is it possible to specify my own definition of a reduced
hash tree in an evidence record and still be compliant with RFC 4998?

Thanks for your help,
Bernd.

P.S.: A "ReducedHashtree" is called a "VerificationPath" in my framework
and looks like this (in XML) for a hash tree size of eight documents:

<VerificationPath>
   <Node type="START"> (base64-encoded hash value) H1 </Node>
   <Node type="RIGHT"> H2 </Node>
   <Node type="LEFT"> H3 </Node>
   <Node type="ROOT"> H4 </Node>
</VerificationPath>

which corresponds to this hash tree:

                     +----+
                     I H4 I
                     +----+
                    /      \
            +----+           +----+
            I H3 I           I HV I
            +----+           +----+
             / \               / \
       +----+   +----+   +----+   +----+
       I    I   I    I   I H1 I   I H2 I
       +----+   +----+   +----+   +----+

A path "connects" a document hash (say H1) to the root hash (H4):

HV = Hash ( H1  || *H2*)
H5 = Hash (*H3* ||  HV )

Please note the combination sequence specified in the type field of a
node.    >Y<

-- 
gpg fp: F722 2826 40C2 B3C4 E136 6DE5 1DC0 7A20 513B C8F4