Finding a Bloc STAR provider

Core Development
22

(apologies for any weird link formatting, I’m a new user and the forum won’t let me use too many links :sweat_smile:)

Hello, I’m Arend. I’m the production lead at Equal Vote and also one of the co-leads on the BetterVoting project.

I’m so excited you decided to move forward with STAR! I’m also glad to see how much deep diving you all have already done. Here’s some clarifications on what I’ve read above:

Pricing

As we’re in open beta our pricing model is still in flux, but we hope to be fully released by next November and I expect it to look something like this:

  • Free for public elections
  • Private elections will have a cost if you have more than X voters
  • If you need something special (custom code, or us doing admin), then we’ll figure out a special arrangement.

(this information is also on the homepage after scrolling down, but more UX work is certainly needed on our side to make everything clear)

As your election will be on the smaller side, it might still fall into the free tier category, but I’m not sure yet.

Anonymity

Guido is correct. Although there’s nothing in the UI that links voters to their ballots, that connection does still exist in the database.

That said our architecture stores voters and ballots in separate tables. We investigated fully decoupling them and believe it would be a low effort update. If that was a deal breaker we could either make that an election setting, or something we can override per election.

Downloading Anonymized Ballots

This is an election setting. We’re allowing anyone to download the ballots by default in order to encourage transparency, but this can be disabled for those want their elections to be more closed.

Editing Ballots

This is something we don’t support yet, but we hope to add it eventually and we’re open to further discussion. I get the impression that this is one of the higher priority asks from the group?

Resolving Ties

Ties will initially be resolved using our recommended tie breaker protocol (starvoting dot org slash ties). If a random tie breaker is needed we use javascript’s random library seeded with the number of voters and let it decide (so it is deterministic).

That said, all tabulation and tie breaking steps are exposed in the Tabulation Logs section on the results page, so you’re welcome to override any part of the tie breaker with your own process if needed.

Preliminary Results

This is also an election setting. Preliminary results are currently available by default, but most private elections will probably want that disabled until the end date, so we may reconsider the default setting.

But as Tim said, currently the election admin CAN see preliminary results regardless. I already have feedback to fix this and it will certainly be resolved in time for your election.

Candidate Order

Candidate order is randomized by default to avoid biases, but this can be disabled (some people have long candidate lists and felt listing them alphabetically would be a better user experience).

Feedback

Any feedback is super appreciated! I will be noting the feedback in this thread but also don’t be shy about using the feedback button. We welcome bugs as well as suggestions. Posting issues on our Github (equal-vote/star-server) is another option.

no vote vs 0

(This is just me nerding out a bit). Although that information doesn’t impact the results, I’ve found that information useful as a proxy for name recognition. Candidates with higher name recognition will have a higher percentage of people give them a score (including 0). I’ve already seen this on some sample elections we’ve ran (at 8:30 timestamp) and I hope to surface more data like that in the “stats for nerds” section of the results page. The results section for bloc-STAR is still minimal but you can see our presidential poll for a more fleshed out example: bettervoting dot com slash pres24 slash results (that was just an online poll, and obviously not a representative sample :laughing:)

Other Tools

Me & Larry have connected before. Our team has been really impressed by the documentation and testing on his library. We certainly have a lot of work to do on our own starpy github repo (Equal-Vote/starpy) including publishing it on pypi. As the anonymized ballot data is public, I fully support folks to download and verify the results using other tools.

For officiating online elections, we built BetterVoting.com because there weren’t really other options for running STAR Voting (and our previous iteration at star.vote needed some updates). We hope that BetterVoting becomes a place for orgs to use better voting methods while also having their logistical & security needs met, and from there we hope that more services will also include STAR in the future.

14 Likes
23

Hi! Thanks for posting. I’m excited too to see you working on this new voting service. I’ve been a strong STAR advocate for years, and it’s about time you made it easily usable :wink:.

I don’t see any “deal breakers” yet, but I’m still doing “due diligence” by taking it for a drive on contrived test elections.

Much of what we’ll see here is rephrasing “but that’s not how Helios worked!”. We’ve mostly been using “block Approval” for years, and Helios supports that well, but last I checked its deep crypto tricks hadn’t been extended to ranked ballots “even in theory”.

I’m not much concerned about security issues beyond the essentials (e.g., is it easy for a random hacker to get root access to your servers?). While, in general, I’d rather trust processes than people, we have complete confidence in the PSF staff who would be running our elections. They’re simply not going to “cheat”, or reveal how voters voted, etc.

I think you’re right that the one thing people will miss most from Helios is the ability to change their vote.

And one more that hasn’t yet come up here: the ability to add some text to the display of a candidate’s name, and particularly to add a hyperlink. Candidates’ nomination statements can be quite lengthy, and it’s great to have live links to their statements in the ballot.

For the rest, your defaults are fine:

  • Randomized order is what we want. We may never see more than 10 candidates.

  • I absolutely want anyone to be able to download the raw anonymized ballots when an election ends (but not before). Already easy to set up. Nobody yet here has complained about that (or I missed it if they did)

  • Fine too that early results are available by default. We don’t want that in “real” elections, but it can be turned off easily. It’s helpful for people just starting.

  • Any deterministic way of breaking ties is OK by me. It would be best, though, if you and @larry could coordinate on a single default way of generating an illusion of randomness in the rare cases it may be needed.

So it is! My apologies for missing it.

I can’t speak to pricing, because I can’t speak for the PSF. Our recently-concluded Steering Council election had exactly 100 voters, although only 76 voted. That will probably grow some by the next election. If elections for the PSF Board also switch to bloc STAR, a substantially larger voter base would be involved.

So too many unknowns for now to say much concretely yet.

So far the test drives have been very encouraging!

3 Likes
24

This is mostly for @EWDurbin: my test elections have gone on to restrict voters to a pre-specified list of email addresses. Which uncovered a feature I don’t think Helios supported: this system remembers which voters have clicked the magic link (in the email the system sent to them) and gone on to submit a ballot. At any time, with a few clicks you can send voters new email: all voters, only those who have voted, or only those who haven’t voted.

So, e.g., after a week passed, you could, in less than a minute, send a reminder email to those who haven’t yet voted. And perhaps more frequently as the deadline approaches.

One potential problem which I assume @ArendPeter already knows about: if one of those emails fails (I put in some known-to-be-bogus addresses), you don’t find out about that. The bounce is just invisible to you. I imagine that could be a rathole to try to “fix”.

And one arguable oddity: if someone submits a ballot without having selected any stars, that counts as “an abstention”. They are recorded as having voted, but the count of ballots cast doesn’t increase. No particularly bad consequence I can see, but since they have voted, they can’t (yet) change their mind and cast “a real” ballot later. They’re done.

I don’t expect that to happen often, but I’ve run little elections before over the web, and there is absolutely nothing people won’t do by accident :frowning:

2 Likes
25

Earlier in the thread Arend said they used Javascript to tabulate the elections, so I’m assuming they wouldn’t be using my library.

Here’s a plodding description of how my deterministic tiebreaker works, including the various Python data structures and library routines I used. Sorry if any/all of this is obvious–I’m only a programmer, and I’ve barely dipped a toe in the election science world.

  • Start with the following data:
    • a list of all the ballots. I store ballots as a dict, mapping candidate name to vote.
    • an integer representing this tiebreaker. I start with 1 for the first tiebreaker, and if I wind up needing additional tiebreakers I increment this integer by 1 each time (so it’s 1, 2, 3, 4, etc).
    • a list of the candidates.
  • Sort the list of candidates.
  • Convert each of the ballot dicts into a ballot list: a list of tuples of (candidate name, vote). Now you have a list of ballot lists.
  • Sort each ballot list.
  • Sort the list of ballot lists. You now have a deterministic blob of data; for this election, with these ballots, this sorted list of sorted ballot lists will always be identical.
  • Serialize the list of ballot lists into binary data. I used the Python function marshal.dumps, but pickle.dumps might be better if you care about consistent results between Python versions or across platforms. Either one will produce identical results every time when run with the same Python binary.
  • Use a high-quality hash algorithm to hash the integer, followed by the serialized list of ballot lists. I used SHA3-512, because it’s awesome, and because I wanted lots of bits in the result. This produces a binary digest.
  • Use the binary digest to seed a PRNG. I created a new Python’s random.Random object, passing in the digest for the seed argument to its constructor. This object uses the Mersenne Twister algorithm.
  • Shuffle the sorted list of candidates, using a random shuffle algorithm, using the PRNG I just created above. I called the shuffle method on my Random object, passing in the list of candidates.
  • (Actually, I shuffled it three times, just for fun. This shouldn’t be necessary. I guess I have a misguided sense of fun.)
  • When breaking a tie, you have a set C of tied candidates of length |C|, and you want to choose M of them, where M < |C|. I iterate over the shuffled list and select the first M candidates I see that are members of C. For example, if the shuffled list is [ Z X G Q R E ], and there’s a three-way tie between Z Q and E, and we need to choose two candidates to break the tie, I’d pick Z and Q, because those are the two candidates of C that appear earliest in the shuffled list. In Python you could express that as [ candidate for candidate in shuffled_sorted_candidates if candidate in C ][:M].
3 Likes
26

For anyone who wants to try their own test election, and especially for @EWDurbin (he needs to try this), here are the steps I recommend. I hope I’ve left nothing material to imagination:

After you log in, click on your account and select New Election. A box pops up:

  • Poll or Election? Election

  • Title? e.g., PSF Steering Council - 2025 term

  • Restricted? Yes

    Fill in contact email address for election help

    • Would you like your election to be restricted to a pre-defined voter list? Yes.

  • Choose voters: click on Email List

The initial box vanishes then.

On your computer, create a text file of voters. This is in CSV format, although there are no commas involved The first line should be exactly (the word “email”):

email

Then one line for each voter’s email address:

their_email_address, like abc@xyz.ty

CAUTION: I had to remove the last newline in my file, else an “extra” voter got created with a senseless entry. Maybe because I’m on Windows, but the file was created with Unix line ends (plain newline, no carriage return),

On the far left, click on Voters.

  • Then click ADD VOTERS.
  • Check the Email box; leave the Voter ID box unchecked.
  • Click SELECT FILE near the bottom.
  • Navigate to your voter file on your machine, and select it.
  • A box with title “Voters” should appear, with one row per voter email address.

On the far left, click on ADMIN HOME.

Click on the pencil icon at the upper right of the top box.

  • Add a description, if you like.
  • Check the Enable Start/End Times? box.
  • Fill in Time Zone, Start Date, and End Date fields.
    – Note that AoE doesn’t appear to be a supported option.
  • Click SAVE.

Click on the pencil icon at the upper right of the Extra Settings box.

  • Check “Randomize Candidate Order”.
  • “Allow Voters To Edit Vote” is greyed out and not checked.
    – If it becomes available, check it.
  • Uncheck “Show Preliminary Results”.
  • “Enable Random Tie-Breakers” ia greyed out and checked.
    – If it becomes available, leave it checked.
  • “Enable Voter Groups” is greyed out and unchecked.
    – If it becomes available, leave it unchecked.
  • Uncheck “Customize Emails To Voters”,
    – Although I actually have no idea what it does.
  • Check “Confirm That Voter Read Instructions”.
  • Uncheck “Make Election Publicly Searchable”.
  • Uncheck “Set Number Of Rankings Allowed”.
  • Click SAVE.

Click ADD to the right of Races. This is the actual election :wink:

  • Fill in Title and Description boxes.
  • Select Basic Mutli-Winner radio button,
  • Enter 5 in the “Number of winners” box.
  • Under “Which voting Method?”, select “STAR voting”.
  • Fill in the candidates’ names, one per line.
  • Click SAVE.

Now you’re back to the admin page.

  • Click CAST BALLOT to the right of “Cast test ballot”.

    This doesn’t count as a real vote; it will be thrown away.

Go back to earlier steps as needed until everything looks right.

Click FINALIZE ELECTION. Nothing material can be changed again after this.

A “Send Email Blast” box pops up. If you’re ready to let voters know, click YES.

  • Click DRAFT EMAIL BLAST.
  • Select “Election Invitation Template”.
  • Alter the text as desired. It looked good to me as-is.
  • Click SEND EMAILS.

Take a vacation :smile:

6 Likes
27

For an independently verifiable result, it would be better to not use any implementation-defined algorithms like marshal.dumps/pickle.dumps (see a bug I just filed), Javascript’s random() or Python’s shuffle().

5 Likes
28

Indeed. I would want the random part of the tiebreaker to be something that you can rewrite easily in any programming language without libraries. This includes not using a standard hash.

Why? If there’s a tie to break randomly, I find it more important that all tabulation systems give the right result than about the quality of the randomness of the simulated coin flip. If you want a real coin, ask a human. (In which case the optimization not to do this when the loser would win in the next round seems important.)

3 Likes
29

Indeed.

In one way this is a classic bike shedding sinkhole: the tiebreaking protocol for bloc STAR already has many deterministic steps. In a real election, it’s very unlikely pseudo-randomness will ever be needed. When it is needed, there’s nothing in the data left on which to make a principled decision, so scant basis on which to object to any resolution.

I can help solve this, but won’t take the time unless @larry and @ArendPeter are agreeable. Keys:

  • A fixed, permuted list of candidates is a bog-standard way for all kinds of systems to resolve ties. C beats D if and only if C appears before D in this list. @larry already does this.

  • Python’s shuffle() implements the very short and simple Fisher-Yates shuffling algorithm, which is still state of the shuffling art. Easy to code in any language.

  • shuffle() in turn requires an integer-valued random-number generator. That’s the “hard part”. There are in fact high quality integer PRNGs that require little state and little code, at least when coded in C or Python. JavaScript seems more of a puzzle, since its ints are “really” doubles under the covers, so are limited to 53 bits, and looks like its Bigint type is always signed. Melissa O’Neill’s brief and very high quality PCG-XSH-RR generator produces 32-bit ints using just 64 bits of state, but it requires 64-bit unsigned integer arithmetic.

  • Possible insecurity if seeding the generator by number of voters: if the initial list of candidates is in the order the election admin entered them, then the admin could bias the election: they know the number of voters in advance too (at least in our elections), so could change the initial order to result in a permuted “random” order they favor. A solution to that would be to sort the candidates by name before shuffling it.

  • Seeding schemes fancier than that really aren’t needed. Nobody cares except for extreme geeks :smile: (but, ya, it takes one to know one).

  • There’s no benefit in shuffling more than once.

  • People overwhelmingly want an election service to do “the hard parts” for them. Very few want any manual steps in any case, at least not after they understand that “when we resort to ‘random’, tie means tie: there’s absolutely no principled way left to break the tie - ‘random’ is as good as it gets”.

30

[…]

  • Possible insecurity if seeding the generator by number of voters: if the initial list of candidates is in the order the election admin entered them, then the admin could bias the election: they know the number of voters in advance too (at least in our elections), so could change the initial order to result in a permuted “random” order they favor. A solution to that would be to sort the candidates by name before shuffling it.
    […]

In another community where I’ve officiated elections using a ranked choice voting mechanism, our tie-breaking algorithm uses a PRNG seed which combines the date the election opened, the names of the tied candidates and the for/against scores for each (we’re using Condorcet+Schulze, but the challenge here is fairly similar at least). We also specify that the list of candidate names for the “coin toss” is supplied in alphabetic order by name, where the names are a single fixed string per candidate as supplied in their original nominations.

Granted, in the 50+ elections I’ve witnessed for that community, I can count the number of ties we’ve had on one hand (after sawing off all the fingers).

3 Likes
31

Despite being relatively simple, this might still be a bit overkill.

If I needed to reproduce results with independent implementation I would be much happier with simple linear congruential generator.

1 Like
32

I hope it will not be possible to view preliminary results. IMHO that should be a deal breaker for choosing a voting system.

3 Likes
33

It’s not on the table here, period. I made them available in my very first toy test election to help me get answers to questions about how the service worked. Early results are not available in the most recent test election (still in progress), and the long writeup I gave suggesting how the PSF should set up elections explicitly turns off “early results”. No worries :smile:.

2 Likes
35

The devil is in the details. I want to use shuffle because it’s principled, clear, and establishing a random permutation for tiebreaking is almost universally used in the research literature, very common in practice, and is applicable to any scoring method whatsoever in which ties are possible.

But LCGs can have bad effects when using Fisher-Yates for shuffling. In particular, if using a full-period LCG with a power of 2 modulus, successive outputs strictly alternate between being even and odd. That in turn can make the possible permutations very far from “looking random”, depending on all the details.

Have a little trust in that I’m not flying blind here :wink:.

1 Like
36

Hm, it looks to me then as if the “pick a random permutation before starting the election” is the best solution. And in this case I don’t mind that the randomness derives from e.g. Python’s or JavaScript’s random function: the permutation becomes part of the election data, and anyone can do their own tally using that same list.

That seems much easier than trying to design a new random generator that’s easy to implement and not lame.

5 Likes
37

I’m agreeable :slight_smile:

If we agree on good process for a language agnostic random tiebreaker then I’m happy to coordinate with Larry to ensure we’re using the same algorithm across starpy, starvote, and BetterVoting. Then we can have a standard to start spreading to other tools.

1 Like
38

My strong preference is to establish a “random” permutation of the candidates. Then C beats D if and only if C appears before D in the permutation. That applies uniformly regardless of which scoring method is used. @larry’s code already does that, although it may be more work for you (for example, does JavaScript even offer a standard shuffle() algorithm?).

I agree with Guido that it would be simpler in some ways to let each implementation use whatever randomdish facilities its implementation language offers. Then 2 more things would be needed:

  • Your service would need to make the permutation picked visible (presumably a new option in the Extra Settings dialog).
  • @larry would need to allow users of his library to specify the permutation to use.

Then users of Larry’s library could reproduce your results.

OTOH, it’s simpler in other ways if all implementations of STAR created the same permutation to begin with (or, at least, could be told to use a “standard” one). Let me think on that. Assuming you have no more than 216 candidates, I’m pretty sure we can do that using int arithmetic no more demanding than 16*16->32 bit unsigned int multiplies (and so not a problem even for JavaScript), and that all the code (including shuffling) would fit on a page of simple Python code. But then my desktop box has a large monitor :wink:.

39

Here’s the relevant code on our end: star-server/packages/backend/src/Controllers/Election/getElectionResultsController.ts at aef38cc0908bc24c4d20df0da83f422d31ab3874 · Equal-Vote/star-server · GitHub

So we seed the random library with election_id + num_votes. This way the tie break order will keep changing for each vote, but it’ll be consistent with the same number of voters.

Then we map each candidate to a random number, and reference those numbers in the tabulators when we’re trying to break ties.

But if there’s a new standard we’re happy to iterate on this. At one point we considered letting the admin set the tie break order. So the seeded approach could be the default, but the admin could override it if they want things to be consistent.

1 Like
40

I’m not fluent in JavaScript, so from context I’m guessing that tieBreakOrders is bound to a structure mapping candidates to “random” floats in [0.0, 1.0). That’s one way to record a permutation, provided all the floats are distinct. I think you’ll search in vain for a guarantee that they are, though :wink: Very likely to be distinct.

With the code below,

let rng = seedrandom(election.election_id + ballots.length.toString())

would be spelled

let rng = TinyRand(ballots.length).get

The .get() method there returns ints in range(65536), and guarantees there are no duplicates across 65536 consecutive calls.

It’s seeded with an integer in a language-independent way. Pass a string instead and it will depend on how the characters are processed. This particular PRNG only has 65536 possible states, so seeding doesn’t have much to do.

Here’s the Python code. I expect it would be easy to rewrite in any language and work the same way.

TinyRand 
# Very simple 16-bit PRNG, self-contained, and needing nothing fancier
# than 16x16->32 bit unsigned integer multiplication.
#
# We don't want much from this. After construction, 65536 consecutive
# calls to .get() will deliver each of the 65536 possible results once
# eahc, in a randomish order.

BITS = 16
PERIOD = 1 << BITS
MASK = PERIOD - 1

class TinyRand:
    def __init__(self, seed=0):
        self.seed(seed)

    def seed(self, seed):
        self.seed = seed & MASK

    def get(self):
        """Return a random iot in range(2**16).

        The period is 2**16, and each posdible result appears once
        across the period.
        """

        # At heart this is the ordinary LCG
        #    state <- state * 43317 + 1 (modulo 2**16).
        # It's strengthed a bit by returnubg the state xor'ed with a
        # shifted copy of the state, a PCG-like trick that destroys the
        # extreme regularity of the base LCG's low-order bits.
        # 43317 came from a table of multipliers with "godd" spectral
        # scores,
        self.seed = (self.seed * 43317 + 1) & MASK
        return (self.seed >> 7) ^ self.seed

if 1:
    t = TinyRand()
    full = {t.get() for i in range(PERIOD)}
    assert len(full) == PERIOD

Note that this is completely unsuitable if the number of candidates is greater than 65536 - then it would necessarily generate duplicate ints.

@larry , you’d get your permuted list building on this via, say,

sorted(list_of_candidates, key=TinyRand(number_of_something).get)

I think I should shut up now and let you and @ArendPeter exchange some ideas :smile:.

41

Although this would actually work:

tget = TinyRand(number_of_something).get
permuted = sorted(list_of_candidates, key=lambda x: tget())

This would make “smallest value most likely to win”; unclear to me whether @ArendPeter’s code base considers “highest value most likely to win” instead; if so, add reverse=True to the sorted call.

42

I’m confused, how is that different?

EDIT: I’m not confused, I’m just dumb, it needs to ignore the x parameter. Do carry on.

1 Like