Carnot implemenation

carnot.nim

# Based on https://github.com/logos-co/nomos-research/blob/98e2a20bbda525cad6e38035c806b374ca5352b2/consensus-engine/docs/carnot-spec.md

import std/[sets, tables]

type
  View = uint

  Block = ref object
    view: View
    qc: Qc

  QcKind = enum
    Standard
    Aggregate

  Qc = ref object
    view: View

    case kind: QcKind
    of QcKind.Standard:
      blck: Id

    of QcKind.Aggregate:
      high_qc: Qc

  Id = array[32, byte]

  Vote = ref object
    blck: Id
    view: View
    voter: Id
    qc: Qc # Opt[Qc]

  NewView = ref object
    view: View
    high_qc: Qc


var
  current_view: View
  local_high_qc: Qc
  latest_committed_view: View
  collection: Table[Id, seq[Vote]]
  known: HashSet[Id]
  self: Id


proc id(v: Block): Id = discard
proc leader(view: auto): Id = discard
proc reset_timer() = discard
proc extends(blck, ancestor: Block) = discard
proc download(view: auto) = discard
proc member_of_leaf_committee(): bool = discard
proc member_of_root_com(): bool = discard
proc member_of_internal_com(): bool = discard
proc child_committee(participant: Id): bool = discard
proc supermajority(votes: auto): bool = discard
proc leader_supermajority(votes: auto): bool = discard
proc morethan_supermajority(votes: auto): bool = discard
proc parent_committee(): Id = discard
proc parent(blck: Block): Block = discard
proc create_vote(): Vote = discard
proc build_qc(votes: auto): Qc = discard
proc build_vote(): Vote = discard
proc build_block(qc: auto): Vote = discard

proc update_high_qc(qc: Qc)

proc send(what, where: auto) = discard
proc broadcast(what: auto) = discard
proc safe_block(blck: Block): bool

func try_to_commit_grandparent(blck: Block): bool

func try_to_commit_grandparent(blck: Id): bool = discard

proc receive_block(blck: Block) =
    if blck.id in known or blck.view <= latest_committed_view:
        return

    # Recursively make sure that we process blocks in order
    # if blck.parent() is missing {
    #     let parent = download(blck.parent)
    #     receive(parent)
    # }

    if safe_block(blck):
      # This is not in the original spec, but
      # let's validate I have this clear.
      # assert blck.view = current_view

      update_high_qc(blck.qc)

      if member_of_leaf_committee():
        let vote = create_vote()
        if member_of_root_com():
          send(vote, leader(current_view + 1))
        else:
          send(vote, parent_committee())

        current_view = current_view + 1
        reset_timer()
        discard try_to_commit_grandparent(blck)


proc safe_block(blck: Block): bool =
  case blck.qc.kind
  of Standard:
    # Previous leader did not fail and its proposal was certified
    if blck.qc.view <= latest_committed_view:
        return false

    # this check makes sure blck is not old
    # and the previous leader did not fail
    return blck.view >= current_view and blck.view == blck.qc.view + 1
  of Aggregate:
      # Verification of blck.aggQC.highQC along
      # with signature or blck.aggQC.signature is sufficient.
      # No need to verify each qc inside blck.aggQC
      if blck.qc.high_qc.view <= latest_committed_view:
          return false;

      return blck.view >= current_view
      # we ensure by construction this extends the blck in
      # high_qc since that is by definition the parent of this blck

func try_to_commit_grandparent(blck: Block): bool =
  let
    parent = blck.parent()
    grandparent = parent.parent()
  return parent.view == grandparent.view+1 and
      blck.qc.kind == Standard and parent.qc.kind == Standard

# Update the latest certification (qc)
proc update_high_qc(qc: Qc) =
    case qc.kind
    # Happy case
    of Standard:
        # TODO: revise
        if qc.view > local_high_qc.view:
            local_high_qc = qc

        # Q: The original pseudocde checked for possilbly
        # missing view and downloaded them, but I think
        # we already dealt with this in receive_block

    # Unhappy case
    of Aggregate:
      if qc.high_qc.view != local_high_qc.view:
          local_high_qc = qc.high_qc
            # Q: same thing about missing views

proc receive_vote(vote: Vote) =
    # if vote.blck is missing {
    #     let blck = download(vote.blck)
    #     receive(blck)
    # }

    # Q: we should probably return if we already received this vote

    if member_of_internal_com() and not member_of_root_com():
        if child_committee(vote.voter):
            collection[vote.blck].add(vote)
        else:
            # Q: not returning here would mean it's extremely easy to
            # trigger building a new vote in the following branches
            return;


        if supermajority(collection[vote.blck]):
            # Q: should we send it to everyone in the committe?
            let self_vote = build_vote();
            send(self_vote, parent_committee())
            # Q: why here?
            current_view += 1;
            reset_timer()
            # Q: why do we do this here?
            discard try_to_commit_grandparent(vote.blck)

    if member_of_root_com():
        if child_committee(vote.voter):
            collection[vote.blck].add(vote)
        else:
            # Q: not returning here would mean it's extremely easy to
            # trigger building a new vote in the following branches
            return


        # Q: Same consideration as above
        if supermajority(collection[vote.blck]):
          # Q: The vote to send is not the one received but
          # the one build by this participant, right?
          let self_vote = build_vote();
          let qc = build_qc(collection[vote.blck])
          self_vote.qc=qc
          send(self_vote, leader(current_view + 1))
          # Q: why here?
          current_view += 1
          reset_timer()
          # Q: why here?
          discard try_to_commit_grandparent(vote.blck)


        # Q: this means that we send a message for every incoming
        # message after the threshold has been reached, i.e. a vote
        # from a node in the leaf committee can trigger
        # at least height(tree) messages.
        if morethan_supermajority(collection[vote.blck]):
          # just forward the vote to the leader
          # Q: But then childcommitte(vote.voter) would return false
          # in the leader, as it's a granchild, not a child
          send(vote, leader(current_view + 1))

    if self == leader(vote.view):
      if vote.view < current_view - 1:
        return


      # Q: No filtering? I can just create a key and  vote?
      collection[vote.blck].add(vote)
      if supermajority(collection[vote.blck]):
        let qc = build_qc(collection[vote.blck])
        let blck = build_block(qc)
        broadcast(blck)

proc receive(newView: View) =
    # download the missing blck
    # if newview.highQC.blck missing {
    #     let blck = download(new_view.high_qc.blck)
    #     receive(blck)
    # }

    # It's an old message. Ignore it.
    if newView < current_view:
        return


    # Q: this was update_high_qc_and_view(new_view.high_qc, Null)
    # update_high_qc(newView.high_qc)

    if member_of_internal_com():
      # TODO collection[newView].append(newView)

      if supermajority(newView):
        let newViewQC = Qc() # build_qc(collection[newView])
        if member_of_root_com():
          send(newViewQC, leader(newView+1))
          current_view += 1
        else:
          send(newViewQC, parent_committee())

proc timeout() = discard