Irkle Whitepaper
Whitepaper for Irkle, a merkle tree library and ecosystem designed to be as fast as possible.
18 Dec 2020 ResearchTable of Contents
Preface
This document (layed out as a post) is the whitepaper for Irkle, a merkle tree library and ecosystem designed to be as fast as possible.
This whitepaper is not intended to be a full scientifically evaluated report on the speed of Irkle, but more of a technology proposal with a working example of the proposal being a functioning library.
Proposals
The following sections are technology proposals for speedups in merkle tree technology which are implemented into Irkle. These may not be entirely novel ideas on their own, but with the benefits of each combined, it allows a greater speedup then would otherwise be possible.
Arraybased tree
Using an arraybased merkle tree brings some key advantages along with it, suited towards the reading of data and ease of implementation for multithreading.
For example, given the following mapping of a conventional tree data structure (assuming a full & perfect binary tree)^{1}:
alpha
bravo
charlie
delta
echo
foxtrot
golf
This would transform into the following array data structure:
[alpha, bravo, echo, charlie, delta, foxtrot, golf]
With this arrangement, the data may become more computationally impactful to expand due to array resizing in some list/array/vector implementations but the utility it provides by allowing an approximate list of all data blocks in the last half ($\frac{n}{2}$). This will return (assuming $2^n$ data blocks like this example is), a list of all data blocks:
[charlie, delta, foxtrot, golf]
Note that this may not give a perfect representation of the data blocks as a perfect $2^n$ is rare and is what’s needed to have no empty/filler nodes in the latter $\frac{2}{n}$’s of a tree.
Another key component of arraybased trees is the locality of data (or locality of reference) presented in any array.^{2} This is especially useful for traversal of a binary and therefore a merkle tree, as node siblings are next to each other (i.e. left is $n1$ and right is $n+1$) for example.
Data reference list
Continuing on from using the latter half of the tree with $\frac{n}{2}$, this can be further explored by maintaining a separate list/array/vector of all data nodes in the actual arraybased merkle tree. This is useful as such a dataset may be searched using a number of conventional arraybased search algorithms to find either the hash or the data contained inside.
Using the examples given in the previous proposal of arraybased trees, a data reference list would look similar to the following:
[&charlie, &delta, &foxtrot, &golf]
Another potential use this brings is a concrete pathing method for data, if used in conjunction with an arraybased tree as previously discussed.
If it is known that parent nodes are always $\left\lfloor \frac{n1}{2} \right\rfloor$ from the child, we may recurse up the tree once finding the desired data block to quickly create a path to our data node in order to execute such functions as tree modification quickly.
This may be done by either utilising the found hash of the parent node and adding it to an array which is then reversed (in order to go parent –> child rather than child –> parent) or alternatively using the modulo^{3} of the previously stated equation each time to figure if the data block/last node was to the left or right of a given parent node.
In Python, we may write the modulobased (nonrecursive for simplicity) method similar to the following:
array_binary_tree = [
"alpha",
"bravo", "echo",
"charlie", "delta", "foxtrot", "golf"
]
golf_pos = 6
golf = array_binary_tree[golf_pos]
parent = (golf_pos  1) / 2 # should be 2.5
if parent % 0 == 0:
print("golf is left")
else:
print("golf is right")
This should output the following:
golf is right
Multithreading
A secondary but often overlooked part of the speed of merkle trees is multithreading – as seen with the git package manager, multithreading is not used (most likely due to the age of this platform). It may speed up systems with little to no overhead, especially on modern systems with a high number of cores.
Multithreading is especially important in the light of merkle trees as compared to other binary trees due to two main factors:
 Embarrassingly parallel^{4}
 Hashing is computationally demanding compared to simply inserting data
For example, if given an example list, we could easily split it up and assign each thread a new task by data blocks divided by cores, i.e. $\frac{d}{c}$ as a simplistic method of multithreading, which would look similar to the following chunk splitting function in Rust:
pub fn split_n_chunks<T: std::fmt::Debug>(
mut items: Vec<T>,
min: usize,
desired_chunks: usize,
) > Vec<Vec<T>> {
if items.len() <= min {
return vec![items];
}
let mut output: Vec<Vec<T>> = vec![];
let chunk_range = 0..(items.len() / desired_chunks);
for _ in 0..desired_chunks {
output.push(items.drain(chunk_range.clone()).collect())
}
match output.last_mut() {
Some(el) => el.extend(items),
None => output.push(items),
};
output
}
Where the values inputting into this split_n_chunks
function match the following:
Variable Name  Datatype  Description 

items 
Vec<T> – List containing input (data blocks) 
Items to split into chunks for the purposes of multithreading 
min 
usize – Unsigned machinedependant integer (e.g. u32 on 32bit) 
Minimum allowed length of items before function doesnt modify 
desired_chunks 
usize – Unsigned machinedependant integer (e.g. u32 on 32bit) 
Representative of amount of cores, i.e. how many chunks to divide into 
Note that this is a simple demonstration of splitting data into chunks for parallelisation and it’s not representative of the best practices. In reality, you should split large lists/arrays/vectors into smaller then $\frac{d}{c}$ and have a thread pool executing so if a thread slows for a specific worktask, the other threads can continue more efficiently.
Further reading
Links
Some external links to find out more about this whitepaper and any primary work based upon it:
Citations

D. W. Harder, (2011). Algorithms and Data Structure. Department of Electrical and Computer Engineering, University of Waterloo. ↩

T. Cormen, (2001). Introduction to algorithms. 2nd ed. Cambridge: MIT Press. ↩

Modulo is used to determine if the number is an integer or a decimal as length determines $\frac{n1}{2}$ may provide a
.5
↩ 
Merkle trees may be easily split into chunks for processing cores to compute, scaling perfectly to the number of hashes proportional to the logarithm of the number of leaf nodes of the tree, divided by core count, i.e. $\frac{\log\left( n \right)=h}{c}$ ↩