Refactor store keys to allow variable-length addresses

[amaury1093]

Summary

Problem Definition

ADR-028 proposes to have addresses of length > 20 bytes for security reasons. However, some modules (bank, distribution, gov, slashing, staking) depend on fixed-length addresses (AddrLen, set to 20 bytes now).

This issue is to discuss refactoring the store keys of these modules to be able to handle variable-length addresses.

Proposal

• Refactor store keys for variable-length addresses #8363 Refactor store keys
• Add in-place migrations scripts for all modules (see Discussion in Consensus versioning & migrations #8429)
  • Add in-place store migrations #8485 set up base infrastructure in Configurator/ModuleManager
  • Add in-place store migrations #8485 x/bank
  • x{stake,slash,gov,distrib} In-place Store Migrations #8504 x/distribution
  • x{stake,slash,gov,distrib} In-place Store Migrations #8504 x/gov
  • x{stake,slash,gov,distrib} In-place Store Migrations #8504 x/slashing
  • x{stake,slash,gov,distrib} In-place Store Migrations #8504 x/staking
  • Weighted votes migrate in-place migrations #8663 weighted votes

Aaron outlined some ideas in this comment for replacing addresses inside store keys:

1. use the account number (uint64) instead of addresses,
2. set AddrLen to something bigger (e.g. 41), addresses are length-prefixed (1 byte) and padded with 0s until AddrLen
3. for variable-length components inside the store key, use length-prefixed components.

From Aaron, about 3/:

So, I think length prefixing will work for multi-part keys without padding as long as all parts except the last one are prefixed, (i.e. [part1 len][part1][part2 len][part2][part3]. Does that sound correct? And theoretically we could prefix with a varint to not have a 255 byte limit, but 255 should be plenty.

The case where length prefixing is problematic is if you care about keys being lexically sorted in index scans. In those cases, fixed length bytes or strings with lexical separators are needed. I tried using length suffixing in the orm to deal with this, but I think that also has its pitfalls. But anyway, we don't need lexical sorting for addresses at all.

It seems to me that 3/ is more space-efficient than 2/, and doesn't require additional acc_num<->addr lookups like in 1/. So 3/ would be my preferred way to go.

cc @alessio @alexanderbez

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[aaronc]

Just noting that ADR 028 doesn't currently support variable length addresses, but the plan is to update it with both 20 and 32 byte addresses based on recent discussions.

[amaury1093]

So, I think length prefixing will work for multi-part keys without padding as long as all parts except the last one are prefixed, (i.e. [part1 len][part1][part2 len][part2][part3]. Does that sound correct?

I'm re-reading this, and just want to make sure we're on the same page for 3/ . We don't need to length-prefix all components, just the variable-length component(s), correct?

e.g. a balance store key for a particular denom is:

"balances" ++ {byte addrLen} ++ {bytes addr} ++ {denom}

and NOT:

{byte len("balances")} ++ "balances" ++ {byte addrLen} ++ {bytes addr} ++ {byte denomLen} ++ {denom}

I don't think we need to length-prefix fixed-length components. See e.g. the draft PR here

[aaronc]

Just this:

"balances" ++ {byte addrLen} ++ {bytes addr} ++ {denom}

And we probably shouldn't even use balances but just 0x0 or whatever.

[amaury1093]

cool, we're on the same page 👍

[clevinson]

ahh this was a misunderstanding on my part as well. Thanks for clarifying @amaurymartiny

[clevinson]

@AmauryM We should add a followup to add a store migration for Sunny's weighted votes PR.