## 4 Scheme Design  
As explained in the previous section, functions are hard-coded and tied to the hard-ware for specialized ECUs and domain controllers, while they are implemented as software in domain-agnostic hardware for zonal controllers and central computers. Our approach aims to cover software over the air updates for any embedded systems in today's, tomorrow's, and future vehicles. We can categorize the software architectures into four main categories:  
* Case 1: A single software package in an ECU (e.g., traditional classic AUTOSAR platform, software is decomposed into software blocks). * Case 2: Multiple software packages in an ECU (e.g., adaptive AUTOSAR, flexible classic AUTOSAR platform). * Case 3: Multiple software packages in different ECUs (e.g., zone controllers and connected ECUs). * Case 4: Multiple software packages on-board and off-board (e.g., AI-based cloud applications, backend user applications). Our approach is built on hash-based signatures [24] due to their advantages, specifically considered to be quantum-resistant and future proof. They are reasonably fast and result in a small signature size. Its security assumption is minimal as it relies only on the criteria of a hash function and unforgeability of a digital signature as stated in Section 5. It is parameterized to fit the need for specific applications and different use-cases. We choose hash tree versus hash table to cover use-cases where software is distributed or used differently across vehicles. Most importantly, ECUs can verify complete software integrity and compatibility without requiring the entire software to be present at the ECU level. Rather, only the tree root and essential branch stubs for absent nodes are necessary. Our SOTA scheme is based on a Merkle tree approach [25, 26]. We present a theoretical explanation and analysis for our approach, irrespective of the specific software use-cases employed. Figure 5 outlines the workflow at the backend repositories:  
1. The image software resides in the image repository (ImgR). 2. The ImgR provides the correspondent hash value of the software image with additional manifest data to the OEM repository (OemR) to generate the signature. 3. The OemR has all information about the vehicle, ECUs, and software clusters. The OemR checks which ECU the software cluster belongs to and uses the corresponding Merkle tree to calculate the root. 4. Using the private key assigned to EcuX, the Merkle tree root is signed to create the signature of the software image. 5. The OemR provides the generated signature to ImgR. 6. The OemR constructs the vehicle package containing the manifest data for the software images to be installed, and then sends it to the OtaM in the vehicle. 7. The ImgR sends the software image appended with the signature. 8. Once EcuX receives the software image, it updates the Merkle tree with the hash of the received software image, and then it determines whether the root tree is the same as the one received from the ImgR (after decrypting the received value with the public key of EcuX). Once verified, EcuX stores the value of updated node and root node in the Merkle tree in a secure location. The Merkle-tree-based scheme is designed to work properly regardless of the quantity of verification or number of software components involved. MT-SOTA does not specify full implementation details on purpose. It describes the main necessary entities and methodology for the concept and leaves it up to OEMs to make their own technological  
Figure 5: Software update over the air workflow, extended with Merkle tree scheme to safely and securely update software in the vehicle. choices, for example, which hash algorithm to use or which public key cryptographic algorithm is used by the keys for signing the Merkle tree root (such as RSA or ECDSA [4]). When the ECU has access to existing software images installed on it, there is no need to send anything beyond the signature.