Grant Proposal: Research on Algebraic Anomalies in ECDSA Signatures for Zcash Transactions
Dear Zcash community,
My name is Andriy Polishchuk. I am an independent researcher and the author of a recently published paper titled “Algebraic Anomalies in ECDSA Signatures Enabling Private Key Recovery Under Ideal Random Nonces” (DOI link).
This paper introduces two novel classes of algebraic vulnerabilities in ECDSA that allow deterministic private key recovery under certain rare but structurally valid conditions — even when nonces are perfectly random. The anomalies were discovered through empirical analysis of over 600 million ECDSA signatures generated on a test elliptic curve, using a transparent Python-based simulation framework available on GitHub: https://github.com/apolish/ECDSA-Anomalies.
Although my experiments were conducted on a simplified curve, the underlying algebraic structure of ECDSA is preserved, raising important questions about possible edge-case vulnerabilities in real-world implementations such as secp256k1, which is used in Zcash.
Grant Proposal Objective
I seek funding from the Zcash Grant Program to:
Extend the current research to scan real-world Zcash transactions for statistical anomalies resembling the algebraic cases (Vulnerability A and B) described in the publication.
Develop an open-source anomaly detection tool for the Zcash ecosystem to analyze signature patterns in shielded and transparent transactions.
Report on potential risks and propose mitigation strategies or statistical validation frameworks, if applicable.
Why this matters for Zcash
Zcash inherits the ECDSA scheme for certain aspects of its transaction verification. While the vulnerabilities outlined in my research do not pose an immediate practical threat, their theoretical existence emphasizes the importance of analyzing signature distributions for hidden algebraic weaknesses.
This work could help Zcash stay ahead of potential cryptanalytic threats by proactively validating its cryptographic assumptions.
Request for Feedback
I would highly appreciate any feedback, questions, or collaboration interest from the Zcash community. In particular:
Has there been prior analysis of this kind on Zcash signatures?
Would the community support funding such a project through the Zcash Grants Program?
Are there any technical constraints or privacy concerns I should take into account when scanning Zcash signatures?
Sorry, but if I understand it correctly, I don’t think this research is worth pursuing. It basically entails to “what if the hash of the message is equal to the negation of the private key times the nonce?”. You can always cherry pick some “vulnerable” values in the parameter space. This could be made simpler by asking “what if the private key was 1” which also has chance of occurring. However the chance of those cherry-picked cases occurring is negligible.
(Additionally, if we assume it’s relevant, this would have a bigger impact in Bitcoin simply due to its much bigger market cap, so it would make much more sense for the Bitcoin ecosystem to fund it…)
Thanks for your comment, and I appreciate the scepticism. Let me clarify a key point:
This is not about cherry-picking x = 1 or asking “what if z = −x·k”. I fully agree that such isolated coincidences are negligible and meaningless.
The research is not probabilistic guessing — it is structural.
The detection method analyses real ECDSA signatures and classifies them into algebraic cases based solely on public values(r, s, z). In certain extremely rare combinations — fully derived, not assumed — the signature structure satisfies closed-form relations that allow deterministic private key recovery. These are:
Case A: m₁ = 1, where s = z·k + r·x·k, and the values align such that x can be recovered.
Case B: m₁ = m₂ > 1, where both s and z relate in a specific way to r·k and x.
No brute force. No nonce reuse. No hypothetical input. Just algebraic conditions derived from actual signature values.
The tool checks if any real Zcash signature in history satisfies these rare but well-defined structural relations. So far, no one has ever audited this — and I believe that confirming their absence would actually reinforce trust in the ECDSA usage of Zcash.
As for Bitcoin, I agree — and I’ll be happy to share the method there later. But Zcash has a tighter security focus and values cryptographic audits, which is why I started here.
I would be happy to expand on the math or show the Python logic if it’s useful.
In Case A you assume zk = a → zk = s (mod (zr-s)) and then compute k from zk and z. But how do you get zk from s? Also, how do you filter for m1=1 in the first place just from the signature and message?
Thanks — and this is the core of Case A logic, so I’ll clarify exactly how it works.
You’re absolutely right: we don’t know zk = z·k directly from the signature, since k (the nonce) is unknown. That’s why in Case A, we don’t try to compute s_zk — we test a specific structural hypothesis:
If yes — the signature is classified as a Case A anomaly, and m₁ = 1 was indeed valid.
To answer your two questions directly:
How do we get s_zk from s?
→ We don’t. We assume s_zk = a based on the modular structure and test it.
How do we filter for m₁ = 1?
→ We apply this test to all signatures. If the resulting x matches the public key, the assumption holds and the signature is flagged.
This is a test-and-confirm method, not a blind assumption. In Case B, by contrast, m₁ can be computed directly (via a quadratic relation), but such signatures are even rarer.
Let me know if you’d like to walk through a real example. I can share code and synthetic data.
In other words, the conditions hold with negligible probability for ECDSA as deployed, and there is no valid attack. I don’t see any argument for there being something useful to fund here.
Thank you for your thoughtful input. I’d like to clarify a crucial aspect of this research:
Although shielded addresses in Zcash use zk-SNARKs and are not vulnerable to ECDSA-related weaknesses, transparent (t-) addresses still rely directly on ECDSA signatures, exactly like in Bitcoin.
In every transparent transaction:
the signature components r and s are public,
the hash of the message z (i.e., the transaction digest) is public,
and the public key P is recoverable from the scriptSig.
These facts make it entirely possible to perform a deterministic audit of past t-address transactions using the algebraic conditions described in my paper.
But here’s the key point:
Yes, the anomalies described (Case A and Case B) are extremely rare.
However:
They are not based on probabilistic guesses — they are derived from strict algebraic structures within the ECDSA equation.
These structures can only be tested once a real transaction is confirmed and all values (r, s, z, P) are on-chain.
And while such a match may never appear — no mathematical proof currently exists that guarantees these conditions can’t arise.
So the risk is minimal, but not zero.
As long as t-addresses are still in use:
by exchanges,
in legacy wallets,
or in migration scenarios,
…this part of the ecosystem remains exposed to ECDSA structure-based attacks.
This research aims not to spread fear, but to verify — deterministically — whether such conditions have ever occurred in Zcash’s transparent transaction history.
Even confirming their absence would be a positive and reassuring result.
Let me know if you’d like to see a deeper breakdown of the verification logic or the test coverage framework.
Of course a (nontrivially) negligible probability is not zero. It’s negligible though. Crypto is inherently based on accepting negligible-but-nonzero probability of attack. (A few schemes have perfect security in isolation, but not when used in nontrivial protocols.)
It’s not that looking for conditions that are supposed to have negligible probability —but that might not do so in an implementation— can’t yield results. Nadia Heninger’s bibliography has a bunch of such examples. But Nadia’s research (for instance) doesn’t just look for conditions because they would be exploitable; it was informed by which implementation errors are plausible.
For Case B, I proved informally that its probability is negligible for uniform-random nonces. (Admittedly that proof has not been thoroughly checked; but I don’t feel that degree of care from me is needed while the paper I’m critiquing has obvious typos/rendering errors.)
For case A, I was unable to prove the corresponding statement, but gave a heuristic argument. I was careful not to over-claim for Case A by saying “no evidence has been provided that the distribution of q is not close to the [one-sided] Uniform Difference Distribution on [0, n)”. The ball is in your court —before I would even potentially consider recommending this for funding— to give some argument that this plausibly might not hold for an implementation. In particular, in order for q to have a different distribution, s_{zr} would have to be correlated with s in some implementation. But I don’t see why it would be.
(I don’t even see why someone would plausibly use that as a backdoor, since if you’re backdooring an ECDSA signing implementation you can do it in ways that would be completely undetectable just from signatures — and that look more like a “bugdoor”. If I were more conspiracy-minded I might speculate that this was a design goal for the NSA; actually I think it’s more likely to have been incompetence.)
That does not matter, because we can prove these conditions happen with negligible probability. It’s already possible that you could generate the key “1”, or that an attacker could guess your key by simply randomly generating one and getting lucky. However those also happen with negligible probability and this is why we don’t care about them.
Thank you, understood — I agree to close the grant application as it stands.
Cases A and B are indeed rare, and I accept that the perceived risk doesn’t justify funding at this time.
That said, I’ll continue my research on other classes of anomalies that I’ve observed appearing on real curves (including secp256k1) in other ECDSA transactions —
though I haven’t yet found analytical methods for private key extraction similar to Case A/B.
In time, I hope to revisit this topic with new insights — and perhaps new implications.
@apolish thank you for your submission. After consideration from @ZcashGrants and sufficient time for the community to provide feedback on the forum, the committee has decided to reject this proposal.
The committee appreciates your grant submission efforts and encourages you to continue as an active member of the Zcash community going forward!
Update: The full grant application has been submitted via the Zcash Community Grants portal.
GitHub Issue: