diff options
| -rw-r--r-- | include/hotstuff/consensus.h | 14 | ||||
| -rw-r--r-- | include/hotstuff/liveness.h | 148 | ||||
| -rw-r--r-- | src/consensus.cpp | 30 | ||||
| -rw-r--r-- | src/hotstuff.cpp | 2 |
4 files changed, 137 insertions, 57 deletions
diff --git a/include/hotstuff/consensus.h b/include/hotstuff/consensus.h index a99e6af..d27f8c5 100644 --- a/include/hotstuff/consensus.h +++ b/include/hotstuff/consensus.h @@ -32,13 +32,18 @@ class HotStuffCore { std::unordered_map<block_t, promise_t> qc_waiting; promise_t propose_waiting; promise_t receive_proposal_waiting; + promise_t bqc_update_waiting; + /* == feature switches == */ + /** always vote negatively, useful for some PaceMakers */ + bool neg_vote; block_t get_delivered_blk(const uint256_t &blk_hash); void sanity_check_delivered(const block_t &blk); void check_commit(const block_t &_bqc); bool update(const uint256_t &bqc_hash); + void on_bqc_update(); void on_qc_finish(const block_t &blk); - void on_propose_(const block_t &blk); + void on_propose_(const Proposal &prop); void on_receive_proposal_(const Proposal &prop); protected: @@ -127,9 +132,11 @@ class HotStuffCore { /** Get a promise resolved when the block gets a QC. */ promise_t async_qc_finish(const block_t &blk); /** Get a promise resolved when a new block is proposed. */ - promise_t async_wait_propose(); + promise_t async_wait_proposal(); /** Get a promise resolved when a new proposal is received. */ promise_t async_wait_receive_proposal(); + /** Get a promise resolved when bqc is updated. */ + promise_t async_bqc_update(); /* Other useful functions */ block_t get_genesis() { return b0; } @@ -137,6 +144,7 @@ class HotStuffCore { ReplicaID get_id() const { return id; } const std::set<block_t, BlockHeightCmp> get_tails() const { return tails; } operator std::string () const; + void set_neg_vote(bool _neg_vote) { neg_vote = _neg_vote; } }; /** Abstraction for proposal messages. */ @@ -154,7 +162,7 @@ struct Proposal: public Serializable { Proposal(): blk(nullptr), hsc(nullptr) {} Proposal(ReplicaID proposer, const uint256_t &bqc_hash, - block_t &blk, + const block_t &blk, HotStuffCore *hsc): proposer(proposer), bqc_hash(bqc_hash), diff --git a/include/hotstuff/liveness.h b/include/hotstuff/liveness.h index 0e1103a..fbf7134 100644 --- a/include/hotstuff/liveness.h +++ b/include/hotstuff/liveness.h @@ -31,7 +31,7 @@ class PaceMaker { /** Get a promise resolved when the pace maker thinks it is a *good* time * to vote for a block. The promise is resolved with the next proposer's ID * */ - virtual promise_t next_proposer(ReplicaID last_proposer) = 0; + virtual promise_t beat_resp(ReplicaID last_proposer) = 0; }; using pacemaker_bt = BoxObj<PaceMaker>; @@ -41,24 +41,64 @@ using pacemaker_bt = BoxObj<PaceMaker>; * direct parent, while including other tail blocks (up to parent_limit) as * uncles/aunts. */ class PMAllParents: public virtual PaceMaker { + block_t bqc_tail; const int32_t parent_limit; /**< maximum number of parents */ + + void reg_bqc_update() { + hsc->async_bqc_update().then([this](const block_t &bqc) { + for (const auto &blk: hsc->get_tails()) + { + block_t b; + for (b = blk; + b->get_height() > bqc->get_height(); + b = b->get_parents()[0]); + if (b == bqc && b->get_height() > bqc_tail->get_height()) + bqc_tail = b; + } + reg_bqc_update(); + }); + } + + void reg_proposal() { + hsc->async_wait_proposal().then([this](const Proposal &prop) { + if (prop.blk->get_parents()[0] == bqc_tail) + bqc_tail = prop.blk; + reg_proposal(); + }); + } + + void reg_receive_proposal() { + hsc->async_wait_receive_proposal().then([this](const Proposal &prop) { + if (prop.blk->get_parents()[0] == bqc_tail) + bqc_tail = prop.blk; + reg_receive_proposal(); + }); + } + public: PMAllParents(int32_t parent_limit): parent_limit(parent_limit) {} + void init() { + bqc_tail = hsc->get_genesis(); + reg_bqc_update(); + reg_proposal(); + reg_receive_proposal(); + } + std::vector<block_t> get_parents() override { - auto tails = hsc->get_tails(); - size_t nparents = tails.size(); + const auto &tails = hsc->get_tails(); + std::vector<block_t> parents{bqc_tail}; + auto nparents = tails.size(); if (parent_limit > 0) nparents = std::min(nparents, (size_t)parent_limit); - assert(nparents > 0); - block_t p = *tails.rbegin(); - std::vector<block_t> parents{p}; nparents--; /* add the rest of tails as "uncles/aunts" */ - while (nparents--) + for (const auto &blk: tails) { - auto it = tails.begin(); - parents.push_back(*it); - tails.erase(it); + if (blk != bqc_tail) + { + parents.push_back(blk); + if (!--nparents) break; + } } return std::move(parents); } @@ -86,17 +126,16 @@ class PMWaitQC: public virtual PaceMaker { } void update_last_proposed() { - hsc->async_wait_propose().then([this](block_t blk) { + hsc->async_wait_proposal().then([this](const Proposal &prop) { update_last_proposed(); - last_proposed = blk; + last_proposed = prop.blk; locked = false; schedule_next(); }); } public: - void init(HotStuffCore *hsc) override { - PaceMaker::init(hsc); + void init() { last_proposed = hsc->get_genesis(); locked = false; update_last_proposed(); @@ -113,7 +152,7 @@ class PMWaitQC: public virtual PaceMaker { return pm; } - promise_t next_proposer(ReplicaID last_proposer) override { + promise_t beat_resp(ReplicaID last_proposer) override { return promise_t([last_proposer](promise_t &pm) { pm.resolve(last_proposer); }); @@ -124,6 +163,11 @@ class PMWaitQC: public virtual PaceMaker { struct PaceMakerDummy: public PMAllParents, public PMWaitQC { PaceMakerDummy(int32_t parent_limit): PMAllParents(parent_limit), PMWaitQC() {} + void init(HotStuffCore *hsc) override { + PaceMaker::init(hsc); + PMAllParents::init(); + PMWaitQC::init(); + } }; /** PaceMakerDummy with a fixed proposer. */ @@ -140,7 +184,7 @@ class PaceMakerDummyFixed: public PaceMakerDummy { return proposer; } - promise_t next_proposer(ReplicaID) override { + promise_t beat_resp(ReplicaID) override { return promise_t([this](promise_t &pm) { pm.resolve(proposer); }); @@ -178,7 +222,7 @@ class PMStickyProposer: virtual public PaceMaker { /** QC timer or randomized timeout */ Event timer; block_t last_proposed; - /** the proposer it believes when it is a follower */ + /** the proposer it believes */ ReplicaID proposer; /* extra state needed for a proposer */ @@ -207,6 +251,8 @@ class PMStickyProposer: virtual public PaceMaker { last_proposed_by.clear(); } + /* helper functions for a follower */ + void reg_follower_receive_proposal() { pm_wait_receive_proposal.reject(); (pm_wait_receive_proposal = hsc->async_wait_receive_proposal()) @@ -219,13 +265,10 @@ class PMStickyProposer: virtual public PaceMaker { if (prop.proposer == proposer) { auto &qc_ref = prop.blk->get_qc_ref(); - if (last_proposed) + if (last_proposed && qc_ref != last_proposed) { - if (qc_ref != last_proposed) - { - HOTSTUFF_LOG_PROTO("proposer misbehave"); - to_candidate(); /* proposer misbehave */ - } + HOTSTUFF_LOG_PROTO("proposer misbehave"); + to_candidate(); /* proposer misbehave */ } HOTSTUFF_LOG_PROTO("proposer emits new QC"); last_proposed = prop.blk; @@ -234,14 +277,16 @@ class PMStickyProposer: virtual public PaceMaker { reg_follower_receive_proposal(); } + /* helper functions for a proposer */ + void proposer_schedule_next() { if (!pending_beats.empty() && !locked) { auto pm = pending_beats.front(); pending_beats.pop(); pm_qc_finish.reject(); - pm_qc_finish = - hsc->async_qc_finish(last_proposed).then([this, pm]() { + (pm_qc_finish = hsc->async_qc_finish(last_proposed)) + .then([this, pm]() { reset_qc_timer(); pm.resolve(proposer); }); @@ -251,43 +296,46 @@ class PMStickyProposer: virtual public PaceMaker { void reg_proposer_propose() { pm_wait_propose.reject(); - (pm_wait_propose = hsc->async_wait_propose()).then( + (pm_wait_propose = hsc->async_wait_proposal()).then( salticidae::generic_bind( &PMStickyProposer::proposer_propose, this, _1)); } - void proposer_propose(const block_t &blk) { - last_proposed = blk; + void proposer_propose(const Proposal &prop) { + last_proposed = prop.blk; locked = false; proposer_schedule_next(); reg_proposer_propose(); } - void gen() { + void propose_elect_block() { DataStream s; /* FIXME: should extra data be the voter's id? */ s << hsc->get_id(); + /* propose a block for leader election */ hsc->on_propose(std::vector<command_t>{}, get_parents(), std::move(s)); } + /* helper functions for a candidate */ + void candidate_qc_timeout() { pm_qc_finish.reject(); pm_wait_propose.reject(); - (pm_wait_propose = hsc->async_wait_propose()).then([this](const block_t &blk) { - pm_qc_finish.reject(); - pm_qc_finish = hsc->async_qc_finish(blk).then([this, blk]() { + (pm_wait_propose = hsc->async_wait_proposal()).then([this](const Proposal &prop) { + const auto &blk = prop.blk; + (pm_qc_finish = hsc->async_qc_finish(blk)).then([this, blk]() { HOTSTUFF_LOG_PROTO("collected QC for %s", std::string(*blk).c_str()); /* managed to collect a QC */ to_proposer(); - gen(); + propose_elect_block(); }); }); double t = salticidae::gen_rand_timeout(candidate_timeout); timer.del(); timer.add_with_timeout(t); HOTSTUFF_LOG_PROTO("candidate next try in %.2fs", t); - gen(); + propose_elect_block(); } void reg_candidate_receive_proposal() { @@ -299,22 +347,25 @@ class PMStickyProposer: virtual public PaceMaker { } void candidate_receive_proposal(const Proposal &prop) { - auto proposer = prop.proposer; - auto &p = last_proposed_by[proposer]; - HOTSTUFF_LOG_PROTO("got block %s from %d", std::string(*prop.blk).c_str(), proposer); + auto _proposer = prop.proposer; + auto &p = last_proposed_by[_proposer]; + HOTSTUFF_LOG_PROTO("got block %s from %d", std::string(*prop.blk).c_str(), _proposer); p.reject(); - p = hsc->async_qc_finish(prop.blk).then([this, proposer]() { - to_follower(proposer); + (p = hsc->async_qc_finish(prop.blk)).then([this, _proposer]() { + to_follower(_proposer); }); reg_candidate_receive_proposal(); } + /* role transitions */ + void to_follower(ReplicaID new_proposer) { HOTSTUFF_LOG_PROTO("new role: follower"); clear_promises(); role = FOLLOWER; proposer = new_proposer; last_proposed = nullptr; + hsc->set_neg_vote(false); timer = Event(ec, -1, 0, [this](int, short) { /* unable to get a QC in time */ to_candidate(); @@ -334,11 +385,12 @@ class PMStickyProposer: virtual public PaceMaker { role = PROPOSER; proposer = hsc->get_id(); last_proposed = nullptr; + hsc->set_neg_vote(true); timer = Event(ec, -1, 0, [this](int, short) { /* proposer unable to get a QC in time */ to_candidate(); }); - proposer_propose(hsc->get_genesis()); + proposer_propose(Proposal(-1, uint256_t(), hsc->get_genesis(), nullptr)); reset_qc_timer(); } @@ -348,6 +400,7 @@ class PMStickyProposer: virtual public PaceMaker { role = CANDIDATE; proposer = hsc->get_id(); last_proposed = nullptr; + hsc->set_neg_vote(false); timer = Event(ec, -1, 0, [this](int, short) { candidate_qc_timeout(); }); @@ -360,10 +413,7 @@ class PMStickyProposer: virtual public PaceMaker { PMStickyProposer(double qc_timeout, const EventContext &ec): qc_timeout(qc_timeout), ec(ec) {} - void init(HotStuffCore *hsc) override { - PaceMaker::init(hsc); - to_candidate(); - } + void init() { to_candidate(); } ReplicaID get_proposer() override { return proposer; @@ -384,9 +434,9 @@ class PMStickyProposer: virtual public PaceMaker { }); } - promise_t next_proposer(ReplicaID last_proposer) override { + promise_t beat_resp(ReplicaID last_proposer) override { return promise_t([this, last_proposer](promise_t &pm) { - pm.resolve(last_proposer); //role == CANDIDATE ? last_proposer : proposer); + pm.resolve(last_proposer); }); } }; @@ -394,6 +444,12 @@ class PMStickyProposer: virtual public PaceMaker { struct PaceMakerSticky: public PMAllParents, public PMStickyProposer { PaceMakerSticky(int32_t parent_limit, double qc_timeout, EventContext eb): PMAllParents(parent_limit), PMStickyProposer(qc_timeout, eb) {} + + void init(HotStuffCore *hsc) override { + PaceMaker::init(hsc); + PMAllParents::init(); + PMStickyProposer::init(); + } }; } diff --git a/src/consensus.cpp b/src/consensus.cpp index 66ce05c..c9ceb9b 100644 --- a/src/consensus.cpp +++ b/src/consensus.cpp @@ -21,6 +21,7 @@ HotStuffCore::HotStuffCore(ReplicaID id, vheight(0), priv_key(std::move(priv_key)), tails{bqc}, + neg_vote(false), id(id), storage(new EntityStorage()) { storage->add_blk(b0); @@ -103,7 +104,10 @@ bool HotStuffCore::update(const uint256_t &bqc_hash) { if (_bqc->qc_ref == nullptr) return false; check_commit(_bqc); if (_bqc->qc_ref->height > bqc->qc_ref->height) + { bqc = _bqc; + on_bqc_update(); + } return true; } @@ -141,7 +145,7 @@ void HotStuffCore::on_propose(const std::vector<command_t> &cmds, on_receive_vote( Vote(id, bqc->get_hash(), bnew_hash, create_part_cert(*priv_key, bnew_hash), this)); - on_propose_(bnew); + on_propose_(prop); /* boradcast to other replicas */ do_broadcast_proposal(prop); } @@ -173,7 +177,7 @@ void HotStuffCore::on_receive_proposal(const Proposal &prop) { Vote(id, bqc->get_hash(), bnew->get_hash(), - (opinion ? + ((opinion && !neg_vote) ? create_part_cert(*priv_key, bnew->get_hash()) : nullptr), this)); @@ -262,9 +266,9 @@ void HotStuffCore::on_qc_finish(const block_t &blk) { } } -promise_t HotStuffCore::async_wait_propose() { - return propose_waiting.then([](const block_t &blk) { - return blk; +promise_t HotStuffCore::async_wait_proposal() { + return propose_waiting.then([](const Proposal &prop) { + return prop; }); } @@ -274,10 +278,16 @@ promise_t HotStuffCore::async_wait_receive_proposal() { }); } -void HotStuffCore::on_propose_(const block_t &blk) { +promise_t HotStuffCore::async_bqc_update() { + return bqc_update_waiting.then([bqc=this->bqc]() { + return bqc; + }); +} + +void HotStuffCore::on_propose_(const Proposal &prop) { auto t = std::move(propose_waiting); propose_waiting = promise_t(); - t.resolve(blk); + t.resolve(prop); } void HotStuffCore::on_receive_proposal_(const Proposal &prop) { @@ -286,6 +296,12 @@ void HotStuffCore::on_receive_proposal_(const Proposal &prop) { t.resolve(prop); } +void HotStuffCore::on_bqc_update() { + auto t = std::move(bqc_update_waiting); + bqc_update_waiting = promise_t(); + t.resolve(); +} + HotStuffCore::operator std::string () const { DataStream s; s << "<hotstuff " diff --git a/src/hotstuff.cpp b/src/hotstuff.cpp index 3626f9d..e1e2f81 100644 --- a/src/hotstuff.cpp +++ b/src/hotstuff.cpp @@ -417,7 +417,7 @@ void HotStuffBase::do_broadcast_proposal(const Proposal &prop) { } void HotStuffBase::do_vote(ReplicaID last_proposer, const Vote &vote) { - pmaker->next_proposer(last_proposer) + pmaker->beat_resp(last_proposer) .then([this, vote](ReplicaID proposer) { if (proposer == get_id()) on_receive_vote(vote); |