diff --git a/src/avalanche.cpp b/src/avalanche.cpp
index 879b95143..d8251f963 100644
--- a/src/avalanche.cpp
+++ b/src/avalanche.cpp
@@ -1,155 +1,164 @@
 // Copyright (c) 2018 The Bitcoin developers
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include "avalanche.h"
 
 #include "chain.h"
 #include "netmessagemaker.h"
 #include "scheduler.h"
 #include "validation.h"
 
+#include <boost/range/adaptor/reversed.hpp>
+
 bool AvalancheProcessor::addBlockToReconcile(const CBlockIndex *pindex) {
     return vote_records.getWriteView()
         ->insert(std::make_pair(pindex, VoteRecord()))
         .second;
 }
 
 static const VoteRecord *
 GetRecord(const RWCollection<BlockVoteMap> &vote_records,
           const CBlockIndex *pindex) {
     auto r = vote_records.getReadView();
     auto it = r->find(pindex);
     if (it == r.end()) {
         return nullptr;
     }
 
     return &it->second;
 }
 
 bool AvalancheProcessor::isAccepted(const CBlockIndex *pindex) const {
     if (auto vr = GetRecord(vote_records, pindex)) {
         return vr->isValid();
     }
 
     return false;
 }
 
 bool AvalancheProcessor::hasFinalized(const CBlockIndex *pindex) const {
     if (auto vr = GetRecord(vote_records, pindex)) {
         return vr->hasFinalized();
     }
 
     return false;
 }
 
 bool AvalancheProcessor::registerVotes(const AvalancheResponse &response) {
     const std::vector<AvalancheVote> &votes = response.GetVotes();
 
     std::map<const CBlockIndex *, AvalancheVote> responseIndex;
 
     {
         LOCK(cs_main);
         for (auto &v : votes) {
             BlockMap::iterator mi = mapBlockIndex.find(v.GetHash());
             if (mi == mapBlockIndex.end()) {
                 // This should not happen, but just in case...
                 continue;
             }
 
             responseIndex.insert(std::make_pair(mi->second, v));
         }
     }
 
     {
         // Register votes.
         auto w = vote_records.getWriteView();
         for (auto &p : responseIndex) {
             const CBlockIndex *pindex = p.first;
             const AvalancheVote &v = p.second;
 
-            w[pindex].registerVote(v.IsValid());
+            auto it = w->find(pindex);
+            if (it == w.end()) {
+                // We are not voting on that item anymore.
+                continue;
+            }
+
+            it->second.registerVote(v.IsValid());
         }
     }
 
     return true;
 }
 
 namespace {
 /**
  * Run the avalanche event loop every 10ms.
  */
 static int64_t AVALANCHE_TIME_STEP_MILLISECONDS = 10;
 /**
  * Maximum item that can be polled at once.
  */
 static size_t AVALANCHE_MAX_ELEMENT_POLL = 4096;
 }
 
 bool AvalancheProcessor::startEventLoop(CScheduler &scheduler) {
     LOCK(cs_running);
     if (running) {
         // Do not start the event loop twice.
         return false;
     }
 
     running = true;
 
     // Start the event loop.
     scheduler.scheduleEvery(
         [this]() -> bool {
             if (!stopRequest) {
                 return true;
             }
 
             LOCK(cs_running);
             running = false;
 
             cond_running.notify_all();
 
             // A stop request was made.
             return false;
         },
         AVALANCHE_TIME_STEP_MILLISECONDS);
 
     return true;
 }
 
 bool AvalancheProcessor::stopEventLoop() {
     WAIT_LOCK(cs_running, lock);
     if (!running) {
         return false;
     }
 
     // Request avalanche to stop.
     stopRequest = true;
 
     // Wait for avalanche to stop.
     cond_running.wait(lock, [this] { return !running; });
 
     stopRequest = false;
     return true;
 }
 
 std::vector<CInv> AvalancheProcessor::getInvsForNextPoll() const {
     std::vector<CInv> invs;
 
     auto r = vote_records.getReadView();
-    for (const std::pair<const CBlockIndex *, VoteRecord> &p :r) {
+    for (const std::pair<const CBlockIndex *, VoteRecord> &p :
+         boost::adaptors::reverse(r)) {
         const VoteRecord &v = p.second;
         if (v.hasFinalized()) {
             // If this has finalized, we can just skip.
             continue;
         }
 
         // We don't have a decision, we need more votes.
-        invs.push_back(CInv(MSG_BLOCK, p.first->GetBlockHash()));
+        invs.emplace_back(MSG_BLOCK, p.first->GetBlockHash());
         if (invs.size() >= AVALANCHE_MAX_ELEMENT_POLL) {
             // Make sure we do not produce more invs than specified by the
             // protocol.
             return invs;
         }
     }
 
     return invs;
 }
diff --git a/src/test/avalanche_tests.cpp b/src/test/avalanche_tests.cpp
index b5ef549f1..39ddf4535 100644
--- a/src/test/avalanche_tests.cpp
+++ b/src/test/avalanche_tests.cpp
@@ -1,215 +1,276 @@
 // Copyright (c) 2010 The Bitcoin developers
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include "avalanche.h"
 
 #include "test/test_bitcoin.h"
 
 #include <boost/test/unit_test.hpp>
 
 struct AvalancheTest {
     static std::vector<CInv> getInvsForNextPoll(const AvalancheProcessor &p) {
         return p.getInvsForNextPoll();
     }
 };
 
 BOOST_FIXTURE_TEST_SUITE(avalanche_tests, TestChain100Setup)
 
 #define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence)        \
     vr.registerVote(vote);                                                     \
     BOOST_CHECK_EQUAL(vr.isValid(), state);                                    \
     BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized);                           \
     BOOST_CHECK_EQUAL(vr.getConfidence(), confidence);
 
 BOOST_AUTO_TEST_CASE(vote_record) {
     VoteRecord vr;
 
     // Check initial state.
     BOOST_CHECK_EQUAL(vr.isValid(), false);
     BOOST_CHECK_EQUAL(vr.hasFinalized(), false);
     BOOST_CHECK_EQUAL(vr.getConfidence(), 0);
 
     // We register one vote for, which keep things at 4/4.
     REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
 
     // One more and we are at 5/3.
     REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
 
     // One more and we are at 5/3.
     REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
 
     // One more and we are at 6/2.
     REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
 
     // One more and we are at 6/2.
     REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0);
 
     // Next vote will flip state, and confidence will increase as long as we
     // vote yes.
     for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) {
         REGISTER_VOTE_AND_CHECK(vr, true, true, false, i);
     }
 
     // The next vote will finalize the decision.
     REGISTER_VOTE_AND_CHECK(vr, false, true, true,
                             AVALANCHE_FINALIZATION_SCORE);
 
     // Now that we have two no votes, confidence stop increasing.
     for (int i = 0; i < 5; i++) {
         REGISTER_VOTE_AND_CHECK(vr, false, true, true,
                                 AVALANCHE_FINALIZATION_SCORE);
     }
 
     // Next vote will flip state, and confidence will increase as long as we
     // vote no.
     for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) {
         REGISTER_VOTE_AND_CHECK(vr, false, false, false, i);
     }
 
     // The next vote will finalize the decision.
     REGISTER_VOTE_AND_CHECK(vr, true, false, true,
                             AVALANCHE_FINALIZATION_SCORE);
 }
 
 BOOST_AUTO_TEST_CASE(block_register) {
     AvalancheProcessor p;
 
     CBlock block = CreateAndProcessBlock({}, CScript());
     const uint256 blockHash = block.GetHash();
     const CBlockIndex *pindex = mapBlockIndex[blockHash];
 
     // Querying for random block returns false.
     BOOST_CHECK(!p.isAccepted(pindex));
     BOOST_CHECK(!p.hasFinalized(pindex));
 
     // Add a new block. Check it is added to the polls.
     BOOST_CHECK(p.addBlockToReconcile(pindex));
     auto invs = AvalancheTest::getInvsForNextPoll(p);
     BOOST_CHECK_EQUAL(invs.size(), 1);
     BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
     BOOST_CHECK(invs[0].hash == blockHash);
 
     // Newly added blocks are also considered rejected.
     BOOST_CHECK(!p.isAccepted(pindex));
     BOOST_CHECK(!p.hasFinalized(pindex));
 
     // Let's vote for this block a few times.
     AvalancheResponse resp{0, {AvalancheVote(0, blockHash)}};
     for (int i = 0; i < 5; i++) {
         p.registerVotes(resp);
         BOOST_CHECK(!p.isAccepted(pindex));
         BOOST_CHECK(!p.hasFinalized(pindex));
     }
 
     // Now it is accepted, but we can vote for it numerous times.
     for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) {
         p.registerVotes(resp);
         BOOST_CHECK(p.isAccepted(pindex));
         BOOST_CHECK(!p.hasFinalized(pindex));
     }
 
     // As long as it is not finalized, we poll.
     invs = AvalancheTest::getInvsForNextPoll(p);
     BOOST_CHECK_EQUAL(invs.size(), 1);
     BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
     BOOST_CHECK(invs[0].hash == blockHash);
 
     // Now finalize the decision.
     resp = {0, {AvalancheVote(1, blockHash)}};
     p.registerVotes(resp);
     BOOST_CHECK(p.isAccepted(pindex));
     BOOST_CHECK(p.hasFinalized(pindex));
 
     // Once the decision is finalized, there is no poll for it.
     invs = AvalancheTest::getInvsForNextPoll(p);
     BOOST_CHECK_EQUAL(invs.size(), 0);
 
     // Now let's undo this and finalize rejection.
     for (int i = 0; i < 5; i++) {
         p.registerVotes(resp);
         BOOST_CHECK(p.isAccepted(pindex));
         BOOST_CHECK(p.hasFinalized(pindex));
     }
 
     // Now it is rejected, but we can vote for it numerous times.
     for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) {
         p.registerVotes(resp);
         BOOST_CHECK(!p.isAccepted(pindex));
         BOOST_CHECK(!p.hasFinalized(pindex));
     }
 
     // As long as it is not finalized, we poll.
     invs = AvalancheTest::getInvsForNextPoll(p);
     BOOST_CHECK_EQUAL(invs.size(), 1);
     BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
     BOOST_CHECK(invs[0].hash == blockHash);
 
     // Now finalize the decision.
     p.registerVotes(resp);
     BOOST_CHECK(!p.isAccepted(pindex));
     BOOST_CHECK(p.hasFinalized(pindex));
 
     // Once the decision is finalized, there is no poll for it.
     invs = AvalancheTest::getInvsForNextPoll(p);
     BOOST_CHECK_EQUAL(invs.size(), 0);
 
     // Adding the block twice does nothing.
     BOOST_CHECK(!p.addBlockToReconcile(pindex));
     BOOST_CHECK(!p.isAccepted(pindex));
     BOOST_CHECK(p.hasFinalized(pindex));
 }
 
+BOOST_AUTO_TEST_CASE(multi_block_register) {
+    AvalancheProcessor p;
+    CBlockIndex indexA, indexB;
+
+    // Make sure the block has a hash.
+    CBlock blockA = CreateAndProcessBlock({}, CScript());
+    const uint256 blockHashA = blockA.GetHash();
+    const CBlockIndex *pindexA = mapBlockIndex[blockHashA];
+
+    CBlock blockB = CreateAndProcessBlock({}, CScript());
+    const uint256 blockHashB = blockB.GetHash();
+    const CBlockIndex *pindexB = mapBlockIndex[blockHashB];
+
+    // Querying for random block returns false.
+    BOOST_CHECK(!p.isAccepted(pindexA));
+    BOOST_CHECK(!p.isAccepted(pindexB));
+
+    // Start voting on block A.
+    BOOST_CHECK(p.addBlockToReconcile(pindexA));
+    auto invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 1);
+    BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
+    BOOST_CHECK(invs[0].hash == blockHashA);
+
+    AvalancheResponse resp{
+        0, {AvalancheVote(0, blockHashA), AvalancheVote(0, blockHashB)}};
+    p.registerVotes(resp);
+
+    // Start voting on block B after one vote.
+    BOOST_CHECK(p.addBlockToReconcile(pindexB));
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 2);
+
+    // Ensure B comes before A because it has accumulated more PoW.
+    BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
+    BOOST_CHECK(invs[0].hash == blockHashB);
+    BOOST_CHECK_EQUAL(invs[1].type, MSG_BLOCK);
+    BOOST_CHECK(invs[1].hash == blockHashA);
+
+    // Now it is rejected, but we can vote for it numerous times.
+    for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE + 4; i++) {
+        p.registerVotes(resp);
+    }
+
+    // Next vote will finalize block A.
+    p.registerVotes(resp);
+
+    // We do not vote on A anymore.
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 1);
+    BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
+    BOOST_CHECK(invs[0].hash == blockHashB);
+
+    // Next vote will finalize block B.
+    p.registerVotes(resp);
+
+    // There is nothing left to vote on.
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 0);
+}
+
 BOOST_AUTO_TEST_CASE(event_loop) {
     AvalancheProcessor p;
     CScheduler s;
 
     // Starting the event loop.
     BOOST_CHECK(p.startEventLoop(s));
 
     // There is one task planned in the next hour (our event loop).
     boost::chrono::system_clock::time_point start, stop;
     BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 1);
 
     // Starting twice doesn't start it twice.
     BOOST_CHECK(!p.startEventLoop(s));
 
     // Start the scheduler thread.
     std::thread schedulerThread(std::bind(&CScheduler::serviceQueue, &s));
 
     // Stop event loop.
     BOOST_CHECK(p.stopEventLoop());
 
     // We don't have any task scheduled anymore.
     BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 0);
 
     // Can't stop the event loop twice.
     BOOST_CHECK(!p.stopEventLoop());
 
     // Wait for the scheduler to stop.
     s.stop(true);
     schedulerThread.join();
 }
 
 BOOST_AUTO_TEST_CASE(destructor) {
     CScheduler s;
     boost::chrono::system_clock::time_point start, stop;
 
     // Start the scheduler thread.
     std::thread schedulerThread(std::bind(&CScheduler::serviceQueue, &s));
 
     {
         AvalancheProcessor p;
         BOOST_CHECK(p.startEventLoop(s));
         BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 1);
     }
 
     // Now that avalanche is destroyed, there is no more scheduled tasks.
     BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 0);
 
     // Wait for the scheduler to stop.
     s.stop(true);
     schedulerThread.join();
 }
 
 BOOST_AUTO_TEST_SUITE_END()