bug: Key not found in preimage

[ftheirs]

Issue Description
While running SNOS for blocks 237025, 237030, 237037, 237042, 237044, 237053, 237083, 237086, 235385, 235620, the following error consistently occurred:

[ERROR prove_block]  
    inner_exc error: Got an exception while executing a hint: Hint Error: Key not found in preimage: 1496700206899231316563006125976608562510487632958670553981981720152324726300  

The error varies depending on the block being processed, but it always fails at the same spot in the execution flow.

---

Debugging Steps and Observations
1- Tracing the Error:
Upon analyzing the trace, it became evident that the error originates in this hint, which fails when a requested node is missing from the preimage. The error indicates that a node required for the proof is not present.

2- Inspecting the Preimage Initialization:
The next logical step was to trace how the preimage is set up. Following the SNOS workflow, it was found that this hint initializes the preimage using os_input.contract_state_commitment_info.commitment_facts.

3- Tracking the Source of Commitment Facts:
Digging further, the commitment_facts are derived from the storage_proofs, specifically within the get_storage_proof function. This function is defined here.

4- Identifying the Missing Nodes:
Through debugging, it was discovered that the missing nodes belong to the storage proof for contract address 0x1. This is a special contract from Starknet's architecture that maps block numbers to their corresponding block hashes. However, the connection between the transactions and the error wasn’t immediately apparent.

5- Investigating the Triggering Contract:
Further investigation revealed that contract 0x00656ca4889a405ec5222e4b0997e5a043902a98cb1f85a039f76f50c000479d is responsible for triggering the issue. The problem occurs in specific functions, such as verify_game and abandon_game. Upon inspecting the Cairo code for this contract, these functions were found to internally call a utility function, which in turn calls get_block_hash_syscall (more documentation can be found here)

---

Conclusion and Solution
The error occurs because the storage proof for contract 0x1 does not include all the necessary keys for the calls and subcalls executed during the transaction. To resolve this issue:

1- Add Missing Keys:
Ensure that all necessary keys for the storage proof of contract 0x1 are included before execution. This involves analyzing the calls and subcalls from all the transactions and identifying the keys they depend on.

2- Optimize the Key Retrieval Process:
Since the exact keys needed cannot always be determined upfront, the retrieval process has been optimized. Basically, we leverage from the structure from this special contract and filter out any keys with values higher than the current block number. This minimizes unnecessary data while ensuring all relevant nodes are included in the preimage.