Collaboration among Adversaries: Distributed Workflow Execution on a Blockchain

We study distributed declarative workflow execution in an adversarial setting. In this setting, parties to an agreed-upon workflow do not trust each other to follow that workflow, or suspect the other party might misrepresent proceedings at a later time. We demonstrate how distributed declarative workflow execution can be implemented as smart contracts, guaranteeing (I) enforcement of workflow semantics, and (II) an incontrovertible record of workflow execution history. Crucially, we achieve both properties without relying on a trusted third party. The implementation itself is based on the Ethereum blockchain, inheriting the security properties (I) and (II) from the guarantees afforded by that chain. A recurring challenge for both the implementation and the analysis is the cost of operations on Ethereum: This cost must be minimised for honest parties, and an attacker should not be able to inflict extra cost on others.