6 ms·

The core of their argument is: > as any routing node which self-clones to gain a larger share of routing-work for a given transaction also reduces by half the

by f_devd 3y ago

The core of their argument is: > 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.

SkepticalSense 3y ago
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.
- trevelyan 3y ago
  You missed the last paragraph. The dominant strategy for users is indeed to broadcast two nodes.
mattwilsonn888 3y ago
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.'
- charcircuit 3y ago
  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.
  - mattwilsonn888 3y ago
    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.
    - charcircuit 3y ago
charcircuit 3y ago
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.
- mattwilsonn888 3y ago
  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 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.
  - charcircuit 3y ago
    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.
    - mattwilsonn888 3y ago
      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.
deleted 3y ago
[deleted]
trevelyan 3y ago
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.
- somezero 3y ago
  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-sybil-attack/ https://www.microsoft.com/en-us/research/publication/the-syb... [2] https://arxiv.org/pdf/1111.2626.pdf https://arxiv.org/pdf/1111.2626.pdf [3] https://en.wikipedia.org/wiki/DARPA_Network_Challenge?wprov=sfti1 https://en.wikipedia.org/wiki/DARPA_Network_Challenge?wprov=... [4] https://link.springer.com/chapter/10.1007/978-3-540-85230-8_1 https://link.springer.com/chapter/10.1007/978-3-540-85230-8_...
  - trevelyan 3y ago
    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.

by f_devd 3y ago

SkepticalSense 3y ago

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.

trevelyan 3y ago
You missed the last paragraph. The dominant strategy for users is indeed to broadcast two nodes.

mattwilsonn888 3y ago

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

charcircuit 3y ago
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.
- mattwilsonn888 3y ago
  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.
  - charcircuit 3y ago

charcircuit 3y ago

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.

mattwilsonn888 3y ago
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 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.
- charcircuit 3y ago
  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.
  - mattwilsonn888 3y ago
    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.

deleted 3y ago

[deleted]

trevelyan 3y ago

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.

somezero 3y ago
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-sybil-attack/ https://www.microsoft.com/en-us/research/publication/the-syb... [2] https://arxiv.org/pdf/1111.2626.pdf https://arxiv.org/pdf/1111.2626.pdf [3] https://en.wikipedia.org/wiki/DARPA_Network_Challenge?wprov=sfti1 https://en.wikipedia.org/wiki/DARPA_Network_Challenge?wprov=... [4] https://link.springer.com/chapter/10.1007/978-3-540-85230-8_1 https://link.springer.com/chapter/10.1007/978-3-540-85230-8_...
- trevelyan 3y ago
  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.