Stratumn.com

Specification and Governance for Anonymous, Publicly Verifiable Boardroom Voting

In the previous post we described the model of a protocol of anonymous voting; this article is dedicated to its implementation on Stratumn Chainscript. We’re going to gradually design the protocol; we start from the simplest two-state version, then introduce authentication, registration, delegation, and end up discussing the model of governance. We try to stick to Occam’s razor principle, and add features only after justifying their necessity.

Two-phase Protocol

We will describe the protocol as a state diagram, executed by a state machine. The state machine can be implemented either as a centralised service run on a server, or as decentralised blockchain logic.

Let’s take the simplest case — a non-anonymous voting protocol. It has only two states: idle and voting:

  • In the Idle state nothing is happening,
  • Voting indicates there’s a voting round currently underway.

The protocol begins in the Idle state, in which anyone can propose an election by sending a Propose message. Upon reception, the system enters the Voting state, and stays there until all participants vote, or the timeout period has elapsed. Participants vote through Vote messages.

In Chainscript, the Propose message is represented as a JSON object: 1:

{
  "state": {    
    "choiceFunction": "plurality",
    "subject": "2017 board elections",
    "options": [
      "Dave",
      "Edith",
      "Fiona"
    ],
    "votingDuration": 86400
  },
  "meta": {
    "action": "propose",
    "stateHash": "8900BF68BE12E72FD37C6F524373E986F9DD5C4444654226A6BA9C09657A83BB",
    "prevLinkHash": "AE2011F908320F74D94FEE67163E564C2B22634585B940E4883D9AB7A1D285BA"
  }
}

The message contains two parts, state and meta. According to the specification, state is the actual payload of the message, and meta puts the message in the context of a segment chain. Throughout our examples, meta will contain the following fields:

  • action, the name of the message
  • stateHash, the SHA-256 hash of serialised state JSON object
  • prevLinkHash, the SHA-256 hash of some existing message, i.e. its state and meta objects all together.
  • signatures, not present in Propose message

As Chainscript does not impose any requirements on the structure of state, it can be an arbitrary JSON object. In particular, Propose’s state consists of:

  • subject, the title/question of the voting being proposed,
  • options, the list of available options,
  • choiceFunction, the algorithm to use to come up with the voting outcome,
  • votingDuration, time in seconds to let participants vote before an automated Timeout is triggered.

Note that the sender is not specified — it doesn’t matter whom the message comes from, its content is valuable by itself.

The Propose message makes the system enter the Voting state, when it starts accepting Vote messages of the format:

{
  "state": {    
    "selectedOption": "Dave"
  },
  "meta": {
    "action": "vote",
    "stateHash": "7C900313698C4EE7E6E8C2A718B21A9D707B2A770D8BD5FBC2E8DDC5F4946543",
    "prevLinkHash": "6E79EC01EE53CF1F0D12DF1315CCA0A39FD63E957810921FCE27F81F7E2EBAC1"
  }
}

The state of this Vote message contains only one field — selectedOption.

Improvements of the Two-Phase protocol

Analyze our implementation’s satisfaction of our initial criteria, we find the following:

Verifiable Yes Votes are plaintext and easy to count
Anonymous Yes No information about the voter is recorded in the message
Franchise No Impossible to determine if vote was cast by an eligible voter

The system is verifiable and anonymous but not franchise-full. Franchise, as defined in our last post, is the guarantee that each participant should have the opportunity to vote exactly the number of times they deserve. In this first protocol attempt, Anyone can generate an arbitrary amount of Vote messages.

In order to solve the issue, we’ll allow only one message per participant, and ensure authenticity with digital signatures. The change will only affect the Vote message:

{
  "state": {    
    "selectedOption": "Dave",
  },
  "meta": {
    "action": "vote",
    "stateHash": "7C900313698C4EE7E6E8C2A718B21A9D707B2A770D8BD5FBC2E8DDC5F4946543",
    "prevLinkHash": "6E79EC01EE53CF1F0D12DF1315CCA0A39FD63E957810921FCE27F81F7E2EBAC1",
    "signatures": [
      {    
        "publicKey": "2844FA9AE863429D405ACA73643FA2377E1359BF0ADEB14A24983EC89F0D1AC9",
        "signature": "B9C02609E758298C3F9761CCD3ABB988160D8FF8050CEB028FBA3AA58BF30CFF"
      }
    ]
  }
}

Message validation logic now includes a digital signature verification algorithm, which accepts selectedOption as message, publicKey and signature and returns boolean true/false. 2

In order to fully verify the authenticity of a message, digital signature verification is not enough; we need also to ensure that the public key itself is valid. For the moment we’ll assume that the PKI problem has been already solved: each voter has his/her public key, everyone knows the keys of everyone else, and the list of keys is static, i.e. the existing voters will forever remain voters, and no new voters can join the network. These conditions are quite constraining, and we'll come back to them later, in the section on governance.

Hidden Who and Registration state

The modified version satisfies our desire for franchise by sacrificing the anonymity of our voters. By authenticating their messages, the participants disclose their identities, and thereby, their preferences. Our goal now is to unlink voters’ identities from their preferences, while still being able to correctly count the votes and disallow double voting. The actual unlinking should happen in a separate state, which we call Registration.

In the previous article we described two ways of anonymization: hidden who and hidden what. We’ve selected to implement the hidden who in the present one. For a more detailed comparison, wait for our next article, comparing these two zero-knowledge protocols.

Hidden who assumes that the votes can be easily counted — the messages take the form of “somebody has voted for the option A”, are publicly legible. The protocol also ensures that there could be only one somebody per participant, and there’s no feasible way to link participants and their vote messages. We say that each participant creates her shadow identity (or just shadow), and then uses it to cast their vote(s).

Each participant creates her shadow identity in the Registration state by sending a specific Register message:

{
  "state": {
    "shadowPublicKey": "22A8EFA42ACD3E16A77D4B420048CFB662B64EF45F79E955105702F5607484E4",
    "proof": "DF383BD03D3B55D1ED5DC76CCE5F8CD6003E1A51B31E98B3693226F92BB88F69",
  },
  "meta": {
    "action": "register",
    "stateHash": "F368CBE037EA41804401F2BADA1944C7E4072034A87FFC1BB18673DFBEF10D25",
    "prevLinkHash": "B57E625206F1FFEB7A7264EFA9B884EF41BB65965535CC8834DA686E81CF1EC0"
  }
}

It carries the newly created shadowPublicKey and the (zero-knowledge) proof that the key is correctly computed. Note, that in contrast to key generation, key computation uses a deterministic algorithm. More precisely, shadowPublicKey is the public key, derived from shadowPrivateKey, which itself is the SHA-256 hash of voter’s private key and current voting round. 3 That means that any participant can deterministically compute a private/public key pair for a shadow identity within a voting round.

Being protected by the one-way hash function, the shadow’s identity public key reveals no information about its creator.

However, if shadowPublicKey cannot be linked to a voter, how can the protocol ensure it has been derived by one of the voters? The answer lies in the domain of Verifiable Computation, a field of cryptography that studies how to verify computations without reproducing them.

The shadowPublicKey is derived from voter’s privateKey and some public data, e.g. the voting round. To make sure that the key is derived correctly, one can reproduce the derivation, which is only possible if the privateKey is known. Since private keys are only known to their holders, nobody else should be able to derive a voter’s shadowPublicKey. However, we still need to be able to verify if the computation is correct, even though we don’t know all of its inputs. This is made possible by introducing another data structure in our protocol, we call it proof.

In general, there are two ways of verifying if the outcome of some computation is correct:4

  1. Directly by taking all the inputs and feeding them into the algorithm that corresponds to the computation, and comparing the obtained outcome with the one to be verified.
  2. Indirectly by feeding the proof of correct computation, part of the inputs, and the output into the algorithm of proof verification. The algorithm outputs the binary true or false, indicating whether the computation is correct or not.

The key thing is that, in addition to the algorithm of proof verification, there’s an algorithm of proof construction. The algorithm takes all the inputs of mentioned computation and produces the proof. The mathematics behind both algorithms guarantee that the verification returns true if only if it the proof is produced by an authentic construction algorithm which got all the inputs of the computation. In our case, the proof is produced by the voter who creates a shadow identity, and can be verified by everyone else.

Proxy Voting and Delegation

Delegation is the ability to delegate one’s voting rights to some other legitimate voter, known as a proxy.

In our implementation the actual votes are produced by shadow identities, i.e. by those who know their shadow private keys. The keys are used to put signatures on the selected options. That means that anyone who knows a shadow private key can cast a vote.

By way of the shadow identity construction, the shadow private key is known only to the shadow’s constructor. However, nothing prevents the original constructor from sharing it with someone else. Such sharing allows voters to designate the proxies, and the sharing is referred to as delegation.

On the implementation side, delegation can be implemented through publishing the encrypted key directly in the Register message:

{
  "state": {
    "shadowPublicKey": "22A8EFA42ACD3E16A77D4B420048CFB662B64EF45F79E955105702F5607484E4",
    "proof": "DF383BD03D3B55D1ED5DC76CCE5F8CD6003E1A51B31E98B3693226F92BB88F69",
    "delegated": "2CA45B31D303863556445BD320E492C058EDF452727BCD8F6A304498A2B1687B"
  },
  "meta": {
    "action": "register",
    "stateHash": "F368CBE037EA41804401F2BADA1944C7E4072034A87FFC1BB18673DFBEF10D25",
    "prevLinkHash": "B57E625206F1FFEB7A7264EFA9B884EF41BB65965535CC8834DA686E81CF1EC0"
  }
}

The new delegated field is actually the encryption of shadowPrivateKey with the proxy’s public key. The message is public, and upon reception, however, only someone with the private key for the encryption can decrypt it. Successful decryption indicates that the shadow’s key can be used to cast votes on behalf of the sender — thus allowing delegation.

Governance

The validity of zero-knowledge proofs is based on the knowledge of a valid private key. A private key is valid if its public counterpart is in the list of known public keys. We mentioned earlier that we assume that everyone has the same list, and it never changes. Now we’re going to relax the second constraint and introduce a mechanism for dynamic membership.

Like any system, our protocol should be able to evolve. We’ve already specified some flexibility and extensibility of the protocol in the social choice function. A social choice function receives multiple ordered preference lists, and outputs a single list that should reflect the collective opinion. While most democracies use majority-rule or plurality as their social function, many others exist, such as instant-runoff, approval, and rank-order.

Just as the social choice function can be specified in the propose message, so can the list of participants. Both choices would apply to that entire voting round.

We allow these variables to be changed between voting rounds. How the change occurs and who controls it is an instance of a governance problem. The actual implementation depends on the architecture of the system, its degree of decentralisation, so we will only focus on the theoretical model. The change occurs via a specific Configure message, which alters the Idle state. The message essentially lists the (new) rules of the system, which are valid under the existing (old) rules.

For example, if a new participant wants to join the system, his/her membership has to be confirmed by all existing participants. 5 Therefore, if Alice and Bob want Charlie to join, the Configure message would contain Charlie’s public key signed by Alice and Bob. In addition to Charlie’s membership, Alice and Bob may decide to include a new social choice function — majority-rule. The Configure message would then look like this:

{
  "state": {
    "participants": [
      {
        "pubKey": "C2E8FAE871A8D8DC1DBCBDAF6F60DF150A780D53CF76FD461C2F98D56D770607",
        "name": "Charlie",
        "action": "add"
      }
    ],
    "choiceFunctions": [
      {
        "name": "majority",
        "codeHash": "A6F2553F5AE8E7E70E9ABAD193BEE0612D61F7A5523806AB1A28559CB456772A",
        "action": "add"
      }
    ]
  },
  "meta": {
    "action": "configure",
    "stateHash": "CD16C3B77A32CC6ACF159048FC8DD171FDD9CCACD8824DC70D48267CBDEB2FC0",
    "prevLinkHash": "5E5DCAFBCE14B4D5BCE5D038278F5B55980C87BABEBD36EC53F23014C08BBDDF",
    "signatures": [
      {
        "publicKey": "A673B58A805FA3AD1F5BE14D30A116BD548A4AA1F1F6C0FF87D6C5A6CB7ED501",
        "signature": "7BE59AB966F9D208ABBFE84F84B87AED35928326F258765B1B6DFD6AD2EE7A32"
      },
      {
        "publicKey": "B588AE9D31202A9DDC84E0D9C0EDB332EE3BCC24C947491CF080A83AA433B703",
        "signature": "0937A82E3DB13E67607599002573F39862108A70E704B02AD33893FE1064EA1A"
      },
    ]
  }
}

Note that the meta section gains an additional field — signatures. It contains Alice’s and Bob’s public keys and their signatures of stateHash. The message is self-verifiable if its context (previous message and Alice’s and Bob’s keys) is given.

The participants and choiceFunctions lists indicate the changes to be made in their corresponding protocol variables. The new social choice function, majority-rule, is referenced by its hash, leaving it is up to every participant to download the code, verify its hash and run it when appropriate.

The actual process of constructing the Configure message and getting multiple signatures can be quite complicated, and this voting protocol does not specify how it should be done. Once a valid Configure message appears in the system, the system changes its rules accordingly.

Trust Model

The outcome of a voting system is an ordered list of preferences, resulting from the application of the social choice function on individual voters’ preferences. To be valuable, the outcome should be trusted. The outcome can only be trusted if trust is preserved through the entire chain of the protocol:

No system or network is possible without a traditional human agreement. It is and will always be the seed of any human process. However, when it comes to the growth and scaleability, technology is the key. Stratumn’s Indigo Framework goes one step further and provides the technologies that let networks grow without compromising trust and privacy. Networks are only made possible on the foundation of mutual agreement among all its participants; governance is key here! Our research shows the possibility of building networks where privacy and inclusivity work together harmoniously.

  1. We omit some technical parts, and present only the segment’s

    undefined data structure

  2. As an example, see

    undefined in NaCl library

  3. For better security public nonce has to be added, but we omit it for simplicity

  4. To lean more about proof systems, check out our article Beyond Decentralization

  5. How many confirmations a new participant has to obtain could be one of the variables of the system