HN user
my username at protonmail.com
The entire argument is based on the definition of an “Incoherent cryptosystem”, which is too restrictive to be useful for cases that you want eg. Tor is also developed and distributed by Tor people and it is supposed to protect you against everyone, including the Tor people.
This is not just a funny joke, but also timely given the recent sanctions.
https://en.wikipedia.org/wiki/International_sanctions_agains...
FHE is simply the wrong tool here. FHE is for a central server operating on data held/known by another. They want MPC -multiple parties jointly computing on distributed data- and that’s fairly more efficient.
Gauss 2.0; He’s very prolific, very famous in the math community. In this context, he is noteworthy because he’s taking automated theorem proving seriously which destigmatizes it for other pure mathematicians.
Not sure simplicity of spec translates into simplicity of user code. This change is backward compatible and will allow things that previously were disallowed.
People [sadly] put a lot of "exotic" cryptography/distributed systems under the term "blockchain" eg. If you want to do byzantine agreement with sub quadratic message complexity, where do you look it up? If you want to do high throughput threshold signing, where do you look it up?
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.
It’s all just bytes and hashes and alike at the bottom. Absolutely nothing magical. It is the abstractions over them that makes them esoteric, not the fundamental building blocks.
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.
zk signature schemes exist and are implied by the existence of one way functions and publicly verifiable nizk.
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...
A signature is a PoK, but not ZK.
Sybil attacks [1] came out about a decade before the Red Balloons paper [2] or the DARPA Challenge itself [3]. It is proven in [1] that CA is necessary for a Sybil-proof system, which made people to talk about Sybil resistance eg [4] - all before Bitcoin or the DARPA challenge.
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 signatures are not Schnorr signatures. A Schnorr signature is dlog proof made non interactive with fiat Shamir binded with the message, and that is equivalent/verifiable as an EdDSA signature, up to one time signing per message (as Schnorr is not deterministic)
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.
I was a long time keepass user but moved to Bitwarden. My problem with keepass is the low quality and often poorly supported closed source clients that you get on mobile.
This is a molecule. With a provable cryptographic property. Honestly for this one I don’t care about “real security”.
Thanks! I’ll definitely take a look. These works are valuable but my problem is just with that particular claim about CAs.
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.
I’m not saying his paper is wrong or not up to the workshop quality. But he’s saying something against an easy-to-prove impossibility theorem in a seriously sloppy/hand-wavy way. I trust Doceur and the entire early 2000s literature more than his paper. But who knows, I might be wrong.
P.S. Also commented about the paper here: https://news.ycombinator.com/item?id=30561786
The only way to provably prevent Sybil attacks are CAs (https://www.freehaven.net/anonbib/cache/sybil.pdf) This is why almost all P2P and DHT papers assumed existence of a CA in their system model eg. Castro’s secure routing etc.
P.S. PoS protocols are also Sybil resistance mechanisms. Look into Tendermint and compare it with, say, PBFT.
Sure! It’s P2P, but doesn’t need centralized certificate authorities (= Has some Sybil resistance)
heapq exposes a minheap by default, but there is a maxheap as well that for some reason, is not exposed! Just do heapq._heapify_max
The paper is simple and readable enough for me to not have to comment. Anyway, The abstract itself says:
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
I'm fine with a sybil resistance mechanism (although it's not sybil-proof, and some particular forms of sybil-resistance are based on faulty models [1])
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
It doesn't give you sybil-proof. It gives you sybil-resistance, and that, in a non-deterministic protocol.
The 3f + 1 assumption means these protocols cannot be deployed in open peer-to-peer systems, since they would be vulnerable to Sybil attacks. In contrast, my approach makes no assumption about the number of Byzantine nodes.
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/...
It depends on the type of the work you do. Whenever I have to cast ints to floats because I want to use something in math library, I want to claw my eyes out.
How much do your colleagues (ab)use goto statements that Go provides? :)
Move 2 million dollars.
So if coinbase was open source, and you had forked it to add BSV support, that’d mean coinbase was decentralized?! Open source/forkability != decentralization. The whole point of decentralization is no particular entity gets to decide something for everybody, and that’s precisely why it’ll take a long long time for regulators to be okay with it.
Previously, it used to be the case that if you don’t want to repair your device or upgrade your RAM you wouldn’t have used Thinkpads, as a MacBook is better at showing you websites. Now, unfortunately, not so much.
Ultra-portable is a feature, not an end goal. Netbooks’ end goal were to be portable and they failed miserably. Most people work on thinkpads, I don’t know about you, but I actually cannot think of a time where my browser, IDE plus a few cached programs don’t exceed 16GB.
I’m just curious whether you know how blockstack in the “about” section of your profile relates to Bitcoin.... That’s just one of the examples illustrative of some sort of Bitcoin’s value outside being a currency - which coincidentally, hasn’t been the goal of core devs for quite a while.