Quote from: JoelKatz on February 21, 2013, 08:09:46 AM

Quote from: myuser on February 21, 2013, 07:54:28 AM

Oddly enough, it seems that there isn't yet a consensus on how consensus works. But from what I understand, consensus is trusted validators looking at the ledger, and certifying it. The only way this would be vulnerable is if a validator orchestrated a 51% attack.

I think descriptions of the "interesting" case (how Ripple uses consensus to solve the double spend problem) are getting confused with how the uninteresting cases are solved. There are really three cases:

1) As a non-validating client or server operates: Here, you just collect validations, which are signed statements of the hash of the last closed ledger. The validations are timestamped and sequenced. This allows a client to determine the current ledger which includes things like balances. You can then follow hash chains to get the results of transactions, view order books, and so on without any trust needed.

2) When a new validator comes online: A new validator can determine the current ledger using the same mechanism a client does. The new validator will then synchronize to the current ledger. The validator can also walk the hash chains to ensure that there is a valid path from the last ledger it accepted to the current ledger.

3) The interesting case -- as a validator operates, solving the double spend problem: The validator must already agree on the last closed ledger as described above. Validators exchange proposals that state which transactions the validator believes should be candidate to be applied to the ledger. Once a consensus is reached, the candidate transactions are applied deterministically so that all validators produce the same new last closed ledger. They then sign validations of this ledger (for use by clients and new validators as in 1 and 2 above). The servers then start the next consensus cycle and also collect validations from the ledger they just closed to ensure that nothing went wrong in the consensus process and to provide to clients.

Using my (overly simplified) agreement room analogy, it works like this:

1) There's a room where everyone agrees on the last closed ledger.

2) If you want to disagree, you can, but you must leave the room to do so.

3) If you want to know what the current ledger is, you walk in and ask everyone in the room.

4) If you want to perform a transaction, you read it out loud. Everyone honest agrees that it's valid.

5) If there are any transactions that someone in the room believes is valid and is not in the current ledger, they attempt to obtain a consensus on that transaction.

6) When a consensus is reach, the consensus transactions are applied to the last closed ledger forming a new last closed ledger.

7) Everyone agrees on the new last closed ledger.

8 ) We go back to step 5. Any transactions believed still valid but that didn't get into the consensus transaction set for some reason should now be voted in by every honest person.

9) If people appear to be acting in ways that don't make sense, such as voting no on transactions that have no reason not to be included or failing to validate the correct ledger, you ignore them.

10) Your top priority is to enforce the rules of the room. Your second priority is to achieve consensus.

Wow, thank you for the amazingly detailed response. That actually really makes sense for me.