It would be difficult to modify POS to have these properties, but the question of how best to accomplish that would be something for developers in those other networks to address.
Ok, I've read about this before but can someone with big brain dispute this? Seems like a solution to quite a problem but as it's crypto, not entire truth could be told here
> as any routing node which self-clones to gain a larger share of routing-work for a given transaction also reduces by half the ability for that transaction to contribute towards the valid block production work threshold
Seems like the primary assumption is that Sybill only happens vertically (one node being taken as multiple), but in reality Sybil is usually a per-actor problem, i.e. a CDN could be by a single actor created to ensure minimal hops thereby creating an effective Sybill attack.
Disclaimer: this is my read of their system it might have different counter-measures/assumptions.
The paper is deeply flawed. The most important flaw is admitted by the authors in the paper in the final paragraph of Part 1.:
"Until we reach the point we can formally establish that users are incentivized
to broadcast their transactions to multiple nodes, we ask readers to treat this assumption as a design parameter as well."
To put it simply, the proof requires behavior by users which is neither incentivised or enforced. Other egregious flaws are that the "proof" insists that sybil actors do things not required of non-sybil actors, i.e. add unnecessary routing hops, and that sybil actors are arbitrarily excluded from being the orgin node.
Author of the original paper this write-up was based on here. The sybil attack as a theoretical problem is defined in the "Red Balloons" paper ("information propagation without self-cloning") so that might be a good starting point.
The solution formally and mathematically achieves these properties:
- not profitable to add routing hops
- profitable to share with others
- not profitable to share with yourself (!!!)
If you have a single central entity somewhere that isn't a sybil attack. Nothing wrong with being concerned about network centralization, but you're much less likely to have it in sybil-proof systems as above given that nodes suddenly have commercial incentives to share data as opposed to hoarding it.
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”.
I think perhaps you should read the paper if you want to have a deeper discussion? An understanding of how the mechanism works should make it clear how the solution enables outbound payments to network nodes, which -- in turn -- creates a for-profit incentive to run access points and network infrastructure.
Self-provisioning networks are indeed more strongly resistant to "centralization" than those which are deployed by outside parties. The alternative in the blockchain space is a reliance on outside parties and business models like Infura to provide access nodes and APIs. Unfortunately, any external business model capable of monetizing such infrastructure requires closure around data-and-money-flows, which creates key points where cartelization and monopolization emerges.
Looking at the links you've provided, afaict you seem mostly concerned that the term "sybil-proof" is used to describe a situation in which not using multiple identifies to collude is a dominant strategy instead of an "impossibility according to the laws of physics"? Four points here:
The first is we're dealing with an academic term that is used in a specific context ("no information propagation without self-cloning") and even more specifically in the context of an impossibility proof that has stood for a decade; showing that this impossibility proof is not actually valid is a substantive step forwards and nitpicking terminology is missing the point.
The second is that your definition isn't better. Even networks with trusted third parties cannot prevent sybilling by this definition since it creates a definitional impossibility. While a certificate authority can limit entry, it can never truly know that two distinct identities are not controlled by the same person. All a CA really does is provide a point of closure (monopolization, centralization) which can theoretically identify and tax colluding participants.
The third is that achieving a dominant strategy in which sybilling is disincentivized is a massive step forward. It does not make sense to refer to this as "sybil-resistance" in a field in which mechanisms without this property are considered to have "sybil-resistance".
Finally, and most importantly, one of the consequences of this mechanism that is that all attack vectors that can be carried out using multiple identities are more efficiently carried out with a single identity. So it is not the existence of multiple identities or the collusion between them that is the source of the problem.
Could you explain a bit more how your example of 'a single actor minimizing hops' creates an effective Sybil attack? If I understand, you mean to describe a node which is not adding unnecessary hops but is itself posing as unique identities to different users.
If so, the response to that is: 'this type of behavior doesn't grant this node an increased ability to influence consensus compared to if they routed all data under the same identity.'
If you wanted to send a transaction you would need to pick a node to share it with. The goal of the Sybil attack is to try and increase the likelyhood that it gets shared to nodes the attacker owns. The attacker then shares the transaction directly to miners.
If gossip works by picking 3 random nodes to share transactions with if an attacker owns 1000 out of 1010 nodes they will very likely be the only one who transactions get shared to.
Sure, but unless the 1000 nodes the attacker owns do something useful for actually routing data, you only need to route to one non-censorious node with the same capabilities who, despite being only one node, will have the greater ability to get that transaction into a block by simply not Sybilling it or Sybilling it less. If the Sybil and honest node truly are otherwise equal, the non-Sybil always gets the transaction into a block first.
Stepping back: you don't even need to trust initial hops based on their identity - they can offer proof of how many hops their routing chains accumulate by showing users those transactions, linked to historical blocks, which are expensive to fabricate.
You can use a succinct commitment scheme to prevent would-be Sybils from only sharing their 'well-routed' transactions: A node commits to a Merkle Tree header hash, and the user is allowed to randomly sample from branches in the tree.
A user expects to be provided with their random sample and see that:
1) The transactions are from a sufficiently 'worked' on chain which is prohibitively expensive to fabricate.
2) The transactions involve the router committing to the Merkle Tree.
3) The transactions involve less hops than other routers the user is sampling transactions from.
The Sybil you are describing now must divide the size of their Merkle Tree sampling for every new identity they wish to inhabit - and if they are in fact consistently Sybilling users, will be forced (statistically) to reveal their excess hops.
What you describe is still very inconvenient for users - to have to sort through all these nodes and compare their samplings, but it is at least a demonstration that this Sybilling behavior is not sustainable. I tried to assume the worst case scenario (related to your concern) when devising the above scheme.
The scheme above handles the case where nodes pose as many in order to extract more fees and reduce their competition, but now it seems like you are thinking about absolute censorship.
Otherwise, if there are no extra hops, then what is the attack? A single router (posing as many) gets transactions into blocks as fast as anyone else?
As soon as he starts Sybilling that data to earn more fees or censoring it, every recourse I mentioned (not just may last comment) makes it unsustainable and unprofitable comparatively - opening the door for others to take his spot.
If your point the whole time was a censorship operation through Sybilling, the user can identify that quickly AND honest nodes will seek out those users. I addressed it earlier - the more extreme the censorship, the greater the incentives for other nodes to remedy it themselves.
>The scheme above handles the case where nodes pose as many in order to extract more fees and reduce their competition, but now it seems like you are thinking about absolute censorship.
Yes, please scroll up. Two different attacks were explained along with saying this article only solves one of them.
> There are no excess hops in the attack I am describing.
As above, you're not describing a sybil attack. Adding a bunch of 1st hop nodes to a network doesn't mean that those nodes are conducting a sybil attack.
If you want to leverage them in an attack, you would have to have them send their TXS to a central block producer that gathers the TXS from all of these first-hop nodes and then tries to use all of their collected-work to orphan the blocks/work from honest nodes in the network. If you work through the paper, you'll see that this attack is provably-costly.
You could theoretically avoid the penalty if you gave all of your 1st hop nodes the same keypair, but in that case you don't have multiple identities on the network and you don't have a sybil attack...
The point of describing such a scheme is that it covers the hole you think you found. You complain "the article doesn't solve this problem," "your scheme doesn't this problem-" okay, well they each solve one of them. The fact that the scheme relies on the properties proven in the article is not incidental.
Do you have any specific critiques? I'm not going to guess your meaning if you aren't going to address my points directly.
The attack vector you are describing doesn't work. If an attacker owns 1010 nodes and collects inbound transactions on 1010 nodes, then they have to relay those transactions to a second-hop block producer, which halves the value of those transactions for creating blocks.
And even then they could not orphan the work produced by other nodes profitably, which would be possible in POW and POS. So at best you have an inefficient strategy for maximizing routing work, but no profitable attack based on it and a strong incentive to behave honestly even if you have a majority of work.
In the immediate term it would be the same as using a single mode except with higher proportional rewards. However depending on the architecture that is the only motivation needed and depriving others of rewards; in the long term this could result in centralization of routing nodes (by control) and finally censorship.
It also seems unclear how consistent routing work is determined; how does the entire network agree on the minimal routing when there are many routes with the same 'depth' ; it also seems to conflict with minimal amount of routing work is required by the difficulty.
The goal of Sybil mitigation is to prevent any actor from gaining any undue control and this doesn't sufficiently show that to me.
> However depending on the architecture that is the only motivation needed and depriving others of rewards; in the long term this could result in centralization of routing nodes (by control) and finally censorship.
Highly recommend reading the original paper (!!) as the "depriving others of reward" concern you have is exactly what is solved through sybil-proofing. So the solution addresses your concern directly -- nodes share because it is profitable for them to do so, and it is profitable for them to do so because others cannot deprive them of their due reward without losing money. If we are both nodes then I'll give you my TX flow because the only way it has value to you is if you figure out a way to get it confirmed faster than I can.
> how does the entire network agree on the minimal routing when there are many routes with the same 'depth'
A good technical analogy is to think about how POW works, but have users attach a difficulty-hash to their TXS instead of a fee. Have nodes "collect" those hashes to meet aggregate difficulty requirements. And now have consensus halve the "measured value" of the tx-embedded hash for each hop in its routing path. Early-hop nodes in this system will have a similar statistical advantage producing blocks.
The POW analogy suffers from attack vectors that are not possible in the sybil-proof mechanism, but it should give you a sense of what is happening. An attacker can create 1-hop routing work using their own money, but in that case they are making blocks with only their own wallets and pay the costs of hashing/burning to release payments entirely out of their own pockets.
In other words it Sybil attacks that create long chains of nodes owned by the some person, but it doesn't stop Sybil attacks that aim to get everyone else on the network to route through you instead of someone else.
Right - and this gets to perhaps the stickiest point on this: is a node a Sybil if they are the most efficient route into the network? If a single node can make all the blocks, they still only hurt themselves by adding hops (reducing block time, opening door for someone else to do it faster).
Many people argue that because nodes can still create an arbitrary number of identities, that they are in fact Sybilling. I believe that is incorrect, and [Wikipedia](https://en.wikipedia.org/wiki/Sybil_attack) seems to agree:
"[A Sybil Attack] is an attack wherein a reputation system is subverted by creating multiple identities"
If you take 'reputation system' generally to mean a system where nodes are gaining power from their identity, or in the case of Saito: their behavior, then you can easily say Saito is Sybil Proof even if it allows arbitrary identities because the 'reputation' you use to influence the network cannot be gamed by making additional identities - even though making them is free.
If all transactions flow through an attacker's nodes they can censor transactions they don't like.
The reputation in this system is properly routing transactions. If someone notices a node censoring transactions they could blacklist that node, but the attacker can instantly spin up another.
Yes, but take this to the extreme and you have nodes who do not wish to censor literally fighting to get to censored, paying users.
The more the censored transactions build up, the easier it is for any honest node to swoop in, outpace the attacker and earn the rewards. And then those users now have a node who is willing to include their data - the incentive structure leads to these connections.
The point is that nodes who censor are giving up money to anyone else willing to include the data.
Short answer is that as such activity continues the incentives to compete by behaving less duplicitously also increase - that may mean unorthodox means of finding those users in extreme attack scenarios like your example tends towards - but in basic cases there are proofs nodes can provide of previous performance which can't be Sybilled.
>incentives to compete by behaving less duplicitously also increase
There are no disincentives to do it and people may want to do it regardless of any incentives that are in place. There being transactions that are illegal to relay (money laundering), so legally nodes are unable to relay no matter the incentives.
>that may mean unorthodox means of finding those users
This has poor usability. Normal users don't want to deal with manually finding nodes themselves. It is hard to figure out the reputation of nodes when their is no hard proof of who the actual owner is.
Well I hoped you wouldn't continue in this thread because I laid out a secure interactive proof scheme that DOES offer statistical proof that a node behaves and performs well, and that it is not likely a Sybil.
If you are that concerned with reputation, you can ask for token lock-ups - further diminishing the ability of many identities appearing distinct.
But the greater point is that these are not Sybils, because they do not gain power over the system. If your counter-point to that is that users will waste money then clearly this attack is not sustainable - some node can take that revenue by saving users' money.
And if your concern is so extreme that a whole network around a user is locked down, then I can make a similarly unusual case that physical transmission of data is incentivized - because it is.
Of course recovering from extreme cases is not user-friendly - but the point is that you can recover and these states of total control are not sustainable; it would take a lot of work to even get into one of these states and it wouldn't even offer the attacker an ability to hold it.
So in practice it is unlikely to happen. The same way it's unlikely you will keep buying bread from the guy that charges twice the market rate.
I'm not sure why you are continuing because it's impossible to defend against all Sybil attacks in an open network.
>If your counter-point to that is that users will waste money then clearly this attack is not sustainable
One simple scenario where it is sustainable is when you are a part of a competitor's network where the existence of the other network results you in making less money. If the attacker wants to destroy the other network to gain market share they may be willing to have a budget they spend each month to attack it.
>And if your concern is so extreme that a whole network around a user is locked down
It's not extreme if there is to defense to it.
>it would take a lot of work to even get into one of these states
As I mentioned it is easy to run multiple instances of the software to become the majority of the network.
>The same way it's unlikely you will keep buying bread from the guy that charges twice the market rate.
If you check 100 stores in your area and they all charge that rate you may think that's the market rate.
You seem to be concerned about censorship attacks -- attacks that necessarily involve orphaning work in some capacity -- either orphaning blocks produced by honest nodes, or orphaning (refusing to include) tx-embedded routing work being sent from honest users.
The payout lottery does make censorship costly for all attackers who orphan work, but you'd need to specify the exact attack method if you want a discussion of specific work-orphaning attack vectors. Even nodes with a majority of "routing work" do not have the ability to costlessly orphan work produced by other nodes, so it isn't clear what exact attack you have in mind or why you think controlling a bunch of first-hop routing nodes under different identifies somehow makes these costs go away.
I'm not personally attacking you by stating my disappointment in you continuing the same argument in two different threads.
I will, again, reiterate that a Sybil attack is about power, not about convincing people you hold multiple identities - that is simply the means - it is not an effective attack if it doesn't get you that power over the network. The proof in the post clearly demonstrates how Sybilling reduces power in that scheme.
Your attack is not a Sybil attack - you've simply surrounded a user with extremely uncooperative nodes who manipulate or censor the user (the former of which isn't even economically feasible in the scheme of the OP, but that's tangential). If the uncooperative nodes surrounding the user all authoritatively proved they were unique identities, well, it obviously wouldn't be a Sybil attack then.
Yet these *unique* uncooperative nodes can perform the equivalent attack you keep bringing up. If you've read carefully at all, then you know I've just proven it can't be a Sybil attack - because *it has nothing to do with node identity and is not reliant on duplicating.*
Furthermore, this attack you describe, which is not strictly reliant on Sybilling, is on a user and not the network. I go as far to argue that even this individual user has recourse, which is beyond the primary claim - and as far as I'm concerned, true.
So addressing that - your argument is that nodes can afford to attack users because they can budget in the expense and surround users. But you can't carry this through - it always involves ripping users off and getting more money from them, and there are various ways for users to escape, including getting a new ISP.
In fact, even traditional monopolistic strategies don't even work to drown competition - because the network is open and it cannot be 51% attacked, so no majority can ever exclude competing nodes from publishing to the chain and earning rewards.
If a user has a constrained network which only routes to one provider - that isn't a Sybil attack, and it certainly isn't an attack on the network itself. I took the liberty to go above and beyond and argue that even these practices become unsustainable when you have a network with these qualities.
But I do not concede that just because one way you can perform this attack is by Sybilling that it is actually a Sybil attack - as I proved by showing you can perform it without duplicating oneself - hell you can do it with a single presented node to the user; what you are describing is hoarding network traffic.
Anyone can declare they have a sybil proof network if they have the power to declare everything that invalidates the proof as being non-sybil.
It might be a productive discussion if there could be an agreed upon definition of Sybil. The "proof" requires Sybils to inject an excess hop but no rationale as to why they would do so.
Saito is as vulnerable to Sybil attacks as Bitcoin is to miner concentration. In an open network cooperating nodes will always have an advantage over independent nodes. You cannot distinguish between the two in a permissionless network.
You're not describing a sybil attack. You're talking about censorship.
If you want to address that, your best strategy is to incentivize people to run access points that do not censor. This requires payouts to routing nodes in proportion to the value of the transactions they process, which requires the ability to make routing payouts, which requires a sybil-proof routing mechanism.
The short answer is that it keeps the system fully 'trust-free' (permisionless), and that it, in the same way Bitcoin incentivizes hashing random numbers, incentivizes routing nodes to form efficient networks (networks which race to get fee paying data into blocks while minimizing hops).
--
Routing nodes will lose to competitors if another routing path on the same fee is included in a block. They also diminish the 'work' in the transaction (which overcomes the threshold to make blocks) by adding hops - so it's only worth it to add hops in order to 'win the race.' All nodes in the path have an expected value on the fee, but the further into the chain of hops, the more that diminishes.
In a technical sense, it isn't necessary to then reward those routing nodes to keep the anti-Sybil property for the routing network itself, but it does give other nice properties related to trustlessness and network provision.
1. Data pays no fees, routers get no rewards
Assuming data is published to a shared medium which requires some threshold of "work" which stems from the data, then even just the act of including that data into your medium becomes more difficult the more hops it accumulates. You then of course rely on trust assumptions to fight spam.
2. Data pays fees, routers get no rewards
If you use some measure of cost to create data, you can handle spam, and that cost determines how much work the data carries with it and thus how likely it is to be included into the medium (trying to be very general here, but in the linked article that medium is a blockchain). The trust assumptions here rest with the routing nodes 'doing their duty.'
3. Data pays fees, routers get rewards
This is the model Saito has - it removes trust assumptions for users and routers as if one tries to 'scam' the other (either a Sybilling user creating fake data, or a Sybilling router creating fake hops), the native money can be leveraged to create recourse without an authoritative audit or punishment - purely economic.
Do you want your transaction fee to pay for mining, or do you want it to pay for the servers that run the network? If it pays for mining, who pays for the servers that run the network?
I hate to be that person, but as someones with Dissociative Identity Disorder I really wish we would stop using this term and go back to pseudospoofing. I cannot express just how much I HAAATE that the "solution" for a "Sybil" attack is Decentralized IDentification, or DIDs. It's a wholesale theft of the language that defines my existence and will lead many people to associate those with DID with the story of Sybil which woefully outdated and from a time when we knew far less about dissociaton than we do today.
This has led me to understand empathically why there were people suggesting we change bus terminology from master/slave to anything else.
This comment is very surprising to me. I don't think it's reasonable to expect any three-letter acronym will only mean one thing. For example my usual nickname has three letters, and has around 20 definitions on wikipedia, including sex-related, drug-related and politically charged meanings (I don't identify with).
In fact, DID already has a disambiguation page on Wikipedia: https://en.wikipedia.org/wiki/DID_(disambiguation). I don't think Dublin Institute of Design or Data Item Descriptions constitute "a wholesale theft of a language".
It's clearly an unfortunate clash of both DID and Sybil in two separate nomenclatures. Each of which, in its own domain, has different referents.
However, like many of the peer comments here I feel the overlap of these two domains is vanishingly small. Presumably only yourself and a handful of others would even be aware of the etymology.
As you feel so strongly, perhaps a well-written blog post would rank highly for anyone curious enough to disambiguate.
Solving Sybils for any blockchain is kinda something rational, ethical cryptographers wouldn't want to do... but I'm sure you can pay someone to claim they've solved it.
I'm kinda okay with blockchains always remaining vulnerable and becoming relics of the past. It's all a scam. Not patching it.
You mean because of the hype and scams associated with blockchain technology?
I would agree with the assessment, but avoiding it for research would be equally dumb. The tech itself has very interesting properties and potential applications outside of “finance”. It’s just a decentralized and slow global db with an (empirically battletested) consensus mechanism.
> with an (empirically battletested) consensus mechanism.
In fact there almost as many consensus mechanisms as there are blockchains. In the beginning it was PoW that defined what was a blockchain, but with its obsolescence in favor of Proof of stakes for many chains the situation got muddier. Facebook's Libra/Diem for instance was based on a strongly consistent algorithm (as opposed to the eventually consistent nature of PoS) that's not that different from PBFT and ByzPaxos.
I'd argue that most PoS networks are not fundamentally different from the consensus algorithms before Bitcoin - the difference is they include a token as an entry point into authority, and that getting caught attacking will demerit tokens from you.
But the attack vectors are the same, and now there is an incentive to pull off an attack since the system is representing money people are willing to trade for goods. I think PoS is dangerous for this reason - same vulnerabilities and defenses but with higher stakes on both sides.
Not defending PoW wholesale, but it is fundamentally different as a network defense tool - though, it too has a reward for attacking it, so long as you can get 51% together - or less with selfish mining (network latency attacks).
> , and that getting caught attacking will demerit tokens from you.
even that's only true if you define dememerit attack and caught in particular ways.
E.g. I have a lot of tokens then sell them. (or go around and buy up worthless no longer used keys from people who had a lot of tokens at some point).
Now I can bifuricate the history at that point, create all the alternative histories I can't and you can't take anything from me.
To protect against these alternative histories one needs to use a separate consensus mechanism. In many systems this has been essentially "some trusted third party signs the real stuff" -- often with some obfuscation in between. If you're okay with that security model, why not eliminate the intermediate step theater and just use the ultimate centralized consensus?
I ultimately agree - I'll play Devil's advocate a bit:
Such an attack is referred to as a "long range attack" and is 'solved' by 'finality' in Ethereum, the largest running PoS network. Finality basically means a hard checkpoint. I won't make you say it: finality can of course be changed on different forks, and that's the core issue in PoS.
There is probably some utility in adding friction to such corruption, but that the mechanism doesn't ultimately prevent it and really just adds incentives to controlling it.
Attacks on PoS are more convoluted, but there are more of them and more ways to approach them. I fully agree this fact is lost in obfuscation and jargon.
One risk in creating cryptosystems is that I think applies very much to these POS systems is that you create something, it gets broken, you revise it, broke, revise it broken, revise it broken, revise it each time adding more complexity... okay no breaks found. Is it now a cryptographically secure system or was it just revised until it was cryptographically secure against review?
That's very much the history of POS systems but it's even worse than that, because as the revisions went they added new conditions to the assumed security model so at the end of the day the security assumptions are very different from where they started. They might be secure but for example a function whose security definition is that whatever the function does it correct is always "secure". :P
There is one prominent POS cryptocurrency (I'll not name it because it's not relevant and naming it will just invoke vicious shills) which has a formal security proof that starts with the assumption that all participants have a network that faithfully delivers all messages without loss and in the same order. It's trivial to have a consensus system that is secure in that model because you don't even need a consensus system in that model: "first transaction out of any competing set wins" is an adequate policy, the network in that case is equivalent to a consensus system. (Maybe the system provides some useful security properties, but its security proof won't tell you anything about them)
In any case we're largely in violent agreement. I think.
While I can agree with your argument that some of the friction in these systems may have practical utility even if it doesn't meet a strong security criteria, the danger that worries me is that people don't actually have a clear mental model for what they do provide or what risks they have. This may lead them to expose themselves in ways that they wouldn't if the properties were better known, and ultimately result in losses greater than the benefits.
Or maybe not: lots of things work fine on fully centralized systems, or works fine even when their security rests on no one bothering to attack. But there is a little pedantic voice inside me that weeps at the obfuscation and misrepresentation.
I asked GPT-4 if they could "summarize for idiots". I do not have enough knowledge to say if they summarized it accurately, but for anyone like me, who felt like a very big dummy while reading this, here's the summary:
The essay discusses a method to prevent Sybil attacks, where a single adversary controls multiple nodes on a network to subvert the network's functionality, in blockchain networks by making it unprofitable for malicious nodes to add unnecessary 'hops' in transaction paths. Saito's mechanism rewards nodes for efficiently routing transactions to block producers, thus making Sybil attacks less lucrative. This is further illustrated with mathematical proof and examples comparing honest and Sybil behaviors, highlighting how the expected rewards change in both scenarios .
