P2P 1,a) 1 1 Peer-to-Peer P2P P2P P2P Chord P2P Chord Consideration for Efficient Construction of Distributed Hash Trees on P2P Systems Taihei Higuchi 1,a) Masakazu Soshi 1 Tomoyuki Asaeda 1 Abstract: Peer-to-Peer (P2P for short) systems and Distributed Hash Tables (DHTs for short), which are implementations of P2P systems, have attracted much attention in recent years because of their performance, scalability, and fault tolerance. Unfortunately, as far as we know, little is known about efficient construction of distributed hash trees on P2P systems. Therefore in this paper we propose several constructions of the hash trees on Chord, which is a most famous implementation of DHTs. Keywords: P2P, Chord, hash tree, data authentication 1. Peer-to-Peer P2P P2P P2P 1 Chord[1] Chord 1 Hiroshima City University a) mw68020@wm.hiroshima-cu.ac.jp 1 1 P2P Chord P2P Chord 2. 1
1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value DHT 2.2 Chord Chord 2.2.1 Chord DHT P2P SHA-1[2] 2 160 0 ID 2 160 1 ID SuccessorList FingerTable Predecessor N O(log N) 2.2.2 SuccessorList Chord k 1 Table 1 Fig. 3 3 SuccessorList Example of SuccessorList N15 SuccessorList Example of node N15 s routing table of SuccessorList SuccessorList[i] SuccessorList[1](N15) SuccessorList[2](N15) SuccessorList[3](N15). i N20 N31 N38. k Successor 2 Successor 2 N15 N26 N15 Successor N26 Successor Chord Successor Successor Successor SuccessorList SuccessorList N r = O(log N) 3 SuccessorList 3 N15 SuccessorList 1 2.2.3 FingerTable Successor Chord 2
5 Fig. 5 Example of hash tree 4 FingerTable Fig. 4 Example of FingerTable 2 N8 FingerTable Table 2 Example of node N8 s routing table of FingerTable FingerTable[i] i FingerTable[1](N8) N14 FingerTable[2](N8) N14 FingerTable[3](N8) N14 FingerTable[4](N8) N21 FingerTable[5](N8) N32 FingerTable[6](N8) N42 Successor N N Chord N O(N) FingerTable FingerTable n +2 0, +2 1, +2 2,, +2 n 1 4 6 Chord 64 FingerTable N8 FingerTable 2 N8 N48 Successsor 6 FingerTable N42 2 1 2 2.3 5 8 k i d i h(m n) m n H h(= 1, 2,, H) 1 H 1 d 3 d 3 k 4, c 21, c 12 r d 3 d 3 k 3 k 4 c 22 c 21 c 22 c 11 c 11 c 12 r r r d 3 m log m 3. Chord 3.1 Chord P2P Chord 3
6 2 Fig. 6 Example of hash tree construction with 2-pass hash tree method 3.2 r N1 1 r 3.2.1 1 2 Chan 2 [3] P2P 6 8 2 s N1 N1 N2 1 N1 1 N2 N3 N3 N8 15 2 Chord Chord Successor 2 3.2.2 2 Chord Successor FingerTable 7 7 2 Fig. 7 Example of hash tree construction with Method 2 8 N1 N2 N3 N5 7 N1 N2 N3 N5 N1 ϕ N3 N5 2 7 N2 N4 N3 N4 N5 N6 N7 3 N4 N6 N7 N8 N8 N8 15 3.2.3 3 Chord 1 1 2 Chord 4
Table 4 4 The number of messages in our proposed methods 1 2 3 8 7 10 8 16 15 22 18 32 31 46 38 64 63 94 78 128 127 190 158 256 255 382 318 512 511 766 638 1024 1023 1534 1278 8 3 Fig. 8 Example of hash tree construction with Method 3 Table 5 5 The number of steps in our proposed methods Chord 2 8 8 2 2 N1 N2 N3 N4 N8 N1 N5 N6 N7 N8 2 2 1 2 4. 3 N Chord 5. 4 1 2 3 5 1 2 3 4 1024 1 1 2 3 8 7 3 4 16 15 4 5 32 31 5 6 64 63 6 7 128 127 7 8 256 255 8 9 512 511 9 10 1024 1023 10 11 2 511 5 1 2 3 Chord 1 2 3 1 1024 3 2 256 1024 1 3 255 3 3 3 6. 3 Table 3 Evaluation of the number of messages and steps in our proposed methods 1 N 1 N 1 2 3 3 2 N 2 log N N 2 (log N) + 1 5 4 P2P Chord 2 3 5
[1] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., Kaashoek, M., Dabek, F. and Balakrishnan, H.: Chord: a scalable peer-to-peer lookup protocol for internet applications, Networking, IEEE/ACM Transactions on, Vol. 11, No. 1, pp. 17 32 (2003). [2] Eastlake, 3rd, D. and Jones, P.: US Secure Hash Algorithm 1 (SHA1) (2001). [3] Chan, H. and Perrig, A.: Round-Efficient Broadcast Authentication Protocols for Fixed Topology Classes, Security and Privacy (SP), 2010 IEEE Symposium on, IEEE, pp. 257 272 (2010). 6