• IPFS 프로토콜 Kademlia 기본 모델 계층 분석

    분산 시스템

    기존의 라우팅 프로토콜에서는 다른 노드를 찾는 서비스를 제공하는 중앙 집중식 서버가 존재합니다. 상호 연결을 하는 경우 각 노드는 동일한 중앙 서버에 등록해야 합니다. 이러한 방식으로, 사용자의 고유 식별 정보에 기초하여 두 당사자에 대한 연결이 성립 됩니다. 분산 시스템에서는 어느 누구도 각 노드의 정보를 관리하지 못합니다. 노드와 노드는 상호 연결되어야 합니다. 특정 알고리즘과 방법을 통해 서로를 찾고, 서로를 식별하고 연결을 설정해야 합니다. 각 노드에는 온라인 네트워크 노드를 나타내는 고유의 node_id 가 있습니다.

    분산 시스템

    Kademlia 기본 모델

    네트워크의 다른 노드를 빠르게 찾고 연결 관계를 유지하려면 현재 노드와 다른 노드 사이의 거리를 계산해야 합니다. kademlia DHT 디자인은 XOR 연산을 사용하여 거리를 계산합니다. 노드 간의 거리(XOR 연산을 통한 노드 ID 사이의 비트 거리)를 기반으로 네트워크 라우팅 정보를 유지합니다.

    XOR 연산

    XOR 연산

    노드 거리를 계산하는 방법은 XOR 연산을 사용합니다. 두 비트의 값이 같으면 XOR 연산의 결과는 0 이고 두 비트의 값이 다른 경우 연산 결과는 1 입니다. 두 네트워크 노드의 ID를 기반으로 이와 같이 계산합니다. 아래 그림에서 노드 ID가 0011 인 A 노드에서 노드 ID가 1110 인 목적지 노드까지 거리는 1101 입니다. 이 XOR 연산을 기반으로 다음과 같은 계산을 유도합니다.

    이웃노드 탐색

    위 그림에서 A 노드 ID에서 다른 노드 ID를 찾는 과정을 간단하게 나열하면 다음과 같습니다.

    • 0번째 비트가 있는 A 노드에는 1 이 있음
    • 처음 세자리는 001 이며 마지막만 다른 노드 즉, ID가 0010 인 노드가 있을 수 있음
      • 해당 노드는 XOR 연산에 따라 거리가 ‘1’ 임을 알 수 있음
    • 1번째 비트를 위와 같이 바라보면 노드와 다른 ID를 가진 노드는 2가지가 있을 수 있음
      • 0000, 0001 임을 알 수 있음
      • 즉, 노드 ID가 00 으로 시작하는 노드가 있음을 알 수 있음
    • 2번째 비트를 위와 같이 바라보면 노드와 다른 ID를 가진 노드는 4가지가 있을 수 있음
      • 0100, 0101, 0110, 0111 임을 알 수 있음
      • 즉, 노드 ID가 0 으로 시작하는 노드가 있음을 알 수 있음
    • 3번째 비트를 위와 같이 바라보면 노드와 다른 ID를 가진 노드는 8가지가 있을 수 있음
      • 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 임을 알 수 있음
      • 즉, 노드 ID가 1 로 시작하며 노드 ID와 공통 시작점을 가지고 있지 않음
    • 이러한 계산을 통하여 A 노드 0011 과의 거리에 따라 다른 카테고리로 나눌 수 있음
      • 0번째 비트와의 거리는 ‘1’
      • 1번째 비트와의 거리는 ‘2~3’
      • 2번째 비트와의 거리는 ‘4~7’
      • 3번째 비트와의 거리는 ‘8~15’

    즉, i 번째부터 시작하는 노드와의 거리는 현재 노드의 [2^i, 2^(i+1)-1] 입니다. 이를 이진트리 형식으로 표현하면 다음과 같습니다.

    이진트리

    위 그림의 각 색상으로 표현된 그룹은 0, 1, 2, 3 번째 비트에서 소스노드 0011 의 ID와 다른 노드 그룹입니다. 이진트리의 경로는 노드 번호의 각 비트의 값으로 나타냅니다. 리프 노드는 네트워크 노드 번호이며 그 값은 루트 노드에서 리프 노드까지의 경로입니다.

    거리계산

    위의 디자인 다이어그램에서 src 노드에서 dst 노드를 찾을 때 위와 같이 src 노드와 dst 노드 사이의 거리를 계산 한 다음 거리와 일치하는 노드 그룹을 찾습니다. 자신의 하프 존에 없는 노드 그룹을 찾고 dst 노드로 부터 절반 거리에 위치한 중계노드인 a 노드를 찾습니다. a 노드는 자신의 라우팅 거리 테이블에서 dst 노드까지 거리보다 절반 짧은 중계노드인 b 노드를 찾습니다. 이런 반복을 통하여 dst 노드를 찾을 수 있도록 합니다.

    이 방법으로 경로를 찾으면 전체 네트워크에 n개의 노드가 있는 경우 최악 검색 속도는 n의 2 로그입니다. 이 알고리즘은 매우 빠른 검색 알고리즘입니다. 노드가 100만 개이면 검색은 최대 20회만에 대상 노드를 찾을 수 있습니다.

    즉, 0011 노드가 1100 노드를 찾는 경우 ‘1’ 로 시작되는 모든 노드 정보를 알 필요 없이 ‘1’로 시작되는 노드 하나만 알면되고, 그 노드를 통해 1100 의 행방을 수소문 하면 되는 것입니다. 결론적으로 Kademlia는 모든 정보를 가지고 있을 수 없는 거대한 집합군에서 특정 노드를 빠르게 O(log2(n)) 찾기 위한 방식입니다.

    k-bucket

    라우팅 저장 정보

    ID가 0011 인 네트워크 노드의 경우 라우팅 테이블에 저장된 정보는 위 그림과 같습니다. 위 그림은 네트워크 ID에 대하여 4가지 비트를 비교하고 모든 노드 정보를 저장하고 있습니다. 그러나 네트워크의 ID가 160 비트까지 늘어나는 경우를 생각한다면 각 노드에 대한 정확한 정보를 저장하는 것은 중복성 및 정확성에 있어 문제가 됩니다. ID의 모든 노드가 항상 온라인 상태가 아니므로 많은 데이터 일관성 문제가 발생합니다.

    IPFS는 이러한 문제를 해결하기 위해 k-buckets 디자인을 적용하였습니다. 이 디자인의 원칙은 로컬 노드와의 거리에 따라 다른 ID 공간의 노드를 그룹화하고, 각 그룹은 최대 K 개의 노드 정보를 저장할 수 있습니다. 예를들어 4비트 ID 공간 주소라면 K = 3 인 경우, 노드는 아래 그림과 같이 라우팅 정보를 저장합니다.

    k-buckets

    위 그림에서 비트로 나뉜 각 그룹은 최대 K 개의 노드 정보를 저장합니다. k-buckets 디자인을 적용하면 각 노드가 저장할 정보의 양을 줄일 수 있습니다. 유효거리가 가까운 노드인 경우 (온라인이 아니거나 노드 정보가 작성되지 않는 경우) 정보를 저장하지 않습니다. 위 그림에서는 그룹 ‘0’ 번이 이에 해당됩니다. ‘3’ 번 그룹의 경우 전체 네트워크 노드 ID 공간의 절반을 담당하기 때문에 온라인 노드 정보를 사용할 수 있습니다.

    노드를 찾을 때 적절한 그룹으로 이동하여 노드를 선택하여 대상 노드에 대한 정보를 요청합니다. 예를들어 a 노드 그룹이 K 보다 작거나 같은 경우 a 노드는 목적지 노드를 찾는데 도움이 됩니다. 검색 프로세스에서 a 노드가 응답하지 않으면 노드 정보를 그룹에서 제거합니다. 응답이 있는 경우 그룹의 k-buckets 큐 끝에 노드를 추가합니다. 즉, 마지막에 저장된 정보는 최근에 사용 가능함을 확인한 노드 정보 입니다. 네트워크 라우팅 과정에서 노드가 사용 가능한 것으로 판명(자신의 k-buckets 대기열 중 하나에 속함)되면 다음 노드 정보가 큐의 끝에 추가됩니다. 만약 큐에 K 개 이상의 노드가 있는 경우 큐의 시작 노드가 사용 가능한지 확인합니다. 연결되어 있는 경우라면 새로 발견된 노드는 추가할 수 없으므로 삭제합니다. 연결되어있지 않다면 큐에서 사용할 수 없는 노드를 제거한 뒤 새로 발견된 노드 정보를 큐 마지막에 추가합니다.

    이를 테스트하면 다음과 같은 그래프를 얻을 수 있습니다.

    시간증가에 따른 온라인 상태

    위 그래프에서 x 축은 시간을 의미하고 y 축은 한 시간전에 온라인 상태인 노드가 온라인 상태를 유지하는 확률을 나타냅니다. 즉, 노드는 온라인 시간이 길수록 상태를 유지하는 경향이 있습니다. 따라서 새로 발견 된 노드를 버리고 오래된 온라인 상태의 노드를 업데이트 합니다. 업데이트 방식의 또 다른 장점은 DOS 공격에 대한 강력한 방어 수단이 있다는 것입니다. DOS 공격이 발생하면 새로운 공격 노드가 이전 온라인 노드의 상태를 대신할 수 없습니다. 또한 새로운 공격 노드의 링크 요청이나 라우팅 정보를 삭제할 수 있습니다.

    IPFS에서 Kademlia 활용

    Kedamlia 프로토콜은 PING, STORE, FIND_NODE, FIND_VALUE 네 가지 유형의 명령을 지원합니다.

    PING은 ID에 대한 노드가 온라인인지 여부를 확인하고 STORE는 이러한 데이터를 저장 노드로 전달합니다. FIND_NODE는 ID에 대한 네트워크 노드 정보를 조회하는 것으로, 실제 네트워크 환경에서는 검색된 노드의 ID가 온라인이 아니거나 생성되지 않는 경우가 발생할 수 있기 때문에 노드를 찾는 명령이 검색으로 진화합니다. 검색중인 ID와 가장 가까운 K 노드를 찾습니다. K 노드는 동일한 k-buckets 리스트에서 찾을 수 있거나, k-buckets가 가득 차있는 경우 가장 가까운 k-buckets 리스트를 검색합니다. 모든 k-buckets 리스트의 노드 정보의 숫자가 충분하지 않으면 정보 숫자가 얼마나 되는지를 반환합니다.

    FIND_VALUEFIND_NODE와 유사하지만 검색 과정에서 K 노드가 발견되기 전에 값(value)을 찾았을 가능성이 있습니다. 일부 값은 캐시되기 때문에 VALUE를 저장하는 노드는 직접 내용을 반환하고 프로세스가 종료됩니다.

    위의 네 가지 명령처리에서 모든 메시지 수신자는 네트워크 주소 스푸핑을 방지하기 위해 임의의 RPC ID를 반환합니다.

    특정 노드 ID에 가장 근접한 K 개의 노드를 찾을 때, K 목표 노드를 찾기 위해 반복 접근법이 사용됩니다. 우선, 라우팅 테이블로부터, 자신에게 가장 가까운 k-buckets 리스트에 있는 노드를 찾은 후 동시에 조회 요청을 시작합니다. 상기 k-buckets의 예에서 K = 3 이기 때문에 a의 값은 1, 2, 3 입니다. 그러므로 같은 k-bucket을 가지고 물어 보는 것이 가장 좋습니다. a = 1 일 때, 룩업 프로토콜은 Chord 네트워크로 진화합니다. 노드의 정보를 질의함으로써, 검색자는 수용된 질의 결과에 따라 가장 가까운 거리를 갖는 새로 발견 된 노드에 검색 명령을 재전송 할 수 있습니다. K 개의 거리 타겟 탐색 노드들에 가장 가까운 노드들로부터, 탐색 정보를 전송하지 않은 노드를 연속적으로 찾고, 이들에게 탐색 명령을 전송합니다. 이러한 노드가 올바르게 응답하지 않거나 오프라인 상태이면 라우팅 정보 테이블에서 노드 정보가 삭제됩니다. 이 프로세스에서 현재 K 노드보다 대상 노드에 더 가까운 노드가 발견되지 않으면 K 노드로 계속 진행하며 조회 명령을 전송하지 않은 나머지 노드는 계속 조회 명령을 전송합니다. 검색 프로세스는 룩업 노드가 타겟 노드에 가장 근접하게 접촉 할 수 있는 K 노드 정보를 찾으면 종료합니다.

    데이터를 저장할 때 가장 가까운 K 개의 거리 키가 있는 노드를 찾고 저장 명령을 보내면 저장된 발신자는 라우팅 데이터의 견고성을 보장하기 위해 24 시간마다 저장 명령을 브로드캐스트합니다.

    데이터를 검색하는 과정에서 캐시를 만날 것이고, K 개의 가장 가까운 노드를 찾기 전에 키의 값을 찾을 것 입니다. 그러면 매우 빨리 데이터를 찾을 수 있습니다. 그러나 데이터 과열 즉, 대상 노드에서 캐시까지의 거리에 따라 많은 사람들이 데이터를 캐시하는 것을 막기위헤 주기적으로 캐시 내용이 삭제됩니다. 물론 대상 노드로부터 더 먼 캐시가 더 빨리 삭제됩니다.

    전달 된 노드의 모든 요청 및 데이터는 노드가 로컬 라우팅 정보를 업데이트하는 것을 도울 수 있습니다. 그러나 인기없는 라우팅 정보 중 아무도 액세스하지 못하면 데이터가 매우 냉각됩니다. 라우팅 정보가 너무 냉각되는 것을 방지하기 위해 노드는 ID를 하나씩 무작위로 선택하고 그에 대한 검색 요청을 시작합니다. 이것은 노드의 따뜻함을 보장할 수 있습니다. 이 검색 프로세스는 조회되는 ID에 대해 자신과 다른 해당 노드를 업데이트 할 수 있습니다.

    네트워크에 새로 결합 된 노드는 이미 네트워크에서 실행중인 노드 하나 이상을 알고 있어야 합니다. 새로운 노드는 먼저 자신의 k-buckets 큐에 알고있는 노드를 추가하고 ID에 대한 조회 요청을 시작합니다. 이런 과정에서 다른 노드가 응답하게 됩니다. 새 노드는 전체 네트워크의 토폴로지를 업데이트하고 다른 노드가 이 최신 노드에 대한 라우팅 정보를 업데이트 합니다.

    Kademlia 라우팅 트리 생성 프로세스

    k-buckets 라우팅 정보는 이진트리 형식으로 저장됩니다. 이진트리의 생성은 동적이며 이진트리 데이터 구조는 발견된 노드의 ID에 따라 동적으로 조정됩니다. 다음은 동적 생성 프로세스를 설명하기 위한 노드 번호가 0000 인 비어있는 이진트리의 예입니다.

    비어있는 이진트리 예

    예 1) 새롭게 발견 된 첫 번째 노드 ID 번호의 첫 번째 비트가 1이면, 두 번째 k-buckets가 생성되고, 첫 번째 비트가 ‘1’인 노드 ID의 정보를 저장합니다. 첫 번째 비트가 ‘0’을 갖는 다른 ID, 이 k-buckets ID의 공간은 현재 노드 0000 을 포함합니다.

    예 2) 첫 번째 노드의 ID 번호가 새로 발견되면 첫 번째 비트는 ‘0’이고 현재 노드 ID 번호는 0000 의 첫 번째 비트와 같습니다. 하지만 두 번째 비트는 1이며 현재 노드 ID 비트의 두 번째 값이 다릅니다. 이런경우 두 개의 k-buckets이 생성되고 ‘00’ 및 ‘01’로 시작하는 ID 정보를 나타냅니다.

    위 내용은 두가지 예로 설명할 수 있습니다.

    • 이진트리에서 새롭게 추가된 노드의 ID가 현재 노드 ID를 커버하는 k-buckets 범위 내에 있으면 현재 노드 ID가 있는 영역을 두개의 k-buckets 으로 분할하고 규칙에 따라 새로운 k-buckets 그룹에 가입됩니다.
    • 새로 추가된 노드 ID가 현재 노드 ID가 위치한 k-buckets 공간과 다른 경우, 자신에 속한 k-buckets 이진트리에 따라 검색되고, 큐가 가득 찼으면 추가되거나 삭제됩니다.

    이진트리 동적 생성 프로세스

    위의 그림은 세 개의 노드가 특정 순서로 추가 될 때 이진트리의 간단한 동적 생성 프로세스를 보여줍니다. 녹색 k-buckets는 노드 ID가 없는 ID 공간을 나타내며 보라색 k-buckets는 노드 ID가 있는 ID 공간을 나타냅니다. 신규 노드의 ID가 현재 ID가 위치하는 ID 공간과 일치하는 경우, 분할 노드의 ID 공간은 2 개의 리프 노드가 됩니다.

    이진트리 동적 조인 프로세스

    네트워크에있는 모든 노드의 ID가 001 로 시작하는 경우 000 을 이 노드에 추가하면 이진트리의 원래 구조는 논리에 따라 삭제해야 합니다. 원래 논리는 k-buckets에서 각 그룹화 노드의 총 수는 K를 초과 할 수 없습니다. 위의 그림에서 노드 0000 의 경우 빨간색 상자의 노드는 k-buckets 통합 표현이어야 하며 버킷이 K 노드를 초과 할 수 없다는 한계를 충족 시키지 몇몇 노드는 삭제해야 합니다. 하지만 이런 경우 라우팅 정보가 손실됩니다. 이 문제를 해결하기 위해 kademlia는 원래의 첫 번째 노드와 새 노드가 생성 된 새로운 이진트리를 생성합니다. 이렇게 하면 새로운 노드 조인 전에 라우팅 구조를 유지 할 수 있습니다.

    Key-Value 데이터 저장 장치의 유효성과 장기적인 성질을 보장하기 위해 노드는 주기적으로 키 정보를 브로드캐스팅해야 합니다. 정보가 정기적으로 업데이트되지 않으면 1) Key-Value를 수락하는 노드가 정보를 저장한 후 노드가 오프라인 상태가 되거나 2) 새로운 노드가 온라인 상태이고 ID 값이 현재 K 노드보다 데이터 게시자에 더 가깝지만 데이터에 대한 정보가 없을 수 있습니다. 위의 두 가지 조건으로 인해 데이터가 검색되지 않을 수 있습니다.

    이 문제를 해결하기 위해 매시간마다 최신 온라인 상태를 얻기위한 조회 명령을 수행하지 않고 간단한 모델을 사용하여 최적화 프로세스를 훨씬 저렴하게 만들 수 있습니다. 노드가 룩업 명령을 수신하면, 다른 K-1 노드가 동일한 명령을 수신 하였으므로, 명령을 수신 한 노드는 자신의 시간을 업데이트하고 다음 시간에 탐색을 수신하지 않도록 타이밍을 설정합니다. 명령어의 경우에는 실제로 룩업 명령어를 발행하므로 실제로 동일한 시간 내에 특정 데이터 쌍의 룩업 명령어에 대해 하나의 노드만 발행됩니다. 이렇게하면 시스템의 메시지 수가 크게 줄어 듭니다.

    또 다른 메커니즘은 k-buckets가 분할 될 때 특정 ID 값의 마지막 K 개 노드의 라우팅 정보를 다시 정렬하고 업데이트하는 것입니다. 이 프로세스는 타이밍 검색의 명령을 어느 정도 완화합니다.

    Kademlia 보안

    k-buckets가 가득차면 노드를 삭제하기 위하여 큐에서 가장 최신의 링크가 유효한지 확인합니다. 유효한 링크인 경우 새로 추가할 노드를 삭제합니다. 유효한 링크가 아닌 경우 이전의 노드가 삭제되고 새로운 노드가 큐 마지막에 추가됩니다. 그러나 이러한 경우 특정 응용 프로그램이 많은 메시지를 생성하여 네트워크에 문제를 발생하게 할 수 있습니다. 새로 추가된 노드는 실제 대기큐에 추가됩니다. 노드에게 검색 명령을 활용하여 응답여부를 확인하고 응답하지 않은 노드는 삭제되고 대기큐에서 k-buckets에 참가할 노드를 선택하게 됩니다. 이를 위하여 대기큐의 노드를 시간대별로 정하는 전략을 사용합니다. 즉, 시간이 가장 짧은 노드가 가장 빨리 교체되는 것 입니다.

    Kademlia는 UDP를 프로토콜로 사용하기 때문에 패킷 손실이나 네트워크 정체로 인한 패킷 지연이 있으며 노드가 제 시간에 응답하지 않으면 RPC 상태 검사가 계속 전송되지 않습니다. RPC 상태 검사에 대한 올바른 응답이 연속 5회 수행되지 않으면 노드는 k-buckets 에서 삭제되지 않지만 관찰 대상으로 표시됩니다. 자체 네트워크의 플래싱으로 인해 노드의 모든 라우팅 정보가 삭제되는 것을 방지하기 위함입니다. 네트워크가 복원되면 라우팅 정보가 업데이트되어야 합니다.

    Kademlia는 검색 속도를 높이기 위하여 이진트리를 사용하지 않고 2^b 크기로 분기되는 트리를 사용하여 트리 높이를 줄이고 검색속도를 높입니다. 그러나 이를 위해서는 k-buckets 라우팅 테이블 크기를 늘려야 합니다.

    S/Kademlia

    S/Kademlia는 악의적 공격에 대비해 두가지 중요한 방식으로 Kademlia를 확장한 디자인입니다. S/Kademlia는 노드ID 생성을 지킬 수 있는 스키마를 제공하여 sybill 공격을 예방합니다. PKI Key-Pair를 생성하기 위해서 노드를 요구하고 이 키에서 아이디를 찾아 서로의 메세지에 서명 할 수 있습니다. 한가지 스키마에는 sybills 를 어렵게 만들기 위한 proof of work 암호화 퍼즐이 포함되어있습니다. S/Kademlia노드는 정직한 노드들이 네트워크 상의 큰 부분의 상대방에게 접속 할 수 있도록 disjoint path에서 값을 탐색합니다. S/Kademlia는 연결에 적대적인 노드가 절반이어도 성공률 0.85정도를 보이고 있다고 합니다.

    노드ID 생성을 지킬 수 있는 스키마란 참여노드의 ID를 랜덤 방식을 사용하여 안전하게 생성함을 의미합니다. 공격자는 이러한 ID 생성 규칙을 통과하지 않는한 공격할 수 없습니다. 또한 주변 노드의 ID를 알 수 있는 방법도 없습니다.

    서명은 약한서명과 강한서명으로 나뉩니다.

    • 약한서명: 노드의 IP 주소, 포트, 타임 스탬프와 같은 메시지 일부를 서명하는 것 입니다. 타임 스탬프 서명에는 유효시간이 지정되어 동적 IP 릴레이 공격 문제를 해결합니다. 약한서명은 메시지 무결성 요구 사항이 요구되지 않는 PING 명령에 사용됩니다.

    • 강한서명: 메시지의 전체 유효성을 보장하고 man-in-the-middle 공격에 효과적으로 대처할 수있는 노드 간 전체 메시지의 서명이며 메시지에 임의의 숫자를 추가하여 릴레이 공격 문제를 해결합니다.

    공격에 대비하기 위하여 노드 ID는 랜덤 방식을 이용하고 공개키를 해싱한 ID를 사용하게 되는데 이를 위한 두가지 방식이 존재합니다. 1) 중앙집중식 인증기관을 통한 방식 과 2) 암호화 퍼즐을 통한 노드 ID 생성 방식 입니다.

    흔히 CA라고 이야기하는 중앙집중식 인증서 방식은 노드가 거의 없거나, 초기 단계에 사용됩니다. 최초 공개 체인에서 초기 노드의 숫자를 파악하고 이 방식을 채택할지 결정합니다.

    완전 분산된 네트워크에서 노드 ID는 매우 어려운 문제를 해결하여야 생성되도록 합니다. 일종의 수수께끼를 풀어야하는 방식인데 크게 두가지 방법이 제공되고 있습니다.

    1. 첫번째 방법
    2. 먼저 비대칭 키 쌍을 생성
    3. 다음 공개 키에 대한 두 가지 해시 작업을 수행
    4. 생성 된 해시 값보다 C1 비트가 0인지 확인
    5. 1에서 다시 시작하여 조건이 충족되면 노드의 ID 번호를 공개 키의 기본 해시 값으로 설정

    6. 두번째 방법
    7. 노드 ID가 생성 된 후
    8. 난수 생성
    9. 노드와 난수 간의 거리를 계산 한 다음 해시 계산
    10. 만족하지 않으면 해시 값의 c2 비트가 0인지 확인 (조건은 난수를 계속 선택하고 조건이 충족되면 노드 ID와 난수 X가 표시)
    11. 악의적인 공격자가 NodeId와 난수 x를 만족하는 많은 양의 정보를 생성하기를 원한다면 엄청난 컴퓨터 자원을 소비합니다. 이 기능은 돌이킬 수 없기 때문에 마이닝 프로세스와 비슷한 값을 찾는 것은 매우 리소스 집약적

    S/Kademlia 는 아직 IPFS의 Main project에 속해있지 않습니다. 하지만 Locality 와 Security 는 매우 중요한 이슈이며 이를 해결할 수 있는 방안은 반드시 필요합니다.

  • IPFS 프로토콜 라우팅 계층 분석

    IPFS 프로토콜 계층 심층 분석

    IPFS는 아키텍처를 6 개의 레이어로 추상화합니다. 각 레이어는 기술 구현 또는 특정 기술 솔루션을 가지고 있습니다. 프로토콜로서 IPFS는 인터페이스 형태로 레이어 간의 기능 및 상호 호출 관계를 정의합니다.

    IPFS 스택

    라우팅 계층 프로토콜

    두 번째 레이어인 라우팅 레이어부터 시작하고자 하는데, 디자인의 첫 번째 레이어인 네트워크 레이어는 기본적인 네트워크 장비 또는 네트워크 기능으로 이해할 수 있습니다. 또한 암호화 전송, 다중 링크 혼합 및 기타 기술을 추가하는 지점 간 링크를 구축 할 수 있습니다. 다음 그림은 IPFS 스택에 대한 기반 기술을 표현한 그림입니다.

    IPFS 스택 기반 기술

    IPFS 라우팅

    라우팅 레이어가 인터페이스 형태로 제공하는 기능을 정의합니다. 라우팅 레이어는 저장된 콘텐츠 검색 및 IPFS 노드의 경로 조회를 지원합니다. 이를 위해 DHTS, mdns, snr 또는 DNS 프로토콜을 사용할 수 있습니다. 네트워크에서 라우팅 프로토콜의 구성은 노드 및 라우팅 데이터를 찾은 다음 init으로 실행되는 IPFS 초기화를 실행합니다. local-discovery를 통하여, IPFS 시스템은 mdns를 라우팅 계층을 로드합니다.

    라우팅 레이어 프로토콜의 함수 정의입니다. 다음과 같이 인터페이스 형식으로 표현합니다.

    IPFS 라우팅 계층 기본 기능

    위 그림은 IPFS 라우팅 계층 프로토콜이 가져야하는 기본 기능을 나타냅니다.

    • ContentRouting: ContentRouting은 간접적인 가치 제공자 계층으로 누가 어떤 컨텐츠를 가지고 있는지에 대한 정보를 찾는 데 사용됩니다.
      • Provide: 특정 키에 따라 현재 노드가 키에 해당하는 값의 저장 위치를 찾고 필요한 경우 브로드캐스트 방식으로 가장 가까운 IPFS 노드에 정보를 브로드캐스팅 할지 여부를 결정합니다. 자신의 IPFS 노드는 키에 해당하는 내용의 저장 경로를 기록하고 상황에 따라 다른 노드에 브로드캐스트하여 다른 사람에게이 노드가 키에 대한 라우팅 정보를 알고 있음을 알립니다.
      • FindProvidersAsync: 키의 라우팅 정보를 알고있는 노드 정보를 획득 할 수 있는 노드의 최대 수를 제한 할 수 있습니다.
    • PeerRouting: PeerRouting은 은 특정 피어에 대한 정보를 찾는 방법입니다. 이것은 간단한 룩업 테이블, 트래킹 서버 또는 DHT를 통해 구현될 수 있습니다.
      • FindPeer: 노드의 ID에 따라 노드에 대한 네트워크 서비스 정보를 얻을 수 있습니다. 키는 IPFS 노드의 ID를 나타내고 반환 정보는 노드에 대한 네트워크 계층 데이터 (예: 포트 번호 및 서비스를 제공하기 위한 프로토콜 유형) 입니다.
    • ValueStore: ValueStore는 기본 Put/Get 인터페이스입니다.
      • PutValue: 라우팅 레이어가 키의 저장 경로뿐만 아니라 키에 대한 특정 콘텐츠를 캐시 할 수 있으며 키에 가장 가까운 라우팅 노드에 콘텐츠를 브로드캐스트 합니다. 정보를 받은 후, 다른 라우팅 테이블은 자신의 라우팅 테이블에 정보를 저장해야 합니다.
      • GetValue: 주어진 키에 따라 라우팅 테이블에 직접 저장된 키에 해당하는 콘텐츠를 얻습니다.
    • IpfsRouting: IpfsRouting은 ipfs가 사용하는 서로 다른 라우팅 유형의 조합입니다. 단일 항목(예: DHT) 또는 각 작업에 더 최적화된 여러 개의 다른 부분으로 만족될 수 있습니다.
      • Bootstrap: 주기적으로 라우팅 테이블 정보를 업데이트하는 타이밍 기능입니다. 분산 라우팅 프로토콜이기 때문에 라우팅 테이블 타이밍에 따라 노드의 업 링크 및 오프라인 정보를 동기화하고 업데이트해야 합니다. Bootstrap 을 통해 호출자는 라우팅 시스템에 힌트를 표시하여 Boostrapped 상태가됩니다.

    IPFS의 라우팅 관련 내용은 다음에서 확인가능 합니다.

    아래는 IPFS에서 사용되는 go-libp2p 패키지중 go-libp2p-routing/routing.go 코드의 일부입니다.

    // package routing defines the interface for a routing system used by ipfs.
    package routing
    
    import ...
    
    // ErrNotFound is returned when the router fails to find the requested record.
    var ErrNotFound = errors.New("routing: not found")
    
    // ErrNotSupported is returned when the router does not support the given record
    // type/operation.
    var ErrNotSupported = errors.New("routing: operation or key not supported")
    
    // ContentRouting is a value provider layer of indirection. It is used to find
    // information about who has what content.
    type ContentRouting interface {
    	// Provide adds the given cid to the content routing system. If 'true' is
    	// passed, it also announces it, otherwise it is just kept in the local
    	// accounting of which objects are being provided.
    	Provide(context.Context, cid.Cid, bool) error
    
    	// Search for peers who are able to provide a given key
    	FindProvidersAsync(context.Context, cid.Cid, int) <-chan pstore.PeerInfo
    }
    
    // PeerRouting is a way to find information about certain peers.
    // This can be implemented by a simple lookup table, a tracking server,
    // or even a DHT.
    type PeerRouting interface {
    	// Find specific Peer
    	// FindPeer searches for a peer with given ID, returns a pstore.PeerInfo
    	// with relevant addresses.
    	FindPeer(context.Context, peer.ID) (pstore.PeerInfo, error)
    }
    
    // ValueStore is a basic Put/Get interface.
    type ValueStore interface {
    
    	// PutValue adds value corresponding to given Key.
    	PutValue(context.Context, string, []byte, ...ropts.Option) error
    
    	// GetValue searches for the value corresponding to given Key.
    	GetValue(context.Context, string, ...ropts.Option) ([]byte, error)
    
    	// TODO
    	// SearchValue searches for better and better values from this value
    	// store corresponding to the given Key. Implementations may halt the
    	// search after a period of time or may continue searching indefinitely.
    	//
    	// Useful when you want a result *now* but still want to hear about
    	// better/newer results.
    	//SearchValue(context.Context, string, ...ropts.Option) (<-chan []byte, error)
    }
    
    // IpfsRouting is the combination of different routing types that ipfs
    // uses. It can be satisfied by a single item (such as a DHT) or multiple
    // different pieces that are more optimized to each task.
    type IpfsRouting interface {
    	ContentRouting
    	PeerRouting
    	ValueStore
    
    	// Bootstrap allows callers to hint to the routing system to get into a
    	// Boostrapped state
    	Bootstrap(context.Context) error
    
    	// TODO expose io.Closer or plain-old Close error
    }
    ...
    
  • Version Control Systems in IPFS

    Merkle DAG

    가장자리가 merkle-link 인 방향성 비순환 그래프입니다. 즉, 객체에 대한 링크는 객체 자체를 인증 할 수 있으며 모든 객체에는 해당 객체의 보안 표현이 포함되어 있음을 의미합니다.

    이것은 분산 시스템을 위한 기본 요소입니다. merkledag는 추가 전용 인증 데이터 구조를 제공하여 분산 프로토콜을 단순화합니다. 당사자는 보안 참조 (merkle-links)를 객체와 교환하고 교환 할 수 있습니다. 참조는 나중에 객체의 정확성을 검증하기에 충분하므로 객체 자체가 신뢰할 수없는 채널을 통해 제공 될 수 있습니다. Merkledags는 또한 버전 제어 시스템 git에서와 같이 데이터 구조의 분기와 후속 병합을 허용합니다. 보다 일반적으로 merkledags는 인증 된 안전한 방법으로 분산, 수렴, 교환 가능하게하는 Secure CRDT의 구성을 단순화합니다.

    Merkle Tree

    머클트리는 이진 해시 트리 (Binary Hash Tree) 라고도 하며 해시 함수로 암호화된 해시값을 이진 트리로 구성된 데이터 구조로 분산 데이터 구조에 주로 쓰입니다.

    그림에서 보면 각 데이터 A, B, C, D의 해시값이 환산되고 A 해시와 B 해시의 합을 해시하여 AB 해시를 만들고 C 해시와 D 해시의 합을 또 해시하여 CD 해시를 만들어 AB 해시와 CD 해시의 합을 해시한 값을 머클 루트 혹은 탑 해시라고 합니다. 이 값은 매우 중요한데 데이터가 하나라도 바뀌면 이 값이 변하기 때문에 데이터가 위변조 되거나 데이터가 변환 되었는지 이 값을 비교하여 효울적으로 검증이 가능합니다. 머클트리는 비트코인 , 이더리움과 같은 블록체인에도 쓰이는데 이 머클 루트 값은 블록 헤더에 포함되는 중요한 값입니다.

    데이터가 증가하면 다음과 같이 확대됩니다.

    머클 루트는 이 수많은 데이터를 하나의 해시 값으로 나타낼 수 있습니다. 이러한 데이터 구조(Data Structure)는 다른 데이터 구조에 비해 많은 장점들을 가집니다. 우선 데이터를 찾고 처리하는 Look up time 을 낮출 수 있어 효율적입니다. 또한, 머클 루트 해시 값으로 데이터 무결성을 효율적으로 검증할 수 있으며 데이터 저장 용량이 중앙 데이터 베이스 구조보다 작기 때문에 확장성 문제 (Scalability)를 해결하는 좋은 방안입니다. IPFS는 이 머클 트리를 변형하여 머클 DAG로 데이터 구조를 설계하여 사용중 입니다.

    Git (Merkle DAG)

    버전 관리 시스템은 시간 경과에 따라 변하는 파일을 모델링하고 여러 버전을 효율적으로 배포 할 수 있는 기능을 제공합니다. 대중적인 버전 관리 시스템인 Git 은 분산된 방식으로 파일 시스템 트리에 대한 변경 사항을 캡쳐하는 강력한 Merkle DAG 객체 모델을 제공합니다.

    • 불변한 객체는 파일(blob), 디렉토리(tree) 및 변경(commit)을 나타냅니다.
    • 객체는 내용의 암호화 해시에 의해 내용이 처리됩니다.
    • 다른 객체에 대한 링크가 내장되어 Merkle DAG를 형성합니다. 이것은 많은 유용한 무결성 및 작업 흐름 속성을 제공합니다.
    • 대부분의 버전 관리 메타 데이터(분기, 태그 등)는 포인터 참조 일 뿐이므로 생성 및 업데이트 비용이 저렴합니다.
    • 버전 변경은 참조를 업데이트 하거나 객체를 추가하면 됩니다.
    • 다른 사용자에게 버전 변경 사항을 배포하는 것은, 단순히 객체를 전송하고 원격 참조를 업데이트 하는 것 입니다.

    Merkle DAG는 Merkle Tree와 약간 다릅니다. Merkle DAG가 더 일반적인 개념인 것이, Binary Tree는 아니지만 그래프이며, 아무 노드나 데이터를 보유할 수 있다는 점입니다. - Merkle Tree에서는 leaf node(가장 아래 세대의 노드만 데이터 보유 가능)

    Merkle DAG 구조를 통해, IPFS는 다음과 같은 세가지 중요한 특성을 갖습니다.

    • Content Addressing : 모든 컨텐츠는 그 자체가 링크이며, multihash checksum으로 그 무결성을 확인할 수 있습니다.
    • Tamper resistance : 모든 컨텐츠는 자체적으로 checksum으로 무결성을 확인할 수 있고, 위변조시 merkle root의 hash값이 변경되기 때문에 IPFS 자체적으로 감지할 수 있습니다.
    • Deduplication : 같은 컨텐츠는 같은 해시값을 갖기 때문에, Merkle DAG 상에서 컨텐츠가 중복되지 않습니다.

    정의

    그림의 상단에 표기된 노드는 데이터와 데이터의 종속 링크 관계를 저장하고 링크는 데이터를 저장합니다. 해시 값은 링크가 데이터의 해시 값이므로이 데이터 구조를 Merkle DAG라고합니다.

    그림의 가운데 세 부분으로 구성된 링크의 데이터 구조는 다음과 같습니다.

    • Name: 하위 데이터의 이름
    • Size: 하위 데이터의 크기
    • Cid: IPFS 네트워크에서 데이터를 찾을 수 있는 하위 데이터의 해시 인덱스.

    그림의 가장 아래부분은 하위 계층의 모든 링크 데이터, 하나의 노드 자체의 데이터, 하나의 노드 데이터의 캡슐화 후 데이터 및 캡슐화 된 데이터를 저장하는 노드의 데이터 구조를 나타냅니다.

    포멧

    IPFS merkledag 형식은 매우 간단합니다. 보다 복잡한 애플리케이션 및 데이터 구조 전송을 위한 허리 역할을 합니다. 그러므로 가능한 간단하고 작게하는 것을 목표로 합니다.

    형식은 논리적 형식과 직렬화 된 형식의 두 부분으로 구성됩니다.

    Logical 포멧

    merkledag 형식은 Nodes와 노드 사이의 Links 두 부분을 정의합니다. NodesLink Segement (또는 링크 테이블)에 Links를 포함합니다.

    노드는 두 부분으로 나뉩니다:

    • Link Segment: 모든 링크 포함

    • Data Segment: 오브젝트 데이터 포함

    IPFS merkledag는 데이터를 대부분 가장자리에 배치하는 merkledags에 대한 이전 접근 방식 대신 HTTP 웹 형식을 채택합니다. 모든 경로 끝점은 링크와 데이터가 모두 포함 된 객체입니다. (이는 오브젝트가 링크 (디렉토리) 또는 데이터 (파일)를 갖는 UNIX 파일과 근본적으로 다릅니다.)

    Logical 포멧 (protobuf)은 다음과 같습니다.

    // An IPFS MerkleDAG Link
    message MerkleLink {
      bytes Hash = 1;   // multihash of the target object
      string Name = 2;  // utf string name
      uint64 Tsize = 3; // cumulative size of target object
    
      // user extensions start at 50
    }
    
    // An IPFS MerkleDAG Node
    message MerkleNode {
      repeated MerkleLink Links = 2; // refs to other objects
      bytes Data = 1; // opaque user data
    
      // user extensions start at 50
    }
    
    Serialized 포멧

    Logical 포멧은 직렬화 형식인 프로토콜 버퍼를 사용하여 raw 바이트로 직렬화 됩니다.

    동작 구성

    위 그림과 같이 test 디렉토리를 만들고 텍스트 파일과 디렉토리 아래에 다른 디렉토리가 만들고 텍스트 파일을 추가합니다. 이 디렉토리 구조는 비교적 간단합니다. 그런 다음 다음 IPFS 명령을 통해 IPFS 네트워크에 업로드 합니다.

    uni2u@uni2u-imac$ ipfs add -r test/
    [added QmZ6LH8CHpfhf6f9cnu1XMieT4wSUPXHePAs97NzVjEStE test/1.txt
     added QmcA9f6fHP75U6VMVFcVr2wrNVGxtJa2hy92jXVfsSexuN test/sub/2.txt
     added QmXEu5pU8t2NZUqLz22Mz9jLrVff5jAPF2jzXsncuTJagf test/sub
     added QmTxemKoT9m1vRqrG3zdaEv51yFCQw2frgf4vi1gsA4FhD test
      20 B / 244 B [====>-----------------------------------------]  8.20%uni2u@uni2u-mac$
    

    업로드가 성공적으로 완료되면 인터페이스는 위와 동일합니다.이 인터페이스는 test 디렉토리의 업로드 정보를 명확하게 보여줍니다.

    데이터 구조에 따르면, test 디렉토리는 위와 같이 저장됩니다. 첫째, 이 디렉토리에 디렉토리와 파일이 있기 때문에 test 전체 디렉토리 해시 값이 있습니다. 두 개의 링크가 있는데 이 두 링크는 각각 데이터 노드 이름, 크기 및 해시 값을 설명합니다. 이 노드의 데이터는 디렉토리 (CAE =)를 나타냅니다.

    다음은 1.txt 파일에 해당하는 노드 데이터 입니다. 이 노드 데이터에는 다음 수준의 데이터 구조가 없으므로 해당 링크가 빈 배열이고 해당 데이터는 1.txt 텍스트 내용의 인코딩 된 데이터 종류입니다.

    유추는 디렉토리 sub와 2.txt의 노드 데이터와 링크 데이터를 얻을 수 있습니다. 다음으로 IPFS 관련 명령을 사용하여 데이터를 확인합니다.

    uni2u@uni2u-imac$ ipfs dag get QmTxemKoT9m1vRqrG3zdaEv51yFCQw2frgf4vi1gsA4FhD
    {"data":"CAE=","links":[{"Cid":{"/":"QmZ6LH8CHpfhf6f9cnu1XMieT4wSUPXHePAs97NzVjEStE"},"Name":"1.txt","Size":22},{"Cid":{"/":"QmXEu5pU8t2NZUqLz22Mz9jLrVff5jAPF2jzXsncuTJagf"},"Name":"sub","Size":65}]}
    uni2u@uni2u-imac$
    uni2u@uni2u-imac$ ipfs dag get QmZ6LH8CHpfhf6f9cnu1XMieT4wSUPXHePAs97NzVjEStE
    {"data":"CAISDnRoaXMgaXMgMS5OeHQKGA4=","links":[]}
    uni2u@uni2u-imac$
    uni2u@uni2u-imac$ ipfs dag get QmXEu5pU8t2NZUqLz22Mz9jLrVff5jAPF2jzXsncuTJagf
    {"data":"CAE=","links":[{"Cid":{"/":"QmcA9f6fHP75U6VMVFcVr2wrNVGxtJa2hy92jXVfsSexuN"},"Name":"2.txt","Size":14}]}
    uni2u@uni2u-imac$
    uni2u@uni2u-imac$ ipfs dag get QmcA9f6fHP75U6VMVFcVr2wrNVGxtJa2hy92jXVfsSexuN
    {"data":"CAISBjIudHh0ChgG","links":[]}
    uni2u@uni2u-imac$
    uni2u@uni2u-imac$ ipfs get QmTxemKoT9m1vRqrG3zdaEv51yFCQw2frgf4vi1gsA4FhD/1.txt
    Saving file(s) to 1.txt
     22 B / 22 B [===========================================================] 100.00% 0s
    uni2u@uni2u-imac$
    uni2u@uni2u-imac$ ipfs dag get QmTxemKoT9m1vRqrG3zdaEv51yFCQw2frgf4vi1gsA4FhD/1.txt
    {"data":"CAISDnRoaXMgaXMfMS50eHQKGA4=","links":[]}
    uni2u@uni2u-imac$
    uni2u@uni2u-imac$ ipfs dag get QmTxemKoT9m1vRqrG3zdaEv51yFCQw2frgf4vi1gsA4FhD/sub
    {"data":"CAE=","links":[{"Cid":{"/":"QmcA9f6fHP75U6VMVFcVr2wrNVGxtJa2hy92jXVfsSexuN"},"Name":"2.txt","Size":14}]}
    uni2u@uni2u-imac$
    uni2u@uni2u-imac$ ipfs dag get QmTxemKoT9m1vRqrG3zdaEv51yFCQw2frgf4vi1gsA4FhD/sub/2.txt
    {"data":"CAISBjIudHh0ChgG","links":[]}
    

    위 내용은 IPFS의 DFS 명령을 통해 데이터 및 링크 정보를 쿼리하는 것입니다. 해시 값과 파일 또는 디렉토리 이름을 사용하여 노드의 관련 정보를 올바르게 쿼리 할 수 있습니다. 즉 링크의 해시 또는 링크의 이름 필드를 통해 관련 노드 데이터를 직접 쿼리 할 수 있습니다. 이 방법은 웹 사이트를 방문하거나 IP 주소를 통해 웹 사이트에 액세스하거나 도메인 이름을 통해 웹 사이트에 액세스 할 때와 비슷합니다. 이것이 Merkle DAG 레이어가 IPFS 네트워크 프로토콜 아키텍처의 IP 레이어라고 불리는 이유입니다.

    인터페이스

    Merkle DAG의 관련 인터페이스를 살펴 보면 다음과 같습니다. Get 인터페이스의 일부는 다음과 같습니다.

    type NodeGetter interface {
      // Get retrieves nodes by CID. Depending on the NodeGetter
      // implementation, this may involve fetching the Node from a remote
      // maching; consider setting a deadline in the context.
      Get(context.Context, *cid.Cid) (Node, error)
     
      // GetMany returns a channel of NodeOptions given a set of CIDs.
      GetMany(context.Context, []*cid.Cid) <-chan *NodeOption
    }
    

    위의 그림에서 Merkle DAG 계층은 Get 명령어를 수신하면 인터페이스에서 Get (cid) 메소드를 호출합니다.이 메소드는 먼저 Cid 정보에 따라 로컬로 저장된 데이터를 찾아 관련 데이터 블록을 검색하고, 데이터 교환의 GetBlock (Cid) 메서드는 네트워크를 통해 데이터를 가져 오는 데 사용됩니다.

    Merkle DAG의 데이터 구조를 구현하는 데 사용 된 인터페이스 객체는 아래와 같이 데이터 교환 레이어를 정의합니다.

    type BlockService interface {
      io.Closer
      BlockGetter
      
      // Blockstore returns a reference to the underlying blockstore
      Blockstore() blockstore.Blockstore
      
      // Exchange returns a reference to the underlying exchange (usually bitswap)
      Exchange() exchange.Interface
      
      // AddBlock puts a given block to the underlying datastore
      AddBlock(o blocks.Block) error
      
      // AddBlocks adds a slice of blocks at the same time using batching
      // capabilities of the underlying datastore whenever possible.
      AddBlocks(bs []blocks.Block) error
      
      // DeleteBlock deletes the given block from the blockservice.
      DeleteBlock(o *cid.Cid) error
    }
    
    type blockService struct {
      blockstore blockstore.Blockstore
      exchange exchange.Interface
      // If checkFirst is true then first check that a block doesn't
      // already exist to avoid republishing the block on the exchange.
      checkFirst bool
    }
    

    Discussion

    Real World Examples

    많은 성공적인 분산 시스템은 전문 merkledags를 핵심으로 사용:

    • merkle trees (merkle dag의 special case) 대량의 데이터를 인증하는데 사용되는 잘 알려진 암호화 기술입니다. 원래의 유스 케이스에는 일회성 lamport 서명이 포함되었습니다.
    • SFS-RO는 유닉스 파일 시스템을 merkledag로 바꾸어 안전한 분산 파일 시스템을 제공합니다.
    • git은 merkledag를 사용하여 분산 버전 제어 및 소스 코드 관리를 가능하게 합니다. 다양한 변경(mercurial), 단조로움(monotone)과 같은 다른 DVCSes도 merkledag를 특징으로 합니다.
    • plan9는 merkledag를 사용하여 스냅 샷 파일 시스템 (Fossil 및 Venti)을 구성합니다.
    • bittorrent는 다운로드 가능한 torrent에 안전하고 짧은 intohash 링크를 제공하기 위해 merkledag를 사용합니다.
    • Google Wave (분산 커뮤니케이션 플랫폼)는 merkledag를 사용하여 교환 가능한 운영 변환을 구성하고 융통성있는 분산 공동작업을 지원합니다. 이 기능은 이후 Google 문서도구로 통합되었습니다.
    • bitcoin은 merkledag를 사용하여 집중 분산 컨센서스가 있는 공유 추가 전용 원장 인 블록 체인을 구성합니다.
    • Tahoe-LAFS는 merkledag를 사용하여 최소 권한 원칙에 기반한 안전하고 분산된 기능 파일 시스템을 구축합니다.
    Thin Waist of Data Structures

    IPFS는 merkledag를 기본(또는 “Internet layer”)으로 제공하여 정교한 응용 프로그램을 쉽게 구축 할 수 있습니다. 이는 모든 복제, 라우팅 및 전송 프로토콜에 걸쳐 (공통 형식을 따르기로 합의함으로써) 실행될 수 있는 안전한 분산형 애플리케이션에 대한 “Thin-Waist” 입니다. 유추를 이끌어 내기 위해 이것은 특정 네트워크를 통해 호스트를 연결하기 위해 제공되는 “Thin-Waist” IP와 같습니다.

    이러한 종류의 모듈화는 공통 기반을 통해 쉽게 복잡하고 강력한 애플리케이션을 작성할 수 있습니다. 인증, 배포, 복제, 라우팅 및 전송의 모든 복잡성은 다른 프로토콜과 도구에서 가져올 수 있습니다. 이러한 종류의 모듈화는 계층화된 인터넷(TCP/IP 스택)을 엄청나게 강력하게 만들었습니다.

    Web of Data Structures

    어떤 점에서 IPFS는 merkledag를 공통 분모로 갖는 “데이터 구조의 웹”입니다. 형식에 동의하면 서로 다른 인증 된 데이터 구조를 서로 연결할 수 있어 정교한 분산 응용 프로그램이 데이터를 쉽게 작성, 배포 및 연결할 수 있습니다.

    Linked Data

    merkledag는 일종의 Linked-Data입니다. 링크는 표준 URI 형식을 따르지 않고 보다 일반적이고 유연한 UNIX 파일 시스템 경로 형식을 선택하지만 주요 내용은 모두 여기에 있습니다. JSON-LD와 같은 형식을 IPFS-LD(IPFS-LD)에 직접 매핑해 시멘틱 웹의 성능을 최대한 활용할 수 있습니다.

    콘텐츠 (및 ID) 주소 지정의 강력한 결과는 링크된 데이터 정의를 콘텐츠 자체와 함께 직접 배포 할 수 있으며 원래 위치에서 제공 할 필요가 없다는 것입니다. 이를 통해 링크 된 데이터 정의, 사양 및 네트워크에서 가져올 필요가 없거나 연결이 끊어 지거나 완전히 오프라인이 될 수 있는 응용 프로그램을 만들 수 있습니다.

    Merkledag Notation

    다른 데이터 구조 및 프로토콜의 정의를 용이하게하기 위해 Merkledag 데이터 구조를 표현하는 표기법을 정의합니다. 이는 논리적 표현을 정의하고 형식 스펙 (ipfs merkledag 형식을 사용할 때)을 정의합니다.

    tree node {
      links {
    
      }
    
      data {
    
      }
    }
    
    commit node {
      "parent" repeated link; // links to the parent commit
      "author" link;          // link to the author of commit
      ""
    }
    

    아직 끝난것이 아니고 계속 진행중

    Reference

  • File Exchange in IPFS

    File Exchange (IPFS BitSwap Protocol)

    BitSwap은 BitTorrent에서 영감을 얻은 프로토콜입니다. BitTorrent에서처럼, Peer들은 본인이 얻고 싶은 파일블록(want_list)와 본인이 갖고 있는 파일블록(have_list)가 있습니다. 그러나, BitTorrent는 하나의 파일을 받고자할 때 그 파일의 블록들만 한정적으로 받아올 수 있는 반면, BitSwap에서는 일치하는 파일블록이라면 어떤 파일에 속해 있든지 받아올 수 있다는 장점이 있습니다.

    만약 노드들이 받기만 하려고하고 줄 생각이 없다면 문제가 발생합니다. 이를 해결하기 위해 BitSwap는 기본적으로 물물교환 시스템(barter system)을 표방합니다. 무언가 받기 위해서는 무언가 주어야합니다. 상대방에게 내가 원하는게 있지만, 내가 대가로 줄게 없으면 (filecoin 구상이 시작된 배경이기도 합니다.) 그 노드는 열심히 일해서 굉장히 희귀한 파일블록이라도 얻어서 보유해놓아야 합니다. (이는 희귀한 파일블록들이 더욱 배포, 확산되는 효과를 낳습니다.)

    또한 BitSwap Credit 시스템을 통하여, 노드들이 peer에게 파일블록을 보내주면, 보낸 노드는 자산이 증가하며, 받은 노드는 부채가 증가하게 됩니다. 결국 평판이 쌓이는 구조이므로 받기만 하려는 어뷰징을 막을 수 있고, 파일블록을 보유하고 보내주는 것에 인센티브가 생기게 됩니다.

    BitTorrent에서는 Tit-for-tat(눈에는 눈, 이에는 이) 전략이 표준으로 되어있지만, BitSwap의 노드들은 각자 자신의 전략을 설정할 수 있습니다. 이러한 전략들의 총체는 곧 BitSwap 생태계의 성능을 좌우하게 될 것 입니다.

    IPFS의 File Exchange 특성인 IPFS BitSwap Protocol을 알아보기 위하여 우선 그 기본인 BitTorrent를 짚고 넘어가겠습니다.

    BitTorrent

    BitTorrent는 오늘날 개별 파일 공유에 가장 많이 사용하는 대표적인 프로토콜입니다. 또한 저작권 측면에서 보면 2010년 이래에 20만명 이상이 저작권으로 고소당하기도 했던 장본인이기도 합니다. 2001년 Bram이 처음 만든 이 프로토콜은 BitTorrent-Protocol을 참고하기 바랍니다.

    IPFS는 BitSwap Protocol의 기본을 위한 BitTorrent

    BitTorrent는 트래픽을 어지럽히는 주범이라고 하지만 오늘날 트래픽의 가장 큰 부분을 차지하고 있는 프로토콜입니다. 기존의 서버-클라이언트 방식이 아닌, 클라이언트-클라이언트 방식의 P2P를 사용합니다. P2P 방식을 이용하여 자료를 공유하면 공유하는 사용자가 많을수록 다운로드 속도가 빨라지는 특징을 보입니다.

    특징

    P2P(Peer-to-Peer) 방식을 사용하는 프로토콜로 서버-클라이언트 구조의 일대일 공유 방식이 아닌 클라이언트-클라이언트 구조의 일대다 파일 공유 방식을 사용합니다.

    일대일 파일 공유 방식은 서버가 원본 파일을 가지고 있고 클라이언트가 서버로부터 원본 파일을 받아가는 방식(그림의 a)입니다. 일대일 파일 공유 방식은 인터넷 환경과 서버의 성능/정책에 따라 파일 전송 속도가 결정되며 전송이 완료될 때까지 유지됩니다.

    일대다 파일 공유 방식(그림의 b)은 원본 파일을 조각(piece)으로 나누어 각 클라이언트간 조각을 교환하는 방식입니다. 각 클라이언트들은 파일을 공유하는 새로운 클라이언트를 발견하면 자신의 조각 정보를 알려주고 새로운 클라이언트에게 자신이 필요한 조각을 요청합니다. 이러한 방식은 하나의 클라이언트에 여러 클라이언트가 세션을 생성하게되고 세션이 늘어나면 사용자의 다운로드 속도가 늘어나 클라이언트가 사용하는 인터넷 환경의 최대 대역폭까지 다운로드 속도를 증가시킵니다.

    동작원리

    BitTorrent는 P2P 방식을 사용하는 대표적인 프로토콜입니다. P2P 방식은 클라이언트와 클라이언트 간에 세션이 직접 생성되어 공유하고자 하는 파일을 여러 개의 조각(Piece)으로 나누어 주고받는 것이 특징입니다.

    대표적인 공유 정책으로 ”optimistic unchoking” 메커니즘이 있습니다. 해당 메커니즘은 클라이언트의 대역폭을 일부 강제적으로 할당하여 무작위로 피어들에게 조각을 보내어 모든 피어들이 일정한 조각을 가지도록 하며, 이와 같은 원리를 통해 공유 속도와 효율성을 증대하였습니다.

    • Piece(조각): 공유 파일을 작게 조각 낸 파일
    • Seeder(시더): 공유 파일 완전체를 가지고 있는 클라이언트 (파일의 모든 조각을 소유)
    • Leecher(리처): 공유 파일 불완전체를 가지고 있는 클라이언트 (파일의 일부 조각만을 소유)
    • Peer(피어): 시더와 리처를 합한 의미
    • Tracker(트래커): 피어들의 정보를 관리하는 서버
    • Swarm(스웜): 각 공유 파일마다 존재하며, 공유 파일에 대한 고유 식별자(Hash)와 공유 파일을 소유하고 있는 피어 리스트 정보를 가짐
    .torrent file

    요청파일 고유의 Hash 값이 포함되어 있으며 트래커의 URL 주소가 포함되어 있습니다. Hash 값은 파일 식별자로써 동일한 파일 이름을 가진 다른 컨텐츠와 구분을 위하여 생성되는 고유의 값이며 트래커의 URL은 파일을 공유하는 피어들의 정보를 관리하는 서버(트래커)를 지정하는 것 입니다.

    Tracker Request

    다운로드 받고자 하는 사용자가 토렌트 파일을 실행하면 BitTorrent 클라이언트는 토렌트 파일에 포함된 요청파일의 고유 Hash 값을 트래커(토렌트 파일에 포함되어 있는 URL)로 전송하는데 이 메시지를 의미(HTTP Get과 비슷한 의미)합니다. 동일한 토렌트 파일을 사용하여 요청파일을 공유하고 있는 모든 피어들은, 트래커에게 해당 파일의 Hash 값을 보내게 되며 피어들로부터 Tracker Request를 받은 트래커는 해당 파일의 Hash값에 해당하는 스웜(Swarm)을 생성하고 해당 파일의 Hash 값을 보낸 피어 IP 주소를 스웜을 통해 관리합니다.

    Tracker Response

    Tracker Request 패킷을 전송 받은 트래커는 피어들에게 Tracker Response 패킷을 전송합니다. 이 때 트래커는 피어들이 보낸 식별자에 대한 스웜이 존재하는지 파악하고, 존재하지 않는다면 다른 피어가 Tracker Request 패킷을 보낼 때까지 대기합니다. 스웜이 생성되면 Tracker Request 동작을 수행하고 있던 피어 리스트를 피어들에게 전송하는데 이 때의 메시지 또는 패킷을 Tracker Response 라고 합니다. 피어 리스트는 기본으로 50개의 피어 IP 주소로 구성되며, 만약 스웜에 저장되어 있는 피어들의 주소가 50 이상이라면 무작위로 피어 주소들을 리스트로 구성하여 전송하게 되고, 50 개 미만이면 모든 피어 리스트를 전송합니다.

    File Download

    트래커로부터 Peer 리스트를 받은 피어들은 서로에게 공유 파일의 식별자를 전송합니다. 식별자를 전송 받은 피어들 중 파일 조각을 보유하고 있어, 해당 공유파일에 대한 공유가 가능한 피어라면, 동일한 식별자를 공유를 요청한 피어에게 전송하여 서로 간의 공유 세션을 형성합니다. 이 때 피어들은 피어 리스트에 의해 최대 50 개의 세션을 동시에 형성하게 되고, 공유 파일은 일정 크기의 조각으로 나뉘어 공유합니다. 그 후, 피어들은 자신이 가지고 있는 조각을 파악하고 자신이 가지고 있지 않은 조각을 다른 피어에게 요청하며, 자신이 가지고 있는 조각을 다른 피어가 필요로 하면 조각을 해당 피어에게 전송합니다. 이와 같은 과정을 통해 다운로드와 업로드가 동시에 일어나게 됩니다.

    .torrent 구조 (시드 파일 구조)

    시드 파일은 일반적으로 토렌트 파일이라고도 불리며, 파일 공유를 위한 여러 메타데이터를 담고 있는 메타파일 입니다. 공유파일이 하나인 싱글 시드 파일과 공유파일이 여러 개인 멀티 시드 파일로 구분할 수 있습니다.

    Name Parameter 설명
    Torrent Filename 토렌트 파일명 (파일명.torrent)
      Info Hash 공유 파일의 Hash 값
    Tracker Tracker URL 트래커 URL 주소 / 여러 트래커 주소 포함 가능
    Metadata Directory 토렌트 파일이 저장되는 디렉토리 이름 (싱글 시드 파일과 멀티 시드 파일 구분)
      Created On 토렌트 파일 생성 일시
      Created By 토렌트 파일 생성자 정보
      Comment 생성자의 코멘트
      Piece Length 피어간 주고받을 조각 크기 / 최소 128KByte
      Private 개인 파일 여부 On/Off
    Files Filename 공유 파일 실제 파일명

    Directory, Piece Length, Private, Filename이 Hash 값을 생성하기 위해 사용되는 파라미터입니다. 기존 P2P는 하나의 파일만 주고받을 수 있었지만 BitTorrent는 하나의 토렌트 파일 안네 여러 파일을 포함시킬 수 있습니다. (토렌트 파일의 “Directory” 를 지정하여 “Files” 내 여러 개의 파일을 포함 시켜서 배포 가능)

    Peer to Tracker 통신

    Peer와 Tracker 통신은 HTTP를 사용하며 클라이언트가 실행한 토렌트 파일(.torrent)에 포함된 정보를 통해 트래커에게 피어 리스트를 요청합니다. 요청을 받은 트래커는 클라이언트의 Hash 정보를 기반으로 스웜에 속한 피어들의 리스트를 요청한 후 클라이언트에 전송합니다.

    Tracker Request 및 Tracker Response 에서 전달되는 정보들은 다음 표와 같습니다.

    Message Parameter 설명
    Tracker Request info_hash 토렌트 파일에 포함된 공유 파일의 Hash 정보
      peer_id 클라이언트 식별 ID
      port Tracker Response 메시지용 클라이언트 port
      upload 업로드 파일 합 (바이트)
      download 다운로드 파일 합 (바이트)
      left 다운로드 받을 남은 파일 크기 합 (바이트)
      key (option) 클라이언트 IP 변경에 무관하게 클라이언트 인식을 위한 값 (피어간 공유하지 않음)
      event Started: 파일전송 시작 / Stopped: 파일전송 중지 / Completed: 파일전송 완료
      numwant (option) 몇개의 피어 정보를 받을것인지 요청 (기본: 50)
      compact Set1: 피어들의 IP 주소와 Port 정보만 받음 / Set0: IP 주소와 Port 외에 Peer-ID 등의 정보를 받음
      no_peer_id Peer-ID는 생략하고 정보 요청 (Compact=1의 경우 무시)
      ip (option) 클라이언트 IP 주소
    Tracker Response complete 현재 파일 공유 시더 수
      downloaded 공유 파일 다운로드 완료 횟수
      incomplete 현재 파일을 다운로드 하고 있는 리처 수
      interval Tracker Request 전송 Interval (단위: 초)
      min interval (option) Tracker Request 전송 최소 Interval (단위: 초)
      peers 피어 IP 리스트

    Peer to Peer 통신

    트래커를 통해 피어 리스트를 받은 BitTorrent 클라이언트는 리스트에 있는 피어들과 BitTorrent 프로토콜을 이용하여 통신을 시작합니다. 클라이언트는 파일을 교환하기 위하여 피어들과 서로의 정보를 주고 (Handshake) 받습니다.

    이후 피어들은 자신이 가지고 있는 조각의 정보를 피어들에게 주기적으로 알려주며 자신이 필요한 조각은 대상 클라이언트에게 요청하여 조각을 받습니다.

    클라이언트는 Handshake(1~4) 이후 피어 1과 피어 2에서 Have 메시지(5~6)를 받았습니다. 해당 Have 메시지에는 피어 1과 피어 2가 가지고 있는 조각의 정보가 포함되어 있습니다. 이러한 Have 메시지를 통해 사용자는 피어 1이 가지고 있는 조각을 알게 됩니다. 0x000001ed라는 조각을 피어 1에게 요청(Request 메시지)하여 피어 1로부터 해당 조각을 Piece 메시지를 통해 전송 (7~8) 받게 됩니다.

    이후 사용자는 자신이 새로운 조각을 가지게 되었으므로 Have 메시지를 통해 0x000001ed인 조각을 자신이 가지고 있다고 피어 1과 피어 2에게 (9~10) 알립니다. 피어 2에서 0x000001ed인 조각을 사용자에게 요청하는 경우(11), 사용자는 자신이 가지고 있는 조각이므로 피어 2에게 해당 조각을 전송(12) 합니다. 이러한 방식으로 피어와 피어 간에 조각 교환이 계속하여 발생하게 됩니다.

    피어간 통신에 사용되는 메시지는 다음표와 같습니다.

    Message 설명
    Keep-alive 대상 피어가 온라인 상태인지 체크하는 메시지
    Choke Request 에 대한 응답을 할 수 없음을 알리는 메시지
    Unchoke Choke 상태를 해지하여 Request 에 대한 응답이 가능함을 알리는 메시지
    Have 자신이 가지고 있는 조각의 정보를 피어들에게 알리는 메시지
    Request 받고자 하는 조각의 Index와 Offset 정보를 대상 피어에게 알리는 메시지
    Piece 실제 파일 조각, Index 및 Offset 정보가 보함된 메시지

    Reference

  • Distributed Hash Tables in IPFS

    DHT (Distributed Hash Tables)

    분산 해시 테이블을 의미하는 것으로 말 그대로 해시 테이블을 분산하여 관리하는 기술 입니다.

    어떤 항목을 찾아갈 때 해시 테이블을 이용하는데, 중앙 시스템이 아닌 각 노드들이 이름을 값으로 맵핑하는 기능을 하는 방식으로 부하가 집중되지 않고 분산된다는 큰 장점이 있어, 극단적으로 큰 규모의 노드들도 관리할 수 있습니다.

    살짝 감이 오지 않습니까? IPFS 의 주요 기능말입니다.

    분산 해시 테이블에 대한 기본 이해

    해시 테이블은 Key/Value 데이터 구조로 구성되어 있습니다. DHT는 해싱으로 생성된 데이터 Key 값과 서버 ID 의 짝을 시스템을 구성하고 있는 모든 노드에 균일하게 분산하기 위하여 고안된 lookup 방법입니다. 데이터 Key 값과 서버 ID 를 통하여 모든 노드와 데이터들을 동일 주소 공간에 할당함으로써 데이터와 노드 정보들을 한꺼번에 관리하기가 용이하기 때문에 P2P 시스템에서 많이 사용합니다. (데이터의 Key 값과 분산 서버 ID는 동일한 해시 함수로 동일한 주소 공간에 데이터와 노드를 배치)

    한마디로 중앙 서버 없이 데이터를 관리하는 분산된 서버를 찾을 수 있으며 클러스터에 참여하는 서버의 추가/제거가 자동으로 이루어질 수 있도록 구성할 수 있기 때문입니다.

    부하가 집중되지 않고 분산된다는 큰 장점이 있어, 극단적으로 큰 규모의 노드들도 관리할 수 있습니다. 종래의 순수 P2P에서 채용되었던 방식에서는 수십만 노드 정도가 한계였으나, DHT의 사용으로 수십억개의 노드를 검색범위로 할 수 있게 되었습니다.

    IPFS 에서는 Kademlia DHTBitTorrent 그리고 Git, Self-certifying File System 에 대한 이해를 필요로 합니다.

    각각은 차차 알아보기로 하고 조금 더 DHT 에 대한 이야기를 해보겠습니다.

    IPFS 에서 DHT

    네트워크에 참여한 노드가 해시 테이블을 사용하여 서버없이 P2P 네트워크를 실현하는 기술로 파일(데이터, 컨텐츠)을 검색하는데 사용됩니다.

    HTTP는 IP를 기반으로 검색이 되었으나 IPFS는 Content-Addressed를 사용합니다. 즉, 컨텐츠 자체가 주소역할을 대신 합니다.

    Content Name Node Location
    Content01 Node01
    Content02 Node03, Node05
    Content03 Node02, Node08

    해시테이블에서 컨텐츠 이름을 찾으면 컨텐츠를 보유하고 있는 노드를 알 수 있습니다.

    Kademlia DHT

    Kademlia는 현재 가장 대중적으로 사용되는 P2P DHT 입니다. Kademlia는 다음과 같은 용어에 대한 이해가 필요합니다.

    • Node: node는 Kademlia DHT 네트워크에 참여하는 컴퓨터
    • pair (Key/Value): KV(Key/Value) 형태로 데이터를 저장, Kademlia 네트워크에서 값을 찾기 위한 고유 키이며 값은 DHT에 저장되는 데이터
    • LookUP: Kademlia 네트워크에서 주어진 키에 대한 실제 값을 찾는 과정
    • Data/Content: Kademlia DHT에 pair(KV) 형태로 저장되어 있는 실제 데이터

    Kademlia를 사용하는 이유

    • Node간 주고받는 데이터를 최소화
    • 네트워크에 속한 node, 인접 node 등에 대한 설정 정보가 자동적으로 Kademlia 네트워크에 확산
    • Kademlia 네트워크의 node들은 다른 node를 통해 파악 (적은 비용으로 node간 경로 탐색)
    • Kademlia는 작동하지 않는 node의 timeout을 피할 수 있는 병렬적이고, 비동기적 쿼리 제공
    • DOS 공격 방지

    Key

    Kademila는 Node와 데이터를 식별하기 위해 160 비트 key를 이용합니다. 네트워크에 참여하는 컴퓨터는 각각 160 비트 NodeId 키를 가집니다. Kademila는 pair(KV)로 데이터를 저장하기 때문에 160 비트 key를 사용해서 데이터를 식별합니다.

    Distance

    두 Node 간의 ‘거리’를 계산하는 것으로 두 NodeId의 XOR로 계산되고 정수형 값을 가집니다. Key와 NodeId는 같은 형태, 길이의 정수형 값을 가지고 있기 때문에 XOR연산이 가능합니다. NodeId는 Node를 식별할 수 있는 무작위의 정수형 값(UUID)을 가집니다. 즉, 물리적 거리가 먼 Node라도 NodeId 값이 비슷하다면 논리적으로 이웃에 위치할 수 있습니다.

    • 임의의 Node와 그 Node 자신에 대한 거리는 0
    • XOR 연산은 대칭성을 가짐: A에서 B 거리의 계산 결과는 B에서 A 거리와 동일
    • 삼각 부등식 성립: A, B, C Node가 주어질 경우, A와 B 사이 거리는 A와 C 또는 C와 B의 거리합과 같거나 작음

    위와 같은 특징은 간단하면서 빠른 XOR 연산의 특징을 보여줍니다.

    Kademlia 탐색 작업이 반복될 때마다 한 비트씩 탐색 대상에 가까워집니다. 2^n 개의 Node를 가지고 있는 Kademlia 네트워크에서는 최대 n번 탐색을 반복하면 임의의 Node를 찾을 수 있습니다.

    라우팅 테이블

    각 NodeId들의 각 비트를 저장한 리스트를 포함하고 있습니다. 리스트의 모든 항목은 다른 Node들의 위치에 대한 주요 정보를 저장합니다. 리스트의 각 항목은 일반적으로 다른 Node의 IP 주소, 포트, NodeId를 저장합니다. 후보 id의 n-1번째 비트는 NodeId와 일치하여야 합니다. (모든 리스트는 특정 node의 거리와 대응됩니다. n번째 리스트에 갈 수 있는 Node는 반드시 NodeId의 n번째 비트가 달라야 합니다.)

    128 비트의 id가 있는 네트워크에서는, 128개의 다른 거리로 다른 Node들을 식별하게 됩니다. Node가 네트워크에 참가하게 되면, 리스트에 추가됩니다. 이러한 과정은 통해 다른 Node들이 Key를 찾는 것을 돕습니다.

    프로토콜 메시지

    • PING: Node 작동상태 확인
    • Sotre: 한 Node에 pair(KV) 데이터를 저장
    • FIND_NODE: 요청한 Key에 제일 가깝게 위치한 k Node들을 반환
    • FIND_VALUE: FIND_NODE와 같은 역할을 하며 요청한 Key에 대한 해당 데이터가 있으면 데이터 반환

    요청에 의해 반환되는 RPC 메시지는 발신자가 지정한 랜덤한 값을 포함합니다. 랜덤으로 정해진 값은 요청 메시지와 응답 결과를 대응시키기 위해 사용됩니다.

    Location Nodes

    Node 탐색은 동기적으로 동작합니다. 동시에 일어나는 탐색 요청은 α로 나타내며, 일반적인 α 값은 3입니다. Node은 원하는 Key 값에 가장 가까운 α개의 Node에 FIND_NODE 요청을 전송합니다. FIND_NODE 요청을 받은 Node들은 자신의 k-buckets을 탐색하여 Key 값에 가장 가까운 k개의 Node들을 반환합니다. 탐색 요청자는 요청 결과를 저장하며, k개의 가장 가까운 NodeId를 저장합니다.

    탐색 요청자는 저장하고 있는 NodeId들을 선택하여 각 Node들이 위와 같은 요청을 하도록 하는 작업이 반복됩니다. 각 Node들은 자신 주위에 있는 Node들에 가장 잘 알고 있기 때문에 이러한 작업이 반복될 수록 Key 값에 더 가까운 Node를 찾게 됩니다.

    탐색 작업은 전 탐색 결과보다 Key에 더 가까운 Node들이 없을때까지 반복됩니다. 탐색이 중지되었을때 저장되어 있는 k Node들이 원하는 Key에 가장 가까운 Node가 됩니다.

    Reference