8. Process Types

Processing of a data collection into a tree can result in a so called unbalanced⁽¹⁾ situation. This will manifest itself when an odd number of elements are present in your data collection (slice).

The following will describe how this can be handled. When working with data that is part of an established scheme, like a blockchain for example, you should select the one that is used in that particular scheme⁽²⁾.

Notes:

• ⁽¹⁾Unbalanced is the inability to process all elements in a binary manner.
• ⁽²⁾You must declare one. There is no default.
• Each Process Type will generate a different root result.

In the below process flow charts shown, all hashes are sha256.Sum256 and are hex string encoded for output. For brevity only the first and last 4 digits are depicted in the flow chart images.

All input slices depicted are based on the hashes of the words in the sentence "I want proof right now"

Word	Hash
I	a83dd0ccbffe39d071cc317ddf6e97f5c6b1c87af91919271f9fa140b0508c6c
want	8656aa55d393b032b7f05fd40daac127c4862315017072b231d726ccf0d686e6
proof	c1cda26362828b69266512052b97cb3729e3b052e4ade47c0a1e3383defe73c7
right	27042f4e6eca7d0b2a7ee4026df2ecfa51d3339e6d122aa099118ecd8563bad9
now	ed5eb9a37e2d8231af3388319b941995f6dc8755c56043d0cc52b5fe405a87de

---

Pass Through

The last element is passed through to the next branch.

^{(Monero blockchain)}

---

Duplicate and Append

When the number of elements is odd, this process will create a duplicate of the last element and append it to the end of the slice, thus having in essence 2 equal data elements at the end, making the number of elements even.

^{(Bitcoin blockchain)}

---

Binary Tree

A Binary tree has branches where the number of elements are of the 2^x order.

An initial index is calculated to start the process, after which we will have a binary tree.

To accomplish this the lowest exponent to raise 2 is determined to obtain a value that is greater than the number of elements (length of) in the slice.

This exponential result is subtracted by the number of elements to obtain the index where the first iteration will start.

The binary logarithm (log base 2) on the length of the input slice will result in the desired exponent. This result will be rounded up to the next integer value.

L = number of elements in the slice.

X = log2(L); X is converted to an integer after rounding it up.

I = 2^X - L; this is the starting index.

startIdx := int(math.Pow(2, math.Ceil(math.Log2(float64(len(ms.Leaves)))))) - len(ms.Leaves)

Examples:

Slice length	Exponent	Index
5	log2(5) = 2.321 => 3	23 - 5 = 8 - 5 = 3
1327	log2(1327) = 10.374 => 11	211 - 1327 = 2048 - 1327 = 721
2048(*)	log2(2048) = 11 => 11	211 - 2048 = 2048 - 2048 = 0 (*)length is in the binary sequence.
10000	log2(10000) = 13.288 => 14	214 - 10000 = 16384 - 10000 = 6384