MONOKH

نخبه break things
Github @monokh Twitter @mo_nokh

Bitcoin From Scratch - Part 2 - The Node

In the previous part, we covered the different data structures involved in Bitcoin: Keys, Transactions, Blocks and how they come together in the mining process.

In this part, we will go over how all of these pieces come together to produce a bitcoin "node". In the end, we have a node that we can interact with via the CLI. Skip to the demo.

The intention is not to create a real implementation of the Bitcoin protocol. The purpose is to demonstrate the concepts in a simple way. Watch for notes when there are significant discrepancies.

The code until this part of the series is available here: https://github.com/monokh/nibble/tree/52172a38bd54fe599c1cef4890c6dc772956bb2d

Node

A bitcoin node is a piece of software that runs as part of the bitcoin network. It is an implementation of the bitcoin protocol. As well as being able to mine, the node also has a copy of the "blockchain". It validates blocks and asserts that they follow the rules. These rules are otherwise known as "consensus rules".

pub struct Node {
    pub blocks: Vec, // Blockchain
    pub balances: HashMap,
    pub mempool: Vec,
    pub keypair: crypto::KeyPair,
}

The blockchain

In the previous section, we demonstrated how mining a block happens but we didn't explain how blocks relate to each other. In reality they are not separate entities. Each block actually refers to the block that came before it.

+------------------------------+       +------------------------------+       +------------------------------+
|        BLOCK 0 (HASH)        +<--+   |        BLOCK 1 (HASH)        +<--+   |        PENDING BLOCK         |
+------------------------------+   |   +------------------------------+   |   +------------------------------+
|                              |   |   |                              |   |   |                              |
|  +-----------+ +----------+  |   |   |  +-----------+ +----------+  |   |   |  +-----------+ +----------+  |
|  | PREV HASH | |  NONCE   |  |   +------+ PREV HASH | |  NONCE   |  |   +------+ PREV HASH | |   ....   |  |
|  +-----------+ +----------+  |       |  +-----------+ +----------+  |       |  +-----------+ +----------+  |
|  +------+ +------+ +------+  |       |  +------+ +------+ +------+  |       |  +------+ +------+ +------+  |
|  |  TX  | |  TX  | |  TX  |  |       |  |  TX  | |  TX  | |  TX  |  |       |  |  TX  | |  TX  | |  TX  |  |
|  +------+ +------+ +------+  |       |  +------+ +------+ +------+  |       |  +------+ +------+ +------+  |
|                              |       |                              |       |                              |
+------------------------------+       +------------------------------+       +------------------------------+

The diagram illustrates that each block refers to the hash of the block before it, thereby creating a "chain" of blocks. All together this is called the "blockchain".

This is very simple to add to our block structure.

pub struct Block {
    pub hash: String,
+   pub prev_block: String,
    pub nonce: u32,
    pub transactions: Vec,
}

This mechanism exists for 2 reasons:

You might now be wondering, if we follow the chain all the way back, where do we get to? When was the beginning of bitcoin time?

The Genesis Block

Block 0 is special. It does not have a block preceding it.

static GENESIS_PREV_BLOCK_HASH: &str = "000000000000000000000000000000000000000000000000000000000000000";
fn make_genesis_block (&self) -> block::ProposedBlock {
    return block::ProposedBlock {
        prev_block: String::from(GENESIS_PREV_BLOCK_HASH),
        transactions: vec![...]
    };
}

For the network to begin, someone has to mine this block.

pub fn start (&mut self) -> Result {
    let genesis_block = self.make_genesis_block().mine(DIFFICULTY);
    self.process_block(&genesis_block)?;
    return Ok(genesis_block);
}

From then onwards, transactions can be sent to the network and eventually mined.

Mempool

The node keeps track of transactions that are awaiting inclusion into a block. This area of the node is referred to as the "mempool".

When a transaction is received by the node, it is added to the mempool.

pub fn send_transaction (&mut self, public_key: key::PublicKey, amount: u32) -> ... {
    let tx = tx::create_signed(&self.keypair, public_key, amount);
    self.verify_reg_tx(&tx)?;
    self.mempool.push(tx.clone());
    return Ok(tx);
}

The mempool is actually a beast of it's own. In the real world, there are more transactions than there is space in a block. As such, transactions are also able to specify a fee that goes to the miner of the block, thereby competing for their inclusion. You transaction could stay in the mempool, unattended for several days.

When the node is ready to mine, it adds the transactions in the mempool to a fresh block and begins mining it. Here you can also see us using the previous block's hash as part of the new block in order to continue the chain.

let mut txs = vec![...];
txs.extend(self.mempool.clone());
let prev_block = self.blocks.last().expect("Previous block does not exist");
let proposed_block = block::ProposedBlock {
    prev_block: prev_block.hash.clone(),
    transactions: txs,
};
let block = proposed_block.mine(DIFFICULTY);
self.process_block(&block)?;

When we have successfully mined the block, we process its contents as to update the state of the node.

fn process_block(&mut self, block: &block::Block) -> Result<(), &'static str> {
    self.verify_block(&block)?;
    self.process_block_transactions(&block);
    self.blocks.push(block.clone());
    return Ok(());
}

We compute the new balance of each public key and store it in balances. The "coinbase" transaction will be explained later.

fn process_block_transactions(&mut self, block: &block::Block) {
    for (i, tx) in block.transactions.iter().enumerate() {
        // Coinbase (first tx in block) is allowed to create new supply (by not deducting a balance)
        if i > 0 { *self.balances.get_mut(&tx.transaction.from).unwrap() -= tx.transaction.amount } // Deduct balance
        *self.balances.entry(tx.transaction.to).or_insert(0) += tx.transaction.amount; // Add balance
    }
}

Our balance mechanism is simplistic. In reality Bitcoin doesn't really have the concept of a singular balance. Transactions are a combination of inputs and outputs. Outputs that have yet to become an input are considered "Unspent" and consist part of your balance. Unspent transaction outputs

Notice when we process the block, we also verify the block.

Consensus Rules

The consensus rules are a set of rules that the node will enforce for blocks and transactions before it considers them valid.

Block verification

First we ensure that the block has the correct PoW (0s at the start of the hash) attached to the block hash.

if !block.hash.starts_with(&"0".repeat(DIFFICULTY)) { return Err("Block verification: Must contain correct PoW according to difficulty") }

Next we must ensure that the block's hash is in fact the hash of it's contents. This mainly ensures that we don't receive a block with a proof of work that was manufactured without work.

let block_hash = crypto::sha256(block.serialize());
if hex::encode(block_hash) != block.hash { return Err("Block verification: Hash must match hash included in block") }

We also ensure that the new block points to the last known block.

let prev_block = self.blocks.last();
let prev_block_hash = prev_block.map_or(GENESIS_PREV_BLOCK_HASH, |b| b.hash.as_str());
if block.prev_block != prev_block_hash { return Err("Block verification: Must reference previous block's hash") }

Blocks that extend an older blocks are also kept by the node. This is incase they eventually become the longer chain. This also means that transactions included in a block cannot be believed to be absolutely final, only that it becomes exponentially less likely to be reversed as more blocks are added onto the chain succeeding it.

Transaction verification

It should not be possible to spend an amount of coin that you don't hold. There are 2 aspects to this:

Signature validation:

You shouldn't be able to spend from a key that you do not have they private key for. The private key is used to produce the signature of the transaction so this should be verified:

if !tx.is_sig_valid() { return Err("Transaction verification: Invalid signature") }

Remember that the signature was produced by taking the hash of the transaction fields and signing with the private key. To verify: We take the hash of the transaction and verify using the public key.

pub fn is_sig_valid(& self) -> bool {
    ...
    return secp.verify(&unsigned_tx_hash, &sig, &self.transaction.from).is_ok();
}

Balance validation:

A transaction cannot spend more than the user has balance. We can use our balance index to perform this check.

let from_balance = self.balances.get(&tx.transaction.from);
if *from_balance.unwrap_or(&0) < tx.transaction.amount { return Err("Transaction verification: Not enough balance") }    

There are many more consensus rules that are required for a robust network. See protocol rules.

There is one scenario where the balance of the user is not considered, effectively creating new bitcoin.

Coin Issuance: The coinbase transaction

The protocol needs to incentivize work in the form of mining. To address this, the miner is allowed to include a transaction to itself with a specific amount of bitcoin (the block reward) without deducting it elsewhere. Essentially creating new coins.

fn create_coinbase_tx (&self) -> tx::SignedTransaction {
    let reward = self.get_block_reward(self.blocks.len());
    return tx::create_signed(&self.keypair, self.keypair.public_key, reward)
}

This transaction which must be included as the first transaction in the block is also verified by the protocol:

if tx.transaction.amount != self.get_block_reward(block_number) { return Err("Transaction verification: Coinbase amount not valid") }

Notice the block reward is dependant on the block number. The block reward will half every X amount of blocks, thereby making bitcoin scarcer over time.

fn get_block_reward (&self, block_number: usize) -> u32 {
    let halving = block_number / 1000;
    if halving >= 10 { return 0 }
    return 512 >> halving;
}

Bitcoin's halving schedule is every 210,000 blocks (about 4 years) and ends after 64 halvings.

Node CLI

A simple cli has been added to allow you to play with the function of the node.

USAGE:
    nibble [SUBCOMMAND]

FLAGS:
    -h, --help       Prints help information
    -V, --version    Prints version information

SUBCOMMANDS:
    balances     Returns balances for each pubkey known by the node
    help         Prints this message or the help of the given subcommand(s)
    mempool      Returns the transactions in the mempool
    mine         Mine a block
    newpubkey    Generate a random pubkey
    send         Amount to send

On start, it mines the genesis block thereby giving you a block's worth of coins.

> balances
{
    03055079d897f5ee5f4e0f01b4cf6e0acd704f1a3a914c18f49b2eb4566693180a: 512
}

Get a few public keys to use as a receiver.

> newpubkey
037570f891ae18e39fb9b0cf0e5d39ec34d94c4e79d2c3f54707bbd3b53531229a

Send 5 coins to this pubkey.

> send 037570f891ae18e39fb9b0cf0e5d39ec34d94c4e79d2c3f54707bbd3b53531229a 5
SignedTransaction {
    transaction: Transaction {
        from: "03055079d897f5ee5f4e0f01b4cf6e0acd704f1a3a914c18f49b2eb4566693180a",
        to: "037570f891ae18e39fb9b0cf0e5d39ec34d94c4e79d2c3f54707bbd3b53531229a",
        amount: 5,
    },
    sig: "304402207a6d4c7d2ce62ae2bd743afd03cb486a9cdaea64e13fb54081055f237474a96702206b37aa28459a4dda07f3cbc4c799abfd71e6a156f4c9b9f67509d6bba21c3b1e",
}

You can see that the mempool includes this transaction using the mempool command.

Mine a block:

> mine
Block {
    hash: "00006ca9037bb5311b037e9c3748e65fcdea6c0047a0c0880667a445d53c6373",
    prev_block: "000a47df8b254225dfc5d39d776d40cd74d6c3f6fddb5915dbc35a4cfb6b2e25",
    nonce: 7435,
    transactions: [
        ...
    ],
}

See the latest balances, you should have a received another block reward and the receiver pubkey should be credit:

{
    03055079d897f5ee5f4e0f01b4cf6e0acd704f1a3a914c18f49b2eb4566693180a: 1019
    037570f891ae18e39fb9b0cf0e5d39ec34d94c4e79d2c3f54707bbd3b53531229a: 5
}

Network Consensus

Now if we run 2 of our nodes, they will create the same genesis and come up with entirely different blocks. This means they are not in "consensus". They don't have the same view of the world. This problem is described as the "Byzantine Generals Problem" where in a distributed network, nodes must be able to continue operating even if they are not always cooperating. We create a network and solve the consensus problem in the next part.