Secure Protocols for Behavior EnforcementMotivationOutline1. IntroductionIncentivesSystem Model2. Formal ModelForwarding DominantFormal Model for Divided SolutionRouting stageForwarding stageCooperation-Optimal Protocol3. The Corsac ProtocolVCG for routing protocolsExample of VCGVCG flawTruthful VCGVCG conclusionForwarding ProtocolFair Exchange ProblemCooperation Optimal4. Evaluation (1)Evaluation (2)Evaluation (3)Evaluation (4)Future challenges5. ConclusionsReferencesSecure Protocols for Behavior EnforcementSlides elaborated by Julien Freudiger and adapted by Jean-Pierre Hubauxhttp://secowinet.epfl.chNote: this chapter (and therefore this slide show) is derived from the paper by S. Zhong, L. Erran Li, Y. Liu, and Y. R. Yang, “On Designing Incentive-Compatible Routing and Forwarding Protocols in Wireless Ad Hoc Networks”, Mobicom 2005Security and Cooperationin Wireless Networks2Motivation•Packet forwarding consumes resources–Nodes are rational => Maximize their payoff–Nodes avoid forwardingProvide incentive to cooperate within Routing and Forwarding protocols using a Game Theoretic approach3Outline1. Introduction–Incentives–System Model2. Formal Model–Dominant action/subaction–Cooperation optimal protocol3. The Corsac Protocol–VCG payments with correct link cost establishment–Forwarding protocol with block confirmation4. Evaluation5. Conclusion41. Introduction•Routing protocol–Discover efficient routing paths: global welfare–Deal with selfish nodes: local welfare•Packet forwarding protocol–address the fair exchange problem=> Joint Incentive5•Incentive strategy:–Punish: Reputation, Jamming, Isolation–Reward: Virtual currency•Incentive is achieved:–Internally: With 802.11 primitives–Externally: Dedicated protocolsIncentivesIncentivePunish RewardInternal External Internal External6•Ad-hoc networks as uncooperative strategic games •Called Ad Hoc Games•Channel model: •Packet successfully transmitted if Ptransmission >= Pmin–Pmin = minimum power to reach destination•No errors (BER = 0)•Nodes can withhold, replace or send a message•Node can transmit at any power level •We define the payoff of a node as:–bi = benefice (reward)–ci = cost of forwardingSystem Modeliiicbu 72. Formal Model•Dominant Action: –A dominant action is one that maximizes player i payoff no matter what actions other players chooseExample: Joint packet forwarding game–Imperfect information–Message from S to D–Two players: p1 and p2•P1 has no dominant action•P2 dominant action is F   iiiiiiaauaau ,,S P1 P2 Dp1\p2 F DF(1-c,1-c)(-c,0)D (0,0) (0,0)8Forwarding Dominant •A forwarding protocol is said forwarding dominant protocol if following the protocol is a dominant action •We need incentives to enforce cooperationTheorem 1: There does not exist a forwarding-dominant protocol for ad-hoc games.9Formal Model for Divided Solution•Each node actions is divided into two parts:–Routing subaction: A routing decision specifies what node is supposed to do in the forwarding stage–Forwarding subaction: Specifies what the node actually does•The total payoff comprises both subactions    firiiaaa ,   fraaRRˆ  fiiaRuu ,10Routing stage•Routing payoff of a node is the payoff that it will achieve under the routing decision•Dominant subaction:–In a routing stage, a dominant subaction is one that maximizes its routing payoff no matter what subactions other players choose.•A routing protocol is a routing-dominant protocol to the routing stage if following the protocol is a dominant subaction of each potential forwarding node in the routing stage          ririRiririRiaauaau ,,    fiRiaRuuˆ,11Forwarding stage•Consider an extensive game model with imperfect information•A forwarding protocol is a forwarding-optimal protocol to the forwarding stage under routing decision R if–All packets are forwarded to their destinations–Following the protocol is a subgame perfect equilibrium•A path is said to be a subgame perfect equilibrium if it is a Nash equilibrium for every subgameNode 1Node 2Last nodeforwardforwardforwarddropdropdropp1\p2 F DF (1-c,1-c) (-c,0)D (0,0) (0,0)12A protocol is a cooperation-optimal protocol to an ad-hoc game if1. Its routing protocol is a routing-dominant protocol to the routing stage2. For a routing decision R, its forwarding protocol is a forwarding optimal protocol to the forwarding stageCooperation-Optimal Protocol133. The Corsac Protocol•Corsac is a cooperation optimal protocol–Routing:•VCG –Forwarding:•Reverse Hash chains14•Nodes independently compute and declare their packet transmission cost to destination•Destination computes Lowest Cost Path (LCP)•Source rewards the nodes –declared cost + added value•The added value is the difference between LCP with the node and without it–Incentive to declare the true price => TruthfulVCG for routing protocols15Example of VCGLeast cost path from S to D:LCP(S,D) = S, v2, v3,Dwith cost(LCP(S,D)) = 5 + 2 + 3 = 10 Least cost path without node v2:LCP(S,D;−v2) = S, v1, v4,Dwith cost(LCP(S,D);−v2) = 7 + 3 + 4 = 14Least cost path without node v3:LCP(S,D;−v3) = S, v2, v4,D with cost(LCP(S,D);−v3) = 5 + 3 + 4 = 12.VCG payments:p2 = 14 − 10 + 2 = 6p3 = 12 − 10 + 3 = 5These values represent the unit payment (the payment for one forwardeddata packet) to nodes v2 and v3, respectively.16VCG flaw•Assume mutual computation of link cost•Consider a node i and its neighbor j1. Node i cheats by making Pi,j greater: –Node j is less likely to be on LCP–Node j payment will decrease.2. Node j responds by cheating and making Pi,j smaller:–Node j more likely to be on LCP–Node j increases its payment•VCG is not truthful in this case–Possible to cheat in determining link costi jPi,j17Truthful VCG•Assume private computation of link cost•Protocol for VCG link cost establishment:–Nodes share a symmetric key with D –Nodes send an encrypted and signed test signal at increasing power levels containing cost information–Messages are protected from forging with HMAC–O(N^3)i j[cost3]K¦HMACD[cost2]K¦HMAC[cost1]K¦HMAC[cost4]K¦HMAC[cost3]K¦HMAC[cost4]K¦HMAC18VCG conclusionTheorem 2: If the destination is able to collect all involved link costs as described above, then the VCG protocol is