somezero

https://en.wikipedia.org/wiki/Liouville_function

https://en.wikipedia.org/wiki/International_sanctions_agains...

An allergic reaction to the term "blockchain" is to miss the forrest for the trees... and I would imagine the authors share the same point of view.

As to why your example isn’t zero-knowledge proof of knowledge of a password, it’s because hash of the same password is always the same thing. So what if someone copies the hashed password and passes it as their own? You say, sign something? But I can reuse the signature. You say, sign a random challenge? Okay, but what if, on the other side, the verifier (ie. the app) adaptively picks a challenge instead of randomly sampling it? … Continue this line of thought, and once you have the correct solution, simplify it and remove the unnecessary parts (eg. Signing something is too strong of a requirement) and you get something called Zero-Knowledge proof of knowledge out of an honest-verifier sigma protocol.

As for ZK proofs that are not proofs of knowledge, then the easiest way to think of it is an encrypted data structure like a database. Imagine the client wants to check whether an element is in some set on a server, where the server has an “encrypted” form of a set and can’t see what’s in it. How can the server check membership of an element and convince the client? That’s done with a ZK proof. You say what about Fully Homomorphic encryption? That’s also technically ZK… what’s not a ZK? For anything that you can’t write a simulator. What’s a simulator? Pick a cryptography textbook.

Almost. The result is from CRYPTO89 paper of Bellare and Goldwasser. They derive a signature scheme from a nizk. It is not known whether you can get a nizk from a signature scheme. Moreover, no signature scheme can be a ZK: https://crypto.stackexchange.com/questions/35177/is-using-di...

Unless I’m categorically missing something, Claims like network centralization is much less likely in a Sybil-proof system, is just plain wrong and confusing, to say the least, if discussed “formally” and “mathematically”.

[1] https://www.microsoft.com/en-us/research/publication/the-syb...

[2] https://arxiv.org/pdf/1111.2626.pdf

[3] https://en.wikipedia.org/wiki/DARPA_Network_Challenge?wprov=...

[4] https://link.springer.com/chapter/10.1007/978-3-540-85230-8_...

EdDSA being deterministic, means it’s not Schnorr by definition.

The other difference of EdDSA is having a different keygen process: SHA512 then clamp the first 32 bytes (and this process breaks down all additive key derivation that’s nice to have) clamping is not the problem and you have to clear cofactors for Schnorr over that curve anyway, but it’s the hashing at the beginning that’s different and has nothing to do with cofactor clearing.

The other difference of EdDSA is not having a standardized verifier (keywords are “cofactored” and “cofactorless” verifier) and this breaks down another nice property of Schnorr signatures which is signature aggregation.

Overall the standards for EdDSA -unfortunately- still leave a lot to be desired.

1. This impossibility theorem is proved in a really broad setting (assuming a “broadcast communication cloud” and a P2P channel). If he wants to circumvent the impossibility theorem he should clearly specify the system model and say how it differs from Doceur’s. There are other instances where by playing with the model you go around an impossibility theorem, but you have to specify the differences. Especially since this theorem is so well known/cited.

2. Some claims in the old paper are just plain wrong. Like, you can’t say it’s Sybil resistant just because it tolerates arbitrary number of Byzantine nodes. Dolev-Strong also needs just one honest party, but it requires a CA.

P.S. Also commented about the paper here: https://news.ycombinator.com/item?id=30561786

P.S. PoS protocols are also Sybil resistance mechanisms. Look into Tendermint and compare it with, say, PBFT.

> This paper shows that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities.

And the proof is a few pages later in a few Lemmas. Note that this paper is where Sybil attacks actually come from, and you can see almost all DHT security papers (eg. Castro’s secure routing paper [1]) assume a CA.

[1] section 3.2 of https://www.cs.rice.edu/~dwallach/pub/osdi2002.pdf

The problem is that this paper doesn't employ such mechanisms:

> This assumption is problematic for P2P systems...they must either exercise centralised control over which nodes are allowed to join the network, or employ expensive Sybil countermeasures such as proof-of-work [30]. This paper shows... is possible to guarantee the standard CRDT consistency properties even in systems in which arbitrarily many nodes are Byzantine, e.g. where the Byzantine nodes outnumber the correct nodes. This makes the algorithms immune to Sybil attacks...

This argument is incorrect. The counter-example is Dolev-Strong [2]. The number of faulty nodes is not fixed, but still needs a CA.

[1] https://eprint.iacr.org/2020/019.pdf

[2] Section 3.4 of http://elaineshi.com/docs/blockchain-book.pdf

I'm confused - probably because I haven't finished reading the paper.

1. Sybil-proof-ness requires a CA [1]. It's orthogonal to whether or not a protocol is BFT. Specifically, the classical BFT protocols "assume" there exist a CA, and then prove their protocols to be BFT.

2. I won't comment whether 3f+1 protocols cannot be deployed in open P2P systems (they can), but "makes no assumption about the number of Byzantine nodes" is weird. This result is valid in a particular system/time model eg. With PKI, in synchronous setting, for any `f` one can achieve consensus in `f+1` rounds using Dolev-Strong. This means you make no assumption about `n`, but the protocol is impractical for variety of reasons eg. large `n`, strong synchrony etc.

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...