ADR 004 Implementation

[alexanderbez]

Summary

Implement ADR 004.

Please cross-reference to any other issues/milestones as necessary.

/cc @cwgoes @fedekunze @jackzampolin

---

For Admin Use

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

[cwgoes]

Thanks @alexanderbez - glad to review and/or update the ADR if anything needs to be revised.

[dshulyak]

quoting from ADR

enabling O(1) read & write access to the balance of a particular account in a particular denomination.

this is not really a O(1). The amount of leaves in the tree increases iavl height and the complexity of the query. i was doing some profiling while working on this issue #5461, and the difference can be significant. note that inserting multiple values also degrades iavl write performance.

so the described griefing vector is still there, it is not straightforward to say what would be worth, storing a single object with all denominations or allow the creation of unlimited separate objects. it definitely makes sense to benchmark proposed change.

[cwgoes]

#5494 (comment)

Agreed on benchmarking. This is a DoS vector we don't consider in general, I suspect it might also appear in other places.

[ValarDragon]

#2860

[dshulyak]

Hmm, yeah. I was thinking primarily w.r.t. gas costs, which don't incorporate this difference (but perhaps they should, though it seems like it would be complex). At least the complexity is logarithmic, not linear. Regardless, we should clarify this in the ADR.

i was looking at different merkle trees wrt write perf, and iavl doesn't seem to scale well when when tree grows in size, e.g if one can find a cheap way to insert multiple unique keys into the same tree - blockchain performance will decrease significantly. Below is a plot for the time it takes to commit 10,000 entries with a key of size 30 bytes, value 100 bytes. Only at 2 mil unique keys it takes 12s to commit 10,000 keys. And beyond that it even worse. Reads degrade as well, i don't have plots for them though.

it is a bit speculative, and i don't know how practical such DoS scenario is but maybe you can find it interesting.

more at https://github.com/dshulyak/merklecmp, but you can also get similar results by tweaking benchmark in iavl repo.

[alexanderbez]

Nice stats @dshulyak! It is well known that amino and IAVL are the two biggest culprits by far in terms of performance and IO bottlenecks, with us already starting to address the former. I would love to see more discussion around IAVL alternatives.

[sunnya97]

2 Points that I should have made at ADR stage, but:

1. SpendableCoinsVestingAccount() and TrackDelegation() shouldn't take in a bank Keeper, as bank types shouldn't be stateful. Instead, they should be passed in the currentBalance as a paramater when called from the bank module.

2. This will also require a refactor of the supply module because its total supply balance is also vulnerable to the same DoS as account balances.

[cwgoes]

This will also require a refactor of the supply module because its total supply balance is also vulnerable to the same DoS as account balances.

This is just an invariant check, right? Or does the state machine use the total balance (as calculated by iteration) in a transaction directly? If the former, it doesn't seem substantially different to me than the existent DoS vector of just making many accounts (though the gas costs likely differ somewhat).

[fedekunze]

This is just an invariant check, right?

Correct, these are just the invariants for the total balance and per-coin balances

[cwgoes]

This is just an invariant check, right?

Correct, these are just the invariants for the total balance and per-coin balances

Do full nodes / validators run the invariants by default?

I'm trying to understand the precise DoS concern and/or change from the current state of affairs.

[fedekunze]

Do full nodes / validators run the invariants by default?

No, there is an invariant mode for nodes. The default is to not run the invariants.