Wallet TX Count and time indexing

This is a port of the https://github.com/bcoin-org/bcoin/pull/605. It includes fixes mentioned in the PR.

This resolves CPU and memory exhaustion issues when requesting transaction history for a wallet with many transactions. Transactions are now also able to be queried by time based on median-time-past (MTP) based on chain data.

Backport:

https://github.com/bcoin-org/bcoin/pull/605

Issues:

bcoin: https://github.com/bcoin-org/bcoin/issues/559
hsd reference issue: #867

Closes #659 - zap will now use time and count indexing for unconfirmed txs.
Closes #867

WDB Migration:

[ ] TODO

Minor changes

Adds get median time to the node http and hs-client node.
Adds get entries to the node http and hs-client node.

Wallet changes

Update wdb version to v3. Migration is handled by #889.

Add getMedianTime - to get median time past for the height, where height is already stored in the db.
Add getMedianTimeTip - to get median time past for the yet to be committed block.
Add block time by height cache.
Wallet now has additional methods for quering history:
- listUnconfirmed(acc, { limit, reverse }) - Get first or last limit unconfirmed transactions.
- listUnconfirmedAfter(acc, { hash, limit, reverse }) - Get first or last limit unconfirmed transactions after/before tx with hash: hash.
- listUnconfirmedFrom(acc, { hash, limit, reverse }) - Get first or last limit unconfirmed transactions after/before tx with hash hash, inclusive.
- listUnconfirmedByTime(acc, { time, limit, reverse }) - Get first or last limit unconfirmed transactions after/before time, inclusive.
- listHistory(acc, { limit, reverse }) - Get first or last limit unconfirmed/confirmed transactions.
- listHistoryAfter(acc, { hash, limit, reverse }) - Get first or last limit unconfirmed/confirmed transactions after/before tx with hash hash.
- listHistoryFrom(acc, { hash, limit, reverse }) - Get first or last limit confirmed/unconfirmed transactions after/before tx with hash hash, inclusive.
- listUnconfirmedByTime(acc, { time, limit, reverse }) - Get first or last limit confirmed/unconfirmed transactions after/before time, inclusive.
- NOTE: Default is ascending order, from the oldest.
Median time past is used by TX Pagination for time indexes. See details below.

Wallet HTTP

GET /wallet/:id/tx/history - The params are now time, after, limit, and reverse.
GET /wallet/:id/tx/unconfirmed - The params are are same as above.

Deprecated and removed:

GET /wallet/:id/tx/range - Instead use the time param for the history and unconfirmed endpoints.
GET /wallet/:id/tx/last - Instead use reverse param for the history and unconfirmed endpoints.

Wallet HTTP Client

getHistory and Wallet.getHistory no longer accept account, instead accepts object with properties: account, time, after, limit, and reverse.
getPending and Wallet.getPending have the same changes as getHistory above.

Deprecate and remove:

getLast and Wallet.getLast, see Wallet HTTP note.
getRange and Wallet.getRange, see Wallet HTTP note.

Examples

GET /wallet/:id/tx/history?after=<txid>&limit=50&reverse=false
GET /wallet/:id/tx/history?after=<txid>&limit=50&reverse=true

By using after=<txid> we can anchor pages so that results will not shift when new blocks and transactions arrive. With reverse=true we can change the order the transactions are returned as latest to genesis. The limit=<number> specifies the maximum number of transactions to return in the result.

GET /wallet/:id/tx/history?time=<median-time-past>&limit=50&reverse=false
GET /wallet/:id/tx/history?time=<median-time-past>&limit=50&reverse=true

The param time is in epoch seconds and indexed based on median-time-past (MTP) and date is ISO 8601 format. Because multiple transactions can share the same time, this can function as an initial query, and then switch to the above after format for the following pages.

GET /wallet/:id/tx/unconfirmed?after=<txid>&limit=50&reverse=false
GET /wallet/:id/tx/unconfirmed?after=<txid>&limit=50&reverse=true
GET /wallet/:id/tx/unconfirmed?time=<time-received>&limit=50&reverse=false

The same will apply to unconfirmed transactions. The time is in epoch seconds and indexed based on when the transaction was added to the wallet.

Wallet RPC

The following new methods have been added:

listhistory - List history with a limit and in reverse order.
listhistoryafter - List history after a txid (subsequent pages).
listhistorybytime - List history by giving a timestamp in epoch seconds (block median time past).
listunconfirmed - List unconfirmed transactions with a limit and in reverse order.
listunconfirmedafter - List unconfirmed transactions after a txid (subsequent pages).
listunconfirmedbytime - List unconfirmed transactions by time they where added.

The following methods have been deprecated:

listtransactions - Use listhistory and the related methods and the after argument for results that do not shift when new blocks arrive.

Wallet CLI (hsw-cli)

history now accepts new args on top of --account: --reverse, --limit, --after, --after.
pending now accepts new args, same as above.

TXDB Change

layout.h - will now also store time for the block, instead of just block hash. This allows us to calculate median time past on the wallet side.
New entries:
- layout.I - Latest Unconfirmed indexed. Makes sure every transactions gets assigned new index.
- z[height][index] -> tx hash (tx by count) - index/query transactions by height and txindex (in a received array). TXIndex for unconfirmed transactions is ever increasing entry in layout.I.
- Z[account][height][index] -> tx hash (tx by count + account) - same as above, just indexed separately for each account.
- y[hash] -> count (count for tx) -> look up Count for tx using hash.
- x[hash] -> undo count (unconfirmed count for tx) - Stores unconfirm index for confirmed transactions in case they get unconfirmed. (Unconfirmed transactions recover their old index and time)
- g[time][height][index][hash] -> dummy (tx by time) - Query confirmed transactions by time, ensures they replicate the same sorting as the count index.
- G[account][time][height][index][hash] -> dummy (tx by time + account) - Same as above, just indexed separately for each account.
- w[time][count][hash] -> dummy (tx by time) - Stores unconfirmed transactions by time.
- W[account][time][count][hash] -> dummy (tx by time + account) - Same as above, just indexed separately for each account.
- e[hash] -> undo time (unconfirmed time for tx) - Time when transaction was first seen, unconfirmed/confirmed. Confirmed transactions will recover time index using this.
Removed entries:
- layout.m and layout.M are no longer used.

TX Pagination

Pagination introduces sorted indexes in the database, that is consistently sorted thoroughout the tx history, whether it's confirmed or unconfirmed. It uses Count indexes to achieve the sorted behaviour. Note this is not strictly based on the tx creation. Instead confirmed transactions use: height + index in the block. Even if one tx was created before another, they will be sorted based on their position in the block and height. Time index for confirmed transactions is based on the "median time past". It ensures, that time increases monotonically with each block. They give us pointer to the Count index. There's also "next" page, which gives us next results based on the last hash of the previous response. This is another pointer to the Count index, indexed separately from time.

Count index

This can look like this, if we have 3 transactions in block 200100:

z[200100][0] - tx1
z[200100][1] - tx2
z[200100][2] - tx3

This means, our wallet has 3 transactions in block 200100 and their index relatively is 0, 1, 2. If we were to reorg and another transactions gets introduced between tx3 and tx2 in the new block, all old entries will get removed and new state will look like this.
z[200100][0] - tx1
z[200100][1] - tx2
z[200100][2] - new tx3
z[200100][3] - old tx3

If you factor in block heights for our transactions, you can see sorted list emerge across different blocks:
z[200100][0] - tx1
z[200100][1] - tx2
z[200101][0] - tx3 (new block)
z[200101][1] - tx4 (new block)

LevelDB allows us to query them with ranges(as it sorts by keys), they will be sorted and also reverse and limits.

Unconfirmed transactions also follow the same scheme. But block height is set to maximum possible value for the height: 0xffffffff. On top unconfirmed transactions have counter for the number of unconfirmed transactions have occured, and that's used for new unconfirmed transactions. This count never decreases and allows previous indexes to be filled, if confirmed transactions get disconnected. Confirmed transactions will store their previous value, to properly recover them in the count index history. This can look like:
z[0xffffffff][0] - first ever unconfirmed tx.
z[0xffffffff][..] - ...
z[0xffffffff][10000] - 10kth tx.

Once they are confirmed, they move to proper block height count index. Disconnected transactions will fill the gaps. layout.Z is used for account based count index.

handshake-org / hsd