How to collect all contract instantiations and count the bytecode redundancies?

Question

I want to traverse the Ethereum blockchain, collect all contract instantiations, and count how often which bytecode has been instantiated.

As result I want to have a map with key:hash(bytecode) -> value:instanceCount

If you wish to know, why I am doing it, read EIP 911 - Reduce gas costs for deploying runtime bytecode by copying bytecodeHash from an existing contract

So far, I have the following ideas how it could be done:

Idea 1 Use web3 to collect all transaction with 0x0 as target, get the contractAddress from the receipt, get the code of this contract, count it in the map. [Q]: how to collect the instantiations that happen within the contracts (-> new)?

Idea 2 For every block get the state root hash, load the corresponding trie from the database (leveldb/geth), traverse the tree, collect all accounts, if account not processed yet, grab the code hash and increase the count, move to the next block. [Q]: traversing the complete trie block by block is most probably inefficient. Is there a way to traverse only the paths that changed since the last block?

Idea 3 Traverse the state trie of the latest block only and count bytecode redundancies as described in 2. This simplifies the implementation, but historical data is not considered.

[Q]: Any other ideas?

EDIT: You can find the code duplication counter implemented in JavaScript in my GitHub Repo -> https://github.com/ivica7/eth-chain-stats-collector

Answer 1

Interesting idea!

[Q]: how to collect the instantiations that happen within the contracts (-> new)?

One option is to inspect transaction traces. Geth provides traceTransaction API https://github.com/ethereum/go-ethereum/wiki/Management-APIs#debug_tracetransaction which is available only for transactions executed while running in full archival node mode. You would need to look for CREATE opcode, the address of the newly created account will be on top of the stack in the next opcode for the same call depth (or 0x0 if CREATE was unsuccessful). Then look up its bytecode in the leveldb database.

Another options is to use callTracer introduced in geth 1.8, which can extract internal calls including CREATE https://github.com/ethereum/go-ethereum/pull/15516. They give an example where you can create a subscription via ipc and get internal transactions from multiple blocks:

$ nc -U /work/temp/rinkeby/geth.ipc
{"id": 1, "method": "debug_subscribe", "params": ["traceChain", "0x0", 
"0xffff", {"tracer": "callTracer"}]}

{"jsonrpc":"2.0","id":1,"result":"0xe1deecc4b399e5fd2b2a8abbbc4624e2"}
{"jsonrpc":"2.0","method":"debug_subscription","params":{"subscription":"0xe1deecc4b399e5fd2b2a8abbbc4624e2","result":{"block":"0x37","hash":"0xdb16f0d4465f2fd79f10ba539b169404a3e026db1be082e7fd6071b4c5f37db7","traces":[{"from":"0x31b98d14007bdee637298086988a0bbd31184523","gas":"0x0","gasUsed":"0x0","input":"0x","output":"0x","time":"1.077µs","to":"0x2ed530faddb7349c1efdbf4410db2de835a004e4","type":"CALL","value":"0xde0b6b3a7640000"}]}}}
{"jsonrpc":"2.0","method":"debug_subscription","params":{"subscription":"0xe1deecc4b399e5fd2b2a8abbbc4624e2","result":{"block":"0xf43","hash":"0xacb74aa08838896ad60319bce6e07c92edb2f5253080eb3883549ed8f57ea679","traces":[{"from":"0x31b98d14007bdee637298086988a0bbd31184523","gas":"0x0","gasUsed":"0x0","input":"0x","output":"0x","time":"1.568µs","to":"0xbedcf417ff2752d996d2ade98b97a6f0bef4beb9","type":"CALL","value":"0xde0b6b3a7640000"}]}}}
{"jsonrpc":"2.0","method":"debug_subscription","params":{"subscription":"0xe1deecc4b399e5fd2b2a8abbbc4624e2","result":{"block":"0xf47","hash":"0xea841221179e37ca9cc23424b64201d8805df327c3296a513e9f1fe6faa5ffb3","traces":[{"from":"0xbedcf417ff2752d996d2ade98b97a6f0bef4beb9","gas":"0x4687a0","gasUsed":"0x12e0d","input":"0x6060604052341561000c57fe5b5b6101828061001c6000396000f30060606040526000357c0100000000000000000000000000000000000000000000000000000000900463ffffffff168063230925601461003b575bfe5b341561004357fe5b61008360048080356000191690602001909190803560ff1690602001909190803560001916906020019091908035600019169060200190919050506100c5565b604051808273ffffffffffffffffffffffffffffffffffffffff1673ffffffffffffffffffffffffffffffffffffffff16815260200191505060405180910390f35b6000600185858585604051806000526020016040526000604051602001526040518085600019166000191681526020018460ff1660ff1681526020018360001916600019168152602001826000191660001916815260200194505050505060206040516020810390808403906000866161da5a03f1151561014257fe5b50506020604051035190505b9493505050505600a165627a7a7230582054abc8e7b2d8ea0972823aa9f0df23ecb80ca0b58be9f31b7348d411aaf585be0029","output":"0x60606040526000357c0100000000000000000000000000000000000000000000000000000000900463ffffffff168063230925601461003b575bfe5b341561004357fe5b61008360048080356000191690602001909190803560ff1690602001909190803560001916906020019091908035600019169060200190919050506100c5565b604051808273ffffffffffffffffffffffffffffffffffffffff1673ffffffffffffffffffffffffffffffffffffffff16815260200191505060405180910390f35b6000600185858585604051806000526020016040526000604051602001526040518085600019166000191681526020018460ff1660ff1681526020018360001916600019168152602001826000191660001916815260200194505050505060206040516020810390808403906000866161da5a03f1151561014257fe5b50506020604051035190505b9493505050505600a165627a7a7230582054abc8e7b2d8ea0972823aa9f0df23ecb80ca0b58be9f31b7348d411aaf585be0029","time":"658.529µs","to":"0x5481c0fe170641bd2e0ff7f04161871829c1902d","type":"CREATE","value":"0x0"}]}}}
{"jsonrpc":"2.0","method":"debug_subscription","params":{"subscription":"0xe1deecc4b399e5fd2b2a8abbbc4624e2","result":{"block":"0xfff","hash":"0x254ccbc40eeeb183d8da11cf4908529f45d813ef8eefd0fbf8a024317561ac6b"}}}

[Q]: traversing the complete trie block by block is most probably inefficient. Is there a way to traverse only the paths that changed since the last block?

I think it's possible to efficiently compute the diff of 2 Patricia Merkle Tries. The general idea is you take 2 roots, check their nibbles, go down the trie only for nibbles that are different in both roots. Repeat it recursively for the lower level nodes. There will be some complications related to leaf/extension nodes but I think they are solvable.

Another option is to keep track of the Patricia Trie nodes that you already traversed in previous blocks, and skip them for further blocks.