# Subsrtate next generation storage
https://forum.polkadot.network/t/generalized-storage-proofs/1315
https://www.prestonevans.me/nearly-optimal-state-merklization/
https://www.rob.tech/blog/nearly-optimal-polkadot-merklization/
## Symmetric
### 32 bit vs 64 bit
`blake2b_compress` sends 128 bytes to 32 bytes, and is optimized for 64 bit machines.
`blake3_compress` sends 64 bytes to 32 bytes, and is optimized for 32 bit machines.
Would 64 bit blake3 be faster? Ain't clear..
Jeff> *I suppose 64bit machines' SIMD parallelizes this 32bit arithmetic nicely anyways, so this decision costs nothing on 64bit machines.*
Jack O'Connor> *Yes, that comes up in the introduction to our paper, and we go into more detail in section 7.2.*
In principle, one might design an analog of `blake3_compress` that sends 64 bytes to 32 bytes, while being optimized for 64 bit machines. Does the blake3 paper argue this looks unecessary?
Can we freely mix these, or does this add cache pressure?
### Vec proofs
Aside from blake3, almost all hash functions admit O(1) sized append proofs. Append proofs are 256-ish bytes in blake2b for example.
Blake3 has both append and edit proofs of size roughly 32 bytes * log(len/?). An edit proof can read or write ytes in a bytes string, but cannot shift them left or right. Afaik only a Bao tree hashes like blake3 support these edit proofs.
An edit proof is half the size if its compression sends 64 bytes to 32 bytes, like blake3 does. (See above 32 vs 64 bit question)
### Indexed by bit strings
We should've storage proofs indexed by bit strings in which all values appear at leaves, never at internal nodes.
These support efficent binary hashing of the form `blake3_compress(left,right)` (See above 32 vs 64 bit question).
Ideally, all leaves should be blake3 or blake2b hashes, making all intermediate `left` and `right` values be hashes
Also, leaf nodes could use `blake3_compress(prefix_len_byte,prefix,hash(value)` or similar.
### Prefix trie
We'll want a prefix trie that compresses internal nodes efficently like `blake2b_compress(left, right, prefix_len_byte, prefix, hash(value))`. Also, leaf nodes could instead use `blake3_compress(prefix_len_byte,prefix,hash(value)` or similar.
In this, we enforce `prefix_len < 32` which would not support all current substrate prefixes, but accounts likely become indexed by bit strings instead.
A priori, prefix should only be remainder of the prefix, so "y", xa", "xb" results in "y" being a leaf, and "x" being an interal node with leaves "a" and "b".
We expect prefixes should be handled
## Asymmetric
### KZG

e(A_1,B_1) \cdot e(A_2,B_2) = e([\alpha_1]_1, [\beta_1]_2) \cdot e([\alpha_2]_1, [\beta_2]_2) \cdot e( Z_{\mathsf{sec}} + Z_{\mathsf{pub}}, [\gamma]) \cdot e(C_1+C_2, [\delta]_2) \mathperiod

11/21/2023Let P(x,y) = x A + y B denote a Pedersen hash on the curve E over F_q. Assume p = |E| < q.

10/17/2023Ideally, almost all rewards in Kusama/Polkadot would come from work done securing parachains like backing and approval checkers, including work supporting XCMP, and availability. We do need participation in relay chain block production and finality, so some rewards must continue, but their levels shall wind up greatly reduced.

10/7/2023https://github.com/paritytech/substrate/pull/13031 https://github.com/paritytech/ark-substrate https://github.com/w3f/ark-scale/ Coordinates Affine coordinates and serialized forms differe in Arkworks and ZCash/BLST, but an easy conversion is given by https://github.com/MystenLabs/fastcrypto/tree/main/fastcrypto-zkp/src/bls12381

6/6/2023
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up