search

c0dearm / sharks

Fast, small and secure Shamir's Secret Sharing library crate
https://crates.io/crates/sharks
Other
59 stars 12 forks source link

Interpolate Now Takes Any IntoIterator #9

Closed zer0x64 closed 4 years ago

zer0x64 commented 4 years ago

Modified Interpolate to be able to take any struct that implements IntoIterator.

This means that you can pass a slice as before, but you can also pass pretty much anything that can generate an iterator of Share (like a HashSet or a Map that comes from iterator operations). It's simply more generic.

One thing to note is that every clone() operation are on the Iterator itself and not on the data underneath. Since the actual code generates a new Iterator instead of simply cloning a starting point, this version also theoretically faster and no sensitive data is copied.

c0dearm commented 4 years ago

Thanks @zer0x64! Good thinking! Will review the PR in a while :+1:

c0dearm commented 4 years ago

Hello there! So I tested locally and there was a 30% regression in performance for the interpolate method, not sure exactly why, maybe because of the clone on each iteration.

So I decided to take a middle-way approach, which is to revert interpolate back but keep the IntoIterator type for the public recover method, this way the user still benefits from using any collection, but performance is still great :smiley:

I've also simplified the use of the generic types.

Let me know what you think!

zer0x64 commented 4 years ago

Hey!

I'll try to figure out the reason for the performance drop, but the only thing I don't like about your approach is that it clones the secret part of the share(which is relatively for now since zeroize() is not implemented). My motivation for that was especially for when the shares were stored on non-contiguous memory and you wanted to avoid the clone (or if you feel fancy and make an interactive iterator that asks for the share).

On a side note, do you think it would be good to derive Clone on Share, since when using it it can be pretty painful to work with without having access to Clone and for me, the Iterator "hack" came from that.

So I'll check this on this weekend to see if I can work around the clone without a performance drop and I'll keep you in thouch! I think that maybe make the interpolate method accept an Iterator instead of an IntoIterator would be a good start.

c0dearm commented 4 years ago

I will investigate too. Deriving Clone for Share is not straight forward, but we can look into it, the thing is that Vec doesn't implement Clone either.

You can run the performance tests using cargo bench recover. You can take the baseline of the current master branch and then run it with your changes to see the difference.

zer0x64 commented 4 years ago

Finally had time to investigate, however couldn't find any reasons for the performance drop other than "compiler magic". Seems like the code gets more optimized when the iterator is re-created instead of cloned. I think we should merge it like it is right now(interface takes an IntoIterator but interpolate() takes a slice) for now!

c0dearm commented 4 years ago

Great! Thanks for your feedback! Let's merge this :smile: