Near consensus mechanism

1. introduction

NEAR use PoS Consensus mechanism , Use the name NighShade The slice design of , Use the name DoomSlug Block generation mechanism .

2. Relevant definitions and symbols

To maintain consensus , The trade will be packaged into blocks . There is one. preconfigured block $G$, be called genesis block. except $G$ outside , Every block There are a link pointing to the previous block $prev(B)$, among $B$ by block, Through the link Eventually connected to $G$（ non-existent cycles）.

• $A<B$： That means $A\ne B$, And $B$ It can be done by previous block link Connect to $A$.
• $A\le B$： That means $A<B$ or $A=B$.
• $A\sim B$： That means $A<B$ or $A=B$ or $A>B$.
• $A\nsim B$： That is, not $A\sim B$.

chain $chain(T)$： Refer to a set of blocks reachable from block $T$, be called tips, namely $chain(T)=\{B|B\le T\}$. For any block $A,B$, If and only if $A\sim B$ when ,$A,B$ between a chain. here , Can become $A,B$ On the same chain .

Each block has an integer height $h(B)$. The block height is monotonically increasing , That is, for any block $B\ne G$, Yes $h(B)>h(prev(B))$. However, the block height is not required to be continuous , Such as $h(G)$ Not for 0. Every node keep track of a valid block with the largest height it knows about, which is called its head.

Blocks will be packed into epoch. On the chain , Belong to the same epoch A group of blocks forming a continuous range ： If block $A<B$ All belong to the same epoch, Then each one satisfies $A<X<B$ Block of $X$ All belong to this epoch.epoch can With sequential indices To mark ：$G$ Belong to index by 0 Of epoch; For each block $B$, It belongs to epoch index Or equal to $prev(B)$ Of epoch index, Or greater than .

Every epoch relation a set of block producers that are validating blocks in that epoch, as well as an assignment of block heights to block producers that are responsible for producing a block at that height.

Responsible for production with a height of $h$ block block producer be called block proposer at $h$.

epoch index $i\ge 2$ Of validator set and block height assignment The information will be in epoch index by $i-2$ The last block determine . about epoch index by 0 and 1 The situation of , Its validator set and block height assignment by preconfigured Of . therefore , if 2 The chain shares a epoch The last block of , Then its follow-up 2 individual epoch Have the same validator set And the same block height assignment, But for the later epoch There is no guarantee that .

curing ： if block $B$ Solidified , Then any future solidified block can only be based on $B$ Built . therefore , stay $B$ And previous block transactions will never be reverse.$final(B,T)$, among $B\le T$, signify $B$ stay $chain(T)$ It's solidified . if $final(B,T)$ It's true , Then for all $T^{\prime }\ge T$,$final(B,T^{\prime })$ It's all true .

2. Data structures

NEAR The fields related to consensus in the block header are ：

struct BlockHeader {
    
    ...
    prev_hash: BlockHash,
    height: BlockHeight,
    epoch_id: EpochId,
    last_final_block_hash: BlockHash,
    approvals: Vec<Option<Signature>>
    ...
}

In specific epoch Of block producers Will exchange many types of messages , The news related to consensus is 2 Kind of ：

• Blocks
• Approvals

The following fields are included ：

enum ApprovalInner {
    
    Endorsement(BlockHash),// by the hash of the approved block
    Skip(BlockHeight),// by the height of the approved block 
}

struct Approval {
    
    inner: ApprovalInner,
    target_height: BlockHeight,// by the specific height at which the approval can be used (an approval with a particular `target_height` can be only included in the `approvals` of a block that has `height = target_height`)
    signature: Signature,// To be right `(inner, target_height)` The signature of the 
    account_id: AccountId // by the account of the block producer who created the approval
}

3. Approvals Requirements

except genesis block Every block outside $B$ in , Both must logically contain information from block producers Of approvals, these block producers The accumulation of stake Must exceed this epoch President Zhong stake Of 2/3. stay epoch Switch when , requirement block producers The accumulation of stake Need to go beyond the next epoch total stake Of 2/3.

approval Yes 2 Types ：

• If and only if $h(B)=h(prev(B))+1$ when , by Endorsement.
• Otherwise Skip with the height of $prev(B)$.

Each... Stored in the block approval Logically for each block producer It's all the same （ except account_id and signature Different ）, therefore , Store all approvals It's redundant . In fact, the physical values are stored signatures of the approvals, The specific storage method is ：

• Get current epoch Of block producers ordered set.

If a block stay epoch The border , It also needs to include approvals form the next epoch, Therefore need add new accounts from the new epoch：

def get_accounts_for_block_ordered(h, prev_block):
    cur_epoch = get_next_block_epoch(prev_block)
    next_epoch = get_next_block_next_epoch(prev_block)

    account_ids = get_epoch_block_producers_ordered(cur_epoch)
    if next_block_needs_approvals_from_next_epoch(prev_block):
        for account_id in get_epoch_block_producers_ordered(next_epoch):
            if account_id not in account_ids:
                account_ids.append(account_id)

    return account_ids

therefore , This boundary block It contains a vector of optional signatures of the same or smaller size than the resulting set of account_ids, with each element being Noneif the approval for such account is absent, or the signature on the approval message if it is present. therefore , It is easy to reconstruct the signature from the information in the block approvals Of block producers, And verify the corresponding signature . if the vector of signature Shorter than account_ids The length of , Then the rest signatures Are assumed to be None.

4. Messages

When I received approval news , Participants deposit only the collection of approval messages in ：

def on_approval(self, approval):
    self.approvals.append(approval)

When participants receive a block, The operations related to consensus are ：

• to update head
• initialization a timer To start sending the block Of approvals to the block producers at the consecutive target_heights. The timer timeout depends on the height of the last solidified block , This information will also persisted.

def on_block(self, block):
    header = block.header

    if header.height <= self.head_height:
        return

    last_final_block = store.get_block(header.last_final_block_hash)

    self.head_height = header.height
    self.head_hash = block.hash()
    self.largest_final_height = last_final_block.height

    self.timer_height = self.head_height + 1
    self.timer_started = time.time()

    self.endorsement_pending = True

The timer will periodically check the following logic ：

def get_delay(n):
    min(MAX_DELAY, MIN_DELAY + DELAY_STEP * (n-2))

def process_timer(self):
    now = time.time()

    skip_delay = get_delay(self.timer_height - self.largest_final_height)

    if self.endorsement_pending and now > self.timer_started + ENDORSEMENT_DELAY:

        if self.head_height >= self.largest_target_height:
            self.largest_target_height = self.head_height + 1
            self.send_approval(head_height + 1)

        self.endorsement_pending = False

    if now > self.timer_started + skip_delay:
        assert not self.endorsement_pending

        self.largest_target_height = max(self.largest_target_height, self.timer_height + 1)
        self.send_approval(self.timer_height + 1)

        self.timer_started = now
        self.timer_height += 1

def send_approval(self, target_height):
    if target_height == self.head_height + 1:
        inner = Endorsement(self.head_hash)
    else:
        inner = Skip(self.head_height)

    approval = Approval(inner, target_height)
    send(approval, to_whom = get_block_proposer(self.head_hash, target_height))

among get_block_proposer Return to the next block proposer.

Simultaneous requirements ENDORSEMENT_DELAY < MIN_DELAY, Although it does not affect the correctness ,NEAR In the request ENDORSEMENT_DELAY * 2 <= MIN_DELAY.

5. Block Production

It defines how to get a certain height in a block approvals Function of ：

def get_approvals(self, target_height):
    return [approval for approval
                     in self.approvals
                     if approval.target_height == target_height and
                        (isinstance(approval.inner, Skip) and approval.prev_height == self.head_height or
                         isinstance(approval.inner, Endorsement) and approval.prev_hash == self.head_hash)]

as long as get_approvals Back to approvals Corresponding block producers The accumulated pledge amount of exceeds% of the total pledge amount 2/3, The block producer assigned this height can produce a block .

6. Curing conditions

block $B$ Solidify in $chain(T)$, among $T\ge B$, or $B=G$, or block $X\le T$ bring $B=prev(prev(X))Andh(X)=h(prev(X))+1=h(B)+2$. namely , or $B$wei genesis block, or $chain(T)$ Include at least 2 individual blocks on top of $B$, And this 3 Block （ Contains blocks $B$ Itself and its successors 2 Block ） With continuous block height .

7. epoch Switch

$epoc{h}_{length}\ge 3$ Defined a epoch The minimum length of . Assuming a epoch $e_{cur}$ Start at height $h$, next epoch by $e_{next}$.

$BP(e)$ by epoch $e$ A series of producers in .
$las{t}_{final(T)}$ by the highest final block in $chain(T)$.

Then the producer produces the approvals The rule is ：

• 1） For a height of $h(prev(B))<h+epoc{h}_{length}-3$ Block of $B$ Belong to epoch $e_{cur}$, There must be more than 2/3 Of approvals of $BP(e_{cur})$（stake-weighted）.
• 2） For a height of $h(prev(B))\ge h+epoc{h}_{length}-3$ And $h(las{t}_{final(prev(B))})<h+epoc{h}_{length}-3$ Block of $B$ Belong to epoch $e_{cur}$, Must have more than at the same time 2/3 Of approvals of $BP(e_{cur})$（stake-weighted） as well as exceed 2/3 Of approvals of $BP(e_{next})$（stake-weighted）.
• 3） For the first height $h(las{t}_{final(prev(B))})\ge h+epoc{h}_{length}-3$ block $B$ Belong to epoch $e_{next}$, There must be more than 2/3 Of approvals of $BP(e_{next})$（stake-weighted）.

8. Safety

honest block producer：

• Can never be the same prev_height Generate 2 individual endorsement（ That is, conflicting endorsements）
• Can never generate a skip message s and an endorsement $e$, bring s.prev_height < e.prev_height and s.target_height >= e.target_height（ That is, conflicting skip and endorsement）

There is a theorem ：

Inferential ：

9. Liveness

Specifically proof of liveness see NEAR The team 2020 Year paper 《Doomslug: block confirmation with single round of communication, and a finality gadget with guaranteed liveness》. The consensus here differs in that it requires 2 Consecutive have endorsements Block of . And in the paper proof It has been extended , The place of , once the delay is sufficiently long for a honest block producer to collect enough endorsements, the next block producer ought to have enough time to collect all the endorsements too.

10. Approval condition

approval condition by ：

• Within any valid block , Must contain approvals from block producers, The accumulated pledge amount exceeds this amount epoch Of the total pledge amount 2/3. For blocks $B$ And the previous block $B^{\prime }$, If and only if B.height == B'.height + 1 when ,$B$ Each of the approval It has to be for an Endorsement with the hash of $B^{\prime }$, Otherwise, it must be a Skip with the height of $B^{\prime }$.

this 2 Two conditions cannot be combined . about approval Medium endorsement, Its prev_hash Must be equal to the hash of the previous block, Otherwise, No 7 Chaste safety proof Will not pass .

about skip messages Come on , Does not require approval Medium hash matching the hash of the previous block, Because if there is malicious actor Can be created at the same height 2 Block , And distribute them to half of the block producers. Each half of block producers Will be given to the same prev_height Sending has different prev_hash Of skip messages To the future producers . If... Is required at this time skip Medium prev_hash Must strictly match the prev_hash, Then no block producer can create a new block .

Reference material

[1] NEAR Consensus mechanism
[2] What is NEAR protocol?
[3] Doomslug vs PBFT, Tendermint, and Hotstuff
[4] NEAR The team 2020 Year paper 《Doomslug: block confirmation with single round of communication, and a finality gadget with guaranteed liveness》