Implementation
Author: HyperonChain Published: May 29, 2022 Updated: Aug 10, 2022
DPoS is considered to be an improved version of PoS. DPoS conducts elections at regular intervals, and then these elected nodes are responsible for block generation and mutual supervision and verification, which can greatly reduce the time for block generation and block confirmation. The problem with this election method is that the block producers will be more centralized than PoW and PoS.
The current consensus algorithm of Ethereum is PoW, and it will gradually transition to PoW + PoS in the future. At present, in order to solve the problem of excessive computing power consumption and performance, one of our attempts is to change the consensus algorithm from PoW to DPoS.
The biggest feature of the DPoS consensus algorithm is that block producers are elected by election rather than random numbers. There is no essential difference between the algorithm design and the centralized voting mechanism and the DPoS algorithm proposed by Bitshares. The only difference is that the voting process becomes a transaction. In the following, I will give you a detailed introduction to our overall process and specific implementation.
The overall process is as follows:
The algorithm implementation mainly includes two core parts:
- Block validator election
- Block validator scheduling
The first batch of block validators is designated by the genesis block, and each subsequent cycle (the cycle is defined by the specific implementation) will be re-elected at the first block at the beginning of the cycle. The validator election process is as follows:
- 1.Kick off validators who did not produce enough blocks in the previous cycle
- 2.Count the votes of candidates when the election block (the first block of each cycle) is generated, and select the top N with the highest votes as validators
- 3.Randomly scramble the order of validator blocks, and the validator produces blocks according to the random result.
The validator schedules to generate blocks according to the election results, and other nodes verify whether the block generation sequence is consistent with the election results according to the election results. If they are inconsistent, the block is considered illegal and discarded directly.
The current code of Ethereum already contains the implementation of several consensus algorithms:
PoWUse on mainnetFakePowuse in unit testsPoA(Proof of Authority)Use in testnet
In order to implement a variety of consensus algorithms in the code, Ethereum abstracts a set of consensus algorithm interfaces. To implement different consensus algorithms, only a few interfaces can be implemented. In addition, in order to avoid replaying historical data from the genesis block for each election, DPoS adds several global state trees to record the state of elections and voting, and stores the corresponding root of the tree in the block header, including:
- EpochTrie records the validator list for each epoch
- VoteTrie records the voter corresponding to the validator
- CandidateTrie records candidate list
- DelegateTrie records the list of validators and corresponding voters
- MintCntTrie records the number of blocks produced by the validator in the cycle
- 1.Interface
type Engine interface {
Author(header *types.Header) (common.Address, error)
// Verify that the block header conforms to the consensus algorithm rules
VerifyHeader(chain ChainReader, header *types.Header, seal bool) error
// Batch verify whether the block header conforms to the consensus algorithm rules
VerifyHeaders(chain ChainReader, headers []*types.Header, seals []bool) (chan<- struct{}, <-chan error)
// Verify whether the uncle block conforms to the consensus algorithm rules, DPoS has no uncle block
VerifyUncles(chain ChainReader, block *types.Block) error
// Verify that the block content conforms to the consensus algorithm rules
VerifySeal(chain ChainReader, header *types.Header) error
// Initialize block header information according to consensus algorithm rules
Prepare(chain ChainReader, header *types.Header) error
// Relevant update operations (such as block mining incentives, etc.) after the completion of the transaction in the block
Finalize(chain ChainReader, header *types.Header, state *state.StateDB, txs []*types.Transaction, uncles []*types.Header, receipts []*types.Receipt, dposContext *types.DposContext) (*types .Block, error)
// Generate a new block based on the block content generated by Prepare and Finalize and the consensus algorithm
Seal(chain ChainReader, block *types.Block, stop <-chan struct{}) (*types.Block, error)
// The API interface provided by the consensus algorithm externally
APIs(chain ChainReader) []rpc.API
}
2. Core Implementation
Let's first look at the process of packing blocks:
The miner will periodically check whether the current validator is the current node through
CheckValidatorto check whether the current validator is the current node, and if so, CreateNewWorkcreate a new block-making task through , which CreateNewWorkmainly includes three parts:Prepare(), the interface that the consensus algorithm seen above needs to implement is mainly to initialize the basic information of the block headerCommitTransactions(), mainly from the transaction pool to package transactions into blocks according to gas priceFinalize(), package the content of prepare and CommitNewWork into new blocks, and there are also functions including block reward, election, update block count, etc.
Finally, Seal will sign the new block, and then broadcast the new block to neighboring nodes. When other nodes receive the new block, they will see whether the new block should be produced by the validator according to the block signature and the election result. Compared with other consensus algorithms, the main difference between the DPoS consensus algorithm is election, so we can focus on this implementation:
func (ec *EpochContext) tryElect(genesis, parent *types.Header) error {
genesisEpoch := genesis.Time.Int64() / epochInterval
prevEpoch := parent.Time.Int64() / epochInterval
currentEpoch := ec.TimeStamp / epochInterval
....
// Calculate whether the current block and the previous block belong to the same cycle according to the time of the current block and the previous block,
// If it is the same cycle, it means that the current block is not the first block of the cycle, no need to trigger election
// If it is not the same cycle, indicating that the current block is the first block of the cycle, the election will be triggered
for i := prevEpoch; i < currentEpoch; i++ {
// If the previous cycle is not the genesis cycle, trigger the rule of kicking out candidates
// The kicking rule is mainly to see if there is a candidate block that is less than a certain threshold (50%) in the previous cycle, and if so, kick it out
if !prevEpochIsGenesis && iter.Next() {
if err := ec.kickoutCandidate(prevEpoch, prevEpochIsGenesis); err != nil {
return err
}
}
// After the candidates are counted, they are sorted according to the number of votes from high to low, and the first N are selected
// It should be noted here that there is currently no threshold for becoming a candidate, and it is easy to be maliciously attacked
votes, err := ec.countVotes()
if err != nil {
return err
}
sort.Sort(candidates)
if len(candidates) > epochSize {
candidates = candidates[:epochSize]
}
// Scramble the validator list, since the seed is composed of the hash of the parent block and the current cycle number,
// So the validator list calculated by each node will also be consistent
seed := int64(binary.LittleEndian.Uint32(crypto.Keccak512(parent.Hash().Bytes()))) + i
r := rand.New(rand.NewSource(seed))
for i := len(candidates) - 1; i > 0; i-- {
j := int(r.Int31n(int32(i + 1)))
candidates[i], candidates[j] = candidates[j], candidates[i]
}
sortedValidators := make([]common.Address, 0)
for _, candidate := range candidates {
sortedValidators = append(sortedValidators, candidate.address)
}
}
return nil
}
We call before packing each block
tryElectto see if the current block is the first block of the new cycle, and if it is the first block, we need to trigger an election. The implementation of the overall election is relatively simple, mainly to do three things:- 1.According to the block generation in the previous cycle, some candidates who were selected but did not meet the required number of blocks were kicked out
- 2.As of the previous block, the top N candidates with the highest votes are selected as validators
- 3.Shuffle the order of validators
Next look at the vote counting implementation (ignore some unimportant code):
func (ec *EpochContext) countVotes() (votes map[common.Address]*big.Int, err error) {
...
// loop through the candidate list
for existCandidate {
candidate := iterCandidate.Value
candidateAddr := common.BytesToAddress(candidate)
delegateIterator := trie.NewIterator(delegateTrie.PrefixIterator(candidate))
existDelegator := delegateIterator.Next()
...
// Traverse the list of voters corresponding to the candidate
for existDelegator {
delegator := delegateIterator.Value
score, ok := votes[candidateAddr]
if !ok {
score = new(big.Int)
}
delegatorAddr := common.BytesToAddress(delegator)
// Get the voter's balance as votes accumulated into the candidate's votes
weight := statedb.GetBalance(delegatorAddr)
score.Add(score, weight)
votes[candidateAddr] = score
existDelegator = delegateIterator.Next()
}
existCandidate = iterCandidate.Next()
}
return votes, nil
}
The logic of counting votes is also very simple:
- 1.First find out the list of candidates corresponding to voters
- 2.The balances of all voters are accumulated as votes into the candidate's total votes
Earlier we saw that in addition to the interfaces seen above, the consensus algorithm interface also requires the implementation
VerifyHeader()of several verification interfaces such VerifySeal()as VerifyUncles(), whether the content and the information of the uncle block conform to the validation rules. Due to space constraints, no detailed introduction is given here.3. Become a candidate/vote
If a node wants to become a validator, it must first become a candidate, and then others can vote for this candidate. Whether it is voting or becoming a candidate, it is actually a transaction for the node. The previous transactions were mainly transfers or contract calls, so now several transaction types are added.
const (
Binary TxType = iota // previous transfer or contract call transaction
LoginCandidate // Become a candidate
LogoutCandidate // logout candidate
Delegate // vote (authorization)
UnDelegate // Cancel voting (authorization)
)
type txdata struct {
Type TxType `json:"type" gencodec:"required"`
AccountNonce uint64 `json:"nonce" gencodec:"required"`
Price *big.Int `json:"gasPrice" gencodec:"required"`
GasLimit *big.Int `json:"gas" gencodec:"required"`
Recipient *common.Address `json:"to" rlp:"nil"` // nil means contract creation
Amount *big.Int `json:"value" gencodec:"required"`
Payload []byte `json:"input" gencodec:"required"`
// Signature values
V *big.Int `json:"v" gencodec:"required"`
R *big.Int `json:"r" gencodec:"required"`
S *big.Int `json:"s" gencodec:"required"`
// This is only used when marshaling to JSON.
Hash *common.Hash `json:"hash" rlp:"-"`
}
When a new block is packaged, all transactions in the block will be executed. If it is found that the transaction type is not the previous transfer or contract call type,
applyDposMessage will be called for processing.
func applyDposMessage(dposContext *types.DposContext, msg types.Message) error {
switch msg.Type() {
case types.LoginCandidate:
dposContext.BecomeCandidate(msg.From().Bytes())
case types.LogoutCandidate:
dposContext.KickoutCandidate(msg.From().Bytes())
case types.Delegate:
dposContext.Delegate(msg.From().Bytes(), msg.To().Bytes())
case types.UnDelegate:
dposContext.UnDelegate(msg.From().Bytes(), msg.To().Bytes())
default:
return types.ErrInvalidType
}
return nil
}
func (d *DposContext) BecomeCandidate(candidate []byte) error {
// Update the candidate tree
return d.candidateTrie.TryUpdate(candidate, candidate)
}
func (d *DposContext) Delegate(delegator, candidate []byte) error {
if !common.IsHexAddress(common.BytesToAddress(candidate).String()) {
return ErrInvalidAddress
}
// Before voting (authorization), you need to check whether the account is a candidate
if _, err := d.candidateTrie.TryGet(candidate); err != nil {
return err
}
// If the voter has voted for someone else before, cancel the previous vote first
oldCandidate, err := d.voteTrie.TryGet(delegator)
if err != nil {
if _, ok := err.(*trie.MissingNodeError); !ok {
return err
}
}
if oldCandidate != nil {
d.delegateTrie.Delete(append(oldCandidate, delegator...))
}
// Update the authorization list corresponding to the candidate
if err = d.delegateTrie.TryUpdate(append(candidate, delegator...), delegator); err != nil {
return err
}
return d.voteTrie.TryUpdate(delegator, candidate)
}
It can be seen that voting/becoming a candidate is not much different from our traditional implementation. The essence is the addition, deletion and modification of data, but the blockchain will be more complex and special than ordinary KV in data update.
Last modified 3mo ago