Temperature check: support address_getAppearances

[perama-v]

Describe the feature

This issue is to introduce the concept of "address appearances" and assess appetite for inclusion in reth.

Specifications

See also the following specifications:

• What an "appearance" is: feat(specs): add spec for address Appearance ethereum/execution-apis#456
• Namespace and method: Add address_getAppearances ethereum/execution-apis#453
• A related, on-the-fly single block method: New eth_getAddressesInBlock method ethereum/execution-apis#452

Motivation

A user (or local application) running reth can start with an address (e.g., 0x30a4...1382) important to them.
They query reth and get the set of transactions that are relevant to that address.

>> {"jsonrpc":"2.0","id":1,
    "method":"address_getAppearances",
    "params":["0x30a4639850b3ddeaaca4f06280aa751682f11382"]}
<< {"id":1,"jsonrpc":"2.0","result":[
    {"blockNumber":"0xd63f51","transactionIndex":"0xe6"},
    {"blockNumber":"0xd63f5a","transactionIndex":"0x11b"},
    {"blockNumber":"0xd68154","transactionIndex":"0x6"},
    ...

This kicks off the journey, which can now proceed in many ways:

• Inspect the transactions (e.g., trace them, looking for particular things) to get a history of activity.
  • "List/graph all historical ether balances changes for a wallet"
  • "List all contracts interacted with"
• Find the intersection with other addresses (such as a particular contract) to get user interactions with a particular protocol.
  • "List all trades on a particular protocol for some wallet"
  • "List all users who have been involved with a protocol"

As addresses are the foundation of user and protocol activity, the feature is general purpose.

Why "in reth" and not separate

The presence of the address_getAppearances natively within reth would mean first class support for user-focused applications. This could lead to:

• More Ethereum users running reth. There is tangible gain for a user: a history of personal activity
• Robust/resilient applications. A new protocol can be deployed and a frontend published that uses address_getAppearances to locate relevant transactions. The frontend does not require any node restart / trace filter / external application to function.

As the method is general purpose it always supports new wallets/protocols that a user is suddenly interested in.

Prior work

The UnchainedIndex, accessible via trueblocks-core (https://github.com/TrueBlocks/trueblocks-core) is an example of the utility of the information that address_getAppearances would provide.

The method is equivalent to the following command in trueblocks-core:

> chifra list 0x30a4639850b3ddeaaca4f06280aa751682f11382
address	blockNumber	transactionIndex
0x30a4639850b3ddeaaca4f06280aa751682f11382	14040913	230
0x30a4639850b3ddeaaca4f06280aa751682f11382	14040922	283
0x30a4639850b3ddeaaca4f06280aa751682f11382	14057812	6
...

Disk impact

The support for address_getAppearances creates additional disk burden. An upper ceiling estimate is 80GB.

The estimate is based on the UnchainedIndex (80GB), which is specially designed for distribution/sharding on IPFS. Such requirements mean that the index adds immutable pieces of data every 12 hours. An address that appears every 12 hours is therefore duplicated.

There are likely means to significantly reduce the disk footprint of a native reth version of this data.

Additional context

What is an "appearance"

Appearances are defined in a way to capture instances when an address arises in a meaningful way in the chain.

A simple example is the subject of a CALL opcode to an EOA. The recipient "appears" in that transaction (they receive ether). Upon tracing, the meaning of the transaction can be determined.

An "appearance" is defined in the following PR:

• feat(specs): add spec for address Appearance ethereum/execution-apis#456

address_getAppearances method

The method is defined in the following PR:

• Add address_getAppearances ethereum/execution-apis#453

This is a chicken an egg situation: The method is stronger if there is an indication of existence/support in a client and vice versa.

Temperature check

Seeking feedback on this concept. Do any of the following resonate with you? Please feel free to add thoughts of any kind

1. Is this desirable?
2. Would a PR implementing a flag-based address_ namespace for address_getAppearances be considered?
3. "In favour but, would like to see more concrete disk footprint prototype/estimate"
4. "I can see how this would enable some_application_idea"
5. "Please keep it off the node and in companion applications/datasets"
6. <other>

Thanks for your time

### Checklist
- [ ] `address_` namespace addition with placeholder impl of `address_getAppearances` (#4146)
- [ ] implement a `get_appearances_from_transaction()` method (#4162)
- [ ] implement `eth_getAppearancesInBlock` JSON-RPC method
- [ ] define new `AppearanceHistory` table (https://github.com/paradigmxyz/reth/pull/4182)
- [ ] Populate the index during a stage
- [ ] implement `address_getAppearances` endpoint (`Address -> Vec<(BlockNumber, TxIndex)>`)
- [ ] Design mechanism to add APIs like this w/o introducing large main codebase maintenance overheads (#4325)

[tjayrush]

Is this desirable?

https://www.google.com/search?q=getting+a+list+of+transactions+per+address&oq=getting+a+list+of+transactions+per+address&aqs=chrome..69i57j33i160l3.7575j0j7&sourceid=chrome&ie=UTF-8#ip=1

Also, without a complete history of appearances, it's impossible to build a reconcilable accounting (in both the financial sense and the 'state change' sense).

This is exactly why all of us are struggling to do automated accounting "off-chain" against an "on-chain" system that reconciles 240,000,000 addresses every 12 seconds.

[mattsse]

definitely supportive,
defer to @rakita @joshieDo if this is currently technically possible or if it would require additional indexes (I think it would)

[tjayrush]

I'm not speaking for the original poster here, but, yes, this would require an additional index and associated hard drive space. That's why it should be optional.

It's also why I proposed (and @perama-v wrote) this feature as well: ethereum/execution-apis#452.

eth_getAddressesInBlock does not require any additional indexes or hard drive space (it can be done on-demand), but it does go a long way towards enabling address_getAppearances.

address_getAppearances, in order to build the index you're asking about, would need to repeatedly call eth_getAddressesInBlock (or it could be called during syncing).

If eth_getAddressesInBlock existed even if there was no additional index in the node, at least external indexers could build their own index off-chain.

I'm not suggesting that address_getAppearances doesn't get added. I think it should because it's so necessary, but a good starting point might be eth_getAddressesInBlock.

[perama-v]

Here are some notes after reviewing existing structures

AccountHistory comparison

There is already the AccountHistory
table that stores all transaction identifiers where an address (account) state was changed.

This AccountHistory is a subset of the data address_getAppearances method would return. Additional data
includes items such as:

• A contract is called as a read-only method.
• An address is mentioned in a log without a state change.

So, a new table (such as AppearancesHistory) is required to capture this additional data. Either:

• New table contains all appearances (including state changes covered by AccountHistory table).
  This is duplication, but with compression (see below) it may be less significant.
• New table only contains appearances that are not covered by AppearancesHistory table.
  For address_getAppearances, one then looks in both tables and combines result. One downside is
  that the AccountHistory table stores block numbers, which may be less suitable (slower, more complex) than storing transaction numbers.

Use global TxNumber

Fortunately, transactions are represented by a global number TxNumber rather than index in block.

Relevant tables:

• TransactionBlock
  to map TxNumber -> block number. See method.
• BlockBodyIndices for block number -> tx index in block

That means we can have a simple mapping of Address -> List(TxNumber)

IntegerList

• "Uses EliasFano to hold a list of integers. It provides really good compression with the capability
  to access its elements without decoding it." source
• Use in databases

So, similar compression can be used for an AppearancesHistory table

New AppearanceHistory table

A new table AppearanceHistory of a similar nature to AccountHistory could be made

///  AppearanceHistory (new) table

/// List of TxNumber (global transaction number, not index in block)
pub type TransactionNumberList = IntegerList;
table!(
/// Stores pointers to transaction appearance-set with appearances for each address key.
/// ( AppearanceHistory ) Address | TransactionNumberList
)

Response algorithm

If reth stores global tx numbers they can be converted to (block_number, transaction_index)
for the JSON-RPC method address_getAppearances response.

// Pseudocode for address_getAppearances method response construction.
fn address_get_appearances(address: Address) -> Vec<(BlockNumber, TxIndex)> {
    // AppearanceHistory table (new)
    let tx_list: TransactionNumberList = appearance_history_table.get(address);
    let mut appearances = vec![];
    for global_tx_num in tx_list.items() {
        // TransactionBlock table
        let block_num = transaction_block_table.get(global_tx_num);
        // BlockBodyIndices table
        let tx_index_in_block = block_body_indices_table.get(global_tx_num);
        appearances.push((block_num, tx_index_in_block));
    }
    appearances
}

New IndexAppearanceHistoryState stage

A stage called IndexAppearanceHistoryState could exist, structurally similar to
IndexAccountHistoryStage

TODO - when is a good time to do this stage?

[joshieDo]

i'm conservatively supportive. Between this, and otterscan index needs, we probably need better abstractions to accommodate feature/flag based indexes without being too messy

I'm skeptical about the estimate... 80GB seems low, but if it's optional it's whatever

A contract is called as a read-only method.

If i'm not mistaken, this implies having to do "something" during the execution stage as well

[perama-v]

I'm skeptical about the estimate... 80GB seems low, but if it's optional it's whatever

The estimate is based on the UnchainedIndex, which has the same data (address-->appearances), but is represented in a custom format suited for distribution by 12 hour block ranges (total size ~80gb, no compression)

If i'm not mistaken, this implies having to do "something" during the execution stage as well

Yes, for each tx certain locations are checked for addresses. So this is additional work that must be performed. The specifics are in the spec in the linked execution apis PR.

The work roughly amounts to a trace with calltracer, and checking fields within that response. Plus a check of addresses in withdrawals and block rewards.

[perama-v]

Added a task list for the foreseeable steps.

Regarding the proposed implement IndexAppearanceHistoryState stage:
- Re-executes transactions, looking for appearances.
- Performs equivalent of eth_getAppearances for each block and stores result in a table

One consideration is that it this re-executes the transactions, separately from the Execution stage. One benefit is that
it keeps the Execution stage clean. Another is possible reuse of the CallTracer for a simple implementation. Instead to avoid re-execution of transactions, it could be brought into Execution stage.

[tjayrush]

So, a new table (such as AppearancesHistory) is required to capture this additional data. Either:

• New table contains all appearances (including state changes covered by AccountHistory table).
  This is duplication, but with compression (see below) it may be less significant.
• New table only contains appearances that are not covered by AppearancesHistory table.
  For address_getAppearances, one then looks in both tables and combines result. One downside is
  that the AccountHistory table stores block numbers, which may be less suitable (slower, more complex) than storing transaction numbers.

There's a third option here. Enhance the AccountHistory table to include all appearances (both state change and non-state changing). That would serve three purposes:

1. It would work identically the same for the current AccountHistory use case, but need to filter out non-state-changing appearances,
2. It would serve all the OtterScan use cases (the Appearance database is a super-set of the Etherscan-like use case as discussed here: https://tjayrush.medium.com/how-accurate-is-etherscan-83dab12eeedd and here: https://medium.com/coinmonks/trueblocks-covalent-comparison-7b42f3d1e6f7.) The needs of a blockchain explorer are lesser than the needs of an complete appearance indexer,
3. It would cut down on nearly all additional disc space needed to support the feature. Only non-state-changing appearances would have to be added which are significantly less than the total.

[tjayrush]

i'm conservatively supportive.

I would encourage you to think very carefully about this. Adding what I call a "complete" index of appearances allows one to produce a "complete" transactional history for any account. This allows for perfect 18-decimal place accurate re-creation of an accounts activity off-chain. This allows perfect, 18-decimal place accurate automated accounting every 12 seconds.

If you ever wondered why no-one can produce automated tax information from a system that comes to balance for 200,000,000 million accounts every 12 seconds, it's because there is no way to get a complete history.