Impact of Adversarial Transactions on Scheduling Algorithm

[bennetyee]

We need to understand what an adversary can do by injecting worst-case transactions on the proposed scheduling algorithm (https://github.com/oasislabs/ekiden/pull/749).

The plan here is to write a tool to modify the synthetically generated load to inject what we think worst-case transactions might be wrt throughput. Once we have this, we can run the generated transactions through the scheduling algorithm and see what the impact is on the overall throughput.

Details

The scheduling algorithm is described here: https://github.com/oasislabs/rfcs/pull/25

A risk here is that we don't really know what a worst-case transaction looks like for any particular scheduling algorithm, so we might end up showing that the scheduling algorithm is okay wrt some bad inputs, but not the actual worst-case ones.

Acceptance Criteria

This is experimental in nature. This is done if it shows that the scheduling algorithm is resistant to injecting bad transactions, or if it has problems and needs to be improved.

[nhynes]

We should also consider adversarial transactions which attempt to select small subsets of compute nodes. Vulnerabilities include probing subsets of nodes for data and selecting malicious compute nodes for contract execution.

Here's some related work on how ad targeting (i.e. scheduling) has been used to attack facebook users.

[bennetyee]

That's a separate issue related to the security of how we select committees, whether compute node identities are leaked (assuming honest/malicious rather than rational/altruistic/malicoius, so compute nodes do not just go and advertise they are part of a committee); etc. For the committee selection aspect, this has more to do with https://github.com/oasislabs/rfcs/tree/master/text/discrepancy-detection since that analyzes how large committees has to be. Though I think the related work is a privacy issue rather than an issue with the integrity of the computation, and maybe it's more related to needing differential privacy and SGX-based compute nodes?

The intention of this issue is trying to understand / address DOS opportunities wrt the horizontal scaling scheduling algorithm. The assumption is that a number of committees has already been selected, and the scheduling algorithm is assigning batches of transactions to the committees. All committees and their members has to be "good enough" from the point of view of security requirements of the transactions, i.e., the committee sizes has to be large enough so that the contract-specific requirements for minimum committee size, the at-risk stake that members will lose if discrepancy is detected, etc, are satisfied.

[nhynes]

the related work is a privacy issue rather than an issue with the integrity of the computation

It's more of an illustrative example of the bad things that can happen if attackers are allowed to choose sufficiently small or descriptive execution committees. Integrity could very well be compromised in either the TEE or non-TEE case if one selects a committee that will blindly accept an invalid root hash or or one containing a breached TEE.

[bennetyee]

Agreed. The d-d RFC talks about how to figure out the appropriate committee size given the level of risks that the contract author (and expected users) is willing to tolerate. We are assuming the diff mechanism to include the starting root hash, so at every "memory barrier" between schedules we have decided on which committee's execution results can/should be accepted. Not all will, since data dependencies and serializing other transactions ahead will change the read-/write-sets.

[bennetyee]

Based on running the simulator with small batches (max subgraph size), zipf alpha=1.0, with adversary injecting about 1% of all total transactions (sometimes in bursts), it looks like the effect on overall throughput is not too different from just having a distribution more skewed away from uniform. The simulator currently assumes the transaction is not data-dependent (or that we punish data dependencies), so does not include having transaction batches revert at the root hash committee (where diff merging and conflict detection takes place) and possibly re-submitted for scheduling. The simulation parameters and resultant data should be gathered in tabular form to show the trends, etc, which is to-be-done (soon?).

The high-level bit is that other than disincentivizing creating transactions with data dependency and/or lots of conflicts, the greedy subgraphs scheduler probably does not need to be tweaked much.