Transcript Document

The Design of A Distributed Rating
Scheme for Peer-to-peer Systems
Debojyoti Dutta1, Ashish Goel2, Ramesh Govindan1, Hui Zhang1
1University of Southern California
2Stanford University
Outline
• Research motivations
• Basic design issues in P2P rating schemes
• A distributed rating scheme to incentivize
cooperation in P2P file-sharing systems
• Dealing with collusion and malice
• Conclusion & future work
6/6/2003
P2Pecon
2
Research motivations
• Object: P2P file-sharing systems
 Open social communities.
 An explicit reputation layer was ignored in the original design.
• Goal: Build reputation in such systems
 Incentive for user participation
 free-riding phenomenon [Adar et al. 2000][Saroiu et al. 2001]
 Isolation of malicious users
 distribution of inauthentic files
 propagation of virus or worms [VBS.Gnutella][Fizzer.Kazza]
6/6/2003
P2Pecon
3
P2P rating: basic design issues
• “Distributed” rating
 following P2P design philosophy.
• “Efficient” rating
 low cost to run and maintain this reputation system.
• “Collusion-proof” rating
 Effectiveness.
6/6/2003
P2Pecon
4
A distributed rating scheme
•
To incentivize cooperation in P2P file-sharing
systems
•
Main components


6/6/2003
Positive rating
Rating verification scheme
P2Pecon
5
Positive rating
•
The recognized service done to the community

Ri of user i: non-decreasing with the number of
successful requests that it has satisfied within some
sliding time window.
 The higher Ri user i has, the better service it gets from
the network.
6/6/2003
P2Pecon
6
Verification-based rating scheme
?
Rating Ri
Verify if R’i is true for i
(i, R’i)
Data request
User i
6/6/2003
User j
P2Pecon
7
Two verification schemes
•
Structured verification scheme (SVS)

Each user has a set of designated supervisors which keep its
up-to-date reputation information.
 The supervisors are responsible for the verification.
lightweight
L
•
Unstructured verification scheme (UVS)

6/6/2003
A user j queries some of user i’s claimed customers for the
verification, and believes i when the majority of the probed
users reply with a “yes”.
P2Pecon
8
Assumption
•
Users are distinguished by their IP addresses.

6/6/2003
At a given time, one IP address corresponds to an unique
user.
P2Pecon
9
SVS – the supervising topology
•
In the supervisory directed graph

Any user is random to its supervisors.

No small supervising loop exists.

There is a fast reactive approach for any user j to deliver a
message to any other user i’s supervisors, and the path never
includes i.
6/6/2003
P2Pecon
10
A Chord[stoica2001] supervising overlay
00
Network user
256
Supervising
Pointer
224
32
Each user has a
O(logN)-entry routing table
and a O(logN)-successor list.
All routing operations go clockwise
64
192
96
160
128
A Chord network with 8 users and 8-bit key space
6/6/2003
P2Pecon
11
SVS – the supervising topology
•
In the supervisory directed graph

Any user is random to its supervisors.

No small supervising loop exists.

There is a fast reactive approach for any user j to deliver a
message to any other user i’s supervisors, and the path never
includes i.
6/6/2003
P2Pecon
12
Rating verification in SVS
Yes/No
Yes/No
user i’s supervisors
ID(i)
verification request
user j
user i
Supervising overlay
6/6/2003
P2Pecon
13
Structured verification scheme
•
“Distributed” rating

•
“Collusion-proof” rating

•
“Efficient” rating
?

Extra cost to maintain a supervisory overlay when the
underlying network is not DHT-based.

Repetitive actions when there are multiple supervisors.
6/6/2003
P2Pecon
14
Unstructured verification scheme
1. When user j decides to verify user i’s rating, it gets
a portion of i’s customer list, and asks the users on
the list if i did the claimed service to them.
 The customer samples should be random on the full customer
list of node i.
 Disclosure of full customer list could raise privacy concern,
and incur high communication cost.
2. When the majority of the probed users reply with
a “yes”, j is convinced that R’i is Ri.
6/6/2003
P2Pecon
15
Randomly sampling without the
complete customer list
user i’s customer list
a
b
c
d
e
f
g
h
hashing
2k-1
0
user i’s customer vector
[ 2, 3, 1, 2]
6/6/2003
P2Pecon
16
P2P users
users
selfish
non-colluding
6/6/2003
malicious altruistic
colluding
P2Pecon
17
Colluding selfish users
•
•
Possible solution 1: discrete rating

Grade : if a user has served no more than 10 users.

Grade   : if a user has served between 10 and 100 users.

Grade    : if a user has served more than 1000 users.
Possible solution 2: rating as virtual currency

A user has to pay (reduce its rating) for the service it claims
to have received.

SVS: asks the requestor’s supervisors for a payment.

LUVS: future work.
6/6/2003
P2Pecon
18
Colluding malicious users
•
6/6/2003
One possible strategy
1.
A user i quickly earns a high rating by faking
transactions with other colluding users.
2.
User i then does bad things until earns bad-enough
reputation.
3.
User i quits the network to clear its history,
4.
User i rejoins the network and repeats the above
actions.
P2Pecon
19
Conclusion & future work
•
A simple distributed rating scheme to incentivize
cooperation in P2P file-sharing systems.

Two distinct verification schemes
•
Refine LUVS scheme to handle colluding selfish
users.
•
Refine our rating scheme to be collusion-proof.
6/6/2003
P2Pecon
20
Backup slides
6/6/2003
P2Pecon
21
Chord – routing table setup
Network user
Pointer
0
64
32
96
128
160
192
224
255
[8,16)[16,32)
[1,2)
[2,4)
[4,8)
Range
4
5
Range
Range
Range
123Range
[32,64)
Range 6
[64,128)
Range 7
[128,256)
Range 8
A Chord network with 8 users and 8-bit key space
6/6/2003
P2Pecon
22
P2P users
•
•
Selfish vs. malicious

Selfish users: maximize the number of successful requests
with good quality.

Malicious users: subvert the system.
Non-colluding vs. colluding

Non-colluding users: work individually.

colluding users: organize into a clique with some common
interests.
6/6/2003
P2Pecon
23