March 21, 2018 at 22:12

Blockchain on Go. Part 4: Transactions, Part 1

Hi Habr! I present to you the translation of the article " Building Blockchain in Go. Part 4: Transactions 1 ".

Content

  1. Blockchain on Go. Part 1: Prototype
  2. Blockchain on Go. Part 2: Proof-of-Work
  3. Blockchain on Go. Part 3: read-only memory and command line interface
  4. Blockchain on Go. Part 4: Transactions, Part 1
  5. Blockchain on Go. Part 5: Addresses
  6. Blockchain on Go. Part 6: Transactions, Part 2
  7. Blockchain on Go. Part 7: Network

Introduction


Transactions are the heart of Bitcoin, and the only purpose of the blockchain is to store transactions in a safe and reliable way so that no one can modify them after they are created. In this article, we begin work on the implementation of a transaction mechanism. But since this is a rather large topic, I divided it into two parts: in this part we implement the general mechanism, and in the second part we will analyze in detail the rest of the functionality.

In this article we will be almost completely edit all of our previous code, so it makes no sense to describe every change, all the changes you can see here .

No spoon


Если Вы когда-то разрабатывали веб-приложение, то для реализации платежей, вероятно, создавали в базе данных две эти таблицы: учетные записи и транзакции. Учетная запись хранила информацию о пользователе, включая его персональную информацию и баланс, а транзакция хранит информацию о переводе денег с одной учетной записи на другую. В Биткоине платежи осуществляются совершенно по-другому:

  1. Нет аккаунтов.
  2. Нет балансов.
  3. Нет адресов.
  4. Нет монет.
  5. Нет отправителей и получателей.

Поскольку блокчейн является публичной и открытой базой данных, мы не хотим хранить конфиденциальную информацию о владельцах кошельков. Монеты не хранятся на счетах. Транзакции не переводят деньги с одного адреса на другой. Нет полей и атрибутов, которые содержат баланс счета. Есть только транзакции. Но что внутри?

Биткоин транзакция


A transaction is a combination of inputs and outputs:

type Transaction struct {
	ID   []byte
	Vin  []TXInput
	Vout []TXOutput
}

The inputs of the new transaction refer to the outputs of the previous transaction (there is an exception, which we will discuss below). Exits - a place where coins are stored. The following diagram illustrates the relationship of transactions:



Note:

  1. There are outputs that are not connected to inputs.
  2. In one transaction, inputs can refer to the outputs of several transactions.
  3. An input must always reference an output.

In this article we will use the words “money”, “coins”, “spend”, “send”, “account”, etc. But there are no such concepts in Bitcoin. Transactions are simply a value locked by a script that can only be unlocked by the one who blocked it.

Transaction outputs


Let's start with the exits:

type TXOutput struct {
	Value        int
	ScriptPubKey string
}

In fact, these are the outputs that store “coins” (note the box Valueabove). Funds are blocked by a special puzzle, which is stored in ScriptPubKey. Inside, Bitcoin uses a scripting language Scriptthat is used to determine the logic for locking and unlocking outputs. The language is quite primitive (this is done intentionally to avoid possible hacks), but we will not discuss it in detail. You can read more about him here .
In Bitcoin, the value field stores the number of Satoshi, not the number of BTC. 1 Satoshi = 0.00000001 BTC. Thus, this is the smallest unit of currency in Bitcoin (as, for example, a cent).
Since we do not have addresses, for now we will avoid all scripting logic. To begin with, it ScriptPubKeywill store an arbitrary string (user wallet address).
By the way, the presence of such a scripting language means that Bitcoin can be used as a platform of smart contracts.
One important thing to know about exits is that they are indivisible , which means that you cannot refer to part of your meaning. When an exit refers to a new transaction, it is fully consumed. And if its value is greater than required, a difference is generated and a new value is sent back to the sender. This is similar to the real situation in the world when you pay, say, $ 5 dollars for what it costs $ 1, and get a change of $ 4.

Transaction Inputs


Consider the input:

type TXInput struct {
	Txid      []byte
	Vout      int
	ScriptSig string
}

As mentioned earlier, the entry refers to the previous exit: it Txidstores the identifier of such a transaction, and Voutstores the exit index of this transaction. ScriptSig- This is a script that provides data that will be further used in the script ScriptPubKey. If the data is correct, the output can be unlocked, and its value can be used to generate new outputs; if it is not, the input cannot refer to the output. This mechanism ensures that users cannot spend coins belonging to other people.

Again, since we still do not have addresses, ScriptSigonly an arbitrary user wallet address will be saved. We will create the public key and signature verification in the next article.

Summarize. Exits - this is the place where "coins" are stored. Each output has an unlock script that defines the logic to unlock the output. Each new transaction must have at least one entry and exit. An input refers to the result of a previous transaction and provides the data (field ScriptSig) that is used in the script to unlock the output to unlock it and use its value to create new outputs.

But what came first: inputs or outputs?

Egg


In Bitcoin, an egg appeared before the chicken. The logic inputs-referencing-outputs is a classic “chicken or egg” situation: inputs produce outputs, and outputs allow you to create inputs. And in Bitcoin, exits always appear in front of entrances.

When a miner begins to mine a block, he adds a coinbase transaction to it . A coinbase transaction is a special type of transaction that does not require pre-existing exits. It creates exits (ie, "Coins") from nowhere. An egg without chicken. This is a reward that miners get for mining new blocks.

As you know, at the beginning of the chain there is a block of genesis. It is this block that generates the very first output in the block chain. And no previous exits are required, as there are no previous transactions and there are no exits.

Let's 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
}

There is only one entry in a coinbase transaction. In our implementation, it is Txidempty, but Vout-1. Also, the coinbase transaction does not store the script in ScriptSig. Instead, arbitrary data is stored there.
In Bitcoin, the very first coinbase transaction contains the following message: “The Times 03 / Jan / 2009 Chancellor on brink of second bailout for banks”. You yourself can look at it .
subsidyIs the amount of the reward. In Bitcoin, this number is not stored anywhere and is calculated only on the basis of the total number of blocks: the number of blocks is divided by 210,000 . Mining the genesis block brings 50 BTC, and every 210,000 blocks the reward is halved. In our implementation, we will store the reward as a constant (at least for now).

Saving transactions in a chain


From now on, each block must store at least one transaction, and it should become impossible to mine blocks without a transaction. Now, we will remove the date field from Block and instead we will now store transactions.

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

NewBlockand NewGenesisBlockmust also be modified accordingly

func NewBlock(transactions []*Transaction, prevBlockHash []byte) *Block {
	block := &Block{time.Now().Unix(), transactions, prevBlockHash, []byte{}, 0}
	...
}
func NewGenesisBlock(coinbase *Transaction) *Block {
	return NewBlock([]*Transaction{coinbase}, []byte{})
}

Now create a function CreateBlockchain

func CreateBlockchain(address string) *Blockchain {
	...
	err = db.Update(func(tx *bolt.Tx) error {
		cbtx := NewCoinbaseTX(address, genesisCoinbaseData)
		genesis := NewGenesisBlock(cbtx)
		b, err := tx.CreateBucket([]byte(blocksBucket))
		err = b.Put(genesis.Hash, genesis.Serialize())
		...
	})
	...
}

Now the function accepts an address that will receive a reward for the extraction of the genesis block.

Proof of work


The Proof-of-Work algorithm should consider transactions stored in a block to ensure consistency and reliability of the chain as a transaction repository. So now we have to change the method ProofOfWork.prepareData:

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, pow.block.Datawe will now add 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[:]
}

Again, we use hashing as a mechanism to provide a unique representation of the data. We want all transactions in the block to be uniquely identified with a single hash. To achieve this, we get the hashes of each transaction, combine them and get the hash of the combined combinations.
Bitcoin uses a more complex technique: it represents all the transactions contained in the block as a hash tree , and uses the root hash of the tree in the Proof-of-Work system. This approach allows you to quickly check whether a block contains a specific transaction that has only a root hash and without loading all transactions.
Check the correct operation:

$ blockchain_go createblockchain -address Ivan
00000093450837f8b52b78c25f8163bb6137caf43ff4d9a01d1b731fa8ddcc8a
Done!

Excellent! We received our first award. But how do we check the balance?

Unspent Exits


We need to find all the unspent outputs (UTXO). This means that these outputs did not refer to any inputs. In the above diagram, this is:

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

Of course, when we check the balance, we don’t need all of them, we only need those that can be unlocked with the key that we own (currently we do not have keys implemented and user addresses will be used instead). To get started, let's define lock-unlock methods on inputs and outputs:

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 fields from ScriptSigc unlockingData. In the next article, we will improve them after we implement addresses based on private keys.

The next step - finding transactions with unspent outputs - this is already more complicated:

func (bc *Blockchain) FindUnspentTransactions(address string) []Transaction {
  var unspentTXs []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 {
        // Was the output spent?
        if spentTXOs[txID] != nil {
          for _, spentOut := range spentTXOs[txID] {
            if spentOut == outIdx {
              continue Outputs
            }
          }
        }
        if out.CanBeUnlockedWith(address) {
          unspentTXs = append(unspentTXs, *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 unspentTXs
}

Since transactions are stored in blocks, we must check every block in the chain. Let's start with the exits:

if out.CanBeUnlockedWith(address) {
	unspentTXs = append(unspentTXs, tx)
}


If the exit was blocked at the same address, we look for the unspent exits that we want. But before accepting it, we need to check whether the input has already been specified on the output:

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

We skip the ones that are already referenced by the inputs (their values ​​have been transferred to other outputs, so we cannot calculate them). After checking the outputs, we collect all the inputs that can unlock the outputs blocked with the provided address (this does not apply to coinbase transactions, since they do not unlock the 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)
        }
    }
}

The function returns a list of transactions containing unspent outputs. To calculate the balance, we need another function that takes transactions and returns only outputs:

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
}

Done! Now we implement the commandgetbalance

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\n", address, balance)
}

Account balance is the sum of the values ​​of all unspent outputs blocked by the account address.

Let's check our balance after mining the genesis block:

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

These are our first coins!

Sending coins


Now we want to send some coins to someone else. To do this, we need to create a new transaction, put it in a block and process it. So far, we have implemented only the coinbase transaction (which is a special type of transaction), now we need a general transaction:

func NewUTXOTransaction(from, to string, amount int, bc *Blockchain) *Transaction {
	var inputs []TXInput
	var outputs []TXOutput
	acc, validOutputs := bc.FindSpendableOutputs(from, amount)
	if acc < amount {
		log.Panic("ERROR: Not enough funds")
	}
	// Build a list of inputs
	for txid, outs := range validOutputs {
		txID, err := hex.DecodeString(txid)
		for _, out := range outs {
			input := TXInput{txID, out, from}
			inputs = append(inputs, input)
		}
	}
	// Build a list of outputs
	outputs = append(outputs, TXOutput{amount, to})
	if acc > amount {
		outputs = append(outputs, TXOutput{acc - amount, from}) // a change
	}
	tx := Transaction{nil, inputs, outputs}
	tx.SetID()
	return &tx
}

Before creating new exits, we first need to find all the unspent exits and make sure that they have enough coins. This is the method FindSpendableOutputs. After that, for each output found, an input is created that refers to it. Then we create two outputs:

  1. One that is blocked with the recipient address. This is the actual transfer of coins to another address.
  2. One that is blocked with the sender address. That is the difference. It is created only when unspent outputs are more important than is required for a new transaction. Remember: outputs are indivisible .

The method is FindSpendableOutputsbased on the method FindUnspentTransactionsthat we defined earlier:

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) && accumulated < amount {
				accumulated += out.Value
				unspentOutputs[txID] = append(unspentOutputs[txID], outIdx)
				if accumulated >= amount {
					break Work
				}
			}
		}
	}
	return accumulated, unspentOutputs
}

The method traverses all unspent transactions and accumulates their values. When the accumulated value is greater than or equal to the amount we want to transfer, the crawl stops and returns the accumulated values ​​and output indices, grouped by transaction IDs. We do not need to take more than we are going to spend.

Now we can change the method Blockchain.MineBlock:

func (bc *Blockchain) MineBlock(transactions []*Transaction) {
	...
	newBlock := NewBlock(transactions, lastHash)
	...
}

Finally, create the command send:

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 a transaction and adding it to the block chain through block mining. But Bitcoin does not do it right away (like us). Instead, it places all new transactions in the memory pool (or mempool), and when the miner is ready to mine a block, it takes all transactions from mempool and creates a candidate block. Transactions become confirmed only when the block containing them is mined and added to the block chain.

Let's check how coin sending works:

$ blockchain_go send -from Ivan -to Pedro -amount 6
00000001b56d60f86f72ab2a59fadb197d767b97d4873732be505e0a65cc1e37
Success!
$ blockchain_go getbalance -address Ivan
Balance of 'Ivan': 4
$ blockchain_go getbalance -address Pedro
Balance of 'Pedro': 6

Excellent! Now let's create more transactions and make sure sending from multiple outputs works correctly:

$ blockchain_go send -from Pedro -to Helen -amount 2
00000099938725eb2c7730844b3cd40209d46bce2c2af9d87c2b7611fe9d5bdf
Success!
$ blockchain_go send -from Ivan -to Helen -amount 2
000000a2edf94334b1d94f98d22d7e4c973261660397dc7340464f7959a7a9aa
Success!

Now Helen's coins are blocked at two exits: one exit from Pedro and one from Ivan. Send to someone else:

$ blockchain_go send -from Helen -to Rachel -amount 3
000000c58136cffa669e767b8f881d16e2ede3974d71df43058baaf8c069f1a0
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 nice! Now let's test the exceptions:

$ 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

Conclusion


Phew! It was not easy, but now we have transactions! Although, some key features of the Bitcoin-like cryptocurrency are missing:

  1. Addresses So far we have no addresses based on the private key.
  2. Awards. Mining blocks is absolutely unprofitable!
  3. Utxo. Getting balance requires scanning the entire chain of blocks, which can take a very long time when there are so many blocks. In addition, it will take a very long time if we want to confirm subsequent transactions. UTXO is designed to solve these problems and to quickly work with transactions.
  4. Mempool Transactions are stored here before they are packaged in a block. In our current implementation, a block contains only one transaction, and this is very inefficient.

References


  1. Full source codes
  2. Transaction
  3. Merkle tree
  4. Coinbase
Tags:

Also popular now: