[Cryptography] Proposal of a fair contract signing protocol
ron at flownet.com
Wed Jun 29 12:03:10 EDT 2016
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."
More information about the cryptography