#7 UTXO management
UTXO들을 효율적으로 관리하기
UTXO들을 데이터베이스에 따로 저장해서 데이터베이스 전체를 탐색하지 않고 UTXO를 접근할 수 있도록 할 것입니다.
구현할 것
이전 파트까지 구현을 했다면, 뭔가 많이 비효율적이라는 생각이 들었을 것 입니다. Balance를 확인하거나 send 트랜잭션을 발생시킬 때마다 전체 블록을 찾아가면서 UTXO를 찾아야했습니다. 지금이야 블록체인이 아주 작기 때문에 괜찮지만 체인의 길이가 길어진다면 문제가 될 것입니다.
예를 들어, FindSpendableOutputs 함수나 FindUTXO함수가 이에 해당합니다.
이번 파트에서는 UTXO를 따로 저장하여 관리하는 방법으로 이를 최적화할 것입니다.
"utxo-"라는 prefix를 블록 해시에 붙힌 값을 key로 하여 UTXO들만 따로 저장합니다.
blockchain/tx.go
TxOutput struct의 집합인 TxOutputs 구조를 만들고, 이에 대한 Serialize, Deserialize 함수를 만든다.
// tx.go
// TxOutput 모음
type TxOutputs struct {
Outputs []TxOutput
}
// TxOutputs를 []byte로
func (outs TxOutputs) Serialize() []byte {
var buffer bytes.Buffer
encode := gob.NewEncoder(&buffer)
err := encode.Encode(outs)
Handle(err)
return buffer.Bytes()
}
// []byte를 TxOutputs로
func DeserializeOutputs(data []byte) TxOutputs {
var outputs TxOutputs
decode := gob.NewDecoder(bytes.NewReader(data))
err := decode.Decode(&outputs)
Handle(err)
return outputs
}blockchain/utxo.go
UTXO들을 관리하기 위한 코드들을 따로 정리하기 위해 utxo.go 파일을 만듭니다. BlockChain의 Database를 공유하고 "utxo-" prefix를 key앞에 붙혀서 UTXO들만 따로 관리합니다.
package blockchain
import (
"bytes"
"encoding/hex"
"log"
"github.com/dgraph-io/badger"
)
// utxo- 로 prefix된 key를 위한 상수 입니다.
var (
utxoPrefix = []byte("utxo-")
prefixLength = len(utxoPrefix)
)
// UTXO를 관리하는 구조입니다.
// BlockChain의 Database를 공유하므로 BlockChain에 대한 포인터를 가집니다.
type UTXOSet struct {
Blockchain *BlockChain
}
// blockchain.go 에서 옮겨온 함수.
// UTXOSet 중에 pubKeyHash 소유의 UTXO를 반환.
func (u UTXOSet) FindUnspentTransactions(pubKeyHash []byte) []TxOutput {
var UTXOs []TxOutput
db := u.Blockchain.Database
err := db.View(func(txn *badger.Txn) error {
opts := badger.DefaultIteratorOptions
it := txn.NewIterator(opts)
defer it.Close()
// "utxo-"로 prefix된 key를 찾아 value를 가져옵니다.
for it.Seek(utxoPrefix); it.ValidForPrefix(utxoPrefix); it.Next() {
item := it.Item()
v, err := item.ValueCopy(nil)
Handle(err)
outs := DeserializeOutputs(v)
// 결과값 중 pubKeyHash 소유의 UTXO만 저장합니다.
for _, out := range outs.Outputs {
if out.IsLockedWithKey(pubKeyHash) {
UTXOs = append(UTXOs, out)
}
}
}
return nil
})
Handle(err)
return UTXOs
}
// blockchain.go 에서 옮겨온 함수.
// amount를 집불하기위해 사용될 UTXO를 검색합니다.
// 사용할 수 있는 금액과 사용할 수 있는 TXO를 찾을 수 있는 매핑을 반환합니다.
func (u UTXOSet) FindSpendableOutputs(pubKeyHash []byte, amount int) (int, map[string][]int) {
// UTXO의 txID => outIdx(해당 트랜잭션에서 몇번째 TXO가 UTXO인지) 매핑
unspentOuts := make(map[string][]int)
accumulated := 0
db := u.Blockchain.Database
err := db.View(func(txn *badger.Txn) error {
opts := badger.DefaultIteratorOptions
it := txn.NewIterator(opts)
defer it.Close()
// "utxo-"로 prefix된 key 모두 탐색합니다.
for it.Seek(utxoPrefix); it.ValidForPrefix(utxoPrefix); it.Next() {
item := it.Item()
k := item.Key()
v, err := item.ValueCopy(nil)
Handle(err)
// "utxo-" prefix를 제거합니다.
k = bytes.TrimPrefix(k, utxoPrefix)
txID := hex.EncodeToString(k)
outs := DeserializeOutputs(v)
// 트랜잭션의 모든 Output(TXO)에 대해 for loop
for outIdx, out := range outs.Outputs {
// {pubKeyHash}소유이고 지금까지의 UTXO의 합이 amount보다 작다면 해당 UTXO를 추가
if out.IsLockedWithKey(pubKeyHash) && accumulated < amount {
accumulated += out.Value
unspentOuts[txID] = append(unspentOuts[txID], outIdx)
}
}
}
return nil
})
Handle(err)
return accumulated, unspentOuts
}
// "utxo-" prefix된 key를 지우고 새로 매핑한다.
func (u UTXOSet) Reindex() {
db := u.Blockchain.Database
// "utxo-" prefix된 데이터를 모두s 지운다.
u.DeleteByPrefix(utxoPrefix)
// UTXO를 모두 찾는다.
UTXO := u.Blockchain.FindUTXO()
err := db.Update(func(txn *badger.Txn) error {
for txId, outs := range UTXO {
key, err := hex.DecodeString(txId)
if err != nil {
return err
}
// 찾은 UTXO의 txId에 prefix를 더해 저장한다.
key = append(utxoPrefix, key...)
err = txn.Set(key, outs.Serialize())
Handle(err)
}
return nil
})
Handle(err)
}
// AddBlock시에 발생합니다.
// block의 transaction을 DB에 업데이트
func (u *UTXOSet) Update(block *Block) {
db := u.Blockchain.Database
err := db.Update(func(txn *badger.Txn) error {
for _, tx := range block.Transactions {
if !tx.IsCoinbase() {
// 트랜잭션의 모든 Input에 대하여
for _, in := range tx.Inputs {
updatedOuts := TxOutputs{}
inID := append(utxoPrefix, in.ID...)
// in.ID에 "utxo-" prefix를 붙혀 찾는다.
item, err := txn.Get(inID)
Handle(err)
v, err := item.ValueCopy(nil)
Handle(err)
// outs은 in.ID 트랜잭션의 모든 UTXO
outs := DeserializeOutputs(v)
// UTXO 중에
for outIdx, out := range outs.Outputs {
// 이번 트랜잭션에서 사용할 UTXO 제외하고 (XXX: 아래 if문이 맞나?)
if outIdx != in.Out {
// 새로운 UTXO 배열을 만든다.
updatedOuts.Outputs = append(updatedOuts.Outputs, out)
}
}
// UTXO가 남아있지 않다면 삭제.
if len(updatedOuts.Outputs) == 0 {
if err := txn.Delete(inID); err != nil {
log.Panic(err)
}
} else {
// UTXO가 남아있다면 다시 저장.
if err := txn.Set(inID, updatedOuts.Serialize()); err != nil {
log.Panic(err)
}
}
}
}
// 이번 트랜잭션으로 생기는 UTXO들
newOutputs := TxOutputs{}
for _, out := range tx.Outputs {
newOutputs.Outputs = append(newOutputs.Outputs, out)
}
// "utxo-" prefix하여 UTXO들을 저장한다.
txID := append(utxoPrefix, tx.ID...)
if err := txn.Set(txID, newOutputs.Serialize()); err != nil {
log.Panic(err)
}
}
return nil
})
Handle(err)
}
// "utxo-" prefix key를 가진 트랜잭션의 수를 반환한다.
func (u UTXOSet) CountTransactions() int {
db := u.Blockchain.Database
counter := 0
err := db.View(func(txn *badger.Txn) error {
opts := badger.DefaultIteratorOptions
it := txn.NewIterator(opts)
defer it.Close()
for it.Seek(utxoPrefix); it.ValidForPrefix(utxoPrefix); it.Next() {
counter++
}
return nil
})
Handle(err)
return counter
}
// {prefix}가 붙은 Key-Value를 제거한다.
func (u *UTXOSet) DeleteByPrefix(prefix []byte) {
// {KeysForDelete}에 속한 key-Value를 제거한다.
deleteKeys := func(KeysForDelete [][]byte) error {
if err := u.Blockchain.Database.Update(func(txn *badger.Txn) error {
for _, key := range KeysForDelete {
if err := txn.Delete(key); err != nil {
return err
}
}
return nil
}); err != nil {
return err
}
return nil
}
collectSize := 100000 // badger의 optimal batching size
u.Blockchain.Database.View(func(txn *badger.Txn) error {
opts := badger.DefaultIteratorOptions
opts.PrefetchValues = false // value를 읽을 필요없으므로
it := txn.NewIterator(opts)
defer it.Close()
keysForDelete := make([][]byte, 0, collectSize)
keysCollected := 0
// prefix된 모든 Key-value에 대해
for it.Seek(prefix); it.ValidForPrefix(prefix); it.Next() {
// key를 가져와 지울 키 리스트에 추가한다.
key := it.Item().KeyCopy(nil)
keysForDelete = append(keysForDelete, key)
keysCollected++
// batching size만큼 key를 모았으면
if keysCollected == collectSize {
// 해당 key값들을 지운다.
if err := deleteKeys(keysForDelete); err != nil {
log.Panic(err)
}
// 변수 초기화
keysForDelete = make([][]byte, 0, collectSize)
keysCollected = 0
}
}
// 처리되지않은 키들을 마저 처리한다.
if keysCollected > 0 {
if err := deleteKeys(keysForDelete); err != nil {
log.Panic(err)
}
}
return nil
})
}
blockchain/blockchain.go
FindUTXO 함수와 AddBlock 함수를 수정합니다.
// 새로운 블록을 만들어서 블록체인에 연결하는 함수
// 새로 추가된 블록을 리턴함.
func (chain *BlockChain) AddBlock(transactions []*Transaction) *Block {
var lastHash []byte
// Read만 하므로 View를 사용
err := chain.Database.View(func(txn *badger.Txn) error {
item, err := txn.Get([]byte("lh"))
Handle(err)
lastHash, err = item.ValueCopy(nil)
return err
})
Handle(err)
// lashHash를 토대로 다음 문제를 풀어 새로운 블록을 생성.
newBlock := CreateBlock(transactions, lastHash)
// 블록의 해시를 키값으로 새로운 블록을 저장하고
// lh의 값 또한 새로운 블록의 해시로 업데이트 해줍니다.
err = chain.Database.Update(func(txn *badger.Txn) error {
err := txn.Set(newBlock.Hash, newBlock.Serialize())
Handle(err)
err = txn.Set([]byte("lh"), newBlock.Hash)
chain.LastHash = newBlock.Hash
return err
})
Handle(err)
return newBlock
}
// block의 모든 UTXO (txID => TxOutputs mapping)을 찾아 반환합니다.
func (chain *BlockChain) FindUTXO() map[string]TxOutputs {
UTXOs := make(map[string]TxOutputs)
spentTXOs := make(map[string][]int)
iter := chain.Iterator()
for {
block := iter.Next()
// 블록의 모든 트랜잭션에 대하여
for _, tx := range block.Transactions {
txID := hex.EncodeToString(tx.ID)
Outputs:
for outIdx, out := range tx.Outputs {
if spentTXOs[txID] != nil {
for _, spentOut := range spentTXOs[txID] {
if spentOut == outIdx {
continue Outputs
}
}
}
// outs에 UTXO추가
outs := UTXOs[txID]
outs.Outputs = append(outs.Outputs, out)
UTXOs[txID] = outs
}
if !tx.IsCoinbase() {
// Inputs에 참조된 모든 UTXO는 이번 트랜잭션에서 사용된 UTXO이다.
for _, in := range tx.Inputs {
inTxID := hex.EncodeToString(in.ID)
spentTXOs[inTxID] = append(spentTXOs[inTxID], in.Out)
}
}
}
if len(block.PrevHash) == 0 {
break
}
}
return UTXOs
}blockchain/transaction.go
NewTransaction함수의 인자를 UTXOSet으로 바꾸고 이에 따라 코드도 약간 수정합니다.
// Transaction을 만드는 함수 입니다.
func NewTransaction(from, to string, amount int, UTXO *UTXOSet) *Transaction {
var inputs []TxInput
var outputs []TxOutput
// Wallets에서 {from}의 address갖는 wallet을 가져옵니다.
wallets, err := wallet.CreateWallets()
Handle(err)
w := wallets.GetWallet(from)
// Public key로 부터 publicKeyHash를 생성합니다.
pubKeyHash := wallet.PublicKeyHash(w.PublicKey)
// {from}이 {amount}를 지불하기 위해 필요한 {from}소유의 UTXO를 가지고 옵니다.
// {from}의 공개키 해시 {pubKeyHash}를 이용합니다.
acc, validOutputs := UTXO.FindSpendableOutputs(pubKeyHash, amount)
// UTXO를 다 모았는데 amount보다 작다면 잔액 부족입니다.
if acc < amount {
log.Panic("Error: not enough funds")
}
// 모아온 UTXOs에 대해 for loop
for txid, outs := range validOutputs {
txID, err := hex.DecodeString(txid)
Handle(err)
for _, out := range outs {
// {txID}를 가지는 트랜잭션의 {out}번째 {from}소유의 아웃풋이 인풋이 됩니다.
// 4번째 인자로 {from}의 PublicKey가 추가됩니다.
input := TxInput{txID, out, nil, w.PublicKey}
inputs = append(inputs, input)
}
}
// 이제 트랜잭션의 인풋으로 사용될 UTXO를 모두 모았습니다.
// 그리고 그 가치의 합은 acc가 될 것입니다.
// 트랜잭션의 아웃풋은 전송될 TXO, 잔금(반환될) TXO
// 항상 두개로 이루어집니다.
// 전송될 TXO을 만듭니다.
outputs = append(outputs, *NewTXOutput(amount, to))
// 반환될 TXO
if acc > amount {
outputs = append(outputs, TxOutput{acc - amount, pubKeyHash})
}
// 인풋과 아웃풋을 바탕으로 Transaction이 생성됩니다.
tx := Transaction{nil, inputs, outputs}
tx.ID = tx.Hash()
UTXO.Blockchain.SignTransaction(&tx, w.PrivateKey)
return &tx
}cli/cli.go
Cli 프로그램에 새로운 명령어 1개를 추가합니다. 커맨드 추가는 printchain과 같으므로 생략하겠습니다.
// UTXOSet을 rebuild합니다.
func (cli *CommandLine) reindexUTXO() {
chain := blockchain.ContinueBlockChain("")
defer chain.Database.Close()
UTXOset := blockchain.UTXOSet{chain}
UTXOset.Reindex()
count := UTXOset.CountTransactions()
fmt.Printf("Done! There are %d transactions in the UTXO set.\n", count)
}UTXOSet을 이용하도록 하기 3개 함수를 수정합니다.
func (cli *CommandLine) createBlockChain(address string) {
if !wallet.ValidateAddress(address) {
log.Panic("Address is not Valid")
}
chain := blockchain.InitBlockChain(address)
defer chain.Database.Close()
UTXOset := blockchain.UTXOSet{chain}
UTXOset.Reindex()
fmt.Println("Finished!")
}
func (cli *CommandLine) getBalance(address string) {
if !wallet.ValidateAddress(address) {
log.Panic("Address is not Valid")
}
chain := blockchain.ContinueBlockChain("") // blockchain을 DB로 부터 받아온다.
UTXOset := blockchain.UTXOSet{chain}
defer chain.Database.Close()
balance := 0
// Human readable Address를 PubKeyHash로 다시 변환.
pubKeyHash := wallet.Base58Decode([]byte(address))
pubKeyHash = pubKeyHash[1 : len(pubKeyHash)-4]
UTXOs := UTXOset.FindUnspentTransactions(pubKeyHash)
for _, out := range UTXOs {
balance += out.Value
}
fmt.Printf("Balance of %s: %d\n", address, balance)
}
// {from}에서 {to}로 {amount}만큼 보냅니다.
func (cli *CommandLine) send(from, to string, amount int) {
if !wallet.ValidateAddress(from) {
log.Panic("Address is not Valid")
}
if !wallet.ValidateAddress(to) {
log.Panic("Address is not Valid")
}
chain := blockchain.ContinueBlockChain("") // blockchain을 DB로 부터 받아온다.
UTXOset := blockchain.UTXOSet{chain}
defer chain.Database.Close()
tx := blockchain.NewTransaction(from, to, amount, &UTXOset)
block := chain.AddBlock([]*blockchain.Transaction{tx})
UTXOset.Update(block)
fmt.Println("Success!")
}Testing
Optimizing이기 때문에 새로 테스트 해 볼 것은 없습니다. 이전 테스트처럼 wallet을 생성하고 send를 호출한 후 getbalance나 printchain으로 정상 동작하는 지 살펴보세요.
혹시 getbalance가 제대로 동작하지 않는다면 reindexutxo 커맨드를 실행해보세요.
코드는 https://github.com/siisee11/golang-blockchain 의 step7 브랜치에 있습니다 .
Last updated: May 2, 2021
Last updated
