Quote from: JoelKatz on May 12, 2013, 11:50:36 PM

We have tried to come up with a way to do this and failed. If anyone has any suggestions for a way to do this, I'd love to hear it. The basic problem is that there's no good way to figure out who is "really" a validator in a way that everyone can agree on.

Sometimes I think you are taunting me...
I actually came up with an algorithm for this when discussing [SteadyCoin] consensus building. It's somewhere back in my post history. Ripple's consensus building is slightly different but I can summarize my original logic. Maybe it can be modified for ripple.

The validation/consensus logic was a variant of BitCoin's block consensus absent the PoW calculation. Each node executes a sequence of deterministic steps:
1) Generate a "candidate set" of validators.
2) Choose a primary validator from the set using a distributed random number generator.
3) Broadcast the primary validator's block to the other validators for confirmation.
4) Each confirming validator broadcasts an "Announce" transaction signaling they are now building upon this new block.
5) Each validator listens for Announce transactions from others on its personal known-nodes-list (Ripple's UNL) to confirm consensus has been reached.

---
1) A validator is in the candidate set if its "Announce" transaction is present in the current building block and in each of the preceding (N) blocks. [Good validators are consistent]

2) At each block interval (X seconds), each node chooses its primary validator by:
  a) Ordering and hashing all received transactions since the previous block.
  b) Comparing that hash to candidate set nodes using a distance function.
  c) The closest node becomes the primary validator.

3) If a node calculates itself to be the primary validator, it completes its block by generating any coinbase transactions and broadcasts its signed block hash.

(Theoretically, if every node was well connected and persistent they would all receive the same transactions, calculate the same primary validator, and be able to complete the final block according to pre-specified coinbase rules.)

4a) If the proper hash arrives from your expected primary validator, then "Announce" your confirmation by issuing a signed transaction that builds upon that block.
4b) If the proper hash doesn't arrive (or is invalid) presume the primary validator to have FAILED in its duties. Remove its "announce" transaction from your current building block set [(N) block candidate-validator penalty] and repeat 1-4.

5a) If a majority of the nodes on your personal known-nodes-list "announce" on the same block as you, all is well.
5b) If a majority of announcements aren't receive, then you are partitioned from the main network. STOP external trading.
5c) If, however, a majority "announce" on a block you are not expecting, then you must presume either you have FAILED (missed some transactions) or something malicious is happening.
  c1) Request the majority block and validate it.
  c2) Identify transaction differences between yours and the majority block.
  c3) If you missed transactions, announce on the majority block and continue.
  c4) If the majority block is missing transactions, announce on the majority block, re-broadcast the excluded transactions, and continue.
  c5) If there a double spends or conflicting transactions, Broadcast malicious user WARNING and halt any related external transactions.
  c6) If re-broadcasted transactions (c4) fail to confirm in the next block, Broadcast validator DoS WARNING.

Because of its (UNL) equivalent the system converges similarly to Ripple.
---
CoinBase reward/mining transactions can be assigned to validators using any pre-agreed upon rule set.

[StableCoin] dynamically adjusts the generation amount and distributes new coins to combat price instability. It doesn't have a default reward for validators.

BitCoin could use its "winner take all" rule to award all 25 BTC to the primary validator. The randomness of (2) above would spread the coins around over time.

Alternately, each new block reward could be spread among all the candidate validator nodes mining pool style.

Sybil validator attacks could be mitigated by either 1) requiring candidate validators to be non-anonymous (i.e. Ripple's UNL), or by 2) requiring candidate validators to put up a forfeitable (4b) fidelity bond.