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.