Bloom filters have the nice property that the filter of the union of two sets is the bitwise OR of the filters of the two sets. This property has been the basis of bloom filter trees, RAMBO etc, and later work that switched from bloom filters to more appropriate ones (since the load at the leaves vs. the root will not be balanced for the same bloom filter parameters).
The most interesting of this line of work that I’m aware of is the paper Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying. In this work, a clever partitioning scheme ensures disjointness of entries pertaining to the same key at different positions. This work is agnostic of the underlying approximate set membership query structure, I believe quotient filters to be the most promising candidate, for a number of reasons but really the choice is arbitrary and the wire encoding vs. the in memory representation of course may have very different considerations.
The main challenge with this approach is that txids can be selected maliciously to create collisions with short hashes, the aggregation/range querying does not work if each block / leaf in the tree uses a different(ly salted) hash. However, this is also where the information theoretic advantage can come from: compact block filters require O(bn) queries for n addresses over a range of b blocks, so the false positive rate has to be designed to be lower to avoid downloading too many blocks. By designing for a different query structure the efficiency limit implied by the specific way in which Golomb coded sets are optimal for CBF can be bypassed. Addressing this does not seem insurmountable.
Trusted Server
The simplest idea I’ve had for a while in relation to this bears some resemblance to LDK’s rapid gossip sync: a server (or github repo) with pre-computed AMSMMQs for a balanced tree structure. In this mode, clients can begin by downloading just the root node (which would encode a coarse grained AMSMMQ structure), or any strata of intermediate nodes below it. Assuming the server is honest, true negatives allow excluding a range of blocks. A possible positive can be responded to by downloading lower levels of the tree to narrow the range further, or downloading existing block filters for specific leaves, suggesting that the optimal structure for the tree as a whole is to minimize total information downloaded by quickly discovering the minimal set of leaf/single block filters to download. Note that because the hashing will be different than CBFs, the error is independent, which provides an advantage (FP in both the AMSMMQ and CBF structure is only as likely as the product of the two independent FPRs).
In this setting a maliciously constructed txid collision would take very little work, and is a griefing attack that in the worst case forces clients to download all compact block filters and this auxiliary structure which would be rendered useless. This is not costless, and the server can rotate the salt as more collisions are constructed over time, so it doesn’t seem insurmountable. For narrow hashes a 2nd preimage attack would also be feasible, which would allow targeting a specific user, requiring more computational work but the same on chain cost.
P2P via probablistic verification node class
Here the txid problem becomes is harder because the network would need to agree on a salt on collisions. I don’t know of a solution to this that doesn’t make it possible for an attacker to force peers that serve these data to reindex the blockchain on collisions, and since it’s not just a single server with its own threshold for collision tolerance, this seems like a serious resource exhaustion vector. For the purpose of discussion, let’s assume a reasonable solution exists.
In this setting, several adjustments make sense:
- compute not just one tree but a forest sharing the same leaves, each with a randomized partitioning scheme per the AMSMMQ paper (so each root represents one of the random partitions, not the whole lookup structure).
- index not just scriptPubKey or prevout scriptPubkey, but also txid merkle tree for outpoint resolution, including full utreexo commitments
Suppose an uninitialized client syncs the block headers, and some of the top layers of this forest. It can then choose a block at random, and prepare a block-with-prevouts structure that is the input to such an index, and also is a necessary but insufficient condition for block validity. With utreexo data, it is further possible to validate that no double spending has occurred, assuming that data is valid.
Note that this also permits the calculation of a leaf filter structure for that block. Leaves can be randomly merged bottom up into the forest (and see the open question in the paper about group testing, it relates to how to design the arity/height, and the partitioning scheme of this structure).
Hopefully this clarifies why I thought quotient filters are the most promising - they are easily merged, resized etc.
In zkSTARKs, soundness is often amplified additively by requiring the prover to grind. Another notion is the relaxed soundness of FlyClient. By including a work requirement in the leaves, this index structure unforgeably costly. Weak arguments for validity construction of the filters per the FlyClient model by having the leaves commit to a Merkle trace of their constructions, and be accompanied by Merkle inclusion proofs that can be checked against the block header mMrkle roots, and are evidence of no omissions.
Since this structure is itself a form of proof of work, as new blocks are found, it that can serve as a randomness beacon that is the basis of a continual distribute recomputation of the index structure. Each worker in this computation must contribute asymptotically less than the cost of validating the whole chain, but the results can be aggregated together. Different roots in the forest would then be “heavy” index structures, selected out of the space of random subsets (corresponding to the AMSMMQ partitioning schema) which were built upon by other clients that successfully used them to spot-check the chain. This continual updating approach seems plausible as a the basis for a mitigation of the txid collision concern, but again I don’t know how to do that without potentially unbounded recomputation work at the time of the adversary’s choosing, though forcing the attacker to target multiple “flavors” at once (i.e. not just a forest of random partitions, but a set of forests, one forest per hash) seems like a promising direction that should impose minimal overhead.
The reason I find this interesting is that this class of clients, unlike regular light clients, could hypothetitcally be non-parasitic on the network without imposing that utreexo commitments or these data be part of the consensus rules or even served by existing full nodes. Even though it’s a relaxed form of soundness, weaker than a full node in a number of ways, it is still significantly better than just heaviest chain, and lets clients progressively improve their surety about the validity of the chain tip that they accept.
The reason I no longer find this as interesting as a few years ago is that SwiftSync largely obsoletes this, even weak FlyClient soundness would introduce a significant overhead making this likely less efficient than CBF today (but less trustful), and the whole thing is likely to be obsolete in a few years by SNARGs enabled UTreeXO, i.e. O(1) CoinWitness, so the tremendous engineering effort required for such a node does not seem justified.