-
Notifications
You must be signed in to change notification settings - Fork 86
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Optimize EdDSAPoseidon.signMessage
method in the eddsa-poseidon
package
#151
Comments
Looking at this literally, I don't think it makes sense for all of the functions. Constructing the class is costly, and requires a private key, so shouldn't be required to do things which don't require a private key. In particular, you need to be able to verify a signature without one. I think the key part of this from our discussion was to reuse the secretScalar across multiple signMessage calls. signMessage is already inside the class so could allow that. I think the best approach might be not to make the class be the only way to call these functions, but an optional optimized way for users who are going to call many functions in a row (particularly signMessage). |
I took a closer look and it actually makes sense to leave it as it is. What we can do is re-use the BLAKE hash initially calculated for the public key in the method for signing messages. So, it might make sense to modify the Does it make sense? |
eddsa-poseidon
functions inside the classeddsa-poseidon
exported functions as methods of the class as well
eddsa-poseidon
exported functions as methods of the class as wellEdDSAPoseidon.signMessage
method in the eddsa-poseidon
package
That seems fine. The hash is the most expensive thing to be sure gets reused, but I think reusing the secret scalar skips some more computations, and is already a publicly understood concept easier to expose. Check my understanding here, but I think that the second argument to |
The only problem I see with passing the secret scalar is that the signMessage function needs the second part of the BLAKE hash too. |
Ah, so it does. Sorry, I missed that in my scan of the code. I don't really understand the details of how the secret scalar is used in circuits (as the documentation of deriveSecretScalar describes), and the signMessage algorithm doesn't look like it lines up precisely with the linked RFC (https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.5). But certainly from the point of view of refactoring while preserving behavior, you're right that the full hash is needed. Reusing the secret scalar too would save a little bit of work, but not much additional. This complexity is starting to argue me back in the direction of putting this into a class which can manage the various values between steps, but I can see it working fine either way. |
It might not be super clear. It just means that it is recommended to use the secret scalar instead of the private key in Circom, because it does not make sense to recalculate blake1 in circuits (I think it would be difficult to implement).
There's another paragraph for signing messages: https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.6. I didn't check it though.
Same feeling! |
That's what I skimmed, and I see 3 different SHA-512 hashes. Even if blake is replacing that, it doesn't seem like our eddsa code is doing all the same steps. I mostly say that to indicate my non-expertise here, though. For my involvement with this I'd focus on making sure any refactoring doesn't change the mathematics of what's going on. |
You're right. No idea why it's different 🤔 |
@artwyman Reviewing this issue, I'm no longer sure it's worth disassembling |
I think you're welcome to prioritize this however you wish. It would be a performance improvement specifically to the use case of signing many messages with the same key. I don't have data to know how big the performance impact would be, though. FWIW that's a scenario which will definitely come up in Zupass (e.g. when signing a bunch of tickets synced from an external source), but at that level there's also a complexity vs. performance trade-off. As a result, if this proposal were implemented, I don't have immediate plans to integrate it, though it could come up later when performance becomes a concern. Based on our discussion above, I think the best way to do this would be inside a class, with an interface specifically tuned to the signing workflow. That would be an addition to the library, rather than a change to the existing functions, which I think should continue to exist as-is. So I think this would be a non-breaking change if done later. All that leads me to think it's okay to not prioritize this right now, but to revisit it later when someone has a desire for the performance improvement. |
Sounds like the best solution.
I agree! Let's move this task to the backlog. We can think about it as soon as it's actually required by Zupass or other projects. |
Description:
The@zk-kit/eddsa-poseidon
package exports a list of functions and a class. Some of those functions would benefit from reusing variables calculated within the constructor (in particular, thesecretScalar
).The
signMessage
inside theEdDSAPoseidon
class may benefit from re-using the BLAKE hash calculated in the constructor. The hash is now not saved as an attribute and thesignMessage
function only takes aprivateKey
, so it may be necessary to adjust them a bit.The text was updated successfully, but these errors were encountered: