# Opaque Computation Integrity
Opaque computation integrity consists of during-execution integrity checks and post-verification. During-execution integrity checks ensure that 1) the individual EncryptedBlock's were not tampered with outside the enclave; 2) no blocks were added/dropped to an EncryptedBlocks object outside an enclave. Post-verification ensures that Opaque properly shuffled data across partitions and executed operators in proper order in accordance with the specifications provided by the generated DAG.

## Building Blocks
We first introduce the building blocks for integrity: the `LogEntry` and the objects built around it. In particular, we modify and add additional tables and fields to Opaque's Flatbuffers specification.

table EncryptedBlocks {
    blocks:[EncryptedBlock];
    log:LogEntryChain;
    log_mac:[LogEntryChainMac]; 
}

table LogEntryChain {
    curr_entries:[LogEntry];
    past_entries:[LogEntry];
    num_past_entries:[int];
}

table LogEntryChainMac {
    mac:[ubyte];
}

table LogEntry {
    ecall:string; // ecall executed
    snd_pid:int; // partition where ecall was executed
    rcv_pid:int; // partition of subsequent ecall
    job_id:int; // Number of ecalls executed in this enclave before this ecall
    num_macs:uint; // Number of EncryptedBlock objects in this EncryptedBlocks
    mac_lst:[ubyte]; // List of all MACs, one from each EncryptedBlock
    global_mac:[ubyte]; // MAC(mac_lst)
}

The key building block is the `LogEntry` field. A `LogEntry` contains metadata representing an ecall. The fields in a LogEntry are defined as follows

- `ecall`: The particular ecall executed
- `snd_pid`: The partition at which this ecall is executed
- `rcv_pid`: The partition at which the subsequent ecall is executed. This field is set to -1 during initialization and is only set once this LogEntry is received by the next partition during subsequent operator execution.
- `job_id`: A counter that counts the number of ecalls executed before this ecall in this enclave. Used to order ecalls during post verification.
- `num_macs`: Number of EncryptedBlock objects resulting from this ecall.
- `mac_lst`: A list of all MACs, one MAC per EncryptedBlock.
- `global_mac`: A MAC over the mac_lst

Just as every ecall will yield a list of EncryptedBlock, every ecall will also produce a `LogEntry`. We define the `LogEntry` produced by this ecall as the current log entry. After an ecall has finished executing, the current log entry is sent with the list of EncryptedBlock as part of the `LogEntryChain` as input to the next ecall.

## Execution Time Integrity Verification
### Enclave Executor Behavior
Before performing any computation, every ecall performs an integrity check per EncryptedBlocks received -- this integrity check is the during-execution integrity check. Note that an ecall may receive multiple EncryptedBlocks if receiving data from different partitions. In particular, the enclave checks

1) For each EncryptedBlocks, the `log_mac` is indeed a MAC over the entire `log` in that EncryptedBlocks to ensure that the log hasn't been tampered with.

2) For each current log entry in a LogEntryChain in an EncryptedBlocks
a) a LogEntry's `global_mac` is indeed the MAC over its `mac_lst` to ensure that no MACs were added, dropped, or tampered with.
b) The MACs of the EncryptedBlock's the ecall received as input are all present in the `mac_lst`.
c) The MAC of each EncryptedBlock is indeed the proper tag for that EncryptedBlock's ciphertext. This is done implicitly as part of AES-GCM.
d) The `job_id` is as expected, i.e. one less than the `job_id` for this next ecall. This is done to prevent replay attacks. (Not yet implemented)

Once these three integrity checks have passed, the enclave creates a `LogEntry` object, copying the LogEntry's `ecall`, `snd_pid`, and `job_id` fields. It also sets `rcv_pid` to its own partition ID and adds that to the `LogEntry`. The enclave then adds the newly created `LogEntry` to a list of `LogEntry`'s, which persists only for the duration of the ecall. We call this list of `LogEntry`'s `past_log_entries`. The enclave finally adds any `LogEntry`'s that were already part of this input LogEntryChain's `past_log_entries` to the `past_log_entries` list.

By continually adding the current log entries for each ecall to a list of log entries that will be sent to the subsequent ecall, we're essentially compiling a history of ecalls and their data movement. In particular, a LogEntry can be uniquely identified by `(op, snd_pid, rcv_pid, job_id)`. We leverage this history of ecalls during post-verification, as explained in a later section.

The enclave then proceeds with computation, and once the ecall has finished computation, it generates a `LogEntry` representing that ecall, which we term `curr_log_entry`. It sets `LogEntry.ecall` to the ecall name; `LogEntry.snd_pid` to its partition ID; `rcv_pid` to `-1`, as `rcv_pid` is to be set by the next partition receiving this `LogEntry`; `job_id` to the current value of the counter (that counts how many ecalls this partition has executed); `num_macs` to the number of EncryptedBlock's in this EncryptedBlocks -- each EncryptedBlock has one MAC tag for its encrypted data; `mac_lst` to a list of MACs of the EncryptedBlock's contained in this EncryptedBlocks; and `global_mac` to a MAC of the `mac_lst`.

The enclave then adds this `LogEntry` to `LogEntryChain.curr_entries`, and adds the `past_log_entries` to `LogEntryChain.past_entries`. The `LogEntryChain` is added as part of the output `EncryptedBlocks`.

The enclave finally computes a MAC over `curr_log_entry || past_log_entries`, and adds this MAC as `log_mac` to the output `EncryptedBlocks`.

### Driver Behavior
During computation, the trusted driver tells each executor enclave its partition ID. The partition ID is added to the executor's `LogEntry` at the end of each ecall and is used at the end of computation during post verification. Note that each executor sees the partition ID in plaintext, likely rendering this passing of partition ID insecure. We plan to address this in a future PR.

In addition, the driver logs the sequence of executed operators. This sequence of executed operators is defined as the expected sequence of operations, which will later be compared with the actual sequence of operations during post verification.

## Post Verification
Once the entire Spark job has completed, the post verification engine runs to ensure integrity of the job before the results of the query are released, i.e. decrypted. In particular, once results are collected at the driver, the driver runs the post verification engine before decrypting the results.

Given the driver's log of executed operators accumulated during execution, the post verification engine creates an expected sequence of ecalls. Each operator maps to one or more ecalls, and the engine uses this mapping to create the expected sequence. Given the expected sequence of ecalls and the number of partitions, the engine also computes a graph representing the expected data movement across partitions throughout the entire job.

### Representing Data Movement as a Graph
Take as an example an Opaque job that uses 2 partitions and performs 3 ecalls. All output from the first ecall goes to partition 1, output from the second ecall is broadcast to all partitions, and output from the third ecall stays in the same partition. In visual form, this job can be represented as follows:


Each node represents a specific ecall at a specific partition, and each edge represents how the output of that ecall is shuffled. For example, P₁₁ represents the first ecall at partition 1, and its outgoing edge means the output of the first ecall at partition 1 stays at partition 1. P₂₁ represents the first ecall at partition 2, and its outgoing edge means the output of the first ecall at partition 2 gets sent to partition 1.

In general, this graph contains num_partitions * (num_ecalls + 1) nodes. Each node has one or more outgoing edges representing to which partitions the output of each ecall is sent.

This data movement graph can be represented as an adjacency matrix. As an example, we demonstrate how the data movement graph above can be represented as an adjacency matrix.

| | P_11 | P_12 | P_13 | P_14 | P_21 | P_22 | P_23 | P_24 |
|------|------|------|------|------|------|------|------|------|
| P_11 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| P_12 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| P_13 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| P_14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| P_21 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| P_22 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| P_23 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| P_24 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

Each node is present along both the x and y-axis of the matrix; we sort the nodes first by partition and then by ecall. That is, we group together all nodes belonging to partition 1, then group together all nodes belonging to partition 2, and lastly stack the two groups of nodes.

The 1's in the matrix represent a directed edge from the node in the y-axis to the node in the x-axis. For example, the "1" in the first row second column represents an edge, i.e. data movement, from node P₁₁ to node P₁₂.

### Verifying Data Movement Integrity
Once the post verification engine has defined the expected sequence of ecalls and the expected data movement graph, it recreates the executed sequence of ecalls and the actual data movement by taking the log from the `EncryptedBlocks` output of the last step of each partition. As mentioned previously, the log represents a history of ecalls, where they occurred, and where the result of the ecall was sent. The engine uses this information to compute an adjacency matrix representing the actual data movement. Lastly, the engine compares the adjacency matrix representing expected data movement with the adjacency matrix represesnting actual data movement. If equal, the integrity check passes.

## Implementation
To implement computation integrity, we modified various parts of the codebase. While most of the changes are extensible and should not require updates when we add support for additional expressions or operators, the following pieces of code will require additions.

* `JobVerificationEngine.scala`: We'll need to add logic to support the added operator when creating the expected ecall sequence and the expected adjacency matrix.
* `EnclaveContext.h` If an ecall in the new operator uses more than one RowWriter in parallel, i.e. `RowWriterA.output_buffer()` isn't called before `RowWriterB.append()` is called, we may need to add vectors to store the MAC lists of the blocks encrypted and appended to each RowWriter. We usually store all MACs of EncryptedBlock's in the same list, but if different EncryptedBlocks are sent to different partitions, we'll need to store the MAC lists separately to ensure that each EncryptedBlocks' LogEntryChain contains the proper MACs. See the `non_oblivious_aggregate_step1()` function in `Aggregate.cpp` for an example.

We also had to make major modifications to `FlatbuffersWriters.cpp` and `FlatbuffersReaders.cpp` to construct the `LogEntry`s and perform the integrity checks; to `concatEncryptedBlocks()` and `emptyBlock()` in `Utils.scala` to add support for the additional Flatbuffers fields; and to the `OpaqueOperatorExec.executeCollect()` function to perform post-verification before decrypting results. However, these parts of the codebase will likely not require changes when we add additional operators.