search

Alzymologist / metadata-offline-project

Experimental work and demonstrations for project on metadata for offline devices
GNU General Public License v3.0
0 stars 0 forks source link

Fix storage #17

Closed burdges closed 1 year ago

burdges commented 1 year ago

Polkadot inherits severally really bone headed pessimizations from Ethereum, like the ecRecover stupidity for ECDSA. Among the worst, we have a trie that does radix 16 hashing, instead of sensible binary hashing, perhaps optimized like in Sphincs+ or whatever.

A proof in dense tree needs 15 copath elements per layer, due to radix 16 being used here. A proof in a binary tree needs 1 copath element per layer and 4x as many layers, so our tree wastes almost 4x the space, if dense. Also, binary trees could employ other optimizations if sparsity were expected.

I've complained about this repeatedly, but every time I convince someone to look at it, they run some half assed test on an artificially sparse tree, which does not reveal the problem as clearly. In fact, we should've semi-dense trees in production. Also, all trees should be better optimized to be denser in the first place.

Anyways, our storage makes PoV blocks around 4x larger than necessary. How does this impact wallets?

If you want chain metadata to be signed by the transaction, ala https://github.com/Alzymologist/metadata-offline-project/blob/ms1-draft/milestone_1.md, then

  1. you'd want this metadata to be checked by the chain too, not merely the block producer, and
  2. you'll likely access this metadata elsewhere in the transaction

In essence, your transactions look more like PoV witnesses than traditional blocks. Assuming all transactions work this way, then naively you've doubled your PoV blocksize, possibly more than doubled the original block size. As a solution, you should merge the PoV witnesses with this chain metadata.

Do we make the wallet metadata employ the same storage primitives as the chain storage? Ideally yes if they're the same, but no if different, with the no case requiring more witnesses in them metadata, again wasting some space. We'd thus prefer if wallet metadata and chain use exactly the same storage.

We cannot migrate wallets nearly as easily as we can migrate chain storage though, so..

We should replace this stupid radix 16 hashing with binary hashing before shipping a wallet which does this.

burdges commented 1 year ago

It seems this does not witness so much of the chain state as I thought.