In the current draft, there may be some minor errors in the description of the
algorithms or confusion on my side on the nature of the notation.
The notation would be much clearer if the merkle tree nodes were indexed by the
tuple representing the range of the hashed values covered by the node.
I've attached below an alternate description of the trees showing the
correspondence of the nodes to the range tuple and a short summary of the
algorithms using this notation.
Paul
PS - will publish associated Python code eventually
0,3 0,4
__|__ __|__
/ \ / \
0,2 2,3 0,2 2,4
/ \ | / \ / \
0,1 1,2 d2 0,1 1,2 2,3 3,4
| | | | | |
d0 d1 d0 d1 d2 d3
Each hash in the tree can be identified as a tuple representing the range
of values covered by the hash.
For a Merkle Hash Tree with n leaf nodes and each i,j node
identified by mth(i,j):
- the root hash, MTH = mth(0,n)
- the leaf hash for data entry di with 0<=i<n is mth(i,i+1)
- leaf values are formed by hashing the input string d(i)
mth(i,i+1) = hash( 0 | d(i))
This is a hash of the single octet with value 0 concatenated with
the ith input string d(i)
- every non-leaf node mth(k1,k2) has the property that
mth(k1,k2) = hash( 1 | mth(k1,k) | mth(k,k2) )
where k = k1+lp2(k2-k1) , and lp2(i) is the largest power of 2 < i
- new entries are added to the tree by:
creating a leaf node
mth(i,i+1) = hash( 0 | d(i))
creating a new root hash
mth(0,i+1) = hash( 1 + mth(k1,k) | mth(k,k2))
recursively creating any mth(i,j) needed for the new root hash
- an empty tree has a root hash value formed by hashing
a null string, hash('')
For n > 1, the audit path for the (m+1)th element d(m) in a list
of n > m elements is found by the recursive function:
PATH(m, D[0:n])
Where:
PATH(m, D[k1,k2]) = {} for (k2-k1)=1
k = k1 + largestPower2(k2-k1)
PATH(m, D[k1:k2]) = PATH(m, D[k1:k]) : MTH(D[k:k2]) for m < k; and
PATH(m, D[k1:k2]) = PATH(m, D[k:k2]) : MTH(D[k1:k]) for m >= k,
0,7
______|______
/ \
0,4 4,7
__|__ __|__
/ \ / \
0,2 2,4 4,6 6,7
/ \ / \ / \ |
0,1 1,2 2,3 3,4 4,5 5,6 d6
| | | | | |
d0 d1 d2 d3 d4 d5
The audit path for d0 is [mth(1,2), mth(2,4), mth(4,7)].
The audit path for d3 is [mth(2,3), mth(0,2), mth(4,7)].
The audit path for d4 is [mth(5,6), mth(6,7), mth(0,4)].
The audit path for d6 is [mth(4,6), mth(0,4)].
_______________________________________________
therightkey mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/therightkey
