[kannanvijayan]

There's a slight variation on this that I had pondered for designing a distributed election algorithm. I'm sure the idea is not novel, but it would be nice to know what work has been done on it.

The goal is to fairly select some candidate from a set of candidates. Each candidate `Ci` generates a UUID `Ui`. The hash of their UUID `hash(Ui)` is published by each candidate. Once all hashes have been collected, each candidate reveals the verifiable original UUID to all the others.

Each candidate then concatenates these UUIDs together (after normalizing the sequence in some way - e.g. sorting), and produce a selector code: `H = hash(U1 ++ U2 ++ ... ++ Uk)`. Finally, the selected candidate is simply the one whose UUID is the closest to `H` under some distance metric.

I tinkered a bit with adapting it for situations where the candidate set could shrink during the selection process (i.e. a candidate drops out), but didn't really pursue it much.

[jmeyer2k]

This is generally referred to as a RANDAO in cryptoeconomics. The problem is that a candidate can decide not to reveal their preimage `Ui` and affect the outcome of the RANDAO in that way.

https://github.com/randao/randao

[kannanvijayan]

Interesting! Thanks for the reference. I'm not sure how not revealing the pre-image would allow them to affect the result with any degree of predictability - it is equivalent to them selecting a different uuid, is it not?

I'll try to read up and see if I can answer that question.

[AgentME]

Say that all the other participants have revealed their pre-images, and you're the last one left you reveal your pre-image. Before you reveal it, you realize you alone have all the pre-images and can calculate the result. You calculate it, and realize you don't like the result. You could then decide to throw away your pre-image to force a new roll. If necessary, claim your computer crashed, your connection dropped, etc.

[AgentME]

I misworded the first sentence confusingly. Here's what I meant:

>Say that all the other participants have revealed their pre-images, and you're the last one left to your reveal your pre-image.

[mojomark]

Couldn't this be solved (or the risk of manipulation largely mitigated) using a trusted third party to witness, and perhaps hold, each candidates pre-image generation?

[AgentME]

If you have the trusted party reveal all of the pre-images, then you're just passing off the ability to decide not to reveal the pre-images to them. You could layer on the ability for all of the parties to reveal their pre-images if the third party fails to reveal them, though now you have the complication that the parties could reveal different pre-images than they gave to the third party. (Maybe one of the parties could realize the third party would defect because of a certain result that party doesn't want either, so that party could change their pre-image to avoid that result.)

The third party isn't any different than the main parties in the mix. If everyone can decide who the most trustworthy party in the mix is, you can have them reveal last.

[kannanvijayan]

Thanks for the succinct explanation - that makes sense.

[betterunix2]

FYI, cryptographic voting protocols have a long history of research:

https://crypto.stanford.edu/pbc/notes/crypto/voting.html

[bluesign]

It is very hard to handle candidate drop on this scenario.

[kannanvijayan]

Yeah that was why I sort of let go of that bit. The best solution I could come up with was to keep the population sizes small and re-run the vote if a drop occurred.

This doesn't work for large populations because the probability of a drop occurring during the selection procedure approaches 1. There, I was considering a tournament style selection - partition the population into small groups, select one from each, and treat the winners as a new candidate population.