Created
March 15, 2023 12:37
-
-
Save arnetheduck/22701a7af2f06854118aad7e68e0c0a6 to your computer and use it in GitHub Desktop.
Carnot implemenation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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