search

dominant-strategies / go-quai

Official Go Implementation of the Quai Network
GNU General Public License v3.0
2.37k stars 460 forks source link

Change the first 2 bytes of transaction hashes to reflect type and context #518

Closed jdowning100 closed 3 months ago

jdowning100 commented 1 year ago

Rationale

Currently it is impossible to determine the type of a transaction based on its hash. This makes indexing and searching for a transaction via its hash difficult. In addition, external transactions need to be sorted in a patricia merkle tree or verkle tree based on destination. Thus, I propose we use the first two bytes of the transaction hash (out of 32) for type (1 byte) and destination (1 byte).

Implementation

We create a 30-byte blake3 hash with the transaction data, and then append two bytes to the front (or append the 30 byte hash to the back). The first byte is 0 for a block, 1 for an internal transaction and 2 for an external transaction. The second byte encodes the destination of a transaction. This is unnecessary for internal transactions. 0 - Prime 1 - Region 0 2 - Region 0 Zone 0 3 - Region 0 Zone 1 4 - Region 0 Zone 2 5 - Region 1 6 - Region 1 Zone 0 7 - Region 1 Zone 1 8 - Region 1 Zone 2 9 - Region 2 10 - Region 2 Zone 0 11 - Region 2 Zone 1 12 - Region 2 Zone 2

Note: Patricia merkle trees use a nibble for sorting (4 bits) however this may be an issue if we have more than 16 blockchains (the max 4-bit number is 15)

wizeguyy commented 1 year ago

I have a few comments: 1) we only need to encode the origin chain location. No need to encode destination, context, or anything else 1) this does not just apply to ETX IDs, but to normal TX IDs as well 1) the actual encoding likely only requires 1 byte, but that depends on the outcome of this proposal to change our address shard encoding scheme. However we decide in that proposal to shard addresses, we should apply identically to TX IDs

jdowning100 commented 1 year ago

Update: We have discussed and decided that the first byte will be the destination for PMT sorting/trimming and the second byte will be the origin for the block explorer. An internal transaction will have the same number for both bytes and a block will have many leading zeros (greater than 4, for example), removing the need for encoding the type in the hash.