Grant Discussion On-Chain Voting Protocol Grant: Milestone 7

Secured
#1
Factomatic is excited to share the report on privacy-preserving voting on the Factom blockchain. You can find it attached.

We propose two different voting protocols, one based on ring signatures and a second one based on homomorphic encryption and zero-knowledge proofs. We hope you enjoy the report and are happy to answer any questions.
 

Attachments

Secured
#2
Thank you for writing this up! It's truly fascinating.

1. The use of commit - reveal for on chain voting where the reveal is not an automated process is still highly concerning to me. I realize this has to do with the underlying voting protocol and not what you present here today, but I wanted to mention it again. Requiring people to in essence vote twice is going to cause problems in a world where getting them to vote once is hard enough. If someone can come up with an efficient means to automate this, then it's a non issue.

2.
To make the process trustless, but at the same time robust, we suggest a distributed encryption scheme, meaning that it requires the cooperation of several parties to decrypt the results.
Is there any reason this can't be implemented in a manner where it's not people but decentralized systems that cooperate to decrypt the results? The systems are programmed in a manner where they automatically decrypt the results at a certain time unless there is manual intervention by the system's operator. When it comes to voting, people need to know that the results WILL be revealed at a certain time. I always worry about people not doing their jobs, especially when X (who may be globally distributed) need to perform the same task for it to be successful.
 
Secured
#3
Thank you for writing this up! It's truly fascinating.

1. The use of commit - reveal for on chain voting where the reveal is not an automated process is still highly concerning to me. I realize this has to do with the underlying voting protocol and not what you present here today, but I wanted to mention it again. Requiring people to in essence vote twice is going to cause problems in a world where getting them to vote once is hard enough. If someone can come up with an efficient means to automate this, then it's a non issue.

2.
Is there any reason this can't be implemented in a manner where it's not people but decentralized systems that cooperate to decrypt the results? The systems are programmed in a manner where they automatically decrypt the results at a certain time unless there is manual intervention by the system's operator. When it comes to voting, people need to know that the results WILL be revealed at a certain time. I always worry about people not doing their jobs, especially when X (who may be globally distributed) need to perform the same task for it to be successful.
1. I completely understand your concern. You could in principle automate the revealing, but not really in a trustless way (or at least I'm not aware of one if it exists) and it would defeat the purpose of having it in the first place. That said, the second protocol we have suggested -- based on homomorphic encryption and zero-knowledge -- I believe could get around this, but it would require some more investigation. With this protocol, you have the identity of the voter revealed, as they sign the messages they record on-chain with a vanilla digital signature. However, the options they voted for and the weight they assigned to each option are hidden and they don't have to be revealed by the voter. Essentially, the voter only casts their vote once and forgets about it. However, we would have to check if there are adaptive adversary attacks to this approach: i.e. security attacks on the protocol, which rely on the fact that there are no vote commitments, so you're free to construct your encrypted vote in potentially malicious ways.

2. There is no reason and that would be exactly the way to go, should we decide to implement such a system. Any party interested in securing the voting protocol, could download an open-source software, which runs as a daemon (similar to factomd or fatd, e.g.; or to the current on-chain voting daemon we're using). This daemon monitors special vote registration chains, registers as a processor for the vote and then participates in the decryption phase by contributing its share in a period between two blocks, which have been configured when the vote was created.
 
Secured
#5
Cryptographic capabilities are truly amazing, that's one of the closest thing to magic I know of! Nice read, thanks @Valentin Ganev! Traceable ring signatures sounds like a truly perfect fit for voting systems (weighting apart) and "relatively simple" to understand and put in practice. Homomorphic encryption is pretty hardcore in comparison.

Your conclusion is:
but require considerable scrutiny from cryptographic experts before being used in production.
What do you mean exactly? Ring signatures for instance have been around for some time, why couldn't we start using it right now?
 
Secured
#6
I cannot open link 7

We note that the security properties of the signature scheme are argued in the random oracle model [7], due to the reliance of the signatures on the Fiat-Shamir heuristic [8] for producing a non-interactive zero-knowledge proof of a secret key corresponding to a public key, which is part of the ring.
What does that mean exactly ? What is the "weak link" of this system in terms of security?
 
Secured
#7
Cryptographic capabilities are truly amazing, that's one of the closest thing to magic I know of! Nice read, thanks @Valentin Ganev! Traceable ring signatures sounds like a truly perfect fit for voting systems (weighting apart) and "relatively simple" to understand and put in practice. Homomorphic encryption is pretty hardcore in comparison.

Your conclusion is:

What do you mean exactly? Ring signatures for instance have been around for some time, why couldn't we start using it right now?
Glad you enjoyed it, Paul! We could use the traceable ring signature or the HE/ZKP approach right now IMO. However, the big caveat is that I'm not a cryptographer, so what I meant by the above is that I think no matter which approach we use, there should be an expert cryptographer reviewing it and also reviewing the code that is used or we end up writing. Essentially, we would need a security audit before potentially going live with either of those solutions.
 
Secured
#8
I cannot open link 7


What does that mean exactly ? What is the "weak link" of this system in terms of security?
Hmm, I'm able to access the link here: https://cseweb.ucsd.edu/~mihir/papers/ro.pdf. The title of the paper is "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols", you could Google it if you're interested to find more details. It's a rather popular publication (4800+ citations).

I would also refer you to this simple explanation, as well as the Wikipedia article on Random Oracles, which gives a very accessible overview.

Bottom line is that a random oracle is a function accessible to everyone in the system (adversaries included). This function outputs a unique (and random) output for each input it receives. There is some concern about the random oracle model, as it places an assumption over cryptographic hash functions, which is not part of the "standard model", namely that the output of the hash function to every unique query is uniformly random over its output domain. While this is not the case in theory, in practice a hash function is deemed a good enough approximation of a random oracle for a large number of problems.
 
Secured
#10
About the broken link I think it's because in your pdf the ~ is missing (at least when with my PDF reader)

Ok now I'm clear on the random oracle/hash function thing. So hash functions are deemed good enough to be used for ring signatures right?
Yes, you're right about the link...

Yes, hash functions are used for the Fiat-Shamir heuristic (in both protocols we suggested actually) and it's fine to use them for this purpose.
 
Secured
#12
I will defer to @David Kuiper about the timeline for the voting UI on MFW, but I believe there will be a testnet release within the next week and after acceptance testing (which will take a while), it will also be deployed on mainnet.

Whether we can use this for the next grant round depends a lot on the type of voting we will choose and more generally on the overall process, which from what I saw earlier is still being discussed. My personal preference would be to move to on-chain voting for this, but only if we have had ample time to test the voting app.
 
Secured
#13
Hi Valentin,

I am a bit late but I have been reading your report. This is a high-quality report and very pedagogical. Thank you for this.

I have some comments and questions:

- Ring signatures: This looks very promising even if it is a 2-step vote and weighting cannot be implemented. The only weakness I see is that one could analyse the vote timing to link identities to vote. Which is not the case of the HE/ZKP approach.

- HE/ZKP signautres: Correct me if I am wrong but in the HE/ZKP approach, theoritically individual ballot could be decrypted if enough receivers cooperate (at least t) to do so. Is it correct?
Then the value t has to be defined carefully : not too high in order not to allow a sub-set of participants to block the vote process intentionnaly and not too low for preserving anonymity. What are the recommanded values in the scientific litterature?

Moreover, this method needs several steps:
0/ Commitment of the polynomial chosen
1/ Verifying shares secretly shared between participants which leads to defining a final set of qualified participants.
2/ Calculating the resulting public key based on the set of qualified participants and their corresponding public keys (yi).
3/ Encryption
4/ Using ZKP to only consider eligible ballots
5/ Decryption (through the cooperation of t authorities)

Some steps could be performed successively which seems to lead to 4 different phases:
- Step 0 (need a user action)
- Step 1 (can be automated at risk)
- Steps 2 and 3 (need a user action)
- Steps 4 and 5 (can be automated at risk)

So, in any case we would need more than 1 step to vote. Not a big deal if the t value is well chosen. I guess it is not a big deal if we consider that the non-cooperative participants should be excluded through an emergency procedure to block the process.
Saying that, we could set a very high value of t (like 90%). Not 100% because there is always possible case of force majeur.
What do you think?
 
Secured
#14
Hi, @Matthias Fortin!

Thank you for taking the time to review the report and for bringing up these questions. I'll try to address them below:

Ring signatures
The only weakness I see is that one could analyse the vote timing to link identities to vote. Which is not the case of the HE/ZKP approach
Can you elaborate what you mean by analyzing the vote timing to link identities to a vote?

HE/ZKP signatures
Correct me if I am wrong but in the HE/ZKP approach, theoritically individual ballot could be decrypted if enough receivers cooperate (at least t) to do so. Is it correct?
Then the value t has to be defined carefully : not too high in order not to allow a sub-set of participants to block the vote process intentionnaly and not too low for preserving anonymity. What are the recommanded values in the scientific litterature?
You are right about the fact that any of the individual votes can be decrypted if enough parties collude. This is the case because the public key with which all ballots are encrypted is the same and is generated by the secret shares of the "trustees". Here is a quote from Benaloh about a good threshold (the paper gives no argumentation about those numbers): "Depending upon the size of an election and political and practical constraints, reasonable threshold values for a particular election may, for example, be 3 of 5 trustees, 8 of 10 trustees, or 90 of 100 trustees". I definitely agree that if we were to use this method, we shouldn't set a 100% value for t, and something like 80-90% seems reasonable. The best part, as you noticed, is that if any trustees try to sabotage the process, there will be a clear evidence of this on-chain, so we could enforce good behavior off-chain by having serious repercussions for misbehaving parties (this would be especially true if ANOs serve as the trustees, which is how I imagined this initially).

Moreover, this method needs several steps:
0/ Commitment of the polynomial chosen
1/ Verifying shares secretly shared between participants which leads to defining a final set of qualified participants.
2/ Calculating the resulting public key based on the set of qualified participants and their corresponding public keys (yi).
3/ Encryption
4/ Using ZKP to only consider eligible ballots
5/ Decryption (through the cooperation of t authorities)

Some steps could be performed successively which seems to lead to 4 different phases:
- Step 0 (need a user action)
- Step 1 (can be automated at risk)
- Steps 2 and 3 (need a user action)
- Steps 4 and 5 (can be automated at risk)
I haven't really done a prototype for the whole thing, but I believe all of the steps can be automated without any risk, provided that we have off-chain consequences for misbehaving parties. The way I imagine it to work is that each participant which takes part in securing the procedure (i.e. it holds a secret share) will run a daemon, which has access to the relevant private keys of the participant, and which will monitor the blockchain for new chains that initiate a vote (this is how it's done at the moment for the on-chain voting app).

Each vote will be initiated by a JSON entry, containing all the relevant metadata for a vote, such as the "t" and "n" parameters of the vote, the start/end blocks for the different phases of the vote, the eligible participants, the eligible trustees, etc. If you look at the procedure described in the report closely, I think it's possible to automate pretty much all of it: e.g. the daemon will generate the random polynomial for each party automatically and will record commitments to its coefficients on-chain (so no user action needed for Step 0), then it will encrypt the shares for each of the other participants in the network and record those in a special chain, which will also be monitored by the daemons; when an entry in this chain appears and the daemon recognizes that it can decrypt it (using the private keys it has access to), it will do so and verify the validity of the share using the commitments from Step 0; it will record a signed complaint on-chain, otherwise, etc. etc.

I realize that the daemon would require significant software engineering effort & testing to get right and there might be edge cases that I'm not seeing right now, but overall I don't see a reason why pretty much the whole process shouldn't be automate-able. Please let me know if you see an issue with the above.
 
Secured
#15
Can you elaborate what you mean by analyzing the vote timing to link identities to a vote?
Hi Valentin,
Sorry for my late answer.
If my understanding of the ring signature process is correct, the reveal entry enables anyone to know the content of each ballot. Therefore, you could analyse individual votes and their timing to try to figure out who voted what. It would be a simple guess, not a certitude but still.
I guess this could be more or less obfuscated by using a daemon and set a random time setting before recording the entries.

The way I imagine it to work is that each participant which takes part in securing the procedure (i.e. it holds a secret share) will run a daemon, which has access to the relevant private keys of the participant, and which will monitor the blockchain for new chains that initiate a vote
When you mention "the relevant private keys of the participant" this is an equivalent procedure for you to "send xij among Zp secretly to party Pj (e.g. by encrypting with Pj's public key and recording the entries on-chain)" mentioned inthe document? Just to be sure we are speaking of the same step.
I understand what you mean. I just don't know how secure or hackable a daemon is. My intial feeling is that having a software monitoring the chain and accessing private keys of other participants is a perfect target for a hacker. But I must certainly miss something. Let me know in this case. Happy to learn :)

You are right about the fact that any of the individual votes can be decrypted if enough parties collude. This is the case because the public key with which all ballots are encrypted is the same and is generated by the secret shares of the "trustees". Here is a quote from Benaloh about a good threshold (the paper gives no argumentation about those numbers): "Depending upon the size of an election and political and practical constraints, reasonable threshold values for a particular election may, for example, be 3 of 5 trustees, 8 of 10 trustees, or 90 of 100 trustees". I definitely agree that if we were to use this method, we shouldn't set a 100% value for t, and something like 80-90% seems reasonable. The best part, as you noticed, is that if any trustees try to sabotage the process, there will be a clear evidence of this on-chain, so we could enforce good behavior off-chain by having serious repercussions for misbehaving parties (this would be especially true if ANOs serve as the trustees, which is how I imagined this initially).
Yes this is the nice part of the protocol! I like it.

Happy to continue this discussion ;)
 
Secured
#16
If my understanding of the ring signature process is correct, the reveal entry enables anyone to know the content of each ballot. Therefore, you could analyse individual votes and their timing to try to figure out who voted what. It would be a simple guess, not a certitude but still.
I guess this could be more or less obfuscated by using a daemon and set a random time setting before recording the entries.
OK, I see what you mean. Yes, you are right that using the timestamp of the vote together with the revealed contents of the cast ballot, one could make a guess about who is behind the vote. I'm inclined to say that in order for this to work, we need a very special type of vote where there are a lot of voting options and they are very dividing (i.e. a lot of parties disagree, there is little consensus) and in addition to this a long public discussion where voting parties expressed their opinions prior to voting has taken place. The only thing that fits this description in our processes thus far is grant ranking IMO.

As you pointed out above, this could be further remedied by having a tool for casting votes at a randomized time during a given day. However, this would make it a bit more inconvenient for people casting votes, as this means they would have to run some software on their OS, instead of relying on a web UI.

Overall, I wouldn't be too worried about this side-channel attack, though, especially with increasing number of standing parties.

When you mention "the relevant private keys of the participant" this is an equivalent procedure for you to "send xij among Zp secretly to party Pj (e.g. by encrypting with Pj's public key and recording the entries on-chain)" mentioned inthe document? Just to be sure we are speaking of the same step.
I understand what you mean. I just don't know how secure or hackable a daemon is. My intial feeling is that having a software monitoring the chain and accessing private keys of other participants is a perfect target for a hacker. But I must certainly miss something. Let me know in this case. Happy to learn :)
The daemon would have access to the private key(s), which represent the digital identity of the trustee (I really need a more trustless word for this :D). Those private key(s) will be used by the daemon, while monitoring the special chain(s) associated with the vote and looking, e.g. for shares encrypted with the corresponding public key. Of course, there is a risk of the daemons getting hacked, but I'm not too worried about this either. If you consider the factomd instances running on the Authority Nodes, it's basically the same setup, as they also have access to very sensitive keying material. Provided that the daemon is properly designed and implemented and the machine on which it is running is properly secured, IMO there is no risk of this sensitive information getting leaked or extracted by an adversary.

In fact, I would argue that a setup with a daemon monitoring a bunch of chains and having access to sensitive information on the machine where it's running, is one of the great benefits of the Factom protocol when designing Dapps, compared to other blockchains. It's much better understood how to secure a server than how to write a secure (and very difficult to update in case a vulnerability is found) smart contract executing on-chain ;).

That said, if we adopt the above voting process for on-chain governance, the daemon should, of course, undergo considerable scrutiny and IMO an official security audit.
 
Last edited: