Does anybody know if consensus algorithms have been proposed that try to reduce centralization by requiring quick coordination across large parts of the network, i.e., it doesn’t work well to have machines only in one place?
Latency comes up occasionally. In fact, the granddaddy of public key crypto, Merkle’s puzzles, relies critically on latency. The problem is, you can only prove upper bounds on latency, not lower bounds, because it is trivial to fake increased latency, but one cannot break the speed of light. If someone responds to your cryptographic challenge within Y milliseconds, you know that they can’t be physically further from you than Z kilometers; but if they fail to respond, they could be anywhere, even next door, and just not responding (for both ordinary and malicious reasons). Nothing stops two machines from pretending to be far away from each other, and making sure they eg communicate only over VPNs with exit points on opposite sides of the globe. Further, if you want to do it over commodity Internet, say if you’re trying to do ‘proof of distance’ by peering only with nodes which respond fast enough that they have to be within Z kilometers of you, public Internet has so much latency that you get poor loose bounds, and someone can pay money for lower latency networking. (This already happens with cryptocurrency mining for the same reasons that HFT firms pay for microwave links. Amusingly, it also happens with computer game companies, not to mention large tech companies prioritizing their own traffic. Google famously owns a ton of fiber it bought up post-dotcom bubble.) Further still, you don’t really care about physical centralization so much as you care about control, and it’s impossible to prove cryptographically in any easy way that two physically distant nodes are not secretly controlled by the same entities in a Sybil attack. You run into similar issues with proof-of-storage.
I didn’t mean trying to fake large distances. I meant graph properties that can be computed more efficiently if a randomly chosen large subgraph of the network has low worst-case delay or some other metric that favors graphs that have homogeneously low delays at large.
You still have issues with Sybil attacks and attackers either accessing special high-speed links (paid for from the successful attacks) or faking latency. You can’t ‘choose a random subgraph’ for the exact same reason you can’t solve cryptocurrency by just ‘choose some “random” peers and decide whether to accept or reject a double-spend based on what they tell you’ - those ‘random peers’ are the very attackers you are worried about colluding. In fact, in an eclipse attack, you might not be able to connect to anyone but an attacker!
I think we are talking past each other. I don’t want to defend against Sybil attacks or network partitions. These parts must be solved by different parts of the algorithm. I just want to take the advantages of colocation away and incentivize a homogeneously distributed network overall.
Any incentive is something to be attacked and sucked away by Sybils pretending to be distant when actually near & enjoying all other benefits of being near.
I think you misunderstand my proposal. I don’t want to incentivize being far away. I want to incentivize being close to many different nodes. A Sybil will have difficulty being close to multiple physically separated nodes at the same time.
There is no difference at the hardware level between being ‘close to’ and ‘having a low-latency connection to’, as I already explained. And to the extent that having those connections matter, miners already have them. In particular, in Ethereum, due to the money you can make by frontrunning transactions to hack/exploit them (‘miner exploitable value’), HFT Ethereum miners/stakers invest heavily in having a lot of interconnected low-latency Sybils nodes so they can see unconfirmed transactions as quickly as possible, compute a maximally-exploitative block (eg. temporarily jacking up the price of a thing being purchased using a flash loan solely to rip off a specific transaction), and get that block committed before anyone can beat them to the same exploit. Having a lot of MEV is considered a bad thing and Ethereum types are spending increasing effort on approaches like commit-and-reveal to minimize MEV, which comes at the expense of users and makes them very unhappy. You could, I suppose, design a protocol which has extra MEV by designing transactions to be especially exploitable, but most people would consider that a bad thing...
Thank you for the detailed explanation. I understand that the incentives are already to have a maximally well-connected network with nodes between (latency-wise) geographically distant other nodes whenever that is feasible from an interconnect point.
Though thinking about it, it probably means that this burns not only compute but also network traffic.
Does anybody know if consensus algorithms have been proposed that try to reduce centralization by requiring quick coordination across large parts of the network, i.e., it doesn’t work well to have machines only in one place?
Latency comes up occasionally. In fact, the granddaddy of public key crypto, Merkle’s puzzles, relies critically on latency. The problem is, you can only prove upper bounds on latency, not lower bounds, because it is trivial to fake increased latency, but one cannot break the speed of light. If someone responds to your cryptographic challenge within Y milliseconds, you know that they can’t be physically further from you than Z kilometers; but if they fail to respond, they could be anywhere, even next door, and just not responding (for both ordinary and malicious reasons). Nothing stops two machines from pretending to be far away from each other, and making sure they eg communicate only over VPNs with exit points on opposite sides of the globe. Further, if you want to do it over commodity Internet, say if you’re trying to do ‘proof of distance’ by peering only with nodes which respond fast enough that they have to be within Z kilometers of you, public Internet has so much latency that you get poor loose bounds, and someone can pay money for lower latency networking. (This already happens with cryptocurrency mining for the same reasons that HFT firms pay for microwave links. Amusingly, it also happens with computer game companies, not to mention large tech companies prioritizing their own traffic. Google famously owns a ton of fiber it bought up post-dotcom bubble.) Further still, you don’t really care about physical centralization so much as you care about control, and it’s impossible to prove cryptographically in any easy way that two physically distant nodes are not secretly controlled by the same entities in a Sybil attack. You run into similar issues with proof-of-storage.
Have them prove an upper bound on latency to something across the globe?
I didn’t mean trying to fake large distances. I meant graph properties that can be computed more efficiently if a randomly chosen large subgraph of the network has low worst-case delay or some other metric that favors graphs that have homogeneously low delays at large.
You still have issues with Sybil attacks and attackers either accessing special high-speed links (paid for from the successful attacks) or faking latency. You can’t ‘choose a random subgraph’ for the exact same reason you can’t solve cryptocurrency by just ‘choose some “random” peers and decide whether to accept or reject a double-spend based on what they tell you’ - those ‘random peers’ are the very attackers you are worried about colluding. In fact, in an eclipse attack, you might not be able to connect to anyone but an attacker!
I think we are talking past each other. I don’t want to defend against Sybil attacks or network partitions. These parts must be solved by different parts of the algorithm. I just want to take the advantages of colocation away and incentivize a homogeneously distributed network overall.
Any incentive is something to be attacked and sucked away by Sybils pretending to be distant when actually near & enjoying all other benefits of being near.
I think you misunderstand my proposal. I don’t want to incentivize being far away. I want to incentivize being close to many different nodes. A Sybil will have difficulty being close to multiple physically separated nodes at the same time.
There is no difference at the hardware level between being ‘close to’ and ‘having a low-latency connection to’, as I already explained. And to the extent that having those connections matter, miners already have them. In particular, in Ethereum, due to the money you can make by frontrunning transactions to hack/exploit them (‘miner exploitable value’), HFT Ethereum miners/stakers invest heavily in having a lot of interconnected low-latency Sybils nodes so they can see unconfirmed transactions as quickly as possible, compute a maximally-exploitative block (eg. temporarily jacking up the price of a thing being purchased using a flash loan solely to rip off a specific transaction), and get that block committed before anyone can beat them to the same exploit. Having a lot of MEV is considered a bad thing and Ethereum types are spending increasing effort on approaches like commit-and-reveal to minimize MEV, which comes at the expense of users and makes them very unhappy. You could, I suppose, design a protocol which has extra MEV by designing transactions to be especially exploitable, but most people would consider that a bad thing...
Thank you for the detailed explanation. I understand that the incentives are already to have a maximally well-connected network with nodes between (latency-wise) geographically distant other nodes whenever that is feasible from an interconnect point.
Though thinking about it, it probably means that this burns not only compute but also network traffic.