A guide to building a blockchain & cryptocurrency from scratch in Ruby

The blockchain

So let’s build a chain of blocks!

blocks = []

height = 0
loop do
  height += 1

  blocks << {
    height: height,
    last_block: height - 1,
    transactions: transactions_for_this_block,
  }
end
lang-ruby

Making the blockchain unalterable

• An input always returns the same hash
• Different messages can’t have the same hash
• You can’t use the hash to know anything about its input (ideal for privacy)
• The input can’t be formatted in a way that will lead to a specific output (we’ll use this for mining)

require "digest"

blocks = []

height = 0
loop do
  height += 1

  block = {
    height: height,
    # We're now using the last block's hash instead of its height.
    last_block: blocks.last&.hash,
    transactions: transactions_for_this_block,
  }

  block["hash"] = Digest::SHA256.hexdigest(block.to_json)

  blocks << block
end
lang-ruby

Agreeing on a single blockchain with Proof of Work

require "digest"

blocks = []

height = 0
loop do
  height += 1

  block = {
    height: height,
    # We're now using the last block's hash instead of its height.
    last_block: blocks.last&.hash,
    transactions: transactions_for_this_block,
  }

  # We'll loop until we find a hash that starts with four '0'.
  loop do
    # At each iteration, we're increase the nonce by one. This
    # will change the hash and give us another change at finding
    # the right block hash.
    block["nonce"] = block["nonce"].to_i + 1
    block["hash"] = Digest::SHA256.hexdigest(block.reject { |k| k == "hash" }.to_json)

    if block["hash"][0, 4] == "0000"
      # We found a block that passes the challenge!
      break
    end
  end

  blocks << block
end
lang-ruby

Putting it together in a small application

Transactions

Adding text transactions to the blocks

Understanding the use-case for Merkle trees

• Nodes that keep the entire transaction history: Every transaction that ever happened would need to be stored if we ever want to recompute the block hash successfully. As the blockchain grows, this might not be sustainable. Having a way to prune older transaction data that no longer matters would help partially fix this problem.
• Validating a recent transaction means downloading the entire block: Again, without all the transactions, it’s impossible to get the block hash and, therefore, to validate the data. For less powerful devices or where bandwidth is at a premium, this could be a problem depending on the size of blocks. Figuring out a solution would enable Simplified Payment Verification as described in the original Bitcoin whitepaper, where a node only keeps track of headers and validate transactions individually. This approach isn’t as safe as running a full node but is a good compromise, for example for mobile payments.

To get to the Merkle root (which is our equivalent of the hash containing all transactions), we start at the bottom: Every transaction is grouped by pair. After each transaction is hashed, pairs are hashed together, forming what is called a leaf. For example HAB = Hash(HA + HB). Leaves are then hashed together until we reach a final hash which is our Merkle root.

With a Merkle tree, we need less information to confirm a transaction is part of a block. With a naïve hash, we would need all of them, but now, we can work with a lot less data. Again an example from the Bitcoin Book:

If we’re trying to validate that transaction K is part of the block, using Transaction K and the hash of transaction L (HL), we can build a leaf and find HKL. We now need only 3 other hashes (HABCDEFGH, HIJ and HMNOP) to arrive back at the Root. That’s a lot less information! Consider as an example that Bitcoin blocks hold more than 2,000 transactions, and you can see the impact of this approach.

Implementing a Merkle tree

require "digest"
require "merkle_tree"

blocks = []

height = 0
loop do
  height += 1

  # We'll see later on to get those transactions. For now,
  # let's assume this method returns an array.
  transactions = fetch_transactions

  block = {
    height: height,
    # We're now using the last block's hash instead of its height.
    last_block: blocks.last&.hash,
    transactions: transactions,
    merkle_root: MerkleTree.new(*transactions).root.value,
  }

  # We'll loop until we find a hash that starts with four '0'.
  loop do
    # At each iteration, we're increase the nonce by one. This
    # will change the hash and give us another change at finding
    # the right block hash.
    block["nonce"] = block["nonce"].to_i + 1

    # The block header hash includes transactions indirectly through the Merkle
    # root. Thanks to the properties of hashes, it offers the same level of safety
    # while being more practical for users of the blockchain.
    block_header = block["nonce"] + block["last_block"] + block["merkle_root"]
    block["hash"] = Digest::SHA256.hexdigest(block_header)

    if block["hash"][0, 4] == "0000"
      # We found a block that passes the challenge!
      break
    end
  end

  blocks << block
end
lang-ruby

Wallets and signing transactions

• The public key can be obtained from the private key, but the reverse isn’t true. This means you can safely share your public key without revealing your private key.
• Your private key can sign messages. Anyone can then verify that the signature matches a public key. Without the private key associated with the public key, it’s impossible to sign the message.
• When done correctly, just as with hashes, private and public keys are unique. If you generate a new private key, nobody else is going to have the same.

require "ecdsa"
require "securerandom"

# 1. We generate a private key.
group = ECDSA::Group::Secp256k1
private_key = 1 + SecureRandom.random_number(group.order - 1)
# 2. The public key is obtained from the private key.
public_key_coordinates = group.generator.multiply_by_scalar(private_key)
public_key = ECDSA::Format::PointOctetString.encode(public_key_coordinates)

message = {
  # The sender's public key is encoded in B
  from: Base58.binary_to_base58(public_key),
  # The destination is the SHA256 of the public key.
  destination: "27a84712e4b22c415fc544d55cdee82327a829f96d03329457f76ebf9af4dcaa",
  amount: "1.2119"
}

# 3. We create the signature so anyone can validate we own the coins being sent.
# We sign the hash of the message instead of the complete message for performance
# reasons.
digest = Digest::SHA2.digest(message.to_json)
signature = nil
temp_key = 1 + SecureRandom.random_number(group.order - 1)
signature = ECDSA.sign(group, private_key, digest, temp_key)
# The signature is encoded as a DER string and then in Base 58.
encoded_signature = ECDSA::Format::SignatureDerString.encode(signature)

# 4. We add a transaction ID.
id = Digest::SHA256.hexdigest(encoded_signature)

# 5. We have a complete transaction!
transaction = {
  id: id,
  signature: encoded_signature,
  message: message,
}
lang-ruby

• It only includes alphanumeric characters, which makes it easy to copy the entire string by double-clicking
• Ambiguous characters (0,o,O,l,i) are avoided

Preventing double-spending:
When users create and sign transactions, they are broadcasted to members of the network. There needs to be a solution to ensure the transactions aren’t executed twice. This responsibility will fall on the miners in our implementation as they will keep track of transaction IDs. A block containing a transaction ID that was already seen in the future would be invalid.
We can see already a scaling problem: Keeping track of all transaction IDs will become expensive over time, and asking miners to keep billions of IDs in memory isn’t practical. An easy fix would be to have an expiration time to the transaction (with a reasonable upper limit at, for example, one week). This way, miners could only store transaction IDs less than a week old and still avoid double-spending. It’s also better for users: They are no ways of canceling transactions actively, so a time limit ensures there isn’t a risk of a transaction being executed six months in the future.

Mining rewards

message = {
  # We add a type to the message. This isn't strictly necessary but we're here to
  # learn! And this will help debug if we need to.
  type: "mining_reward",
  # There's no sender as this is a mining reward.
  from: nil,
  destination: "27a84712e4b22c415fc544d55cdee82327a829f96d03329457f76ebf9af4dcaa",

  # The amount is 1 coin + SUM(fees of all transactions)
  amount: "7.2861"
}
lang-ruby

P2P network: Working with other miners

# From node.rb: https://github.com/antoinefink/melon/blob/master/node.rb

post "/transactions/submit" do
  transaction = JSON.parse(request.body.read)

  if transaction["message"]["type"] != "funds_transfer"
    halt(400, "Transaction has an invalid type")
  end

  # We verify that sender is the actual owner of the coins. This is done by
  # confirming the signature of the message is valid. Only someone with the
  # private key would be able to sign the message of the transaction.
  if @@blockchain.valid_cryptography?(transaction) == false
    halt(400, "Transaction is cryptography is invalid")
  end

  # The miner fetches the amount of coins available to the wallet sending
  # funds and ensures the balance doesn't fall bellow 0.
  if @@blockchain.address_has_enough_funds?(transaction["message"]) == false
    halt(400, "The sender's address doesn't have enough funds")
  end

  # The transaction looks good! We add it to the pending transactions list.
  PendingTransaction.create(transaction)

  $logger.info("Received one pending transaction (#{transaction["id"]})")

  "accepted"
end

# From blockchain.rb: https://github.com/antoinefink/melon/blob/master/blockchain.rb

def valid_cryptography?(transaction)
  # The signature of the message needs to be valid and come from the sender.
  if transaction["id"] != Digest::SHA256.hexdigest(transaction["signature"])
    $logger.warn("Transaction ID isn't the SHA256 of the signature")
    return false
  end

  # The signature should be valid.
  if transaction["message"]["type"] != "mining_reward"
    public_key = ECDSA::Format::PointOctetString.decode(
      Base58.base58_to_binary(transaction["message"]["from"]),
      ECDSA::Group::Secp256k1,
    )

    digest = Digest::SHA256.digest(transaction["message"].sort.to_h.to_json)

    signature = ECDSA::Format::SignatureDerString.decode(
      Base58.base58_to_binary(transaction["signature"])
    )

    if ECDSA.valid_signature?(public_key, digest, signature) == false
      $logger.warn("Transaction signature is invalid")
      return false
    end
  end
end

def address_has_enough_funds?(message_transaction)
  from = Digest::SHA256.hexdigest(message_transaction["from"])
  total = BigDecimal(message_transaction["amount"]) + BigDecimal(message_transaction["fee"])

  address_balance(from) > total
end
lang-ruby

Dealing with currency amounts with BigDecimal
You’ll notice in the “address_has_enough_funds?” methods that we are parsing and comparing amounts using Ruby’s BigDecimal library. If you ever worked with currencies and float, you know why: Currency calculations involving decimals are notoriously imprecise by default. For most calculations, it’s a reasonable tradeoff. If you’re dealing with π, it’s even necessary!
For currencies, we have to be precise. BigDecimal gives us that guarantee.

Receiving and sending new blocks

# Connects to all known peers and requests their highest block. If a block is
# found, we'll do the necessary validations and then alter our local
# blockchain.
def find_higher_blocks_on_the_network
  $logger.info("Looking for higher blocks on the network")

  Array(@peers).each do |peer|
    peer_response = JSON.parse(HTTParty.get("http://#{peer}/blocks/last").body)

    return if peer_response.nil?

    block = Block.initialize_from_json(self, peer_response)

    if block.height > last_block_height.to_i
      $logger.info("Found an higher block: #{block.height} (from #{last_block_height.to_i})")
      validate_and_switch_to_fork(peer, block.height)
    end
  end
end
lang-ruby

Handling forks

Note that this where the term 51% attack comes from: An attacker with more than 50% of the mining power can remove, reorder or add transactions (although he can’t change them as transactions are signed).

# We fetch all the blocks of the fork until we reach a common point.
# The blocks are then gradually validated and applied while we revert at the
# same time the blocks we had created.
def validate_and_switch_to_fork(peer, target_height)
  new_blocks = []

  height = target_height

  loop do
    new_blocks << Block.initialize_from_json(self, JSON.parse(HTTParty.get("http://#{peer}/blocks/#{height}").body))

    # Once we reach the genesis block or a common point, we can stop fetching
    # blocks.
    break if new_blocks.last.height == 0 ||
        new_blocks.last.previous_block_header_hash == find_block_by_height(height)&.previous_block_header_hash

    height += -1
  end

  # We now reverse our local blockchain before we start applying the fork.
  reverse_blocks_and_transactions_until(new_blocks.last.height - 1)

  new_blocks.reverse.each do |block|
    validate_and_apply_block(block)
  end
end

def validate_and_apply_block(block)
  validate(block)
  save_block(block)

  $logger.info("Finished validating and applying block ##{block.height}")
end

# Validates the block by performing verifications in order:
# 2. Height and previous block hash
# 3. Time: Can't be before the previous block.
# 4. Transactions: Wallets should only spend fund they own. Signatures and
#    IDs should be valid.
# 5. There should be exactly one mining reward transaction.
# 6. Merkle tree root: Should be valid.
# 7. Block hash: Is it valid and is the level of difficulty what's expected.
def validate(new_block)
  previous_block = find_block_by_height(new_block.height - 1)

  # 1. Height.
  if previous_block&.height.to_i + 1 != new_block.height.to_i
    raise "Height isn't valid"
  end

  if previous_block.nil? == false
    # 2. Previous block hash
    if previous_block.block_header_hash != new_block.previous_block_header_hash
      raise "Previous block header hash is wrong"
    end

    # 2. Time: Can't be before the previous block.
    if previous_block.time > new_block.time
      raise "New block can't have been created before the previous one"
    end
  end

  # 3. Transactions: Wallets should only spend fund they own.
  new_block.transactions.each do |transaction|
    if WalletTransfer.find(transaction["id"]).nil? == false
      raise "A transaction with the same ID already exists on the blockchain"
    end

    case transaction["message"]["type"]
    when "funds_transfer"
      if valid_cryptography?(transaction) == false
        raise "Cryptography of the transaction is invalid"
      end

      # The amount + fee needs to be available to the wallet.
      if address_has_enough_funds?(transaction["message"]) == false
        raise "From address doesn't have enough funds"
      end

    when "mining_reward"
      fees = new_block.transactions.reject { |t| t["message"]["type"] == "mining_reward" }
        .map { |t| BigDecimal(t["message"]["fee"]) }
        .reduce(&:+) || BigDecimal(0)

      mining_reward = BigDecimal(transaction["message"]["amount"])
      if mining_reward != fees + 1
        raise "Mining reward amount is invalid (#{mining_reward.to_s("F")})"
      end
    end
  end

  # 4. There should be exactly one mining reward transaction.
  mining_rewards = new_block.transactions.reject { |t| t["message"]["type"] != "mining_reward" }
  if mining_rewards.size != 1
    raise "Unexpected amount of mining rewards"
  end

  # 5. Merkle tree root: Should be valid.
  merkle_root = MerkleTree.new(*new_block.transactions.map(&:to_json).sort { |a, b| a["id"] <=> b["id"] }).root.value
  if new_block.merkle_root != merkle_root
    raise "Merkle root is invalid"
  end

  # 6. Block hash: Is it valid and is the level of difficulty what's expected.
  if new_block.compute_block_header_hash != new_block.block_header_hash
    raise "Block header hash is invalid"
  end

  if new_block.block_header_hash[0, DIFFICULTY_LEVEL] != "0" * DIFFICULTY_LEVEL
    raise "Block doesn't match expected difficulty level"
  end
end

# Validate all the cryptographical components of the transactions.
# Therefore it doesn't include ensuring the wallet has the required funds to
# make the transaction.
def valid_cryptography?(transaction)
  # The signature of the message needs to be valid and come from the sender.
  if transaction["id"] != Digest::SHA256.hexdigest(transaction["signature"])
    $logger.warn("Transaction ID isn't the SHA256 of the signature")
    return false
  end

  # The signature should be valid.
  if transaction["message"]["type"] != "mining_reward"
    public_key = ECDSA::Format::PointOctetString.decode(
      Base58.base58_to_binary(transaction["message"]["from"]),
      ECDSA::Group::Secp256k1,
    )

    digest = Digest::SHA256.digest(transaction["message"].sort.to_h.to_json)

    signature = ECDSA::Format::SignatureDerString.decode(
      Base58.base58_to_binary(transaction["signature"])
    )

    if ECDSA.valid_signature?(public_key, digest, signature) == false
      $logger.warn("Transaction signature is invalid")
      return false
    end
  end
end
lang-ruby

Conclusion

• Mining difficulty is static: It should be adjusted based on the computing power of all miners combined.
• Proof of Stake could be better than Proof of Work: As Bitcoin uses Proof of Stake and it’s also easier to build, that’s the path we chose. But it has some downsides, including 51% attacks while the coin is still new and energy consumption. Proof of Stake provides an interesting solution to those problems.
• Transactions should include an expiry time based on the height or time: This change would make validations easier as it wouldn’t be necessary for nodes to keep the entire history of the blockchain on hand.
• Block size is currently unlimited: Although it is debatable what constitutes the right block size, there should be one.
• Calculating the balance of an address involves going through all previous transactions. This, of course, doesn’t scale well.
• Pending transactions should be extracted based on their fee per byte.
• New peers should be able to connect, and both receive a list of peers and be added themselves to the list of peers