Fair and Honest votingSo 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 anyones vote? |
Method
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 anyones 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\)):
\(Key_i=g^x \pmod p\)
Once all the voters have been registered, their voting keys are published. Next each voter calculates a $y_i$ value as:
\(y_i =\prod_{j=1}^{i-1} g^{x_j} / \prod_{j=i+1}^n g^{x_j}\)
This will then make sure that:
\(\prod_{i=1}^n g^{x_i y_i} \pmod p = 1\)
Each voter can then provide a verifiable hash of their vote (\(v_i\)):
\(Verification_i=H(g^{x_i y_i} g^{v_i}) \pmod p\)
and make their vote (where $v_i$ is a yes vote) with:
\(Vote_i=g^{x_i y_i} g^{v_i} \pmod p\)
In the end, anyone can compute:
\(Tally=\prod_{i=1}^n g^{x_i y_i} g^{v_i} \pmod p\)
and then determine:
\(g^{\sum v_i} \pmod p\)
and an exhaustive search we can determine the summation of yes votes (\(\sum v_i\)).
Figure 1: Open Vote
Outline
Here is the code (I have just used 512-bit prime numbers, but in practice this would be at least 1,024-bit values):
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) v[0]="0" v[1]="1" v[2]="2" v[3]="3" v[4]="4" 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:
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
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.