[somezero]

> 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/...

[pdpi]

The big novel feature in Nakamoto consensus (the Bitcoin paper one) is precisely that it gives you Sybil-proof BFT without a CA. That's the whole reason for the massive energy consumption.

[somezero]

It doesn't give you sybil-proof. It gives you sybil-resistance, and that, in a non-deterministic protocol.

[wyager]

It gives you sybil resistance with arbitrarily low probability of failure, so you might as well say "proof".

[somezero]

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

[wyager]

I think we're on the same page - I was referring to Bitcoin's algorithm giving you arbitrarily low failure probability, not the OP's paper.

[rocqua]

Sybil proofness does not require a CA. The abstract of your link only states that CAs can be a solution. An alternative approach would be to have the system function as long as one member remains non-sybil.

[somezero]

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