Liveness. Finally, we argue that by the end of epoch R, every forever honest node will have output a bit. Observe that whenever a forever honest node is the leader in some epoch r (and such an r must exist because R ≥ f + 1), it will sign a unique and valid proposal. It follows that in this epoch r, all nodes (that have not already produce an output earlier) will output some bit.
Liveness. The protocol as presented thus far does not ensure liveness. We remedied this by introducing timeouts, such that players default to choosing an action when they did not respond. For some applications this may not be satisfactory, in that we want the parties to respond as quickly as possible rather than waiting for the timeout. We will fix this using an idea of Xxxxxxxxx and Xxxxxxxxxxxxxx [1]. We require both parties to submit a deposit in order to accept the contract. If a party times out, it loses its deposit. This incentivizes the parties to answer within the timeout. However, playing a move at any time before the timeout is still an equilibrium. We can fix the problem by withholding an amount of the deposit proportional to time taken. However, this unfairly punishes honest parties which may incur a short delay for legitimate reasons. Instead, the protocol is parameterized by two timeouts Tthreshold < Ttimeout. Tthreshold is a “reasonable” time before which parties are not punished, and Ttimeout is the timeout where a default action is taken. Let D be the size of the deposit. A party makes a decision at time t is paid ρ(t) defined by: D if t ≤ Tthreshold . ρ(t) = D Σ 1 − t−Tthreshold Ttimeout−Tthreshold if T threshold < t < T timeout 0 o.w. This ensures that parties have largest incentive to answer within reasonable time, and otherwise to answer as quickly as possible. 9 Multiparty transactions In this section we consider generalizing the contract to more parties. Consider a multiparty transaction with n parties: each party may possibly transact with every other party (acting both as seller and buyer). Note that we could just invoke the two- party contract for each pair, however this would incur transaction fees O(n2) times which we would like to avoid. We present a contract that enables a set of n parties to make any number pairwise transactions using O(n) transaction fees, which is easily seen to be optimal. We denote by P1, . . . Pj the n players, and let xij be the size of the payment from Pi to Pj . We will essentially run the two-party protocol n2 times in parallel, and compress the bookkeeping using a procedure similar to how you would split the bill at a restaurant, the algorithm is as follows:
