## 7 MT-SOTA Optimization Techniques
### Dynamic Merkle Tree Algorithm  
Up to this point, our emphasis has been on a static tree design, in which software nodes are sequentially assigned to the leaf nodes located at the bottom level. We showed that the smaller the tree height (maximal number of levels below the root) is, the better the software update performance is. As software nodes are anticipated to be dynamically added in the vehicle, the tree can be re-designed such that the addition and removal of nodes can be performed efficiently with the minimum tree height possible. The goal is to build a self-balancing Merkle tree that automatically keeps its height small for node insertions and deletions. Self-balancing trees have proven their efficiency for many binary search trees, such as red-black trees and AVL trees [29]. Given that nodes are added and removed independently, the algorithm should be meticulously designed to achieve optimal results, resulting in the minimal achievable tree height. Deviating from the bottom-up approach we have adopted in our study, we can follow a top-bottom approach to add the new leaf node. To explain our approach, we show in Figure 19 an example of a Merkle tree with eight nodes. To add node 6, it needs to move down node 5 to a lower level, add node 6 to the right side, and then calculate their parent node and the root node. When all nodes are added, it ends up with a balanced Merkle tree similar to the static tree we worked with previously. When a node needs to be removed, we initiate the process from the node's location. In our pursuit to maintain a minimized tree height, we assess whether another individual leaf can be rotated to take the place of the removed node, facilitating the rebalancing of \begin{table}
\begin{tabular}{c c c} \hline \hline
**Type of Memory** & **Amount of Memory Used** & **Description** \\ \hline Non-volatile program flash & 7 KB & MT-SOTA handler code \\ \hline \multirow{8}{*}{Non-volatile data flash} & Memory USED (Max & \\  & Nodes/Hash Output Size): & \\  & 16.5 KB (128/64) & Merkle tree contents (64 or 128 \\  & 8.5 KB (128/20) & as max number of stored \\  & 4.5 KB (128/16) & nodes). The larger the hash \\  & 6.3 KB (64/64) & output size is, the more \\  & 4.2 KB (64/32) & memory is needed. \\  & 3.5 KB (64/20) & \\  & 3.2 KB (64/16) & \\ \hline \multirow{8}{*}{RAM (data)} & \multirow{8}{*}{100 bytes + copy of Dflash Merkle tree contents} & MT-SOTA handler-related \\  & & variables. The Merkle tree \\ \cline{1-1}  & & contents have to be copied to \\ \cline{1-1}  & & RAM when a new software \\ \cline{1-1}  & & update has to be performed, \\ \cline{1-1}  & & and then the updated RAM \\ \cline{1-1}  & & copy will be copied to Dflash \\ \cline{1-1}  & & once the software update is \\ \cline{1-1}  & & validated and completed. \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Memory utilization with MT-SOTA scheme. the tree. When the tree has an even number of leaf nodes, the process of removing a node is straightforward. The designated node is removed, its adjacent node is elevated to its position, and the corresponding branch is adjusted to reconnect to the tree root. When the tree has an odd number of leaf nodes, removing a node mandates rebalancing the tree. A straightforward approach involves leaving the node in its position and replacing it with the other single leaf node. Subsequently, adjustments are made to the branch of the transitioning leaf node, followed by the recalculation of parent nodes for all nodes that have undergone modification. As shown in Figure 20, removing node 5 requires only the calculation of the root, while removal of node 3 requires transitioning node 6 to the node 3 position, resulting in reducing the tree height by 1. To achieve a fast search when adding a node, each non-leaf node holds an additional bit to indicate if it has a full balanced structure. At a given time, the tree has N nodes with HT as height. If \(2^{HT}\) is larger than the number of existing nodes, then the height of the tree remains the same when a new node is added.