search

keep-starknet-strange / raito

Bitcoin ZK client written in Cairo.
https://raito.wtf
MIT License
40 stars 34 forks source link

[feat] Try to optimize `merkle_tree::merkle_root` #50

Closed maciejka closed 2 months ago

maciejka commented 2 months ago

Current merkle_root calculation uses u256 to represent internal hashes in the tree. While this seems very natural, it is not how things work internally. Under the hood compute_sha256_u32_array which accepts Array<u32> and returns [u32; 8], so some work is wasted doing conversions. Try to optimise the process. Don't go too far though merkle_root function should still return u256 but can accept Array<Array<u32>>.

Provide speedup measurements.

Jeanmichel7 commented 2 months ago

Hello, can I try to do it ?

onlydustapp[bot] commented 2 months ago

Hey @Jeanmichel7! Thanks for showing interest. We've created an application for you to contribute to Raito - Bitcoin ZK Client. Go check it out on OnlyDust!

TAdev0 commented 2 months ago

@maciejka

PavitraAgarwal21 commented 2 months ago

hey can i take this issue

onlydustapp[bot] commented 2 months ago

Hey @PavitraAgarwal21! Thanks for showing interest. We've created an application for you to contribute to Raito - Bitcoin ZK Client. Go check it out on OnlyDust!

Jeanmichel7 commented 2 months ago

@maciejka it seems that TAdev0 is already assigned to another issue, is it possible to assign it to me?

maciejka commented 2 months ago

Hey, sorry for the confusion. We discussed assigning him on the project tg group. Maybe you can work together? @TAdev0?

pt., 9 sie 2024, 18:21 użytkownik Jean-Michel @.***> napisał:

@maciejka https://github.com/maciejka it seems that TAdev0 is already assigned to another issue, is it possible to assign it to me?

— Reply to this email directly, view it on GitHub https://github.com/keep-starknet-strange/raito/issues/50#issuecomment-2278307799, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABOTB6ETYNTLO5CFJKF2JTZQTT7LAVCNFSM6AAAAABMISMASGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENZYGMYDONZZHE . You are receiving this because you were mentioned.Message ID: @.***>

TAdev0 commented 2 months ago

Please go ahead @Jeanmichel7 if you d like

Jeanmichel7 commented 2 months ago

Ah ok I should also join the Telegram group, it's up to you

TAdev0 commented 2 months ago

ok well, lets both work on it, and we can review together once one or other has pushed a PR? what do you think?

Jeanmichel7 commented 2 months ago

ok let's do that, I'll be available tomorrow for the review and push my draft optimizations.

TAdev0 commented 2 months ago

hi @Jeanmichel7 , just pushed a PR which is ready for review. You can check it out and see what you can improve. There is no doubt there is room for improvements in my impl, i'll give it a second look tomorrow as well

Jeanmichel7 commented 2 months ago

hi @TAdev0 , you've already made the changes I was thinking of making, so I continued from your code to try to improve performance by rewriting compute_sha256_u32_array to be more specific to our use case, but that only improved performance a little. On the big test I'm at 55468570 instead of 58159320gas. I don't know if it's a good idea, I'm pushing a draft and I'd like your opinion.