Skip to content

Consensus_Design

Jump to bottom
dabasov edited this page Oct 29, 2021 · 27 revisions

Consensus implementation

Workers

Protocol is executed through several workers, each worker is responsible for part of protocols logic

BlockWorker

BlockWorker runs main protocol loop. It is responsible for processing following messages:

  • MessageVRFShare. VRF share sent by miner
var msg = NewBlockMessage(MessageVRFShare, node.GetSender(ctx), nil, nil)
vrfs.SetParty(msg.Sender)
msg.VRFShare = vrfs
  • MessageVerify. Proposal sent for verification by leader
var msg = NewBlockMessage(MessageVerify, node.GetSender(ctx), nil, block)
  • MessageVerificationTicket. Verification sent by miner
msg := NewBlockMessage(MessageVerificationTicket, node.GetSender(ctx), nil, nil)
msg.BlockVerificationTicket = bvt
  • MessageNotarization. Notarization created by miner, light version of MessageNotarizedBlock without notarized block itself and only tickets included
var msg = NewBlockMessage(MessageNotarization, node.GetSender(ctx), nil, nil)
msg.Notarization = notarization
  • MessageNotarizedBlock. Notarized block together with notarization.
var msg = &BlockMessage{
	Sender: node.GetSender(ctx),
	Type:   MessageNotarizedBlock,
	Block:  b,
}

HandleVRFShare(ctx, bmsg)

Main goal of this stage is to create random seed during VRF process. See DKG process for more datails.

  1. When miner receives VRFShare it tries to find this round in storage and if it is not created yet creates it. We do not want to loose share in case we are delayed a little (probably at previous round) and haven't started this round yet.
  2. Miner tracks this share timeout
  3. Verifies VRF signature
  4. And checks threshold to create random seed and starts round
  5. After new round is started, if current miner is generator, it generates new proposal and sends it to all other miners
var mr = mc.getOrStartRoundNotAhead(ctx, msg.VRFShare.Round)
mr.AddTimeoutVote(vrfs.GetRoundTimeoutCount(), vrfs.GetParty().ID)
msg, err := mc.GetBlsMessageForRound(mr.Round)
dkg.VerifySignature(&share, msg, partyID)
mr.setState(RoundShareVRF)
mr.shares[share.party.GetKey()] = share

if len(shares) < blsThreshold {
	groupSignature, err = dkg.CalBlsGpSign(recSig, recFrom)
	var rbOutput = encryption.Hash(groupSignature.GetHexString())
	mr.SetVRFOutput(rbOutput)
	seed, err := strconv.ParseUint(rbo[0:16], 16, 64)
        mc.startRound(ctx, mr, seed) //generates new block if generator
}

HandleVerifyBlockMessage(ctx, bmsg)

Main goal of verification stage is to verify best ranked proposal and broadcast own verification ticket to all miners. This stage is implemented in two substages:

  • at first miner collects blocks for verification and starts the timer
  • after timer is done, miner selects top ranked collected block and votes for it

In theory, this stage should be done optimistically and if top ranked proposal is received miner should vote for it immediately and wait for delta only in case it should switch to the next rank or same ranked block is received. Instead we use dynamically calculated Delta for each waiting interval and probably should be eliminated in the future. After voting for the first block, we process every new block on the same or higher level. It is not obvious why we do not vote for every block on the same rank, since we can never create notarization here.

  1. Start round for new block if not exist (this logic might be faulty since we should know seed to verify proposed block's seed)
  2. Validate block
  3. Add this block to round as current proposed
  4. Check notarizations in case proposed block is already notarized (not sure that it is possible)
  5. Add this block to verification
  6. Set round state to RoundCollectingBlockProposals
//collect
if mr == nil { //seems not right
	mc.startRound(ctx, mr, b.GetRoundRandomSeed())
}
err := b.Validate(ctx)

if mr.GetRandomSeed() == b.GetRoundRandomSeed() {
	b = mc.AddRoundBlock(mr, b)
	mc.checkBlockNotarization(ctx, mr, b)
	return
}

vts := mr.GetVerificationTickets(b.Hash)
if len(vts) == 0 || !b.IsBlockNotarized() {
	//mc.AddToRoundVerification(ctx, mr, b)
	if !mc.ValidGenerator(mr.Round, b) {
                return
        }
        b.ComputeChainWeight()
	mr.AddProposedBlock(b)
        mc.AddRoundBlock(mr, b)

        go mc.CollectBlocksForVerification(vctx, mr)
	r.SetState(round.RoundCollectingBlockProposals)
}
  1. When timer is ready (in Delta after start) get top ranked block
  2. Verify it
  3. Broadcast verification ticket to all miners
  4. Set this block as round block
  5. Check for notarization and if it is notarized broadcast Notarization and send Notarization Block to miners
//when timer is done
	b = TopRank(r.GetBlocksByRank(blocks))
        if mc.GetCurrentRound() != r.GetRoundNumber() {
		return nil, ErrRoundMismatch
	} 
        bvt = mc.VerifyBlock(ctx, b)
	go mc.SendVerificationTicket(ctx, b, bvt)
        r.Block = b
	mc.ProcessVerifiedTicket(ctx, r, b, &bvt.VerificationTicket)

HandleVerificationTicketMessage(ctx, bmsg)

The main goal of this phase is to collect all verification tickets for current round and create notarization for verified block.

In theory, we can collect tickets for next rounds, we still do not know how to verify this block, but we can collect tickets, load block by id and create notarization for it.

  1. Miner gets or creates new round for this ticket
  2. Miner verifies tickets in some sophisticated manner
  3. Adds verification ticket to round
  4. Checks blocks notarization
    1. Sets random seed of round to new one even if it is already set
    2. Sets current round to notarized block's round if it is bigger (not sure it is possible)
    3. Broadcasts Notarization
    4. Starts new round
	var mr = mc.getOrStartRoundNotAhead(ctx, rn)
        mc.verifyTicketsWithRetry(ctx, rn, bvt.BlockID, []*block.VerificationTicket{&bvt.VerificationTicket}, 3)
	b, err := mc.GetBlock(ctx, bvt.BlockID)
	if err != nil {
		mr.AddVerificationTickets([]*block.BlockVerificationTicket{bvt})
		return
	}
	mc.AddVerificationTicket(b, vt)

	//mc.checkBlockNotarization(ctx, r, b)
        seed = b.GetRoundRandomSeed()
	mc.SetRandomSeed(r, seed)
	c.setCurrentRound(roundNumber)
	go mc.SendNotarization(context.Background(), b)
	go mc.startNextRoundNotAhead(common.GetRootContext(), r) //increments round and sends VRFShare

HandleNotarizationMessage(ctx, bmsg)

Notarization message is processed in to stages: HandleNotarizationMessage handler adds message to channel and then HandleNotarizationWorker processes messages sequentially.

The main goal of this phase is to add message to channel

mc.notarizationBlockProcessC <- not:

HandleNotarizedBlockMessage(ctx, bmsg)

The main goal of this phase is to verify notarization block and transit to the new round

  1. Get or start new round
  2. Verify all notarizations
  3. If VRF is not complete, start new round with notarized block's seed (start round will generate proposal if we are leaders, not sure it is what we want)
  4. Sets new round block
  5. Starts new round
	var mr = mc.getOrStartRoundNotAhead(ctx, nb.Round)
        err := mc.VerifyNotarization(ctx, nb, nb.GetVerificationTickets(), mr.GetRoundNumber())
	if !mr.IsVRFComplete() {
		mc.startRound(ctx, mr, nb.GetRoundRandomSeed()) //????
	}

	var b = mc.AddRoundBlock(mr, nb)
	mc.AddNotarizedBlock(ctx, mr, b)
	mc.StartNextRound(ctx, mr) // start next or skip

NotarizationProcessWorker

The main goal of this worker is to process notarizations and transfer to the new round

  1. If miner has no block, get it from network async
  2. Miner merges verification tickets from notarization and checks block for notarization itself
  3. Transit to the next round if everything is correct
	var b, err = mc.GetBlock(ctx, not.BlockID)
	if err != nil {
		go mc.GetNotarizedBlock(ctx, not.BlockID, not.Round)
		return
	}
        mc.VerifyTickets(ctx, b.Hash, vts, r.GetRoundNumber());
	mc.MergeVerificationTickets(b, vts)
        mc.AddNotarizedBlock(ctx, r, b)
        mc.SetRandomSeed(r, seed)
        go mc.SendNotarization(context.Background(), b)
        go mc.startNextRoundNotAhead(common.GetRootContext(), r) //increments round and sends VRFShare

RoundWorker

Round worker runs round timer and reacts to round timeouts accordingly. Worker is responsible for processing two main types of timeouts: soft and hard. Every conf.round_restart_mult(set to 2 by default) timeout is processed like hard, all others starting from 0 like soft.

Round worker only monitors current round and changes round to monitor every timeout. It means, that while we are in wait, it does not matter, if network make progress or not, next timer will be created only after timeout. So protocol can't guarantee that new round will timeout exactly after tick time, it can take up to 2*tick to timeout.

If current round is not created for some reason, last finalized round is used instead and current round is set to last finalized round. In general it is not a good idea to make progression backwards, but we do.

Timer

Timer is initiated with 4 seconds but after first timeout is recalculated

//SteadyStateFinalizationTimer - a metric that tracks the steady state finality time (time between two successive finalized blocks in steady state)
ssft := int(math.Ceil(chain.SteadyStateFinalizationTimer.Mean() / 1000000))
tick := conf.softto_min //softto_min default is 3000 millisecs
if tick < conf.softto_mult*ssft { //softto_mult default is 3
	tick = conf.softto_mult * ssft
}
return tick //in milliseconds

Soft timeout

Soft timeouts are handled

  1. If we were generators and proposed block, resend it
  2. If VRF share were produced resend it
if len(proposals) > 0 { // send the best block to the network
		go mc.SendBlock(context.Background(), b)
}
if r.vrfShare != nil {
	go mc.SendVRFShare(context.Background(), r.vrfShare.Clone())
}

Hard timeout

When hard timeout happens current round is restarted.

  1. Miner loads LFB from sharder if don't have one
  2. Creates round if needed and updates round seed for lfb
  3. Resend lfb to sharders if miner is ahead
  4. We are looking for the first next round to lfb, where neither we nor other miners have notarized block, or other miner's block has different to ours block seed, or notarized block has zero seed. We restart this round starting from VRF phase
mc.ensureLatestFinalizedBlocks(ctx)
if lfbr == nil {
	lfbr = mc.AddRound(mc.CreateRound(round.NewRound(lfb.Round))).(*Round)
}
if lfb.RoundRandomSeed != 0 && lfbr.RandomSeed != lfb.RoundRandomSeed {
	lfbr.SetRandomSeedForNotarizedBlock(lfb.RoundRandomSeed, 0)
}
if isAhead {
	mc.kickSharders(ctx) // not updated, kick sharders finalization
}

var xrhnb = xr.GetHeaviestNotarizedBlock()
if xrhnb == nil {
	// fetch from remote miner
	xrhnb = mc.GetHeaviestNotarizedBlock(ctx, xr)
}
if xrhnb == nil ||
	xrhnb.GetRoundRandomSeed() == 0 ||
	xrhnb.GetRoundRandomSeed() != xr.GetRandomSeed() {
	xr.Restart()
	xr.IncrementTimeoutCount(mc.getRoundRandomSeed(i-1), mc.GetMiners(i))
	mc.RedoVrfShare(ctx, xr)
}

Finalize workers

FinalizeRoundWorker

Finalize round worker listens to finalizedRoundsChannel and processes round finalizations.

  1. Computes block to finalize
  2. Collects all blocks between this block and last finalized block
  3. Performs view change
  4. Sends block for finalization
  5. Prunes chain
  6. If round of block to finalize (computed in 1) is less than last finalized block, miner reverts lfb and sets computed block to lfb.
lfb := c.ComputeFinalizedBlock(ctx, plfb.Round, r)
for b := lfb; b != nil && b.Hash != plfb.Hash; b = b.PrevBlock {
	frchain = append(frchain, b)
}
c.viewChanger.ViewChange(ctx, lfb);
c.finalizedBlocksChannel <- fb
c.PruneChain(ctx, frchain[len(frchain)-1])

FinalizedBlockWorker

  1. Sharders try to repair their chain
  2. Updates block's state from other miner or sharders if needed
  3. Saves block state changes and rebases state
  4. Updates latest finalized block
  5. Updates miners/sharder finalzied block
  6. Prunes dead blocks
fb := <-c.finalizedBlocksChannel
if fb.MagicBlock != nil && node.Self.Type == node.NodeTypeSharder {
	var err = c.repairChain(ctx, fb, bsh.SaveMagicBlock())
}
c.GetBlockStateChange(fb)
c.SaveChanges(ctx, fb)
c.rebaseState(fb)
c.SetLatestOwnFinalizedBlockRound(fb.Round)
c.SetLatestFinalizedBlock(fb)
c.SetLatestFinalizedMagicBlock(fb)
go mOrSh.UpdateFinalizedBlock(ctx, fb)
c.DeleteBlocks(deadBlocks)

Data structures

Round

Round is the main structure that holds all related to consensus protocol data.

type Round struct {
	datastore.NOIDField
	Number        int64 `json:"number"`
	RandomSeed    int64 `json:"round_random_seed"`
	Block     *block.Block `json:"-"`
	VRFOutput string       `json:"vrf_output"`
	minerPerm       []int
	state           int32
	proposedBlocks  []*block.Block
	notarizedBlocks []*block.Block
	shares          map[string]*VRFShare

	softTimeoutCount int32
	vrfStartTime     atomic.Value

	delta                 time.Duration
	verificationTickets   map[string]*block.BlockVerificationTicket
	vrfShare              *round.VRFShare

	timeoutCounter
}

type timeoutCounter struct {
	prrs int64    // previous round random seed
	perm []string // miners of this (not previous) round sorted by the seed

	count int // current round timeout

	votes map[string]int // voted miner_id -> timeout
}

Number

Number stores round number this structure is associated with. Number is set during when round is created and never changes.

RandomSeed

Random seed is generated during VRF process and is used to create miner permutation and to choose current leaders.

RBO = encryption.Hash(groupSignature.GetHexString())
RandomSeed := RBO[0:16]

Block

For generator, this is the block the miner is generating till a notarization is received. For a verifier, this is the block that is currently the best block received for verification. Once a round is finalized, this is the finalized block of the given round.

VRFOutput

Copy of RBO used for RandomSeed creation

MinerPerm

Permutation of miners for given round

State

Implementation of state machine pattern, responsible for storing round phase, one of given values:

  1. RoundShareVRF
  2. RoundVRFComplete
  3. RoundGenerating (not used)
  4. RoundGenerated (not used)
  5. RoundCollectingBlockProposals
  6. RoundStateVerificationTimedOut
  7. RoundStateFinalizing
  8. RoundStateFinalized

ProposedBlocks

All proposed blocks known for this round

NotarizedBlocks

All notarized blocks known for this round

Shares

All VRF shares collected for this round

SoftTimeoutCount

Every time round timeout happens, SoftTimeoutCount is incremented and checked for equality to round_restart_mult and if equal round is restarted.

VrfStartTime

Time when VRF process is started

TimeoutCounter

Structure used for handling round timeout logic

Delta

Delta is adaptive time interval used to collect blocks for block verification

        waitTime := config.BlockProposalMaxWaitTime
	mb := mc.GetMagicBlock(r.GetRoundNumber())
	medianTime := mb.Miners.GetMedianNetworkTime()
	generators := mc.GetGenerators(r)
	for _, g := range generators {
		sendTime := g.GetLargeMessageSendTime()
		if sendTime < medianTime {
			waitTime = time.Duration(int64(math.Round(sendTime)/1000000)) * time.Millisecond
		}
	}

	minerNT := time.Duration(int64(miner.GetLargeMessageSendTime()/1000000)) * time.Millisecond
	if minerNT >= waitTime {
		mr.delta = time.Millisecond
	} else {
		mr.delta = waitTime - minerNT
	}

VerificationTickets

All verification tickets collected for current round by miner

VrfShare

VRF Share current miner created for given round

BlockMessage

type BlockMessage struct {
	Type                    int
	Sender                  *node.Node
	Round                   *Round
	Block                   *block.Block
	BlockVerificationTicket *block.BlockVerificationTicket
	Notarization            *Notarization
	Timestamp               time.Time
	RetryCount              int8
	VRFShare                *round.VRFShare
}
Clone this wiki locally