Tiebreaking standard using the blockchain?

[Meni Rosenfeld]

The following issue is very general, but to spare you the abstractions I will describe it by way of presenting the situation I have at hand.

We at the Israeli Bitcoin Association will soon have our first elections to our board of directors. Many details are TBD but basically, members get to vote and the directors who received the most votes are chosen.

A problem exists if there are ties. Let's say there are 7 members, and the vote counts from high to low are 66, 55, 45, 36, 28, 15, 15, 15, 10, ... . Then places 6-8 are shared by people who got 15 votes, and the method doesn't determine which 2 of them to admit.

Some voting systems resolve this with an additional tiebreaking voting round, but this creates a lot of overhead and is not mathematically elegant. Game-theoretically, a better way is to randomly choose the winners; but then we have a problem of ensuring the random choice was done fairly.

A natural way to resolve this would be to use the blockchain. Hashes of future blocks are more or less random and not easy to manipulate. So we can announce in advance that ties will be broken based on the hash of the first block with a timestamp of at least Nov 30 2014 00:00:00. However, I don't want to reinvent the specific way to use the hash to make the selection.

So my question is - is there some standard, deterministic way to use the blockchain to resolve ties? Is there some website which gives results based on this standard? If not, how do we go about creating such a standard?

Note that to address the general problem, the method needs to return a permutation - since we have a number of results which a priori are all equivalent, and we would like to order them somehow. So basically, the method will accept a date (or block height) designation, and a list of text items, and return a randomly permuted list of the items. Some ideas I had is to take the block hash modulo n! and choose a result from the n! permutations, ordered lexicographically, based on the result. Or to use the hash as a random seed which is input to a simple permutation-finding program.

Optionally, the standard would allow using the hashes of multiple blocks, to make it harder to mine blocks specifically to manipulate the system.

[Elwar]

Maybe just take the next block ID and use the last number, if higher or lower than X the tie goes to one or the other. Same can be done for 3 and 4 way ties breaking up the numbers to 3 and 4 divisions.

[Meni Rosenfeld]

Maybe just take the next block ID and use the last number, if higher or lower than X the tie goes to one or the other. Same can be done for 3 and 4 way ties breaking up the numbers to 3 and 4 divisions.

That's similar to the mod suggestion. As you described it only works when on item needs to be chosen (A method that generates a permutation could be used for, say, choosing 2 items out of a tie of 4). Anyway, my main point is that I don't want to describe in our bylaws "We will take the block hash and do modular division and X Y Z...", I want to be able to write "We will use the standard blockchain tiebreaking protocol".

[Elwar]

Maybe just take the next block ID and use the last number, if higher or lower than X the tie goes to one or the other. Same can be done for 3 and 4 way ties breaking up the numbers to 3 and 4 divisions.

That's similar to the mod suggestion. As you described it only works when on item needs to be chosen (A method that generates a permutation could be used for, say, choosing 2 items out of a tie of 4). Anyway, my main point is that I don't want to describe in our bylaws "We will take the block hash and do modular division and X Y Z...", I want to be able to write "We will use the standard blockchain tiebreaking protocol".

Ahh, this is the first I have read of someone wanting to use the blockchain for tie breaking. A few methods for voting but not tie breaking.

Perhaps you could come up with the standard

[Meni Rosenfeld]

Maybe just take the next block ID and use the last number, if higher or lower than X the tie goes to one or the other. Same can be done for 3 and 4 way ties breaking up the numbers to 3 and 4 divisions.

That's similar to the mod suggestion. As you described it only works when on item needs to be chosen (A method that generates a permutation could be used for, say, choosing 2 items out of a tie of 4). Anyway, my main point is that I don't want to describe in our bylaws "We will take the block hash and do modular division and X Y Z...", I want to be able to write "We will use the standard blockchain tiebreaking protocol".

Ahh, this is the first I have read of someone wanting to use the blockchain for tie breaking. A few methods for voting but not tie breaking.

Perhaps you could come up with the standard

Interesting, seems to me a general problem, and a useful solution for it, so I'd be surprised if no one else considered it.

[iddo]

This new "Bitcoin Beacon" paper has some answers to the OP:
http://arxiv.org/abs/1605.04559

Maybe in your context people already trust the organizers, so you don't need public verifiability of tiebreaking, and then commit/decommit (with or without penalties) among the organizers is already ok, but the beacon will only help of course (described in section5 of PDF in the arxiv link).

[DannyHamilton]

I want to be able to write "We will use the standard blockchain tiebreaking protocol".

I'm not aware of any such standard, but I suppose one may exist without my knowledge.

If I were going to create a standard, I think I would do it as follows...

• Each contestant chooses (or is assigned) some unique piece of data
• A designated future tie-breaking block height is chosen
• If there are any ties, then the unique data of each tied contestant is separately combined with the hash of the designated block using some predetermined method
• The resulting combined data for each contestant is hashed
• The resulting hashes are sorted using a predetermined sort ordering and the "winners" are chosen in the sorted order of their respective hashes

As an example the following could be chosen before the election as the tie breaking mechanism:

• Block height 412150, where the genesis block is block 0, is chosen as the tie breaking block height, but only after 6 additional blocks have been added to the blockchain (to avoid using an orphaned block).
• Each contestant is assigned a number in the order that they registered (or were nominated?) for the election.
• HMAC_SHA256 is chosen as the hashing method, with the contestant unique data represented as a string for the key and the block hash in hex represented as a string for the message
• Hash results will be sorted numerically in increasing order
• The "winners" will be chosen in numeric order of the resulting hashes as sorted from lowest to highest

After the election it is found the contestants that were assigned 3, 7, and 9 are tied for the final 2 positions.

Calculate the following:

• HMAC_SHA256("3", "00000000000000000159ed8373074591e4088c3735d4e85238b65c0a11bad6c9") = e69350a027d8b375da6b9c08556cc8a952b712174d87fe8f96be18c2eedd5abe
• HMAC_SHA256("7", "00000000000000000159ed8373074591e4088c3735d4e85238b65c0a11bad6c9") = dd9de1981a23af9af43110fb0e056b0ba06560b4dc8de7a37a133a3e9a9ea163
• HMAC_SHA256("9", "00000000000000000159ed8373074591e4088c3735d4e85238b65c0a11bad6c9") = ddfa6b045541afaafeb50e40b4732fa394de1952012cfde8519b13f7b872a9d8

The first winner is the contestant assigned 7 since his HMAC hash has the lowest value, the next winner is the contestant assigned 9 since his HMAC hash has the next lowest value.

If you want to reduce the number of people that have access to the contestants' unique identifiers before the results are determined, then you can randomly choose a 256 bit number for every contestant and publish the SHA256(identifier) list of contestant hashes.  Then after the election, you can publish the identifier so that the SHA256(identifier) list and the elections results can verified.


EDIT: Removed an idea that was pretty silly and not well thought out.

[iddo]

If you want to use multiple blocks, then pre-define a set of block heights. Repeat the process for each block hash, using the output from the previous HMAC hash as the new key for the next HMAC hash.

This is useless, an attacker will simply try to influence only the last block.

[DannyHamilton]

If you want to use multiple blocks, then pre-define a set of block heights. Repeat the process for each block hash, using the output from the previous HMAC hash as the new key for the next HMAC hash.

This is useless, an attacker will simply try to influence only the last block.

You are correct.  I hadn't thought that part through very well.  I've removed it from my post.