Cryptoeconomic "ring signatures"

Thanks:)

The additional collateral for mixing makes the rewards less attractive even for large stakeholders. It’s possible to claim that they should settle for less lucrative rewards (and more blockchain bloat for all full nodes) because they’d have better security, but it’s a questionable claim in general and here also due to linkability analysis between the accounts that submit ephemeral keys and the validators’ accounts (also light client support might be more secure without mixing). Besides time value of money, the larger collateral raises the bar so smaller stakeholders cannot participate, which has negative implications on decentralization.

If I understand correctly what you guys are saying, it’s about a non-validator who gambles that not all the validators will submit ephemeral keys for the mix, so if his gamble pans out then he creates a block and earns a reward, otherwise he loses his collateral. In the variant without lookbehind privacy this gamble is useless because you have prove that you’re a legit validator when you create the block. It isn’t really clear to me why lookbehind privacy is desirable in this context. The arguments in favor of privacy for block creators are 1) less potential for a collusion attack, and 2) less potential for DoS on a validator when he tries to submit the block that he created during his timeslot. These arguments are debatable (since there are advantages with non-private block creators), but either way it seems that lookbehind privacy is irrelevant.

A coin tossing scheme (“common coin”) is where parties in round X agree on a random number. I suspect that running commoncoin at each round will satisfy the lookahead privacy as defined here. The parties can use a deterministric threshold signature
to sign the current block number, the hash of the signature will determine the blockproposer. The block proposer will include the signature when submitting the block.

The mathematical question really is whether one can design a better common coin algorithm assuming presence of a blockchain. I strongly suspect that what we are discussing here can be reformulated as common coin with some additional assumptions.

One possibility would be to use the common coin algorithm of
Micali which is used in Algorand.

With block chain you could make it simple in the following way: Micali algorithm is using regular signatures. Instead of signatures, each validator could hash a random number R N times in a chain sequence where N is the number of blocks in an epoch. The resulting hash

Then at each block, each validator would reveal a next level pre-image in the hash chain. This pre-image would be used as a signature in Micali algorithm to derive a random bit. So the blockchain would essentially be used to implement one-time signatures and plug them into the Micali algorithm.

Lookbehind privacy is desirable to limit adaptive attacks. Below are various examples, though imagination is the limit when it comes to adaptive attacks:

  • Miners in the main shard responsible for including collation header in blocks can decide (e.g. through bribing or collusion) to not include collation headers based on the identity of the proposer. Without lookbehind privacy this attack is facilitated because the proposer’s identity would be leaked at the time of collation proposal. This is at best a discouragement attack, and could be used for censorship or consensus attacks.
  • Validators in the child shard can decide (e.g. through bribing or collusion) to not build upon specific collation header chains based on the identity of the corresponding proposers, i.e. go against the default fork choice rule. This could be used to increase the probability of a collation header chain reorg, e.g. for the purpose of discouragement, censorship or consensus attacks.

A block proposer solution that has both lookahead and lookbehind privacy can be achieved via something like a “block coin”

It basically works as follows:

  • The block coin is an ethereum coin that will be fairly distributed among the validators based on the deposit amount.
  • The validators can use coinjoin/mixers so nobody knows who owns which block coin.
  • A block coin can be used to put one ephemeral key into the waiting set.
  • For every block a random ephemeral key is drawn from the waiting set that can be used for signing the block.

There are some details to be filled in like:

  • How many block coins do we want in distribution? To little and the mixers won’t work. To many and validators can hoard them and use them all at once to have temporary more influence.
  • Coins tend to get lost, we do not want to run out of block coins. So maybe let the block coins expire after a certain time and be redistributed among the validators.

As an added bonus we can have the shard collation proposers be drawn from the same waiting set.

Looks like this is related to Mental Poker protocols - essentially you use crypto to securely shuffle cards, so that until a party reveals her card other parties do not know which party has which card

Mental Poker

These scenarios seem just as plausible without lookbehind privacy, the attackers can always censor the block that was created if they don’t like the contents of the block, the only distinction with lookbehind privacy is that the attackers cannot censor the block just according to the identity of the proposer who created the block. If Alice and Bob are proposers who would create the same block, then the contents of the block are likely to be much more relevant for censorship attacks (rather than the identities Alice/Bob). Also, with lookbehind privacy in place, maybe the attackers have nothing against the validator identity but don’t like the account that submitted the ephemeral key E so they’d censor the block that E created (as you say imagination is the limit). If you think that cartel censorship is a significant concern then there are more important design choices, namely not relying on a mostly static set of validators who’d create blocks in the next epochs.

So here’s how this can be done using Mental Poker see (this article for details)

  1. Each validator has a commutative encryption key

  2. Each validator encrypts the sequence of numbers 1,2,3,4,5,6,7,8 … using commutative encryption. As a result, each number gets encrypted by keys of all validators, and the resulting value is stored in a smartcontract.

  3. The encryptions are shuffled so each validator V is dealt an encrypted value E. For each encrypted value, all other validators decrypt the value. The result y is then passed to V, who decrypts it using its private key and gets the plaintext number x

  4. At this point everyone has been dealt a plaintext number, but no one knows numbers assigned to other parties.

  5. At the time when a block needs to be proposed by a particular validator, the validator submits a proof proves that y is an encryption of x

This is in fact, similar to what Justin proposed, but uses commutative encryption to make things more secure.

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 :slight_smile:

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:

  1. 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.

  2. Validators register to be block proposers for a particular epoch.

  3. We do not want them to be known until the epoch starts.

  4. Once the epoch starts, it is ok for them to be known.

  5. We do not want non-validators to register, and then do a no-show.

  6. 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 ? :rofl:

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.