zk-kit
zk-kit copied to clipboard
privacy-scaling-explorations
Optimize `EdDSAPoseidon.signMessage` method in the `eddsa-poseidon` package
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, the secretScalar).~~
The signMessage inside the EdDSAPoseidon class may benefit from re-using the BLAKE hash calculated in the constructor. The hash is now not saved as an attribute and the signMessage function only takes a privateKey, so it may be necessary to adjust them a bit.
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 signMessage function a bit so that the BLAKE hash can be passed in instead of the privateKey and re-used within the class.
Does it make sense?
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 mulPointEscalar here is identical to the secret scalar (the calculations leading up to it seem identical). So an alternative version of signMessage which took secretScalar instead of privateKey as an argument could start at that line.
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.
I don't really understand the details of how the secret scalar is used in circuits
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).
the signMessage algorithm doesn't look like it lines up precisely with the linked RFC
There's another paragraph for signing messages: https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.6. I didn't check it though.
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.
Same feeling!
There's another paragraph for signing messages: https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.6. I didn't check it though.
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.
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.
You're right. No idea why it's different 🤔
@artwyman Reviewing this issue, I'm no longer sure it's worth disassembling signMessage to re-use the Blake hash. It doesn't seem as trivial as refactoring, and I don't know if the benefits of this performance improvement outweigh the possible complexity of the code.
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.
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.
Sounds like the best solution.
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.
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.