Optimize the getContractAddressAtBlock function in the DTL

[smartcontracts]

Is your feature request related to a problem? Please describe. We have a function called getContractAddressAtBlock which finds the address inside the Lib_AddressManager that was associated with a given contract name at a given block. We need this function because it's possible for this address to change over time and we need to be sure that we're looking at the correct address whenever we're scanning for events.

Here's the exact problem statement:

• We have a contract Lib_AddressManager that stores a mapping of string => address which can be accessed via a public getter getAddress(string).
• Addresses can change over time, so getAddress(x) at block N may differ from getAddress(x) at block M != N.
• Goal is to determine the value of getAddress(x) at some given block N.
• We cannot make the assumption of an archival node that can respond to getAddress(x, { block: N }). Instead, we must rely on the AddressSet event.

Our current approach is as follows:

1. Find all AddressSet events from the creation of the Lib_AddressManager to the target block N..
2. If there are no events, return the zero address (0x00...00).
3. If there are events, return the _newAddress parameter of the last emitted event.

This approach quite inefficient when the Lib_AddressManager was created a long time ago. We would like to find an alternative solution that doesn't have to scan as many blocks.

Describe the solution you'd like I'd like to find a solution to this problem that scans a minimal number of blocks. I think this is a fun problem to solve so I'll leave it to someone else to tackle :-). We are hoping to find a solution that does NOT require any changes to the Lib_AddressManager contract. Feel free to use any optimization technique that you'd like, including keeping a cache of the AddressSet events if necessary.

Describe alternatives you've considered For bonus points, I WILL also accept a PR into the regenesis/0.5.0 branch that makes changes to the Lib_AddressManager if those changes make the above algorithm significantly simpler/more efficient. I think this will be a fun mini-project for someone. If you'd like to work on this project, please leave a comment on this issue.

[rajivpo]

Im also going to take a stab at this, but if anyone else is interested, they should definitely go for it 😄

[rajivpo]

Looking to surface some feedback on modifying Lib_AddressManager if possible prior to going down this rabbithole. Was thinking there might be a way to reduce the amount of event querying by allocating an additional, public mapping that maps addressLastChanged[keccak256(abi.encodePacked(nameHash, oldAddressLastSet)) to block.number (block in which new address is set). The main idea being that one can quickly and cheaply recover the block(s) in which the address was changed and thus narrow the filter range for recovering the old address from AddressSet events by iteratively getting the indices of when the address changes occur for a given name.

Some downsides of this approach:

• increased gas costs to call setAddress (loading and setting storage, additional set of encoding + hashing)
• not elegant/simple (this actually feels a bit more complicated to me than what there is currently - but maybe others might feel differently).

See below for further details for changes to Lib_AddressManager

Also, if preferred, I can make the corresponding changes to _getContractAddressAtBlock prior to soliciting feedback 😄

[smartcontracts]

Maybe easier to do a nested mapping like mapping (bytes32 => mapping (uint256 => uint256)) since it's functionally identical but a bit easier to read. I wouldn't worry about the increased cost, it's not very much and only incurred by us.

[smartcontracts]

What would the pseudocode for the new algorithm look like with ^^^ that change?

[rajivpo]

I'm thinking something like this (plz ignore bad syntax)

    // narrow the range to check events for
    let blockNumberOfAddressChange =
      await Lib_AddressManagerContract.addressLastChanged(contractName).(0) // presumably need a way to store base here

    while (blockNumberOfAddressChange > 0) {
      let nextBlockNumberOfAddressChange = await Lib_AddressManagerContract.addressLastChanged(contractName).(blockNumberOfAddressChange)
      if (nextBlockNumberOfAddressChange === 0 || nextBlockNumberOfAddressChange > blockNumber) {
        break
      }
      blockNumberOfAddressChange = nextBlockNumberOfAddressChange
    }
    // get address from event
    const events = await this.state.contracts.Lib_AddressManager.queryFilter(
      this.state.contracts.Lib_AddressManager.filters.AddressSet(contractName),
      blockNumberOfAddressChange,
    )

    if (events.length > 0) {
      return events[events.length - 1].args._newAddress
    } else {
      // Address wasn't set before this.
      return constants.AddressZero
    }

[reggieag]

Building off of @rajivpo's idea, I would like to propose a different data structure to add to Lib_AddressManager. First I would like to introduce a new struct. The struct will contain the start_block, end_block, and _address. The start_block and end_block will define a range that the address is valid within.

    struct AddressHistoryEntry {
        uint256 start_block;
        uint256 end_block;
        address _address;
    }

Then I would like to introduce a mapping from the contract name to an array of AddressHistoryEntry structs.

	mapping (bytes32 => AddressHistoryEntry[]) private addressHistory;

I believe an array of structs better represents the address changes. Adding a new address would be done by updating the last record and appending a new AddressHistoryEntry struct. Retrieving an address as of a certain block will be done by first finding the appropriate array of AddressHistoryEntry structs and then searching the array to find the appropriate address. This can be done using sequential search or binary search depending on performance optimization needs.

As far as the interface to this data goes, I think there are two options. One is to build a new method in the contract that will handle searching the data structure given a contract name and a block number. The method would then return the appropriate _address. Another is to have the contract return the array given a contract name and have the DTL client walk the array. IMO it would be cleaner to have this functionality encapsulated in the contract, but it may be harder to make code updates to contract methods in the future. Happy to provide some rough code examples!

If we definitely want to avoid making updates to the contract, then the best option that I can think of is to read the AddressSet events into the DTL and build an efficient data structure optimized for retrieval. This might be complicated since you will need to maintain the data structure in the DTL as new blocks are added to the chain. Let me know though if you have any thoughts on a cache approach! I'm not very familiar with DTL's behavior. There might be a more optimal cache design that I'm missing.

[reggieag]

Also, I hope I'm not stepping on your toes @rajivpo ! Happy to lean out of this if you've got it 😄

[rajivpo]

@reggieag not at all - go for it!

[smartcontracts]

Gonna close this. Not much we can optimize here and I got rid of the need for this in mainnet.