tl;dr: Efficiently maintaining authenticated state on disk is a research problem many blockchains are facing. Succinctly, Merkle trees do not fit in memory and maintaining them on-disk is rife with performance penalties. What can be done? This blog discusses a few potential directions: We could investigate on-disk, high-arity Verkle trees[^Kusz18]. We could make the problem obsolete by designing homomorphic authenticated data structures[^PSTY13] whose digest can be updated directly without going to disk. We could investigate new state synchronization designs that rely not on Merkle trees, but on other cryptographic primitives such as multiset incremental hash functions[^BGG94],[^BM97]. We could borrow ideas from stateless validation[^RMCI17],[^CPZ18],[^BBF19],[^GRWZ20],[^PSB21]. We could design new databases optimized for storing Merkle trees. We could authenticate a database like RocksDB directly, instead of storing a Merkle tree in the database[^RPK+18].

This is a slightly-rewritten version of the original post from here. $$ \def\Gr{\mathbb{G}} $$ Introduction This document explains how to open different polynomials at different points. The opening proof consists of one inner-product argument (IPA) proof, one commitment and one scalar. The key application here is computing a slim Verkle proof fast!

This always comes up. Without loss of generality, let $n=2^k$ so $k=\log{n}$. Then: \begin{align} T(2^k) &= 2T(2^{k-1}) + O(2^k\log^2{(2^k)}\log\log{2^k})\ &= 2T(2^{k-1}) + O(2^k k^2\log{k})\

A complete $k$-ary tree has all levels, except possibly the last, completely filled. - - - - [.] - - - - / \ / \ / \ / \ (*) (*) / \ / \ / \ / \