logos-blockchain/logos-blockchain-specs
1
0
Fork 0
mirror of https://github.com/logos-blockchain/logos-blockchain-specs.git synced 2026-01-15 03:23:10 +00:00
Code Issues Packages Projects Releases Wiki Activity
logos-blockchain-specs/carnot/spec.md
mjalalzai e4308809d3 Simplified unhappy path
2023-03-29 08:27:35 -07:00

450 lines
16 KiB
Markdown
Raw Permalink Blame History

# Carnot Specification
This is the pseudocode specification of the Carnot consensus algorithm.
In this specification we will omit any cryptographic material, block validity and proof checks. A real implementation is expected to check those before hitting this code.
In addition, all types can be expected to have their invariants checked by the type contract, e.g. in an instance of type `Qc::Aggregate` the `high_qc` field is always the most recent qc among the aggregate qcs and the code can skip this check.
'Q:' is used to indicate unresolved questions.
Notation is loosely based on CDDL.
## Messages
A critical piece in the protocol, these are the different kind of messages used by participants during the protocol execution.
* `Block`: propose a new block
* `Vote`: vote for a block proposal
* `Timeout`: propose to jump to a new view after a proposal for the current one was not received before a configurable timeout.
### Block
(sometimes also called proposal)
We assume an unique identifier of the block can be obtained, for example by hashing its contents. We will use the `id()` function to access the identifier of the current block.
We also assume that a unique tree order of blocks can be determined, and in particular each participant can identify the parent of each block. We will use the `parent()` function to access such parent block.
```python
@dataclass
class Block:
view: View
qc: Qc
```
##### View
A monotonically increasing number (considerations about the size?)
```python
View = int
```
##### Qc
There are currently two different types of QC:
```python
Qc = StandardQc | AggregateQc
```
###### Standard
Q: there can only be one block on which consensus in achieved for a view, so maybe the block field is redundant?
```python
class StandardQc:
view: View
block: Id
```
###### Aggregate
`high_qc` is `Qc` for the most recent view among the aggregated ones. The rest of the qcs are ignored in the rest of this algorithm.
We assume there is a `block` function available that returns the block for the Qc. In case of a standard qc, this is trivially qc.block, while for aggregate it can be obtained by accessing `high_qc`. `high_qc` is guaranteed to be a 'Standard' qc.
```python
class AggregateQc:
view: View
qcs: List[Qc]
def high_qc(self) -> Qc:
return max(self.qcs, key=lambda qc: qc.view)
```
##### Id
undef, will assume a 32-byte opaque string
```python
Id: bytes = bytearray(32)
```
### Vote
A vote for `block` in `view`
qc is the optional field containing the QC built by root nodes from 2/3 + 1 votes from their child committees and forwarded the the next view leader.
```python
class Vote:
block: Id
view: View
voter: Id
qc: Option[Qc]
```
### Timeout_Msg
view: View
high_qc: Qc
rb : RB # Random Beacon
sender: Id
```
```python
@dataclass
class Timeout_Msg:
view: View
high_qc: Qc
rb: RB
sender: Id
```
```python
### Timeout_Msg_qc
view: View ### Currently the 3 QC fields are not being used. But I am keeping it as it might be useful to save a roundtrip during unhappy path.
high_qcs: list[Qc]
sender: Id
```
```python
@dataclass
class Timeout_Msg_qc:
view: View
high_qcs: list[Qc]
sender: Id
```
### Sync_Msg
view: View ### Currently the 3 QC fields are not being used. But I am keeping it as it might be useful to save a roundtrip during unhappy path.
high_qc: Qc
timeout_qc: Timeout_qc
sender: Id
```
```python
@dataclass
class Sync_Msg:
high_qc: Qc
timeout_qc: timeout_qc
sender: Id
```
## Local Variables
Participants in the protocol are expected to mainting the following data in addition to the DAG of received proposal:
* `current_view`
* `local_high_qc`
* `latest_committed_view`
* `collection`: TODO rename
```python
CURRENT_VIEW: View
LOCAL_HIGH_QC: Qc
LATEST_COMMITTED_VIEW: View
PENDING_VOTE_COLLECTION: dict() #id here presents Hash of the block returnd by block.Id()
PENDING_TIMEOUTMSG_COLLECTION: dict()
LAST_VIEW_TIMEOUT_QC: Timeout_qc
```
## Available Functions
The following functions are expected to be available to participants during the execution of the protocol:
* `leader(view)`: returns the leader of the view.
* `reset_timer(view)`: resets timer for a specific view. If the timer expires the `timeout` routine is triggered.
* `extends(block, ancestor)`: returns true if block is descendant of the ancestor in the chain.
* `download(view)`: Download missing block for the view.
getMaxViewQC(qcs): returns the qc with the highest view number.
* `member_of_leaf_committee()`: returns true if the participant executing the function is in the leaf committee of the committee overlay.
* `member_of_root_com()`: returns true if the participant executing the function is member of the root committee withing the tree overlay.
* `member_of_internal_com()`: returns true if the participant executing the function is member of internal committees within the committee tree overlay
* `child_committee(participant)`: returns true if the participant passed as argument is member of the child committee of the participant executing the function.
* `supermajority()`: the behavior changes with the position of a participant in the overlay:
* committee members: returns if the number of distinctive signers of votes, for a block in the child committee is equal to the threshold.
* For leader: returns if the number of distinct voters for a block is 2/3 + 1 for both children committees of root committee and overall 2/3 + 1
* `morethanSsupermajority(votes)`: returns if the number of distinctive signers of votes for a block is is more than the threshold: TODO
* `parent_committee`: return the parent committee of the participant executing the function withing the committee tree overlay. Result is undefined if called from a participant in the root committee.
* `oblivious_adjacent_committees()`: returns the committees from which a node has not received the timeout_qc.
<!-- #####Supermajority of child votes is 2/3 +1 votes from members of child committees
#####Supermajority for the qc to be included in the block, should have at least 2/3+1 votes from both children of the root committee and overal 2/3 +1
#####combined votes of the root committee+its child committees. -->
## Core functions
These are the core functions necessary for the Carnot consensus protocol, to be executed in response of incoming messages, except for `timeout` which is triggered by a participant configurable timer.
### Receive block
```python3
def receive_block(block: Block):
if block.id() is known or block.view <=LATEST_COMMITTED_VIEW:
return
# Recursively make sure that we process blocks in order
if block.parent() is missing:
parent: Block = download(block.parent())
receive(parent)
if safe_block(block):
# This is not in the original spec, but
# let's validate I have this clear.
assert block.view == current_view
update_high_qc(block.qc)
vote = create_vote()
if member_of_leaf_committee():
if member_of_root_committee():
send(vote, leader(current_view + 1))
else:
send(vote, parent_commitee())
# current_view += 1
# reset_timer()
increment_view_qc(block.qc)
```
##### Auxiliary functions
```python
def safe_block_qc (block: Block):
match block.qc:
case StandardQc() as standard:
# Previous leader did not fail and its proposal was certified
# if standard.view <= LATEST_COMMITED_BLOCK:
if standard.view < CURRENT_VIEW:
return False
# increment_view_qc(standard.view+1)
# this check makes sure block is not old
# and the previous leader did not fail
return block.view >= CURRENT_VIEW and block.view == (standard.view + 1)
case AggregateQc() as aggregated_qc:
# Verification of block.aggQC.highQC along
# with signature or block.aggQC.signature is sufficient.
# No need to verify each qc inside block.aggQC
if aggregated_qc.high_qc().view <= LATEST_COMMITED_BLOCK:
return False
return block.view >= CURRENT_VIEW
# we ensure by construction this extends the block in
# high_qc since that is by definition the parent of this block
```
```python
# Commit a grand parent if the grandparent and
# the parent have been added during two consecutive views.
def try_to_commit_grand_parent(block: Block):
parent = block.parent()
grand_parent = parent.parent()
if (parent.view == (grand_parent.view + 1) and
isinstance(block.qc, (StandardQc, )) and # Q: Is this necessary? Yes, this is very important for safety.
isinstance(parent.qc, (StandardQc, )) # Q: Is this necessary?
):
LAST_COMMITTED_VIEW=grand_parent.view
return true
else:
return false
# Update last_committed_view ? (Ans: Yes, last_committed_view has to be updated.)
```
```python
# Update the latest certification (qc)
def update_high_qc(qc: Qc):
match qc:
# Happy case
case Standard() as qc:
# 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 (You are right!)
# Unhappy case
case Aggregate() as qc:
high_qc = qc.high_qc()
if high_qc.view != LOCAL_HIGH_QC.view:
LOCAL_HIGH_QC = high_qc
# Q: same thing about missing views. (Ans: This is a different case. A node might have a higher local_high_qc but other
# nodes where not able to see it due to failure. Now since a new leader is being selected, we need to make sure the high_qc is
# synched across network.)
```
### Receive Vote
Q: this whole function needs to be revised
```python
def receive_vote(vote: Vote):
if vote.block is missing:
block = download(vote.block)
receive(block)
if vote.view < CURRENT_VIEW: # Unless we collect votes for attestation for rewards (PoS)
return
if leader(vote.view+1): # Q? Which view? CURRENT_VIEW or vote.view? => Ans: vote.view+1 Vote for the view
if root_commitee(vote.voter):
# Q: No filtering? I can just create a key and vote? (Ans: A check is added to confirm the root_commitee voter)
PENDING_VOTE_COLLECTION[vote.block].append(vote)
if len(PENDING_VOTE_COLLECTION[vote.block])==supermajority():
qc = build_qc(PENDING_VOTE_COLLECTION[vote.block])
block = build_block(txs,CURRENT_VIEW+1,qc, AggQC=None) # #build_block
broadcast(block)
# Q: we should probably return if we already received this vote (Ans: Yes. It should be done, for all types of messages received. votes should be counted from )
if member_of_internal_com() and not member_of_root():
if child_commitee(vote.voter):
PENDING_VOTE_COLLECTION[vote.block].append(vote)
# else:
# Q: not returning here would mean it's extremely easy to
# trigger building a new vote in the following branches
# return
# (return is not necessary as long as it stays within if scope)
if len(PENDING_VOTE_COLLECTION[vote.block])==supermajority():
# Q: should we send it to everyone in the committee?
self_vote = build_vote()
send(self_vote, parent_committee)
if member_of_root():
if child_commitee(vote.voter):
PENDING_VOTE_COLLECTION[vote.block].append(vote)
# else:
# Q: not returning here would mean it's extremely easy to
# trigger building a new vote in the following branches
# return
# Ans: return is not necessary as long as it stays within if scope
# Q: The vote to send is not the one received but
if len(PENDING_VOTE_COLLECTION[vote.block])==supermajority():
# Q: The vote to send is not the one received but
# the one build by this participant, right?
self_vote = build_vote();
qc = build_qc(PENDING_VOTE_COLLECTION[vote.block])
self_vote.qc=qc
send(self_vote, leader(current_view + 1))
# 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. (Ans: Root nodes only forward additional votes from their child committees.)
if len(PENDING_VOTE_COLLECTION[vote.block]) > supermajority():
# 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. (Ans: Leader does not have a child. But it needs to count votes
# (individually and within qc) to make sure, threshold of votes is reached.)
send(vote, leader(current_view + 1))
```
###### This is all part of pacemaker (liveness) module
### Timeout
```python3
##### When a node timesout and cannot complete the view on time. It has to send its timeout_Msgs to the its parent committee. Since root
### committee does not have a parent it sends to itself
def local_timeout():
save_consensus_state()
stop_timer(current_view)
#ignore any happy path msg. Except Timeout_Msg from child committee
# Assumption here is that somehow RB also knows about the timeout and has already given the RB to rebuild the overlay tree.
# Received_RB() is not implemented but returns true if Overlay is recalculated due to current_view failure
# rb is the random beacon value for new overlay for current_view. It is included because if a node receives timeout_Msg and
# is somehow unaware of new overlay can built the overlay using the RB in timeout message.
if member_of_leaf() and Received_RB(current_view):
timeout_Msg = create_timeout(CURRENT_VIEW,LOCAL_HIGH_QC, LAST_VIEW_TIMEOUT_QC, rb)
send(timeout_Msg, parent_committee()) # Need to be discussed. It can only be sent to the next leader but since the RB needs agreement to generate the seed for the leader+overlay, therefore newView is sent to the root_committee().
```
```python3
#######
def receive_timeout_Msgs(timeout_Msg: Timeout_Msg):
if CURRENT_VIEW > timeout_Msg.view:
return
if timeout_Msg.view <= LAST_VIEW_TIMEOUT_QC.view:
return
if not child_commitee(timeout_Msg.sender):
return
# Overlay is built if the node has not done so for the view timeout_Msg.view
# built_overlay(rb) is not defined. It takes random beacon as input and generates a new overlay.
if not Received_RB(timeout_Msg.view,rb):
built_overlay(rb)
if timeout_Msg.view>LOCAL_HIGH_QC.view:
LOCAL_HIGH_QC = timeout_Msg.high_qc
PENDING_TIMEOUTMSG_COLLECTION[timeout_Msg.view].append(timeout_Msg)
#Supermajority
if len(PENDING_TIMEOUTMSG_COLLECTION[timeout_Msg.view])== supermajority():
timeout_qc = create_timeout_qc(PENDING_TIMEOUTMSG_COLLECTION[timeout_Msg.view])
increment_view_timeout_qc(timeout_qc.view)
LAST_VIEW_TIMEOUT_QC = timeout_qc
timeout_Msg = create_timeout(CURRENT_VIEW,LOCAL_HIGH_QC, LAST_VIEW_TIMEOUT_QC)
if member_of_root():
send(timeout_qc, leader(timeout_qc.view+1))
# send(timeout_qc, child_committee())
else:
send(timeout_qc, parent_committee())
if leader(timeout_qc.view+1):
AggQC = build_AggQC(PENDING_TIMEOUTMSG_COLLECTION[timeout_Msg.view])
block = build_block(txs,CURRENT_VIEW,qc=None, AggQC)
broadcast(block)
```
```python3
def increment_view_qc (qc: Qc):
if qc.view < CURRENT_VIEW:
return false
LAST_VIEW_TIMEOUT_QC = None
start_timer(qc.view+1)
return true
```
```python3
def increment_view_timeout_qc (timeout_qc: Timeout_qc):
if timeout_qc==None or timeout_qc.view < CURRENT_VIEW:
return false
LAST_VIEW_TIMEOUT_QC = timeout_qc
start_timer(timeout_qc.view+1)
return true
```
```python3
def start_timer(next_view: int):
stop_timer(CURRENT_VIEW)
CURRENT_VIEW = next_view
timer_start(duration)
```
Reference in New Issue View Git Blame Copy Permalink