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集存储在不同的存储桶中。从而,UTXOSetBlockchain绑定在了一起

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树:

为每个块构建一个Merkle树,它以叶子(树的底部)开始,其中叶子是事务哈希(比特币使用双SHA256散列)。叶子数必须是偶数,但不是每个块都包含偶数个事务。如果存在奇数个事务,则最后一个事务是重复的(在Merkle树中,而不是在块中!)。

从底部向上移动,叶子成对分组,它们的哈希串联,并且从连接的哈希中获得新的哈希。新的哈希形成新的树节点。重复此过程,直到只有一个节点,称为树的根。然后将根哈希用作事务的唯一表示,保存在块头中,并用于工作量证明系统。

Merkle树的好处是节点可以在不下载整个块的情况下验证某些事务的成员资格。为此,只需要事务哈希,Merkle树根哈希和Merkle路径。

最后,让我们编写代码:

type MerkleTree struct {
    RootNode *MerkleNode
}

type MerkleNode struct {
    Left  *MerkleNode
    Right *MerkleNode
    Data  []byte
}

我们从结构开始。一切MerkleNode保持数据和链接到其分支。MerkleTree实际上是链接到下一个节点的根节点,这些节点又链接到其他节点等。

让我们先创建一个新节点:

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
}

创建新树时,首先要确保的是有一些偶数叶子。之后,data(这是一系列序列化事务)被转换为树叶,并从这些叶子生长树。

现在, 让我们修改 Block.HashTransactions,在工作量证明系统中用于获取事务哈希:

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
}

首先,交易是序列化的(使用encoding/gob),然后他们被用来建立一个Merkle树。树的根将作为块事务的唯一标识符。

P2PKH

还有一件事我想更详细地讨论。

你还记得,在比特币中有Script编程语言,用于锁定事务输出;和交易输入提供解锁输出的数据。语言很简单,这种语言的代码只是一系列数据和运算符。考虑这个例子:

5 2 OP_ADD 7 OP_EQUAL

5, 2, 以及 7 是 data. OP_ADDOP_EQUAL 是 operators. Script代码从左到右执行:每个数据都放入堆栈,下一个操作符应用于顶层堆栈元素。Script堆栈只是一个简单的FILO(第一输入最后输出)内存存储:堆栈中的第一个元素是最后一个元素,每个元素都放在前一个元素上。

让我们将上述脚本的执行分解为以下步骤:

  1. Stack:空。Script:5 2 OP_ADD 7 OP_EQUAL.
  2. Stack: 5. Script: 2 OP_ADD 7 OP_EQUAL.
  3. Stack: 5 2. Script: OP_ADD 7 OP_EQUAL.
  4. Stack: 7. Script: 7 OP_EQUAL.
  5. Stack: 7 7. Script: OP_EQUAL.
  6. Stack: true. Script: empty.

OP_ADD从堆栈中获取两个元素,汇总它们,并将总和推入堆栈。OP_EQUAL从堆栈中取出两个元素并对它们进行比较:如果它们相等则会推动它们true到堆栈;否则它会推动false。脚本执行的结果是顶部堆栈元素的值:在我们的例子中,它是true,这意味着脚本成功完成。

现在让我们看看比特币中用于执行付款的脚本:

<signature> <pubKey> OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG

调用此脚本支付公钥哈希(P2PKH),这是比特币中最常用的脚本。它实际上支付公钥哈希,即用某个公钥锁定硬币。这是比特币支付的核心:没有账户,没有资金转移;只有一个脚本可以检查提供的签名和公钥是否正确。

该脚本实际上存储在两个部分:

  1. 第一块, <signature> <pubKey>,存储在输入中ScriptSig 字段.
  2. 第二块, OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG存储在输出中ScriptPubKey.

因此,它的输出定义了解锁逻辑,它的输入提供数据来解锁输出。让我们执行脚本:

  1. Stack: 空 Script: <signature> <pubKey> OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
  2. Stack: <signature>Script: <pubKey> OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
  3. Stack: <signature> <pubKey>Script: OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
  4. Stack: <signature> <pubKey> <pubKey>Script: OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
  5. Stack: <signature> <pubKey> <pubKeyHash>Script: <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
  6. Stack: <signature> <pubKey> <pubKeyHash> <pubKeyHash>Script: OP_EQUALVERIFY OP_CHECKSIG
  7. Stack: <signature> <pubKey>Script: OP_CHECKSIG
  8. Stack: true or false. Script: empty.

OP_DUP复制顶部堆栈元素。OP_HASH160采用顶部堆栈元素并将其哈希RIPEMD160;结果被推回堆栈。OP_EQUALVERIFY比较两个顶部堆栈元素,如果它们不相等,则中断脚本。OP_CHECKSIG通过散列事务并使用来验证事务的签名<signature><pubKey>。后一个运算符非常复杂:它会对事务进行修剪,对其进行哈希处理(因为它是已签名的事务的哈希),并使用提供的方式检查签名是否正确<signature><pubKey>.

拥有这样的脚本语言使得比特币也成为智能合约平台:除了转移到单个密钥之外,该语言还可以实现其他支付方案。例如,

Conclusion

就是这样!我们已经实现了基于区块链的加密货币的几乎所有关键功能。我们有区块链,地址,挖掘和交易。但是还有一件事给所有这些机制赋予生命,并使比特币成为一个全球系统:共识。在下一篇文章中,我们将开始实现区块链的“分散”部分。敬请关注!

原文链接:https://jeiwan.cc/posts/building-blockchain-in-go-part-6/