Verified history, the missing block hashes

tl;dr. Our goal is to minimise (or remove) the barrier to entry for projects wishing to integrate with PISA. One missing piece of the puzzle is a mechanism in the EVM to verify historical logs for a given smart contract. We have an example of how historical event verification using Solidity could work, but to avoid implementing elaborate and complicated protocols we need a simple extension to the existing BLOCKHASH opcode.

At PISA Research we’re building an accountable watchtower for Layer 2 scaling solutions (and more generally, any smart contract on Ethereum). I highlight accountable because this is what makes PISA unique amongst watchtowers. Clients that hire PISA are sure their job will be completed, or they’ll be refunded.

At its core PISA is a simple protocol, when some on-chain criteria is satisfied, the watchtower submits a transaction on the client’s behalf to some target contract. If the transaction is not accepted in the blockchain by an expiry time, then the client is liable to receive compensation in a trust-free fashion.

How? The client has evidence they have hired us and the blockchain should contain evidence we didn’t do our job. The client can simply submit the evidence that they hired us and the PISA contract should retrieve evidence from the target contracts to see if the watchtower did its job.

But how does the PISA contract get evidence from the target contracts? There is no reliable way to do this today, so we came up with the DataRegistry that temporarily stores the data for later use. It has a very simple interface making it ideal for storing evidence, but to integrate with it the target contracts need to modify their source code.

Can we produce on-chain evidence without modifying all existing smart contracts, and without the need for a data registry?

Well yeah, the logs! Smart contracts can emit events about their state, or any state they have access to. These events are recorded as logs in transaction receipts and the block header provides a commitment to all transaction receipts for that given block. Once an event is emitted, it cannot be mutated. So historical logs are technically part of the chain already and thus this seems like the perfect data structure for our evidence use case in PISA.

A photograph of some historical logs

The problem is that smart contracts don’t natively have access to transaction receipts from inside the EVM, so we can’t use events as evidence.

But this isn’t hard to solve. We can provide proof that a transaction receipt is in a block by providing a header and merkle proof of inclusion in the receiptsRoot. Here’s a project showing how this could work.

However, the real fundamental problem, is that the EVM lacks access to most historical block hashes. We need block hashes in the EVM so we can verify that the receipt is not only in a valid block, but it is also in the current chain. However the EVM only provides access up to the 256 most recent block hashes, or in other words, the hashes produced in the last hour. So the solution doesn’t really work for PISA unless the user is expected to return online every hour to check for on-chain evidence and submit it to the blockchain.

What! You can only get the last 256 block hashes?!?!?

There are 3+1 options for solving the block hash problem

1. Periodically store the current block hash in a contract. We can simply submit transactions to record the current block hash in a smart contract to create historic checkpoints of blocks hashes. That way, we could provide a chain of block headers, and the contract could verify each block header is in the blockchain (i.e. working backwards, depending on the hash chain). Roughly, we can verify about 300 headers within the block gas limit of 8,000,000, so checkpointing would have to take place once every ~250 blocks.
2. Run a bi-section protocol if one party doesn’t accept a block hash as valid. For this both parties would put up some stake, then run an on-chain bisection protocol to get to a block which they agree upon. This protocol has potentially cheaper on-going costs, but it’s interactive and cannot be re-used in other challenges as it’s only relevant to the parties taking part in the bi-section
3. Form a zkSnark proof of a hash chain to prove a past block is part of the current chain. Unlike the bi-section protocol it’s non-interactive but we would need to implement a snark which isn’t trivial.
4. +1 best option. Upgrade the EVM to support lookup of older block hashes!

One promising proposal, EIP-1218, suggests storing previous blocks back to genesis with exponentially decreasing gaps towards the present. Since the EIP suggests storing the block hashes in the state it’s still possible to prove the blockhash of any block, however a prover would need to supply a number of merkle proofs of past state.

Whilst this EIP would certainly make proving arbitrary blocks possible, it is non-trivial for a contract developer to implement (and to get it right). It also requires access to an archive node to retrieve the necessary state-proofs.

A simpler solution for our use case would be to extend the existing BLOCKHASH opcode to contain a much greater number of blocks, perhaps say the last 200,000 (~1 month), which could open up a great deal more use cases for easy historical event verification.

So where does this get us?

For PISA this is an improvement on the DataRegistry approach for two main reasons:

1. It’s far cheaper to create evidence. Although verifying the inclusion of an event with the above method costs around 135k gas, writing one is cheap (starting at 750 gas for an event with one topic, and going up from there). Verifying an event should only be used in worse case scenarios when PISA hasn’t done its job and in this case the gas payer can be compensated. Here’s a link to a POC I created to measure gas costs.
2. Automatic integration with most smart contracts in Ethereum. Now there’s a good chance a contract doesn’t need to be altered at all to be integrated with PISA. Any contract using events to signal state changes to external observers could be trivially integrated with PISA.

PISA already works, we can integrate with contracts via the DataRegistry. But this involves cooperation between projects, redeployment of smart contracts, and potentially some gas cost increases. But with verified history PISA can seamlessly provide support to any project, new or existing.

However more use cases could emerge. Verified history extends the view of a contract from the current state to the whole history of transactions, events and state. Basically anything that is observable by an external party about the chain.

But for now, the one missing piece is easy access to historical block hashes in the EVM. The one thing between PISA and seamless integrations.