Automatic address discovery

[mvaivre]

Address discovery should be triggered in two cases:

1. When restoring a wallet
2. Manually, for cases where a user is using a same account on multiple devices

This should follow the strategy defined in BIP44 and should be implemented on the backend by @tdroxler (following discussions with @polarker).

Details must be discussed, but this feature will be considered in my future mockups. This will ship after 1.2.0 (address derivation). Before that, user will need to "rederive" addresses manually.

[mvaivre]

@tdroxler This one would improve our UX a lot! Do you think we could increase priority and start looking at it / discussing it? Thanks :)

[tdroxler]

Sure, let's have a call soon.

[mvaivre]

Summary of our last discussion with @tdroxler :

• We don't remember why we wanted to involve the backend in this, except for the call to check if a certain address has transactions.
• We will implement BIP44 in the FE, where we're gonna check 20 addresses per group
• Address discovery will happen when restoring a wallet, and when opening a wallet protected by passphrase.
• Thomas will check which endpoint to use in order to make this process efficient (we don't want/need to use the one returning the list of TX with attached details).
• Process: derive addresses by bumping the path index number, check the associated group and check if there are TX associated to the address. If no tx are found, increase the index. Do that until you get 20 addresses with no tx (per group).
• We will add an option in the app's settings to manually trigger the discovery process at any point.

We will see how this is handled by our backend (little stress test). If the load is too high, we may decide to test less addresses per group by default and / or ask for a user action to trigger the discovery.

[tdroxler]

I just checked which endpoint should be called and I think I'll rather add a new one /addresses/<address>/active which return true/false if a tx exists for that address. All other endpoint are way to heavy for that task, while we can find a super light sql query to do that check.

[LeeAlephium]

May want to even make it take a range instead to reduce the network requests? /addresses/active?offset=0&range=24 so the typical case of 4 addresses plus 20 unused, and can return a bool[]

[mvaivre]

The endpoint mentioned by Thomas is for one address only. It basically simply check if TX were done with that address.

[tdroxler]

May want to even make it take a range instead to reduce the network requests? /addresses/active?offset=0&range=24 so the typical case of 4 addresses plus 20 unused, and can return a bool[]

we can't do this from the backend as we don't have access to the key used to derive next addresses

[LeeAlephium]

@tdroxler user can pass a set of addresses then instead as a json array: /addresses/active payload: ['0xoeauaoueao', '0xsaotehusoatehuoatheua', ...]

[LeeAlephium]

Otherwise we're going to have an initial 80 requests - 20 requests per group...

[nop33]

Otherwise we're going to have an initial 80 requests - 20 requests per group...

That's only true if the first 80 address indexes have 20 addresses per group. It will definitely be more than that, since we are scanning sequentially.

[nop33]

I run a script that iterates through address indexes sequentially until it finds 20 addresses per group. I run it 100 times, and the average total addresses that had to be discovered is ~~109~~ 101.09.

Click here for source code

const sdk = require("@alephium/sdk");

const totals = [];
let min = 9999999;
let max = 0;

for (let i = 0; i < 100; i++) {
  const wallet = sdk.walletGenerate();
  const group0addresses = [];
  const group1addresses = [];
  const group2addresses = [];
  const group3addresses = [];
  const addressIndexesToSkip = [];

  while (
    group0addresses.length < 20 ||
    group1addresses.length < 20 ||
    group2addresses.length < 20 ||
    group3addresses.length < 20
  ) {
    const newAddress = sdk.deriveNewAddressData(wallet.seed, undefined, undefined, addressIndexesToSkip);
    const group = sdk.groupOfAddress(newAddress.address);
    if (group === 0) {
      group0addresses.push(newAddress);
    } else if (group === 1) {
      group1addresses.push(newAddress);
    } else if (group === 2) {
      group2addresses.push(newAddress);
    } else if (group === 3) {
      group3addresses.push(newAddress);
    }
    addressIndexesToSkip.push(newAddress.addressIndex);
    // console.log(newAddress.address, group);
  }

  const total = group0addresses.length + group1addresses.length + group2addresses.length + group3addresses.length;

  min = Math.min(min, total);
  max = Math.max(max, total);

  // console.log(`Group 0: ${group0addresses.length}`);
  // console.log(`Group 1: ${group1addresses.length}`);
  // console.log(`Group 2: ${group2addresses.length}`);
  // console.log(`Group 3: ${group3addresses.length}`);
  console.log(`Total: ${total}`);

  totals.push(total);
}

console.log("Average: ", totals.reduce((a, b) => a + b, 0) / totals.length);
console.log("Min: ", min);
console.log("Max: ", max);

[LeeAlephium]

Hahah yeah, I forgot that they're indeterminate so it will definitely be more. Nice experiment man! I love it :D

[tdroxler]

@LeeAlephium yes totally doable and better to suffer only once the http layer. Response will be bool[] with (of course) the same order as the passed addresses

[tdroxler]

I implemented the new way here Path is POST /addresses-active, I can't use /addresses/active otherwise the http server think active is an address

[tdroxler]

We should also limit the max number of addresses to pass, what's a good number for you? As I wrote in the PR: 1000 addresses take around 0.1s, 4000 address 0.5s. We clearly don't need that much, maybe 200 is a good limit?

[nop33]

200 sounds good to me

[tdroxler]

or as cheng proposed:

maybe 4 * 20 since the gas limit of address discovery is 20 by default? so 80 it could also automatically scale when we increase group number?

[nop33]

Alright, in this case, we'll need min 2 requests, which is fine

[tdroxler]

Egal for me, what's the ideal number for you that would require the less call? based on group number?

[nop33]

The minimum would indeed be 80. This case is when the wallet is completely new (no txs in any address) AND it also happens that the first 80 address indexes (from 0 to 79) happen to be equally distributed in 4 groups. The probability of this is quite low, based on the tests I did above.

More realistically, for normal users (1 address), the minimum addresses that we'd have to check would be around 110 I believe.

For users who create more than 1 address, that number will probably be a bit higher, but not much.

Making 2 requests is not a problem. I am just presenting the data I discovered in my tests.

---

EDIT: generating 1000 different wallets and trying to find how many sequential addresses need to be generated so that there are at least 20 addresses per group, results show:

Min: 80
Max: 155
Average: 99.052

[tdroxler]

nice explanation thx!

Then let's do groupNum * 20 as 20 is the number given by the BIP, at least it will make sense in few months when we see that code again :sweat_smile:

[tdroxler]

new endpoint is available here:

curl -X POST 'https://mainnet-explorer-v18-0-backend.alephium.org/addresses-active' -d '["arst","1DKWCEc9HjhchKoMCMA4J1nbNGNjrAoPFnkcgA1w6h7jh"]'

[false,true]

[LeeAlephium]

@nop33 is right though, this'll be most likely always 2 requests... I think there's a lot of evidence that 100 is a good number...!

[polarker]

As we are not generating new addresses for each new transaction by default, 20 is a more than enough gap for address discovery.

I think I saw projects using around 5 addresses for discovery for Ethereum-like projects. I might not remember it exactly, but it should not be far from it.

[nop33]

I think we all agree on the 20 number as the number for gap. But here we were discussing the max number of addresses that the new endpoint accepts as a payload in order to minimize requests to the backend, which is something completely different :)

[nop33]

For what it's worth, groupNum * gap * 2 would be a much better alternative imo :) But I'll stop discussing here and focus on building now 😇

[polarker]

For me, 5 as the default gap per group is practical enough for our design. I would send 5 * 4 addresses per query. Just my own perspective, not meaning it should be taken.

[nop33]

This was implemented and merged into the v2.0 branch, it can be closed.