[feat]: `Hash` type + `Into<u256, Hash>` impl + ``Into<Hash, u256>` impl + `PartialEq<Hash>` + Display `Hash` + optimize `merkle_root`

[TAdev0]

@maciejka first draft for Hash type and `Into<u256, Hash> impl

[vercel[bot]]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated (UTC)
raito	✅ Ready (Inspect)	Visit Preview	💬 Add feedback	Aug 13, 2024 2:44pm

[TAdev0]

@maciejka just implemented Display trait.

I'm not totally convinced regarding new function. For me, new always generates the default value for a type. It seems more logic for me to leave it like this and add a Into that will be used as constructor...

whats your opinion?

[Jeanmichel7]

There's one thing that confuses me about what we're doing, We start with a Hash of type [u32;8] we transform it into array< u32 > to send it to compute_sha256_u32_array which returns us a [u32;8] which we transform back into array< u32 > to send it back to compute_sha256_u32_array which returns us the right type. (double hash)

And in the function it's still transformed from array< u32 > to [u32;16] after calculating the padding.

This is useful for dynamic input, but given that our inputs are always hashes, wouldn't it be better to rewrite this function?

[maciejka]

There's one thing that confuses me about what we're doing, We start with a Hash of type [u32;8] we transform it into array< u32 > to send it to compute_sha256_u32_array which returns us a [u32;8] which we transform back into array< u32 > to send it back to compute_sha256_u32_array which returns us the right type. (double hash)

And in the function it's still transformed from array< u32 > to [u32;16] after calculating the padding.

This is useful for dynamic input, but given that our inputs are always hashes, wouldn't it be better to rewrite this function?

Span seems close to Array internaly so I would not expect to gain much here. We can explore this optimization later. Unless you have hard data.

[TAdev0]

@maciejka PR updated.

• renamed new function to fn to_hash(array: [u32; 8]) -> Hash

It's getting a bit complicated for Display but it should be good:

• Added a into<Hash, u256>
• updated fmt as you suggested

converting to u256 allows to get rid off ValueDisplay of Display<[u32; 8]>

[TAdev0]

@maciejka , @Jeanmichel7 PR has been merged into mine - ready for final review!

[Jeanmichel7]

// before test_merkle_root_01 ... ok (gas usage est.: 197890) test_merkle_root_02 ... ok (gas usage est.: 4420910) test_merkle_root_03 ... ok (gas usage est.: 80930040)

// after // test 3 and 4 added, so old test 03 corresponds to test 05 test_merkle_root_01 ... ok (gas usage est.: 2049950) test_merkle_root_02 ... ok (gas usage est.: 5543080) test_merkle_root_03 ... ok (gas usage est.: 11781830) test_merkle_root_04 ... ok (gas usage est.: 12417230) test_merkle_root_05 ... ok (gas usage est.: 68324700) test_merkle_root_05_bis ... ok (gas usage est.: 56916300)

// result test_merkle_root_01 ... ok (gas usage est.: 197890) -> 2049950 test_merkle_root_02 ... ok (gas usage est.: 4420910) -> 5543080 test_merkle_root_03 ... ok (gas usage est.: 80930040) -> 68324700 or 56916300 depending on input type

the conversion from u256 to Hash in the tests is quite resource-intensive. Is it better to run the tests from the u256 hash or from the Hash type?

[TAdev0]

added a test with 33 leaves in the tree

test raito::merkle_tree::tests::test_big_merkle_root ... ok (gas usage est.: 125278750)

test raito::merkle_tree::tests::test_big_merkle_root ... ok (gas usage est.: 148745460)

improvement is greatly underestimated because we convert uint256 to Hash in the test (otherwise its way too long to create a big test with Hash structs, no other choice than manually creating each Hash ... would take a lot of time)

and this is only 33 leaves, a real block will have way more. And the more leaves, the more it is improved