# [Cryptography] Proposal of a fair contract signing protocol

mok-kong shen mok-kong.shen at t-online.de
Thu Jun 30 11:47:19 EDT 2016

```Am 29.06.2016 um 18:03 schrieb 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
>
>
> 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.