TreeUtil.hash_tree

Calculate root hash of a L-tree or a binary tree. The number of leaves is not required to be a power of 2.

template TreeUtil(alias hash_2n_n, H, M)

@safe @nogc pure nothrow

hash_tree

(

uint len

)

(

in H[] leaves

in M[] masks

)

if (

len > 0

)

if (

is_hash_2n_n!(hash_2n_n, H) &&

2 * H.length == M.length

)

Parameters

len: Number of leaves. Must be larger than 0.
leaves H[]: The leaves of the tree. Exactly l.
masks M[]: One bitmask for each layer of the tree.

Examples

L-tree hash sanity test.

t {
		import dcrypt.pqc.sphincs.sphincs256: hash_2n_n;

		enum l = 3;
		enum hash_bytes = 32;
		alias ubyte[hash_bytes] hash256;
		alias TreeUtil!(hash_2n_n, ubyte[hash_bytes], ubyte[2*hash_bytes]) Tree;
		hash256[l] leaves;
		for(uint i = 0; i < l; ++i) { leaves[i][] = cast(ubyte) (i+1); } // Make leaves distinct.
		
		ubyte[64][2] masks;
		masks[0][] = 1;
		masks[1][] = 2;
		
		hash256 root = Tree.hash_tree!l(leaves, masks);
		
		leaves[0][] ^= masks[0][0..hash_bytes];
		leaves[1][] ^= masks[0][hash_bytes..$];
		
		hash256 root2 = hash_2n_n(leaves[0], leaves[1]);
		
		root2[] ^= masks[1][0..hash_bytes];
		leaves[2][] ^= masks[1][hash_bytes..$];
		
		root2 = hash_2n_n(root2, leaves[2]);
		assert(root == root2)

Test hash_ltree against result of reference implementation (l_tree()).

t {

		import dcrypt.pqc.sphincs.sphincs256: hash_2n_n, hash256;

		enum l = 67;
		enum hash_bytes = 32;
		alias TreeUtil!(hash_2n_n, ubyte[hash_bytes], ubyte[2*hash_bytes]) Tree;
		
		hash256[l] leaves;
		for(uint i = 0; i < leaves.length; ++i) {
			leaves[i] = cast(ubyte) i;
		}
		
		ubyte[2*hash_bytes][7] masks;
		
		for(uint i = 0; i < masks.length; ++i) { 
			masks[i][0..hash_bytes] = cast(ubyte) (1+2*i);
			masks[i][hash_bytes..$] = cast(ubyte) (2+2*i);
		}
		
		hash256 root = Tree.hash_tree!l(leaves, masks);
		
		assert(root == x"59641ed4970735d4e1d84ec00e4780d1ab211ebd9339b9962de2a15ead43e1e4", "hash_ltree() failed.")

TreeUtil.hash_tree

Parameters

Examples

Meta

Source