Smart Markers in Smart Contracts: Enabling Multiway Branching and Merging in Blockchain for Decentralized Runtime Verification

The increasing complexity of modern hardware and software platform along with the imperative assurance on stability deems runtime verification of task fulfillment necessary in distributed systems. Distributing the burden of a central verification monitor to individual devices could improve the efficiency. Our previous work shows the possibility of achieving decentralized runtime verification by incorporating some mechanisms of the blockchain technology for locating the accountability when error occurs. However, traditional blockchain technology disallows branching and hence does not support verification of tasks which involves multiway dependencies. In this paper, we introduce a novel approach of smart marker that can be included in a blockchain to enable multiway branching and merging in order to verify the fulfillment of tasks that involve one-to-many and many-to-one dependencies. The design of smart marker satisfies three requirements of recognizability, compatibility, and authenticability. We implement a prototype of the smart marker scheme and analyze its performance.