MSc Defense by Tobias Hallundbæk Petersen

Plan X: Towards scalable distributed ledger technology for compositional digital contracts


We have implemented event matching and validation for compositional contracts as defined by Andersen et al (2006) based on the XMLStore API by Ambus (2004). XMLStore is part of Plan X (originally developed at DIKU and ITU), a compositional, programmable architecture and framework for building shared distributed storage systems and execution environments with support for immutable (tamper-proof) data and code, such as blockchain and distributed ledger systems.

We extend Ambus's XMLStore with public-key based authentication to ensure that contracts can only be matched with events signed by properly authenticated agents. Our implementation supports the entire life cycle of contracts: contract template parsing, contract template instantiation and contract residuation, symbolically computing the remaining contract after a successful event match. These operations interface with XMLStore, which stores parsed templates, residual contracts and resources associated with participating agents. Running the implementation on our local XMLStore with a name server that supports compare-and-swap semantics, the contract residuation prevents double spending of resources and inconsistent residuation. (In our present implementation residuation is not atomic in the face of external failures, which can result in loss of resources.)

The running time of matching a contract c against an event e and computing its residual contract c' is shown to be O(|e + c|); in particular, it is independent of the history of all previous matches. The implementation has been tested empirically on our local (non-distributed) XMLStore, supporting the asymptotic analysis. Both the theoretical and the empirical results provide support for the possibility of achieving amortized O(|e + c|) and eventually even O(|e|) time per event or real-time performance (since events are usually small) in large-scale decentralized ledger systems and thus, in principle, unbounded global transaction rates.

Advisors: Jesper Andersen (Deon Digital Denmark A/S) and Fritz Henglein (DIKU)
Examiners: Fritz Henglein (DIKU) and Peter Sestoft (ITU)

All are welcome. No registration required.