4 ms·

The obvious question for anything that claims to solve Byzantine consensus is: what about Sybil attacks? If you rely on 2/3 of all nodes to be honest, but you o

The obvious question for anything that claims to solve Byzantine consensus is: what about Sybil attacks? If you rely on 2/3 of all nodes to be honest, but you open up the network for anyone to join, what stops me from creating a million fake "nodes" and outvoting everyone else? So far I've only skimmed the white paper, but I didn't see any response to this problem. (If the answer is "good guys can make lots of fake nodes too" then you're creating a computational arms race that will inevitably lead to just as much wasted effort as proof-of-work.) There's also the minor practical issue that every node has to do an amount of computation and network traffic that's linear in the total number of other nodes, meaning the total workload grows quadratically with the size of the network.

zmanian 12y ago
Sybil resistance in two forms in Tendermint. 1. You assume the initial distribution of tokens is trusted. If someone presents you a consensus without a history to make you believe that initial distribution isn't full of sybils, distrust. 2. Assuming a large trusted initial distribution, operationally you have to believe that 1/3rd of the validator nodes don't want to double spend/ present an alternate reality to you.
- teraflop 12y ago
  For point 1, sure: Bitcoin does the same thing, and "blesses" a particular initial block as the starting point of the chain by hard-coding it into the client. No reason Tendermint wouldn't do the same thing. I don't see how your point 2 solves anything, though; it's just failing to acknowledge the problem. Why is it reasonable for me to think that a supermajority of the nodes are honest? If validators are supposed to be computationally cheap to run, compared to bitcoin miners, then what stops an attacker from running lots of them to get a larger voting share?
  - Kalium 12y ago
    In the Bitcoin/cryptocurrency world, there's a rarely-voiced but firmly believed assumption that being annoying and expensive to attack makes you secure. So the response that you are saying doesn't solve anything is what is believed to be the solution. Personally, I agree with you.
  - vbuterin 12y ago
    Validators are expensive to run. You need to put down a large security deposit in order to be a validator, and being a cheating validator will cost you the entire deposit.
wmf 12y ago
It's a proof of stake system, so "a validator has voting power equal to the amount of the bonded coins."
- teraflop 12y ago
  I see. I'm still skeptical about how robustly that will turn out to work in practice. Unless the majority of coins are locked up by validators, it seems like there's a constant risk of an attacker amassing a large number of coins and suddenly turning them into voting power with no warning. Upon re-reading the paper, I also noticed that it says "In the beginning of the Propose step the [deterministically chosen] designated proposer for that round broadcasts a proposal to its peers via gossip" but it's not obvious to me what happens if that proposer fails to participate. Is the algorithm allowed to skip to the next round? If so, is there some guarantee that the gaps can't later be filled in, and the history retroactively modified? (The DLS algorithm solves this problem by requiring all nodes to propose a value.)
  - jaekwon 12y ago
    Yes, the algorithm allows for skipping absent or Byzantine validators. It doesn't skip the height, it just progresses to the next round. In the end it's about getting more than 2/3 of commit votes. You can prevote or precommit more than once per height (on different rounds), but a commit for a height must be the last signature for that height. The sudden mass bonding is a problem for light clients doing a certain type of desirable SPV. We're considering options to mitigate this issue. One such option is to throttle the bonding and unbonding at the protocol level, or to introduce a second class of coin for validating and controlling issuance of it.
  - aqme28 12y ago
    It's the same idea as peercoin and others. Once you have amassed enough coins to control the vote, you're now financially dis-incentivized from voting in such a way as to undermine trust in the blockchain.
mjb 12y ago
> The obvious question for anything that claims to solve Byzantine consensus is: what about Sybil attacks? Not really answering your question (which is answered elsewhere in the thread), but these things are independent in an interesting way. Sybil attacks, in the simplest sense, depend on running consensus across a group where you don't have trustworthy membership information. If you do, then it turns into an authentication problem, which is different. Sybil attacks are an attack on the protocol that controls jury membership (or authenticates jury members), rather than the consensus protocol itself.
teraflop 12y ago
One more question/critique: Section 6.5 purports to give a game-theoretic justification for why a node should include as many valid signatures from its peers when proposing a block, for fear of retaliation. But nothing stops me from dividing my voting share among, say, a thousand nodes which appear to be unrelated. If one of those nodes decides to "defect" (steal a larger-than-intended share of fees by excluding some signatures) then the expected time before it is selected again can be made arbitrarily large, by making the node's voting share arbitrarily small. If that expected time is significantly larger than the unbonding period, then there's no way to retaliate, is there? It can just unbond and then transfer its coins to a "new" node. EDIT: I originally typo'd "arbitrarily large" instead of "arbitrarily small" above, but hopefully the meaning was clear.
- zack-bitcoin 12y ago
  If the blockmaker excludes signatures, then a larger portion of the fees get burned, and the blockmaker gets a smaller reward.
- jaekwon 12y ago
  +1 Yes, you raise a valid point. It's a weakness that must be addressed. There needs to be additional assumptions in the model, e.g. the respective voting powers should be on the same order of magnitude, and the number of validators should only be as large as the throughput (in blocks/s). More bandwidth && less latency && more CPU helps.
zack-bitcoin 12y ago
The list of nodes will be hard-coded at the genesis with known meatspace identities. It can only be updated by a transaction signed by >2/3 of the existing nodes. I am writing the "validators contract" for tendermint right now. It will have this functionality.
- Mtinie 12y ago
  In this initial allocation of nodes, will one node equal one individual (with a verifiable identity)? If it does, I expect that it would reduce the likelihood of a Sybil-styled attack during the early days of the network -- with the risk of introducing a different vector, direct coercion of the node owners. Is the plan to make the hard-coded genesis nodes as geographically diverse as possible?
  - jaekwon 12y ago
    ;) Where are you at? We're in the Bay Area.
    - influx 12y ago
      If you need someone in Seattle, hit me up.
justicezyx 12y ago
sybil attack has nothing to do with byzantine consensus. If you cannot trust majority of the nodes, it has no sense to reach any consensus. an analogy is, making money and can money make you happy, 2 issues, completely independent.

zmanian 12y ago

Sybil resistance in two forms in Tendermint. 1. You assume the initial distribution of tokens is trusted. If someone presents you a consensus without a history to make you believe that initial distribution isn't full of sybils, distrust. 2. Assuming a large trusted initial distribution, operationally you have to believe that 1/3rd of the validator nodes don't want to double spend/ present an alternate reality to you.

teraflop 12y ago
For point 1, sure: Bitcoin does the same thing, and "blesses" a particular initial block as the starting point of the chain by hard-coding it into the client. No reason Tendermint wouldn't do the same thing. I don't see how your point 2 solves anything, though; it's just failing to acknowledge the problem. Why is it reasonable for me to think that a supermajority of the nodes are honest? If validators are supposed to be computationally cheap to run, compared to bitcoin miners, then what stops an attacker from running lots of them to get a larger voting share?
- Kalium 12y ago
  In the Bitcoin/cryptocurrency world, there's a rarely-voiced but firmly believed assumption that being annoying and expensive to attack makes you secure. So the response that you are saying doesn't solve anything is what is believed to be the solution. Personally, I agree with you.
- vbuterin 12y ago
  Validators are expensive to run. You need to put down a large security deposit in order to be a validator, and being a cheating validator will cost you the entire deposit.

wmf 12y ago

It's a proof of stake system, so "a validator has voting power equal to the amount of the bonded coins."

teraflop 12y ago
I see. I'm still skeptical about how robustly that will turn out to work in practice. Unless the majority of coins are locked up by validators, it seems like there's a constant risk of an attacker amassing a large number of coins and suddenly turning them into voting power with no warning. Upon re-reading the paper, I also noticed that it says "In the beginning of the Propose step the [deterministically chosen] designated proposer for that round broadcasts a proposal to its peers via gossip" but it's not obvious to me what happens if that proposer fails to participate. Is the algorithm allowed to skip to the next round? If so, is there some guarantee that the gaps can't later be filled in, and the history retroactively modified? (The DLS algorithm solves this problem by requiring all nodes to propose a value.)
- jaekwon 12y ago
  Yes, the algorithm allows for skipping absent or Byzantine validators. It doesn't skip the height, it just progresses to the next round. In the end it's about getting more than 2/3 of commit votes. You can prevote or precommit more than once per height (on different rounds), but a commit for a height must be the last signature for that height. The sudden mass bonding is a problem for light clients doing a certain type of desirable SPV. We're considering options to mitigate this issue. One such option is to throttle the bonding and unbonding at the protocol level, or to introduce a second class of coin for validating and controlling issuance of it.
- aqme28 12y ago
  It's the same idea as peercoin and others. Once you have amassed enough coins to control the vote, you're now financially dis-incentivized from voting in such a way as to undermine trust in the blockchain.

mjb 12y ago

> The obvious question for anything that claims to solve Byzantine consensus is: what about Sybil attacks? Not really answering your question (which is answered elsewhere in the thread), but these things are independent in an interesting way. Sybil attacks, in the simplest sense, depend on running consensus across a group where you don't have trustworthy membership information. If you do, then it turns into an authentication problem, which is different. Sybil attacks are an attack on the protocol that controls jury membership (or authenticates jury members), rather than the consensus protocol itself.

teraflop 12y ago

One more question/critique: Section 6.5 purports to give a game-theoretic justification for why a node should include as many valid signatures from its peers when proposing a block, for fear of retaliation. But nothing stops me from dividing my voting share among, say, a thousand nodes which appear to be unrelated. If one of those nodes decides to "defect" (steal a larger-than-intended share of fees by excluding some signatures) then the expected time before it is selected again can be made arbitrarily large, by making the node's voting share arbitrarily small. If that expected time is significantly larger than the unbonding period, then there's no way to retaliate, is there? It can just unbond and then transfer its coins to a "new" node. EDIT: I originally typo'd "arbitrarily large" instead of "arbitrarily small" above, but hopefully the meaning was clear.

zack-bitcoin 12y ago
If the blockmaker excludes signatures, then a larger portion of the fees get burned, and the blockmaker gets a smaller reward.
jaekwon 12y ago
+1 Yes, you raise a valid point. It's a weakness that must be addressed. There needs to be additional assumptions in the model, e.g. the respective voting powers should be on the same order of magnitude, and the number of validators should only be as large as the throughput (in blocks/s). More bandwidth && less latency && more CPU helps.

zack-bitcoin 12y ago

The list of nodes will be hard-coded at the genesis with known meatspace identities. It can only be updated by a transaction signed by >2/3 of the existing nodes. I am writing the "validators contract" for tendermint right now. It will have this functionality.

Mtinie 12y ago
In this initial allocation of nodes, will one node equal one individual (with a verifiable identity)? If it does, I expect that it would reduce the likelihood of a Sybil-styled attack during the early days of the network -- with the risk of introducing a different vector, direct coercion of the node owners. Is the plan to make the hard-coded genesis nodes as geographically diverse as possible?
- jaekwon 12y ago
  ;) Where are you at? We're in the Bay Area.
  - influx 12y ago
    If you need someone in Seattle, hit me up.

justicezyx 12y ago

sybil attack has nothing to do with byzantine consensus. If you cannot trust majority of the nodes, it has no sense to reach any consensus. an analogy is, making money and can money make you happy, 2 issues, completely independent.