Compact historical queries

[rootulp]

Context

During a onsite meeting, we discussed that the Headicure sub-workstream for header-pruning has a prerequisite on a consensus breaking change in celestia-core. The consensus breaking change is to make block's commit to a Merkle mountain range of previous blocks.

Most of the motivation for this is that Celestia light nodes after Headicure header-pruning won't retain block headers after a certain window. So the Merkle mountain range in the header enables light nodes to make claims about things in historical blocks (i.e. blobs, transactions, state) that they no longer have the header for.

Proposal

Investigate if it's possible to convert BlockID.Hash into a Merkle mountain range.

celestia-core/proto/tendermint/types/types.pb.go

Lines 211 to 215 in d5042ba

	// BlockID
	type BlockID struct {
	Hash []byte `protobuf:"bytes,1,opt,name=hash,proto3" json:"hash,omitempty"`
	PartSetHeader PartSetHeader `protobuf:"bytes,2,opt,name=part_set_header,json=partSetHeader,proto3" json:"part_set_header"`
	}

Note: this is a consensus breaking change. Adopting this change may involve a multi-step migration plan. We may release one version where consensus nodes can start computing the Merkle mountain range. After a period of time, we can create another release where consensus nodes start including their computed hash after a particular block height. This release process draws inspiration from the Ethereum Verkle tree migration.

[rach-id]

To add more information:

• The merkle tree implementation used will be the RFC6962, and it's a merkle mountain tree specification for an add-only log of certificates.
• The Hash would be replaced by the right most path of the tree. This would allow proving inclusion of recent blocks. Also, would provide all the nodes that need to be updated when adding a new header efficiently.

Please correct me if I missed something.

[musalbas]

I still think this is a very over-engineered solution compared to just making it so that Celestia light nodes store just the data root and state root of the past headers, rather than the entire header.