Parallel collections for vote processing

At AgoraVoting we recently completed a very important feature, cryptographically secure voting. Among many other things, this adds a lot of heavy number crunching to the process of carrying out elections. One of the steps in the process validates votes, using something called proofs of knowledge. I won’t go into the math details here, just note that like other domains such as 3D graphics, processing votes is embarrassingly parallel. So we carried out an experiment to see how Scala’s parallel collections can achieve parallelism for one particular task.

In this experiment, we have to parse voting records which are then transformed into collections for their validation. The technique is to first obtain a collection with all the necessary data, and then compute in parallel on it. But first, lets see what happens with sequential code, for comparison. I’ve left out the preprocessing code that first obtains the collection, here’s the compute-intensive fragment:

[scala]

ctexts.foreach( vote => {
vote.foreach( question => {

val pk_p = BigInt((question(2) \ "p").as[String])
val pk_g = BigInt((question(2) \ "g").as[String])

val commitment = BigInt((question(0) \ "commitment").as[String])
val response = BigInt((question(0) \ "response").as[String])
val challenge = BigInt((question(0) \ "challenge").as[String])
val alpha = BigInt((question(1) \ "alpha").as[String])

val toHash = alpha + "/" + commitment
val digest = MessageDigest.getInstance("SHA-256")
val hash = digest.digest(toHash.getBytes("UTF-8"))
val expected = BigInt(1, hash)

assert (challenge == expected)

val first_part = pk_g.modPow(response, pk_p)
val second_part = commitment * (alpha.modPow(challenge, pk_p)) % pk_p

assert(first_part == second_part)
})
})

[/scala]

Here’s what happens when running this code:

seq

as you can see, the cores are underutilized. This test run took 1175.254 seconds. Now let’s turn ctexts into a parallel collection before processing on it:

[scala highlight=”1″]

ctexts.par.foreach( vote => {
vote.foreach( question => {

// the same code here …

})
})

[/scala]

Yes, that’s a difference of just three characters, par converts ctexts into a parallel collection. Here’s what happens:

par

All the cores are maxed out, total time: 307.184 seconds. Not bad!

Leave a Reply

Your email address will not be published. Required fields are marked *