Duplicate events and transactions as leafs of Merkle Tree

[HarryR]

While running the Lithium daemon with some of the tests I noticed a problem, the merkle root was the same for different blocks because it contains only a single transaction where the leaf parameters are the same.

Currently the leaf for transactions consists of:

• from address
• to address
• value uint256
• HASH(input bytes)

Currently the leaf for events consists of:

• contract address
• event_signature bytes32
• HASH(data bytes)

By adding the account nonce to the transaction leaf, and the log index, and possibly the transaction hash, to the event leaf then these will be globally unique, in addition to being unique per block.

See output of the command example python3 -mpanautomata lithium --account 0xffcf8fdee72ac11b5c542428b35eef5769c409f0 --rpc-from 127.0.0.1:8545 --rpc-to 127.0.0.1:8546 --contract 0xcfeb869f69431e42cdb54a4f4f105c19c080a601 --pid .lithium.a2b.pid :

 - 1 25144545796772994323936184663483249006474355431830597686564571283204804054690
 - 2 28386316935363475644474287371547255139245003767829727448387744556204560219635
 - 3 1608453543790845306044356571442812765450819287243782312146423734333907079265
 - 4 23226699201228133502946478258957221446297972194933351578362701180971847991712
 - 5 46280059812566817361796334201777778228423712511330317334637967761529581637163
 - 6 18458067662610892097818812694543715757078440079369795367214521180651649993548
 - 7 29737115939349253453048426967975993376624138379601501403621356956185611453758
 - 8 5695612260822115368989898091783675875926841974333615971595410050315376413213
 - 9 5695612260822115368989898091783675875926841974333615971595410050315376413213
 - 10 5695612260822115368989898091783675875926841974333615971595410050315376413213
 - 11 6065271073267843650579898311687279722396421949023807417093290553004650350461
 - 12 5695612260822115368989898091783675875926841974333615971595410050315376413213
 - 13 7356112846142861658211773605102234513909924143003729887657322591734096678585
 - 14 5695612260822115368989898091783675875926841974333615971595410050315376413213
 - 15 372761693264218693700002835151041629906341802544926775239145613568796527310

The new parameters for the merkle tree leafs would be:

Transactions:

• from address
• from_nonce uint... - Account nonce
• to address
• value uint256
• HASH(input bytes)

Events:

• tx_hash bytes32 - transaction ID which emitted the events
• logidx uint... - index of the log item within the transaction
• contract address
• event_signature bytes32
• HASH(data bytes)

[HarryR]

Now that the proof creation uses a common set of code, it should be possible to modify the underlying code without having to modify the on-chain or client-side code.

Having the tx_hash and log_idx fields in an event proof means that if two identical events are emitted in the same transaction they can be individually distinguished at the proof level. Likewise, having the from_nonce field in transaction proofs means that two transactions with identical parameters can be distinguished.

Either the Panautoma.sol file needs modifying, or the LithiumProver.sol file does. The proof field may have to include extra fields other than the block_idx and path. The fields account_nonce, transaction_hash and log_idx being included in the proof should cover all of these in one go, with the log_idx being unnecessary for transactions.

However, these are only needed to construct the leaf value, which means LithiumProver.sol can remain unmodified. This means that the only files which need to be modified are lithium/common.py and Panautoma.sol.

[HarryR]

It seems that the account nonce can't be retrieved from the transaction receipt, the following fields are in the transaction receipt:

• transactionHash
• transactionIndex
• blockHash
• blockNumber
• gasUsed
• cumulativeGasUsed
• contractAddress
• logsBloom
• status

I think the transactionIndex field should be used. Given that there are currently 100-200 transactions per block on average, I think it's safe to assume that a uint8 would be fatally small, but a uint16 would be adequate for a decent amount of time (65k transactions per block). Additionally the account nonce field may be going away in future, so cannot be depended on.

For logs, the following is an example of a log item:

[
    {
        "address": "0x9561c133dd8580860b6b7e504bc5aa500f0f06a7",
        "blockHash": "0x3a10ed208587bfad56e7833e9e1e58efb8a0d7df6c640039c30d895084af419f",
        "blockNumber": "0x19",
        "data": "0x6a6eec830ff29aadc4fea95a94b653075d65777c3f06c625229eca9f07befaf4000000000000000000000000000000000000000000000000000000000000000c",
        "logIndex": "0x0",
        "topics": [
            "0x2cbdbe00cebef89186c967208065ecaafca1aa8a8971c4ccaa8ac017a9cad9ae"
        ],
        "transactionHash": "0x56a163311d8ed6edcf0fc02eb349a1e81421c75d4cc14b0284cf2b823ec0c409",
        "transactionIndex": "0x0",
        "type": "mined"
    }
]

Is it safe to assume that logIndex can also be constrained to a uint16? For logs they would need the transactionIndex and logIndex fields to make them unique in the absence of the block hash, transaction hash etc. as is used by the short proofs.

So, LithiumProver may need modifying, because it unpacks the Proof object from bytes, which will need to include the transaction and event indices?

Then the leaf hash provided to LithiumProver can be hashed along with the transactionIndex and `logIndex fields. So:

leaf_hash = H(txIdx, logIdx, leaf_data_hash)

Or the LithiumProver interface could be modified to accept bytes memory for the leaf rather than a hash? I think this would make the split between generic Prover and Lithium Specific prover cleaner.

Additionally, if the same data from the same transaction index and log index are included in two blocks, which contains only that transaction, then the merkle proof will be valid across two blocks. For this reason the block height must be included to fix the merkle proof to a specific block height.

leaf_hash = H(blockHeight, txIdx, logIdx, leaf_data_hash)

The blockHeight parameter is included in the bytes proof as a uint256, but this could easily be truncated to be a uint64 (hey, if Windows NT counts time in milliseconds and uses a uint64_t then blocks will be fine - see Year 2038 and Year 2184 problems).

So, after reducing blockHeight from uint256 to uint64 and adding the transactionIndex and logIndex fields to the proof, the total proof size is 8+4+(32*N) where N is the merkle proof path size. This is a net reduction even though more information has been added, which is good :D

In the go-ethereum source blockHeight is uint64 too:

• https://github.com/ethereum/go-ethereum/blob/ec8ee611caefb5c5ad5d796178e94c1919260df4/core/types/log.go#L43

The transaction index and log index fields are 32bits:

• https://github.com/ethereum/go-ethereum/blob/ec8ee611caefb5c5ad5d796178e94c1919260df4/core/types/log.go#L47
• https://github.com/ethereum/go-ethereum/blob/ec8ee611caefb5c5ad5d796178e94c1919260df4/core/types/log.go#L51

The current proof field uses uint256 for the block index, so with reduction to 64bits and the two 32bit fields there is an 8 byte reduction in proof size.

Additionally the network ID field needs including in the leaf hash.

leaf_hash = H(uint64(network_id), uint64(block_height), uint32(tx_idx), uint32(log_idx), leaf_data_hash)

This shouldn't require any modifications to merkle.py as the leaf data containing network-specific stuff is just... data to it.