diff options
Diffstat (limited to 'vendor/github.com/dexon-foundation/dexon-consensus/core/agreement.go')
-rw-r--r-- | vendor/github.com/dexon-foundation/dexon-consensus/core/agreement.go | 492 |
1 files changed, 492 insertions, 0 deletions
diff --git a/vendor/github.com/dexon-foundation/dexon-consensus/core/agreement.go b/vendor/github.com/dexon-foundation/dexon-consensus/core/agreement.go new file mode 100644 index 000000000..8741baf10 --- /dev/null +++ b/vendor/github.com/dexon-foundation/dexon-consensus/core/agreement.go @@ -0,0 +1,492 @@ +// Copyright 2018 The dexon-consensus Authors +// This file is part of the dexon-consensus library. +// +// The dexon-consensus library is free software: you can redistribute it +// and/or modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation, either version 3 of the License, +// or (at your option) any later version. +// +// The dexon-consensus library is distributed in the hope that it will be +// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser +// General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the dexon-consensus library. If not, see +// <http://www.gnu.org/licenses/>. + +package core + +import ( + "fmt" + "math" + "sync" + "time" + + "github.com/dexon-foundation/dexon-consensus/common" + "github.com/dexon-foundation/dexon-consensus/core/types" +) + +// Errors for agreement module. +var ( + ErrNotInNotarySet = fmt.Errorf("not in notary set") + ErrIncorrectVoteSignature = fmt.Errorf("incorrect vote signature") +) + +// ErrFork for fork error in agreement. +type ErrFork struct { + nID types.NodeID + old, new common.Hash +} + +func (e *ErrFork) Error() string { + return fmt.Sprintf("fork is found for %s, old %s, new %s", + e.nID.String(), e.old, e.new) +} + +// ErrForkVote for fork vote error in agreement. +type ErrForkVote struct { + nID types.NodeID + old, new *types.Vote +} + +func (e *ErrForkVote) Error() string { + return fmt.Sprintf("fork vote is found for %s, old %s, new %s", + e.nID.String(), e.old, e.new) +} + +func newVoteListMap() []map[types.NodeID]*types.Vote { + listMap := make([]map[types.NodeID]*types.Vote, types.MaxVoteType) + for idx := range listMap { + listMap[idx] = make(map[types.NodeID]*types.Vote) + } + return listMap +} + +// agreementReceiver is the interface receiving agreement event. +type agreementReceiver interface { + ProposeVote(vote *types.Vote) + ProposeBlock() common.Hash + // ConfirmBlock is called with lock hold. User can safely use all data within + // agreement module. + ConfirmBlock(common.Hash, map[types.NodeID]*types.Vote) + PullBlocks(common.Hashes) +} + +type pendingBlock struct { + block *types.Block + receivedTime time.Time +} + +type pendingVote struct { + vote *types.Vote + receivedTime time.Time +} + +// agreementData is the data for agreementState. +type agreementData struct { + recv agreementReceiver + + ID types.NodeID + leader *leaderSelector + lockValue common.Hash + lockRound uint64 + period uint64 + requiredVote int + votes map[uint64][]map[types.NodeID]*types.Vote + lock sync.RWMutex + blocks map[types.NodeID]*types.Block + blocksLock sync.Mutex +} + +// agreement is the agreement protocal describe in the Crypto Shuffle Algorithm. +type agreement struct { + state agreementState + data *agreementData + aID types.Position + notarySet map[types.NodeID]struct{} + hasOutput bool + lock sync.RWMutex + pendingBlock []pendingBlock + pendingVote []pendingVote + candidateBlock map[common.Hash]*types.Block + fastForward chan uint64 + authModule *Authenticator +} + +// newAgreement creates a agreement instance. +func newAgreement( + ID types.NodeID, + recv agreementReceiver, + notarySet map[types.NodeID]struct{}, + leader *leaderSelector, + authModule *Authenticator) *agreement { + agreement := &agreement{ + data: &agreementData{ + recv: recv, + ID: ID, + leader: leader, + }, + candidateBlock: make(map[common.Hash]*types.Block), + fastForward: make(chan uint64, 1), + authModule: authModule, + } + agreement.stop() + return agreement +} + +// restart the agreement +func (a *agreement) restart( + notarySet map[types.NodeID]struct{}, aID types.Position) { + + func() { + a.lock.Lock() + defer a.lock.Unlock() + a.data.lock.Lock() + defer a.data.lock.Unlock() + a.data.blocksLock.Lock() + defer a.data.blocksLock.Unlock() + a.data.votes = make(map[uint64][]map[types.NodeID]*types.Vote) + a.data.votes[1] = newVoteListMap() + a.data.period = 1 + a.data.blocks = make(map[types.NodeID]*types.Block) + a.data.requiredVote = len(notarySet)/3*2 + 1 + a.data.leader.restart() + a.data.lockValue = nullBlockHash + a.data.lockRound = 1 + a.fastForward = make(chan uint64, 1) + a.hasOutput = false + a.state = newInitialState(a.data) + a.notarySet = notarySet + a.candidateBlock = make(map[common.Hash]*types.Block) + a.aID = *aID.Clone() + }() + + if isStop(aID) { + return + } + + expireTime := time.Now().Add(-10 * time.Second) + replayBlock := make([]*types.Block, 0) + func() { + a.lock.Lock() + defer a.lock.Unlock() + newPendingBlock := make([]pendingBlock, 0) + for _, pending := range a.pendingBlock { + if aID.Newer(&pending.block.Position) { + continue + } else if pending.block.Position == aID { + replayBlock = append(replayBlock, pending.block) + } else if pending.receivedTime.After(expireTime) { + newPendingBlock = append(newPendingBlock, pending) + } + } + a.pendingBlock = newPendingBlock + }() + + replayVote := make([]*types.Vote, 0) + func() { + a.lock.Lock() + defer a.lock.Unlock() + newPendingVote := make([]pendingVote, 0) + for _, pending := range a.pendingVote { + if aID.Newer(&pending.vote.Position) { + continue + } else if pending.vote.Position == aID { + replayVote = append(replayVote, pending.vote) + } else if pending.receivedTime.After(expireTime) { + newPendingVote = append(newPendingVote, pending) + } + } + a.pendingVote = newPendingVote + }() + + for _, block := range replayBlock { + a.processBlock(block) + } + + for _, vote := range replayVote { + a.processVote(vote) + } +} + +func (a *agreement) stop() { + a.restart(make(map[types.NodeID]struct{}), types.Position{ + ChainID: math.MaxUint32, + }) +} + +func isStop(aID types.Position) bool { + return aID.ChainID == math.MaxUint32 +} + +// clocks returns how many time this state is required. +func (a *agreement) clocks() int { + return a.state.clocks() +} + +// pullVotes returns if current agreement requires more votes to continue. +func (a *agreement) pullVotes() bool { + return a.state.state() == statePullVote +} + +// agreementID returns the current agreementID. +func (a *agreement) agreementID() types.Position { + a.lock.RLock() + defer a.lock.RUnlock() + return a.aID +} + +// nextState is called at the specific clock time. +func (a *agreement) nextState() (err error) { + a.state, err = a.state.nextState() + return +} + +func (a *agreement) sanityCheck(vote *types.Vote) error { + if _, exist := a.notarySet[vote.ProposerID]; !exist { + return ErrNotInNotarySet + } + ok, err := verifyVoteSignature(vote) + if err != nil { + return err + } + if !ok { + return ErrIncorrectVoteSignature + } + return nil +} + +func (a *agreement) checkForkVote(vote *types.Vote) error { + if err := func() error { + a.data.lock.RLock() + defer a.data.lock.RUnlock() + if votes, exist := a.data.votes[vote.Period]; exist { + if oldVote, exist := votes[vote.Type][vote.ProposerID]; exist { + if vote.BlockHash != oldVote.BlockHash { + return &ErrForkVote{vote.ProposerID, oldVote, vote} + } + } + } + return nil + }(); err != nil { + return err + } + return nil +} + +// prepareVote prepares a vote. +func (a *agreement) prepareVote(vote *types.Vote) (err error) { + vote.Position = a.agreementID() + err = a.authModule.SignVote(vote) + return +} + +// processVote is the entry point for processing Vote. +func (a *agreement) processVote(vote *types.Vote) error { + a.lock.Lock() + defer a.lock.Unlock() + if err := a.sanityCheck(vote); err != nil { + return err + } + if vote.Position != a.aID { + // Agreement module has stopped. + if !isStop(a.aID) { + if a.aID.Newer(&vote.Position) { + return nil + } + } + a.pendingVote = append(a.pendingVote, pendingVote{ + vote: vote, + receivedTime: time.Now().UTC(), + }) + return nil + } + if err := a.checkForkVote(vote); err != nil { + return err + } + + a.data.lock.Lock() + defer a.data.lock.Unlock() + if _, exist := a.data.votes[vote.Period]; !exist { + a.data.votes[vote.Period] = newVoteListMap() + } + a.data.votes[vote.Period][vote.Type][vote.ProposerID] = vote + if !a.hasOutput && vote.Type == types.VoteCom { + if hash, ok := a.data.countVoteNoLock(vote.Period, vote.Type); ok && + hash != skipBlockHash { + a.hasOutput = true + a.data.recv.ConfirmBlock(hash, + a.data.votes[vote.Period][types.VoteCom]) + return nil + } + } else if a.hasOutput { + return nil + } + + // Check if the agreement requires fast-forwarding. + if len(a.fastForward) > 0 { + return nil + } + if vote.Type == types.VotePreCom { + if hash, ok := a.data.countVoteNoLock(vote.Period, vote.Type); ok && + hash != skipBlockHash { + // Condition 1. + if a.data.period >= vote.Period && vote.Period > a.data.lockRound && + vote.BlockHash != a.data.lockValue { + a.data.lockValue = hash + a.data.lockRound = vote.Period + a.fastForward <- a.data.period + 1 + return nil + } + // Condition 2. + if vote.Period > a.data.period { + a.data.lockValue = hash + a.data.lockRound = vote.Period + a.fastForward <- vote.Period + return nil + } + } + } + // Condition 3. + if vote.Type == types.VoteCom && vote.Period >= a.data.period && + len(a.data.votes[vote.Period][types.VoteCom]) >= a.data.requiredVote { + hashes := common.Hashes{} + addPullBlocks := func(voteType types.VoteType) { + for _, vote := range a.data.votes[vote.Period][voteType] { + if vote.BlockHash == nullBlockHash || vote.BlockHash == skipBlockHash { + continue + } + if _, found := a.findCandidateBlockNoLock(vote.BlockHash); !found { + hashes = append(hashes, vote.BlockHash) + } + } + } + addPullBlocks(types.VoteInit) + addPullBlocks(types.VotePreCom) + addPullBlocks(types.VoteCom) + if len(hashes) > 0 { + a.data.recv.PullBlocks(hashes) + } + a.fastForward <- vote.Period + 1 + return nil + } + return nil +} + +func (a *agreement) done() <-chan struct{} { + a.lock.Lock() + defer a.lock.Unlock() + a.data.lock.Lock() + defer a.data.lock.Unlock() + ch := make(chan struct{}, 1) + if a.hasOutput { + ch <- struct{}{} + } else { + select { + case period := <-a.fastForward: + if period <= a.data.period { + break + } + a.data.setPeriod(period) + a.state = newPreCommitState(a.data) + ch <- struct{}{} + default: + } + } + return ch +} + +// processBlock is the entry point for processing Block. +func (a *agreement) processBlock(block *types.Block) error { + a.lock.Lock() + defer a.lock.Unlock() + a.data.blocksLock.Lock() + defer a.data.blocksLock.Unlock() + + if block.Position != a.aID { + // Agreement module has stopped. + if !isStop(a.aID) { + if a.aID.Newer(&block.Position) { + return nil + } + } + a.pendingBlock = append(a.pendingBlock, pendingBlock{ + block: block, + receivedTime: time.Now().UTC(), + }) + return nil + } + if b, exist := a.data.blocks[block.ProposerID]; exist { + if b.Hash != block.Hash { + return &ErrFork{block.ProposerID, b.Hash, block.Hash} + } + return nil + } + if err := a.data.leader.processBlock(block); err != nil { + return err + } + a.data.blocks[block.ProposerID] = block + a.addCandidateBlockNoLock(block) + return nil +} + +func (a *agreement) addCandidateBlock(block *types.Block) { + a.lock.Lock() + defer a.lock.Unlock() + a.addCandidateBlockNoLock(block) +} + +func (a *agreement) addCandidateBlockNoLock(block *types.Block) { + a.candidateBlock[block.Hash] = block +} + +func (a *agreement) findCandidateBlock(hash common.Hash) (*types.Block, bool) { + a.lock.RLock() + defer a.lock.RUnlock() + return a.findCandidateBlockNoLock(hash) +} + +func (a *agreement) findCandidateBlockNoLock( + hash common.Hash) (*types.Block, bool) { + b, e := a.candidateBlock[hash] + return b, e +} +func (a *agreementData) countVote(period uint64, voteType types.VoteType) ( + blockHash common.Hash, ok bool) { + a.lock.RLock() + defer a.lock.RUnlock() + return a.countVoteNoLock(period, voteType) +} + +func (a *agreementData) countVoteNoLock( + period uint64, voteType types.VoteType) (blockHash common.Hash, ok bool) { + votes, exist := a.votes[period] + if !exist { + return + } + candidate := make(map[common.Hash]int) + for _, vote := range votes[voteType] { + if _, exist := candidate[vote.BlockHash]; !exist { + candidate[vote.BlockHash] = 0 + } + candidate[vote.BlockHash]++ + } + for candidateHash, votes := range candidate { + if votes >= a.requiredVote { + blockHash = candidateHash + ok = true + return + } + } + return +} + +func (a *agreementData) setPeriod(period uint64) { + for i := a.period + 1; i <= period; i++ { + if _, exist := a.votes[i]; !exist { + a.votes[i] = newVoteListMap() + } + } + a.period = period +} |