Making debugging proof failures better

[BGluth]

We're planning on making some (better) debugging tools to help diagnose issues when we find a block that fails. Check out #415 for a bit more info and .

So right now, it's pretty cumbersome to run the current suite of debugging tools whenever we need to. For example, currently if evm_arithmetization produces a final trie that differs from what we expect (ie. the trie state that trace_decoder arrived at), we have to manually insert lines into trace_decoder to output all/some of the intermediate trie states. We then have to sift through these serialized states and pass them into trie_diff or trie_query, which is fairly cumbersome and also error prone.

It would be nice to automate this process as much as possible. Ideally, it would probably be best to get these diagnostics when something fails during proof generation. However, doing this would be a bit of work since producing useful output requires data that is internal to both trace_decoder & evm_arithmetization. For example, if we realize that a specific trie at a given point within a block differs between what trace_decoder and what the EVM got, then the EVM trie needs to be passed back up to trace_decoder (or vice versa).

Note that doing this will require us to store all of the intermediate trie states in memory (because currently we generate a Vec<GenerationInputs> before starting any proof gen) instead of just mutating a single trie after each txn/segment. At first this might seem like this will significantly increase the amount of required memory, but it's important to also note that cloning a HashedPartialTrie is very efficient, since all nodes are wrapped in an Arc, and multiple tries can point to the same trie subset. With this, the memory requirements are actually probably very cheap.

I can see two decent ways to go about implementing this by doing (when a flag is passed into zero_bin):

• Automatically print out this diagnostic information when an error occurs (what's mentioned above).
• Output some extra intermediate state information to disk and then pass this to a separate debugging binary to perform various queries on it.

Currently I'm just considering identifying trie divergences between trace_decoder & evm_arithmetization but we could also expand this later on to also make queries to a production full node (as a ground truth to determine which side is at fault).

Finally, a few other things to consider:

• Since we're working with two different trie types for mpt & smt tries, is there a nice way to unify these (IIRC @0xaatif was working on this)?
• With the unified way of dealing with both trie types, is cloning tries cheap?
• Is there a better way than passing diff state back up from evm_arithmetization? Should it instead just dump stuff to disk on failure?

[BGluth]

One of the issues with making this work for both mpt & smt tries is that we need to access private state inside of the trie libraries (at least for mpt_trie, not sure about smt_trie) in order to construct the output. Unless we're ok with the debug calls (eg. trie_diff) just outputting to stdout, I think we might need to introduce a new library. For example, we probably want to make a trait or something that abstracts the trie_diff method across both trie types. This method should return some common type that represents a computed trie diff. Since this output type is needed by both trie types, it should live in an external library. Since we probably don't want to have mpt_trie & smt_trie both have a dependency on trace_decoder, I think this might mean that we want a new library just for trie debugging.

[einar-polygon]

While debugging a discrepancy lately, it would have been wonderful to be able to write something like sim --tx=0x5c504ed43, which would then print something in geth's structlog format, that I could then diff. Currently from my understanding, to get something similar, I would need to do some subset of the following: (1) pull the block (2) bundle a single transaction (3) set up logging, (4) instrument the interpreter with ad-hoc log statements and (5) filter out other transactions in the block.

This should ideally also show instructions executed in kernel context.

[atanmarko]

@einar-polygon Extra metadata fields in debug struct are there just for the purpose of easier manual handing of json files. I don't see the value to save 100 bytes for the sake of preventing redundancy, when you have 100kb of data. E.g. I send you a file with problematic transaction, you don't need to run GenerationInputs to learn its tx hash, you know it when you open first characters of the file. If you leave some debugging task for a few days, you again just open the beginning of the file, you don't need to search elsewhere to remember your tx hash/block number.

[einar-polygon]

A few percent overhead to make it human-friendly seems reasonable to me.

[Nashtare]

I don't see the value to save 100 bytes for the sake of preventing redundancy

I don't think we're talking about the same thing here. What I was saying is that by storing all these redundant files, we keep requiring manual handling during debugging, which hinders productivity. The purpose of these tools is to not have to do manual manipulation, extracting bits from here and there. If I still have to do this, then I could say that I'm good with what we currently have, I'll just recompile the decoder by adding a write to disk for txn 57 and I'll have what I wanted.

I just don't find the cosmetic benefit of printing the txn hash / index useful for this purpose. Typically zero-bin will write to debug/ folder the generation inputs of failed payloads with the name blocknumber_txnindex.json. We could have this tool do the same, so that you effectively don't need to store these extra fields.

[Nashtare]

it is much easier to navigate data if you had that little overhead of explicit redundant fields at the beginning of the file than to dig into 200000 characters long row

Well, you just need formatting with jq to have a pretty readable format. What's more GenerationInputs already contain the txn index, and all the block header. The txn hash can be easily retrieved too, and if we worry about it, well we can always write it in the file name.
To be fair, these GenerationInputs are rarely aimed at being parsed by a human eye anyway, given that 99% of these consist in serialized tries and hashes. That's why we have these trie diff tools.

[atanmarko]

What I was saying is that by storing all these redundant files, we keep requiring manual handling during debugging, which hinders productivity. The purpose of these tools is to not have to do manual manipulation, extracting bits from here and there.

@Nashtare We don't require manual handling and you don't extract bits and pieces. You load your json file into code directly as a whole into a debug structure:

    // Read the JSON contents of the file as an instance of debug `Transaction`.
    let file = File::open(path)?;
    let reader = BufReader::new(file);
    let tx: Transaction = serde_json::from_reader(reader)?;
    println!("I'll run now debug proving with failing transaction {}", tx.txn_hash);
   // I send GenerationInputs to the prover:
   interpret_and_debug_my_tx(tx.data);

Typically zero-bin will write to debug/ folder the generation inputs of failed payloads with the name blocknumber_txnindex.json

I don't think we should spend any more energy on this topic, rpc extract will output raw GenerationInput (tx or batch) on the stdout, and the developer should name it however he thinks is most productive for him.

cargo run --bin rpc -- --rpc-url <public rpc node> --start-block 20134716 --end-block 20134716 --rpc-type native extract --tx 0x12f68bfce0678a930357db00e49a0be987260cdada2c9a22d246f23d33b61aa2 > b20134716_0x12f68bfce0678a930357db00e49a0be987260cdada2c9a22d246f23d33b61aa2.json

[Nashtare]

Thanks for the write-up @BGluth and apologies for not replying earlier.
In terms of debugging, these tools should be aiming at helping us identify easily the point of failure in our process.

For now the flow is node -> decoder -> prover. Any failure can come from an internal issue in one of these components. On the top of my head, the two main ones we can have are:

• invalid final state from the decoder processing: this isn't caught right away (because we do not pass the stateRoot header field to the decoder) but can be easily tested from a given payload by using the newly added integration test that check for consistency.
• decoder - prover mismatch: typically resulting in a KernelPanic error on the prover side, usually caused by a root mismatch upon execution of a given txn payload.

Now back to the debugging tooling that we may benefit from having:

Trie discrepancy tool 1

We already have eth-trie-tools trie_diff binary to check the first discrepancy between 2 serialized tries, but it has limitations:

• it stops at the first discrepancy
• it requires some manual handling / manipulation beforehand
• it only outputs the node discrepancy (say it is an account, it will highlight the account value differing, but we still need to manually track it back to the txn that touched this account)

Ideally, in case of a bad decoder processing, we could pass in a given block that we know is being badly processed, and for which, this tool would (at a high level):

• load all the accessed accounts for the failing block
• compute the block state transition (resulting in the final invalid state root X)
• fetch the next block's initial state (which root should match X if the previous block was properly processed), by forcing inclusion of the previously fetched accessed accounts (for comparison of Lead nodes)
• remove any node hash caching
• then for each node diff¹:
  • store the diff (key + value) between Node A (trie T) and Node A' (trie T'), possibly fetching from the initial witness payload the last transaction touching the found key
• output the total diff

Trie discrepancy tool 2

In the case of a trie discrepancy between the decoder and the prover (i.e. the prover reconstructed a different trie), then a similar logic than 1 could be applied, but the tries to be compared would need to be fetched differently:

• if say txn N is failing in a given block, we'd need to pick the curr_block_tries in trace_decoder/src/decoding.rs post txn N processing (which would be matching the post-txn state)
• load the prover computed post-txn state (the fetching logic is already implemented in output_debug_tries method to log the tries upon error)
• then apply the comparison process

Some more details on what this tool could be covering was listed here: #415.

Txn execution trace discrepancy tool

Proving failures may be due to txn execution discrepancies: say a user bytecode is wrongly executed which results in a completely arbitrary sequence of state transitions leading to a different ending world state trie, but for which using the previous tools wouldn't be of much help. Instead, it'd be nice to have a tool comparing the transaction trace fetchable from the node, to the one replicated in the prover KERNEL. There is already an issue for this matter here: #221

Where would this tooling lie?

We could either have a standalone debugger crate gathering all these ressources, or modify the existing zero-bin to some extent to include these under specific CLI args / conditional features. Given the discussions revolving around zero-bin CLI complexity, I'd tend to favor in an ideal world the debugging tools be decoupled, although this may require so much of already existing code that it may be best to directly integrate them in the existing crates.

Footnotes

1. To iterate over each node diff, we can either modify the eth-trie-tools related binary to not stop on the first discrepancy, or flush all cached node hashes before the start, and hiding a discrepancy after being found by modifying the cached hash of a given node with the one from the "same" node in the other trie we're comparing to (this is the approach I've been doing manually for now). ↩

[BGluth]

Just to add a bit more about the trie diff impl.

There are actually two different ways to impl trie diff detection:

• Top-down (easier)
• Bottom-up (harder)

I started the impl for both of these, but ended up stopping after doing the top-down approach since it was catching all of the diffs for all the tries we used it against. The bottom-up approach I think is a bit better since it will find the lowest (in terms of trie depth) point of divergence when there is a change lower down that causes a structural change further up. The top-down impl will always IIRC stop at the highest node where there is a structural divergence, which is a bit less useful that the bottom-up approach. I haven't seen a second structural difference that's above the underlying node that is different, so the top-down approach has been fine so far.

The difference between the impls is pretty much just as it sounds from the names. One starts at the root and goes down, while the other starts at the leaf nodes and works upwards. This is not a terribly technical description, but if there's interest in doing the bottom-up impl later on, I'm more than happy to go over what the impl would probably look like.

[hratoanina]

The use case of trie-diffing would mostly be for the state trie, right? In that case, since all accounts are leaf nodes with 64-nibble keys, and we know that there will never be anything interesting in a branch node, why not simply iterate through the tries to gather all the leaf nodes and compare them key by key?

[BGluth]

The use case of trie-diffing would mostly be for the state trie, right?

Hmm I think it should be useful for both, since if a storage slot gets a wrong value written to it, then it will still pick that up (where this will produce a hash difference). Also if the wrong slot gets written to (or doesn't get written to when it should), then this will pick up the structural difference if one exists.

I guess if there's no structural difference, then your leaf key iterator approach might be a bit better, since we can always tell exactly where the value diverged. It will produce bad results though I think if there is a structural difference. By "bad results", I mean it could produce a ton of extra divergences (noise) that are all caused by a single structural divergence.

[einar-polygon]

Since this is a discussion: Do any of us really prefer the Display impl, that prints hashes as: 0x0000…0000 instead 0x0000000000000000000000000000000000000000000000000000000000000000? Otherwise I suggest we remove it. Related.

[BGluth]

I actually really like the verbose version most of the time, especially when I need to cross reference the hash in one or more files. With the truncated representation, there's often not enough nibbles to prevent other hashes being picked up when searching in a text file.

[cffls]

Had a discussion with @Nashtare and he asked me to provide some ideas here.
I think it will be very helpful if we had something that can check the consistency between zero tracer and witness without relying on the decoder from zk_evm.
The tool should be able to do the following:

1. Apply state deltas from zero trace and compute the pre-state trie for each transaction.
2. Execute a transaction from the pre-state trie and compute the post-state trie.
3. For each transaction in the block, compare if the post-state trie yielded by transaction execution (from step2) matches to the pre-state trie computed for the next transaction (from step1).

This will catch many errors incurred by the inconsistency between the tracer and witness, e.g. a txn trace that contains an account read that isn't resolvable (hit hashnode) in witness.