Skip to content

Instantly share code, notes, and snippets.

@arnetheduck
Created March 15, 2023 12:37
Show Gist options
  • Save arnetheduck/22701a7af2f06854118aad7e68e0c0a6 to your computer and use it in GitHub Desktop.
Save arnetheduck/22701a7af2f06854118aad7e68e0c0a6 to your computer and use it in GitHub Desktop.
Carnot implemenation
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment