源码参考

https://github.com/huangzhenshi/BuildBitCoinSystemGo/tree/master/blockchain_learn/chapter6

参考博客

https://www.jianshu.com/p/bfda51cd340d

发起一笔正常交易的构建过程：

校验发起人、收款人的Address是否有效
检查发起人是否有足够的支付余额，并且返回相应的用来消费的outputs（map结构）
余额充足的话交易成立，会以outputs来构建这笔交易的inputs，以及构建该笔交易的outputs
把inputs和outputs构建成一笔交易，再求Hash值，作为该笔交易的Txid
再对这笔交易的每个input逐个做签名，最终生成一个完整和有效的Transaction

主要耗费时间的是第二步，需要遍历所有的交易，直到找到足够的用来支付当前交易的 output余额，随着比特币交易的增多，需要遍历的工作量越来越大，而且有很多是无意义的遍历，因为很多被完全消费掉的交易（没有余额），每一次交易仍然会被遍历一次。所以引入UTXOSet，过滤掉没有余额的交易，从而提升交易的速度。

UTXOSet

UTXOSet的数据结构和Blockchain是一样的，都是一个map的结构

UTXOSet和Blockchain的区别在于

Blockchain里面的key存储的是block的hash，value对应的是整个Block，而UTXOSet的，key为transactionID，value是这个transaction里面的所有的未被消费掉的TXOutputs的集合。
UTXOSet不需要 tip这个字段，因为UTXO的定位就是未消费的output的索引，而且这个字段可以从原生的Blockchain里面很快获取到，没有必要重复存储
UTXOSet的map里面存储的不是所有的交易，只存储包含未花费bitcoin的交易
UTXOSet的map里面存储的不是完整的交易，完整的一个交易由：输入、输出、Txid组成，而UTXOSet里面存储的交易只有Txid（key)和输出（value），没有输入

type UTXOSet struct {
    Blockchain *Blockchain
}
type Blockchain struct {
    tip []byte
    db  *bolt.DB
}

UTXOSet的作用：过滤和缩小查询时候的内存空间。用额外的存储空间换查询速度，从而提升比特币交易的速度。
优点：

过滤：每次交易的时候只需要遍历有余额的比特币交易，原生的区块链被分为两部分：没有任何余额的比特币交易、有余额的比特币交易（UTXOSet）。而且每次遍历UTXOSet的时候，只要剩余金额大于交易金额，遍历就可以break了，找到了足够支付当前交易的余额。也就是说，转账的金额越小，或者转账发起人拥有的比特币越多，遍历的时间就越短。
UTXOSet中的交易不包含该笔交易的输入源，所以计算交易的时候占用内存更小

缺点:

每次发起一次比特币的交易的时候（包括转账和挖矿奖励），都需要更新这个UTXOSet，不过更新的成本很低，因为更新的时候是知道所有input的Txid，可以根据键值对快速查找，新增也很方便，把所有的output丢进去就可以了
需要额外的存储空间来存储这些未消费的UTXOSet

UTXO的初始化和交易更新

初始化
根据一个完整的区块链，来初始化构建一个UTXO，调用 Reindex()方法

func (u UTXOSet) Reindex() {
    UTXO := u.Blockchain.FindUTXO()
    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())
        }
    })
}

func (bc *Blockchain) FindUTXO() map[string]TXOutputs {}

更新：每次发生交易的时候都需要更新这个UTXOSET，不过计算的开销并不大，都是通过键值对查找和替换

        //遍历所有的交易
        for _, tx := range block.Transactions {
            //如果是挖矿交易的话，只需要把output加进去就可以了
            //如果是普通交易的话，需要先把所有的input都逆推到Txid，再一个个delete掉，最后再把所有的output加进去
            //这里的代码就是删除对应的本次交易消费掉的output
            if tx.IsCoinbase() == false {
                //遍历所有的Vin，通过Vin.Txid找到对应的UTXO中的outs
                //建立一个新的updatedOuts，通过过滤掉Vin消费的out，剩下的丢到updatedOuts里面，最后替换掉就ok
                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())
                    }

                }
            }
            //不管是挖矿交易还是正常交易，都需要把新产生的output封装在当前Txid里面，然后put到UTXOSet中
            newOutputs := TXOutputs{}
            for _, out := range tx.Vout {
                newOutputs.Outputs = append(newOutputs.Outputs, out)
            }
            err := b.Put(tx.ID, newOutputs.Serialize())
        }
    })

UTXO提供的方法 FindSpendableOutputs

优点：如果A用户比特币充裕，足够支持当前amount金额的交易，则不需要遍历所有的output，只要遍历到够花就break了
适用业务场景: 该方法适用于交易和查询余额的时候，查询账户余额的时候需要遍历整个UTXOSet
缺点:

每次发起一次比特币的交易的时候（相互转账或者挖矿奖励），都需要更新这个UTXOSet，不过更新的成本很低，因为更新的时候是知道所有input的Txid，可以根据键值对快速查找，新增也很方便，把所有的output丢进去就可以了
需要额外的存储空间来存储这些未消费的outputs

// 注意这里读取的是数据库
// 返回值：第一个是该用户的全部余额或者可供消费的output集合的总金额，第二个是用来即将被消费的属于该用户的output
// 可能是（比如要转账10比特币，该用户正好拥有10个比特币），也可能不是该用户的所有output（比如A有100个比特币，只需要转出10个）
// 该方法有一个特别好的地方，如果A用户比特币充裕，足够支持当前amount金额的交易，则不需要遍历所有的output，只要遍历到够花就break了
func (u UTXOSet) FindSpendableOutputs(pubkeyHash []byte, amount int) (int, map[string][]int) {
    unspentOutputs := make(map[string][]int)
    accumulated := 0
    db := u.Blockchain.db
    //数据库中读取chainstate bucket，然后遍历
    err := db.View(func(tx *bolt.Tx) error {
        b := tx.Bucket([]byte(utxoBucket))
        c := b.Cursor()
        //遍历所有的包含有未花费output的交易
        for k, v := c.First(); k != nil; k, v = c.Next() {
            txID := hex.EncodeToString(k)
            outs := DeserializeOutputs(v)
            //遍历该交易中所有的未花费的output，按照pubkeyHash进行匹配，并且追加到unspentOutputs当中
            for outIdx, out := range outs.Outputs {
                if out.IsLockedWithKey(pubkeyHash) && accumulated < amount {
                    accumulated += out.Value
                    unspentOutputs[txID] = append(unspentOutputs[txID], outIdx)
                }
            }
        }

        return nil
    })
    if err != nil {
        log.Panic(err)
    }

    return accumulated, unspentOutputs
}

挖矿奖励

当一个区块链节点收到一笔记账消息的时候，会在这个记账信息的后面添加一笔交易，也就是给自己的Address添加挖矿奖励的交易

func (cli *CLI) checkAndRecord(from, to string, amount int) {
    bc := NewBlockchain()
    UTXOSet := UTXOSet{bc}
    tx := NewUTXOTransaction(from, to, amount, &UTXOSet)
    
    //添加一笔给自己奖励的交易，并且加入到[]Transaction中
    cbTx := NewCoinbaseTX(myaccount, "")
    txs := []*Transaction{cbTx, tx}
    newBlock := bc.MineBlock(txs)
}

第六章：挖矿和UTXOSet