DEV Community: criss.dev

Build your first blockchain from scratch (#3 Finding the longest chain)

criss.dev — Thu, 31 Oct 2019 09:46:11 +0000

In the previous articles (Probabilistic Finality, DAG) we looked into how Probabilistic Finality works and how DAGs can help to find the longest chain.

Today we are going have a look at implementing a basic DAG in Crystal. We will focus on implementing a DAG::Vertex class and finding the vertex with the longest distance from a given starting vertex.
Each vertex will have a unique name and a Hash to represent its edges pointing to its children.

Here is the complete finished implementation:

module DAG
  record Tip,
    vertex : DAG::Vertex,
    distance : Int32,
    branch_root : (DAG::Vertex | Nil)

  class Vertex
    alias Name = String

    getter name : Name
    getter edges : Hash(Name, Vertex)

    def initialize(@name, @edges = {} of Name => Vertex)
    end

    def add(edge_to vertex : Vertex) : Nil
      @edges[vertex.name] = vertex
    end

    def children : Array(Vertex)
      @edges.values
    end
  end

  extend self

    def tips(
    from vertex : Vertex,
    visited = Hash(Vertex::Name, Bool).new(false),
    distance = Hash(Vertex, Int32).new(0),
    tips = Array(DAG::Tip).new,
    start : (Vertex | Nil) = nil,
    current_branch_root : (Vertex | Nil) = nil
  ) : Array(DAG::Tip)
    # remember the starting vertex
    start = vertex if distance.empty?

    # mark current vertex as visited
    visited[vertex.name] = true

    # sort children just to make it easier to test
    sorted_children = vertex.children.sort_by { |c| c.name }
    # if it has no children it's the tip of a branch
    if !sorted_children[0]?
      tips << DAG::Tip.new(
        vertex: vertex,
        distance: distance[vertex],
        branch_root: current_branch_root
      )
    else
      # it has children so let's continue the traverse
      sorted_children.each do |child|
        if !visited[child.name]
          # we mark the child of the starting vertex as the current root
          # of the branch we are exploring
          if start == vertex
            current_branch_root = child
          end
          # we calculate the distance of the child
          distance[child] = distance[vertex] + 1

          tips(
            from: child,
            visited: visited,
            distance: distance,
            tips: tips,
            start: start,
            current_branch_root: current_branch_root
          )
        end
      end
    end

    tips
  end

  def tip_of_longest_branch(from vertex : DAG::Vertex) : DAG::Tip
    tips = self.tips(from: vertex)

    tip_of_longest_branch from: tips
  end

  def tip_of_longest_branch(from tips : Array(DAG::Tip)) : DAG::Tip
    # Tip of longest branch (chain)
    tips.max_by { |t| t.distance }
  end
end

Let's break the code apart to understand how it works.

1. DAG::Vertex Class

module DAG
  ...

  class Vertex
    alias Name = String

    getter name : Name
    getter edges : Hash(Name, Vertex)

    def initialize(@name, @edges = {} of Name => Vertex)
    end

    def add(edge_to vertex : Vertex) : Void
      @edges[vertex.name] = vertex
    end

    def children : Array(Vertex)
      @edges.values
    end
  end

  ...

end

This should be straight forward. We build a class Vertex and pass along the Name when we initialize it. Afterwards we create its edges:

v1 = DAG::Vertex.new("A")
v2 = DAG::Vertex.new("B")

v1.add edge_to: v2

pp v1.name #=> "A"
pp v1.children #=> [#<DAG::Vertex:0x7f0f4866ee60 @edges={}, @name="B">]
# same as
pp v1.edges.values #=> [#<DAG::Vertex:0x7f0f4866ee60 @edges={}, @name="B">]

You can play with the code here

2. Distances and the Tips of branches

module DAG

  ...

  extend self

  def tips(
    from vertex : Vertex,
    visited = Hash(Vertex::Name, Bool).new(false),
    distance = Hash(Vertex, Int32).new(0),
    tips = Array(DAG::Tip).new,
    start : (Vertex | Nil) = nil,
    current_branch_root : (Vertex | Nil) = nil
  ) : Array(DAG::Tip)
    # remember the starting vertex
    start = vertex if distance.empty?

    # mark current vertex as visited
    visited[vertex.name] = true

    # sort children just to make it easier to test
    sorted_children = vertex.children.sort_by { |c| c.name }
    # if it has no children it's the tip of a branch
    if !sorted_children[0]?
      tips << DAG::Tip.new(
        vertex: vertex,
        distance: distance[vertex],
        branch_root: current_branch_root
      )
    else
      # it has children so let's continue the traverse
      sorted_children.each do |child|
        if !visited[child.name]
          # we mark the child of the starting vertex as the current root
          # of the branch we are exploring
          if start == vertex
            current_branch_root = child
          end
          # we calculate the distance of the child
          distance[child] = distance[vertex] + 1

          tips(
            from: child,
            visited: visited,
            distance: distance,
            tips: tips,
            start: start,
            current_branch_root: current_branch_root
          )
        end
      end
    end

    tips
  end

To find out the distances starting from say block B1 to Bn we use depth first search (DFS), that explores each branch to the end and than moves on to the next one. If you think you need to better understand DFS you should watch this video.

  def tips(
    from vertex : Vertex,
    visited = Hash(Vertex::Name, Bool).new(false),
    distance = Hash(Vertex, Int32).new(0),
    tips = Array(DAG::Tip).new,
    start : (Vertex | Nil) = nil,
    current_branch_root : (Vertex | Nil) = nil
  ) : Array(DAG::Tip)

  ...
end

The tips method is a recursive method that initially only needs the from vertex parameter and all other parameters are passed along with each step.

visited is an empty hash, which has been initialized with a default value of false for each key that is unknown.

distance contains a Hash of DAG::Vertex with its value being the distance from the first block passed as from vertex parameter

tips contains an Array of DAG::Tip which is a Struct defined using the record macro

module DAG
  record Tip,
    vertex : DAG::Vertex,
    distance : Int32,
    branch_root : (DAG::Vertex | Nil)

  ...
end

We will examine the missing start and current_branch_root parameters later. First let's refresh our memory with an example of a DAG:

If we pass block 3000.1 as from vertex we should receive an Array of [ 3001.2, 3004.2, 3005.1 ] as the tips of this DAG.

Let's step into the method now:

    ...

    # remember the starting vertex
    start = vertex if distance.empty?

    # mark current vertex as visited
    visited[vertex.name] = true

    # sort children just to make it easier to test
    sorted_children = vertex.children.sort_by { |c| c.name }

    ...

start is set to the first vertex that we actually passed to the method and it's not altered afterwards as distance will never be empty once we move on to the next step of the traverse.

visited is marking the vertex as visited and this is repeated each step

sorted_children is only set for convenience

    # if it has no children it's the tip of a branch
    if sorted_children.empty?
      tips << DAG::Tip.new(
        vertex: vertex,
        distance: distance[vertex],
        branch_root: current_branch_root
      )
    else
      # it has children so let's continue the traverse
      sorted_children.each do |child|
        if !visited[child.name]
          # we mark the child of the starting vertex as the current root
          # of the branch we are exploring
          if start == vertex
            current_branch_root = child
          end
          # we calculate the distance of the child
          distance[child] = distance[vertex] + 1

          tips(
            from: child,
            visited: visited,
            distance: distance,
            tips: tips,
            start: start,
            current_branch_root: current_branch_root
          )
        end
      end
    end

sorted_children.empty? if this returns true it means we are at the end of a branch. So it's a DAG::Tip

if !visited[child.name] otherwise we continue traversing unvisited children.

if start == vertex
  current_branch_root = child
end

Remember the DAG example above? You have to imagine that once the traverse reaches a tip it steps back until the the branch splits off again and starts traversing unvisited vertices. If we start from 3000.1 all possible current_branch_roots are 3001.1 and 3001.2. We will need this later on to determine which is the branch root of the longest chain.

distance[child] = distance[vertex] + 1 now we calculate the distance and in the next step call tips again to make another step.

  def tip_of_longest_branch(from vertex : DAG::Vertex) : DAG::Tip
    tips = self.tips(from: vertex)

    tip_of_longest_branch from: tips
  end

  def tip_of_longest_branch(from tips : Array(DAG::Tip)) : DAG::Tip
    # Tip of longest branch (chain)
    tips.max_by { |t| t.distance }
  end

tips.max_by { |t| t.distance } to find the tip of the longest branch and its branch root we filter for the one with the highest distance value.
If there are multiple vertices with the same distance we don't really care which one we pick. Why this is not important will become apparent later in the series.

Now let's give it a try:

v1 = DAG::Vertex.new("A")
v2 = DAG::Vertex.new("B")
v3 = DAG::Vertex.new("C")
v4 = DAG::Vertex.new("D")


v1.add edge_to: v2
v2.add edge_to: v3
v3.add edge_to: v4

pp DAG.tips from: v1
#[DAG::Tip(
#  @branch_root=
#   #<DAG::Vertex:0x7fce8d002e60
#    @edges=
#     {"C" =>
#       #<DAG::Vertex:0x7fce8d002e40
#        @edges={"D" => #<DAG::Vertex:0x7fce8d002e20 @edges={}, #@name="D">},
#        @name="C">},
#    @name="B">,
#  @distance=3,
#  @vertex=#<DAG::Vertex:0x7fce8d002e20 @edges={}, @name="D">)]


pp DAG.tip_of_longest_branch from: v1
# @vertex=#<DAG::Vertex:0x7f3acc219e20 @edges={}, @name="D">)

You can try it out yourself here and create more complex structures resembling real life scenarios.

3. Conclusion
We found an easy way to create a DAG and using a simple depth first search we were able to find the tip of the longest chain.

Integrating the code into a working blockchain will require some more work, but we'll get to that later on.

4. Cocol Project
The Cocol Project is an effort to implement a basic, but fully working, blockchain in Crystal — a "Minimum Viable Blockchain"

The code we talked about in this article is part of the ProbFin shard. Here is the DAG implementation and the tests

Build your first blockchain from scratch (#2 DAG)

criss.dev — Tue, 22 Oct 2019 14:52:19 +0000

How to use a DAG to find the longest chain

1. Introduction

In the first part #1 we talked about how probabilistic finality works and why it's needed. Also we saw an example of how blocks might be structured and linked to each other:

The data structure above resembles a Directed Acyclic Graph (DAG) and fortunately DAGs allow for an easy way to find the longest chain. This is an important part of achieving probabilistic finality.

A DAG is made up of nodes (also called vertices) and edges. An edge represents a link between 2 vertices (e.g. 3000.1->3001.1). We can and should traverse a DAG to find out more about its structure, like how far away is vertex 3005.1 from vertex 3000.1

Additionally a DAG has some unique properties. Find out more about it here

2. How to find the longest chain

If we look again at the example above, it becomes apparent that 3005.1 is the tip of the longest chain. But how can we find it out programmatically?

We are going to use Depth First Search to traverse the graph and mark every vertex with its distance from the starting vertex.
We start at 3000.1 and give it a distance of 0. Now we traverse through all vertices and give each a distance of parent distance + 1. So 3001.1 has a parent distance of 0 and +1 gives a distance of 1.

3. Conclusion

If we store blocks as a DAG, we can use Depth First Search to find the longest chain.

4. Next Up

We will finally make our hands dirty and implement a DAG in Crystal

UPDATE: #3 Finding the longest chain implementation

Build your first blockchain from scratch (#1 Probabilistic Finality)

criss.dev — Fri, 18 Oct 2019 10:01:01 +0000

This is the first part in a series that will teach you how to build a full featured blockchain from scratch.

Introduction

I won't be able to cover all aspects in detail, neither is it intended. You should rather make yourself familiar with the high level concept of how a blockchain works. As kind of a reference point you should be familiar with Andreas Antonopoulos' book Mastering Bitcoin, which if needed covers quite some detail.

Understanding how e.g. Bitcoin works doesn't necessarily give you the insight on how to actually build your own blockchain. So I will try to focus during the series solely on the aspects of engineering and will reference to videos, blog articles or to Mastering Bitcoin when it might be of help.

Think of the series as a walkthrough. You can follow along and end up with your own blockchain, but you need to do your homework to fully grasp the non-technical side of blockchain.

Let's start with one of the hardest parts of blockchain: Probabilistic Finality. It's at the core of the consensus mechanism and depends on multiple concepts that come together to achieve probabilistic finality.

1. Probabilistic Finality

Finality is the agreement that a valid transaction between A and B has been executed and can't be reverted. If A uses a Visa card to buy coffee from B, B trusts its bank that the agreement the bank made with Visa will ensure a finalized transaction.

In a decentralized network the trust is given to the majority of the participants (nodes in our case) and we find out what is considered finalized by looking at how the majority sees the state of the transaction.

Learn more about it here: On Settlement Finality, Finality in Blockchain Consensus [video]

So how do we "implement finality" in our blockchain?

Imagine you are a node within our blockchain network. Your node is maintaining a copy of the blockchain data and at the moment it's waiting for the next block to be propagated. Current block is #3000 and #3001 should arrive soon. But because there are multiple miners there is a chance you will receive 2 versions of #3001. Which one to choose?

The example above shows how the current tip of the blockchain could look like after we received 2 versions of block #3001. In the end we don't choose any of the propagated #3001 blocks, but wait for several more consecutive blocks to make a decision.

To understand why waiting makes sense we also need to understand Proof of Work (PoW).

2. Proof of Work (PoW)

PoW is the algorithm that makes mining possible. It is usually explained by what
it does:

In the simplest terms, mining is the process of hashing the block header repeatedly, changing one parameter, until the resulting hash matches a specific target. The hash function’s result cannot be determined in advance, nor can a pattern be created that will produce a specific hash value.
(from Mastering Bitcoin)

But more than by what it does, we need to understand what it's used for. The game theoretic aspect is one of its use cases, that we will cover later. It is important for finality, but not so much for the engineering part.

PoW is also used for randomness and we are very much interested in that part, so that we can implement finality.

Imagine 3 miners embark on the mission to mine the next block. All 3 look for a different solution, since the block header they constructed is unique and because of that the time it takes to mine is more or less random.

Another way to think about mining is by imagining a race, where each participant has a different predetermined, but unknown, finish line. Thus the time it takes to reach the finish line is unpredictable and random.

2.1 Randomness

Let's find out what would happen if we build a blockchain without PoW. If every node in the network would have the ability to create a block instantly, it would look like in the example below

Multiple miners will create a block at the same time and broadcast it to the network. It would be impossible to reach consensus, if for each round T all blocks of Tn would be propagated at the same time.

It can still happen that different miners find the next block at the same time (see example below), but at some point the chances that only one miner will find the next block are very high (because of the randomness in PoW) and as a consequence we can consider the chain of B1.1-> B2.1->B3.1->B4.1->B5.1 as the longest one. Also we can decide to finalize block B2.1 if we want.

Note: Block 4.2 has been abandoned mid-mining because it just wasn't fast enough. So there is no reason to waste more energy on it.

3. Conclusion

In order to reach probabilistic finality we need to make our nodes agree on the longest chain and the mechanism that enables this is PoW. There is much more to PoW, but for now we don't need to cover that.

4. Next Up

In the next article will find out how a Directed Acyclic Graph works and why we need it to find the longest chain.