Community Wide Challenge - (Solutions not votes)
-
I am looking for the best full and partial scope solutions people have for the classic Splitting the Loot problem.
The 51% problem exists because it’s a binary process. A sends transaction, B receives. Confirmations are the same, two steps. Check the signature, add your own. There are only two steps, therefore there are only options A and B. To raise the barrier to 75% we would need a 4 participant process. 90% would require at least a 10 participant process.
For an introduction:
If you have two children splitting a cake, the solution is for one to choose the cut and the other to pick the piece he/she wants.For three thieves splitting the loot things get a little more challenging. How do you split the loot equally, while not allowing 2 guys to screw over the 3rd guy?
Now raise this to N thieves or participants.
I’m looking for both full scope (100 participants) and partial scope (20 5 participant groups) solutions.
You don’t need to be a genius, you just have to be creative.
-
Good luck thinking/piecing together a solution zero… just woke up (forums are the first thing I check each morning lol) but I’ll see if I can think of anything useful while at work.
-
It seems the key to these kinds of puzzles is creating risk as well as opportunity. In the two person case, one child could take the opportunity to cut the cake unequally, but then they risk having the other child choose the larger piece. By definition, both make a choice regarding the pieces they want. But the example is too simple to see that. Also there seems to be always 1 less cut than there are people.
In the case of more than one person, you have the extra issue of two people working together against the third. So you need two kinds of risk, one the size of the loot that might be taken away, and the chance that a piece that is in limbo may ruin everybody’s sneaky plans.
So suppose in the three person case, you have two cuts through the center of the cake which makes it four pieces. Then they all choose the piece they want. This leaves the last piece to be cut yet again.
For 4 people:
Cut the cake three ways, each chooses a piece from the 6 pieces. Combine the remaining two pieces as one piece. Cut 4x again. Choose from 4 from the 6. Repeat until done. There is the chance of the cuts being done unfairly, however, the person who hasn’t cut yet, gets to choose first. This effectively forces even cuts.For 5:
Cut 4 ways, etc. 5 out of 8 pieces are chosen. 3 out of 8 pieces form one piece. Cut 4 ways again.This does get us fair distribution. Or so it seems. Suppose two of 5 thieves, #1 and #5, are working against the other three. Suppose the first one cuts and the fifth one chooses first. If the others try to cut unevenly, the 5th one can pick the largest piece. So if two work against three, they can only take a larger portion if the other 3 try to screw the other 2.
-
This is a solution for the full scope. But need to turn it into code.
Partial scope involving small groups will follow after.
How to turn the above into code?
What if instead of tracking transactions (send and receive) separately we track them two by two. This is more work so we should perhaps reward say 500 coins. Say our work function hands out random sends (minus) and receives (plus). You get split share credits as they come. Those shares don’t count until there’s a matching plus of the same value for the minus. Say in a round the work is either plus or minus, so to get a block you have to go two rounds, and the block is split between the addresses that found them (250 each). If there are too many pluses or minuses you only get credit for the matching ones. So some attacker spamming sends, needs to then spam receives. And they can’t be sending out both in the same round. Instead of silly things like tainting or dangerous things like rollbacks, pools can delay the processing of spammed sends or receives, effectively blocking them in real time. But suppose rogue pools choose not to. Then these sends and receives have to survive multiple confirmations together. We can have a separation limit of say 10 rounds. So a -50 coin send can wait 10 rounds to be matched with +50 coin receive. Beyond that, the earlier one is discarded and the attacker has to repeat his attempt.
What I’m suggesting is not just add the nonce as proof of work, but use the nonce to create mock transactions and match them to rounds that occur after. Also we can randomize whether a round is a send round or a receive round.
If the attacker alternates send rounds and receive rounds and records them all as being the same positive or negative value, they would get credit. BUT we can improve that situation. We can deal with the maturity period (120 confirmations) differently from the transaction period (after 120). We can say that each -50 send has to match 120 +50 receives. And those +50 receives have to match 120 -50 sends.
