Subject: [ltans] Question about RFC 4998 Section 4.2 Archive TimeStamp Generation

From: Satoru Otsubo <[email-masked]>
Date: Sun, 20 Dec 2009 19:52:02 +0900

I am Satoru Otsubo.

An example of a constructed hash tree for 3 data groups is
 presented at RFC 4998 Section 4.2.
Here is a copy of Figure 1.

                   h123
                     x
             xxxxxxxxxxxxxxxxxxx
             x                 x 
             x                 x
            h12                x
             x                 x
       xxxxxxxxxxxxx           x
       x           x           x
       x           x           x
       h1        h2abc         h3
                   x
               xxxxxxxxxxx
               x    x    x 
               x    x    x 
              h2a  h2b  h2c

            ( Figure 1 )

And, the reduced hash tree rht1 for data group 1 is shown as follows:

         ( ( h2abc  h1 ) ( h3 ) )

            ( Figure 2 (simplified))

    rht1 = SEQ(pht1,pht2),
      where pht1 = SEQ(h2abc, h1), and
            pht2 = SEQ(h3)

But I think the reduced hash tree rht1 for data group 1 is preferably the following.

         ( ( h1 ) ( h2abc ) ( h3 ) )

    rht1 = SEQ(pht1,pht2,pht3),
      where pht1 = SEQ(h1),
            pht2 = SEQ(h2abc), and
            pht3 = SEQ(h3)

That is, any of partialHashTrees includes only one hash and data group 1
 is placed at the first partialHashTree. 
On verification, I think,
 (1) h1 and h2abc are binary sorted, concatinated and hashed, then,
 (2) the result of (1) and h3 are binary sorted, concatinated and hashed.

Why in RFC 4998 Section 4.2, are h2abc and h1 gathered as a partialHashTree ?
And why h2abc and h1 are binary sorted in advance
 and h1 is placed at the second position in a partialHashTree,
 assuming the binary ordering is h2abc<h1 ?

(By the way, I think the reduced hash tree rht3 for data group 3 is the following.

           ( ( h3 ) ( h12 ) )

    rht3 = SEQ(pht1,pht2),
      where pht1 = SEQ(h3), and
            pht2 = SEQ(h12)

This is wrong ?
If so, I appreciate if anyone shows the correct reduced hash tree.

)

Thanks in advance.