1Sprite: A cheat-proof system for Mobile Ad Hoc Networks –Sheng, Chen, Yang (Yale)Presented byNikhil ShettyApril 14, 2006.Introduction• Ad Hoc Network decentralized.• Presently they are with central authority– Hence cooperation can be assumed• Future – civilian purposes• Cannot assume cooperation anymore• Users have different strategies2Protocol Requirements• How to stimulate cooperation?– Provide incentives• Report actions honestly? – Make truth telling the dominant strategy• Should have low overhead• Should not require tamper-proof hardwareModel• Two types of uncooperative nodes– Faulty / malicious nodes– Selfish nodes• Model does not assume faulty / malicious nodes • Selfish node is an economically rational mode – maximize their welfare • Forwarding costs energy – requires incentive3Previous work• Reputation System– Reputation is propagated through network– Repeated game – Selfish nodes can collude– Monitoring may not be possible• Virtual currency– Put currency in packet and send– Decrement currency at forwarders– Requires tamper-proof hardwareBasic Characteristics• Sprite – A Simple cheat-proof credit-based system • Based on Algorithmic mechanism design• Virtual currency used• No Tamper-proof hardware required• Use of centralized Credit Clearance Service4ArchitectureOverview • Virtual money• Sender loses money – incurs cost to forward messages• Node can earn money in 2 ways– Forwarding others’ messages– Buying credit from CCS• When they forward packets, keep receipts• Transfer receipts to CCS when connection is good.5Who pays whom?• Should we charge sender or destination or both?• Destination pays– DOS Attack possible• Share Cost– Sender colludes with intermediate nodes• If destination benefits from contents, use higher layer to extract payment• Hence, only sender pays – Self-regulatingWho gets paid?• Ideally, any node that has tried to forward packet.– Because node incurs cost• But decision cannot be made based on attempt but on outcomes.• If next node in line says it received the packet, CCS will pay the previous node.• Final receiver also gets paid something because he is giving receipt back to the CCS. – Incentive to forward receipts6Objectives of payment• Prevent cheating.• Provide incentives to forward messages.• Balanced payment not required– Sender may pay more – security overhead– Long-term outflow possible – CCS may return the money periodically.Possible Cheating Actions• Node saves receipt but does not forward message.• Node received message but does not report receipt.• Node does not receive message but falsely claims that it has.• All these can get complicated by collusion.7Payment scheme v.1Forwarding motivation• Beta < Alpha • Required so that node forwards message and does not earn enough but just receiving it.• Beta should be greater than the cost of submitting the receipt.8Payment Scheme v.2Reporting motivation• Beta > cost for reporting the receipt (small).• However, collusion is possible • E.g Last node does not report the packet receipt. It loses beta. But sender gains alpha as he has to pay lesser. He can transfer some amount to the last node and they can gain a benefit of (alpha – beta).9Reporting motivation• Make sender pay for the whole path though the message may not have reached the destination.• Last nodes do not gain anything by colluding as their payoff decreases.• Similarly, gain from previous collusion is included in the price sender pays. • Net gain by collusion is 0.Payment scheme v.310Preventing false receipts• Instead of forwarding messages, nodes forward the receipts only.• Sufficient for getting credit. Preventing false receipts• CASE 1: Destination colludes with intermediate nodes.• Destination submits receipt for message it has not received.• Pay as normal case.• Whether destination actually received the packet can be validated by higher layers at sender. Can make destination pay to it for the data.11Preventing false receipts• CASE 2: Destination does not collude with intermediate nodes.• If destination does not receive the packet, we can reduce the payoff of all the nodes by a factor of gamma.• Cheating nodes will not be able to recover even cost of forwarding receipt.A Game Model• Game: Submissions of receipts regarding a given message m as a one-round game.• Players: The game has (d+1) players, n0, n1, …. nd, from the sender to destination.• Players’ Information: Let Ti be the information held by player ni. – Unknown to CCS– Ti = TRUE if message m received– Ti = FALSE otherwise.12Model (continued)Where e’ is the index of the last node that has ever received the message m.Player has some information about e’ from its own information.Model (continued)• Actions: Let Ai be the action of player ni. Two possible actions: Ai is either TRUE or FALSE, i.e. by submitting a valid receipt or by withholding the receipt.13Model (continued)• Cost of Actions: Let Uibe the cost of ni’saction. Cost of sending a receipt to CCS is very low. Let delta be the cost of forwarding receipt to another node. Then node incurs a cost of delta. Ni must compensate the node with delta.Model (continued)• Payment:14Model (continued)Analysis of the Game: Security Perspective:15AnalysisAnalysis16AnalysisAnalysis17AnalysisAnalysis18AnalysisAnalysis19AnalysisAnalysis20AnalysisAnalysis21AnalysisAnalysis22Battery Usage - AfterthoughtBattery requirement• If c and b denote estimated credit balance and number of messages allowed to be transmitted with the battery, if c/L < b then forward the message else don’t.• L is the average number of hops in a path.• Number of packets that I can send is less than the max possible with the battery, then I forward the message.23Conclusion• Cheat-proof mechanism obtained • analyzed with game theory.• Requirement of CCS• Requirement of receipt submission once in a while• Battery not a part of the optimization. Fixed rates for
View Full Document
Unlocking...