비트코인과 이더리움 블록 비교

비트코인의 블록은 헤더와 바디로 나누어 볼 수 있습니다. 이더리움도 비트코인의 블록구조와 크게 다르진 않지만 블록의 헤더부분에 uncle_list와 stack_trace 라는 값이 추가되어 있는 형태입니다.


  • uncle list: 비트코인의 이전블록을 이더리움에서 parent 블록이라고 말하기 때문에 생긴 용어. stale 블록을 uncle 블록이라 칭함 (자세한 설명은 아래에서)

비트코인과 이더리움 블록헤더 비교


비트코인이더리움
블록해시hashstate_root
이전 블록해시prev_lbockparent_hash
거래관련된 루트해시mrkl_root

TRIEHASH(transaction_list)

TRIEHASH(uncle_list)

TRIEHASH(stack_trace)

난이도bitsdifficulty
타임스탬프timetimestamp
넌스noncenonce
그외 데이터

size

ver

n_tx

extra_data

(block) numbber

coinbase address (채굴주소)

.... 등등

비트코인과 블록헤더의 구조는 거의 유사하나 블록해시를 구할 때, 몇 가지 항목이 더 추가됨

  • uncle_list, stack_trace, extra_data 등등

이더리움 블록 구성

위에서 비트코인과 간략하게 비교했으니 이제 이더리움만 자세하게 파봅시다.



https://etherscan.io/block/5529581 해당 주소에서 이더리움의 블록정보를 확인한 정보입니다.


이더리움의 코드(GO)를 보면 아래와 같이 블록과 블록헤더가 struct로 선언되어 있습니다.

블록

// Block represents an entire block in the Ethereum blockchain.
type Block struct {
	header       *Header
	uncles       []*Header
	transactions Transactions
	// caches
	hash atomic.Value
	size atomic.Value
	// Td is used by package core to store the total difficulty
	// of the chain up to and including the block.
	td *big.Int
	// These fields are used by package eth to track
	// inter-peer block relay.
	ReceivedAt   time.Time
	ReceivedFrom interface{}
}

블록헤더

// Header represents a block header in the Ethereum blockchain.
type Header struct {
	ParentHash  common.Hash    `json:"parentHash"       gencodec:"required"`
	UncleHash   common.Hash    `json:"sha3Uncles"       gencodec:"required"`
	Coinbase    common.Address `json:"miner"            gencodec:"required"`
	Root        common.Hash    `json:"stateRoot"        gencodec:"required"`
	TxHash      common.Hash    `json:"transactionsRoot" gencodec:"required"`
	ReceiptHash common.Hash    `json:"receiptsRoot"     gencodec:"required"`
	Bloom       Bloom          `json:"logsBloom"        gencodec:"required"`
	Difficulty  *big.Int       `json:"difficulty"       gencodec:"required"`
	Number      *big.Int       `json:"number"           gencodec:"required"`
	GasLimit    uint64         `json:"gasLimit"         gencodec:"required"`
	GasUsed     uint64         `json:"gasUsed"          gencodec:"required"`
	Time        *big.Int       `json:"timestamp"        gencodec:"required"`
	Extra       []byte         `json:"extraData"        gencodec:"required"`
	MixDigest   common.Hash    `json:"mixHash"          gencodec:"required"`
	Nonce       BlockNonce     `json:"nonce"            gencodec:"required"`
}

블록헤더 설명

  • ParentHash : 부모 블록의 해시값
  • UncleHash : 현재 블록의 엉클 블록들의 해시값
  • Coinbase : 채굴 후 해당 트랜잭션의 수수료를 받을 계정 주소
  • Root: 계정의 상태정보가 모여있는 머클 패트리시아 트리의 루트 노드 해시값
  • TxHash: 블록의 모든 트랜잭션에 대한 머클트리의 루트노드 해시값
  • ReceiptHash: 블록 내 모든 트랜잭션에 대한 receipt들의 머클트리의 루트노드 해시값
  • Bloom: 로그 정보를 사용하는데 사용하는 32바이트 블룸필터
  • Difficulty: 블록 난이도로 이전블록의 난이도와 타임스탬프로 계산
  • Number : 현재 블록번호
  • GasLimit: 블록당 지급가능한 최대 가스 총합
  • GasUsed: 블록내 트랜잭션에 사용된 가스의 총합
  • Time : 블록의 최초 생성시간
  • Extra : 블록의 기타정보
  • MixDigestNonce : 작업증명에서 해시값을 계산하는데 충분한 계산횟수를 보장하기 위해 사용하는 값


Root, TxHash, ReceiptHash는 머클트리의 각 노드를 해시한 최종 루트해시값에 해당하고 나머지 값들은 각각 하나의 상수로 볼수 있습니다.


제네시스 블록

제네시스 블록은 블록의 첫번째에 위치하는 최초 블록을 말하며 블록번호 0번에 해당되고 어떤 트랜잭션도 포함되지 않습니다.

// Genesis specifies the header fields, state of a genesis block. It also defines hard
// fork switch-over blocks through the chain configuration.
type Genesis struct {
	Config     *params.ChainConfig `json:"config"`
	Nonce      uint64              `json:"nonce"`
	Timestamp  uint64              `json:"timestamp"`
	ExtraData  []byte              `json:"extraData"`
	GasLimit   uint64              `json:"gasLimit"   gencodec:"required"`
	Difficulty *big.Int            `json:"difficulty" gencodec:"required"`
	Mixhash    common.Hash         `json:"mixHash"`
	Coinbase   common.Address      `json:"coinbase"`
	Alloc      GenesisAlloc        `json:"alloc"      gencodec:"required"`
	// These fields are used for consensus tests. Please don't use them
	// in actual genesis blocks.
	Number     uint64      `json:"number"`
	GasUsed    uint64      `json:"gasUsed"`
	ParentHash common.Hash `json:"parentHash"`
}

제네시스 블록 설명

  • Alloc : 일정량의 이더를 초기 계정에 할당할때 사용하는 값으로 채굴작업 없이 초기 일정량의 이더를 발생하여 ICO를 통해 판매하는데 사용할수 있음
  • Coinbase : 채굴 후 보상코인을 수령할 주소인데 제네시스 블록에서는 채굴이 일어나지 않기에 어떠한 값을 할당해도 상관없음
  • Nonce : mixhash와 함께 채굴 시에 사용되는 값, 8바이트
  • Mixhash : Nonce와 함께 채굴 시에 사용되는 값, 32바이트
  • Difficulty : 채굴시의 목표값
  • ExtraData : 32바이트 옵션항목
  • GasLimit : 블록의 최대 가스량
  • ParentHash : 이전 부모블록의 해시값, 제네시스블록은 부모가 없기 때문에 0으로 할당
  • TimeStamp : 블록의 생성시간

이더리움 블록체인과 채굴

비트코인: 거래(이체) 데이터 저장방식 (거래정보만 블록에 저장)

이더리움: 계정 데이터 저장방식 (모든 계정정보를 저장)

  • 계정의 balance등의 정보를 직접변경
  • patricia tree를 사용하여 저장 데이터의 용량을 줄임


위와 같이 이더리움 블록체인은 비트코인과 유사하나 다른점이 존재합니다. 비트코인과는 달리 이더리움 블록은 transaction list와 가장 최근의 상태(state) 복사본을 가지고 있다는 것입니다. 이외에도 블록의 넘버와 difficulty 또한 블록 내에 저장됩니다. 기본적인 이더리움 블록 검증 알고리즘은 아래와 같습니다.


  1. 참조하고 있는 이전 블록이 존재하는지와 유효한지 확인
  2. 현재 블록의 타임스탬프가 참조하고 있는 이전 블록의 타임스탬프보다 크고 현 시점을 기준으로 15분 후보다 작은 값인지 확인
  3. 블록 넘버, difficulty, 트랜잭션 루트, uncle 루트, gas limit등이 유효한지 확인
  4. 블록에 포함된 작업 증명이 유효한지 확인
  5. 위 그림의 S[0] 이 이전 블록의 마지막 상태(state)라고 가정
    1. TX를 현재 블록의 n개의 트랜잭션 리스트라고 가정하고 0 부터 n-1에 대해, S[i+1] = APPLY(S[i], TX[i]) 로 설정했을 때, 어플리케이션이 오류를 반환하거나, 이 시점까지 블록에서 소모된 총 gas가 GASLIMIT를 초과하면 오류를 반환
  6. 채굴자에게 지불된 보상 블록을 S[n] 덧붙인 후 이것을 S_FINAL 이라 가정
    1. 상태 S_FINAL의 머클 트리 루트가 블록 헤더가 가지고 있는 최종 상태 루트와 같은지를 검증. 이 값이 같으면 그 블록은 유효한 블록이고 다르면 유효하지 않은 것으로 판단

이러한 접근은 모든 상태를 각 블록에 저장할 필요성 때문에 매우 비효율적인 것처럼 보이지만, 실제로는 효율성의 측면에서는 비트코인과 비교할만 합니다. 그 이유는 상태가 트리 구조로 저장되고, 모든 블록 후에 단지 트리의 작은 부분만이 변경되기 때문입니다. 보통 인접한 두 개의 블록간에는 트리의 대부분의 내용이 같아서 한번 데이터가 저장되면 포인터(서브트리의 해쉬)를 사용하여 참조될 수 있기 때문입니다. 패트리시아 트리(Patricia tree)로 알려진 이러한 종류의 특별한 트리는 머클 트리 개념을 수정하여 노드를 수정할 뿐만 아니라, 효율적으로 삽입되거나 삭제하여 이러한 작업을 수행할 수 있도록 해줍니다. 또한, 모든 상태 정보가 마지막 블록에 포함되어 있기 때문에, 전체 블록체인 히스토리를 모두 저장할 필요가 없어지게 됩니다. 이러한 방법으로 비트코인에 적용된 기술과 비교하면 5~20배의 저장 공간 절약의 효과가 생깁니다.

물리적인 하드웨어 관점에서 볼 때, 컨트랙트 코드는 “어디에서" 실행되는가 하는 의문이 쉽게 들 수 있습니다. 컨트랙트 코드를 실행하는 프로세스는 상태 전환 함수 정의의 한 부분이고, 이것은 블록 검증 알고리즘의 부분이므로, 트랜잭션이 블록 B에 포함되면 그 트랜잭션에 의해 발생할 코드의 실행은 블록 B를 다운로드 하고 검증하는 모든 노드들에 의해 실행됩니다.

엉클블록

동시에 블록이 생성되어 전파되는경우 블록의 유효성 검증은 통과되었지만, 블록의 난이도가 상대적으로 낮아 블록으로 채택되지못한 블록을 엉클블록이라고 합니다. 엉클블록이 많아지만 다음과 같은 문제가 발생합니다.

  1.  엉클블록에 포함된 트랜잭션은 처리가 되지않기 때문에 트랜잭션처리의 지연문제가 발생
  2. 엉클블록은 체인에 연결되지않기 때문에 엉클블록을 발견하는데 사용된 컴퓨팅파워가 낭비되는 문제가 발생
  3. 엉클블록이 생성된 후 다음 블록이 생성되면 평균 블록 생성시간이 늘어나 블록생성 난이도가 낮아지기 때문에 네트워크 보안수준을 떨어뜨리게 됨

이더리움은 이러한 문제를 고스트 알고리즘을 사용하여 해결하였습니다. 고스트 알고리즘은 다음 번에 설명하겠습니다.


BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)

AVL Tree 예시

AVL Tree

Not AVL Tree

용어

  • 노드의 height: h
  • balance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)
  • empty height: -1

특징

  • AVL 트리는 BST이면서 동시에 균형을 유지하고 있음
  • 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1)
    • 즉, 모든 노드들은 balance factor 를 알고 있음
  • 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장

문제는 이러한 균형을 맞추려 하다 보니 유지하는 방법이 복잡함. 예를 들어, 노드 삽입이나 삭제로 인해 왼쪽과 오른쪽 서브트리의 height의 계산결과가 2, -2가 나온 경우, 트리를 rotation 시켜줘야 함


rotation에는 2가지 관점이 있는데 AVL 트리를 height balance로 유지하는 것과 binary search tree로 유지하는 관점이 있음. 관점은 나뉘어 있지만 가장 중요한 것은 rotation 시키면서 트리의 height를 낮춰야 복잡도가 줄어듦

rotation의 방법은 4가지로 1번만 rotation 시키는 LL, RR와 2번 rotation 시키는 LR, RL이 존재.


Single Rotation

LL (Right)


왼쪽은 차이가 2이고 오른쪽은 0이므로 왼쪽이 무너진 경우. 이 경우는 오른쪽으로 트리를 회전시켜주면 해결

RR (Left)


왼쪽은 차이가 0이고 오른쪽은 2이므로 오른쪽이 무너진 경우. 이 경우는 왼쪽쪽으로 트리를 회전시켜주면 해결

Double Rotation

위에서 본 LL, RR과는 달리 방향이 일정하지가 않기 때문에 첫 회전에서는 LL 또는 RR로 방향을 맞춘 다음 다시 회전시켜 높이의 균형을 유지시켜줌

RL (Right & Left)


가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 RR의 형태를 이루기 때문에 자리를 바꾼 후, RR 로 회전을 한번 더 시킴.

LR(Left & Right)

가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 LL의 형태를 이루기 때문에 자리를 바꾼 후, LL 로 회전을 한번 더 시킴.

장단점

  • 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춤
  • 프로그래밍하기가 어렵고 디버깅 또한 어려움.
  • 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는데에 시간이 듦
  • 대규모 tree를 이룬 후 검색하는 것은 DB에서 주로 발생하는데 DB는 이미 B-Tree 자료구조를 사용 중임


'공부 > 자료구조' 카테고리의 다른 글

AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30

Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.

정의

  1. 각각의 모든 node 들의 key는 중복된 값이 아님 (unique)
  2. 기존의 binary tree는 순서가 없지만 BST는 순서가 존재
  3. parent node의 왼쪽은 부모보다 작은 값이고 오른쪽은 부모보다 큰 값임
  4. 왼쪽, 오른쪽의 서브 트리또한 BST임

Search

  1. 찾고자 하는 Key와 root node값이 같으면 성공
  2. Key가 root node 값보다 작다면 (key < root node) 왼쪽의 sub tree로 이동
  3. Key가 root node 값보다 작다면 (key > root node) 오른쪽의 sub tree로 이동
  4. 1~3번 반복
  5. 만약 조건에 맞는 데이터가 없으면 실패 (tree에 값이 존재하지 않는 경우)


위 그림에서 120 값을 찾는 예시입니다. 

  1.  root node(=100)와 찾고자 하는 값 (=120) 비교
  2. root node보다 찾고자 하는 값이 더 크므로 (100 < 120) 오른쪽 subtree로 이동
  3. 오른쪽 subtree의 노드값(=150)과 찾고자 하는 값(=120)과 비교
  4. 찾고자 하는 값이 더 작으므로 (150 > 120) 왼쪽 subtree로 이동
  5. 120값이므로 검색 성공


Insert

값을 삽입하고자 하거나 찾고자 하는 값이 없을 경우 루트노드에서 시작, 값을 비교해가면서 tree의 가장 마지막까지 간 다음 값을 입력

예시

위 그림에서 80을 넣고자 하면 아래와 같은 위치에 삽입


Delete

  1. 첫 단계는 지우고자 하는 값이 해당 tree에 있는지 search
  2. 지우고자 하는 값이 leaft node(가장 마지막)에 위치해있으면, 그냥 지우면 됨
  3. internal node라면 다음과 같이 분기가 됨
    1. 지워야 하는 node가 child node를 1개 가지고 있는 경우, internal node를 지운 후 해당자리에 child node를 옮김
    2. 지워야 하는 node가 child node를 2개 가지고 있는 경우, 왼쪽의 subtree에서 가증 큰 노드 또는 오른쪽 subtree에서 가장 작은 노드를 옮김

예시

50 (leaf node) 삭제


75 (internal node 이며 1개의 child node 존재) 삭제


150 (internal node 이며 2 child node 존재) 삭제

1. 왼쪽의 subtree에서 가장 큰 노드를 이동


2. 오른쪽 subtree에서 가장 작은 노드를 이동



internal node이며 child node를 2개 가지고 있는 경우 삭제하는 방법은 2가지가 있지만 여기서 조건적으로 효율적인 방법이 존재.

1, 2번의 방법 중 트리의 height를 줄일 수 있는 방법을 채택하는 것이 향후 트리 검색의 속도를 향상시킬 수 있음

복잡도

BST는 검색, 삽입, 삭제 모두 O(h)임. h는 BST의 높이(height)

BST에서는 inorder(LVR) 검색 방식을 사용

BST는 평균(최상) 시간복잡도가 O(log₂n)이지만 최악의 경우 O(n)임. (skewed tree이면 node의 수만큼 시간이 소요됨)

  • tree가 complete binary tree거나 full binary tree이면 O(log₂n), skewed tree이면 O(n)

위 O(N)의 경우때문에 노드가 얼마 되지 않아도 검색속도가 나오지 않을 가능성이 존재함. 이 때문에 AVL Tree가 고안됨


'공부 > 자료구조' 카테고리의 다른 글

AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30

+ Recent posts