Running private lotteries attack

#1

Probably a naive question, but it will help with learning the system… Does anything prevent a malicious Eve from splitting their tokens into billions of smaller tokens, and then running the sortition on all of them…constantly… and then waiting to act badly until they happen to at some moment hold a sufficient number of votes to act decisively (and maliciously)?

#2

Dividing stake across multiple accounts does not increase your chance of winning lotteries or increase the weight of your stake.

#3

Dividing stake across multiple accounts does not increase your chance of winning lotteries or increase the weight of your stake.

This is a claim without any supporting argument, reference, or evidence. Please try, at least a little, to support your claim.

The discussion on page 28 of the white paper [https://arxiv.org/pdf/1607.01341.pdf] seems to say very clearly that the number of users (not the size of their stake) matters a great deal:
“A careful, Markov-chain-like analysis shows that, no matter what options the Adversary chooses
to make at round r −1, as long as he cannot inject new users in the system, he cannot decrease the
probability of an honest user to be the leader of round r + 40 much below h. This is the reason for
which we demand that the potential leaders of round r are users already existing in round r − k.”

My attack proposal was simply that moles may lay hidden for much longer than k rounds, acting benignly until cued (or having their account compromised) only much later.

#4

This is an interesting attack. A protocol that’s vulnerable to an adversary splitting stake is definitely not resilient against the Sybil attack, which is something that’s required of any permissionless cryptocurrency.

I believe that the Algorand protocol uses the output of the verifiable random function, weighted by stake, to sample from a binomial distribution. Due to the additivity of the binomial distribution, splitting stake should not increase a user’s chance of selection. I got that from section 5.1 of the following document: https://algorandcom.cdn.prismic.io/algorandcom%2Fa26acb80-b80c-46ff-a1ab-a8121f74f3a3_p51-gilad.pdf

Unfortunately the ideas are not all condensed into one paper, which makes things a bit harder to find.

Modulo stake-splitting, I believe that all of the inputs to cryptographic sortition are committed to in an unpredictable way well ahead of selection, which as you brought up is argued to be secure with the “Markov-chain-analysis”. By strong unforgability of the VRF, Eve needs to hold more than some fraction of the stake to control a committee with overwhelming probability.

I’m being a bit imprecise and vague here, so please let me know if this makes sense!

#5

To complement what @algorand-sybil said (which its username is funny for this thread discussion :slight_smile:).

The most important point of not injecting new users in the system is being completely sure that all the keys that participate in sortition with seed Qr, weren’t created knowing what the value of Qr was going to be.

An adversary can have an edge on predicting that some future seed has a particular value, thus can generate keys that will have an advantage in the sortition using that seed. That’s bad, and the additive property of the binomial distribution wouldn’t hold since this manipulated keys coins wouldn’t have the same chance of sortition success compared to others.

To fix this problem, when seed Qr is used for sortition, is safer only to consider keys created a long time ago were the value Qr couldn’t be better predicted than random. The sortition will be fair.

Considering your attack idea, the design is totally ok if you generate keys with a long time before admitting them to executing your attack. When you created them, you couldn’t predict what the value of the first seed would be, so your keys have the same chance of being selected as any other key in the system. And of course, an equal probability of having all that coins in only one key (due to additivity of binomial distribution).

Don’t take this as an official response since I also reconstructed knowledge merging various papers, but I hope can be useful.