Transcript ppt
Contract signing Rohit Chadha, John Mitchell, Andre Scedrov, Vitaly Shmatikov Contract signing (fair exchange) Two parties want to exchange signatures on an already agreed upon contract text Parties adversarial Both parties want to sign a contract Neither wants to sign first Fairness: each party gets the other’s signature or neither does Timeliness: No player gets stuck Abuse-freeness: No party can prove to an outside party that it can control the outcome Optimism Fairness requires a third party, T • Even 81 • FLP Trivial protocol • Send signatures to T which then completes the exchange Optimistic 3-party protocols • T contacted only for error recovery • Avoids communication bottlenecks Optimistic player • Prefers not to go to T General protocol outline Willing to sell stock at this price OK, willing to buy stock at this price B Here is my signature C Here is my signature Trusted third party can force or abort contract • Third party can declare contract binding if presented with first two messages. Optimism and advantage Once customer commits to the purchase, he cannot use the committed funds for other purposes Customer likely to wait for some time for broker to respond, since contacting T to force the contract is costly and can cause delays Since broker can abort the exchange, this waiting period may give broker a way to profit: see if shares are available at a lower price The longer the customer is willing to wait, the greater chance the broker has to pair trades at a profit Broker has an advantage: it can control the outcome of the protocol Fairness, optimism, and timeliness Model and fairness Call the two participants P and Q Definitions lead to game-theoretic notions • If P follows strategy, then Q cannot achieve win over P • Or, P follows strategy from some class … Need timeouts in the model “waiting” Fairness for P • If Q has P’s contract, then P has a strategy to get Q’s contract Optimistic protocols Protocol is optimistic for Q if, assuming Q controls the timeouts of both Q and P, then and honest Q has a strategy to get honest P’s contract without any messages to/from T Silent strategies A strategy of Q is P-silent if it succeeds whenever P does nothing Define two values, rslvP and rslvQ on reachable states S: rslvP(S ) = 2 if P has a strategy to get honest Q’s signature, = 1 if P has a Q-silent strategy to get Q’s signature, = 0 otherwise Timeliness Q is said to have a (P-silent) abort strategy at S if • Q has a (P-silent) strategy to drive the protocol to a state S’ such that rslvP (S’)=0 Q is said to have a (P-silent) resolve strategy at S if • Q has a (P-silent) strategy to drive the protocol to a state S’ such that rslvQ(S’)=2 A protocol is said to be timely for Q if • For all reachable states, S, Q has either a P-silent abort strategy at S or a P-silent resolve strategy at S A protocol is timely if it is timely for both Q and P Advantage Advantage Advantage • Power to abort and power to complete Balance • Potentially dishonest Q never has an advantage against an honest P Reflect natural bias of honest P • P is interested in completing a contract, so P is likely to wait before asking T for an abort or for a resolve • Formulate properties stronger than balance Optimistic participant Honest P is said to be optimistic if • Whenever P can choose between – waiting for a message from Q – contacting TTP for any purpose P waits and allows Q to move next Modeled by giving the control of timeouts to Q [Chadha, Mitchell, Scedrov, Shmatikov] Advantage Q is said to have the power to abort against an optimistic P the protocol in S • if Q has an abort strategy Q is said to have the power to resolve against an optimistic P the protocol in S • if Q has a resolve strategy Q has advantage against an optimistic P if Q has both the power to abort and the power to complete Hierarchy Advantage against honest P H-adv Advantage against optimistic P O-adv Advantage flow B C O-adv I am willing to sell at this price O-adv O-adv I am willing to buy at this price Here is my signature Here is my signature Impossibility Theorem [Chadha, Mitchell, Scedrov, Shmatikov] Impossibility Theorem In any optimistic, fair, and timely contract-signing protocol, any potentially dishonest participant will have an advantage at some non-initial point if the other participant is optimistic 3-valued version of: • Even’s impossibility of deterministic two-party contract signing • Fischer-Lynch-Paterson impossibility of consensus in distributed systems Proof Outline Pick an optimistic flow: S0 , …., Sn Recall rslvQ rslvQ(S) = 2 if Q has a strategy to get P’s signature, = 1 if Q has a P-silent strategy to get P’s signature, = 0 otherwise We shall assume that rslvQ(S0 )=0 • A cryptographic assumption Clearly, rslvQ(Sn )=2 Pick i such that rslvQ(Si)=0 and rslvQ(Si+1) >0 The transition from Si to Si+1 is a transition of P Proof outline contd.. Protocol is timely for Q • Q does not have a P-silent resolve strategy at Si ( rslvQ (Si)=0) • Q has a P-silent abort strategy at Si Let S, S’ be reachable states such that • Q has an P-silent abort strategy at S • S' is obtained from S using a transition of P that does not send any messages to T Then Q has an P-silent abort strategy at S'. Q has a P-silent abort strategy at Si+1 Proof outline contd… Let S be a reachable state such that Q has an Psilent abort strategy at S • Then Q also an abort strategy if P does not send any messages to T Q also an abort strategy at Si+1 if P does not send any messages to T Q has power to abort against an optimistic P at Si+1 Since rslvQ(Si+1)>0, Q has a P-silent resolve strategy at Si+1 • Q also an resolve strategy at Si+1 if P does not send any messages to T Q has an advantage against optimistic P Jim Gray No evidence of advantage If • Q can provide evidence of P’s participation to an outside observer X, then • Q does not have advantage against an optimistic P • The protocol is said to be abuse-free Evidence: what does X know X knows fact in state • is true in any state consistent with X’s observations in Conclusions Consider several signature exchange protocols • Garay Jakobsson and Mackenzie • Boyd Foo • Asokan Shoup and Waidner Used timers to reflect real-world behavior Formal definitions of fairness, optimism, timeliness and advantage were given Reflect natural bias: optimistic participants defined Give game-theoretic definitions of protocol properties Conclusions Describe the advantage flows in several signature protocol Impossibility result • any fair, timely and optimistic protocol necessary gives advantage Define abuse-freeness precisely using epistemic logic Give an example of a non abuse-free nonoptimistic protocol Further Work Other properties like trusted-third party accountability to be investigated Multiparty contract signing protocols to be investigated Use of automated theorem provers based on rewriting techniques