Yes very similar to (actually, looks the same as) Merkle Mountain Ranges (MMR). Wow, several people (including Peter Todd, Greg Maxwell, Mike Hearn, Oleg Andreev, Andrew Miller) were basically discussing stateless clients and this asynchronous accumulator for Bitcoin in 2013 (see here and here)! Back then they called it “storageless”.
The idea of having explicit data structures in the system to make low-witness-update-frequency history objects easily usable is definitely an interesting one.
Given how cheap, user-friendly and low-complexity an MMR is, it does feel natural to consider including one at the consensus layer to dump every piece of history to it, including transactions, blocks, receipts, and application-specific history. Every piece of history can be wrapped in a thin layer of metadata, e.g. to classify the event type.
For example blockhashes can be dumped as [TYPE_BLOCKHASH, {block number goes here}, {block hash goes here}]. Compared to the blockhash refactoring proposal it wouldn’t impose storage, it would allow for efficient checking of arbitrary blockhashes, and wouldn’t require ad-hoc opcodes and/or contracts at the consensus layer.
any application that allows you to reference objects from the history is very often also going to require some kind of stateful mechanism for efficiently proving whether or not those objects have already been consumed
Yes, and this would a design space that’s left open for application developers. The extreme approach I alluded to above with the SNARKs/STARKs is for contracts to define their own application-level accumulator for efficient proofs of object consumption or non-consumption. (For anyone reading, there are universal accumulators with efficient proofs of both set ownership and set non-ownership.)
This approach suffers from a practical issue around transaction synchronisation. Indeed, updating the application-level accumulator is a serial bottleneck that will cause contention when many users want to interact with the contract at the same time. One could do “accumulator sharding” with several accumulators to allow for parallelism. And applications can setup a queuing mechanism for participants to reserve “interaction slots” to avoid wasted work from contention and give everyone a chance to participate.
EDIT: The practical issue around transaction synchronisation goes away with miner-updated witnesses implemented using miner data.