Due to a disk crash and backup failure, this site has been restored from an old backup with a number of more recent articles missing. The missing site content is being restored as time permits. We apologise for any inconvenience.
Nutters.org

A Proposal for a Hybrid Contract-Signing Protocol

or "An offer too good to refuse! Just sign here."

A Constrained Rant by The Famous Brett Watson, 27-Oct-2001.

Introduction

This document describes a protocol by which two or more parties can sign a contract over a communications network, with an arbitrarily small chance of any party being able to cheat. Cheating, in the context of a contract-signing protocol, means that one party obtains a signed contract from another without providing the other party with a signed copy of the contract. If neither party fully trusts the other, then neither party will be willing to sign the contract first, and so some special protocol becomes necessary. I assume the presence of a digital signature algorithm, a legal system which recognises digital signatures as binding, and the ability of the participants to verify the authenticity of each other's signatures. I do not describe a concrete implementation of the protocol; the description is at the level of the message content that must be communicated between the participants.

The proposed protocol is something of a hybrid between a contract-signing protocol designed by Michael O. Rabin [1], and one described by Bruce Schneier [2] (which he attributes to Ben-Or, Goldreich, Micali, and Rivest [3], but I refer to it as "Schneier's" in this document for want of a better — and briefer — name). None of these documents can be found on the web, so far as I am aware, so I will provide a very brief overview of the two prior protocols here, as they are significant in understanding the novel elements (if any can be claimed) in my proposal. In these descriptions, I assume that the contract text has been agreed upon and is called CONTR, and that a cryptographically secure message digest of CONTR is available as C.

Previous Proposals

The most obvious way to sign a contract securely over a network involves the use of a trusted intermediary, usually designated "Trent" in cryptographic scenarios. In this case, if Alice and Bob wish to enter into a contract, they each sign a copy of the contract and send it to Trent. Trent will forward the signed contracts only when he has received valid signatures from all parties involved. So long as Trent does his duty, there is no chance anyone can cheat.

But if there are a lot of contracts being signed, the intermediary may become a bottleneck in the process. Further, given that Trent must be independent of the other parties, he may want to be paid for his services. (Even if Trent is a computer program, the owners of the computer may charge for the service.) There is incentive, therefore, to come up with protocols that involve no middle-man. Both Rabin and Schneier present protocols which have this property.

In Rabin's proposal there exists another entity called the beacon. This entity produces messages at regular intervals which contain a timestamp t, and a random number i in the range 0..(k-1). The message is signed by the beacon so that its authenticity may be verified. Our would-be partners in contract, Alice and Bob, then commence the protocol by exchanging signed messages of the following kind.

If [name of other party] can produce a message (C, t, i) signed by me, and (t, i) signed by the beacon, then I, [name of self], will be committed to CONTR as of time t.

This preliminary message does not commit the parties to the contract in any way, but it is what binds the subsequent exchange of signed messages to such a commitment. With that preliminary out of the way, Alice and Bob send each other arbitrary numbers in the range 0..(k-1), then add the two modulo k to produce a single value i. They then send each other a signed message of the form (C, t, i), as mentioned in the preliminary agreement. This exchange must be complete some time before t so that both parties are assured that neither is trying to cheat.

There is a one-in-k chance that the beacon's message will contain the same value for i as the message exchanged by Alice and Bob, and that the contract is therefore signed. In the (highly likely) event that it differs, the parties must try again. If one of the parties has attempted to cheat by withholding their message, then there is only a one-in-k chance of it being successful. The attempt at cheating is obvious to the other party, whether or not the cheat is successful. In the rare case that the cheat succeeds, the cheated party has little recourse but to call their lawyer, but if the cheat attempt fails, they know not to deal with the dishonest party further.

Summary of Rabin's Protocol

Advantages
Disadvantages

In the protocol presented by Schneier, Alice and Bob take turns in exchanging messages which commit them to the contract with an increasing level of probability. The parties decide for themselves how much advantage (as a percentage greater than zero) they are willing to give the other party in terms of opportunity to cheat. Let us assume that Alice decides on two percent, and Bob decides on three percent. The exchange of messages could then start with Alice sending Bob a message in which she commits to CONTR with probability 2%. Bob reciprocates, sending a message in which he commits with probability 5%. Alice responds with a 7% commitment, and so on.

If the protocol terminates before it is complete (with both parties committing to CONTR with probability 100%), or an agreed-upon deadline for completion passes, then parties may have to start calling their lawyers, and get a judge to make a ruling on whether the contract is signed or not. The judge could make this decision by tossing a coin or employing his own judgement, but there are some unpleasant complications in terms of making sure that only one decision is made on the case, and that all parties are informed of it in a timely manner.

Summary of Schneier's Protocol

Advantages
Disadvantages

The Hybrid Protocol

My hybrid proposal uses random numbers in a way similar to Rabin's, but the random number is only used to arbitrate when the protocol fails to complete by a given deadline, as opposed to Rabin's protocol in which it is used as a part of every message exchange. Thus, there need not be a strict "beacon", as such, but a mutually agreed-upon means of determining the number. An example might help here: let us say that Alice and Bob wish to engage in my protocol without using a "beacon". On Monday, they exchange email agreeing to the terms of the contract and the fact that they are going to use my protocol to sign it. They also agree that the random number (which would be provided by the beacon in Rabin's protocol) will be R = f(x1) + f(x2) + ... + f(xn), such that R is in the range 1..(k-1), where f() is a hashing function, and xn is the nth stock market price printed in the stock market report of next Friday's Financial Times newspaper.

For simplicity in describing my proposal, however, I'll assume that there is an agreed-upon source for the random number called the "Random Number of the Day Site". It publishes one random number per day generated from a variety of real-world sources (such as news headlines, weather reports, and stock-market prices). It should be understood that the random number cannot feasibly be predicted or influenced in a deterministic manner by any party — an assumption which was also true of Rabin's beacon. It should also be understood that this site commences data-gathering at time t on a daily basis, and publishes its random number soon after that, such that any number disclosed in advance of t cannot feasibly be based on the generated number. This random number is in the range 0..(k-1) as it was for Rabin's beacon, except that k can be arbitrarily large (eg 2128).

Having agreed upon a source for the random number, the participants each decide on an "advantage factor" that they are willing to grant the other party (as per Schneier's example), and a "minimum advantage factor" that they are willing to be granted themselves. If the other party is not willing to grant them their minimum advantage factor, then they don't trust each other enough to sign the contract, and the protocol cannot commence. Assuming that the requirement for mutually agreeable advantage factors is met, the protocol consists of an exchange of signed messages in the following form.

I aggree to the terms of CONTR if the Random Number of the Day for day d is less than n times k.

Unlike Rabin, I do not include a preliminary message, but in an actual implementation of this protocol, some of the constant information may well be factored out into a preliminary message or reduced to the form of a message digest. The participants exchange messages, increasing n at each step to be one "advantage factor" greater than the largest n they have received from the other party, until they send a message with n of 100%. At that point, the contract is sealed regardless of what value the random number turns out to be, since the random number is always less than k.

For example, if Alice and Bob insist on a minimum advantage of one percent, Alice allows Bob an advantage of two percent, and Bob allows Alice an advantage of three percent, then the protocol can commence, and the resulting exchange may start as follows. Alice sends Bob a signed message with n equal to 2%. Bob reciprocates with n equal to 5%. Alice responds with n equal to 7%, and so on until both parties exchange messages with n equal to 100%, at which point both parties are fully committed.

If the protocol terminates early because one party is cheating, or the protocol is delayed such that the deadline for completion passes, the Random Number of the Day will determine whether the contract is signed or not. There will be three possible outcomes: both parties possess signed messages committing the other to the contract, in which case it is signed; neither party posesses a signed message which commits the other, in which case it is unsigned; or one party possesses a message committing the other, in which case it is time for the other party to call in the lawyers. It will be obvious to both parties which of these cases has happened.

Properties of the Hybrid Protocol

It should be clear immediately that the hybrid protocol shares with Rabin's protocol the advantage that cheaters only necessitate external legal intervention in an arbitrarily small percentage of cases. Neither party conveys an advantage to the other party in excess of their "advantage factor", since at every step they only grant one "advantage factor" more than they have been granted. Because knowing the random number in advance is infeasible, the would-be cheater must stop the protocol at some arbitrary point, at which time the non-cheating party will have committed to one "advantage factor" more of the possible outcomes than the cheater. For an "advantage factor" of p, the cheater succeeds with probability p; in other cases the contract is mutually signed or unsigned.

Mathematical Demonstration of Resistance to Cheating

  1. Let ka be the largest number to which party A has committed.
  2. Let kb be the largest numeric advantage party B is willing to grant party A
  3. Party B will therefore commit to a number no larger than k(a+b).
  4. Assuming that party B does in fact make this commitment, and party A then attempts to cheat by terminating the protocol, the cheat is successful only if the random number R satisfies ka <= R < k(a+b).
  5. Thus there is a range of kb numbers (of the k possible numbers) which result in a successful cheat. Party A therefore cheats with probability b of success, where b is determined by party B.

The protocol shares the termination properties of Schneier's example. Whereas Rabin's protocol is non-deterministic with an expected number of rounds k to completion, the hybrid protocol (and Schneier's) share the property that they will complete in no more than n + 1 message exchanges, for the smallest n satisfying np >= 1, where p is the smallest "advantage factor" offered by any party in the exchange (and must be greater than zero for the protocol to work).

Note also that the "Random Number of the Day" is only used where the protocol is not completed, as opposed to Rabin's protocol in which the "beacon" is used to arbitrate every round. Thus the speed of Rabin's protocol is regulated by the frequency of beacon messages, which is in turn limited by the need for clock synchronisation between participants and reasonable delivery windows for the messages. The hybrid protocol's loose dependency on the random number means that the random number can be generated infrequently, and with proportionately loose synchronisation constraints. In the normal case, the hybrid protocol runs to completion without reference to the random number, limited only by the speed of the network and message processing at the hosts.

Summary of the Hybrid Protocol

Advantages
Disadvantages

Generalisation to N-Party Contracts

Note that the hybrid protocol generalises (as do its parents) to an arbitrary n-party contract rather than just two parties. One way this can be achieved is by all possible pairs of participants engaging in two-way exchanges of this kind. At the end of the process, each party will have supplied a signed contract to every other party, and received one in turn. If point-to-point communication is the only available option, this arrangement is actually quite reasonable.

Cheating would confuse matters to some extent, but in general would oblige the cheater to try to cheat all parties in exactly the same way. If Alice, Bob, and Carol are jointly signing a contract, and Alice is fortunate enough to cheat Bob but not Carol, then Carol could provide Bob with her copy of Alice's binding signature and Alice would be no better off for her efforts. On the other hand, Alice and Carol might both be trying to cheat Bob, in which case they can combine their chances by choosing different termination points. Their chances of defrauding Bob without either of them providing Bob with a signature are no better than if they operated independently, but the chances of at least one of them doing so are doubled. If Bob suspects that Alice and Carol may be in cahoots, he should insist on a multicast-oriented version of the protocol, as this makes such collusion impossible.

A multicast-oriented version of the protocol could be described as follows. Each partial commitment message is described as an offer, with a value equal to the n in that offer, and a participant's offer is on the table if the participant has signed the offer and delivered it to all other participants. Before commencing, all participants must agree on a smallest "advantage factor" that they are all willing to use and accept, and I will call this the minimum bid. The protocol then proceeds on the basis of a simple set of rules.

  1. Everyone is assumed to have an initial offer on the table valued at zero.
  2. You must put a new offer on the table when no other offer on the table is lower than yours.
  3. When you put a new offer on the table, it must exceed the lowest offer (other than yours) by at least the minimum bid, or be a 100% offer.
  4. At any time, the highest offer made by any participant is the one which is "current" for that participant (so there's no point in revising your bid downwards).

Note, in the first instance, that the two-party protocol still obeys these more general rules.

This is a bit like a game of poker in which the players "raise" each other to some maximum level, but don't take strict turns in doing so. For example, assume that Alice, Bob, and Carol have agreed on 1% as the minimum bid. Alice and Bob are relatively trusting, and are willing to offer 5% in their opening bids, whereas Carol only offers 1%. Carol then finds herself having the lowest bid on the table, with the next lowest offer at 5%. All the participants can see that the onus is on Carol to bid at least 6% in order for the protocol to progress further. Participants are quite welcome to exceed the minimum bid, up to whatever advantage factor they are willing to offer their co-signers.

The number of messages exchanged in the n-party protocol is no more than nm, where n is the number of parties, and m is the lowest number satisfying mp >= 1, where p is the "minimum bid". This is based on the worst case, where all parties increment their bid by exactly the minimum bid in unison. If multicast must be simulated by multiple-unicast, then the total number of messages is increased further by a factor of n-1.

Conservative Cheating in an N-Party Contract

The n-party multicast scenario introduces the possibility of conservative cheating. In this case, the cheater does not try to obtain a one-sided contract, but attempts to operate at zero risk of being victim to such a situation himself. He does so by violating the protocol such that he matches the lowest bid instead of exceeding it, effectively offering an advantage factor of zero. Thus, his bid is always the lowest on the table, and there is no chance that he will be the victim of a one-sided contract.

In order to cheat conservatively, you must wait for all other parties to make their bid, and then match the lowest bid, justifying the action by pretending that you made it up in advance of receiving the other low bids. Or, in Rabin's protocol, you simply wait for all other parties to send their signed message before you send yours. Note, therefore, that if more than one party attempts conservative cheating, all cheating parties will be exposed as they wait (indefinitely) for each other to go first. Whoever does not bid last runs a risk of being cheated by the remaining parties, as they may not bid at all!

In order to eliminate the possibility of conservative cheating, strict turn-taking must be introduced into the protocol. Turn-taking would also potentially reduce the number of messages used in the protocol, at least slightly, but it would result in the need for a pre-arranged order in which the participants are to operate. Given the need for coordination amongst the participants in any case (to agree on a minimum bid), this requirement is probably not onerous. To see that turn-taking eliminates conservative cheating, observe that no party may, at the end of their turn, have the lowset offer on the table. The conservative cheat relies on always having the lowest offer. On the other hand, the presence of one conservative cheat does not prevent the protocol from completing, so it may not be worth the bother of preventing or detecting them — other than letting them detect each other!

Conclusion

I submit that the combination in hybrid form of these two contract-signing protocols results in a protocol that is as arbitrarily cheat-proof as either of them, whilst obtaining the best of both worlds in terms of their other characteristics. The protocol is almost certainly faster than Rabin's, thanks to its asynchronous operation, and it has much better properties than Schneier's in the advent of cheating. It hybridises the two protocols by putting the equivalent of Rabin's beacon in the position of the judge in Schneier's protocol.

Bibliography

  1. Michael O. Rabin. "Transaction protection by beacons," Journal of Computer and System Sciences, v. 27 n. 2, October 1983, pp. 256-267
  2. Bruce Schneier. Applied Cryptography, Second Edition, John Wiley & Sons, Inc., 1996, pp. 119-120
  3. M. Ben-Or, O. Goldreich, S. Micali, and R. L. Rivest. "A Fair Protocol for Signing Contracts," IEEE Transactions on Information Theory, v. 36, n. 1, Jan 1990, pp. 40-46

Nutters.org Author: The Famous Brett Watson
Revision: 1
Date: 2001-10-27
History: [2001-10-27] Changes based on suggestions from my lecturer, Annabelle McIver.