## 7 MT-SOTA Optimization Techniques
### Skewed (Unbalanced) Merkle-Tree-Based SOTA  
The Merkle-tree-based approach provides a flexible balanced approach to build the tree of hashes. As described in this paper, the root is retrieved from the hash tree in an average time proportion to \(\log_{2}(\text{N})\), where N is the number of nodes (software clusters) in the tree. In theory, this could be optimal when all leaf nodes are utilized and updated at an equal rate. However, given that software modules within the vehicle are dynamically integrated and updated at varying rates, the objective is to reduce the path required for nodes that undergo more frequent updates.  
To come up with an efficient approach to speed up the overall system performance, MT-SOTA is updated in a way to build an unbalanced tree to allow faster execution for more frequent software nodes. Let us first explain our approach with a simple use case with four nodes. On the left side of Figure 21, we have a balanced Merkle tree with four nodes and height of 2. Each updated leaf node requires changing two nodes (its parent node and the root node) and consequently two hash operations to retrieve the root. If we can move the leaf node, the mostly updated, to a higher level closer to root level, we will need to change only the root node in the tree whenever this leaf node is updated. Thus, by structuring the Merkle tree such that the path of the frequently accessed nodes is reduced, performance can be improved. Compared to the balanced Merkle tree, updating the leaf nodes which are on the shorter path to the root takes less time and has lower overhead in terms of memory access. In order to implement such an approach, each software node has to be given an attribute to indicate its priority level. On average, the unbalanced tree is two times deeper than the balanced one. The drawback for such approach is the height of the tree increases, resulting in increasing the path of some leaf nodes in the tree. The key difference between regular Merkle tree and an unbalanced or skewed Merkle tree is that the paths from the different leaf nodes to the root note have different lengths, depending on type of the skewed tree.  
In order to deal with this trade-off, we can combine a characteristic of a B-tree [30] type with our Merkle tree. A leaf node is not anymore a single node hash but has a variable number of child nodes within some pre-defined range. The leaf node is a block of multiple individual nodes that share some common criteria. As shown in Figure 22, node 8 is the most frequently updated node and set at the top level below the root level as a single node, and then nodes 6 and 7 come at the next level and thus combine together to create a single  
Figure 21: Transition from balanced to skewed (unbalanced) Merkle tree.  
node with an array of two nodes. The nodes 1, 2, and 3 correspond to the lowest level with an array of three nodes. By structuring the tree in such block-based nodes, we can obtain the benefit of having shorter paths, without adversely affecting the paths of the other leaf nodes. In this paper, we focused our analysis on a balanced Merkle tree but we plan to incorporate unbalanced tree analysis in future work.