An illustrated proof of the CAP theorem \ stacker news ~tech

An illustrated proof of the CAP theorem mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/

191 sats \ 3 comments \ @hn 8 Oct tech bot

This link was posted by tripdout 2 hours ago on HN. It received 47 points and 17 comments.

2298 sats \ 1 reply \ @supertestnet 8 Oct

I don't think bitcoin satisfies any of these qualities, not according to the definitions given in the article.

Consistency

If we are discussing the mempool, it is definitely not consistent. You can quickly ascertain this experimentally by sending a transaction only to peer 1 and then immediately requesting a copy of the mempool from from peer 1 and peer 2. What will happen? They will very probably give you back different copies of the mempool. This is not consistent per the article's definition: "In a consistent system, once a client writes a value to any server and gets a response, it expects to get that value (or a fresher value) back from any server it reads from."

But of course, the mempool isn't technically "part of" bitcoin's consensus rules -- the blockchain is. But the same thing applies there. If you find a block in bitcoin and send it to peer 1, then immediately request a copy of the latest block from peer 2, peer 2 may not know about it yet. So you "[wrote] a value to [one] server...[got] a response...[and got an older value]...back from [another] server." This violates their definition of consistent, so bitcoin, per their definitions, is not an example of a consistent system.

Availability

This one I'm less sure of. Your bitcoin client can craft a "write" request intended to be added to the blockchain (i.e. you can craft a transaction) and send it to a peer, but pay a fee of 0. The peer will then probably drop the request. If your client then makes a "read" request, the peer will likely reply with either the same chain it had before or a different one, but still without the user's transaction in it. So I think, in bitcoin, write requests are sometimes ignored. I think this violates their definition of availability: "The server is not allowed to ignore the client's requests."

I'm not sure though because I think bitcoin might satisfy their definition of "not ignoring requests" as long as the peer sends back an error message. If he sends back an error message, he didn't "ignore" your message, he replied. But even there, I don't think peers in bitcoin have to return error messages. I haven't checked the codebase, but I doubt you would ban a peer for a single ignored message. I think you would ban them if they ignored "multiple" requests, but not for a single one. So I'm not entirely sure. You might say "but if they ignore a message that means the peer crashed, and the article says it doesn't count as an ignored message if it was due to a crash." And that might be true -- I'm not sure -- but Bitcoin also doesn't exactly have a "spec" so if a node "chose" to literally ignore 1% of messages I don't think this would count as a node "crashing." It would just be a slightly jerk-ish node, and I don't think there's anything in bitcoin that forbids that.

Partition tolerance

This is defined as "the network will be allowed to lose arbitrarily many messages sent from one node to another."

This is what I was talking about just a moment ago: I really don't think any bitcoin client bans peers just for dropping one message. But I do suspect they ban peers who drop "arbitrarily many" messages -- e.g. all of them. So per this definition I actually don't think bitcoin qualifies as partition tolerant. I think you will ban peers if they drop a certain number of messages, and that seems inconsistent with the article's definition of a partition tolerant system, which is supposed to permit nodes to lose "arbitrarily many messages" without issue. But again, I'm not entirely sure -- "the network" is fine even if you ban one peer, since you have seven others. So I just don't know for this one, but I don't think bitcoin satisfies it.

0 sats \ 0 replies \ @south_korea_ln 10 Oct

Thanks for this.

I prefer trusting your analysis than the one cooked up by ChatGPT in my comment ;)

111 sats \ 0 replies \ @south_korea_ln 8 Oct

I had to ask what ChatGPT thinks of the CAP theorem in the context of Bitcoin.

Yes, the CAP Theorem does apply to Bitcoin, as it is a decentralized network that can be seen as a type of distributed system. The CAP Theorem states that in a distributed system, it is impossible to simultaneously achieve Consistency, Availability, and Partition Tolerance. Bitcoin, as a blockchain network, faces the same trade-offs described by the CAP Theorem.

In Bitcoin's context:

Consistency: All nodes in the network agree on the same state of the blockchain. This is achieved through consensus mechanisms (e.g., Proof of Work), but can lead to delays in confirming transactions.

Availability: The system is operational and accessible to participants, meaning transactions can be submitted and processed. Bitcoin strives for high availability.

Partition Tolerance: The system continues to function despite communication breakdowns or delays between nodes (network partitions). Bitcoin prioritizes partition tolerance, ensuring the network remains functional even if nodes are temporarily disconnected.

Bitcoin's design favors Partition Tolerance and Availability, often at the expense of Consistency. This is because achieving immediate consistency across the global network is challenging due to latency and potential network partitions. For instance, Bitcoin may temporarily show conflicting versions of the blockchain (due to forks) until consensus is reached after several blocks, meaning eventual consistency is favored over immediate consistency.

Thus, Bitcoin, like other distributed systems, adheres to the CAP Theorem's trade-offs.