Hi all,
I submitted the new application. Please let me know if you have any questions related to my project.
Best regards,
Dimitri.
Hi @Dimitri - Thank you for submitting your grant proposal! We will review it in the upcoming weeks and reach out if we have any questions.
In the meantime, if you have any questions for us, you can post them to this thread or DM us at @ZcashGrants.
Zcash Community - We want to hear your feedback on this grant! You can post your comments to this thread or DM us at @ZcashGrants if you’d like to provide feedback in private.
Thanks!
2 Likes
hi Dimitri
since math and cryptography are not my specialty I went to AI to understand it better what your proposal is exactly
can u confirm if u implement dis hashing algortihm ting dat it makes some part of Zcash much faster?
what AI told me:
…This new recipe is special because it can make the secret code very quickly. It’s like being able to bake a cake in just a few minutes instead of an hour!..
if dat is de case - I support u
Hi @zerodartz,
the new hash function \mathcal{H}_{new}\!: \{0,1\}^* \to E(\mathbb{F}_{\!q}) to an elliptic curve E works in constant linear time, namely in O(\log_2(q)) multiplications in the basic field \mathbb{F}_{\!q}. The constant behind O is equal to approximately 2 (respectively, 4 if \mathcal{H}_{new} behaves as a random oracle). In two words, a deterministic execution of Müller’s square root algorithm underlies \mathcal{H}_{new}. Recall that the unique bottleneck of Müller’s algorithm (and thereby of \mathcal{H}_{new}) is computing a certain element of one non-full Lucas sequence V_n(\cdot, 1).
In comparison, the previous state-of-the-art hash functions \mathcal{H}_{old} to E are based on Tonelli–Shanks’s square root algorithm instead of Müller’s one. Therefore, they require O(\log_2(q) + \nu^2), where \nu is the 2-adicity of \mathbb{F}_{\!q}, that is, 2^\nu \mid\mid q-1. At the moment, for all Zcash curves \nu = 32. Here, the constant behind O is equal to approximately 1/2 (respectively, 1 if \mathcal{H}_{old} behaves as a random oracle). In fact, if for the role of \mathcal{H}_{old}, SwiftEC is taken, then it is already a random oracle with the constant 1/2, but SwiftEC does not work for some curves. Finally, there is recent Sarkar’s square root algorithm with the complexity O(\log_2(q) + \nu^{3/2}), but I don’t know the exact constant behind O for it.
Let me know if you have any questions.
1 Like
Is this implementation a drop-in replacement for an existing hash function in the protocol? Or would it require a protocol change to use this new hash function?
How do you know the hash function will be useful to the protocol? Has it been reviewed by cryptographers familiar with Zcash?
Execution risks: What obstacles do you expect? What is most likely to go wrong? Which unknown factors could jeopardize success? Who would have to incorporate your work in order for it to be usable?
There are no risks and obstacles, because the hash function has already been constructed in the article.
What if the hash function is broken by further research?
What if it is found unsuitable for use in the Zcash protocol?
What if the next pool change is 5-10 years away, and the new hash function doesn’t get used until then?
5 Likes
Sarkar’s square-root algorithm is already implemented in pasta_curves (sqrt_common in pasta_curves/fields.rs at main · zcash/pasta_curves · GitHub). Our implementation technically takes O(\log_2(q) + \nu^2) field multiplications. But in practice that’s irrelevant because with 2^8-entry tables, that part of the algorithm is 1+2+3+4 = 10 table lookups and a similar number of field multiplications. It’s very fast, and the O(\nu^2) part takes less time than the O(\log_2(q)) part I believe. (Put another way, it would be O(\log_2(q) + \nu) if not for 3 extra field multiplications and lookups.)
I think we are unlikely to change the hash-to-curve algorithm from SSWU, because SSWU is being standardised and it would be quite disruptive, for something that is not a bottleneck.
6 Likes
Correction: it’s 14 table lookups (I had forgotten the inv lookups). The extra 4 are O(\nu) so this doesn’t really affect my argument.
I was going to ask how does it compare to whatever has been implemented in Zcash, but Daira just answered that. As it stands, while super interesting, unfortunately it doesn’t seem it’s worth implementing.
Something that I also think would be important (though it may be moot at this point) would be an analysis on what is the impact of hash-to-curve in the overall performance of Zcash operations (node syncing, RPC calls, or wallet operations) so that everyone can better evaluate the impact of the proposal.
3 Likes
Is this implementation a drop-in replacement for an existing hash function in the protocol? Or would it require a protocol change to use this new hash function?
This is a completely new hash function, hence it is not compatible with old ones.
How do you know the hash function will be useful to the protocol? Has it been reviewed by cryptographers familiar with Zcash?
I don’t know the protocol. Hence, I would like to hear opinions of Zcash cryptographers.
What if the hash function is broken by further research?
Any cryptography can be broken by further research. If it is necessary, we can wait for publication of my article.
What if the next pool change is 5-10 years away, and the new hash function doesn’t get used until then?
You are right that my application (as research in general) may not give an immediate effect.
2 Likes
@daira, thanks for your comment. I heard that table lookups are vulnerable to side-channel attacks (see, e.g., Cache-timing attacks on AES). Is your implementation secure with regards to such attacks ? Your approach may be suspicious, because many critically-minded cryptographers fear table lookups. That is why, it is desirable to avoid them if possible.
2 Likes
There are tricks to doing constant-time lookups on small tables: essentially load the whole table into registers. For the current use of hash-to-curve in Orchard, however, there is no need to protect against timing attacks, because it is only used on constant, non-secret data.
For ZSAs, hash-to-curve will be applied to non-constant asset ids in order to obtain an asset base. But the asset base is then cached in memory, so the hash-to-curve is not in the code path that is executed by a wallet when processing a payment (i.e. when the asset type is secret). The hash-to-curve is only in the path that happens when an asset is issued, which is a public action. So again, it does not need to be constant time.
Although this is not relevant to hash-to-curve, square roots are also used in elliptic curve point decompression. In that case the input is a public point (except when receiving an address that has been kept secret maybe, but that doesn’t seem like a particularly practical attack).
4 Likes
@Dimitri, thank you for your grant submission. The @ZcashGrants Committee has recently voted to reject this proposal, & the meeting minutes regarding this decision will be posted soon.
2 Likes
@daira, why do you use SSWU rather than just taking successive x-coordinates h(m), h(m)+1, … until f(x) is square? Here, E\!: y^2 = f(x) is the given elliptic curve and h\!: \{0,1\}^* \to \mathbb{F}_{\!q} is an auxiliary hash function to the (prime) field \mathbb{F}_{\!q}. If constant-timeness is not necessary, this is the simplest solution, because the condition \sqrt{f(x)} \in \mathbb{F}_{\!q} is rapidly checked in bit time O(\log^2(q)) by widespread Euclidean-type algorithms. And on average, two x-coordinates are enough.
I want to say that all the theory of hash functions to elliptic curves is useless if their input is not secret.
2 Likes
The new application hyperlink appears to be 404-ing. Can you double check that your application contents are available at the correct archive? I was interested in looking at how much funding was requested for this grant.
1 Like
The link should be working now.
2 Likes
This “hash-and-try” method is what we used for DiversifyHash in Sapling. The fact that DiversifyHashSapling is not a total function ended up being very annoying, and leaking through to user-visible properties of the protocol — specifically, that not all diversifiers or diversifier indices produce a valid Sapling address.
Even though we do not need to do hashing-to-curve in the current circuits, we did not want to put a function in the protocol that cannot be implemented in a zk circuit at reasonable cost. That particularly applies to Orchard, where we want it to be possible to move more of the protocol into circuits that are recursively proven; not being able to do that would have closed off potential design avenues for scaling improvements. A circuit for the hash-and-try method would have to handle the worst case, which would multiply the cost of hashing to the curve by a factor of k to get a 2^{-k} failure probability, and k would probably need to be at least 40.
In any case, it was not especially complicated to implement SSWU or to specify its use in Orchard. We just followed an Internet Draft, draft-irtf-cfrg-hash-to-curve-10, which did not exist when we designed Sapling. (Depending on a draft was not ideal, but we made the judgement that it and the papers that it was based on had already had sufficient review, and the standard was unlikely to change in important ways before publication.)
I disagree; having a bounded-cost total function is important by itself. That is, a bounded-cost function is clearly better than an unbounded-cost one, regardless of whether a particular implementation is constant-time.
2 Likes