It’s useless here because the mix doesn’t need to output private randomness, only public randomness. So it’s enough to use collective coin flipping (or secure coin flipping with honest majority) with or without cryptoeconomics.
I thought private randomness was one of the requirements, so that until the block is proposed no-one knows the proposer …
If a coin is flipped there is a period of time between the flip and the block propose, where everyone knows whos going to propose - arguably the proposer can be DoSed then
Here is another paper that discusses
shuffling in the presence of Byzantine parties
Yeah as mentioned above if you buy the arguments that such security properties are important then you can have this supposedly more secure variant, but then you inherently have honest forks (similarly to peercoin etc.) and you don’t need a shuffle (a.k.a. permutation) at all.
Edit: probably we were too vague. By saying that a protocol outputs “private randomness” this commonly means that random outputs of the protocol are delivered to specific participants and the rest don’t learn these outputs. For Justin’s protocol the random bits that decide the shuffle are public, but only the proposer learns where he was elected in the epoch. In the variant with honest forks, the random bits are also public, but only the proposer learns if he was elected in the epoch (this can be done by combining the public random bits with a decommitment of the proposer, and using hash inequality). So mental poker is an overkill because private randomness is unneeded in all cases.
What do you mean with honest forks?
I see 
I think I misunderstood the problem. I thought the problem was to pre-determine the order in which validators will propose. Now I see that this is just to register a validator set in the previous epoch without prematurely revealing the validators
Multiple validators elected to create a block in the same timeslot.
I think that you’re suggesting a different solution that doesn’t involve ephemeral accounts (Justin’s variant with linkable ring signatures requires sending the ephemeral identity from an account that’s different from the validator’s account). You can indeed do the mix in a way that involves sending messages only from the accounts of the fixed set of validators, using a secure shuffle protocol where the validators commits to secrets and each validator obtains an output that allows him to publicly prove his position in the permutation, but it’s complex and the mental poker approach isn’t suitable because it requires all the validators to run the computation together for each of the timeslots. Also you could never achieve lookbehind privacy this way because the validator becomes known after he proves his place in the permutation and creates the block.
Ok, thanks, but I don’t understand what it has to do with lookbehind privacy.
You seem to imply that lookbehind privacy, will result in honest forks. But wouldn’t it be possible to assign a timeslot to just one ephemeral key? Why does it matter if it will be known which validators owns the ephemeral key.
Ok, lets us try to define what the problem is:
-
There is a global set of validators that is registered in a smartcontract. Out of these validators we can assume that some (say less than 1/3) are Byzantine.
-
Validators register to be block proposers for a particular epoch.
-
We do not want them to be known until the epoch starts.
-
Once the epoch starts, it is ok for them to be known.
-
We do not want non-validators to register, and then do a no-show.
-
We want (?) to punish validators for registering and non-proposing.
I hope, that 1. ,2., 3., 4., 5, 6 correctly describe the goal …
Several things that I am confused about:
a) since some of the validators may be byzantine, they can potentially pass ring signature private keys to any number of non-validators. So it is not clear to me what the security of the ring signature is … Potentially any byzantine validator can pass her key to a 1000 non-validators, they can all sign up for the epoch and do a no-show, unless you ask for a deposit that is slashed in case of bad behavior (for instance no-show)
b) If 1/3 of the global set of validators is byzantine, how do we protect against a lot of byzantine validators massively registering for a particular epoch and then forming a majority …
I think generally there is some confusion in this thread, since it is not clear in general what the exact definition of the problem is …
Yes sorry I got confused when kladkogex raised the idea of generating private randomness and delivering it to specific validators, the “Edit:” afterwards clarifies that all these schemes can rely on public randomness. As you say, Justin’s scheme uses public randomness to create a permutation of the ephemeral keys and doesn’t have honest forks.
1 Like
So what prevents one bad validator from passing her ring signature key to a 1000 bad guys and all of them registering ephemeral identities, and then non-proposing when time comes ?) My understanding from reading the above is that validators are not punished for non-proposing and deposits will be returned to bad guys if they non-propose ?
Regarding the ephemeral accounts - looks like these guys will need to use a privacy overlay network like ToR,
otherwise the IP addresses will be recorded and correlated to the accounts, so the ephemeral identities will not help much …
Linkable ring signature is a more complex construction than just a ring signature, it gives the extra feature that if you double-sign then your original identity becomes known. So in your scenario the identity of the validator becomes known and the protocol can confiscate the security deposit of this validator. The advantage of linkable ring signature over cryptoeconomic mixing is that the identities of the other validators remain hidden when one validator double-signs.
I see … Interesting … But this is if you double sign the same message I suppose ?
If you produce two signatures on two different messages you are not going to reveal identity ?)
Which brings another question - when we say that the validator proves identity by doing a ring signature - what message is being signed ? 
No, any two messages, so the full scheme needs one-time linkable ring signature (I think it’s section 4.4 of cryptonote) and it’s even more complex. You sign the ephemeral key, and I suppose that you’d also need to submit to the blockchain a fresh one-time pubkey for the next epoch.
This is automatic because they will lose the block reward when they are not proposing.
I would add:
7) Lookahead privacy, only the validator proposing the block knows when he is allowed to propose a block.
8) Look behind privacy, only the validator proposing the block, knows that the block is his after is has been proposed.
Where 8 is a nice to have.
Interesting … so it is a new key for each signature …
One thing which is unclear to me is whether the validators propose in turns so there is a pre-determined order or whether validators can propose at any time?
In other words, for a given block number N, can one have 10 validators proposing 10 different versions of the block?)
Every validator is assigned a timeslot in which this validator is allowed to propose a block. Blocks proposed outside that timeslot will not be allowed.
If the next validator has not seen the previous block or thinks it is invalid, he will propose a block with the same block number bypassing the previously proposed block, creating a fork.
So it is possible, but not very likely.
Edit: And you only have one validator per timeslot.
So the “shuffling” that Vitalik is mentioning, is shuffling used to determine the ordering of validators vs timeslots ?))
Yes, the shuffling determines a mapping from the timeslots to the validators.
When there are more validators then timeslots in an epoch, it also determines which validators are unlucky and are not allowed to propose a block. All the unlucky validators can claim their deposit via a proof that they owned the secret value that was not used.
If the number of blocks per epoch equals the number of validators and you do not have lookbehind privacy, the last validator that can propose a block will have no lookahead privacy. So if that is the case you probably want to “overbook” the epoch, by having at least some unlucky validators to protect the last few validators.
The variant that @JustinDrake proposes seems to have one weakness - if someone monitors the network during submissions one can relate the submitted signature to the IP address of the submitter. The submitter will then need to use an anonymizing network like ToR.
I found an interesting paper that seems to guarantee anonymous assignment of agents to slots. The protocol is complex, but does seem to require an anonymizing network.
It is an interesting paper, arguably very technical, we should probably ask @iddo what he thinks about this paper. Is this paper relevant in any way? In general, can oblivious transfer techniques be useful or relevant in any way to what we are discussing here?
And in general, is there an algorithm for shuffling that would be relatively simple and would not require using an anonymizing network? In the perfect world, one would introduce just a little bit more math to what @JustinDrake is suggesting to solve the IP address spoofing problem.
Just creating another identity does not seem to be strongly secure, since the IP address stays the same, and if you use multiple IP addresses you will run out of them quickly unless you use mTor or something similar …