peermart: secure decentralized pricing and

Diss. ETH No. 16200
PEERMART:
SECURE DECENTRALIZED
PRICING AND ACCOUNTING
FOR PEER-TO-PEER SYSTEMS
A dissertation submitted to the
SWISS FEDERAL INSTITUTE OF TECHNOLOGY ZURICH
for the degree of
Doctor of Technical Sciences
presented by
DAVID KASPAR HAUSHEER
Dipl. El.-Ing. ETH
born December 13, 1975
citizen of Cham (ZG), Switzerland
accepted on the recommendation of
Prof. Dr. Burkhard Stiller, examiner
Prof. Dr.-Ing. Ralf Steinmetz, co-examiner
Prof. Dr. Bernhard Plattner, co-examiner
2006
Berichte aus der Kommunikationstechnik
David Hausheer
PeerMart:
Secure Decentralized
Pricing and Accounting
for Peer-to-Peer Systems
Shaker Verlag
Aachen 2006
Bibliographic information published by Die Deutsche Bibliothek
Die Deutsche Bibliothek lists this publication in the Deutsche
Nationalbibliografie; detailed bibliographic data is available in
the internet at http://dnb.ddb.de.
Zugl.: Zürich, ETH, Diss., 2005
Copyright Shaker Verlag 2006
All rights reserved. No part of this publication may be reproduced, stored in
a retrieval system, or transmitted, in any form or by any means, electronic,
mechanical, photocopying, recording or otherwise, without the prior permission
of the publishers.
Printed in Germany.
ISBN 3-8322-4969-9
ISSN 0945-0823
Shaker Verlag GmbH • P.O. BOX 101818 • D-52018 Aachen
Phone: 0049/2407/9596-0 • Telefax: 0049/2407/9596-9
Internet: www.shaker.de • eMail: [email protected]
Abstract
The Internet is becoming increasingly popular as an infrastructure for
buyers and sellers to discover and trade different kinds of goods in a fast and
easy manner. As a result of the rapid technological progress, many more as
well as new types of products and services will be offered over the Internet in
the near future, which will attract even more customers. This vast amount of
goods and traders requires reliable trading mechanisms to be in place which
are truly scalable and efficient.
Existing online marketplaces like eBay typically rely on large, serverbased infrastructures. Such centralized systems are relatively easy to maintain and secure, however, they are often vulnerable against attacks and may
suffer from overload or even failures on these servers.
At the same time, an increasing number of applications in the Internet
benefit from the scalability and robustness of emerging peer-to-peer (P2P)
networks. P2P-based applications are fully decentralized systems leveraging
unused resources of peers and thus, they are able to provide much higher reliability and performance than traditional client/server-based applications.
In turn, the approach developed and termed PeerMart defines a decentralized and secure marketplace for trading any kind of services such as the provision of hardware and software resources over the Internet. It provides an
auction-based mechanism combining the economic efficiency of double auctions with the technical performance and robustness of P2P networks that enables reliable, market-based pricing of any service being offered.
iii
iv
The pricing mechanism is complemented by a decentralized accounting
scheme called PeerMint which provides accountability for applications in a
secure and scalable way. The scheme developed uses multiple distributed account holders and session mediation peers to store and update accounting information of individual peers and sessions and enables to charge for a peer’s
service usage in an aggregated manner.
A prototype has been implemented on top of a structured P2P overlay
network to show the practical applicability and scalability of the mechanisms
developed. Detailed experiments were performed to provide evidence of the
mechanisms’ efficiency and reliability even in the presence of faulty or malicious peers.
Kurzfassung
Das Internet wird immer beliebter als Marktplattform für eine schnelle
und einfache Suche nach verschiedenen Gütern und deren Kauf und Verkauf.
Durch den raschen technischen Fortschritt werden in Zukunft noch mehr und
auch neue Arten von Produkten und Dienstleistungen über das Internet angeboten, was zusätzliche Käufer und Verkäufer anlocken wird. Diese Vielzahl
von Händlern und angebotenen Waren erfordert effiziente und skalierbare
Handelsinfrastrukturen.
Bestehende Marktplätze im Internet wie beispielsweise eBay basieren
üblicherweise auf grossen, Server-basierten Infrastrukturen. Solche zentralen
Systeme sind verhältnismässig einfach zu verwalten und abzusichern, sie
laufen jedoch durch ihre zentrale Lage Gefahr besser angreifbar zu sein und
eher überlastet zu werden oder sogar ganz auszufallen.
Gleichzeitig profitiert eine zunehmende Zahl von Anwendungen im Internet von der Skalierbarkeit und Robustheit neu aufkommender Peer-to-Peer
(P2P) Netzwerke. P2P-basierte Anwendungen sind vollständig verteilte Systeme welche die ungenutzten Ressourcen der Peers wirksam einsetzen und
dadurch in der Lage sind eine viel höhere Verlässlichkeit und Performance
zu erreichen als klassische Client/Server-basierte Anwendungen.
Der entwickelte Ansatz, genannt PeerMart, besteht aus einem vollständig
dezentralen und sicheren Marktplatz für den Handel von beliebigen Waren
und Dienstleistungen wie die Bereitstellung von Hardware und Software
Ressourcen über das Internet. PeerMart bietet einen Auktions-basierten
Mechanismus an, welcher die ökonomische Effizienz von Double-Auctions
v
vi
mit der technischen Performance und Robustheit von P2P Netzwerken kombiniert und so eine verlässliche, Markt-basierte Bepreisung von beliebigen
Gütern ermöglicht.
Dieser Pricing Mechanismus wird ergänzt durch ein dezentrales Accounting System namens PeerMint, welches einen sicheren und skalierbaren
Abrechnungsmechanismus für Dienste innerhalb von Anwendungen bereitstellt. Das entwickelte System benutzt mehrere verteilte Peers als Account
Holders sowie Session Mediators um die Abrechnungsinformationen einzelner Peers und Sessions fortlaufend nachzuführen und ermöglicht eine aggregierte Abrechnung der Dienstnutzung eines Peers.
Ein Prototyp wurde implementiert basierend auf einem strukturierten P2P
Overlay Netzwerk, um die praktische Anwendbarkeit und Skalierbarkeit der
entwickelten Mechanismen zu zeigen. Detailierte Experimente wurden mit
dem Prototypen durchgeführt, um den Nachweis zu erbringen, dass die
Mechanismen auch in Gegenwart von fehlerhaften oder bösartigen Peers
verlässlich und effizient funktionieren.
vii
Table of Contents
Abstract
iii
Kurzfassung
v
Table of Contents
vii
List of Figures
xi
List of Tables
xv
1 Introduction
1
1.1
1.2
Thesis Goals and Contributions . . . . . . . . . . . . . . . .
Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . .
2 P2P Systems and Overlay Networks
2.1
2.2
2.3
2.4
7
Peer-to-Peer versus Client/Server Systems
P2P Overlay Networks . . . . . . . . . .
2.2.1 Unstructured Overlay Networks .
2.2.2 Structured Overlay Networks . . .
P2P Applications . . . . . . . . . . . . .
Chapter Summary . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Economics of P2P Systems
3.1
3.2
3.3
3.4
The Free Rider Problem . . . . . . . .
3.1.1 Selfishness . . . . . . . . . .
3.1.2 Maliciousness . . . . . . . . .
3.1.3 Unreliability . . . . . . . . . .
Problem Analysis . . . . . . . . . . .
3.2.1 The Prisoner’s Dilemma . . .
3.2.2 The Tragedy of the Commons
Incentives for P2P Systems . . . . . .
3.3.1 Mechanism Design . . . . . .
3.3.2 Incentive Schemes . . . . . .
Chapter Summary . . . . . . . . . . .
4
5
8
9
11
14
16
18
19
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
21
21
22
22
23
24
25
25
26
29
viii
4 Economic P2P Architecture
4.1
4.2
4.3
4.4
4.5
31
Requirements . . . . . . . . . . . . . . .
4.1.1 Economic Requirements . . . . .
4.1.2 Technical Requirements . . . . .
4.1.3 Further Requirements . . . . . . .
Architectural Models . . . . . . . . . . .
4.2.1 Related Architecture Frameworks
4.2.2 Service/Resource Model . . . . .
4.2.3 Market Model . . . . . . . . . . .
4.2.4 Peer Model . . . . . . . . . . . .
P2P Trading Scheme . . . . . . . . . . .
4.3.1 Economic Mechanisms . . . . . .
Architectural Components. . . . . . . . .
4.4.1 Core Functionality . . . . . . . .
4.4.2 Further Aspects . . . . . . . . . .
Chapter Summary . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Design Space
5.1
5.2
5.3
5.4
5.5
Pricing . . . . . . . . . . . . . .
5.1.1 Pricing Interactions . . .
Pricing Functionality . . . . . .
5.2.1 Price Determination . . .
5.2.2 Price Dissemination . . .
Auctions . . . . . . . . . . . . .
Accounting and Charging . . . .
5.4.1 Local Accounting . . . .
5.4.2 Token-based Accounting
5.4.3 Remote Accounting . . .
Chapter Summary . . . . . . . .
53
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Decentralized Auction-based Pricing with PeerMart
6.1
6.2
6.3
Model and Concept . . . . . . .
Requirements . . . . . . . . . .
Design . . . . . . . . . . . . . .
6.3.1 Assumptions. . . . . . .
6.3.2 Peer Identification. . . .
6.3.3 Service Identification . .
6.3.4 Broker Set Creation . . .
6.3.5 Bidding Process . . . . .
6.3.6 Matching Process . . . .
6.3.7 Broker Set Maintenance.
32
32
33
36
37
38
39
42
44
46
48
48
49
51
52
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
54
54
55
56
59
61
64
66
66
67
72
73
74
76
77
77
78
78
78
79
81
82
ix
6.4
6.5
6.6
6.3.8 Example . . . . . . . . . . . . . .
Implementation . . . . . . . . . . . . . .
6.4.1 Implementation Architecture . . .
6.4.2 Implementation on Top of Pastry .
Evaluation . . . . . . . . . . . . . . . . .
6.5.1 Analytical Results . . . . . . . . .
6.5.2 Experimental Results . . . . . . .
6.5.3 Possible Attacks. . . . . . . . . .
Chapter Summary . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
83
84
85
86
90
90
93
97
98
Model and Concept . . . . . . . . . . . . . . . . . . .
7.1.1 Session Model. . . . . . . . . . . . . . . . . .
7.1.2 Transaction Model . . . . . . . . . . . . . . .
7.1.3 Distributed Accounting Concept . . . . . . . .
Requirements . . . . . . . . . . . . . . . . . . . . . .
Design . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.1 Peer Identification. . . . . . . . . . . . . . . .
7.3.2 Overlay Network . . . . . . . . . . . . . . . .
7.3.3 Scheme Configuration . . . . . . . . . . . . .
7.3.4 Peer Account Creation . . . . . . . . . . . . .
7.3.5 Session Setup . . . . . . . . . . . . . . . . . .
7.3.6 Account Balance Updates . . . . . . . . . . . .
7.3.7 Account Maintenance . . . . . . . . . . . . . .
7.3.8 Account Queries . . . . . . . . . . . . . . . .
Implementation . . . . . . . . . . . . . . . . . . . . .
7.4.1 MMAPPS Accounting and Charging System. .
7.4.2 Accounting and Charging Interfaces . . . . . .
7.4.3 Accounting and Charging System Interactions .
7.4.4 Implementation on Top of Pastry . . . . . . . .
Evaluation . . . . . . . . . . . . . . . . . . . . . . . .
7.5.1 Analytical Results . . . . . . . . . . . . . . . .
7.5.2 Experimental Results . . . . . . . . . . . . . .
7.5.3 Possible Attacks. . . . . . . . . . . . . . . . .
Chapter Summary . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
100
100
101
102
104
105
105
105
106
106
107
108
109
111
112
112
113
115
117
120
121
123
127
128
7 Secure Decentralized Accounting with PeerMint
7.1
7.2
7.3
7.4
7.5
7.6
8 Summary and Conclusions
8.1
8.2
8.3
99
129
Review of Contributions . . . . . . . . . . . . . . . . . . . 130
Critical Assessment and Applicability . . . . . . . . . . . . 131
Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 133
x
Acknowledgements
135
References
137
Curriculum Vitae
147
xi
List of Figures
Figure 1.1:
Figure 2.1:
Figure 2.2:
Figure 2.3:
Figure 2.4:
Figure 2.5:
Figure 2.6:
Figure 2.7:
Figure 3.1:
Figure 3.2:
Figure 4.1:
Figure 4.2:
Figure 4.3:
Figure 4.4:
Figure 4.5:
Figure 4.6:
Figure 4.7:
Figure 4.8:
Figure 4.9:
Figure 4.10:
Figure 5.1:
Figure 5.2:
Figure 5.3:
Figure 5.4:
Figure 5.5:
Figure 5.6:
Figure 5.7:
Figure 6.1:
Figure 6.2:
Economic P2P Architecture .........................
P2P Overlay Network...................................
Pure P2P Architecture ..................................
Centralized P2P Architecture .......................
Hybrid P2P Architecture ..............................
Pastry Routing ..............................................
P2P Applications ..........................................
P2P File Sharing Traffic...............................
Taxonomy of Incentive Patterns...................
Barter-Trade versus Bond-based Patterns ....
Architectural Models....................................
Related Architecture Frameworks................
Service/Resource Model...............................
Service Example...........................................
Market Model ...............................................
Peer Model ...................................................
P2P Trading Scheme ....................................
Trader Type Ranges .....................................
Economic Mechanisms.................................
Core Functionality Components and
Interactions ...................................................
Basic Pricing Interactions.............................
Basic Pricing Functionality ..........................
Design Space for Auctions ...........................
Hybrid Accounting .......................................
Distributed Accounting ................................
Distributed Accounting in Karma ................
Distributed Accounting with Mediators .......
ER: Market Model........................................
Double Auction Mechanism.........................
3
10
12
13
14
15
16
17
26
28
38
39
40
41
43
44
46
47
48
49
54
55
63
68
69
70
71
74
75
xii
Figure 6.3:
Figure 6.4:
Figure 6.5:
Figure 6.6:
Figure 6.7:
Figure 6.8:
Figure 6.9:
Figure 6.10:
Figure 6.11:
Figure 6.12:
Figure 6.13:
Figure 6.14:
Figure 6.15:
Figure 6.16:
Figure 6.17:
Figure 6.18:
Figure 7.1:
Figure 7.2:
Figure 7.3:
Figure 7.4:
Figure 7.5:
Figure 7.6:
Figure 7.7:
Figure 7.8:
Figure 7.9:
Figure 7.10:
Figure 7.11:
Figure 7.12:
MSC: Double Auction..................................
Matching Strategy of Brokers ......................
MSC: Broker Set Creation ...........................
MSC: Bidding Process .................................
MSC: Matching Process...............................
MSC: Broker Set Maintenance.....................
Double Auction in PeerMart ........................
PeerMart Implementation Architecture........
Implementation of PeerMart on top of
FreePastry.....................................................
PeerMart Package Structure .........................
Redundancy Costs ........................................
Experiment Setup .........................................
PeerMart Overhead with Fixed Broker Set ..
PeerMart Overhead with Fixed Fraction of
Parallel Peers ................................................
PeerMart Reliability with Fixed Fraction of
Parallel Peers ................................................
PeerMart Reliability with Fixed Broker Set.
Basic Session Model ....................................
MSC: Basic Transaction Model ...................
Distributed Redundant Accounting in
PeerMint .......................................................
MSC: Distributed Redundant Accounting ...
MSC: Peer Account Creation .......................
MSC: Session Setup in PeerMint .................
Example Session in PeerMint.......................
MSC: Account Balance Update in PeerMint
MSC: Session Account Maintenance in
PeerMint .......................................................
MSC: Peer Account Maintenance in
PeerMint .......................................................
MSC: Account Query in PeerMint...............
Accounting and Charging System................
75
76
79
80
81
82
83
84
87
90
92
94
95
95
96
97
100
102
103
103
107
108
108
109
110
110
111
113
xiii
Figure 7.13:
Figure 7.14:
Figure 7.15:
Figure 7.16:
Figure 7.17:
Figure 7.18:
Figure 7.19:
Figure 7.20:
Figure 7.21:
Figure 7.22:
Figure 7.23:
Accounting and Charging System
Interactions ...................................................
MSC: Accounting and Charging System .....
Implementation of PeerMint on top of
FreePastry.....................................................
Embedding PeerMint into the A&C System
PeerMint Package Structure .........................
Redundancy Costs ........................................
PeerMint Message Overhead with Fixed
Mediator Set .................................................
PeerMint Message Overhead with Fixed
Account Holder Set ......................................
PeerMint Reliability without Collusion .......
PeerMint Reliability with Collusion.............
Impact of Collusion ......................................
115
116
118
119
120
123
124
124
125
126
126
xiv
xv
List of Tables
Table 2.1:
Table 2.2:
Table 3.1:
Table 3.2:
Table 5.1:
Table 5.2:
Table 5.3:
Table 6.1:
Table 6.2:
Table 6.3:
Table 7.1:
Table 7.2:
P2P versus C/S Systems ...............................
P2P Network Architectures ..........................
Payoff Matrix for the Prisoner’s Dilemma...
Properties of Incentive Patterns....................
Price Dissemination Design Space...............
Internet-based Auction Design Space ..........
Design Space and Evaluation of
Accounting Mechanisms ..............................
PeerMart Messages.......................................
System Variables and Design Parameters ....
Overhead of PeerMart ..................................
System Variables and Design Parameters ....
Overhead of PeerMint ..................................
8
11
23
29
61
64
65
89
91
91
121
122