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 두 부분을 정의합니다. Nodes는 Link 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
""
}
