밑바닥부터 시작하는 비트코인

func practice2() {
	var bitFieldSize int64 = 10                            // 그룹의 개수
	bitField := bytes.Repeat([]byte{0}, int(bitFieldSize)) // 비트 필드로 표현된 블룸 필터

	// 여러 개의 원소를 블룸 필터에 추가
	for _, item := range [][]byte{[]byte("hello world"), []byte("goodbye")} {
		h := utils.Hash256(item) // 해시값
		n := utils.BytesToBigInt(h)
		bit := big.NewInt(0).Mod(n, big.NewInt(10)).Int64() // 해시값을 그룹의 개수로 나눈 나머지를 구함, 항상 0~9 사이의 값이 나옴

		bitField[bit] = 1 // 원소가 속한 그룹의 비트를 1로 설정
	}

	fmt.Println(bitField) // [0 0 1 0 0 0 0 0 0 1]
}

블룸 필터를 적용할 전체 집합의 원소 개수가 아주 큰 경우에는 어떻게 해야 할까요? 만약 원소 개수가 1백만 개라고 했을 때 각 그룹의 원소의 개수가 5개인 블룸 필터를 만들고자 한다면, 비트 필드의 길이가 20만 비트여야 합니다. 이를 그대로 전송하기에는 너무 많은 데이터양입니다.

전체 집합의 원소 개수가 아주 큰 경우는 해시함수를 여러 개 사용하여 블룸 필터의 비트 필드 길이를 줄일 수 있습니다. 예를 들어, 길이가 32인 비트 필드에서 5개의 해시함수를 사용하면 ₃₂C₅∽200,000개의 그룹을 만들 수 있습니다.

하나의 원소 a에 해시함수 f1, f2, f3, f4, f5를 적용하여 f1(a), f2(a), f3(a), f4(a), f5(a)를 구한 뒤, 각각의 결과를 32로 나눈 값에 해당하는 비트 필드의 값을 1로 변경한다는 뜻. 32비트 필드에서 5개의 비트를 순서에 상관없이 선택하면 201,376개의 그룹이 만들어지고 각 그룹은 평균 1백만/20만 = 5개의 원소를 가지게 됩니다.

블룸 필터의 특징은 다른 그룹에 속한 원소가 오탐지(false-positive)될 수 있다는 것입니다. 비트코인에서는 이를 오히려 역이용해 관심 트랜잭션을 오탐지되는 그룹에 숨기는 경우도 있습니다. 오탐지율이 높아지면 그룹 안의 트랜잭션 수가 많아지면서 관심 트랜잭션 비율은 낮아지고, 오탐지율이 낮아지면 그룹 안의 트랜잭션 수가 적어지면서 관심 트랜잭션의 비율이 높아집니다. 한편, 존재하는 것을 부정(false-negative)할 수는 없으므로 존재하지 않는 원소는 확실하게 존재하지 않습니다. 오탐지율은 비트 필드 크기와 해시함수의 개수로 조절할 수 있습니다.

1.3 BIP0037 블룸 필터

BIP0037에 따라 비트코인에서 블룸 필터를 정의하는 정보는 다음과 같습니다.

비트 필드의 길이 (그룹의 개수)
해시함수의 개수
오탐지율에 영향을 주는 tweak 파라미터
블룸 필터의 비트 필드 값

BIP0037에서는 여러 개의 해시함수를 섞어서 사용하지 않고 murmur3이라는 하나의 해시함수만을 사용합니다. 암호학적으로는 sha256에 뒤쳐지나, 블룸 필터는 암호학적 안정성이 크게 요구되지 않기 때문에 출력 계산이 빠른 murmur3이 사용되고 있습니다.

BIP0037 블룸 필터를 나타내는 BloomFilter 구조체는 다음과 같습니다.

const BIP37Constant = 0xfba4c795

type BloomFilter struct {
	Size     uint32 // 비트 필드의 길이 (바이트 단위)
	Funcs    uint32 // 해시함수의 개수
	Tweak    uint32 // 오탐지율을 조절하는 값
	BitField []byte // 비트 필드
}

func New(size, funcs, tweak uint32) *BloomFilter {
	return &BloomFilter{
		Size:     size,
		Funcs:    funcs,
		Tweak:    tweak,
		BitField: make([]byte, size*8), // 비트 필드의 길이는 size * 8
	}
}

func (b *BloomFilter) Add(data []byte) {
	for i := uint32(0); i < b.Funcs; i++ {
		seed := i*BIP37Constant + b.Tweak // 시드값 계산
		h := utils.Murmur3(data, seed)    // Murmur3 해시값 계산
		bit := h % (b.Size * 8)           // 비트 필드의 인덱스 계산
		b.BitField[bit] = 1               // 비트 필드의 해당 비트를 1로 설정
	}
}

다음의 예제는 2바이트 크기 비트 필드 길이와 2개의 해시함수 그리고 tweak 값이 42인 블룸 필터입니다. 이 블룸 필터에 "hello world"와 "goodbye"를 추가한 뒤에 비트 필드를 확인해 보면 16비트 중 4비트가 1로 설정된 것을 확인할 수 있습니다. 따라서 임의의 트랜잭션이 필터를 통과할 확률은 1/4 * 1/4 = 1/16(첫 번째 해시값이 필터를 통과할 확률 4/16 * 두 번째 해시값이 필터를 통과할 확률 4/16)입니다. 트랜잭션의 전체 집합이 160개인 경우, 라이트 노드는 평균 10개의 트랜잭션을 수신하며 그중 2개(hello world, goodbye)는 라이트 노드의 관심 트랜잭션입니다.

func main() {
	bf := bloomfilter.New(2, 2, 42)
	bf.Add([]byte("hello world"))
	bf.Add([]byte("goodbye"))

	fmt.Println(bf.BitField) // [0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0]
}

1.4 블룸 필터 설정

라이트 노드가 블룸 필터를 생성하고 풀 노드에게 알려주면 풀 노드는 포함증명을 보낼 때 이를 참고합니다. 이에 앞서 라이트 노드는 먼저 version 메시지의 릴레이 필드 값을 0으로 설정해야 합니다. 이는 풀 노드가 블룸 필터에 걸러지지 않는 트랜잭션을 라이트 노드에게 보내지 않도록 하기 위함입니다. 그러고나면 라이트 노드는 'filterload' 명령어와 페이로드에 블룸 필터를 담아 풀 노드에게 전달합니다.

filterload 메시지의 페이로드는 다음과 같은 형식입니다. 마지막 필드인 Matched item flag는 0, 1, 2 중 하나의 값으로 0인 경우는 풀 노드가 동작 중 비트 필드를 없데이트할 수 없고, 1이나 2인 경우는 조건부로 비트 필드를 업데이트할 수 있게 하는 값입니다.

비트 필드 크기	varint, 바이트 단위
비트 필드	비트 필드를 바이트로 변환
해시 함수의 수	4 bytes, little-endian
Tweak	4 bytes, little-endian
Matched item flag	1 byte

BloomFilter 구조체로부터 filterload 메시지를 구성하는 메서드는 다음과 같습니다.

func (b *BloomFilter) Filterload(flag ...bool) *network.GenericMessage {
	payload := utils.EncodeVarint(int(b.Size))                             // 비트 필드의 크기 (바이트 단위)
	payload = append(payload, b.FilterBytes()...)                          // 비트 필드를 바이트 단위로 변환하여 추가
	payload = append(payload, utils.IntToLittleEndian(int(b.Funcs), 4)...) // 해시 함수의 개수
	payload = append(payload, utils.IntToLittleEndian(int(b.Tweak), 4)...) // tweak 값

	// flag가 있으면 추가
	if len(flag) > 0 {
		if flag[0] {
			payload = append(payload, 0x01)
		} else {
			payload = append(payload, 0x00)
		}
	} else {
		payload = append(payload, 0x01)
	}

	return network.NewGenericMessage(network.FilterloadCommand, payload)
}

func (b BloomFilter) FilterBytes() []byte {
	return utils.BitFieldToBytes(b.BitField)
}

🥷 2. 테스트 네트워크에서 관심 트랜잭션의 포함증명 가져오기

2.1 머클블록의 입수

라이트 노드가 필요로 하는 또 하나의 명령어는 풀 노드에게 관심 트랜잭션이 포함된 머클블록을 요청하는 'getdata'입니다. getdata 메시지 페이로드의 형식은 다음과 같습니다.

데이터 아이템의 개수	varint
데이터 아이템 유형	4 bytes, little-endian (tx, block, filteredblock, compact block)
데이터 아이템 식별자	32 bytes, little-endian

머클블록을 입수하기 위해서 사용하는 유형은 filteredblock이며, 식별자는 getheaders 요청으로 받은 블록 헤더를 지정하여 풀 노드에게 블룸 필터를 통과한 트랙잭션으로 머클블록을 구성하도록 요청합니다.

getdata 메시지를 위한 타입과 구조체를 다음과 같이 정의하였습니다.

type DataItemType uint32

const (
	TxDataItem DataItemType = iota + 1
	BlockDataItem
	FiltedBlockDataItem
	CompactBlockDataItem
)

type DataItem struct {
	Type DataItemType
	Hash []byte
}

type GetDataMessage struct {
	Cmd  Command
	Data []DataItem
}

func NewGetDataMessage() *GetDataMessage {
	return &GetDataMessage{
		Cmd: GetDataCommand,
	}
}

func (gdm *GetDataMessage) AddData(typ DataItemType, hash []byte) {
	gdm.Data = append(gdm.Data, DataItem{
		Type: typ,
		Hash: hash,
	})
}

func (gdm GetDataMessage) Command() Command {
	return gdm.Cmd
}

func (gdm GetDataMessage) Serialize() ([]byte, error) {
	result := utils.EncodeVarint(len(gdm.Data))
	for _, d := range gdm.Data {
		result = append(result, utils.IntToLittleEndian(int(d.Type), 4)...)
		result = append(result, utils.ReverseBytes(d.Hash)...)
	}

	return result, nil
}

2.2 관심 트랜잭션 입수

이제 블룸 필터를 풀 노드로 전송하고 관심 트랜잭션을 받아오는 일만 남았는데... 10장에서 해결하지 못한 네트워크 문제때문에 다시 발목이 잡혔습니다. 네트워크와 관련된 문제는 13장 세그윗을 마무리하고 마지막에 한 번에 해결하도록 하겠습니다.

1월 17일 추가

관심 트랜잭션 입수와 관련된 문제 해결 과정을 아래 게시글에 기술하였습니다.

밑바닥부터 시작하는 비트코인 - 외전1 네트워크 요청 및 응답 개선

본 게시글에서는 저서 '밑바닥부터 시작하는 비트코인'의 Python으로 작성된 예제 코드를 Go로 컨버팅 하여 작성하였습니다. 📺시리즈 2023.08.25 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인

piatoss3612.tistory.com

❗ 3. 수정 사항

GetHeadersMessage를 직렬화하는 과정에서 시작 블록과 마침 블록 해시값을 리틀 엔디언으로 변환해주지 않았던 부분을 수정했습니다.

📖 참고자료

밑바닥부터 시작하는 비트코인

비트코인은 블록체인 기술의 집약체입니다. 이더리움, 이오스 같은 2, 3세대 블록체인은 비트코인을 바탕으로 확장, 발전한 개념입니다. 디앱 개발에서 머무르지 않고 블록체인 개발자로 성장하

www.hanbit.co.kr

GitHub - jimmysong/programmingbitcoin: Repository for the book

Repository for the book. Contribute to jimmysong/programmingbitcoin development by creating an account on GitHub.

github.com

GitHub - vcaesar/murmur: Go Murmur3 hash implementation

Go Murmur3 hash implementation. Contribute to vcaesar/murmur development by creating an account on GitHub.

github.com

'블록체인 > Bitcoin' 카테고리의 다른 글

밑바닥부터 시작하는 비트코인 - 13장 세그윗 2 (1)	2024.01.14
밑바닥부터 시작하는 비트코인 - 13장 세그윗 1 (0)	2024.01.13
밑바닥부터 시작하는 비트코인 - 11장 단순 지급 검증 (1)	2024.01.09
밑바닥부터 시작하는 비트코인 - 10장 네트워킹 (1)	2024.01.08
밑바닥부터 시작하는 비트코인 - 9장 블록 (0)	2023.09.21

최근에 올라온 글

최근에 달린 댓글

« 2025/01 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Total

Today

Yesterday

글 보관함

TAG more

개발 코어 강화 일지

티스토리 뷰