## 4 Scheme Design
Updating the Merkle tree follows the same method at OemR and EcuX once the leaf nodes are updated with the new hash values. The main difference is that OemR obtains the hash value of the software image from ImgR as OemR does not have access to the software image itself, while EcuX calculates the hash value of the software images if the software cluster belongs to it. Otherwise, it retrieves it from OemR. Figure 6: Merkle Tree of ECU composed of N software entities. Figure 7: Signature Generation and Verification with MT-SOTA. Figure 9 shows how a Merkle tree is modified to add or update a software cluster. When EcuX receives a new software image SW\({}_{M}\), it first has to perform hashing operation on SW\({}_{M}\), then the hash value H\({}_{M}\) is inserted into the corresponding leaf node in the tree, and the node is marked as updated. Next, the parent hash for this updated node and its sibling is calculated. Then, it needs to find the sibling node of its parent node and calculates their hash. This process is iterated until reaching the tree root. Mathematically, this can be represented as follows:  
Let j be the position of the node to be verified; then,  
if j is even  
\[\text{MT}[\text{i}][\text{j}/2]=\text{Hash}(\text{MT}[\text{i}-1][\text{j}], MT[\text{i}-1][\text{j}+1])\]  
if j is odd  
\[\text{MT}[\text{i}][(\text{j}-1)/2]=\text{Hash}(\text{MT}[\text{i}-1][\text{j }-1],\text{MT}[\text{i}-1][\text{j}])\]  
Figure 8: Verification process at the target ECU through use of the Merkle (hash) tree: a received root signature is decrypted to obtain a server-side root that is compared to a client-side root calculated at the target ECU based on an updated hash tree incorporating the hash of the received software. When EcuX has to remove a software image, it first identifies the leaf node associated with the removed software image and designates it as invalid. The hash of its parent is then updated to match the value of the sibling node of the removed leaf node. Subsequently, it computes the hashes for all intermediary levels until reaching the tree root. Figure 10 shows how a Merkle tree is modified when a software cluster is removed. Regardless of the verification types EcuX has to perform, the calculated Merkle tree root is compared with the decrypted received value. If they match, the integrity, authentication, and compatibility of the updated software cluster is verified. Otherwise, EcuX should indicate a failure error and report it to OtaM, and then to OemR. The path composed of all modified nodes is called the proof path of the software cluster node. For a Merkle tree of height HT, the proof path includes HT nodes to obtain the root. Thus, the higher the tree level is, the longer the proof path is. Figure 10: Visual view of Merkle tree modification: removal of software cluster. Figure 9: Visual view of Merkle tree modification: update of a software cluster. The storage size of the Merkle tree depends on the hash output size. The Merkle tree height increases exponentially with the number of nodes. The higher the tree is, the more memory storage it requires. The MT-SOTA scheme has the capability to retain all nodes in the tree, encompassing both leaf and non-leaf nodes. This expedites the signature verification procedure by eliminating the necessity to recompute values for unaffected nodes within the tree. It is possible to store only the leaf nodes to save on memory storage at the cost of increased computation because the values of all non-leaf nodes have to be calculated. The Merkle tree needs to accommodate for \((2^{HT+1}-1)\) nodes. Thus, the storage of the tree (in bytes) is equal to \((2^{HT+1}-1)\times\|H_{i}\|\). Assuming that SHA-2-256 is used as the hash algorithm, each node requires 32 bytes for the hash value storage. Table 2 shows the number of bytes used to store the complete Merkle tree based on the number of software cluster nodes when using SHA-2-256.