Skip to content

LLR

Jump to bottom
Egor Lysenko edited this page Mar 5, 2022 · 3 revisions

Light Lachesis Repeater (LLR)

Light Lachesis Repeater (LLR) is a non-BFT PoS auxiliary consensus algorithm which is interconnected with the Lachesis aBFT consensus algorithm.

The main purpose of LLR is to allow light stateless syncing, which Lachesis cannot offer.

LLR can be deployed only in conjunction with a BFT consensus algorithm.

Properties of the algorithm:

  • LLR consensus finality cannot be overridden, assuming that less than 1/3W of validators are Byzantine. Lachesis' finality is required to guarantee the property.
  • LLR consensus liveness cannot be halted if more than 1/3W of validators are honest and online. Yet, Lachesis liveness is required for LLR liveness, which has a requirement of more than 2/3W of honest and online validators.
  • LLR and Lachesis share the same validators group in each epoch.
  • Archiving finality for a block/epoch using LLR consensus has a complexity of O(n) operations and messages, where n is a number of validators in an epoch. In a base case scenario, it's proportional to a number of top 1/3W+1 validators.
  • Published LLR doublesign/wrongsign cannot escape slashing unless passed more than 32768 epochs since the message (MaxLiableEpochs) or validator (and his delegators) has withdrawn stake (7 days of delay) or Lachesis is censored.
  • LLR client must download and verify each epoch, but not necessarily each block. It's possible to download and verify only needed blocks.
  • LLR votes are embedded into Lachesis consensus messages (LLR votes don't increase number of signatures to verify for Lachesis clients).

LLR messages

Epoch record
type LlrFullEpochRecord struct {
	BlockState BlockState
	EpochState EpochState
}

Epoch record contains all necessary information to process Lachesis events and blocks of the epoch, including EVM state root but excluding EVM state. In go-opera, this information is encapsulated into 2 structures - BlockState (updates in every block) and EpochState (updates in every epoch).

LLR depends on the following information from epoch record:

  • Validators group of the epoch
  • First block number of the epoch

This record is critical for snapsync, which needs it to:

  • Obtain state root of a first block in the epoch for EVM state download
  • Start Lachesis fullsync after EVM state download is complete

The record has a size of O(n), where n is the number of validators in the epoch.

Epoch record may be processed either if it received 1/3W+1 votes or if it's included into genesis state.

Epoch vote message
type LlrEpochVote struct {
	Epoch idx.Epoch
	Vote  hash.Hash
}

This message expresses the statement:

  • Epoch record of Epoch has hash=Vote

Epoch vote for Epoch is processed with weights pf validators group in Epoch-1. Thus, epoch vote may be processed only after epoch record for Epoch-1 was processed.

Block record
type LlrFullBlockRecord struct {
	Atropos  hash.Event
	Root     hash.Hash
	Txs      types.Transactions
	Receipts []*types.ReceiptForStorage
	Time     inter.Timestamp
	GasUsed  uint64
}

Block record contains information about a block, where Root is a state root after execution of the block.

Block record for block B+N may be synced before block B.

Block record may be processed either if it received 1/3W+1 votes or if it's included into genesis state.

Block votes message
type LlrBlockVotes struct {
	Start idx.Block
	Epoch idx.Epoch
	Votes []hash.Hash
}

The message expresses 2 statements:

  • Blocks [Start, Start + len(Votes) - 1] have the epoch=Epoch
  • Blocks [Start, Start + len(Votes) - 1] have record hashes as in Votes

The message may contain up to 64 votes.

Start must be not lower than blocks height in processed epoch record for Epoch. Start + len(Votes) - 1 must be smaller than MaxBlocksPerEpoch + blocks height in processed epoch record for Epoch.

Block vote for Epoch is processed with weights pf validators group in Epoch. Thus, block vote may be processed only after epoch record for Epoch was processed.

Types of misbehaviour proofs

  1. BlockVoteDoublesign [Pair of doublesigned block votes]: This pair contains different record hashes for the same block from the same validator. Epoch must be not older than MaxLiableEpochs.
  2. WrongBlockVote (Record) [Pair of the same wrongsigned block votes (same record hashes) from different validators]: "Wrong" means record hash doesn't match to Lachesis' on-chain valuem which is evaluated on-chain during MPs processing of a block. It requires 2 votes from different validators to prevent slashing due to emitting a wrong vote after a singular hardware/software failure. Epoch must be not older than MaxLiableEpochs.
  3. WrongBlockVote (Epoch) [Pair of the same wrongsigned block votes (same epochs) from different validators]: "Wrong" means vote's block epoch doesn't match to Lachesis' on-chain value, which is evaluated on-chain during MPs processing of a block. It requires 2 votes from different validators to prevent slashing due to emitting a wrong vote after a singular hardware/software failure. Epoch must be not older than MaxLiableEpochs.
  4. EpochVoteDoublesign [Pair of doublesigned epoch votes]: This pair contains different record hashes for the same epoch from the same validator. Epoch must be not older than MaxLiableEpochs.
  5. WrongEpochVote [Pair of the same wrongsigned epoch votes from different validators]: "Wrong" means record hash doesn't match to Lachesis' on-chain value, which is evaluated on-chain during MPs processing of a block. It requires 2 votes from different validators to prevent slashing due to emitting a wrong vote after a singular hardware/software failure. Epoch must be not older than MaxLiableEpochs.

LLR protocol outline

Similarly to DAG streams, LLR indexes all messages lexicographically and streams batches of continuous data from peers.

Epoch pack is a container of all epoch votes known by peer for the epoch and an epoch record.

Downloading of all messages (block votes, block records, and epoch votes/record combined into epoch pack) is done in parallel, with the following dependencies:

  • Block votes are downloaded from lowest non-decided block number until lowest non-decided epoch number (not including)
  • Block records are downloaded from lowest non-downloaded block number until lowest non-decided block number (not including)
  • Epoch packs are downloaded from min(lowest non-decided epoch, lowest non-downloaded epoch) until infinity

Attacks

Bribing past validators

An attacker may buy private keys of either:

  • old validators who have already withdrawn stake
  • active validators with a condition that misbehaviour will be done only in epochs which are at least MaxLiableEpochs old.

This way, the attacker will escape slashing by construction of the attack. Yet, it implies that misbehaviour is done in old epochs, which limits the damage:

  • LLR voting is irreversible locally. Even if a different record hash gets more weight, node will continue to accept only the first confirmed record hash. Thus, this attack will affect only nodes that were syncing from scratch the affected epoch during or after the attack.
  • Periodically recent epochs get included into new genesis files (more often than MaxLiableEpochs). If an attack will breach voting for a past epoch and node is syncing the said epoch for the first time, it won't affect the node if it uses a genesis file where the affected epoch is included into genesis state.
  • Epoch is allowed to contain no more than MaxBlocksPerEpoch blocks. Thus, it won't be possible to breach voting for a recent block by stating that it's a part of an old non-liable epoch.
Clone this wiki locally