Fixed Merkle Tree

This page describes what-how-abouts of Fixed Merkle Tree

Fixed Merkle Tree as name suggests is a regular merkle tree whose number of leaves is fixed. In our protocol it is 1024. For the sake of explaining FMT lets consider an allocation with only one Blobber(allocation with single blobber is also available), as FMT is blobber specific anyway.

The data for FMT is arranged in following manner:

1. An array(Arr) of length 1024 is created which holds data for each leaf.

2. For each 64 KB block, it is further divided into pieces of 64 bytes each and these pieces are one by one appended to the corresponding index. So first 64 bytes is appended to Arr[0] and second 64 bytes is appended to Arr[1] and so on.

3. The leaf data is now hashed which gives leaf hash.

4. Fixed Merkle Root is then calculated using these 1024 leaf hashes.

In code implementation an array of 1024 with elements as hasher is created and when data is written into each hasher, it simply digests it and thus reducing memory consumption.

If data is not exact multiple of 64 KB then zero byte(or empty data) is used. For example if data is only 1 Byte then for first index of array, this 1 B is hashed without any addition of zero bytes. For all other leaves hash of empty is taken.