Better history access by contracts


#1

Currently, the Ethereum API only gives access to the last 256 blocks. This makes it hard and expensive for contracts to verify that something did indeed happen a long time in the past, though it isn’t impossible, as demonstrated by Andrew Miller’s and Kobi Gurkan’s https://github.com/amiller/ethereum-blockhashes

My proposal for a future hard fork: add a function that provides logarithmic access to the entire blockchain history, whereby each block of number N offers direct access to the hash of the \lceil log_2 N\rceil blocks of number (N-1) \& ~(-1 << k) for k from 0 to \lceil log_2 N\rceil-1.

Then contracts can cheaply verify the presence of a transaction or log event in logarithmic time and space for both clients and servers. Validators don’t need to maintain more than a logarithmic extra state, though full history servers may have to maintain O(N log N) extra bits (or only O(N) using some compression at the cost of recomputing O(log N) hashes on demand).

PS: Shouldn’t there be a topic for discussion of the contract API? Or is the API considered fixed in stone forever, even for backward-compatible extensions?


#2

I’m not someone deeply involved in the Ethereum community so I could be leading you wrong here but I think the reason there’s no topic is because this isn’t the right forum to ask for this kind of consensus-breaking improvement. You might have better luck by opening an EIP?


#3

I believe it is a bit too early to open an EIP; I’d like to test the waters of the community first — I’m just starting to get involved, and I am not sure what the best forum is. The EIP repository’s template suggests posting to the the Protocol Discussion forum. I will do just that.

Thanks!


#4

Good luck! I hope you get some useful feedback. :slight_smile:


#5

Changing the number of blocks available to smart contracts would change client’s ability to prune old blocks, or start processing from a snapshot near head. With the 256 block limit, clients can choose to start processing at some snapshot block > 256 blocks behind head and have a fully functioning validating client. If we make it possible to lookup blocks from an arbitrary time in the past, then it means a validating client must retain all blocks in history and cannot start from a snapshot nor prune history.


#6

Why couldn’t you prune old blocks? You only need to remember ~23 extra blocks at any given time.


#7

Perhaps I am vastly misunderstanding your proposal. In the original message you said:

This tells me that the entire blockchain history is available, meaning retained somewhere that is accessible. Right now this is not a requirement, only the most recent 256 blocks actually need to be retained.

When you say:

I’m confused because that seems to conflict with the first quote.

At the moment, all nodes could delete all but the most recent 256 blocks and the system will continue to function. New nodes wouldn’t be able to sync from genesis block, but the chain could continue to mine new blocks and state would continue to update properly. Any system that requires access to blocks older than 256 ago in smart contracts will make this scenario no longer possible.


#8

That’s a total non-sequitur. Ethereum blocks already contain indirect links to the entire chain, and yet you already don’t need to maintain the entire history to validate the next block.

Instead of remembering just “the (hash of the) previous” block, you remember “the (hash of the) previous” block modulo 2^k for all k. That’s a tiny amount of information. You never need to go back in history to consult new values when you only go forward. Going from block N to N+1, each of the K “previous” blocks either is unchanged or becomes block N. No need to preserve much state if at all.
(Also, 23 is less than one tenth of 256, in case you didn’t notice, though for backward compatibility reasons you can’t just drop those 256 backlinks.)

Those who do keep parts of the history that matter to them (or all of it) can then trivially prove to a verifying contract that they did the right thing at some point in the past, at cost O(ln N) instead of O(N), without using clever, somewhat expensive, and possibly less stable, indirect, means such as amiller’s contract.