Voting For The 21st Century

Voting For The 21st Century

And so as a proud Edinburgh, Scottish, UK and EU citizen, I voted last week. It is one of the most fundamental things that we have in our world .. the right to vote.

But I watched the count, and saw a mainly 19th Century system of voting — I do appreciate some of the reasons why it is done like this, but really we need to look at the core infrastructure for making parts of it digital and to integrate trust at every point.

And so I took my piece of paper — which came in the post — to the election station. I handed it over, and they looked up my name on a piece of paper, and then someone looked up another piece of paper and wrote my ID onto the voting card. I then went into a voting booth, and put a cross on the paper with a pencil (!!!), and folded it up. Then it went off in a van, and lots of people counted the votes.

So let’s have a bit of fun, and see if we can find a solution to creating a more citizen-focused election system, and where our voters can register themselves digitally, and then for each voter to cast their vote, and then for every voters to see the total of the votes cast, while not revealing any of the votes for each person.

Meet Alice, Bob, Carol, Dave, Eve and Trent

So how can be created a trusted voting system? With this we want to make sure that Alice, Bob, Carol, Dave and Eve can vote in an election, but keep their votes secret. But none of them trust Trent to count the votes, so can we find a way for them all to vote, and broadcast their votes to everyone else, and then for each of them to know the result of the vote, without revealing anyone’s vote?

One of the advantages of using Blockchain is the application of smart contracts which can be used for self-tallying voting. Within [1] the authors define a smart contract method within Ethereum, and where there is no need for a trust infrastructure and where the privacy of the voter is preserved. The only way to breach the vote is where all the voters collude against the system. Zero-knowledge proof using is implemented using the Schnorr proof [2] and is made non-interactive using the Fiat-Shamir heuristic [3]. In their solution (as illustrated in Figure 1), voters register their voting key with (for voter i):

Once all the voters have been registered, their voting keys are published. Next each voter calculates a $y_i$ value as:

This will then make sure that:

Each voter can then provide a verifiable hash of their vote (vi):

and make their vote (where $v_i$ is a yes vote) with:

In the end, anyone can compute:

and then determine:

and an exhaustive search we can determine the summation of yes votes (∑vi).

Figure 1: Open Vote

The following is some Go code to implement this [here]:

package main

import (
    "fmt"
    "math/big"
    "math/rand"
    "strconv"
    "os"
)

func get_g_p(size string) (g, p *big.Int) {

    if size == "512" {
        p, _ = new(big.Int).SetString("FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17", 16)

        g, _ = new(big.Int).SetString("678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4", 16)

    }
    if size == "768" {
        p, _ = new(big.Int).SetString("E9E642599D355F37C97FFD3567120B8E25C9CD43E927B3A9670FBEC5D890141922D2C3B3AD2480093799869D1E846AAB49FAB0AD26D2CE6A22219D470BCE7D777D4A21FBE9C270B57F607002F3CEF8393694CF45EE3688C11A8C56AB127A3DAF", 16)

        g, _ = new(big.Int).SetString("30470AD5A005FB14CE2D9DCD87E38BC7D1B1C5FACBAECBE95F190AA7A31D23C4DBBCBE06174544401A5B2C020965D8C2BD2171D3668445771F74BA084D2029D83C1C158547F3A9F1A2715BE23D51AE4D3E5A1F6A7064F316933A346D3F529252", 16)

    }
    if size == "1024" {
        p, _ = new(big.Int).SetString("FD7F53811D75122952DF4A9C2EECE4E7F611B7523CEF4400C31E3F80B6512669455D402251FB593D8D58FABFC5F5BA30F6CB9B556CD7813B801D346FF26660B76B9950A5A49F9FE8047B1022C24FBBA9D7FEB7C61BF83B57E7C6A8A6150F04FB83F6D3C51EC3023554135A169132F675F3AE2B61D72AEFF22203199DD14801C7", 16)

        g, _ = new(big.Int).SetString("F7E1A085D69B3DDECBBCAB5C36B857B97994AFBBFA3AEA82F9574C0B3D0782675159578EBAD4594FE67107108180B449167123E84C281613B7CF09328CC8A6E13C167A8B547C8D28E0A3AE1E2BB3A675916EA37F0BFA213562F1FB627A01243BCCA4F1BEA8519089A883DFE15AE59F06928B665E807B552564014C3BFECF492A", 16)

    }
    return
}

func calcit(i, n int, g, p *big.Int, y []*big.Int) (res *big.Int) {

    res, _ = new(big.Int).SetString("1", 10)

    for j := 0; j <= i-1; j++ {

        gm := y[j]
        res = new(big.Int).Mul(res, gm)
        res = new(big.Int).Mod(res, p)

    }
    for j := i + 1; j < n; j++ {

        gm := y[j]
        gm2 := new(big.Int).ModInverse(gm, p)
        res = new(big.Int).Mul(res, gm2)
        res = new(big.Int).Mod(res, p)

    }
    fmt.Printf(" ")
    return new(big.Int).Mod(res, p)

}
func mult(n int, val []*big.Int, p *big.Int) (r *big.Int) {
    res := val[0]

    for j := 1; j < n; j++ {
        res = new(big.Int).Mul(res, val[j])
    }
    return (new(big.Int).Mod(res, p))

}
func makeG(g *big.Int, val string, p *big.Int) (r *big.Int) {

    v := BigInt(val)

    return (new(big.Int).Exp(g, v, p))

}
func BigInt(val string) (r *big.Int) {
    r, _ = new(big.Int).SetString(val, 10)
    return
}
func getVote(Y *big.Int, x string, p, V *big.Int) (r *big.Int) {
    r = new(big.Int).Mul(new(big.Int).Exp(Y, BigInt(x), p), V)
    return r
}

func main() {

    argCount := len(os.Args[1:])

    n := 5

    x := make([]string, n)
    v := make([]string, n)
    y := make([]*big.Int, n)
    V := make([]*big.Int, n)
    Y := make([]*big.Int, n)
    RegVote := make([]*big.Int, n)

        if (argCount>0) {v[0] = string(os.Args[1])}
        if (argCount>1) {v[1] = string(os.Args[2])}
        if (argCount>2) {v[2] = string(os.Args[3])}
        if (argCount>3) {v[3] = string(os.Args[4])}
        if (argCount>4) {v[4] = string(os.Args[5])}

    g, p := get_g_p("512")

    // Voter random values
    x[0] = strconv.Itoa(rand.Intn(1e12))
    x[1] = strconv.Itoa(rand.Intn(1e12))
    x[2] = strconv.Itoa(rand.Intn(1e12))
    x[3] = strconv.Itoa(rand.Intn(1e12))
    x[4] = strconv.Itoa(rand.Intn(1e12))

    // Voting keys (broadcast by each voter)
    y[0] = makeG(g, x[0], p)
    y[1] = makeG(g, x[1], p)
    y[2] = makeG(g, x[2], p)
    y[3] = makeG(g, x[3], p)
    y[4] = makeG(g, x[4], p)

    // Voter values
    V[0] = makeG(g, v[0], p)
    V[1] = makeG(g, v[1], p)
    V[2] = makeG(g, v[2], p)
    V[3] = makeG(g,v[3], p)
    V[4] = makeG(g, v[4], p)

    // Each voter calculates Y[i]
    Y[0] = calcit(0, 5, g, p, y)
    Y[1] = calcit(1, 5, g, p, y)
    Y[2] = calcit(2, 5, g, p, y)
    Y[3] = calcit(3, 5, g, p, y)
    Y[4] = calcit(4, 5, g, p, y)

    RegVote[0] = getVote(Y[0], x[0], p, V[0])
    RegVote[1] = getVote(Y[1], x[1], p, V[1])
    RegVote[2] = getVote(Y[2], x[2], p, V[2])
    RegVote[3] = getVote(Y[3], x[3], p, V[3])
    RegVote[4] = getVote(Y[4], x[4], p, V[4])

    res0 := mult(5, RegVote, p)

    fmt.Printf("Vote1: %s, Vote2: %s, Vote3: %s, Vote4: %s, Vote5: %s\n", v[0],v[1],v[2],v[3],v[4])

    fmt.Printf("\n\nResult: %s", res0)

    
    for i := 1; i <= 10000; i++ {
        m, _ := new(big.Int).SetString(strconv.Itoa(i), 10)

        gm := new(big.Int).Exp(g, m, p)

        if gm.Cmp(res0) == 0 {
            fmt.Printf("\n\nTotal votes: %d", i)
            break
        }

    }

    fmt.Printf("\n\nVoter 1 (Vote Registration): %s", y[0])
    fmt.Printf("\n\nVoter 2 (Vote Registration): %s", y[1])
    fmt.Printf("\n\nVoter 3 (Vote Registration): %s", y[2])
    fmt.Printf("\n\nVoter 4 (Vote Registration): %s", y[3])
    fmt.Printf("\n\nVoter 5 (Vote Registration): %s", y[4])

    fmt.Printf("\n\nVoter 1 (Vote Value): %s", RegVote[0])
    fmt.Printf("\n\nVoter 2 (Vote Value): %s", RegVote[1])
    fmt.Printf("\n\nVoter 3 (Vote Value): %s", RegVote[2])
    fmt.Printf("\n\nVoter 4 (Vote Value): %s", RegVote[3])
    fmt.Printf("\n\nVoter 5 (Vote Value): %s", RegVote[4])

}

A sample run is [here]:

Vote1: 1, Vote2: 2, Vote3: 5, Vote4: 4, Vote5: 7

Result: 9499059345615389969840435808419125566245033357929304072344622690626502412542421684367703931302105397849390388675957378812140288740537857002835713186278293

Total votes: 19

Voter 1 (Vote Registration): 9717449441774596863932107182522723015293019558573861235057183453449918138887484006291371511239749270767730899934430122393332033312936519989621006232074095

Voter 2 (Vote Registration): 9979211979303271906561128573865484289840376149275844120064408657002526626214797587891497218571132555435308773667814984558530219287171718477448831292894276

Voter 3 (Vote Registration): 10260226055060144909495657309307620665975071716357821511668071773900528485759688558486229480267259436593234659383692953025154725723321456089371862729851636

Voter 4 (Vote Registration): 9374282770821534675247529713877083124189697278016496283445307756495925999913081637387484809415414806767669261226720017163156578480783405351792775885639485

Voter 5 (Vote Registration): 4715963672204178893519744645692315549756487065582594365925661689297962812692255475841524311321805156191081950992986134375414091134136796396861607730531987

Voter 1 (Vote Value): 32401232193006155720196638992531749412084427625631678775764791290303067299038470925303292706484585376785616471016503624166807297868000818159189905703742127006021153078333400603184740396745033006868636123575476150574731231178751789899302048597281566920155032719238246134742893881885934332176587099252458401520

Voter 2 (Vote Value): 22406638132804436992749249332952255862162414944274300242628892974896078442234146704784479269219657506758579636670217945256674939338444271409977122656492124652882892514131096981560147734302688011165533810813487451674675199550957033283366017521668531453196706310725822481137764122042248446613834059798769842615

Voter 3 (Vote Value): 11834926401421874979308640231507451884942087416483011363111684342351525054363986593712103415883169303927633242165502268430163354878431359401053897301322619263682111064193604401114412618063533264047238753072165283347737047811644373914381304774348253452543539995578870900232732281890514453274058217545113710666

Voter 4 (Vote Value): 9010114599879211200405233875413417299014138956847221705372417222243449960878258128009741739156673077210332638713398209172206282380236417865418977282905859379831673974563957671842162376097005309032662153452734661963752442476145490385627496849733054419140843839444313342637419185836216665660748272509770080480

Voter 5 (Vote Value): 21219110896547932984699096012205897827178091285359326237468919338515016060660237484642042927251805611756927000698809651784889873791932282484359734714554873875258800569641390232193260619426197901273988198800139619942591866665242425682016857024332330895501275000000583742729422468884919102219079592569480126060

Conclusions

And there you go. A voting system where Alice, Bob, Carol, Dave and Eve can vote, and for their vote to be counted, and where they can all determine the results of the vote, with Trent having to count them. Along with human trust in democracy, we need more digital trust, and to make sure that every single vote is counted, and that we can trust the results.

References

[1] P. McCorry, S. F. Shahandashti, and F. Hao, “A smart contract for board- room voting with maximum voter privacy,” in International Conference on Financial Cryptography and Data Security. Springer, 2017, pp.357–375.

[2] C.-P. Schnorr, “Efficient signature generation by smart cards,” Journal of cryptology , vol. 4, no. 3, pp. 161–174, 1991.

[3] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” in Conference on the Theory and Application of Cryptographic Techniques. Springer, 1986, pp. 186–194.