Michael Chen
Jul 7 · 4 min read

By Sfxdx, edited by Michael Chen

Introduction

The doc describes the implementation details of DAGchain scope1.

Definitions

Objects

EventHeader

Team member ̶C̶o̶n̶s̶e̶n̶s̶u̶s̶ ̶n̶o̶d̶e̶

Election table (RAM-only)

It’s a map, located in memory:

Global state

Transaction

Activities

Setting up genesis superframe

input: genesis superframe params

  1. Write genesis transactions state
  2. <last SfSealer> = construct event, according to genesis params
  3. <superframe height> = 1
  4. <team> = nodes, according to genesis balances

Additional event checks

input: event

  1. if event.<superframe height> != state.<superframe height>
    a) ignore event
  2. isSfStarter = <event height> == 0
  3. if isSfStarter
    a) check that linked only to <last SfSealer>

p2p synchronization

When node requests current heights of last events, it specifies the superframe it’s interested in

Transactions posting

  1. if event frame >= SUPERFRAME_LEN — 3
    a) Don’t post transactions

Events posting

input: newly created event

  1. if <last event from me> == nil // beginning of a superframe
    a) event.parent = <last SfSealer>

Consensus activities

stronglySee

Input: event hash A, event hash B

output: bool

  1. event — a current event.
  2. witness — a witness of the previous frame.
  3. counter — a counter for calculating strongly seeing.
  4. nodes — consensus nodes.
  5. for node range nodes
    a) if witness.FirstSeq[node.ID] <= event.LastSeq[node.ID]
    i. counter = counter + 1
  6. if counter >= ⅔ * nodes.length
    i. return true
  7. return false

rootStronglySeesRoot

Input: root hash A, frame height B, node id B

output: root hash or nil

Returns hash of root B, if root A strongly sees root B. Due to a fork, there may be many roots B with the same pair of {frame height B, node id B}, but strongly seen may be only one of them (if no more than 1/3n are Byzantine), with a specific hash.

  1. A doesn’t exist
    a) return nil
  2. there’s no root B with {frame height B, node id B}
    a) return nil
  3. for B := range roots{frame height B, node id B}
    a) if A strongly sees B
    i. return B.hash
  4. return nil

election.processRoot

input: root

output: (decided frame height, sfWitness hash) or nil

calculate SfWitness votes only for the new root. If this root sees that the current election is decided, then return decided sfWitness

election.ProcessKnownRoots

input: frameToDecide

output: (decided frame height, sfWitness hash) or nil

The function is similar to processRootVotes, but it fully re-processes the current voting. This routine is called after node startup, and after each decided frame.

confirmEvents(sfWitness hash)

  1. eventsToConfirm = not confirmed events, which are seen by sfWitness
  2. orderedEventsToConfirm = someOrderingAlgorithm(eventsToConfirm)
  3. for event := range orderedEventsToConfirm
    a) event.confirmedBy = sfWitness // it should be written in a DB, and indexed by decided frame height
    b) for tx := range event.txs
    i. // execute tx against current global state, including changes after prev. executed txs in this loop. We don’t need to take old state, we take the latest one.
    ii. p.executeTx(tx, p.txsState)

sealSuperframe

input: sfWitness

Remove the current hashgraph, except raw events history and transactions state. Calculate new team for the next superframe.

  1. p.<last SfSealer> = sfWitness
  2. p.<superframe height> += 1
  3. calculate new <team>
    a) // if we’re here, txs are already executed
    b) nodes = balances in the latest txs state
    c) sortedNodes = sort nodes by stake amount, public ID
    d) p.<team> = take first CONSENSUS_TEAM_SIZE elements from sortedNodes
  4. prune the caches and indexes. Except events history, transactions state and values above

onFrameDecided

input: decided frame height, sfWitness hash

  1. confirmEvents(sfWitness)
  2. if decided frame height == SUPERFRAME_LEN — 1
    a) sealSuperframe(sfWitness)
  3. clear election caches for the decided frame

consensus routine for each event

input: event

  1. if !event.isRoot
    a) return // in terms of consensus, we’re interested only in roots
  2. // process election for the new root
  3. decidedFrame, sfWitness := p.election.processRoot(event)
  4. if decidedFrame == nil
    a) return
  5. // if we’re here, then this root has seen that lowest not decided frame is decided now
  6. p.onFrameDecided(decidedFrame, sfWitness)
  7. // then call resetElection/processKnownRoots until it returns nil — it’s needed because new elections may already have enough votes, because we process elections from oldest to newest
  8. while true
    a) p.election.resetElection(decidedFrame + 1)
    b) decidedFrame, sfWitness = p.election.processKnownRoots()
    c) if decidedFrame == nil
    i. break
    d) p.onFrameDecided(decidedFrame, sfWitness)

Fantom Foundation

Fantom is the world's first DAG based smart contract platform.

Michael Chen

Written by

Chief Marketing Officer @ Fantom Foundation

Fantom Foundation

Fantom is the world's first DAG based smart contract platform.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade