3 ms·

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 nod

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
    Your idea doesn't help. Historical proof of routing transactions doesn't mean you will route all transactions. >Sybilling users, will be forced (statistically) to reveal their excess hops. There are no excess hops in the attack I am describing.
    - mattwilsonn888 3y ago
      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.
      - charcircuit 3y ago
        >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.
        mattwilsonn888 3y ago
        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.
- trevelyan 3y ago
  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.
f_devd 3y ago
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.
- trevelyan 3y ago
  > 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.

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
  Your idea doesn't help. Historical proof of routing transactions doesn't mean you will route all transactions. >Sybilling users, will be forced (statistically) to reveal their excess hops. There are no excess hops in the attack I am describing.
  - mattwilsonn888 3y ago
    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.
    - charcircuit 3y ago
      >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.
      - mattwilsonn888 3y ago
        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.
trevelyan 3y ago
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.

f_devd 3y ago

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.

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