Ignorance may be Strength : Weaving the Chains Together

The final step of the process by which we build the blockchain (before we turn our attention to testing and implementing on AWS) is to weave all these individual chains together.

At the moment, each node has generated its own transactions and its own blocks, and chained those blocks together. Each node has distributed its transactions and blocks to all the other nodes, and all of them have been stored in journals specific to the originating node: we have created multiple copies of all the transactions and blocks, and that "should" be enough, but there is one more step I want to go through.

At any given moment in time T, each node has produced a "latest" block and that should have been sent to all the other nodes. At a point of eventual consistency, all the nodes will have the same set of blocks which were the latest at time T. We can thus define a Weave as a structure that contains:

The unique timestamp associated with the Weave (i.e. the time T);
The previous Weave.ID, if any;
A list of all the nodes, together with the ID of the last Block they published before or at time T.

Note that for consistency, the list of block ids will be in alphabetical order by node name (i.e. the ASCII collation order of the URL strings of each node).

We can then hash this value and come up with a unique hash for "the overall weave at time T".

Separately (and not today), we will require all the nodes to provide a signature for that hash: why this is separate will become clear when we get there.

Defining the Weave

First things first: we need to define a type to hold the Weave:

package records

import "github.com/gmmapowell/ChainLedger/internal/types"

type Weave struct {
    ID           types.Hash
    ConsistentAt types.Timestamp
    PrevID       types.Hash
    LatestBlocks []NodeBlock
}

WEAVE_OUTLINE:internal/records/weave.go

This depends on the idea of a NodeBlock which is a pair of the node name and its latest block ID:

package records

import "github.com/gmmapowell/ChainLedger/internal/types"

type NodeBlock struct {
NodeName string
LatestBlockID types.Hash
}

WEAVE_OUTLINE:internal/records/nodeblock.go

And then we need a class that can create the Weave. For hopefully obvious reasons, I've called this a Loom:

package loom

import (
    "github.com/gmmapowell/ChainLedger/internal/records"
    "github.com/gmmapowell/ChainLedger/internal/types"
)

type Loom struct {
}

func (loom *Loom) WeaveAt(when types.Timestamp) *records.Weave {
    ret := records.Weave{}
    return &ret
}

WEAVE_OUTLINE:internal/loom/loom.go

Copying the process we followed for building blocks, we also have a thread that will build the Weaves on a time basis:

package loom

import "github.com/gmmapowell/ChainLedger/internal/helpers"

type LoomThread interface {
    Start()
}

type IntervalLoomThread struct {
    clock helpers.Clock
    loom  *Loom
}

func (t *IntervalLoomThread) Start() {
    go t.Run()
}

func (t *IntervalLoomThread) Run() {
    t.loom.WeaveAt(t.clock.Time())
}

WEAVE_OUTLINE:internal/loom/loom_thread.go

(I have put a minimal skeleton in each of these, mainly to stop Go complaining about things not being used; none of this is actually used, because I haven't wired it in.)

Getting it Started

Following along with the model from the Blocker, we will call Start on this thread when we start up the node

package loom

import "github.com/gmmapowell/ChainLedger/internal/helpers"

type LoomThread interface {
    Start()
}

type IntervalLoomThread struct {
    clock helpers.Clock
    loom  *Loom
}

func (t *IntervalLoomThread) Start() {
    go t.Run()
}

func (t *IntervalLoomThread) Run() {
    t.loom.WeaveAt(t.clock.Time())
}

func NewLoom(clock helpers.Clock) LoomThread {
    loom := &Loom{}
    return &IntervalLoomThread{clock: clock, loom: loom}
}

WEAVE_START_THREAD:internal/loom/loom_thread.go

Now we need to make the thread call the Loom on a repeating basis. But when?

When Do We Weave?

It's vitally important that each Weave is generated on all the nodes using the same set of blocks, which means they all have to generate a block based on a specific moment in (Unix) time. To be clear, they don't need to actually weave at the same time, but they need to weave based on the data that was present at a single moment in time. And their clocks do not need to be in sync (although it helps if they are close) - they are working on the times at which each of the nodes said it did the work.

But how do they pick a time that they can all agree on?

This is one of the big problems in distributed software: agreeing on anything. Generally, you either need to designate one node the "leader", in which case you have a single point of failure (if that node goes down, who leads?) or you have to have some kind of system for deciding how to resolve different opinions.

On the other hand, if you can decide on a "rule" that you can build into the software, you can avoid all of these issues. In this case, there is an obvious rule to follow which will generate the same results on all the nodes. It is this:

Generate a weave at a regular heartbeat of Nms, and do it when the unix time on your local clock modulo N is zero.

That is, have a recurring heartbeat, which fires at least every Nms or so; when it does, take the current time and "clear out" the bottom Nms, so that the result is an exact multiple of N. If that weave hasn't been built yet, then build it now.

I'm going to take advantage of that check on previous work and have my clock go three times as fast as I want to weave: this reduces the possibility that I simply "miss" an interval and means that it will generally produce a weave within about N/6ms of the registered time.

For now, I am going to specify a value of 1000ms (or 1s) for N. This is very frequent and I don't think such a value would be appropriate for a production system; I would probably choose 60,000ms (or 1 minute). On the other hand, remember that until the final Weave is generated, you do not have guaranteed transactional integrity and non-repudiability, so a granularity of many minutes or hours would delay the time when anyone could declare the transaction "complete".

How Do We Specify This?

It's quite simple: this is a system-wide configuration parameter. The obvious thing to do is to put it right in the code, but since we have a configuration file, I'm going to put it there. Note that it's really important that you specify the same value on all nodes, and it would probably a good idea on startup for the nodes to agree on this value. An alternative would be to have this configuration - along with the names and public keys of all the nodes - in a central place. For now, I'm just going to put it at the top level of the harness configuration and make that work its way through all the nodes, although it's so dull I'm going to do it off camera.

The Loom Loop

With all that in place, we can now update the LoomThread:

func (t *IntervalLoomThread) Run() {
    delay := time.Duration(t.interval/3) * time.Millisecond
    timer := t.clock.After(delay)

    for {
        select {
        case weaveBefore := <-timer:
            weaveBefore = weaveBefore.RoundTime(t.interval)
            if !t.myjournal.HasWeaveAt(weaveBefore) {
                weave := t.loom.WeaveAt(weaveBefore)
                t.myjournal.StoreWeave(weave)
            }
        }
        timer = t.clock.After(delay)

    }
}

WEAVE_REGULAR_BUILD:internal/loom/loom_thread.go

RoundTime is a new method we have defined on types.Timestamp which returns a timestamp which is an exact multiple of the argument granularity:

func (ts Timestamp) RoundTime(granularity int) Timestamp {
    i64 := int64(ts)
    i64 /= int64(granularity)
    i64 *= int64(granularity)
    return Timestamp(i64)
}

WEAVE_REGULAR_BUILD:internal/types/timestamp.go

The Journaller is given the job of recording the weaves. We have two operations we are using here: HasWeaveAt and StoreWeave. Putting all of the plumbing to one side, the core of the code is handled here:

func LaunchJournalThread(name string, finj helpers.FaultInjection) chan<- JournalCommand {
    var txs []*records.StoredTransaction
    var blocks []*records.Block
    weaves := make(map[types.Timestamp]*records.Weave)
    ret := make(chan JournalCommand, 20)

...

            case JournalHasWeaveAtCommand:
                v.ResultChan <- weaves[v.When] != nil
            case JournalStoreWeaveCommand:
                weaves[v.Weave.ConsistentAt] = v.Weave

...

}

WEAVE_REGULAR_BUILD:internal/storage/journal_thread.go

We are storing the Weaves in a map based on their timestamp because this makes it very easy to find if there is one already defined for a given timestamp. This is the only case we have right now, and I'm thinking that any other cases we have will probably also want to access them based on timestamp, so I think it's a good fit, but if something comes up, we can always revisit that decision.

And when we run it we see that we are trying to weave together the blocks on a regular basis but not duplicating them:

2025/03/04 14:44:43 http://localhost:5001 weaving at 1741099483000
2025/03/04 14:44:43 http://localhost:5002 weaving at 1741099483000
2025/03/04 14:44:44 http://localhost:5001 weaving at 1741099484000
2025/03/04 14:44:44 http://localhost:5002 weaving at 1741099484000
2025/03/04 14:44:45 http://localhost:5001 weaving at 1741099485000
2025/03/04 14:44:45 http://localhost:5002 weaving at 1741099485000

(Note that each timestamp is an exact multiple of 1000.)

Actually Weaving the Blocks

We have built the loop and, to make it work, we have built something approximating a Weave, but we certainly haven't met the contract we set for ourselves. That is going to require quite a bit more work, most of which is more plumbing. I'll just quietly get on with that and just point to the highlights.

The Weave ID is the first thing in the struct, but it's the hardest thing to calculate, because it is a hash of all the other fields, so we need to assemble those first.

ConsistentAt is the timestamp we have been passed in.

PrevID seems fairly easy; we just need to keep track of each time we generate a Weave and record that. The first one will be nil or blank or something.

The block ids are, understandably, the most complicated piece. But let's take it slowly and it will all become clear.

We know we want a slice of NodeBlock, so we can create that:

func (loom *Loom) WeaveAt(when types.Timestamp, prev *records.Weave) *records.Weave {
    var prevID types.Hash
    if prev != nil {
        prevID = prev.ID
    }
    nbs := make([]records.NodeBlock, len(loom.allJournals))