Jon Michael Galindo

~ writing, programming, art ~

<< Previous next >>
9 October 2017

Distributed Consensus

The blockchain technology underlying Bitcoin and Ethereum consists partially in cryptography, but more importantly in the value of anonymous consensus. Because I will spend this post praising the virtues of anonymous consensus, I feel I should first offer a caveat.

Anonymous consensus nearly worthless in factual, non-computable scenarios. For example, just because ten anonymous people agree that a particular report is true, does not guarantee that the report is true: only convincing. If these ten people agree that a particular politician is the best candidate for office, it speaks only to the effectiveness of that candidate's campaigning and image.

It is, however, supremely useful in two scenarios: nonfactual and perfectly computable. The former would involve all ten people agreeing that an artwork was family-friendly: It is reasonable to treat the art as family-friendly. The latter would involve accepting a computed solution. If most clients agree on its computation, then they must have also agreed to use the same, demonstrably correct, algorithms: Ergo, anonymous, decentralized, trustworthy computation. (Any attacker capable of controlling more than half the clients effectively owns the system.)

I would like to add my two cents on another application that comes to mind with distributed computing.

If I wished to offload computation to anonymous machines, I would need some means of verifying their computations. For example, if I were to pay a machine 5 cents to process a block of data, it would be in its interest to simply return a random, less-resource-intensive result and collect the 5 cents.

The obvious solution is distributed consensus. I will instead ask 2 random machines to compute the same block. If their results agree, they must be running the same software.

If they disagree, I have two choices: I can compute the result myself and oust the offender, or I can distribute to a third random machine to see if it reaches consensus with either of the first two. By combining these two strategies, I can even eliminate the half-client attack.

Unfortunately, one problem remains inherent to distributed consensus computing: double-computation. All processes must be computed at least twice, effectively halving the computational efficiency of any such system.

However, what if, instead of comparing all computations, only half of any machine's computations were compared against another machine's computations? If reward transfer happened only post-confirmation of a random block, offenders would go unrewarded. In other words, transfer 2 blocks of data to a machine, and receive its 2 responses. Randomly select 1 of those to be verified by another machine or by myself. If the 1 selected passes, the machine obtains the reward for both. If it fails, the machine is ousted from the network and its 2 solutions discarded.

In this case, why stop at 2? Pass 10 blocks and randomly test 1, or pass 100. In these cases, reward monitoring is more contingent. The probability of an offender obtaining reward must be managed against the number of clients in a network. In other words, a running probability is kept for a machine that is repeatedly passing the verification test, and only once that probability exceeds the inverse of the number of nodes in the system (scaled by the number of blocks in a cycle) by some margin will the machine's rewards be dispensed and its solutions accepted as canon.

It is just a thought. Effective implementation would require significant development, and its applications differ from a full-consensus distributed blockchain. I can imagine it proving particularly useful in a game server setting. Elements of the game world could be computed on players' machines without fear of client-side code modification. It could also be used to create a distributed leasable computation farm with acceptable overhead and acceptable (though imperfect) trust levels. I suppose it could also be used to verify software integrity of clients accessing a network, for example to ban gamers using mods, although I prefer not to dwell on big-brother scenarios and I would definitely condemn this in particular. All told, I certainly see applications ripe for experimentation in personal projects.

© Jon Michael Galindo 2015-2018