search

keep-starknet-strange / raito

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

dev: using Array<u32> as buffer in encode trait #300

Closed PavitraAgarwal21 closed 4 days ago

PavitraAgarwal21 commented 2 weeks ago
vercel[bot] commented 2 weeks ago

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 Nov 11, 2024 5:39am
PavitraAgarwal21 commented 2 weeks ago

Hey @maciejka , could you take a look at the changes in the encode traits? I’d like to confirm if the core logic seems solid to you. If it looks good, I'll start updating the tests and addressing any minor errors. Thanks for your help!

m-kus commented 2 weeks ago

@maciejka I think this would not work because of compact size encoding and pubkey script (and also segwit flags). Maybe we can instead use a more efficient ByteArray alternative?

struct WordArray {
    buffer: Array<u32>,
    pending_word_len: usize
}

In case the pending word is partially filled we apply inefficient algorithm involving mult/div, if we are lucky and pending word len is 0 and our item happened to be of u32 - then we just append.

Will need to benchmark this to make sure we are actually gaining something.

maciejka commented 2 weeks ago

Isn't ByteArray doing the same but with 8 bits of granularity? What we save here is that we don't need to deserialize from array of felts to an array of u32 before hashing.

PavitraAgarwal21 commented 2 weeks ago

Hey! @m-kus @maciejka , what idea should we move forward with?

m-kus commented 2 weeks ago

Isn't ByteArray doing the same but with 8 bits of granularity? What we save here is that we don't need to deserialize from array of felts to an array of u32 before hashing.

Yes, ByteArray packs data into 31-byte chunks which we later convert to Array, here we use 4-byte chunks from the beginning.

maciejka commented 2 weeks ago

Isn't ByteArray doing the same but with 8 bits of granularity? What we save here is that we don't need to deserialize from array of felts to an array of u32 before hashing.

@PavitraAgarwal21we are busy at devcon. Sorry for the delay. I will have a look today.

maciejka commented 4 days ago

See: https://github.com/keep-starknet-strange/raito/pull/306