add(mempool): Verify transactions with unmined inputs in the mempool

[arya2]

Motivation

We want to verify transactions in the mempool that spend the transparent outputs of other transactions in the mempool.

Closes #8777.

Solution

• Adds a handle to the mempool service in the transaction verifier
• Adds AwaitOutput request in the mempool service
• Updates the spent_utxos() method in the transaction verifier to try querying the mempool for spent outpoints before returning a TransparentInputNotFound error.
• Polls the mempool service from the transaction verifier after verifying a mempool transaction that creates new UTXOs (in case they're spent by other mempool transactions that are still being verified)
• Updates getblocktemplate method and ZIP-317 transaction selection to include transactions that spent the outputs of other transactions in the mempool when all of their dependencies have been selected

Tests

Added tests to check that:

• Inserting a transaction also updates the transaction dependencies tracked in the verified set
• The Storage.remove() method works as expected (the rest of evict_one() should be covered already)
• The mempool responds to AwaitOutput requests when the output for the queried outpoint is:
  • Added to the mempool
  • Already available in the mempool
• The transaction verifier:
  • Calls the mempool with AwaitOutput requests as expected and processes UnspentOutput responses correctly
  • Polls the mempool after verifying a mempool transaction that creates new transparent outputs
  • Includes all of the expected spent_mempool_outpoints in its response
• Long poll ids remaining consistent as long the mempool contents are unchanged (and everything else is unchanged)
• ZIP-317 mempool transaction selection excludes transactions that have dependencies unless their dependencies have already been selected

If needed, this PR could also add tests for:

• ZIP-317 mempool transaction selection always returns the right order of transactions (this could be unnecessary since they’re sorted afterwards anyway but it could be a good sanity check)
• The getblocktemplate method returns transactions with dependencies in the right order when the transaction hashes would have them sorted in the wrong order
• Ideally at least a basic acceptance test that checks that it all works via RPCs

Follow Up Work

The mempool's Downloads sends a result to the response channel too early, it should wait until the transaction is being inserted into the mempool's verified set.

PR Author's Checklist

• [x] The PR name will make sense to users.
• [ ] The PR provides a CHANGELOG summary.
• [x] The solution is tested.
• [x] The documentation is up to date.
• [x] The PR has a priority label.

PR Reviewer's Checklist

• [ ] The PR Author's checklist is complete.
• [ ] The PR resolves the issue.

[arya2]

This is a complex PR (not your fault, it's a complex issue). I've been reviewing it for a while but it feels I could spend ages reviewing this to be 100% sure. I'm OK with approving it but do you think we should ask for someone else to take a look?

In hindsight, it probably should've been split into multiple PRs. A second review would be ideal since it involves concurrency and consensus changes, though it has also gone through a few rounds of self-review.

I think a second review of just the changes to ZIP 317 block production would be okay.

Also, did you manage to test it for the use case we wish to address (i.e. sending to tex addresses?)

I haven't, and there's no acceptance test that tries to submit an orphaned transaction, I'll try doing that now.

[upbqdn]

I'm also still reviewing. A bunch of other things took precedence in the meantime, unfortunately.

[arya2]

What do you mean by "orphaned" transactions in the title?

Transactions that spend outputs that are missing in the chain state, though I'm not sure if "orphan transactions" is the right term if those outputs can still be found in the mempool.

This PR is still missing an acceptance test for the use case we're trying to address (testing it manually with zcashd seems difficult, and a test that creates transactions could provide a valuable reference for other tests in the future), but I think it's fine to merge it without an acceptance test since each component has unit tests (though I'm happy to prioritize writing that test if anyone disagrees).

[upbqdn]

What do you mean by "orphaned" transactions in the title?

Transactions that spend outputs that are missing in the chain state, though I'm not sure if "orphan transactions" is the right term if those outputs can still be found in the mempool.

This RFC, https://github.com/zcashfoundation/zebra/blob/257567b559dba0359519d61684e80daac52cc434/book/src/dev/rfcs/0005-state-updates.md#L62, defines orphaned blocks as those that are no longer included in the best chain, which implies they were mined at some point. I'd assume orphaned txs are those in such blocks, but this PR doesn't apply to them. Maybe something like "Verify transactions spending mempool UTXOs"?

[arya2]

I'm trying to figure out what happens if someone submits txs containing a circular dependency. We should make sure we can handle such cases well.

The transaction verifier would return an TransparentInputNotFound error for both because (unlike pending_utxos in the state service) the mempool only responds to AwaitOutput requests once the transaction creating that output has been added to the mempool's verified set.

A similar question around ordering the transactions in block templates caused me some strife (the code should work as expected there too, and it's been excluded from release compilations, but it was difficult to reason about). That exact question may have also caused me some strife a little earlier, as well as what happens to long chains of dependent transactions.

[gustavovalverde]

@mergify refresh

[mergify[bot]]

refresh

✅ Pull request refreshed