Design a scheme for ordering EVM trace objects according to their execution within a transaction.
- The key requirement is that you don't have all the traces within the transaction up front. You might only have one trace out of 5 (or 1,000). So, if you were to use this scheme to order 3/5 traces, then insert the remaining 2, the order should still work as expected without needing to update the first 3.
- Ideally, the scheme would determine a value for each trace that can be used in a SQL
ORDER BYclause. The value could be of any data type - integer, float, text (e.g. sorted lexicographically), or something more exotic.
Here's an example of a trace_filter request and response (Alchemy sandbox link)
Request
{
id: 1,
jsonrpc: "2.0",
method: "trace_filter",
params: [
{
fromBlock: "0xc26f54",
toBlock: "0xc26f54",
toAddress: ["0x000000000000abe945c436595ce765a8a261317b"],
},
],
}Request
{
jsonrpc: "2.0",
id: 1,
result: [
{
action: {
from: "0x15dce17509846b420b1f5c158fe3d7518204abb6",
callType: "call",
gas: "0xed2a4",
input:
"0x00000000000000000000000000abc3136b63363200000000000000000000000000708a100000000000000000000000000000000000000000000000000000000000000040000000000000000000000000000000000000000000000000000000000000001f0000000016128acb08000000cb0c5d9d92f4f2f80cce7aa271a1e148c226e19d00000000000000000000000000000000000000000000000000000000000000000000000000000000000000008ae720a71622e824f576b4a8c03031066548a3b1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000075cf0c1848f9db946ab000000000000000000000000fffd8963efd1fc6a506488495d951d5263988d2500000000000000000000000000000000000000000000000000000000000000a000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000e000000000c128acb0800000060594a405d53811d3bc4766596efd80fd545a2700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000cb0c5d9d92f4f2f80cce7aa271a1e148c226e19d0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e41dbb290f7bc000000000000000000000000000fffd8963efd1fc6a506488495d951d5263988d2500000000000000000000000000000000000000000000000000000000000000a000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000040000000002a9059cbb000000c02aaa39b223fe8d0a0e5c4f27ead9083c756cc2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000060594a405d53811d3bc4766596efd80fd545a270000000000000000000000000000000000000000000000000e41dbb290f7bc0000000000005022c0d9f0000008ae720a71622e824f576b4a8c03031066548a3b100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e4f726c005981e87000000000000000000000000000000000000abe945c436595ce765a8a261317b00000000000000000000000000000000000000000000000000000000000000800000000000000000000000000000000000000000000000000000000000000000",
to: "0x000000000000abe945c436595ce765a8a261317b",
value: "0x0",
},
blockHash:
"0xe0583a364c20fa67748ca92e276df63919c67e12fdc9bdbc17deae8cf730cf35",
blockNumber: 12742484,
result: {
gasUsed: "0x4551d",
output:
"0x00000000000000000000000000000000000000000000000000d96b96f61c5e87",
},
subtraces: 12,
traceAddress: [],
transactionHash:
"0x87951d0547018db2c4817282a53e2015d91934b42d1b8d8bba1bef7cb480f263",
transactionPosition: 0,
type: "call",
},
{
action: {
from: "0xcb0c5d9d92f4f2f80cce7aa271a1e148c226e19d",
callType: "call",
gas: "0xd59b0",
input:
"0xfa461e33fffffffffffffffffffffffffffffffffffffffffffffd8b5acf779720eba17300000000000000000000000000000000000000000000075cf0c1848f9db946ab000000000000000000000000000000000000000000000000000000000000006000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000e000000000c128acb0800000060594a405d53811d3bc4766596efd80fd545a2700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000cb0c5d9d92f4f2f80cce7aa271a1e148c226e19d0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e41dbb290f7bc000000000000000000000000000fffd8963efd1fc6a506488495d951d5263988d2500000000000000000000000000000000000000000000000000000000000000a000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000040000000002a9059cbb000000c02aaa39b223fe8d0a0e5c4f27ead9083c756cc2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000060594a405d53811d3bc4766596efd80fd545a270000000000000000000000000000000000000000000000000e41dbb290f7bc000",
to: "0x000000000000abe945c436595ce765a8a261317b",
value: "0x0",
},
blockHash:
"0xe0583a364c20fa67748ca92e276df63919c67e12fdc9bdbc17deae8cf730cf35",
blockNumber: 12742484,
result: { gasUsed: "0x1672a", output: "0x" },
subtraces: 5,
traceAddress: [1, 2],
transactionHash:
"0x87951d0547018db2c4817282a53e2015d91934b42d1b8d8bba1bef7cb480f263",
transactionPosition: 0,
type: "call",
},
{
action: {
from: "0x60594a405d53811d3bc4766596efd80fd545a270",
callType: "call",
gas: "0xbeb56",
input:
"0xfa461e33fffffffffffffffffffffffffffffffffffffffffffff8a30d505ab873a2b51b000000000000000000000000000000000000000000000000e41dbb290f7bc000000000000000000000000000000000000000000000000000000000000000006000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000040000000002a9059cbb000000c02aaa39b223fe8d0a0e5c4f27ead9083c756cc2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000060594a405d53811d3bc4766596efd80fd545a270000000000000000000000000000000000000000000000000e41dbb290f7bc000",
to: "0x000000000000abe945c436595ce765a8a261317b",
value: "0x0",
},
blockHash:
"0xe0583a364c20fa67748ca92e276df63919c67e12fdc9bdbc17deae8cf730cf35",
blockNumber: 12742484,
result: { gasUsed: "0x49c1", output: "0x" },
subtraces: 5,
traceAddress: [2, 2, 0],
transactionHash:
"0x87951d0547018db2c4817282a53e2015d91934b42d1b8d8bba1bef7cb480f263",
transactionPosition: 0,
type: "call",
},
],
};The traceAddress field represents the location of the trace within the transaction call stack.
Consider the second trace in the response above, which has traceAddress: [1, 2]:
Tree traceAddress execution index
A [] 0
CALLs B [0] 1
CALLs C [1] 2
CALLs D [1, 0] 3
CALLs E [1, 1] 4
CALLs F [1, 2] 5
Notes:
- A is the top-level call (an EOA calling a contract).
- These "call traces" are created when a contract executes one of the CALL opcodes
- Notice that the length of the list is equal to the depth of the call, and the value represents the index of the call among its siblings (both zero-indexed).
At a glance, our problem appears to be trivially solved by the "execution index" column I included. We can just count the number of traces that come before the target trace, and use that integer as a sort key.
However, let's update the trace_filter request we sent earlier and add a fromAddress equal the to from of the third trace in the response above:
Request
{
id: 1,
jsonrpc: "2.0",
method: "trace_filter",
params: [
{
fromBlock: "0xc26f54",
toBlock: "0xc26f54",
+ fromAddress: ["0x60594a405d53811d3bc4766596efd80fd545a270"],
toAddress: ["0x000000000000abe945c436595ce765a8a261317b"],
},
],
}Request
{
jsonrpc: "2.0",
id: 1,
result: [
{
action: {
from: "0x60594a405d53811d3bc4766596efd80fd545a270",
callType: "call",
gas: "0xbeb56",
input:
"0xfa461e33fffffffffffffffffffffffffffffffffffffffffffff8a30d505ab873a2b51b000000000000000000000000000000000000000000000000e41dbb290f7bc000000000000000000000000000000000000000000000000000000000000000006000000000000000000000000000000000000000000000000000000000000000c0000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000040000000002a9059cbb000000c02aaa39b223fe8d0a0e5c4f27ead9083c756cc2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000060594a405d53811d3bc4766596efd80fd545a270000000000000000000000000000000000000000000000000e41dbb290f7bc000",
to: "0x000000000000abe945c436595ce765a8a261317b",
value: "0x0",
},
blockHash:
"0xe0583a364c20fa67748ca92e276df63919c67e12fdc9bdbc17deae8cf730cf35",
blockNumber: 12742484,
result: { gasUsed: "0x49c1", output: "0x" },
subtraces: 5,
traceAddress: [2, 2, 0],
transactionHash:
"0x87951d0547018db2c4817282a53e2015d91934b42d1b8d8bba1bef7cb480f263",
transactionPosition: 0,
type: "call",
},
],
};As expected, the result includes only the third trace. Here's the visualization for this trace, constructed the same way as before:
Tree traceAddress execution index
A [] 0
CALLs B [0] 1
CALLs C [1] 2
CALLs W [2] 3
CALLs X [2, 0] 4
CALLs Y [2, 1] 5
CALLs Z [2, 2] 6
CALLs Z [2, 2, 0] 7
Using the same counting methodology, we could conclude that this trace has an execution index of 7.
However, the first trace we analyzed is not present in this tree. The "true" tree looks like this:
Tree traceAddress execution index
A [] 0
CALLs B [0] 1
CALLs C [1] 2
+ CALLs D [1, 0] 3
+ CALLs E [1, 1] 4
+ CALLs F [1, 2] 5
CALLs W [2] 6
CALLs X [2, 0] 7
CALLs Y [2, 1] 8
CALLs Z [2, 2] 9
CALLs Z [2, 1, 0] 10Now, it should be clear that the naive "execution index" method doesn't work if we can only analyze one trace at a time (which is our requirement).
Ideas?
Maybe! Why not just fetch all the traces in the transaction, then order them?
This problem is motivated by a project we're working on at Ponder - we're experimenting with trace_filter as a data source to support a "transaction call" event type.
With Ponder, we have unusual requirements:
- Only use standard Ethereum RPC methods (
eth_,trace_, maybedebug_) - Minimize RPC usage/cost (cache aggressively, avoid wasteful requests)
- Must be able to order events deterministically into a single stream across types (logs, traces) and across any number of EVM chains
- Must run locally with hot reloading (need fast retrieval of raw events, already ordered)
This "execution index" challenge follows from these requirements. There's a bit more to explain - if you've made it this far and are still curious, DM me :)
TL;DR if we can find a way to use trace_filter to fetch + cache call traces rather than iterate through every block on the network using trace_block, it's a big win for Ponder users.