TLDR: proving ownership of one out of 1 million utxos, means 1 million keys, with a proof size that is reasonably compact, and a verification time that is reasonably quick (hence we talk about "sublinear", i.e. less than O(n)).
Not TLDR: you can see work I did previously to find schemes that are at least close to this here: https://reyify.com/blog/little-riddle , and the referenced earlier blog posts. These aren't, probably, fast enough in verification. Then there's also the idea of using Curve Trees which I discussed in a post here on nostr in some detail, recently. This is another approach (at least, I *think* it is), but now I think about it, we *might* still get stuck with linear verif time here too.
Also, AFAICT (haven't really got into this properly), this project uses SpartanNIZK specifically, and that does *not* have sublinear verification time (it has a cost component linear in the size of the R1CS, specifically), which is probably the single most crucial property if you want, as I do, to be able to publish "I own one of a huge number of keys" proofs. Groth16 has constant (very fast) verification time irrespective of circuit complexity, which means for some applications, the trusted setup is probably the better choice.
However while it wasn't too hard to get basic toy examples to compile and run, there are a lot of nasty details here. You need to include the signature verification in the ZK proof, here they used ECDSA not Schnorr (and they converted it into a format suitable for the R1CS), not a huge deal, but then there's the part that's quite demanding: how to include a merkle tree inclusion proof inside the circuit; they are using the Poseidon "ZK-friendly" hash function for this ( https://www.poseidon-hash.info/ ), so to do this kind of work properly you kind of have to really understand the intricacies of that hash function.
Whichever way you look at it, it's a very promising area, things have come a long way in a few years. In particular the circom library(**) makes it pretty easy to build at least "basic" snarks, using groth16 (spartan does *not* use that construction, though, groth16 is super efficient but has a per-circuit trusted setup ceremony - undesirable, for some things!).
** docs.circom.io
Spent the last several days looking into this ZKP project:
https://github.com/personaelabs/spartan-ecdsa/tree/main
. It's really interesting; first, it uses transparent snarks, so no trusted setup. Second, this specific project uses secq256k1 to allow field arithmetic (for the signature) to be included in the constraints efficiently. Third, this specific application of spartan ( https://eprint.iacr.org/2019/550 , and https://github.com/Microsoft/Spartan ) is to do exactly what I've been looking for: prove in ZK that a given signature is one one of a large set of public keys
However while it wasn't too hard to get basic toy examples to compile and run, there are a lot of nasty details here. You need to include the signature verification in the ZK proof, here they used ECDSA not Schnorr (and they converted it into a format suitable for the R1CS), not a huge deal, but then there's the part that's quite demanding: how to include a merkle tree inclusion proof inside the circuit; they are using the Poseidon "ZK-friendly" hash function for this ( https://www.poseidon-hash.info/ ), so to do this kind of work properly you kind of have to really understand the intricacies of that hash function.
Spent the last several days looking into this ZKP project:
https://github.com/personaelabs/spartan-ecdsa/tree/main
. It's really interesting; first, it uses transparent snarks, so no trusted setup. Second, this specific project uses secq256k1 to allow field arithmetic (for the signature) to be included in the constraints efficiently. Third, this specific application of spartan ( https://eprint.iacr.org/2019/550 , and https://github.com/Microsoft/Spartan ) is to do exactly what I've been looking for: prove in ZK that a given signature is one one of a large set of public keys
Also, stablecoins are not stable and they are not coins.
The Federal Reserve....
wait I'm noticing a pattern here 😄
It's not a simple question ... blatant hack-ability is mostly not considered realistic. 2 decades of usage in the wild speaks to this. Is (EC)DSA a bit weaker than Schnorr theoretically? Yes. It has some quirks. My guess, if NSA were motivated to get this in, it was more "we'll crack a few systems here and there because this is hard to get right", but even that is a stretch. The biggest pitfalls in DSA are there in Schnorr too: bad nonce randomness. DSA has more weird special cases though, like "forgeries" that aren't real forgeries.
😄 I like this conspiracy theory: NSA paid Claus Schnorr to apply for an extremely aggressive patent so no one could use the stronger signature scheme.
Also spartan-ecdsa is really interesting.
I have it in noble-curves readme https://github.com/paulmillr/noble-curves#weierstrass-short-weierstrass-curve
Interesting, thanks. Cool that you can swap it out for everything including signing! Curious whether you have benchmark/ test code that you could run against that swapped out for secp,
I like this detail from Dan Bernstein's 2014 takedown of ECDSA (I have to specify the year, he's probably written like 10 others):
"DSA was "invented" by NSA's David Kravitz, according to a patent application filed secretly in July 1991. It was proposed as a standard by NIST the next month. NIST didn't admit NSA's role until after a lawsuit was filed by Computer Professionals for Social Responsibility. NIST memos state that the "reasons for the selection" of DSA are summarized in an NSA document; as far as I know, that document is still classified Top Secret."
Voluntary-basis fact checking is interesting, but honestly I don't see it actually working except in edge cases.
Who decides if information is correct?
(There's a secondary question, is there an ethical basis for punishing someone that spreads information that is adjudicated to be false, without knowing for sure that they knew it was false when they spread it; if yes, then how can anyone know that for sure?)
I've probably said it before, but I was absolutely shocked when I heard "serious" people starting to use the term fake news some ~15 years ago. The world is full of lying of course, and half truths even on highly respected media, but the idea that "fake news" is a real thing that needs to be legislated sounded, and still sounds incredibly childish (see above). I still genuinely don't get it.
The real problem is not the spreading of falsehoods, it's the cancer of stifling free speech because people are saying things you disagree with, with threats of violence - which actually *creates* much more spreading of falsehoods via backchannels. I saw this first hand in China.
(None of this means I disagree with applying the handicap principle to stuff like online discourse, that's an interesting topic but it won't solve "fake news", because that is a broken concept).
ah, ty
prime, 256 bit, koblitz
https://crypto.stackexchange.com/questions/18965/is-secp256r1-more-secure-than-secp256k1
koblitz method is very deterministic, and thus widely regarded as strong against backdooring via random values, which are used with these keys with ECDH to generate shared secrets
the R is from random, meaning that it is more likely to be possible the group was selected because of it having a convenient symmetry to enable a backdoor
so, yeah, koblitz ftw, he may well deserve some lionizing from us bitcoiners
Re the 'few bits weaker' for Koblitz curve, I *believe* they refer to the fact that curves of this type (j-invariant 0, y^2=x^3 + 0x +C), have a non trivial endomorphism y-> -y, x -> qx, where q is a cube root of unity in the finite field. Through some dark arts this reduces the amount of work needed to brute force a private key by a factor 6, i.e. you lose 2 to 3 bits of security. But I don't even know what paper I read that in, so barely above the 'revealed to me in a dream' level of citation here.
About suspicions about parameter selection, the big story was the hashing used to create the group generators, but it is also here that using a prime order group *should* help .... in a cyclic group of prime order every element (except the identity) is a generator, and there's some vague sense in which "if one generator were not secure, nor would any other be" (see: "random self-reducibilty").
If you want to see a world class expert explain people's concerns about the NIST p256 generators, check this out:
The one you're remembering is secp256r1 - it was for a long time the most popular group in use for TLS on the internet. Plus a few other contexts, it was basically 'industry standard' until the DJB stuff (curve25519/ed25519) slowly took over.
(the 'k' is for Koblitz curves, named after Neal Koblitz. I forget what the 'r' stands for. The 'p' is for prime, i.e. prime order curve. And SEC = 'standards for efficient cryptography').
You have a point.
Here's a counterpoint: young people often dream of becoming the best sportsball player ever to play sportsball. Sometimes they're motivated enough to try to achieve it. Often they come up with brilliant new techniques for, uh, sporting the ball. But very few dream of making up different rules for the game of sportsball.
Still, you do for sure have a point.
The TLDR here is that, yes, this was an implementation error, much as Monero made an implementation error in not checking the order of points, using the same curve with cofactor 8. in both cases the errors were patched. But the errors were very easy to miss and absolutely disastrous, especially in the libgcrypt case, allowing cracking of keys in seconds for any process that was sharing the same RAM.
Others, like JP Aumassin (author of the excellent 'Serious Cryptography'), and apparently Matt Green, apparently shared, partly, my skepticism about not validating inputs:
https://research.kudelskisecurity.com/2017/04/25/should-ecdh-keys-be-validated/
which btw links to this entertaining, concrete take on why not checking inputs is dodgy as hell: https://vnhacker.blogspot.com/2015/09/why-not-validating-curve25519-public.html
Do I have a point in this endless wittering? :) Well, I've always thought that engineers, and sometimes the most brilliant ones are the most guilty of this, have a tendency to over-optimise and over-engineer, and simplicity is absolutely key for robustness. There is nothing simpler than a group with NO structure - a cyclic group of prime order.
And as a counterpoint, building a system which is so cool in its sophistication that you don't need to check whether external inputs are adversarial, just lacks common sense.
But despite the meaningful, but probably over-the-top "immune to sidechannel attacks" claim on curve25519's wikipedia page ("citation needed" - indeed!), the real point to me is that in practice, using a group which is a subgroup of the full curve, is dangerous. And this is borne out, e.g. by this paper from 2017:
https://eprint.iacr.org/2017/806
Quote:
"Since Libgcrypt’s implementation of Curve25519 uses the Montgomery ladder for scalar-by-point multiplication, branchless formulas for point doubling and addition, and built-in countermeasures specially designed to resist cache attacks, our attack cannot observe high-level key dependent behavior, such as key-dependent branches or memory accesses. Instead, we achieve key extraction by combining the specific mathematical structure of Curve25519 with low-level side channel vulnerabilities deep inside Libgcrypt’s basic finite field arithmetic operations. ** By observing the cache access patterns during at most 11 scalar-by-point multiplications, our attack recovers the entire secret scalar within a few seconds**. We note that the mathematical structure that enables our attacks in also present in other popular curves such as Curve41417 [15] and Curve448 [44] (Goldilocks curve) when represented in Montgomery form [57]."
(emphasis mine).
The TLDR here is that, yes, this was an implementation error, much as Monero made an implementation error in not checking the order of points, using the same curve with cofactor 8. in both cases the errors were patched. But the errors were very easy to miss and absolutely disastrous, especially in the libgcrypt case, allowing cracking of keys in seconds for any process that was sharing the same RAM.
Others, like JP Aumassin (author of the excellent 'Serious Cryptography'), and apparently Matt Green, apparently shared, partly, my skepticism about not validating inputs:
https://research.kudelskisecurity.com/2017/04/25/should-ecdh-keys-be-validated/
which btw links to this entertaining, concrete take on why not checking inputs is dodgy as hell: https://vnhacker.blogspot.com/2015/09/why-not-validating-curve25519-public.html
But despite the meaningful, but probably over-the-top "immune to sidechannel attacks" claim on curve25519's wikipedia page ("citation needed" - indeed!), the real point to me is that in practice, using a group which is a subgroup of the full curve, is dangerous. And this is borne out, e.g. by this paper from 2017:
https://eprint.iacr.org/2017/806
Quote:
"Since Libgcrypt’s implementation of Curve25519 uses the Montgomery ladder for scalar-by-point multiplication, branchless formulas for point doubling and addition, and built-in countermeasures specially designed to resist cache attacks, our attack cannot observe high-level key dependent behavior, such as key-dependent branches or memory accesses. Instead, we achieve key extraction by combining the specific mathematical structure of Curve25519 with low-level side channel vulnerabilities deep inside Libgcrypt’s basic finite field arithmetic operations. ** By observing the cache access patterns during at most 11 scalar-by-point multiplications, our attack recovers the entire secret scalar within a few seconds**. We note that the mathematical structure that enables our attacks in also present in other popular curves such as Curve41417 [15] and Curve448 [44] (Goldilocks curve) when represented in Montgomery form [57]."
(emphasis mine).