Generalizing multi-party contract signing

Sjouke Mauw (Lead / Corresponding author), Saša Radomirović

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


Multi-party contract signing (MPCS) protocols allow a group of signers to exchange signatures on a predefined contract. Previous approaches considered either completely linear protocols or fully parallel broadcasting protocols. We introduce the new class of DAG MPCS protocols which combines parallel and linear execution and allows for parallelism even within a signer role. This generalization is useful in practical applications where the set of signers has a hierarchical structure, such as chaining of service level agreements and subcontracting. Our novel DAG MPCS protocols are represented by directed acyclic graphs and equipped with a labeled transition system semantics. We define the notion of abort-chaining sequences and prove that a DAG MPCS protocol satisfies fairness if and only if it does not have an abort-chaining sequence. We exhibit several examples of optimistic fair DAG MPCS protocols. The fairness of these protocols follows from our theory and has additionally been verified with our automated tool. We define two complexity measures for DAG MPCS protocols, related to execution time and total number of messages exchanged. We prove lower bounds for fair DAG MPCS protocols in terms of these measures.

Original languageEnglish
Title of host publicationPrinciples of Security and Trust
Subtitle of host publication4th International Conference, POST 2015 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015 London, UK, April 11–18, 2015 Proceedings
EditorsRiccardo Focardi, Andrew Myers
Place of PublicationBerlin
PublisherSpringer Verlag
Number of pages20
ISBN (Electronic)9783662466667
ISBN (Print)9783662466650
Publication statusPublished - 2015
Event4th International Conference on Principles of Security and Trust - Mile End campus of Queen Mary University of London., London, United Kingdom
Duration: 16 Apr 201517 Apr 2015 (Link to Conference website)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th International Conference on Principles of Security and Trust
Abbreviated titlePOST 2015
Country/TerritoryUnited Kingdom
OtherPOST 2015 held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015
Internet address

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Generalizing multi-party contract signing'. Together they form a unique fingerprint.

Cite this