Use go language to build blockchain Part4. Transaction 1

English source address

Introduction

Transactions are at the heart of Bitcoin, and the sole purpose of the blockchain is to store transactions in a safe and secure manner, so no one can modify them after they have been created. Today we start implementing transactions, but since this is a fairly large topic, I will It is divided into two parts: in this part, we will implement the general mechanism of transactions, and in the second part, we will study the details.
Also, since the code changes are huge, it doesn’t make sense to describe them here. You can see all the changes here.

There is no spoon(The Matrix lines)

If you’ve ever developed a web application, in order to implement payments, you’d probably create these tables in your database: accounts and transactions. An account would store information about users, including their personal information and balances, and a transaction would store a Information about the transfer of funds from one account to another. In Bitcoin, transactions are implemented in completely different ways. They are:

  1. no account
  2. no balance
  3. no address
  4. no coins
  5. no sender and receiver

Since the blockchain is a public and open database, we don’t want to store any sensitive information about wallet owners. Coins are not held in accounts. Transactions do not transfer money from one address to another. There is no field to hold account balances or attributes. There are only transactions, but what’s inside a transaction?

bitcoin transaction
A transaction is a combination of inputs and outputs

type Transaction struct {<!-- -->
ID []byte
Vin[]TXInput
Vout []TXOutput
}

For each new transaction, its input will refer to the output of the previous transaction (there is an exception here, the coinbase transaction), and the reference means the cost. The so-called reference to a previous input means to include a previous output Among the inputs of another transaction is the transaction output before spending. The output of the transaction is where the coins are actually stored. The diagram below illustrates the interrelationships between transactions.

have to be aware of is:

  1. There are some outputs that are not associated with an input
  2. The input of a transaction can refer to the output of multiple previous transactions
  3. An input must reference an output

Throughout the text, we will use words like ‘money’, ‘coin’, ‘spend’, ‘send’, ‘account’, etc. But in Bitcoin, these concepts do not actually exist. Transactions are simply Through a script (script) to lock (lock) some values (value), and these values can only be unlocked (unlock) by the person who locked them.
(Every bitcoin transaction creates an output, which is recorded in the blockchain. Sending bitcoin to someone actually means creating a new UTXO and registering it with that person’s address, which can be used by him.)

Transaction output

start with the output

type TXOutput struct {<!-- -->
Value int
ScriptPubKey string
}

The output mainly consists of two parts:

  1. A certain amount of Bitcoin (Value)
  2. A locked script (ScriptPubKey) that must be unlocked to spend the money

In fact, ‘coin’ is stored in the official output (note, that is, the Value field above). The storage here refers to locking the output with a mathematical puzzle, which is stored in ScriptPubKey. Internally, Bitcoin uses a scripting language called Script, which is used to define the logic of locking and unlocking outputs. Although this language is quite primitive (this is intentional to avoid potential hacking and abuse), it is not complicated, but We also won’t discuss its details. You can find a detailed explanation here.

In Bitcoin, the value field stores the number of satoshi, not the number of BTC. One satoshi is equal to one hundred millionth of BTC (0.00000001BTC), which is also the smallest currency unit in Bitcoin (like a cent coins)

Since addresses are not implemented, for now we will avoid full scripts involving logic. ScriptPubKey will store an arbitrary string (user-defined wallet address).

By the way, having such a scripting language also means that Bitcoin can actually be used as a smart contract platform.

Regarding the output, a very important point is: they are indivisible. That is to say, you can’t just quote a part of them. Either don’t use them, and if you want to use them, you must use them all at once. When a new transaction If an output is referenced, the output must be spent in full. If its value is greater than required, a change will be generated, and the change will be returned to the sender. This is very similar to the real-world scenario, when When you want to pay, if something is worth $1 and you give a $5 bill, you get a $4 change.

Transaction input

here is the input

type TXInput struct {<!-- -->
Txid []byte
Vout int
ScriptSig string
}

As mentioned before, an input refers to an output: Txid stores the ID of the previous transaction, and Vout stores the index of all outputs in that transaction (because a transaction can have multiple outputs, you need The specific one when there is information). ScriptSig is a script that provides data that unlocks the ScriptPubKey field in the output structure. If the data provided by ScriptSig is correct, then the output is unlocked, and the unlocked value can be used To generate new outputs; if the data is incorrect, the output cannot be referenced in the input, or in other words, the output cannot be used. This mechanism ensures that users cannot spend coins belonging to others.
Again, since we haven’t implemented the address yet, ScriptSig will only store a user-defined arbitrary wallet address at the moment. We will implement the public key and signature in the next article.
Let’s briefly summarize. The output is where the ‘coin’ is stored. Each output will have an unlock script, which defines the logic of unlocking the output. Every new transaction must have at least one input and output. A The input refers to the previous output and provides unlocking data (that is, the ScriptSig field), which will be used to unlock the output in the output’s unlocking script, and its value can be used to generate a new output after the unlocking is completed .
Each input is the output of a previous transaction, so assuming that a certain transaction starts to go back and forth, which one of the inputs and outputs involved in it existed first? In other words, this is a chicken and the egg who comes first Who comes first, which came first, the egg or the chicken?

First came the egg

In Bitcoin, there is an egg first, and then there is a chicken. The logic of input reference output is a classic ‘egg or chicken’ problem: input first produces output, and then output makes input possible. In Bitcoin, There is output first, and then there is input. In other words, each transaction has only output and no input.
When the miner mines a new block, it adds a coinbase transaction to the new block. A coinbase transaction is a special kind of transaction that doesn’t need to refer to the output of a previous transaction. It generates coins ‘out of thin air’ (that is, new coins are generated), this is the miner’s reward for digging out mining, and it can also be understood as ‘issue new coins’.
At the beginning of the blockchain, that is, the first block, is called the genesis block. It is this genesis block that produces the initial output of the blockchain. For the genesis block, there is no need to refer to the previous transaction Output. Because there is no transaction at all before the creation block, that is, there is no transaction output.
To create a coinbase transaction:

func NewCoinbaseTX(to, data string) *Transaction {<!-- -->
if data == "" {<!-- -->
data = fmt.Sprintf("Reward to %s", to)
}

txin := TXInput{<!-- -->[]byte{<!-- -->}, -1, data}
txout := TXOutput{<!-- -->subsidy, to}
tx := Transaction{<!-- -->nil, []TXInput{<!-- -->txin}, []TXOutput{<!-- -->txout}}
tx. SetID()

return & tx
}

The coinbase transaction has only one output and no input. In our implementation, it shows that Txid is empty, and Vout is equal to -1. Moreover, in the current implementation, the coinbase transaction does not store scripts in ScriptSig, but only stores an arbitrary The string data.

In Bitcoin, the first coinbase transaction contains the following message: “The Times 03/Jan/2009 Chancellor on brink of second bailout for banks”. Click here to view

Subsidy is the reward for digging out a new block. In Bitcoin, this number is not actually stored, but calculated based on the total number of blocks: the total number of blocks divided by 210000 is subsidy. The reward for digging out the genesis block It is 50BTC, and the reward is halved every 210,000 blocks. In our implementation, this reward value will be a constant (at least for now).

Save the transaction to the blockchain

From now on, each block must store at least one transaction. If there is no transaction, it is impossible to generate a new block. This means that we should overflow the Data field of the Block and store the transaction instead:

type Block struct {<!-- -->
Timestamp int64
Transactions []*Transaction
PrevBlockHash []byte
Hash[]byte
Nonce int
}

NewBlock and NewGenesisBlock must also be changed accordingly:

func NewBlock(transactions []*Transaction, prevBlockHash []byte) *Block {<!-- -->
block := & amp;Block{<!-- -->time.Now().Unix(), transactions, prevBlockHash, []byte{<!-- -->}, 0}
pow := NewProofOfWork(block)
nonce, hash := pow. Run()

block.Hash = hash[:]
block.Nonce = nonce

return block
}

func NewGenesisBlock(coinbase *Transaction) *Block {<!-- -->
return NewBlock([]*Transaction{<!-- -->coinbase}, []byte{<!-- -->})
}

Next modify the function that creates the blockchain:

func CreateBlockchain(address string) *Blockchain {<!-- -->
var tip []byte
db, _ := bolt. Open(dbFile, 0600, nil)

_ = db.Update(func(tx *bolt.Tx) error {<!-- -->
cbtx := NewCoinbaseTX(address, genesisCoinbaseData)
genesis := NewGenesisBlock(cbtx)

b, _ := tx.CreateBucket([]byte(blocksBucket))

if b == nil {<!-- -->
b, _ := tx.CreateBucket([]byte(blocksBucket))
_ = b. Put(genesis. Hash, genesis. Serialize())
_ = b.Put([]byte("l"), genesis.Hash)
tip = genesis. Hash
} else {<!-- -->
tip = b. Get([]byte("l"))
}
return nil
})
bc := Blockchain{<!-- -->tip, db}

return & bc
}

Now, this function will accept an address as a parameter, and this address will be used to receive the reward for mining the genesis block.

Proof of Work

The workload proof algorithm must take into account the transactions stored in the block, so as to ensure the consistency and reliability of blockchain transaction storage. Therefore, we must modify the ProofOfWork.prepareData method:

func (pow *ProofOfWork) prepareData(nonce int) []byte {<!-- -->
data := bytes. Join(
[][]byte{<!-- -->
pow.block.PrevBlockHash,
pow.block.HashTransactions(), // This line was changed
IntToHex(pow. block. Timestamp),
IntToHex(int64(targetBits)),
IntToHex(int64(nonce)),
},
[]byte{<!-- -->},
)

return data
}

Instead of using pow.block.Data before, now we use pow.block.HashTransactions():

func (b *Block) HashTransactions() []byte {<!-- -->
var txHashes[][]byte
var txHash [32]byte

for _, tx := range b.Transactions {<!-- -->
txHashes = append(txHashes, tx.ID)
}
txHash = sha256.Sum256(bytes.Join(txHashes, []byte{<!-- -->}))
return txHash[:]
}

It is not the first time that we have encountered this approach of providing a unique representation of data through a hash value. We want to identify all transactions in a block with only a hash value. To do this, first obtain each transaction hash values, and then associate them, and finally obtain a combined hash value after connection.

Bitcoin uses a more complex technique: it represents all transactions contained in a block as a Merkle tree, and then uses the root hash of the tree in the workload proof system. This method allows us to quickly Retrieve whether a block contains a certain transaction, that is, only need root hash without downloading all transactions to complete the judgment.

To check that it’s correct so far:

╰─ ./blockchain_impl_in_go createblockchain -address Ivan ─╯
00000060b65eb7a78b68206835d12e06c8b00940da37b5c773c1d465a8a3a35f

Done!

Great, we’ve got our first mining reward, but how do we check the balance?

Unspent transaction output

We need to find all unspent transactions outputs (UTXO), unspent (unspent) means that this output has not been included in any transaction input, or is not referenced by any input. In the above illustration In , the unspent output is

  1. tx0, output 1;
  2. tx1, output 0;
  3. tx3, output 0;
  4. tx4, output 0.

Of course, when checking balances, we don’t need to know all UTXOs on the entire blockchain, just the ones we can unlock (currently we haven’t implemented keys, so we’ll use user-defined addresses instead). First, let’s define the lock and unlock methods on the input and output:

func (in *TXInput) CanUnlockOutputWith(unlockingData string) bool {<!-- -->
return in.ScriptSig == unlockingData
}

func (out *TXOutput) CanBeUnlockedWith(unlockingData string) bool {<!-- -->
return out. ScriptPubKey == unlockingData
}

Here, we just compare the script field with unlockingData. After we implement the address based on the private key in the follow-up article, this part will be improved.
Next, find transactions that contain unspent outputs, which is actually quite difficult:

func (bc *Blockchain) FindUnspentTransactions(address string) []Transaction {<!-- -->
var upsentTXs []Transaction
spentTXOs := make(map[string][]int)
bci := bc. Iterator()

for {<!-- -->
block := bci. Next()

for _, tx := range block.Transactions {<!-- -->
txID := hex.EncodeToString(tx.ID)
Outputs:
for outIdx, out := range tx.Vout {<!-- -->
if spentTXOs[txID] != nil {<!-- -->
for _, spentOut := range spentTXOs[txID] {<!-- -->
if spentOut == outIdx {<!-- -->
continue Outputs
}
}
}
if out.CanBeUnlockedWith(address) {<!-- -->
upsentTXs = append(upsentTXs, *tx)
}
}
if tx.IsCoinbase() == false {<!-- -->
for _, in := range tx. Vin {<!-- -->
if in.CanUnlockOutputWith(address) {<!-- -->
inTxID := hex.EncodeToString(in.Txid)
spentTXOs[inTxID] = append(spentTXOs[inTxID], in.Vout)
}
}
}
}
if len(block. PrevBlockHash) == 0 {<!-- -->
break
}
}

return upsentTXs
}

Since transactions are stored in blocks, we have to check every transaction in the blockchain. Starting with the output:

if out.CanBeUnlockedWith(address) {<!-- -->
unspentTXs = append(unspentTXs, tx)
}

If an output is locked by an address, and this address happens to be the address we are looking for, then this output is what we want. But before getting it, we need to check whether the output has been included in the output of a transaction, That is to check if it has already been spent:

if spentTXOs[txID] != nil {<!-- -->
for _, spentOut := range spentTXOs[txID] {<!-- -->
if spentOut == outIdx {<!-- -->
continue Outputs
}
}
}

We skip outputs that are already contained in other inputs (meaning that the output has been spent and can no longer be used). After checking the output, we aggregate all inputs that unlock the output for a given address (this does not Applies to coinbase transactions as they do not unlock outputs)

if tx.IsCoinbase() == false {<!-- -->
    for _, in := range tx. Vin {<!-- -->
        if in.CanUnlockOutputWith(address) {<!-- -->
            inTxID := hex.EncodeToString(in.Txid)
            spentTXOs[inTxID] = append(spentTXOs[inTxID], in.Vout)
        }
    }
}

This function returns a list of transactions containing unspent outputs. To calculate the balance, we also need a function that takes these transactions as input and returns an output:

func (bc *Blockchain) FindUTXO(address string) []TXOutput {<!-- -->
       var UTXOs []TXOutput
       unspentTransactions := bc. FindUnspentTransactions(address)

       for _, tx := range unspentTransactions {<!-- -->
               for _, out := range tx.Vout {<!-- -->
                       if out.CanBeUnlockedWith(address) {<!-- -->
                               UTXOs = append(UTXOs, out)
                       }
               }
       }

       return UTXOs
}

That’s all! Now let’s implement the getbalance command

func (cli *CLI) getBalance(address string) {<!-- -->
bc := NewBlockchain(address)
defer bc.db.Close()

balance := 0
UTXOs := bc.FindUTXO(address)

for _, out := range UTXOs {<!-- -->
balance += out.Value
}

fmt.Printf("Balance of '%s': %d\\
", address, balance)
}

The account balance is the sum of all unspent transaction outputs locked by the account address.
After mining the genesis block, let’s check our balance:

╰─ ./blockchain_impl_in_go getbalance -address Ivan ─╯
Balance of Ivan: 10

This is our first money!

Send coins

Now, we want to send some coins to other people. To do this, we need to create a new transaction, put it in a block, and then mine the block. Previously we only implemented the coinbase transaction (which is a special kind of transaction), now we need a generic normal transaction.

func NewUTXOTransaction(from, to string, amount int, bc *Blockchain) *Transaction {<!-- -->
var inputs []TXInput
var outputs []TXOutput

acc, validOutputs := bc. FindSpendableOutputs(from, amount)
\t
if acc < amount {<!-- -->
log.Panic("ERROR: Not enough funds")
}

for txid, outs := range validOutputs {<!-- -->
txID, _ := hex. DecodeString(txid)
\t\t
for _, out := range outs {<!-- -->
input := TXInput{<!-- -->txID, out, from}
inputs = append(inputs, input)
}
}
outputs = append(outputs, TXOutput{<!-- -->amount, to})
if acc >amount {<!-- -->
outputs = append(outputs, TXOutput{<!-- -->acc - amount, from})
}
tx := Transaction{<!-- -->nil, inputs, outputs}
tx. SetID()
\t
return & tx
}

Before creating a new output, we must first find all unspent outputs and make sure they have enough value (value), which is what the FindSpendableOutputs method does. Then, for each found output, a reference is created Inputs for this output. Next, we create two outputs:

  1. One is locked by the recipient address. This is the actual transfer of coins to the other address
  2. One is locked by the sender’s address. This is a change. It is only generated when unspent outputs exceed the requirements of the new transaction. Remember: outputs are not subdividable.

The FindSpendableOutputs method is based on the previously defined FindUnspentTransactions method:

func (bc *Blockchain) FindSpendableOutputs(address string, amount int) (int, map[string][]int) {<!-- -->
unspentOutputs := make(map[string][]int)
unspentTXs := bc. FindUnspentTransactions(address)
accumulated := 0
work:
for _, tx := range unspentTXs {<!-- -->
txID := hex.EncodeToString(tx.ID)

for outIdx, out := range tx.Vout {<!-- -->
if out.CanBeUnlockedWith(address) & amp; & amp; accumulated < amount {<!-- -->
accumulated + = out.Value
unspentOutputs[txID] = append(unspentOutputs[txID], outIdx)

if accumulated >= amount {<!-- -->
break work
}
}
}
}
return accumulated, unspent Outputs
}

This method iterates over all unspent transactions and accumulates its value. When the accumulated value is greater than or equal to the value we want to send, it stops and returns the accumulated value, along with the transaction ID The output index of the group. We only need to withdraw enough money to pay.
Now we can modify the Blockchain.MineBlock method

func (bc *Blockchain) MineBlock(transactions []*Transaction) {<!-- -->
var lastHash[]byte

_ = bc.db.View(func(tx *bolt.Tx) error {<!-- -->
b := tx.Bucket([]byte(blocksBucket))
lastHash = b. Get([]byte("l"))

return nil
})

newBlock := NewBlock(transactions, lastHash)

_ = bc.db.Update(func(tx *bolt.Tx) error {<!-- -->
b := tx.Bucket([]byte(blocksBucket))
_ = b.Put(newBlock.Hash, newBlock.Serialize())
_ = b.Put([]byte("l"), newBlock.Hash)
bc.tip = newBlock.Hash

return nil
})
}

Finally, let’s implement the send method:

func (cli *CLI) send(from, to string, amount int) {<!-- -->
bc := NewBlockchain(from)
defer bc.db.Close()

tx := NewUTXOTransaction(from, to, amount, bc)
bc.MineBlock([]*Transaction{<!-- -->tx})
fmt.Println("Success!")
}

Sending coins means creating new transactions and packing them into the blockchain by mining new blocks. But Bitcoin doesn’t do this all at once (although our current implementation does). Instead, it puts all new transactions into a memory pool (mempool), and then when the miner is ready to dig a new block, it takes all transactions from the mempool and creates a candidate block. Only when the miner contains these transactions After the block is dug out and added to the blockchain, the transactions in it are confirmed.
Let’s check that sending coins works:

$ blockchain_go send -from Ivan -to Pedro -amount 6
000000655594c9b0c6c1034ec0236d91d2115bbd74ed008901ea81c29f231d7f

Success!

╰─ ./blockchain_impl_in_go getbalance -address Ivan ─╯
Balance of Ivan: 4

╰─ ./blockchain_impl_in_go getbalance -address Pedro ─╯
Balance of Pedro: 6

Great! Now, let’s create some more transactions to make sure sending coins from multiple outputs works as well:

╰─ ./blockchain_impl_in_go send -from Pedro -to Helen -amount 2 ─╯
0000003d3c12819d42b9c9a2968a803b651a775af1af262d51384d6c2577f8e1

Success!

╰─ ./blockchain_impl_in_go send -from Ivan -to Helen -amount 2 ─╯
00000050e41ef1982c2aab6ad43d748b7f65c720a34a6fb9f144960d911e4711

Success!

Now, Helen’s coins are locked in two outputs: one from Pedro and one from Lvan. Let’s send them to others:

╰─ ./blockchain_impl_in_go send -from Helen -to Rachel -amount 3 ─╯
000000417eabcad236c9d42c5c33d72c5e63a293c2b5491390f362d1d3fcdb89

Success!

$ blockchain_go getbalance -address Ivan
Balance of 'Ivan': 2

$ blockchain_go getbalance -address Pedro
Balance of 'Pedro': 4

$ blockchain_go getbalance -address Helen
Balance of 'Helen': 1

$ blockchain_go getbalance -address Rachel
Balance of 'Rachel': 3

Looks OK! Now, to test some failure cases:

$ blockchain_go send -from Pedro -to Ivan -amount 5
panic: ERROR: Not enough funds

$ blockchain_go getbalance -address Pedro
Balance of 'Pedro': 4

$ blockchain_go getbalance -address Ivan
Balance of 'Ivan': 2

Summary

It wasn’t easy, but transactions are now finally possible! However, we are still missing some key features like Bitcoin:

  1. Address. We don’t have a real address based on a private key yet.
  2. Reward. It is definitely not profitable when mining now!
  3. UTXO set. Obtaining the balance needs to scan the entire blockchain, and when there are many blocks, it will take a long time to do so. Also, if we want to verify subsequent transactions, it will also take a long time. The UTXO set is for Solve these problems and speed up trading-related operations.
  4. Mempool. Before transactions are packaged into blocks, these transactions are stored in the mempool. In our current implementation, a block contains only one transaction, which is quite inefficient.

link

Full source codes
transaction
Merkle tree
Coinbase