블록체인은 전세계적으로 분산되어있는 노드들간에 합의를 이루는 과정을 통해서 신뢰를 확보하는데요. 이때 처음 내 컴퓨터에 있는 이더리움 프로그램이 켜질때 어떻게 전세계의 컴퓨터들과 연결되는 걸까요?그것에 관련된 글을 적어 보았습니다.
(이 글은 의문을 품고 공부하면서 동시에 작성되어 두서가 없습니다. 또한 잘못된 정보(혹은 업데이트 되지 않은 정보)가 포함 되어 있을 가능성도 있음을 알려 드립니다.)
이더리움에서 흩어져 있는 노드를 찾을 때 Kademlia DHT 의 일부를 수정해서 사용한다고 하는 글을 보았을 때 좀 이해가 안 갔는데, 이유는 Kademlia은 토렌토등에서 사용되며 특정 노드/ 특정 값을 찾고, 일부 노드에만 분산 저장하기 위한 알고리즘인데, 이더리움도 비트코인처럼 그저 랜덤 하게 설정되는것으로 추측 했었기 때문이다. 특정 노드 / 특정 값을 찾기 위함이라면 이더리움 스웜 (IPFS 와 비슷하며, IPFS 는 그 용도로 이미 Kademlia 를 사용중) 이 말이 되지, 일반 이더리움에서는 어떻게 적용 된다는 말인지 궁금했다. 따라서 좀 더 정확히 알아 보기로 했다.
(비트코인의 경우 마스터링 비트코인에는 '종자노드' 로부터 새로운 노드들의 정보를 얻고, 그 노드들과 연결된 노드로 전파되어 내 노드 정보를 전파하는 동시에 , 연결에 연결된 노드들의 정보를 알 수 있다. 정도로만 나와서 그 많은 노드 정보 중에 선택되는 노드의 기준이 무엇인지 그 책 만으로는 알 수가 없다. 따라서 랜덤으로 생각하고 넘겼는데..이 글을 쓰면서 찾아보니 진짜 랜덤이네. 그렇다면 Kademlia 의 자신과 가까운 녀석들의 정보를 많이 가지고 있게 하는 것이, 적은 노력으로 더 골고루 분포 될 수 있게 하는 힘이 되지 않을까 싶었다.)
먼저 이더리움에서 사용되고 있다는 카뎀리아에 대해서 알아보자.
Kademlia
Kademlia 는 아래와 같은 4개의 프로토콜이 있다.
- PING — 상대 노드가 여전히 살아있는지 확인
- STORE — 노드에 (키,값) 쌍을 저장
- FIND_NODE — 자신의 버킷에 있는 k개의 노드들 (요청된 노드에 가장 가까운)들을 리턴 한다.
- FIND_VALUE — FIND_NODE 와 동작방식이 같으나, 해당 키가 노드ID가 아니라 저장소에 있다면, 해당되는 값을 리턴 해준다.
FIND_VALUE 와 STORE 는 데이터 분산 저장에 관련된 내용이니 분명히 이더리움에서는 (스웜에서는 사용되겠지만) 제외하고, FIND_NODE 와 PING 만 노드 디스커버리를 위해 사용되리라 추측 할 수 있겠다.
이에 따라서 Kademlia 에서 사용하는 노드 디스커버리에 한정 해서 실생활 상황으로 설명 해 보겠다. ,
제주도 서귀포 출신 A군이, 광화문 교보문고를 찾아 가려면, 일단 서울역 가는 방법만 알면되고, 그 후에 서울역에서 광화문 가는 방법을 물어보면 될 것이다. 광화문에 가서 그 근처 사람에게 물어보면 교보문고를 찾을 수 있을 것인데, 그 근처의 지리는 그 근처의 사람이 더 잘 안다는 매우 단순한 논리에서 시작된다.
다시 반복하자면 제주도 서귀포 출신 A 군은 서귀포 근처(거리 상 가까운 지리)에 대해서 잘아는 친구들이 서귀포 각 지역마다 있을 것이다. 서울,대구,부산,광주에 대해서는 그 넓은 지역의 친구 한 명 만 알면 된다. A군이 서울의 신촌의 특정 맛집을 찾는 방식은 서울 친구에게 물어보면 그 서울 친구는 자기 주변의 친구 중에 신촌 근처에 사는 친구의 전화번호를 A군에게 알려주면 될 것이다. 신촌 근처사는 B군이 제주도 특정 맛집을 찾을 때도 마찬가지다. 먼저 아까 교환한 전화번호로 A군에게 전화하면 A군은 그 지역 제주도 친구의 전화번호를 건네 주면 될 것이다.
각 노드가 모든 노드를 알 필요 없이 자기와 가까운 노드에 대해서는 세밀히, 먼 노드에 대해서는 대표격으로 몇개만 안다면, 몇 단계만 거치면 서로서로 찾아 갈 수 있다는 것이며, Kademlia 의 주요 특징은 그 거리를 XOR 연산으로 한다는 것이다. (즉 지리적인 토폴로지로 가까운 노드를 찾는 것이 아님. 이 부분은 문제가 될 소지가 있어 보임. 한국에서 미국 노드와 연결되 있으면 아무래도 추가 부담이 들어가니까)
즉 노드A의 ID 가 1111 이고 노드 B의 ID가 0111 이고 노드 C의 ID가 1110 이면 A와 B의 거리는 굉장히 먼것이고, A와 C의 거리는 매우 가까운 것으로 치고, 자기와 가까운 거리의 노드의 정보에 대해서만 많이 가지고 있고, 멀리 떨어진 정보는 대표노드 한두개씩만 가지고 있는 방식이다. log2 n 쿼리만으로도 모두(아무것이나) 찾을 수 있다.
이더리움에서 노드 디스커버리?
일단 이더리움에서 Kademlia 를 사용한다는 것은 잊어버리고, 어떻게 내 컴퓨터에서 이더리움을 시작하면 ,연결되어야 할 노드들을 알 수 있는지 알아보자.
먼저 구글링을 통해 스택오버플로우의 https://ethereum.stackexchange.com/questions/7743/what-are-the-peer-discovery-mechanisms-involved-in-ethereum 답변을 발견했는데, 아래의 순서로 p2p를 시작한단다.
1. 부트스트랩 노드에 대해 이미 하드코딩되어 알고 있다. (부트스트랩 노드는 항상 활성화 되어 있다고 가정한다)
2. 부트스트랩 노드는 얼만큼의 시간 안 에 그들과 접속한 모든 노드(즉 최신의)들의 리스트를 가지고 있다.
3. 내 노드가 이더리움 네트워크에 접속 할 때 부트스트랩 노드에 먼저 접속해서 최신의 노드들에 대한 정보를 공유한다. (내가 접속하는 순간 나도 그 리스트에 들어가며, 남들이 나에게 연결 할 수 있게 될 것이다)
4. 부트스트랩과는 빠이빠이하고, 정해진 숫자의 공유된 노드 리스트에게 연결한다.
일단 이 답변에서는 Kademlia의 역할이 확실히 보이지는 않는다. 항상 부트스트랩 노드에 의지해서 연결 될 노드를 찾지는 아닐 것이며, 자신의 노드에 예전에 연결된 노드들이 있고 그 노드들의 상태를 확인해서 문제 없으면 다시 연결 할 것이고, 모든 노드에 연결이 안되면, 그때 부트스트랩 전용 노드를 통해 다시디스커버리를 할 것으로 추측 할 수 있다.기존에 가지고 있던 노드들 중 하나만 접속된 다면 이 녀석에게 노드 디스커버리 프로토콜을 적용 해서 추가 노드를 찾을 것이다. 모든 노드가 라우팅테이블을 가지고 있기에.
일단 이 정도 추론해보고, 실제 이더리움에서는 어떻게 구성이 되어있고, 활용되는지 관련 문서를 번역해보고, 소스도 살펴 보았다.
Network Formation
- 새로운 노드는 신뢰 할 만하게 접속 해야할 노드를 찾을 수 있다.
- 노드들은 다른 노드들과 균일하게 접속하기 위해 충분한 네트워크 토폴로지를 갖는다.
- 노드 구분자는 랜덤이다.
RLPx 는 p2p 이웃노드탐색프로토콜로써 사용된 Kademlia 식의 라우팅을 이용한다. RLPx 탐색은 XOR를 위해 512-bit 공개키를 이용하는데 DHT 전체 특징은 구현되지 않았다. 나의 노드가 인터넷에 직접 연결되어 있거나, UPnP 옵션이 있다면 연결 요청을 받을 수도 있을 것이다.
Implementation Overview
패킷들은 동적으로 만들어지고, RLP 엔코딩된 헤더가 앞에 붙으며, 암호화되고, 인증된다. 멀티플렉싱이 패킷의 목적지 프로토콜을 명시한 프레임 헤더를 경유해 작동 된다. 모든 암호계산은 secp256k1로 하며, 각 노드는 정적 개인키를 유지하여야 한다.
RLPx 구현은 다음과 같이 구성된다:
- 노드 디스커버리 <-- 이번 포스트에서는 이것만 집중
- 암호화된 전송
- 프레이밍(Framing)
- 흐름 컨트롤
Node Discovery
노드 디스커버리와 네트워크 형식은 Kademlia-like UDP 식으로 구현되어 있다. Kademlia 와의 주요 차이점은
- 패킷들은 서명된다.
- 노드 아이디는 공개키이다.
- DHT 관련 몇몇 특징이 제외 되었다. (FIND_VALUE 와 STORE)
- XOR 거리는 sha3(nodeid)에 기반하여 계산된다.
노드 아이덴터티
이더리움 각 노드는 공개키(256-bit hash (sha3/Keccak-256)는 해당 노드의 ID 로 사용된다. 모든 노드의 이진 배열 길이는 동일하기에 XOR로 길이를 구하는 토대가 된다. 두 노드간의 거리는 아래와 같다.
istance(n₁, n₂) = keccak256(n₁) XOR keccak256(n₂)노드 테이블 (* 이더리움 특화 말고 일반적인 설명)
각 노드는 자신의 이웃에 해당 하는 다른 노드들에 대한 정보를 유지하고 있다. 모든 노드는 라우팅 역할을 한다고 볼 수 있겠다.이 이웃노드들은 'k-bucket' 이라고 하는 라우팅 테이블을 보유하고 있는데 구조는 다음과 같다.
- 하나의 버킷은 2^i ~2^(i+1) 사이의 값을 갖는 값들로 이루어져 있으며, (0 ≤ i < 256 ) 개의 버킷가 있다.
- 자신의 노드와 다른 노드의 거리 값을 구해서 그 값에 해당 하는 값이 6이면, 2^2~ 2^3 사이의 버킷에 들어간다.
- 각 버킷에는 k 개의 노드 정보(ip,port,nodeid)들을 가지고 있다.( k 는 redundancy 라고 하며 이더리움에서는 k = 16) , 즉 2^10~ 2^(11) 사이의 값도 16개를, 2^100~ 2^(101) 사이의 값 중에서도 16개를 가지고 있으니, 자신과 가까운 노드들일 수록 자세하게 가지고 있는게 확인 된다. 이것은 글 초기의 제주도 서귀포 출신 A군의 이야기를 다시 생각해 보면 쉽게 이해 할 수 있을 것이다.
* 위의 이미지(설명)는 이더리움에서 사용되는 노드테이블 구조와 정확히 매칭되진 않는다. 이더리움은 조금 변경하였다. 실제 코드에는 아래와 같이 설정되어있다.
bucketSize = 16 // 하나의 버켓에 담기게 될 노드 숫자.
// We keep buckets for the upper 1/15 of distances because
// it's very unlikely we'll ever encounter a node that's closer.
hashBits = len(common.Hash{}) * 8
nBuckets = hashBits / 15 // 버킷의 갯수
테이블 안의 노드 정보는 아래와 같이 업데이트 된다.
새로운 노드 (N1)를 만날 때 마다, 대응하는 버킷에 삽입 될 수 있다. 버킷이 k 개 미만의 엔트리를 포함하면, N1은 그냥 첫번째 엔트리에 추가 되며, 버킷에 이미 k 개 항목이 포함 되어 있으면 버킷의 가장 최근에 본 노드 N2에 ping 패킷을 보내서 유효성을 다시 체크하고 N2에서 응답을 받지 못하면 죽은 것으로 간주헤 제거하고 N1이 버킷의 첫번째 엔트리에 추가한다.
노드 찾기 및 라우팅
특정 노드ID에서 가장 가까운 K (k closest nodes) 개의 노드의 위치를 찾아(lookup)보자. 참고로 여기서 k 는 위의 k-bucket 의 k (k=16개였던)와 의미가 다르다.
첫째. 보통 타겟에 가장 가까운 3개의 Node ID 를 찾는다.
둘째. 그 노드들에게 동시적으로 FindNode RPC 콜을 날려준다.
세째. 그 노드들은 가지고 있는 노드 정보 중에 타겟에 가까운 노드를 대답해준다.
네째. 그 노드들로 부터 응답받은 노드를 k-bucket에 담고, 다시 FindNode RPC 콜을 날려준다. 재귀적으로 시행한다.(보통 Kademlia 에서는 이런 행동을 하는 도중에 모든 노드들이 새로운 노드로 노드 테이블을 업데이트 하는데, 이더리움에서도 마찬가지일 것이다. 즉 live node 를 업데이트하는 과정이 find node 과정중에 자연스럽게 발생된다.)
다섯째. 더 이상 가까운 노드를 리턴하지 않으면 종료한다.
이것 역시 이해가 안 간다면, 글 초기의 제주도 서귀포 출신 A군의 이야기를다시 생각해 보면 쉽게 이해 할 수 있으리라 본다.
연결 결정/유지
RLPx 는 노드간의 거리 기반으로 'potential' 노드 리스트를 제공한다. 이상적인 피어 숫자(디폴트 5) 에 준하여 잘 작동하는 접속만 유지하려 노력한다.이 전략은 모든 연결되었던 'close' 노드에 대해여 1개의 랜덤한 노드와 접속하는 것에 의해 실현된다. 연결을 결정하기 위한 자신만의 메타데이터와 전략을 사용 할 수 도 있다.
주요 코드 (V4)
golang으로 작성된 코드는 (여기) 에 있으며, cpp 등으로 만들어진 것도 있다. 노드디스커버리에 관련된 소스는 p2p 폴더안의 discover폴더가 버전4, discv5폴더가 버전5를 다루고 있다.p2p 폴더의 server.go에서 시작된 로직은
- table.go 에는 전반적인 kademlia 알고리즘을 관리하고 있으며,
- node.go 에는 kademlia 에서 사용되는 노드 구조체를
- udp.go 에는 kademlia 알고리즘에서 UDP 프로토콜을 사용하여 외부로 통신하는 부분을 담고 있다.
즉 table.go 의 lookup 메소드는 내부에 findnode 메소드를 가지고 있는데 , findnode 메소드는 udp 콜을 한다.
- database.go 에는 node 관련된 정보를 저장한 level.db 와의 통신부분을 담당하며
- ntp.go 에는 network time protocol 의 약자로 이더리움 피어들끼리 현재 시간을 맞추기 위한 로직을 담는다.
부트스트랩 노드 정보 : (소스링크)
var MainnetBootnodes = []string{
"enode://a979fb575495b8d6db44f750317d0f4622bf4c2aa3365d6af7c284339968eef29b69ad0dce72a4d8db5ebb4968de0e3bec910127f134779fbcb0cb6d3331163c@52.16.188.185:30303", // IE
"enode://3f1d12044546b76342d59d4a05532c14b85aa669704bfe1f864fe079415aa2c02d743e03218e57a33fb94523adb54032871a6c51b2cc5514cb7c7e35b3ed0a99@13.93.211.84:30303", // US-WEST
"enode://78de8a0916848093c73790ead81d1928bec737d565119932b98c6b100d944b7a95e94f847f689fc723399d2e31129d182f7ef3863f2b4c820abbf3ab2722344d@191.235.84.50:30303", // BR
"enode://158f8aab45f6d19c6cbf4a089c2670541a8da11978a2f90dbf6a502a4a3bab80d288afdbeb7ec0ef6d92de563767f3b1ea9e8e334ca711e9f8e2df5a0385e8e6@13.75.154.138:30303", // AU
"enode://1118980bf48b0a3640bdba04e0fe78b1add18e1cd99bf22d53daac1fd9972ad650df52176e7c7d89d1114cfef2bc23a2959aa54998a46afcf7d91809f0855082@52.74.57.123:30303", // SG
// Ethereum Foundation Cpp Bootnodes
"enode://979b7fa28feeb35a4741660a16076f1943202cb72b6af70d327f053e248bab9ba81760f39d0701ef1d8f89cc1fbd2cacba0710a12cd5314d5e0c9021aa3637f9@5.1.83.226:30303", // DE
}노드디스커버리 관련 기본 구조체 : (소스링크)
type (
ping struct {
Version uint
From, To rpcEndpoint
Expiration uint64
// Ignore additional fields (for forward compatibility).
Rest []rlp.RawValue `rlp:"tail"`
}
// pong is the reply to ping.
pong struct {
// This field should mirror the UDP envelope address
// of the ping packet, which provides a way to discover the
// the external address (after NAT).
To rpcEndpoint
ReplyTok []byte // This contains the hash of the ping packet.
Expiration uint64 // Absolute timestamp at which the packet becomes invalid.
// Ignore additional fields (for forward compatibility).
Rest []rlp.RawValue `rlp:"tail"`
}
// findnode is a query for nodes close to the given target.
findnode struct {
Target NodeID // doesn't need to be an actual public key
Expiration uint64
// Ignore additional fields (for forward compatibility).
Rest []rlp.RawValue `rlp:"tail"`
}
// reply to findnode
neighbors struct {
Nodes []rpcNode
Expiration uint64
// Ignore additional fields (for forward compatibility).
Rest []rlp.RawValue `rlp:"tail"`
}
rpcNode struct {
IP net.IP // len 4 for IPv4 or 16 for IPv6
UDP uint16 // for discovery protocol
TCP uint16 // for RLPx protocol
ID NodeID
}
rpcEndpoint struct {
IP net.IP // len 4 for IPv4 or 16 for IPv6
UDP uint16 // for discovery protocol
TCP uint16 // for RLPx protocol
}
)FIND_NODE 함수: (소스링크)
// findnode sends a findnode request to the given node and waits until
// the node has sent up to k neighbors.
func (t *udp) findnode(toid NodeID, toaddr *net.UDPAddr, target NodeID) ([]*Node, error) {
nodes := make([]*Node, 0, bucketSize)
nreceived := 0
errc := t.pending(toid, neighborsPacket, func(r interface{}) bool {
reply := r.(*neighbors)
for _, rn := range reply.Nodes {
nreceived++
n, err := t.nodeFromRPC(toaddr, rn)
if err != nil {
log.Trace("Invalid neighbor node received", "ip", rn.IP, "addr", toaddr, "err", err)
continue
}
nodes = append(nodes, n)
}
return nreceived >= bucketSize // bucketSize 는 16이고 table.go 파일에 하드코딩 되어 있다.
})
t.send(toaddr, findnodePacket, &findnode{
Target: target,
Expiration: uint64(time.Now().Add(expiration).Unix()),
})
err := <-errc
return nodes, err
}
// pending adds a reply callback to the pending reply queue.
// see the documentation of type pending for a detailed explanation.
func (t *udp) pending(id NodeID, ptype byte, callback func(interface{}) bool) <-chan error {
ch := make(chan error, 1)
p := &pending{from: id, ptype: ptype, callback: callback, errc: ch}
select {
case t.addpending <- p:
// loop will handle it
case <-t.closing:
ch <- errClosed
}
return ch
}
FIND_NODE 패킷 처리 함수(Neighbors 데이터 공유): (소스링크)
func (req *findnode) handle(t *udp, from *net.UDPAddr, fromID NodeID, mac []byte) error {
if expired(req.Expiration) {
return errExpired
}
if !t.db.hasBond(fromID) {
return errUnknownNode
}
target := crypto.Keccak256Hash(req.Target[:])
t.mutex.Lock()
closest := t.closest(target, bucketSize).entries
t.mutex.Unlock()
p := neighbors{Expiration: uint64(time.Now().Add(expiration).Unix())}
var sent bool
// Send neighbors in chunks with at most maxNeighbors per packet
// to stay below the 1280 byte limit.
for _, n := range closest {
if netutil.CheckRelayIP(from.IP, n.IP) == nil {
p.Nodes = append(p.Nodes, nodeToRPC(n))
}
if len(p.Nodes) == maxNeighbors {
t.send(from, neighborsPacket, &p)
p.Nodes = p.Nodes[:0]
sent = true
}
}
if len(p.Nodes) > 0 || !sent {
t.send(from, neighborsPacket, &p)
}
return nil
}
UDP 객체의 send 메소드: (소스링크)
func (t *udp) send(toaddr *net.UDPAddr, ptype byte, req packet) ([]byte, error) {
packet, hash, err := encodePacket(t.priv, ptype, req)
if err != nil {
return hash, err
}
return hash, t.write(toaddr, req.name(), packet)
}
func (tab *Table) lookup(targetID NodeID, refreshIfEmpty bool) []*Node {
var (
target = crypto.Keccak256Hash(targetID[:])
asked = make(map[NodeID]bool)
seen = make(map[NodeID]bool)
reply = make(chan []*Node, alpha)
pendingQueries = 0
result *nodesByDistance
)
// don't query further if we hit ourself.
// unlikely to happen often in practice.
asked[tab.self.ID] = true
for {
tab.mutex.Lock()
// generate initial result set
result = tab.closest(target, bucketSize)
tab.mutex.Unlock()
if len(result.entries) > 0 || !refreshIfEmpty {
break
}
// The result set is empty, all nodes were dropped, refresh.
// We actually wait for the refresh to complete here. The very
// first query will hit this case and run the bootstrapping
// logic.
<-tab.refresh()
refreshIfEmpty = false
}
for {
// ask the alpha closest nodes that we haven't asked yet
for i := 0; i < len(result.entries) && pendingQueries < alpha; i++ {
n := result.entries[i]
if !asked[n.ID] {
asked[n.ID] = true
pendingQueries++
go func() {
// Find potential neighbors to bond with
r, err := tab.net.findnode(n.ID, n.addr(), targetID)
if err != nil {
// Bump the failure counter to detect and evacuate non-bonded entries
fails := tab.db.findFails(n.ID) + 1
tab.db.updateFindFails(n.ID, fails)
log.Trace("Bumping findnode failure counter", "id", n.ID, "failcount", fails)
if fails >= maxFindnodeFailures {
log.Trace("Too many findnode failures, dropping", "id", n.ID, "failcount", fails)
tab.delete(n)
}
}
reply <- tab.bondall(r)
}()
}
}
if pendingQueries == 0 {
// we have asked all closest nodes, stop the search
break
}
// wait for the next reply
for _, n := range <-reply {
if n != nil && !seen[n.ID] {
seen[n.ID] = true
result.push(n, bucketSize) // 새로 얻는 노드를 통해서 다시 찾기 위해 result 에 푸시
}
}
pendingQueries--
}
return result.entries
}
이더리움의 node discovery 는 비트코인에 비해 적은 노력으로 최신의 상태를 잘 반영 할 수 있으며, 보다 더 신뢰가능하며,고른 분포를 가진 망을 구성 할 수 있으리라 보인다.
실제 데이터를 주고 받는 WIRE 프로토콜에서는 이렇게 노드디스커버리에 의해 연결 가능한 노드들만으로 이루어진 라우팅테이블에 담긴 노드들중 랜덤하게 선택 하여 실제 스트림 통신을 하게 된다.
- Node Discovery and Network Formation
- Peer Preference Strategies
- Peer Reputation
- Multiple protocols
- Encrypted handshake
- Encrypted transport
- Dynamically framed transport
- Fair queuing
레퍼런스:
https://rchain.atlassian.net/wiki/spaces/CORE/pages/15564804/Ethereum+P2P+Node+Discovery+and+Routing
https://github.com/ethereum/devp2p/blob/master/discv4.md
https://github.com/ethereum/devp2p/blob/master/rlpx.md
https://eprint.iacr.org/2015/263.pdf
'블록체인' 카테고리의 다른 글
| [이더리움 메모] 트랜잭션의 실전적 종류 구분. (0) | 2018.06.05 |
|---|---|
| [이더리움 메모] 스마트 컨트랙트와 비용 (0) | 2018.06.01 |
| [블록체인] TPS 그리고 Disruptor 패턴 (0) | 2018.05.12 |
| [이더리움] Merkle Patricia Tree (MPT) 를 이해하기 위한 여정 (4) | 2018.05.10 |
| [블록체인] 개발자를 위한 블록체인 로드맵 (1) | 2018.04.15 |
개발자를 위한 비트코인(블록체인)_ver발표.pdf
