Mainline DHT Protocol (BEP-0005)

bep_0005.rst_post (bittorrent.org)

bep_0005.rst_post

개요

비트토렌트에서는 DHT, PeX를 통해 트래커를 사용하지 않는(trackerless) 토렌트에서 노드를 찾는 방법을 제공하고 있다.

그 중 Kademlia DHT를 수정한 Mainline DHT를 사용해 노드들을 검색한다.

 

BEP-5에서는 노드와 피어를 다음과 같이 구분하고 있다.

"

Please note the terminology used in this document to avoid confusion. A "peer" is a client/server listening on a TCP port that implements the BitTorrent protocol. A "node" is a client/server listening on a UDP port implementing the distributed hash table protocol. The DHT is composed of nodes and stores the location of peers. BitTorrent clients include a DHT node, which is used to contact other nodes in the DHT to get the location of peers to download from using the BitTorrent protocol.

"

 

BEP에 명시된 내용에 의하면 "peer"는 비트토렌트 프로토콜을 TCP로 구현한 클라이언트/서버를 의미하고 "node"는 DHT 프로토콜을 UDP로 구현한 클라이언트/서버를 의미한다. 물론 비트토렌트 클라이언트에서는 둘다 사용한다. 노드가 피어가 될 수도 있고 피어가 노드가 될 수도 있다.

 

라우팅 테이블

라우팅 테이블은 모든 노드가 가지고 있는 노드 목록이다. 모든 노드는 라우팅 테이블을 가지고 있으며 테이블에는 상태 Good 노드들이 들어가있으며 노드에 대한 자세한 정보는 아래에 있다. 라우팅 테이블에 들어가 있는 노드들은 다른 노드에게 쿼리해서 받은 응답에 포함되어 있던 노드 목록을 추가한 것이다. 라우팅 테이블의 중요한 조건은 무조건(must) Good 노드들만을 포함하고 있어야한다. 라우팅 테이블은 노드 ID로 지정되는 범위인 0부터 2^160 사이의 값을 모두 저장할 수 있다. 라우팅 테이블은 다시 bucket 으로 나눠지며 각 bucket은 각 노드 DI 범위별로 나누어져있다. 생성될 때부터 0부터 2^160 사이의 범위의 bucket이 생성되는 것은 아니고 노드가 추가되면서 K개 만큼 쌓이고 그 이상 들어오면 분리를 한다. 현재 K의 기본값은 8로 정해져있다. bucket이 Good 노드로 꽉차게 되면 새로 들어오는 노드들은 추가되지 않고 폐기된다.

 

만약 기존에 bucket안에 있던 노드가 아래 조건으로 인해 Bad 노드로 된 후에 새로 다른 노드를 알게되면 Bad 노드를 bucket에서 제거하고 새로운 노드를 추가한다. 만약 bucket안에 노드가 15분 이내로 아무런 활동도 하지 않으면 Questionable 상태로 보며 해당 노드에게 Ping 쿼리를 날린다. 만약 Ping 쿼리를 받은 노드가 응답을 보내면 해당 노드는 다시 Good 상태로 본다. 노드는 Questionable 노드들 중 가장 마지막으로 확인한 노드에게 Ping 쿼리를 날리며 응답이 오면 그다음 Questionable 노드에게 Ping 쿼리를 날리고 응답을 받지 못하면 해당 노드를 bucket에서 제거한다.

 

이러한 기능을 구현하기 위해서 각 bucket은 "last changed" 라는 속성을 만들어서 bucket의 신선도(fresh)를 유지할 수 있도록 해야한다. bucket 안에 있는 노드가 Ping 응답을 보내거나 새로운 노드가 bucket에 추가되거나, 기존에 있던 노드가 제거되고 새로운 노드로 변경되면 "last changed" 값이 업데이트된다. 만약 bucket의 last changed 값이 15분동안 변경되지 않으면 반드시 업데이트(refreshed) 되어야 한다. 이를 위해서 bucket안에 있는 랜덤 ID를 선택하여 find_node 쿼리를 수행하여 반영할 수 있다.

 

노드

노드들은 크게 Good, Questionable, Bad 노드로 구분된다. 노드들 중에서 Good 노드는 다른 유형(Questionable, Bad) 노드와 비교해서 더 큰 우선순위를 갖는다.

 

Good 노드

• 쿼리을 보내고 15분 이내 응답을 보내준 노드
• 15분 이내 응답을 보내주고나서 15분 이내로 쿼리를 보낸 노드

Questionable 노드

• 15분동안 아무런 활동(쿼리 또는 응답)도 하지 않은 노드

Bad 노드

• 여려 쿼리를 보내도 아무런 응답을 하지 않는 노드

 

노드 ID

모든 노드들은 160-bit 크기의 고유의 ID를 가지고 있으며 이는 토렌트의 infohash와 동일한 길이이다. ID 생성은 랜덤으로 정해지며 생성된 ID를 이용해 다른 노드와의 거리를 계산하거나 노드와 infohash의 근사(closeness)를 계산할 때 사용한다. 노드 ID를 가지고 있는 목적은 라우팅 테이블에 자기 자신과 가까운 ID를 가진 노드 목록을 확보하는 것이다. 계산 방법은 아래에 명시되어 있으며 라우팅 테이블 업데이트를 반복적으로 수행하게 되다보면 유사한 ID를 가진 노드끼리 뭉치게 되는 것 같다.

 

노드 ID를 이용한 거리 계산

ID간의 거리는 XOR로 계산하여 unsigned interger 형식의 정수값을 거리의 척도로 사용한다.

정수값이 작을 수록 더 가까운 노드로 본다.

• 거리 계산법
  • distance(A, B) = |A xor B|

import os

# 160-bit 크기의 랜덤 ID 생성
node_a = os.urandom(20)
node_b = os.urandom(20)

# 두 ID의 거리를 XOR로 계산
distance = int.from_bytes(node_a, 'big') ^ int.from_bytes(node_b, 'big')

print(distance)

 

노드 ID를 이용한 토렌트 피어 검색

토렌트 피어를 검색할 때는 노드는 자기가 가지고 있는 라우팅 테이블에서 infohash와 가까운 노드들을 찾아서 해당 노드들에게 질의한다.

• 노드 선택 방법(거리 계산하고 동일)
  • distance(Node ID, InfoHash) = |Node ID ^ InfoHash|

import os

node_id = os.urandom(20)  # 160-bit 크기의 랜덤 ID 생성
infohash = os.urandom(20)  # 160-bit 크기의 랜덤 Info Hash 생성

# 두 ID의 거리를 XOR로 계산
distance = int.from_bytes(node_id, 'big') ^ int.from_bytes(infohash, 'big')

print(distance)

 

피어 검색 시나리오 (* 노드, 피어 구분)

1. Ubuntu 18.04 ISO 이미지를 다운로드하려고 한다.
2. 토렌트 파일을 다운로드 받아서 토렌트 클라이언트에 등록한다.
3. 토렌트 클라이언트는 토렌트 파일에서 infohash를 계산한다.
4. 클라이언트가 가지고 있는 라우팅 테이블 내 노드와 infohash를 계산해 가까운(distance가 작은) 노드들을 찾는다.
5. 선택된 노드들에게 GET_PEERS 쿼리를 보내서 infohash와 연관된 피어들이 있는지 물어본다.
   1. 선택된 노드에게 infohash와 연관된 피어가 있으면 응답에 보낼 때 해당 피어 정보를 추가해서 보낸다.
   2. 선택된 노드에게 infohash와 연관된 피어가 없으면 자신의 라우팅 테이블에서 infohash와 가까운 노드를 계산하고 응답에 해당 노드에 대한 정보를 추가해서 보낸다.

 

Kademlia DHT와 Mainline DHT의 메세지 유형

Kademlia DHT 메세지 유형

• ping
• store
• find_node
• find_value

Mainline DHT 메세지 유형

• ping
• find_node
• get_peers
• announce_peer

 

Bencode

비트토렌트에서 사용하는 Mainline DHT 알고리즘에서는 피어 간에 주고 받는 메세지를 bencode 방식으로

인코딩/디코딩하여 전송한다.

 

ping 

다른 노드가 살아있는지 확인하기 위해 보내는 메세지

 

요청

{
	"y": "q",
	"q": "<쿼리 유형>",
	"a": {
		"id": "<노드 ID>"
	},
	"t": "<트랜잭션 ID>"
}

응답

{
	"y": "r",
	"r": {
		"id": "<상대노드 ID>"
	},
	"t": "<트랜잭션 ID>"
}

 

find_node

노드에 대한 정보를 찾기 위해 보내는 메세지

요청을 받은 노드는 타겟 ID를 알 경우, 해당 타겟의 정보를 넣는다. 만약 타겟 ID를 모를 경우에는 K(8) Closest Good 노드 목록을 리턴한다. 근데 가까움의 기준이 응답을 하는 노드의 ID를 기준으로 하는지 타겟 ID를 기준으로 하는지는 명시가 되어있지 않다. 아마도 타겟 ID를 기준으로 가까운 K(8) Closest Good 노드 목록을 리턴하는 것 같다.

 

요청

{
	"y": "q",
	"q": "<쿼리 유형>",
	"a": {
		"id": "<노드 ID>",
		"target": "<타겟 ID>"
	},
	"t": "<트랜잭션 ID>"
}

응답

{
	"y": "r",
	"r": {
		"id": "<노드 ID>",
		"nodes": "<K(8) Closest Good 노드 목록 | 타겟 ID를 가진 노드>"
	},
	"t": "<트랜잭션 ID>"
}

 

get_peers

토렌트의 infohash와 연관된 피어들을 찾기 위해 사용하는 메세지다. "a" 키에 ID 외에 추가로 "info_hash" 키가 들어가며 값으로는 토렌트의 infohash 값을 넣어서 요청한다. 만약 요청받은 노드가 받은 infohash값과 연관된 피어들을 알고 있으면 "values" 키에 피어들을 넣으며 각각 피어 정보는 간소화(compact)된 포맷으로 구성되있다. 만약 요청받은 노드가 infohash와 연관된 피어를 가지고 있지 않으면 infohash와 가까운 K(8) closest Good 노드 목록을 추가해서 응답한다. 추가로 token 키도 포함이 되는데 이 값은 이후에 announce_peer 쿼리를 날릴 때 필요한 값이다.

 

요청

{
	"y": "q",
	"q": "<쿼리 유형>",
	"a": {
		"id": "<노드 ID>",
		"info_hash": "<Info Hash>"
	},
	"t": "<트랜잭션 ID>"
}

응답

{
	"y": "r",
	"r": {
		"id": "<노드 ID>",
		"info_hash": "<Info Hash>",
        "token": "<Token>",
        "values": "<피어 목록>",
        "nodes": "<K(8) Closest Good 노드 목록>"
	},
	"t": "<트랜잭션 ID>"
}

 

announce_peer

노드가 피어로도 되며 토렌트 다운로드를 시작한다고 알리는 메세지이다. 인자값으로 들어가는 info_hash는 다운로드하려는 토렌트의 info_hash를 의미하며 token은 get_peers 메세지에서 받은 token 값이 추가되고 port는 다운로드할 때 사용할 포트를 의미한다. announce_peer 메세지를 받는 노드(get_peers에서 응답을 해준 노드)는 token 값과 IP가 일치하는지 확인해야한다. 이는 악성 노드가 네트워크에 조인하는 것을 방지하기 위한 방법이다. 추가로 "implied_port" 키가 응답에 포함될 때도 있는데(즉 없을 수도 있다.) "implied_port"가 0이 아닌 값으로 설정되있는 경우, "port" 키의 값은 무시되며 요청을 보내올 때 사용된 포트를 다운로드할 때 사용한다는 의미이다. 이는 NAT로 인해 포트가 열려있지 않은 환경에서도 다운로드를 할 수 있게끔 하는 방법이다.

 

요청

{
	"y": "q",
	"q": "<쿼리 유형>",
	"a": {
		"id": "<노드 ID>",
		"info_hash": "<Info Hash>",
		"token": "<토큰>",
		"port": "<포트>",
		"implied_port": "<0 또는 1>",
	},
	"t": "<트랜잭션 ID>"
}

응답

{
	"y": "r",
	"a": {
		"id": "<노드 ID>"
	},
	"t": "<트랜잭션 ID>"
}