[Cryptography] Cryptographically securing a two-phase commit

[Jerry Leichter]

This whole problem "feels like" distributed consensus; even the example you give of the attacker simply failing to send the last message is exactly the way the classic FLP result on the impossibility of consensus in a fully asynchronous system even with a single fail-stop process is proved.

Let me see if I can construct an argument.  The introduction of cryptography here is irrelevant to the underlying problem, as is the use of existing file formats.  2PC is exactly a consensus protocol:  Normally, what's important is that all parties agree on a single bit, COMMIT/ABORT.  There's an additional layer here that is only relevant given that we've decided on COMMIT:  Whether we've all agreed on the value.  But that's just yet another consensus problem.  Let's ignore it and just look at the COMMIT/ABORT problem.

What are the assumptions about the environment in which COMMIT/ABORT consensus must be reached?  What's the definition of a correct protocol?  If you assume (a) all parties that follow the protocol correctly must agree on the result; (b) both COMMIT/ABORT are possible outcomes (i.e., ignore the trivial case that everyone always decides on ABORT); (c) you must always reach a decision in some bounded amount of time; (d) all communications is fully asynchronous - you can't make decisions based on timeouts - then you're already in FLP territory, and even in the case of a process that simply stops (or maybe a message that is lost - subtly different; there's *tons* of work on exactly now all this plays out) no solution is possible.

If you change things to the Byzantine General's variation, solutions without cryptography exist if and only if the number of hostile processes is less than 1/3 of the total.  With cryptography (signatures, in particular) you can actually tolerate n-1 hostiles out of n.  Again ... many, many variations; this is all exquisitely sensitive to the detailed assumptions.
                                                        -- Jerry