Skip to content

My Understanding of the TeleHash Protocol

drusellers edited this page Feb 24, 2011 · 10 revisions

Purpose of TeleHash

A TeleHash client is called a switch. More on that later.

TeleHash is a peer-to-peer protocol to create one, always-on Distributed Hash Table (DHT) between all online TeleHash switches worldwide. In that sense it’s similar to BitTorrent although the TeleHash protocol can handle other applications besides file transfer.

Since the TeleHash protocol is designed to support one global DHT it can be categorized as a distributed protocol. TeleHash is, however, just a protocol: it defines how packets flow between switches and what the content of those packets is. TeleHash switches need to be implemented so that:

  1. The content of incoming packets is used to feed the local version of the DHT (each switch has an internal representation of the global DHT).
  2. Information is sent to other switches so that DHT entries that are important to a switch get sufficiently distributed.
  3. Packets can continue to pass through NAT network devices like home routers (UDP tunnels on NAT devices typically time out after 60 seconds).

TeleHash Glossary

Telex: UDP packet sent between switches containing one JSON entry that is potentially encrypted.
Switch: a client, that is connected to the Internet, which sends and receives Telexes and it maintains a local representation of the global DHT.
Kademlia: (wikipedia) The DHT method used by TeleHash switches as well as BitTorrent.
End: a SHA-1 hash key (40 hex characters, 160-bits) stored in the global DHT and distributed between switches. Switches will distribute and look up ends in the global DHT that are important to them. TeleHash defines the SHA-1 hash of the external IP:PORT of a switch as part of the protocol. Applications built on top of TeleHash can add their own ends to the DHT like hashes of files, hashes of e-mail addresses or hashes of other application-specific values (e.g. user@chat).

Example of storing the user@chat as an end


kbuckets: data structure kept by each switch that stores a local representation of the global DHT. There are 160 kbuckets (one for each bit in a SHA-1 hash). kbuckets are filled by comparing each incoming hash value with the switch’s own end (the hash value of its external IP:PORT). Hash values that differ in bit 0 (e.g. bit 0 of own end has value 1, bit 0 of a incoming hash has value 0) are stored in kbucket 0. Hash values that have an identical bit 0 but differ in bit 1 are stored in kbucket 1. Hash values that have identical bits 0 and 1 but differ in bit 2 are stored in kbucket 2, and so on. Given all unique values that can be stored in 160 bits (2^160), 1 in 2 values will be stored in kbucket 0, 1 in 4 in kbucket 1, 1 in 8 in kbucket 2, 1 in 16 in kbucket 3, and so on.

TeleHash’s Distributed HashTable

TeleHash’s global DHT is maintained by the participating switches at any given moment. Switches come online and go offline yet the DHT remains in place because there will always be thousands of switches that remain online. Each switch tries to distribute its own ends – the hashes it is interested in – by sending them to all of the switches it can find. Likewise, each switch will store the ends sent by other switches.

Since each switch has a different end – the external IP:PORT – a given hash will end up in different kbuckets on different switches. Hash X may end up in kbucket 1 on switch A and kbucket 5 on switch B. Suppose switch B receives a lookup request for hash Y but doesn’t know Y. Switch B determines that Y goes in kbucket 7 (distance is 7) yet kbucket 7 and kbucket 6 are empty. It will reply with the IP:PORT (not hashed) of the switch (switch C) that has sent hash X (kbucket 5) since that is the best match it can find. Hash X and Y have the first 5 bits in common meaning that Y will sit in kbucket 5 or lower on switch C. Since kbucket 5 holds 1/64 of all possible values and kbucket 7 only 1/256 the requestor has a better chance of finding Y on switch C, or on a switch known by C. The requestor will eventually be directed to a switch that holds hash Y in its kbuckets (probably 0, 1 or 2) at which time it will receive the IP:PORT (not hashed) of the switch is was looking for.

[Edit by Paul:
According to my understanding, the above paragraph is incorrect. A switch or client that is looking for hash Y will send lookup requests to all the switches whose hashed IP:PORT are closest to the hash being looked for. The requester will keep a list of these IP:PORTs and their hashes. Any switch that receives this lookup request will either reply with the data or a list of IP:PORTs whose hashes are closest to the desired hash value. The requester then updates it’s list to include any IP:PORTs whos hashes are closer to the desired hash and sends lookup requests to these new switches. In this way, the requester will find IP:PORTs whose hashes are stored in higher kbuckets and are therefore closer to the hash value being looked up. Eventually, no closer switches will be found and the search will end (hopefully after finding the desired hash).

In particular, it is incorrect to say that switch B will reply with the IP:PORT of a switch that sent hash X since this switch may have a hash of its IP:PORT that is actually farther from the desired hash key that is being looked for. Also, hash X could sit in any bucket in C (not 5 or lower) since it depends on how close X is to the hash of C’s IP:PORT. If a hash is found, it is likely to be found in a higher k bucket than a lower one.]

Once a switch has found the IP:PORT (not hashed) of another switch the two applications built on top of TeleHash can connect directly.

Through this lookup mechanism switch P will always find the IP:PORT of switch Q if:

  1. Switch P persistently looks for the hash sent out by switch Q on as many switches as possible.
  2. Switch Q persistently sends out the hashes it is interested in to as many switches as possible.

Applications build on top of TeleHash switches can – and should – add their own hashes to the DHT. A chat application for example should instruct the switch to push out the hash of the user name and to look for the hashes of its contacts.

Something went wrong with that request. Please try again.