## 4 Scheme Design
In this case, the authentication path, the hash values of the neighbors of the nodes on the path from the leaf to the root, is also not transmitted. Thus, the communication cost is negligible. We use the following notations in our MT-SOTA scheme:  
* SW = SW0,..., SWN-1: SW\({}_{i}\) is one of the software cluster images to be updated in an ECU. * N is the number of software clusters in an ECU. * N\({}_{max}\) is the max number of software clusters that can reside in an ECU throughout the lifetime of the ECU. * S\({}_{i}\) = \(||\)SW\({}_{i}||\) is the size of the software cluster SW\({}_{i}\) in bytes. * H\({}_{i}\) is the hash value of the software cluster SW\({}_{i}\) image. \(||\)Hi\(||\) is the size of H\({}_{i}\) in bytes. * HT: is the Merkle tree height. The height at the root node is equal to log\({}_{2}\)(N). * SW\({}_{M}\) is the modified SW cluster, SW\({}_{M}\)\(\in\) SW.
* MT: is the Merkle tree structure, MT[i][j] is the node at height i and index j. The MT-SOTA scheme consists of two phases. At the OemR side, there are the setup and generation phases. At the EcuX side, there are the setup and verification phases. The setup phase of the Merkle tree is similar between OemR and EcuX. The setup phase consists of creating a full binary Merkle tree using the hashes of all installed software clusters. The tree needs to accommodate for N\({}_{max}\) nodes that might be deployed throughout the ECU lifecycle. While a Merkle tree can be essentially infinite, we can use only a fixed number of levels due to embedded systems constraints. Our Merkle tree construction is a bottom-up approach, with height or level equal to HT, and can have up to 2\({}^{HT}\) leaf nodes. Figure 6 shows the binary Merkle tree where the hashes of the software images are used for the leaves of the tree. The interior nodes, called non-leaf nodes, are constructed by hashing the child nodes. In addition to the tree information, there is additional management information that needs to be saved. We summarize the setup phase of the Merkle tree in Algorithm 1 as follows:  
1. The first set of hash results of the software images SW\({}_{0}\) to SW\({}_{N-1}\), which are the H\({}_{0}\) to H\({}_{N-1}\), represents leaf nodes in the hash tree at height 0. 2. These nodes are combined in pairs to provide the first combined hash nodes. The value of the parent node is the hash of the concatenation of two child node hashes (left \(\parallel\) right), where concatenation is represented by \(\parallel\). 3. The hash results are further combined in pairs to an intermediate level hash results. These intermediate level hash results are repeatedly paired and combined until only a single combined hash result remains. This is the Merkle tree root. During runtime, ImgR has a new software image update. Prior to downloading this software update to the vehicle, ImgR has to request OemR to generate the signature in the generation phase. Each image software is assigned a unique identifier which is used to locate the leaf nodes in the Merkle tree corresponding to EcuX. As shown in Figure 7, OemR inserts the new hash value in the leaf node, calculates the new hash of the parent hash for this updated leaf node and its sibling, and then the parent of the new hash value and its sibling has to be hashed. This will be repeated until we get to the tree root. This root is signed by the private key of EcuX to generate the signature. At the vehicle side, once EcuX receives a new software cluster update, it has to verify the signature to validate the received image. Depending on what the EcuX should perform, the corresponding verification should be performed. There are three operations that can be performed:  
1. Update an existing software cluster;
2. Add a new software cluster;
3. Remove an existing software cluster. Figure 8 summarizes the steps performed in the ECU to verify the signature. Verification is a bottom-up approach where it starts from the leaf node of the received software cluster (SW\({}_{M}\)) and goes through the proof path to obtain the top root of the tree.