Contract signing

A multi-party contract signing protocol allows a set of participants to exchange messages with each other with a view to arriving in a state in which each of them has a pre-agreed contract text signed by all the others.  ``Optimistic'' protocols allow parties to sign a contract initially without involving a trusted third party T. If all signers are honest and messages are not arbitrarily delayed, the protocol can conclude successfully without T's involvement.  Signers can ask T to intervene if something goes amiss, for example, if an expected message is not received.

There are two such optimistic protocols in the literature.  The first one (GM) was introduced by Garay and MacKenzie in 1999.  The second one (BW) was introduced by Baum-Waidner and Waidner in 2000.  Both of them consist of a main protocol and sub-protocols involving a trusted party, and both were analysed by Chadha, Kremer and Scedrov in 2004.  That analysis revealed a flaw in the case of GM.  Those authors also presented a fix -- a revised sub-protocol for the trusted party.

We show an attack on the revised GM protocol for any number n>4 of signers. Furthermore, we argue that our attack shows that the message exchange structure of GM's main protocol is flawed: whatever the trusted party does will result in unfairness for some signer. This means that it is impossible to define a trusted party protocol for Garay and MacKenzie's main protocol; we call this ``resolve-impossibility''.

We propose a new optimistic multi-party contract signing protocol, also based on private contract signatures, and employs the ideas of Chadha, Kremer and Scedrov for the trusted party.  We present a proof that our protocol satisfies fairness.  The protocol requires n(n-1)(ceiling(n/2)+1) messages to be sent in the optimistic execution, which is about half the number of messages required by the state-of-the-art Baum-Waidner and Waidner protocol, and it does not use a non-standard notion of a signed contract.

Relevant papers

Our results are summarised in the following draft paper (currently under review).

This previous paper explains the flaw in the Garay-MacKenzie protocol as fixed by Chadha-Kremer-Scedrov, and the impossibiility of fixing it by modifying the resolve subprotocol:

This paper describes our new protocol, together with a proof of its correctness:



  • Aybek Mukhamedov, University of Birmingham