[Cryptography] Proposal of a fair contract signing protocol

[Ron Garret]

On Jun 29, 2016, at 7:40 AM, Sidney Markowitz <sidney at sidney.com> wrote:

> mok-kong shen wrote on 29/06/16 11:53 PM:
>> [I hope that the following more carefully/clearly formulated revised
>> version of my OP should render the underlying idea of mine
>> understandable and more easily seen to be correct.]
> 
> Well, at least you have made it clear that it is different than the Two
> Generals problem, so we can't simply say that what you are trying to do has
> been proven impossible that way. The Two Generals problem says (roughly) that
> it is impossible for two parties to unequivocally come to an agreement over an
> unreliable channel. Your protocol is allowed to time out without any contract
> coming into effect if it takes too long, so that is not an issue.

It is true that this problem is different than the 2G problem.  However, coming up with a proof of impossibility of fair commitment protocols without an RTP (even with reliable communications) is a pretty elementary exercise.  I even exhibited such a proof on this list.  Here it is again, with elaboration:

Theorem: fair commitment protocols using only interleaved actions by the participants (i.e. without a trusted third party) are not possible, even with reliable communications

Let’s start with some definitions:

An agent A is COMMITTED to some action C with respect to a contractual counter-party B if there exists an action or sequence of actions S that B can take following A’s failure to perform C by some deadline that results in negative consequences for A.  The canonical example would be B suing A for failing to perform C.  Note that it is not necessary that B actually perform S for a commitment to exist on the part of A.  B might elect not to sue A for failure to perform C, but that doe not vitiate A's commitment.

A FAIR CONTRACT is a contract that commits A to performing an action CA and B to performing an action CB with the property that there is no period of time where A is committed to CA while B is not committed to CB.  A FAIR PROTOCOL is a protocol that produces a fair contract.  INTERLEAVED ACTIONS are a set of actions with the property that 1) every action is performed by either A or B, and 2) no two actions occur simultaneously (and hence they have a total order with respect to time).

We now proceed with the proof by reductio: assume that a fair protocol exists.  Then there is some key action K with the property that performing K results in the simultaneous commitment of A to CA and B to CB.  Assume without loss of generality that K is performed by A.  Then B is committed to CB after K, i.e. after K, if B does not perform CB then there exists an action S that A can take that results in negative consequences to B.

Now consider the situation before K.  In this situation, A can produce negative consequences for B by performing K followed by S.  Therefore, by the definition of commitment, B is committed to CB before K.  This contradicts our assumption that B was not committed to CB before K.  QED.

> Proposal of a fair contract signing protocol

You might as well open with “proposal for trisecting an angle with compass and straightedge."

rg