I know it is possible to verify historical ETH balances (for the last 256 blocks) using a merkle proof on-chain - are there any known implementations?
NB - I'm looking for Solidity code (i.e. on-chain) ways of doing this.
You probably need to build you own code on the top of these two libraries: https://github.com/hamdiallam/Solidity-RLP and https://github.com/commitground/solidity-patricia-tree
The former library allows decoding RLP encoded data structure. The second allows checking that certain data is stored in Merkle-Patricia tree.
Ethereum stores state of all addresses in Merkle-Patricia tree. Path to the leaf is an address, and leaf data is RLP encoding of four values nonce, balance, storageRoot, and codeHash.
Root hash of the tree is stored in block header among other things.
So here is what you need to do in your smart contract:
For anyone coming to this, I found the below - it is unproven though and has some limitations: