# A Cryptography-Powered Infrastructure to Ensure the Integrity of Robot Workflows
## 3 Compliance Architecture
### Dynamic View and Information Flow
#### 3.4.1 Preparation Phase  
Prior to composing a program, the client needs to know which workflows the robot supports. This is either inherent knowledge or the client retrieves the available workflows directly from the execution entity. The response contains a list of workflow names including the corresponding workflow description. Having this information the client builds a WorkflowQueue object which consist of a list of workflow name/workflow parameter pairs. Executing a workflow queue with the execution entity requires a successful verification of the signature chain corresponding to this queue. Hence the client sends a WorkflowQueueSigningRequest to the CSP which is initialized with the CSP's private key and a cryptographic hash function. The following steps describe the cryptographic mechanism used to sign the workflow queue.  
To protect the order of workflows, the CSP needs to use a specific data structure that enables the detection of workflow reordering within a queue. Multiple potential solutions can be chosen, we mention three alternatives here: Merkle trees, Verkle trees or the concatenation of all workflows. A Merkle tree [39] is a tree structure of hashes where a leaf node contains the hash of a certain data item (in our case, a single workflow) and where a non-leaf node contains a hash of its child nodes' hashes. This allows for arbitrary interleaving of workflows where each workflow is integrity-checked using an individual hash and were the sequence of workflows is ensured by hashing the child nodes' hashes. A Verkle tree [40] is a variation of the Merkle tree that uses vector commitments thus reducing the trees proof size. An alternative approach to ensuring the integrity of the overall queue could be to concatenate all workflows and sign their cumulative hash. However, in this case it would not be possible to find out which part of the queue has been modified. In addition, as we point out in our outlook, a Merkle or Verkle tree will enable the use of sanitizable signatures that will allow parts of the workflows to be modified by authorized actors even after signing. For the rest of this paper, we will assume that a Merkle tree is chosen.  
As a superordinate data structure, we are using Merkle trees since the binary Merkle tree is more efficient in its construction than the corresponding Verkle tree as the construction is the most used operation in our concept. However, when we mention a Merkle tree in the remainder of the document, any other method of order integrity preservation can be substituted.  
We leave it open which kind of hashing method is used by a specific implementation but urge to use modern, strong hashing like SHA2/3. Similar, also the signature algorithm should be state of the art such as RSA.  
Based on this, the CSP performs the following two steps:  
1. Generate a Merkle tree from the workflow instances contained in the workflow queue. For that each workflow instance is hashed, by concatenating the workflow description and the parameter string and finally applying the hash function to it. These hashes are then paired up and a new hash is generated from each pair. This is repeated until the root of the tree has been generated.
2. Sign the root of the Merkle tree with the private key and get the signature of the workflow queue as result. By signing only the root of the Merkle tree, the signing process is very efficient.  
The resulting signature allows for the verification of the workflow queue in terms of containing the right workflows and having them in the right order. After finishing the signing process the CSP sends the signature back to client, who merges it with the initially created WorkflowQueue object to get an ExecuteWorkflowQueueRequest. The request body contains the WorkflowQueue object, whereas the signature is defined as a separate request header.