Miner implementation does not correctly walk mempool

[kantai]

In order to "walk" the mempool and find transactions for inclusion in a block, a miner does the following (starting at block height n)

1. Asks the mempool DB for all (consensus_hash, block_hash) pairs at height n
2. Figures out the consensus_hash, block_hash pair for the current chain's view of height n
3. Finds the matching pair between 1 and 2, and then fetches all transactions accepted into the mempool at that block, if there's no such matching pair, stop walking
4. Attempts to include transactions from 3 in the block
5. Repeat from 1 at height n-1 until out of transactions or height = 0

Steps 1->2->3 have a (breaking) logic bug: if the mempool db doesn't have any entries for a block's ancestor, then the walk stops. This, however, is entirely possible, and would be expected to occur 50% of the time if there is a short-lived fork and this has happened a few times over the course of the Stacks chain so far.

For example, at block 1631:

In step (1), the mempool will only ever have entries for a given block height on the fork it followed (in 1631's case, the a node believed 51d33db6d82374122349314a1c582909dca473ce/adfa719db9a3ccb47b21e55a8a7f60d0bac4a51d9a266851ea8c2a41df49ae70 to be the chain tip).

But, 1632 is mined by someone with a different height 1631 block. 1632's parent block is 3152453237a1a030320b168d87555c18a6942893/8819f44ab05b1130cd053052400bcaaa64a27a58dbc55db600c8dbe878ae5428

Once this occurs, any node that had a different 1631 height view will never consider for inclusion a transaction that they first received earlier than that block height.

Fixing this is not consensus-breaking, but would require miners themselves to upgrade.

[kantai]

In the fix/mempool-walks, you can experiment with a local chain state to see this activity in action (you'll need a develop chain state, because the database schema changed):

$ rm -r /tmp/stacks-node.clone/ && cp -r /tmp/stacks-node /tmp/stacks-node.clone && BAD_BEHAVIOR=1 ./target/debug/blockstack-core try-mine /tmp/stacks-node.clone
INFO [1611933620.471113] [src/chainstate/stacks/miner.rs:671] [main] Include tx 585345aa581299bd674040ace226d2ed81d4cf153888fc6b6fb91bfb790c54d7 (Coinbase) in anchor block
WARN [1611933620.500962] [src/chainstate/stacks/miner.rs:1334] [main] Failed to apply tx 0ce01ed2760575e764d52184953644c22687246778474b062600055f11003f5a: ClarityError(Interpreter(Interpreter(InsufficientBalance)))
WARN [1611933620.561175] [src/chainstate/stacks/miner.rs:1334] [main] Failed to apply tx a1a6741d2d506ff0c3b3e9eeb82e6b628041b2ab58ddb5f2c48a1eb46fd7584e: ClarityError(Interpreter(Interpreter(InsufficientBalance)))
INFO [1611933621.078429] [src/chainstate/stacks/miner.rs:671] [main] Include tx f444c2cbae28a83e64db7cbee544b898c7a7e27d676c01c7f460f0fecdc8b79c (TokenTransfer) in anchor block
INFO [1611933621.113587] [src/chainstate/stacks/miner.rs:671] [main] Include tx 93c5307d1444504ea81d8c47afb2bfcfcfdf26e88eb70bec4bb19bbf82575758 (TokenTransfer) in anchor block
INFO [1611933621.137045] [src/chainstate/stacks/miner.rs:671] [main] Include tx 428c874d2711f2e1343b6dc521f84671ac55207c93d5930aa1e7631a2cd61ca7 (TokenTransfer) in anchor block
INFO [1611933621.179936] [src/chainstate/stacks/miner.rs:671] [main] Include tx 88aed0de5a55814a858ce8269b8e5e2342a0a6eeabe1cdaa19a703a60733abef (TokenTransfer) in anchor block
INFO [1611933621.214277] [src/chainstate/stacks/miner.rs:671] [main] Include tx bed39b0932dc31ef105364e8665db31e9dba6563306517de2a32788eddfe6e68 (TokenTransfer) in anchor block
INFO [1611933621.242159] [src/chainstate/stacks/miner.rs:671] [main] Include tx c6fb69142772364cf8cb97cf27ae4b7fe379c0181621998a8a691f3e0a008709 (TokenTransfer) in anchor block
INFO [1611933621.268353] [src/chainstate/stacks/miner.rs:671] [main] Include tx f8e01b54435e0d28d55bcc7dd6149feafbe95cade805dd25165f3fb9db8bdc1b (TokenTransfer) in anchor block
INFO [1611933621.307402] [src/chainstate/stacks/miner.rs:671] [main] Include tx fea43892df9bebf3e1220a008bb6a7d60eab68a9446812f6f374f09a3dc7e60d (TokenTransfer) in anchor block
INFO [1611933621.320928] [src/chainstate/stacks/miner.rs:671] [main] Include tx e5dc489fd570681ba80806e6a768b500e6ebec697d4edffcb38b200a7a43cdda (TokenTransfer) in anchor block
INFO [1611933621.357101] [src/chainstate/stacks/miner.rs:671] [main] Include tx 0dadff86b5a3c7781f76d62759498eda6fe6c3e70fc107cbd8a6c9d19e7f25c0 (TokenTransfer) in anchor block
INFO [1611933622.707365] [src/chainstate/stacks/miner.rs:845] [main] Miner: mined anchored block fa4d9daec41066d135d88cf308b00d066f990bc78da84bfa7189ebf06e6aa6a9 with 11 txs, parent block 0068f09215dc7d514b691fde8ae29372a8b178cf851ce2076a22e6f87ad1e11c, state root = ab8ba40ce2959fd5e1a5b7e37a771391a32497aa6d8b6f6cc42bc2eaa6d155c8
Successfully mined block @ height = 1715

$ rm -r /tmp/stacks-node.clone/ && cp -r /tmp/stacks-node /tmp/stacks-node.clone && MEMPOOL_BAD_BEHAVIOR=1 ./target/debug/blockstack-core try-mine /tmp/stacks-node.clone
INFO [1611933636.866913] [src/chainstate/stacks/miner.rs:671] [main] Include tx d7f86519738c58b29317870a6a3bbb7f4f8847475203ecdc87e93aed051c3eeb (Coinbase) in anchor block
WARN [1611933636.896731] [src/chainstate/stacks/miner.rs:1334] [main] Failed to apply tx 0ce01ed2760575e764d52184953644c22687246778474b062600055f11003f5a: ClarityError(Interpreter(Interpreter(InsufficientBalance)))
WARN [1611933636.957009] [src/chainstate/stacks/miner.rs:1334] [main] Failed to apply tx a1a6741d2d506ff0c3b3e9eeb82e6b628041b2ab58ddb5f2c48a1eb46fd7584e: ClarityError(Interpreter(Interpreter(InsufficientBalance)))
WARN [1611933637.093556] [src/core/mempool.rs:590] [main] Stopping mempool walk because no mempool entries at height = 1682
INFO [1611933637.123276] [src/chainstate/stacks/miner.rs:845] [main] Miner: mined anchored block 4d03f36f40e35f70c0091370f47d3b5c3e09243a92c7cdb1a0c68e5d0760b583 with 1 txs, parent block 0068f09215dc7d514b691fde8ae29372a8b178cf851ce2076a22e6f87ad1e11c, state root = 76948ff7698872c05840264d30451ca8c5ce4454d138d6fb811392dc4a583783
Successfully mined block @ height = 1715