Introduction

在本系列的第一部分中，我说区块链是一个分布式数据库。那时，我们决定跳过“分布式”部分并专注于“数据库”部分。到目前为止，我们已经实现了几乎所有构成区块链数据库的东西。在这篇文章中，我们将介绍在前面部分中跳过的一些机制，在下一部分中，我们将开始研究区块链的分布式特性。

Reward

我们在之前的文章中跳过的一件小事就是采矿奖励。我们已经拥有了实现它的一切。

奖励只是一个coinbase transaction。当挖掘节点开始挖掘新块时，它从队列中获取事务并将coinbase transaction预先添加到它们。 coinbase transaction的唯一输出包含矿工的公钥哈希。

实现奖励就像更新奖励一样简单send 命令:

func (cli *CLI) send(from, to string, amount int) {
    ...
    bc := NewBlockchain()
    UTXOSet := UTXOSet{bc}
    defer bc.db.Close()

    tx := NewUTXOTransaction(from, to, amount, &UTXOSet)
    cbTx := NewCoinbaseTX(from, "")
    txs := []*Transaction{cbTx, tx}

    newBlock := bc.MineBlock(txs)
    fmt.Println("Success!")
}
复制代码

在我们的实现中，创建事务的人挖掘新块，从而获得奖励。

The UTXO Set

在第三章中我们研究了比特币在数据库中存储块的方式。块存储在blocks数据库，事务输出存储在chainstate数据库。让我提醒你结构chainstate 是什么:

1. 'c' + 32-byte transaction hash -> unspent transaction output record for that transaction
2. 'B' -> 32-byte block hash: the block hash up to which the database represents the unspent transaction outputs

自那篇文章以来，我们已经实现了交易，但我们还没有使用过chainstate存储他们的输出。所以，这就是我们现在要做的。

chainstate不存储交易。相反，它存储所谓的UTXO集或未使用的事务输出集。除此之外，它存储“数据库代表未使用的事务输出的块哈希”，我们现在将省略它们，因为我们没有使用块高度（但我们将在下一篇文章中实现它们）。

那么，为什么我们要设置UTXO？

看下我们之前实现的 Blockchain.FindUnspentTransactions方法：

func (bc *Blockchain) FindUnspentTransactions(pubKeyHash []byte) []Transaction {
    ...
    bci := bc.Iterator()

    for {
        block := bci.Next()

        for _, tx := range block.Transactions {
            ...
        }

        if len(block.PrevBlockHash) == 0 {
            break
        }
    }
    ...
}
复制代码

该函数查找具有未使用输出的事务。由于事务存储在块中，因此它会迭代块链中的每个块并检查其中的每个事务。截至2017年9月18日，比特币有485,860个区块，整个数据库占用140+ Gb的磁盘空间。这意味着必须运行完整节点来验证事务。此外，验证事务需要迭代许多块。

该问题的解决方案是有一个只存储未使用输出的索引，这就是UTXO设置的作用：这是一个从所有区块链事务构建的缓存（通过迭代块，是的，但这只做一次），以后用于计算余额和验证新交易。截至2017年9月，UTXO集合约为2.7 Gb。

好吧，让我们考虑一下我们需要改变什么来实现UTXO集。目前，以下方法用于查找事务：

1. Blockchain.FindUnspentTransactions- 查找具有未使用输出的事务的主函数。这是所有块的迭代发生的功能。
2. Blockchain.FindSpendableOutputs- 创建新事务时使用此功能。如果找到足够数量的输出保持所需数量，会使用Blockchain.FindUnspentTransactions.
3. Blockchain.FindUTXO- 查找公钥哈希的未使用输出，用于获得结余。会使用Blockchain.FindUnspentTransactions.
4. Blockchain.FindTransaction- 通过其ID在区块链中查找交易。它迭代所有块直到找到它。

如您所见，所有方法都迭代数据库中的块。但是我们现在无法改进所有这些，因为UTXO集不存储所有事务，而只存储那些具有未使用输出的事务。因此，它不能用于Blockchain.FindTransaction.

所以，我们需要以下方法：

1. Blockchain.FindUTXO- 通过迭代块找到所有未使用的输出。
2. UTXOSet.Reindex — 使用 FindUTXO找到未使用的输出，并将它们存储在数据库中。这是缓存发生的地方。
3. UTXOSet.FindSpendableOutputs – 类似 Blockchain.FindSpendableOutputs，但使用UTXO集。
4. UTXOSet.FindUTXO – 类似 Blockchain.FindUTXO，但使用UTXO集。
5. Blockchain.FindTransaction 和原来保持一致.

因此，两个最常用的函数将从现在开始使用缓存！我们开始编码了。

type UTXOSet struct {
    Blockchain *Blockchain
}
复制代码

我们将使用单个数据库，但我们会将UTXO集存储在不同的存储桶中。从而，UTXOSet和 Blockchain绑定在了一起

func (u UTXOSet) Reindex() {
    db := u.Blockchain.db
    bucketName := []byte(utxoBucket)

    err := db.Update(func(tx *bolt.Tx) error {
        err := tx.DeleteBucket(bucketName)
        _, err = tx.CreateBucket(bucketName)
    })

    UTXO := u.Blockchain.FindUTXO()

    err = db.Update(func(tx *bolt.Tx) error {
        b := tx.Bucket(bucketName)

        for txID, outs := range UTXO {
            key, err := hex.DecodeString(txID)
            err = b.Put(key, outs.Serialize())
        }
    })
}
复制代码

此方法最初创建UTXO集。首先，如果存在，则删除存储桶，然后从区块链中获取所有未使用的输出，最后将输出保存到存储桶。

Blockchain.FindUTXO几乎与Blockchain.FindUnspentTransactions完全相同，但现在它返回一个映射TransactionID → TransactionOutputs .

现在，UTXO集可用于发送coins：

func (u UTXOSet) FindSpendableOutputs(pubkeyHash []byte, amount int) (int, map[string][]int) {
    unspentOutputs := make(map[string][]int)
    accumulated := 0
    db := u.Blockchain.db

    err := db.View(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte(utxoBucket))
        c := b.Cursor()

        for k, v := c.First(); k != nil; k, v = c.Next() {
            txID := hex.EncodeToString(k)
            outs := DeserializeOutputs(v)

            for outIdx, out := range outs.Outputs {
                if out.IsLockedWithKey(pubkeyHash) && accumulated < amount {
                    accumulated += out.Value
                    unspentOutputs[txID] = append(unspentOutputs[txID], outIdx)
                }
            }
        }
    })

    return accumulated, unspentOutputs
}
复制代码

或者校验余额:

func (u UTXOSet) FindUTXO(pubKeyHash []byte) []TXOutput {
    var UTXOs []TXOutput
    db := u.Blockchain.db

    err := db.View(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte(utxoBucket))
        c := b.Cursor()

        for k, v := c.First(); k != nil; k, v = c.Next() {
            outs := DeserializeOutputs(v)

            for _, out := range outs.Outputs {
                if out.IsLockedWithKey(pubKeyHash) {
                    UTXOs = append(UTXOs, out)
                }
            }
        }

        return nil
    })

    return UTXOs
}
复制代码

这些是Blockchain 方法对应的略微修改过的版本.

设置UTXO意味着我们的数据（事务）现在被分成存储：实际事务存储在区块链中，未使用的输出存储在UTXO集中。这种分离需要牢固的同步机制，因为我们希望始终更新UTXO集并存储最近事务的输出。但是我们不希望每次开采新块时重新索引，因为我们想要避免这些频繁的区块链扫描。因此，我们需要一种更新UTXO集的机制：

func (u UTXOSet) Update(block *Block) {
    db := u.Blockchain.db

    err := db.Update(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte(utxoBucket))

        for _, tx := range block.Transactions {
            if tx.IsCoinbase() == false {
                for _, vin := range tx.Vin


    
 {
                    updatedOuts := TXOutputs{}
                    outsBytes := b.Get(vin.Txid)
                    outs := DeserializeOutputs(outsBytes)

                    for outIdx, out := range outs.Outputs {
                        if outIdx != vin.Vout {
                            updatedOuts.Outputs = append(updatedOuts.Outputs, out)
                        }
                    }

                    if len(updatedOuts.Outputs) == 0 {
                        err := b.Delete(vin.Txid)
                    } else {
                        err := b.Put(vin.Txid, updatedOuts.Serialize())
                    }

                }
            }

            newOutputs := TXOutputs{}
            for _, out := range tx.Vout {
                newOutputs.Outputs = append(newOutputs.Outputs, out)
            }

            err := b.Put(tx.ID, newOutputs.Serialize())
        }
    })
}
复制代码

该方法看起来很大，但它的作用非常简单。当开采新块时，应更新UTXO集。更新意味着删除已用完的事务并从新挖掘的事务中添加未使用的输出。如果删除了一个输出的事务，不再包含输出，那么它也会被删除。非常简单！

现在让我们在必要时使用UTXO集：

func (cli *CLI) createBlockchain(address string) {
    ...
    bc := CreateBlockchain(address)
    defer bc.db.Close()

    UTXOSet := UTXOSet{bc}
    UTXOSet.Reindex()
    ...
}
复制代码

在创建新的区块链后立即重新编制索引。现在，这是唯一的地方Reindex虽然它在这里看起来很过分，但是因为在区块链的开头，只有一个区块有一个交易，而且Update可以用来代替。但是我们将来可能需要重建索引机制。

func (cli *CLI) send(from, to string, amount int) {
    ...
    newBlock := bc.MineBlock(txs)
    UTXOSet.Update(newBlock)
}
复制代码

并且在挖掘新块之后更新UTXO集。

我们来看看它是否有效

$ blockchain_go createblockchain -address 1JnMDSqVoHi4TEFXNw5wJ8skPsPf4LHkQ1
00000086a725e18ed7e9e06f1051651a4fc46a315a9d298e59e57aeacbe0bf73

Done!

$ blockchain_go send -from 1JnMDSqVoHi4TEFXNw5wJ8skPsPf4LHkQ1 -to 12DkLzLQ4B3gnQt62EPRJGZ38n3zF4Hzt5 -amount 6
0000001f75cb3a5033aeecbf6a8d378e15b25d026fb0a665c7721a5bb0faa21b

Success!

$ blockchain_go send -from 1JnMDSqVoHi4TEFXNw5wJ8skPsPf4LHkQ1 -to 12ncZhA5mFTTnTmHq1aTPYBri4jAK8TacL -amount 4
000000cc51e665d53c78af5e65774a72fc7b864140a8224bf4e7709d8e0fa433

Success!

$ blockchain_go getbalance -address 1JnMDSqVoHi4TEFXNw5wJ8skPsPf4LHkQ1
Balance of '1F4MbuqjcuJGymjcuYQMUVYB37AWKkSLif': 20

$ blockchain_go getbalance -address 12DkLzLQ4B3gnQt62EPRJGZ38n3zF4Hzt5
Balance of '1XWu6nitBWe6J6v6MXmd5rhdP7dZsExbx': 6

$ blockchain_go getbalance -address 12ncZhA5mFTTnTmHq1aTPYBri4jAK8TacL
Balance of '13UASQpCR8Nr41PojH8Bz4K6cmTCqweskL': 4
复制代码

Nice! 1JnMDSqVoHi4TEFXNw5wJ8skPsPf4LHkQ1地址收到奖励3次：

1. 一次来自于挖掘创世块。
2. 一次来自于开采块0000001f75cb3a5033aeecbf6a8d378e15b25d026fb0a665c7721a5bb0faa21b.
3. 一次来自于开采块000000cc51e665d53c78af5e65774a72fc7b864140a8224bf4e7709d8e0fa433.

Merkle Tree

我想在这篇文章中讨论另外一种优化机制。

如上所述，完整的比特币数据库（即区块链）需要超过140 Gb的磁盘空间。由于比特币的分散性，网络中的每个节点必须是独立且自给自足的，即每个节点必须存储区块链的完整副本。随着许多人开始使用比特币，这条规则变得更难以遵循：每个人都不可能运行完整的节点。此外，由于节点是网络的成熟参与者，因此他们有责任：他们必须验证交易和阻止。此外，与其他节点交互并下载新块需要一定的互联网流量。

In the original Bitcoin paper由Satoshi Nakamoto发布，有一个解决这个问题的方法：简化付款验证（SPV）。 SPV是一个轻便的比特币节点，不会下载整个区块链和不验证块和事务。相反，它在块中查找事务（以验证付款）并链接到完整节点以检索必要的数据。此机制允许多个轻型钱包节点仅运行一个完整节点。

为了使SPV成为可能，应该有一种方法来检查块是否包含某些事务而不下载整个块。这就是Merkle树发挥作用的地方。

比特币使用Merkle树来获取事务哈希值，然后将其保存在块头中并由工作量证明系统考虑。到目前为止，我们只是在块中连接每个事务的哈希并应用SHA-256给他们。这也是获得块事务的唯一表示的好方法，但它没有Merkle树的好处。

让我们看一下Merkle树：

type MerkleTree struct {
    RootNode *MerkleNode
}

type MerkleNode struct {
    Left  *MerkleNode
    Right *MerkleNode
    Data  []byte
}
复制代码

func NewMerkleNode(left, right *MerkleNode, data []byte) *MerkleNode {
    mNode := MerkleNode{}

    if left == nil && right == nil {
        hash := sha256.Sum256(data)
        mNode.Data = hash[:]
    } else {
        prevHashes := append(left.Data, right.Data...)
        hash := sha256.Sum256(prevHashes)
        mNode.Data = hash[:]
    }

    mNode.Left = left
    mNode.Right = right

    return &mNode
}
复制代码

func NewMerkleTree(data [][]byte) *MerkleTree {
    var nodes []MerkleNode

    if len(data)%2 != 0 {
        data = append(data, data[len(data)-1])
    }

    for _, datum := range data {
        node := NewMerkleNode(nil, nil, datum)
        nodes = append(nodes, *node)
    }

    for i := 0; i < len(data)/2; i++ {
        var newLevel []MerkleNode

        for j := 0; j < len(nodes); j += 2 {
            node := NewMerkleNode(&nodes[j], &nodes[j+1], nil)
            newLevel = append(newLevel, *node)
        }

        nodes = newLevel
    }

    mTree := MerkleTree{&nodes[0]}

    return &mTree
}
复制代码

func (b *Block) HashTransactions() []byte {
    var transactions [][]byte

    for _, tx := range b.Transactions {
        transactions = append(transactions, tx.Serialize())
    }
    mTree := NewMerkleTree(transactions)

    return mTree.RootNode.Data
}
复制代码

5 2 OP_ADD 7 OP_EQUAL
复制代码

<signature> <pubKey> OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
复制代码