SYSTEMS AND METHODS FOR COMMUNICATION, STORAGE AND PROCESSING OF DATA PROVIDED BY AN ENTITY OVER A BLOCKCHAIN NETWORK

Abstract

A computer-implemented method of making a decision on a blockchain is provided. The method comprises providing a blockchain voting commitment transaction (2) redeemable by means of a first signature (σ(A.sub.m), σ(B.sub.m)) associated with a selection (A, B) and a second signature (σ(A), σ(B)) associated with the selection, providing each of a plurality of participants (U.sub.i) with at least one share (k.sub.A,i, k.sub.B,.sub.i) of at least one respective secret value (k.sub.A, k.sub.B) wherein a threshold number of shares is required in order to execute said second signature, and submitting the blockchain voting commitment transaction (2) to the blockchain.

Claims

1. A computer-implemented method of making a decision on a blockchain, the method comprising: providing a first blockchain transaction having an output redeemable by means of a first signature associated with a selection of a candidate by a plurality of participants and a second signature associated with the selection, wherein the first signature is a signature by said selected candidate; providing each of said plurality of participants with at least one share of at least one respective secret value wherein a threshold number of shares is required in order to produce said second signature; and submitting the first blockchain transaction to the blockchain.

2. The method of claim 1, wherein at least one participant adds to the first blockchain transaction at least one signed input representative of a cryptographic asset.

3. The method of claim 2, further comprising the step of providing a second blockchain transaction redeemable, upon satisfaction of a locktime condition, to return at least a portion of the cryptographic asset to at least one participant.

4. The method of claim 1, wherein the first blockchain transaction comprises an m-of-n multisignature redeem script, and wherein at least one share is added to the redeem script.

5. The method of claim 4, wherein at least one share is encrypted with a first public key of at least one decision.

6. The method of claim 5, further comprising the step of combining at least one share with identification data identifying a selection prior to encryption with the first public key.

7. The method of claim 6, wherein the combination comprises concatenation of the at least one share and the identification data.

8. The method of claim 1, wherein the step of providing the shares to the participants comprises at least one of: (i) a dealer entity providing the shares to the participants; and (ii) the participants generating the shares among themselves.

9. The method of claim 1, comprising the step of obscuring which participant provides which share prior to submission of the first blockchain transaction to the blockchain.

10. The method of claim 1, further comprising the step of providing a third blockchain transaction arranged to redeem the first blockchain transaction.

11. The method of claim 1, further comprising the step of validating at least one share using at least one second public key.

12. The method of claim 11, wherein the plurality of participants collaborate in combining at least one subset of shares to determine at least one said second public key.

13. A computer-implemented system comprising: a processor; and memory including executable instructions that, as a result of execution by the processor, causes the system to perform any embodiment of the computer-implemented method as claimed in claim 1.

14. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform an embodiment of the method as claimed in claim 1.

Description

[0055] These and other aspects of the present invention will be apparent from and elucidated with reference to, the embodiment described herein. An embodiment of the present invention will now be described, by way of example only, and with reference to the accompanying drawings, in which:

[0056] FIG. 1 illustrates a schematic showing the interaction of three transactions of the present invention;

[0057] FIG. 2 is a table showing the relationship between a number of voters, a threshold number of votes required for a selection to be determined a winner, and a degree of a polynomial in accordance with the invention;

[0058] FIG. 3 shows a flow chart illustrating the present invention;

[0059] FIG. 4 shows a voting commitment transaction;

[0060] FIG. 5 shows two winner payment transactions;

[0061] FIG. 6 shows a refund transaction; and

[0062] FIG. 7 is a schematic diagram illustrates a computing environment in which various embodiments can be implemented.

[0063] The present application describes a system of Threshold Secret Share Voting (TSSV), which is a system where a set of voters is asked to choose between a pair of candidates where the winning candidate receives x BTC committed by each voter. The winning candidate must receive both a majority of votes and a number of votes past a specified threshold. The TSSV protocol utilises the distribution of private key shares, and is designed such that any bitcoins committed are recoverable if one or more participants act maliciously or do not follow protocol expectations.

[0064] The abbreviation “BTC” may be used herein as a shorthand for any variation of the Bitcoin protocol. It should not be interpreted as being restricted to or indicative of any one particular Bitcoin-related protocol.

Secret Sharing

[0065] A threshold cryptosystem is defined by (t ; n) - threshold, where n is the number of parties and t + 1 is the minimal number of parties required to reconstruct a secret. Secret Sharing schemes are examples of threshold cryptosystems, whereby a secret k is divided among n players, such that at least t + 1 participants are required to collaborate in order to reconstruct k. The knowledge of any t pieces of the secret k leaves the latter undetermined.

[0066] Shamir’s secret sharing (or SSS) is based on polynomial interpolation and without loss of generality the secret is assumed to be an element of a finite field F. The scheme comprises a dealer (dealerless versions also exist), a set of n participants U.sub.1, ..., U.sub.n and an access structure A, i.e. the groups of players able to reconstruct the secret. This is described in greater detail in Shamir, A. (1979) “How to share a secret”, Communications of the ACM, 22(11), 612-613.

[0067] For Shamir’s solution, an arbitrary random secret is stored as f(0) in a t degree polynomial f (x) and only player i can calculate its share f (x.sub.i). If t + 1 out of n players collaborate, they can reconstruct any point on f (x), with their shares (of the key k) k.sub.1, k.sub.2, ..., k.sub.n which correspond to f (x.sub.1), f (x.sub.2), ..., f (x.sub.n) using Lagrange Polynomial Interpolation.

[0068] Using the Lagrange Polynomial Interpolation, a function f (x) with degree t can be reconstructed with t + 1 points

[00001]$p=\left\{\left(x_1,f\left(x_1\right)\right),\left(x_2,f\left(x_2\right)\right),\mathrm{...},\left(x_{t+1},f\left(x_{t+1}\right)\right)\right\}$

[00002]$f\left(x\right)={\displaystyle \underset{i\in p}{.Math.}f\left(x_i\right)}{\displaystyle \underset{j\in p,j\in i}{.Math.}\frac{x-x_i}{x_i-x_j}={\displaystyle \underset{i\in p}{.Math.}f\left(x_i\right)}}{b}_{i,p}\left(x\right)$

where

[00003]$b_{i,p}\left(x\right)={\displaystyle \underset{j\in p,j\in i}{.Math.}\frac{x-x_i}{x_i-x_j}}$

Note that b.sub.i,p (x.sub.i) = 1 and b.sub.i,p (x.sub.j) = 0.

[0069] In the presence of a dealer the dealer simply selects a secret α.sub.o = k, assumed to be an element of the finite field F of size p (p prime), and randomly pick t — 1 positive integers a.sub.1, ..., a.sub.t-1, which represent the coefficient of the polynomial f (x) = a.sub.o + a.sub.1x + a.sub.2x.sup.2+... The dealer then computes n points (x.sub.i, f (x.sub.i))belonging to the polynomial and distribute it to the participants.

[0070] In the dealerless shares distribution phase: [0071] 1. Each player U.sub.i is assigned x.sub.i which is known by everyone. Each x.sub.i has to be unique. [0072] 2. Each player U.sub.i generates a random polynomial f.sub.i(x) with degree t. [0073] 3. Each player U.sub.i secretly sends (encrypted with the recipients’ public key) every other player their respective point on the polynomial, f.sub.i(x.sub.j)mod n. [0074] 4. Each player U.sub.i sums all their received f.sub.1(x.sub.i), f.sub.2(x.sub.i), ... f.sub.p (x.sub.i) (all mod n, where n is the order of the group generated by the point G on the elliptic curve) to form

[00004]$k_i=f\left(x_i\right)modn$

which is a share on the polynomial f (x) mod n.

[0075] An important element of the threshold signature calculations is the determination of k × G where k is the secret key and G is a point on the Elliptic Curve.

[0076] If f(x) is a t-degree polynomial, secret k can be interpolated by k = Σ.sub.i∈π b.sub.i,πk.sub.i where π is a size t + 1 subset of shares k.sub.a, k.sub.b, ..., k.sub.t, k.sub.t+1 and b is an interpolating factor. π is a group of t + 1 players collaborating to calculate k × G without revealing their share k.sub.i. k is the x = 0 point on a t-degree polynomial [0077] Each player U.sub.i calculates a part b.sub.i,πk.sub.i × G [0078] All players in π add their part together (reconstructing the secret k via Lagrange interpolation) giving:

[0079] This process of calculating Q = kG is referred to as Secret Share Joining.

Public Verifiable Secret Sharing Schemes

[0080] In the TSSV protocol it is desirable that voters be able to verify that they are given correct secret shares. Indeed, if inconsistent shares are distributed among the players, the incorrect share/votes of the voters would fail to contribute to the voter’s preferred candidate. For the shares verification we will employ the Publicly Verifiable Secret Sharing scheme (PVSS) which allows voters to verify their own shares as well as the shares of the other voters. This is described in greater detail in Stadler, M. (1996, May), “Publicly verifiable secret sharing” - International Conference on the Theory and Applications of Cryptographic Techniques (pp. 190-199), Springer Berlin Heidelberg.

[0081] In a PVSS scheme, each participant U.sub.i has a decryption function D.sub.i, which is able to access the information encrypted with the corresponding public encryption function E.sub.i. In this way, the dealer can use the public encryption function to distribute the shares and publish them in this form

[00006]$K_i=E_i\left(k_i\right),i=1,\mathrm{...},n.$

[0082] The encrypted shares can be, hence, publicly verified by any interested individual as we shall detail below. The participants can, not only verify their own shares, but anybody can verify that the participants received correct shares, i.e. whether the dealer was honest or not.

[0083] The main steps of the protocol are: [0084] 1- Secret sharing: the dealer runs an algorithm Share(k) = (k.sub.1, ..., k.sub.n) to compute the shares and distribute them among the participants. [0085] 2- Reconstruction: participants can reconstruct the secret by running the algorithm Recover, such that Recover ({D.sub.i(K.sub.i) |i ∈ A}) = k. [0086] 3- Verification: an algorithm PubVerify is used to validate the encrypted shares. If we run the algorithm PubVerify({K.sub.i|i ∈ A}) = 1 .fwdarw. Recover ({D.sub.i(K.sub.i) |i ∈ A}) = u and u = k then the dealer is honest and the shares are consistent.

[0087] The PVSS scheme can be interactive or non-interactive depending on necessity in the recovery phase.

De-Linking Outputs From Inputs in Bitcoin Transaction

[0088] The design of the voting protocol is such that the transaction that pays the winning candidate also contains the votes of the individual voters. In order for participants in the voting protocol, the candidates, or any external party, not to know the vote (and/or its encrypted value) of any another participant, it is important to incorporate a solution allowing each participant to contribute their encrypted vote without any other participant being able to link this encrypted value to its voter source.

[0089] This requirement is similar to that of the popular Bitcoin coin mixing solution CoinJoin, which is described in greater detail at Maxwell, G. (2013, August) - “CoinJoin: Bitcoin privacy for the real world” - Post on Bitcoin Forum. http://tinyurl.com/gn6kmx4. In CoinJoin each of a set of participants contribute and represent one of the inputs of a Bitcoin transaction; this transaction contains multiple outputs where each of the output addresses is provided by participants of the inputs. In order to strengthen the anonymity of the coin mixing process it is important to delink the input participant from their output address. To address this issue, a variety of shuffling solutions have been developed where participants may provide their output addresses without any other participant or external adversary being able to associate a participant to a specific output address.

[0090] Shuffling solutions include CoinShuffle (described in greater detail at Ruffing, T., Moreno-Sanchez, P., & Kate, A. (2014, September), “CoinShuffle: Practical decentralized coin mixing for Bitcoin” - European Symposium on Research in Computer Security (pp. 345-364), Springer International Publishing), CoinShuffle++ (described in greater detail at Ruffing, T., Moreno-Sanchez, P., & Kate, A. (2016) - “P2P mixing and unlinkable Bitcoin transactions” NDSS’17. https://goo.gl/QrfMhp), and Circle Shuffle.

Threshold Secret Share Voting

[0091] Referring to FIGS. 1 to 6, a method of making a decision on a blockchain is provided. The decision may be in the form of a desired course of action, a preferred candidate in an election, or any other decision. A number of participants, or voters, are provided with shares in respective secret values associated with one or more outcomes of the decision. The outcomes may be candidates up for election. The participants then vote for their preferred outcome, selection, or candidate, by providing to a first, or commitment, transaction 2 an input 4 containing a share associated with that outcome. The commitment transaction 2 (see FIG. 4) is arranged to be redeemable only upon provision of both a first signature (6a, 6b) associated with one of the outcomes, and a second signature (8a, 8b) associated with that outcome. In FIGS. 4 to 6, a signature for public key X is denoted σ(X). Upon provision of at least a threshold number of shares of a secret value, enough information is available to execute the second signature (8a, 8b), and therefore to satisfy the requirements of the commitment transaction 2 and reveal the outcome and/or enact the decision.

[0092] For the Threshold Secret Share Voting (TSSV) protocol one imagines a scenario where a set of participants {U.sub.i} have a choice of voting for one or more selections, or candidates. In this example, there are two candidates designated A and B. Each candidate has a main private-public key pair ((PrivA.sub.M, PubA.sub.M) and (PrivB.sub.M, PubB.sub.M)) where the public keys are made available to all voters. Each voter has one vote and a winning candidate is the candidate with: [0093] the most votes, [0094] AND enough votes past a specified threshold.

[0095] As an example, if there are to be 9 participants (voters) then the winning candidate can be asked to receive at least 5 votes.

[0096] In combination with their vote, voters are asked to commit to a certain amount of funds (e.g. bitcoins) alongside their vote. The accumulated committed funds from all voters will be given to the winning candidate. These funds may be seen as, or act as, a reward to the winner, or a disincentive for frivolous or malicious participation in the voting process.

[0097] The TSSV protocol uses three transactions. These transactions are labelled the Vote Commitment Transaction 2 (FIG. 4), Winners Payment (or Redemption) Transaction 10 (FIG. 5), and the Refund Transaction 12 (FIG. 6). These transactions have the following responsibilities.

[0098] Vote Commitment Transaction: The Vote Commitment Transaction (VCT) 2 is the transaction which contains both the bitcoin commitment and the vote commitment of each voter. For the proposed TSSV design, this transaction 2 comprises inputs 4 from the entire set of voters, though not all voters are required to provide votes. The VCT 2 records all user votes as well as pools the bitcoin commitments at one output 14. These votes are encrypted.

[0099] Refund Transaction: The Refund Transaction (RT) 12 is a failsafe measure for voters to recover their committed funds if a candidate is unable to collect the accumulated bitcoins of the voters before a specified time. The RT 12 is created and signed after users have voted and the VCT 2 has been created (but not submitted).

[0100] Winners Payment Transaction: The Winners Payment Transaction (WPT) 10, or redemption transaction, is the transaction that pays a winning candidate the accumulated bitcoins. The winning candidate will be the only person, candidate or otherwise, who would be able to collect the pooled bitcoins. FIG. 5 shows two possible redemption transactions 10a, 10b: (a) shows the redemption transaction 10a in the event that candidate A wins, and (b) shows the redemption transaction 10b in the event that candidate B wins.

[0101] A visual representation of the interplay between these three transactions 2, 10, 12 and the pooled bitcoins is shown in FIG. 1.

[0102] The Voting Commitment Transaction (VCT) 2 is the transaction that contains the user votes. Of the two commitments (vote and bitcoins) a voter must make for the VCT, the process of making the BTC funds is the one most easily understood and the one best facilitated by the Bitcoin protocol.

[0103] In the case of the bitcoin commitment, each user utilises the unspent BTC at a specific address they control/own and includes this as an input 4 of the commitment transaction 2, and signs their input 4. The voter’s input 4 in the commitment transaction 2 is only signed by the voter provided that the voter is satisfied with the other available details of the commitment transaction 2. The refund transaction 12 should also have been signed by all relevant parties. Each user is expected to commit the same amount (xBTC) of bitcoins to their vote, though this is not essential.

[0104] In the case of the ‘vote commitment’, a vote v.sub.i by a voter U.sub.i for a candidate B in the context of the TSSV protocol is expressed as the concatenation of: a secret share k.sub.B,i of a key k.sub.B given to U.sub.i; and an identification value for candidate B. The vote may be expressed in the following manner: v.sub.i = k.sub.B,i|| IDCandidateB where k.sub.B,i is the share held by voter U.sub.i of the key k.sub.B and || represents concatenation.

[0105] The key share component of v.sub.i will play a part in allowing the candidate B to claim the accumulated committed funds of all voters if candidate B is able to garner sufficient votes. The vote v.sub.i is not necessarily embedded into the VCT 2 as it is; it is preferably first encrypted with the public key of the candidate the voter U.sub.i wants to vote for (Candidate B in this example). The encrypted vote can be represented as v̂.sub.i = Enc.sub.B(v.sub.i).

[0106] In the event that candidate B attempts to decrypt v̂.sub.l, the component IDCandidateB serves as an indicator to candidate B that they have done the decryption successfully. The bit size of IDCandidateB should be large enough that it is unlikely that an incorrect decryption (private) key will produce from the ciphertext v̂.sub.i the value string||IDCandidateB.

[0107] Given that Bitcoin transactions do not have fields dedicated to the storage of metadata, the success of the TSSV protocol is dependent on finding a suitable location for recording the votes of the participants. Given that the design of the protocol is such that all votes are represented in one commitment transaction (the VCT 2), this adds some restrictions on incorporating the set of vote commitments.

[0108] For the proposed design of the TSSV protocol, the votes are stored using Bitcoin’s script for an m-of-n multi-signature transaction. The m-of-n multi-signature script takes the following format: [0109] OP_0 Sig1 Sig2 ... NumSigs Pub1 Pub2 Pub3 Pub4 ... NumKeys OP_CHECKMULTSIG where the content in bold would be of the <scriptPubKey> and the content underlined is of the <scriptSig>. <scriptPubKey> is the ruleset that allows for a transaction output to be utilised. <scriptSig> is the content required that would satisfy <scriptPubKey>. NumSigs is the number of required signatures, NumKeys is the number of possible signatures, and PubX is the public key that corresponds to the signature SigX. While this script is intended for m-of-n signatures, the PubX elements of the redeem script may be appropriated for use as a store of metadata.

[0110] As an example, a 2-of-4 multi-signature script is shown where of the 4 data elements reserved for Public Keys two are utilised to store metadata. The script takes the following format: [0111] OP_0 SigA SigB OP_2 metal meta2 PubA PubB OP_4 OP_CHECKMULTSIG For our purposes, these metadata elements could be representative of the set of encrypted votes {v̂.sub.i: i ∈ [1, n]} of users.

[0112] As an example, a 1-of-7 multi-signature script is shown where, of the seven data elements reserved for Public Keys, five are utilised to store encrypted votes and two for genuine public keys. The script takes the following format: [0113] OP_0 SigB OP_1 v̂.sub.1 v̂.sub.2 v̂.sub.3 v̂.sub.4 v̂.sub.5 PubA PubB OP_7 OP_CHECKMULTSIG

[0114] For the current version of the Bitcoin protocol, the maximum number of public keys allowable in a multisig output is 15. For this reason, the maximum number of votes (voters) that the described m-of-n script may allow is thirteen (bearing in mind that two positions (of the 15) are reserved for the public keys of the candidates A or B). At least 2 public keys are attached to each candidate (e.g. Candidate A), a main public key and the collaboratively derived public key based on the k.sub.A,i key shares. However, importantly, multiple m-of-n multisig scripts can be utilised within one larger script. As an example, if-else conditions could be utilised within the script to determine which candidate gets paid. Each of the options within the script may have its own m-of-n segment within the script, leading to the inclusion of at least 26 possible votes. More elaborate scripts may be constructed to incorporate more votes, keeping in mind however, that the maximum size of the script is currently 10 kilobytes (as explained in more detail in Bitcoin Script Interpreter -https://github.com/bitcoin/bitcoin/blob/fcf646c9b08e7f846d6c99314f937ace50809d7a/src/scri pt/interpreter.cpp#L256) and that transaction costs are dependent on the size of the transaction.

[0115] The use of the public key elements of the m-of-n bitcoin script requires that consideration be given to the size restrictions placed on of a public key for the Bitcoin protocol. This is bearing in mind that that the public key is being appropriated for storing v̂.sub.i where v̂.sub.i is of the same bit length and is the encryption of v.sub.i = k.sub.B,i|| IDCandidateB.

[0116] It should be noted that for the TSSV protocol being proposed, the Bitcoin elliptic curve digital signature algorithm (ECDSA) signature (that is ultimately required for the winning candidate to claim their funds) requires a 256-bit private key (see, for example, Private Key https://en.bitcoin.it/wiki/Private_key). To reconstruct a 256-bit (32 bytes) private key requires that the key shares themselves also be 256 bits in length.

[0117] The Bitcoin protocol utilises Elliptic Curve (EC) (of 256 bit length) encryption where the public key kG is a point on the curve; each coordinate being of 256 bits. This is described in more detail at Franco, P., 2014. Understanding Bitcoin: Cryptography, engineering and economics. John Wiley & Sons. The Bitcoin protocol allows for representation of the EC public key as a compressed or uncompressed point. For the compressed point only the x-value (256 bits) of the EC point is stored, whereas for the uncompressed point both the x and y values are stored (each being of 256 bits).

[0118] The implication of this is that, if the uncompressed public key is utilised in the m-of-n script, there is enough storage space for the concatenation of a 256-bit key share and the candidate ID. The 256 bits of the EC point’s x-value may be used for the key share k.sub.B,i whereas the other 256 bits reserved for the y-value may be utilised to store the candidate ID.

[0119] In voting systems, it is usually desirable that a user’s vote not be traced to the voter. For the proposed TSSV protocol, if a voter simply adds their v̂.sub.i to the set/list of existing v̂.sub.is then another voter may, on its own or collaboratively, determine the voter’s v̂.sub.i. Consider the case where the first voter adds their v̂.sub.i to the list of votes. The second voter will easily be able to tell the (encrypted) vote already in the list is that of the first voter. While this only lets one know the ciphertext v̂.sub.i and not ν.sub.i itself, this puts a malicious voter/participant in a better position to link a voter to a v.sub.i.

[0120] More importantly, vote shuffling prevents the candidates (A or B) from linking a voter to a vote, given that the encryption of a vote is done with a public key of one of the two candidates. If there was no shuffling, a candidate with the aid of one or more voters, may be able to link a voter to a vote, given that a candidate can decrypt v̂.sub.i. It should also be noted that, given there being only two candidates in a TSSV protocol, a candidate not being able to decrypt a vote implies that the vote is for the other candidate.

[0121] For this reason, for the TSSV protocol, a shuffling solution is incorporated into the process of users providing their votes to the <scriptPubKey>. Examples of shuffling solutions are described above; any of which may be utilised in an instance of a TSSV protocol. The fundamental responsibility of a shuffling solution utilised for TSSV purposes is to allow for each voter to provide their (encrypted) vote without any other voter or non-voter being able to determine which (encrypted) vote originates from which voter.

[0122] Therefore the set of encrypted votes {v̂.sub.i, v̂.sub.2, ... , v̂.sub.n-1, v̂.sub.n,} may be created without any voter or candidate (or otherwise) knowing which element of the set originated from which voter.

[0123] The TSSV protocol is designed in such a way that only the successful candidate would be able to collect the pooled bitcoins. This restriction is facilitated by the threshold secret schemes where, for such schemes, t + 1 shares of a set of shares {k.sub.i: i ∈ [1, n]} may be used to determine a secret k. t is the degree of the polynomial used to calculate the secret key shares.

[0124] Each of the two candidates (A and B) is assigned a public key.

[00007]$PubA=k_{A}G$

[00008]$PubB=k_{B}G$

where G is the base point of the Elliptic Curve (EC) and kG is an example of EC ‘point-multiplication-by-scalar’. G is a base point on EC and k is a scalar value.

[0125] The values of k.sub.A and k.sub.B are unknown (by anyone, candidate or voter) at the earlier stages of the protocol. These k.sub.A and k.sub.B values can only be determined when users have submitted a sufficient number of votes for a particular candidate. These user votes contain a key share of k.sub.A or k.sub.B depending on the voter’s candidate of choice. The key shares of k.sub.A and k.sub.B are such that:

[00009]$k_A\equiv f\left(k_{A,1},k_{A,2},\mathrm{...},k_{A,n}\right)$

[00010]$k_B\equiv f\left(k_{B,1},k_{B,2},\mathrm{...},k_{B,n}\right)$

[0126] As an example, a voter’s vote commitment, if they choose to vote for candidate B, would be

[00011]$v_i=k_{B,i}\parallel IDCcandidateB$

[0127] The value k.sub.B,i is a key share of the key k.sub.B, a share that would have been previously distributed to voter U.sub.i.

[0128] The distribution of key-shares in theory can be dealer-based or dealer-less. In a dealer-based distribution, the dealer knows k.sub.A and k.sub.B and distributes the key shares of both k.sub.A and k.sub.B. A participant in possession of a share k.sub.B,i and a share k.sub.A,i may be considered as a legitimate participant. This dealer must not be any of the candidates and is instead a third party. If candidates A or B were dealers, either candidate could sign the output of the TSSV, collecting all the pooled funds despite not winning the necessary votes, given that the malicious candidate would have known all the secret keys. For the dealer-less implementation, each voter constructs their own key share. Voters collaborate using Secret Share Joining, as described above, to calculate the public keys PubA = k.sub.AG and PubB = k.sub.BG.

[0129] A PVSS scheme is utilised for candidates and voters to validate the key shares in light of PubA and PubB. Having a dealer distribute the key shares gives an appropriate authority control over the list of eligible voters; this is as the ownership of a key share can be seen as a certification of voting eligibility.

[0130] If candidate B is able to obtain sufficient votes (k.sub.B,i shares), candidate B will be able to construct the secret k.sub.B and utilise this k.sub.B in signing the output of the Voting Commitment Transaction 2 in order collect the pooled committed bitcoins.

[0131] The degree of the polynomial, for an implementation of Shamir’s Secret Sharing, must be chosen in light of the number of voters and the number of votes necessary for a candidate to win. The winning candidate must achieve the most votes and the number of votes the winning candidate receives must also be greater than a specified threshold. As an illustration, FIG. 2 shows the number of votes necessary for a candidate to win and the degree of the polynomial for varying amounts of voters. The minimum votes necessary for the winning candidate may be higher if a larger threshold is desired. As an example, a government referendum may require both a majority and at least 75% of the votes for a policy proposal to be accepted.

[0132] To collect the winnings, a winning candidate B needs to provide more than the signature 8b for PubB (FIG. 4). In addition to having being assigned the public key PubA/PubB for which the corresponding private keys are split, candidates A and B both respectively possess their own separate (main) public keys PubA.sub.m and PubB.sub.m. Candidate A knows the private key for PubA.sub.m and Candidate B knows the private key for PubB.sub.m.

[0133] The need for this extra public key is due to the fact that any set of t + 1 voters could theoretically collaborate, calculate k.sub.B, and steal the accumulated funds. This is due to the fact that there would not be the requirement for a signature 6b based on the extra public key - more so its private key (corresponding to public key) which would be only known to the candidate. For this reason, a signature 6b of the winning candidate for a public key pubB.sub.M is also necessary in order for the winning candidate (candidate B) to claim the accumulated funds.

[0134] With this in mind we consider the different ways, as per the bitcoin script, in which the pooled bitcoins can be claimed. The <scriptPubKey> of the Voting Commitment Transaction 2 includes consideration for three ways of collecting payment.

[0135] The first of these rulesets (‘ruleset’ can be interpreted as a Boolean sub-function (of the main <scriptPubKey> function) is represented in the <scriptPubKey> by the subscript [0136] OP_DUP OP_HASH160 <Hash(PubS)> OP_EQUALVERIFY OP_CHECKSIG

[0137] The term subscript here is used to describe a segment of a larger script. In this case, the larger script being referred to is the <scriptPubKey>. This script shows a basic way in which most bitcoin transaction outputs are protected; it simply requires the signature for the included public key. For the Vote Commitment Transaction (VCT) 2, this subscript controls the ability of users to obtain a refund of their committed bitcoins if the execution of the TSSV protocol does not go as planned, i.e. if there is no winning selection or if the winning selection does not redeem the vote commitment transaction. Successful submission of the Refund Transaction 12 to the blockchain depends on the <scriptSig> containing the signature for a public key PubS. This public key can either be a public key that one of the voters is able to sign or it could be public key based on a separate set of distributed key shares. For the latter option, obtaining the signature of PubS would be a collaborative effort between at least t + 1 voters to construct the private key and generating the signature. Note that: [0138] A copy of the signed refund transaction 12 is available to all voters prior to the VCT 2 being submitted to the blockchain. [0139] the Refund Transaction 12 includes an nLockTime value which prevents the submission of the Refund Transaction 12 to the blockchain unless a specified point in time (such as Unix time or block height) has passed. [0140] the Refund Transaction 12 returns to each user the bitcoins that user committed.

[0141] The second ruleset of these options of claiming pooled funds of the VCT 2 is one such that Candidate A is able to claim the pooled funds depending on Candidate A’s ability to produce two required signatures 6a, 8a (FIG. 4). The subscript (shown below) is a 2-of-15 multisig, i.e. it requires signatures that correspond with two public key fields found within a set of fifteen public key fields. There could be fewer than 15 fields if there are less than 13 voters. [0142] OP_2 <v̂.sub.1> <v̂.sub.2> ... <v̂.sub.12> <v̂.sub.13> <PubA> <PubA.sub.m> OP_15 OP_CHECKMULTSIG

[0143] This subscript serves dual purposes. The first of these responsibilities is to contain (at most 13 of) the encrypted votes and the second is to allow Candidate A to claim the pooled bitcoins if he is able to produce the respective signatures 8a, 6a of the public keys PubA and PubA.sub.m. PubA = k.sub.AG and the signature 8a of PubA is obtained using the secret values found within the v̂.sub.1 values in order to find k.sub.A. This of course depends on there being enough votes for Candidate A within the script. Each vote for candidate A has a key share k.sub.A,i and is encrypted with a public key of Candidate A (preferably PubA.sub.m). PubA.sub.m is a public key generated by Candidate A and therefore Candidate A should be able to produce the signature 6a for this (main) public key. The signature 6a of PubA.sub.m is Candidate A’s responsibility as it was Candidate A who would have generated PubA.sub.m, and would this be in possession of PubA.sub.m’s corresponding private key PrivA.sub.M.

[0144] The third ruleset is of similar content as the second, and is intended to contain additional votes as well as to grant or deny Candidate B the ability to claim the VCT funds based on the provision of at least two signatures. This is shown below [0145] OP_2 <v̂.sub.13> <v̂.sub.14> ... <v̂.sub.25> <v̂.sub.26> <PubB> <PubB.sub.m> OP_15 OP_CHECKMULTSIG

[0146] In this case, in the m-of-n subscript, there are once again at most 13 fields appropriated for votes/metadata while two fields are assigned for usage as legitimate public keys. The public keys which do in fact require signatures are PubB and PubB.sub.m. PubB = k.sub.BG is the public key which corresponds with the k.sub.B,i shares. At least t + 1 votes for candidate B being present in the m-of-n scripts for Candidate B would allow Candidate B to utilise the k.sub.B,i key shares to produce a signature 8b for PubB. Candidate B generated PubB.sub.m and therefore should be able to produce its signature 8a. Provision of both of these signatures 8a, 8b would allow Candidate B to collect pooled bitcoins of the Voting Commitment Transaction 2.

[0147] It should be noted that: [0148] It does not matter in which of the two m-of-n subscripts the encrypted votes are found; all v̂.sub.i are visible in the blockchain to both candidates, and both candidates can try to decrypt v̂.sub.i from either Candidate A or Candidate B’s m-of-n subscript, in an effort to retrieve key shares of the their public keys for which signatures are required. [0149] t + 1 is the threshold amount of votes that a candidate requires in order to win, where t is the degree of the polynomial used in a polynomial-based secret sharing mechanism. [0150] t would be chosen such that t + 1 is guaranteed to be the majority of votes where it is a choice between two candidates.

[0151] Referring to FIG. 3, a flowchart illustrating a process 300 embodying the present invention is shown. Initially, at step 302, a decision is made on the number of voters, n. Using the key sharing techniques described above, at step 304, n shares are created for a private key k.sub.A. Similarly, n shares are created for a key k.sub.B. These private keys correspond to public keys PubA and PubB respectively.

[0152] Each voter is then given a unique share k.sub.A,i of k.sub.A and a unique share of k.sub.B,.sub.i of k.sub.B at step 306. The voters then collaborate at step 308 using k.sub.A, i key shares to calculate PubA = k.sub.AG using secret share joining, and similarly collaborate using k.sub.B,i key shares to calculate PubB = k.sub.BG. PubA and PubB are then communicated at step 310 to all voters and candidates and a key share scheme is used to validate the key shares in light of PubA and PubB. The candidates A and B then each create separate main public keys PubA.sub.m and PubB.sub.m respectively at step 312.

[0153] At step 314, each voter votes by concatenating its secret share with the ID of its candidate of choice to provide

[00012]$v_i=k_{B,i}\parallel IDCcandidateB$

[0154] At step 316, each voter then encrypts its vote with the public key of its candidate of choice. For example, in the case of candidate B the encrypted vote is:

[00013]${\widehat{v}}_i=En{c}_B\left(v_i\right)$

[0155] Each voter contributes its vote to a list at step 318, this being done using a shuffling technique as described above so that there is no link to the user and the vote. The voter commitment transaction 2 is then created at step 320. This includes inputs from each voter. Each voter contributes an amount xBTC of Bitcoin.

[0156] At step 322, the output of the voter commitment transaction 2 of the value nxBTC, is governed by an m-of-n script from which pubkey elements are appropriated for their use as the stores of encrypted votes. This output script of the voter commitment transaction 2 allows for: [0157] a refund of xBTC to each voter [0158] candidate A to collect xBTC using signatures σ(A.sub.m) and σ(A) [0159] candidate B to collect nxBTC using signatures σ(B.sub.m) and σ(B)

[0160] The refund transaction 12 is then created at step 324, signed and a copy distributed to each voter. The voter commitment transaction 2 is then submitted to the blockchain.

[0161] At step 326, candidate B tries to decrypt all of the v̂.sub.i values. If the decryption process reveals candidate B’s ID as the latter segment of v.sub.i, then candidate B recognises the first segment of v.sub.i as a secret share k.sub.B,i. If candidate B receives enough votes (shares), he can sign the output. Candidate A carries out a substantially identical process to that carried out be candidate B.

[0162] Finally, if at step 328 neither candidate is able to claim their winnings prior to the nLockTime of the refund transaction 12, the refund transaction 12 is submitted, by any voter, and each voter’s committed funds are returned to the voter, minus transaction costs.

[0163] Turning now to FIG. 7, there is provided an illustrative, simplified block diagram of a computing device 2600 that may be used to practice at least one embodiment of the present disclosure. In various embodiments, the computing device 2600 may be used to implement any of the systems illustrated and described above. For example, the computing device 2600 may be configured for use as a data server, a web server, a portable computing device, a personal computer, or any electronic computing device. As shown in FIG. 7, the computing device 2600 may include one or more processors with one or more levels of cache memory and a memory controller (collectively labelled 2602) that can be configured to communicate with a storage subsystem 2606 that includes main memory 2608 and persistent storage 2610. The main memory 2608 can include dynamic random-access memory (DRAM) 2618 and read-only memory (ROM) 2620 as shown. The storage subsystem 2606 and the cache memory 2602 and may be used for storage of information, such as details associated with transactions and blocks as described in the present disclosure. The processor(s) 2602 may be utilized to provide the steps or functionality of any embodiment as described in the present disclosure.

[0164] The processor(s) 2602 can also communicate with one or more user interface input devices 2612, one or more user interface output devices 2614, and a network interface subsystem 2616.

[0165] A bus subsystem 2604 may provide a mechanism for enabling the various components and subsystems of computing device 2600 to communicate with each other as intended. Although the bus subsystem 2604 is shown schematically as a single bus, alternative embodiments of the bus subsystem may utilize multiple busses.

[0166] The network interface subsystem 2616 may provide an interface to other computing devices and networks. The network interface subsystem 2616 may serve as an interface for receiving data from, and transmitting data to, other systems from the computing device 2600. For example, the network interface subsystem 2616 may enable a data technician to connect the device to a network such that the data technician may be able to transmit data to the device and receive data from the device while in a remote location, such as a data centre.

[0167] The user interface input devices 2612 may include one or more user input devices such as a keyboard; pointing devices such as an integrated mouse, trackball, touchpad, or graphics tablet; a scanner; a barcode scanner; a touch screen incorporated into the display; audio input devices such as voice recognition systems, microphones; and other types of input devices. In general, use of the term “input device” is intended to include all possible types of devices and mechanisms for inputting information to the computing device 2600.

[0168] The one or more user interface output devices 2614 may include a display subsystem, a printer, or non-visual displays such as audio output devices, etc. The display subsystem may be a cathode ray tube (CRT), a flat-panel device such as a liquid crystal display (LCD), light emitting diode (LED) display, or a projection or other display device. In general, use of the term “output device” is intended to include all possible types of devices and mechanisms for outputting information from the computing device 2600. The one or more user interface output devices 2614 may be used, for example, to present user interfaces to facilitate user interaction with applications performing processes described and variations therein, when such interaction may be appropriate.

[0169] The storage subsystem 2606 may provide a computer-readable storage medium for storing the basic programming and data constructs that may provide the functionality of at least one embodiment of the present disclosure. The applications (programs, code modules, instructions), when executed by one or more processors, may provide the functionality of one or more embodiments of the present disclosure, and may be stored in the storage subsystem 2606. These application modules or instructions may be executed by the one or more processors 2602. The storage subsystem 2606 may additionally provide a repository for storing data used in accordance with the present disclosure. For example, the main memory 2608 and cache memory 2602 can provide volatile storage for program and data. The persistent storage 2610 can provide persistent (non-volatile) storage for program and data and may include flash memory, one or more solid state drives, one or more magnetic hard disk drives, one or more floppy disk drives with associated removable media, one or more optical drives (e.g. CD-ROM or DVD or Blue-Ray) drive with associated removable media, and other like storage media. Such program and data can include programs for carrying out the steps of one or more embodiments as described in the present disclosure as well as data associated with transactions and blocks as described in the present disclosure.

[0170] The computing device 2600 may be of various types, including a portable computer device, tablet computer, a workstation, or any other device described below. Additionally, the computing device 2600 may include another device that may be connected to the computing device 2600 through one or more ports (e.g., USB, a headphone jack, Lightning connector, etc.). The device that may be connected to the computing device 2600 may include a plurality of ports configured to accept fibre-optic connectors. Accordingly, this device may be configured to convert optical signals to electrical signals that may be transmitted through the port connecting the device to the computing device 2600 for processing. Due to the ever-changing nature of computers and networks, the description of the computing device 2600 depicted in FIG. 7 is intended only as a specific example for purposes of illustrating the preferred embodiment of the device. Many other configurations having more or fewer components than the system depicted in FIG. 7 are possible.

[0171] It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be capable of designing many alternative embodiments without departing from the scope of the invention as defined by the appended claims. In the claims, any reference signs placed in parentheses shall not be construed as limiting the claims. The word “comprising” and “comprises”, and the like, does not exclude the presence of elements or steps other than those listed in any claim or the specification as a whole. In the present specification, “comprises” means “includes or consists of” and “comprising” means “including or consisting of”. The singular reference of an element does not exclude the plural reference of such elements and vice-versa. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In a device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.