DISTRIBUTED NETWORK WITH BLINDED IDENTITIES

Abstract

According to an embodiment of a first aspect of the invention, there is a distributed network comprising a plurality of network nodes. Each of the plurality of network nodes is linked to a first node identity of a plurality of first node identities. Each of the plurality of first node identities comprises a first verification key of a public-key signature scheme. The distributed network is configured to perform a key shuffling step adapted to perform an unlinkable one-to-one mapping between the plurality of first node identities and a plurality of second node identities. Each of the plurality of second node identities comprises a second verification key of a public-key signature scheme. The distributed network is configured to perform a consensus protocol with a subset of the plurality of second node identities. Further aspects of the invention relate to a corresponding computer-implemented method, a network node and a computer program product.

Claims

1. A distributed network comprising a plurality of network nodes, wherein each of the plurality of network nodes is linked to a first node identity of a plurality of first node identities; each of the plurality of first node identities comprises a first verification key of a public-key signature scheme; the distributed network is configured to perform a key shuffling step adapted to perform an unlinkable one-to-one mapping between the plurality of first node identities and a plurality of second node identities, wherein each of the plurality of second node identities comprises a second verification key of a public-key signature scheme; and perform one or more steps of a consensus protocol with a subset of the plurality of second node identities.

2. A network according to claim 1, wherein the network is further configured to regularly repeat the key shuffling step.

3. A network according to claim 1, wherein the network is further configured to perform an identity revealing step adapted to reveal the mapping between the plurality of first node identities and the plurality of second node identities after performing the consensus protocol.

4. A network according to claim 1, wherein the network is further configured to perform a further key shuffling step adapted to perform an unlinkable one-to-one mapping between the plurality of second node identities and a plurality of third node identities, wherein each of the plurality of third node identities comprises a third verification key.

5. A network according to claim 1, wherein the network is a proof-of-stake blockchain network; the plurality of first node identities are permanent node identities; each of the plurality of permanent node identities comprises as first verification key a permanent verification key; the plurality of second node identities are a plurality of blinded node identities, wherein each of the plurality of blinded node identities comprises as second verification key a blinded verification key; and the network is configured to perform as consensus protocol a proof-of-stake consensus protocol on transactions to be written on the blockchain network with a subset of the plurality of blinded node identities.

6. A network according to claim 5, wherein the network is further configured to assign a network identity to each of the plurality of permanent node identities; and certify the network identity by the corresponding permanent node identity.

7. A network according to claim 6, wherein the network identity further comprises a Transport Layer Security “TLS” certificate and a network address.

8. A network according to claim 5, wherein the network is further configured to perform an unlinkable one-to-one mapping between the plurality of blinded node identities and a plurality of blinded network identities, wherein each of the plurality of blinded network identities comprises a network verification key and a network encryption key, in particular of a signature scheme and a public-key encryption scheme, respectively.

9. A network according to claim 5, wherein the network is further configured to perform an unlinkable one-to-one mapping between the plurality of permanent node identities and a plurality of blinded network identities, wherein each of the plurality of blinded network identities comprises a network verification key and a network encryption key, in particular of a signature scheme and a public-key encryption scheme, respectively.

10. A network according to claim 8, wherein the network is further configured to perform a gossip protocol to disseminate information between the network nodes; and assign the plurality of blinded network identities to a plurality of vertices of a gossip graph so that each vertex can look up a network verification key of its neighbours.

11. A network according to claim 10, wherein each vertex of the gossip graph is configured to encrypt its network address with the network encryption key of its neighbours; sign the encrypted network address with a network signature key corresponding to its network verification key; and provide the signed and encrypted network address to its neighbours.

12. A network according to claim 1, wherein each of the plurality of network nodes comprises a stake identity, the stake identity comprising a stake verification key of a public-key signature scheme; and the network is configured to certify the first node identities by the corresponding stake identities.

13. A network according to claim 1, wherein the network is further configured to elect members of a committee from the plurality of second node identities according to predefined election scheme; perform the consensus protocol with the elected members of the committee.

14. A network according to claim 13, wherein the elected members of the committee perform a distributed key generation protocol.

15. A network according to claim 1, wherein the plurality of second node identities are assigned to a plurality of shards.

16. A network according to claim 1, wherein the key shuffling step comprises electing, by the plurality of first node identities, a plurality of mixers as a subset of the first node identities, the plurality of mixers being arranged at a specified order; receiving, by each mixer, an input list comprising a plurality of verification keys; computing, by each mixer, an output list comprising a permutation and re-randomization of the input list, wherein the computing uses in particular a secret permutation and a secret re-randomization exponent; wherein the first mixer of the specified order receives as input list the first verification keys of the plurality of first node identities, in particular the permanent verification keys of the plurality of permanent node identities; each subsequent mixer receives as input list the output list of the previous mixer; and the output list of the last mixer of the specified order establishes the plurality of second node identities, in particular the plurality of blinded node identities.

17. A network according to claim 16, wherein the network is further configured to perform a further key-shuffling step, the further key shuffling step comprising electing, by the plurality of second node identities, a plurality of mixers as a subset of the second node identities, the plurality of mixers being arranged at a specified order; receiving, by each mixer, an input list comprising a plurality of verification keys; computing, by each mixer, an output list comprising a permutation and re-randomization of the input list, wherein the computing uses in particular a secret permutation and a secret re-randomization exponent; wherein the first mixer of the specified order receives as input list the first verification keys of the plurality of first node identities, in particular the permanent verification keys of the plurality of permanent node identities; each subsequent mixer receives as input list the output list of the previous mixer; and the output list of the last mixer of the specified order establishes the plurality of second node identities, in particular the plurality of blinded node identities.

18. A network according to claim 16, the key shuffling step further comprising computing, by each mixer, a zero-knowledge proof proving that the re-randomization and the permutation has been computed correctly; and adding, by each mixer, the zero-knowledge proof to the output list.

19. (canceled)

20. A network according to claim 1, wherein the key shuffling step uses a blind signature scheme.

21. A network according to claim 1, wherein the key shuffling step uses a Pointcheval-Sanders signature scheme.

22. A computer-implemented method for performing a consensus protocol in a distributed network comprising a plurality of network nodes, in particular in a proof-of-stake blockchain network, the method comprising linking each of the plurality of network nodes to a first node identity of a plurality of first node identities, wherein each of the plurality of first node identities comprises a first verification key; performing a key shuffling step comprising performing an unlinkable one-to-one mapping between the plurality of first node identities and a plurality of second node identities, wherein each of the plurality of second node identities comprises a second verification key; performing the consensus protocol, in particular the proof-of-stake consensus protocol, with a subset of the plurality of second node identities.

23-24. (canceled)

25. A computer program product for operating a distributed network, in particular a proof-of-stake blockchain network, the distributed network comprising a plurality of network nodes, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by one or more of the plurality of network nodes to cause the one or more of the plurality of network nodes to perform a method comprising linking each of the plurality of network nodes to a first node identity of a plurality of first node identities, wherein each of the plurality of first node identities comprises a first verification key; performing a key shuffling step comprising performing an unlinkable one-to-one mapping between the plurality of first node identities and a plurality of second node identities, wherein each of the plurality of second node identities comprises a second verification key; and performing the consensus protocol, in particular the proof-of-stake consensus protocol, with a subset of the plurality of second node identities.

26. (canceled)

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0086] The invention will be better understood and objects other than those set forth above will become apparent from the following detailed description thereof. Such description makes reference to the annexed drawings, wherein:

[0087] FIG. 1 shows an exemplary block diagram of a distributed network according to an embodiment of the invention;

[0088] FIG. 2 illustrates the creation of blocks in the distributed network according to an exemplary embodiment of the invention;

[0089] FIG. 3 shows a flow chart comprising method steps of a computer-implemented method for performing a consensus protocol in a distributed network;

[0090] FIG. 4 shows a node identity structure of network nodes of a network according to an embodiment of the invention;

[0091] FIG. 5 illustrates an exemplary example of a key shuffling step according to embodiments of the invention;

[0092] FIG. 6 shows a node identity structure of network nodes of a network according to another embodiment of the invention;

[0093] FIG. 7 shows a node identity structure of network nodes of a network according to an embodiment of the invention;

[0094] FIG. 8 shows a time diagram of the key shuffling and revealing steps according to another embodiment of the invention;

[0095] FIG. 9 shows a high-level illustration of a protocol for performing the key shuffling step according to an embodiment of the invention using a cryptographic mix network;

[0096] FIG. 10 shows a high-level illustration of another protocol for performing the key shuffling step according to an embodiment of the invention based on blind signatures;

[0097] FIG. 11 shows a high-level illustration of another protocol for performing the key shuffling step according to an embodiment of the invention using threshold Pointcheval-Sanders signatures;

[0098] FIG. 12 shows an exemplary embodiment of a network node according to an embodiment of the invention;

[0099] FIG. 13 shows a gossip graph according to an embodiment of the invention; and

[0100] FIG. 14 shows a node identity structure of network nodes of a network according to another embodiment of the invention.

MODES FOR CARRYING OUT THE INVENTION

[0101] At first, some general aspects and terms of embodiments of the invention will be introduced.

[0102] According to embodiments, a distributed network comprises a plurality of network nodes that are arranged in a distributed fashion. In such a distributed network computing, software and data is distributed across the plurality of network nodes. The network nodes establish computing resources and the distributed network may use in particular distributed computing techniques.

[0103] According to embodiments, distributed networks may be in particular embodied as blockchain networks. The term “blockchain” shall include all forms of electronic, computer-based, distributed ledgers. According to some embodiments, the blockchain network may be embodied as proof-of-work blockchain network. According to other embodiments, the blockchain network may be embodied as proof-of-stake blockchain network.

[0104] FIG. 1 shows an exemplary block diagram of a distributed network 100 according to an embodiment of the invention.

[0105] The distributed network 100 comprises a plurality of network nodes 10. The plurality of network nodes 10 are coupled or connected to neighbouring nodes 10 via communication links 11, which may also be denoted as edges 11. The plurality of network nodes 10 may communicate with their neighbours via the communications links 11, in particular by means of a gossip protocol. The network 100 may be in particular a proof-of-stake blockchain network.

[0106] Proof-of-stake (PoS) describes a method by which a blockchain network reaches distributed consensus about which node is allowed to create the next block of the blockchain. PoS-methods may use a weighted random selection, whereby the weights of the individual nodes may be determined in particular in dependence on the assets (the “stake”) of the respective node.

[0107] According to embodiments, each network node of the distributed network may be associated with a fixed amount of stake. Accordingly, a party controlling more stake may simply control more node identities.

[0108] FIG. 2 illustrates the creation of blocks in the distributed network 100 according to an exemplary embodiment of the invention. In this exemplary embodiment three blocks 201, 202 and 203 are illustrated. Block 201 comprises a plurality of transactions, namely the transactions tx1.1, tx1.2 and possibly further transactions indicated with dots. Block 202 comprises also a plurality of transactions, namely the transactions tx2.1, tx2.2 and possibly further transactions indicated with dots. Block 203 also comprises a plurality of transactions, namely the transactions tx3.1, tx3.2 and possibly further transactions indicated with dots. The blocks 201, 202 and 203 are chained together. More particularly, each of the blocks comprises a block hash of the previous block. This cryptographically ties the current block to the previous block(s).

[0109] FIG. 3 shows a flow chart 300 comprising method steps of a computer-implemented method for performing a consensus protocol in a distributed network, e.g. in the distributed network 100 of FIG. 1.

[0110] At a step 310, the distributed network 100 links each of the plurality of network nodes 10 to a first node identity of a plurality of first node identities, in particular to a permanent node identity of a plurality of permanent node identities. Each of the plurality of first node identities comprises a first verification key and a first signature key of a public-key signature scheme, in particular a permanent verification key and a permanent signature key.

[0111] At a step 320, the distributed network 100 performs a key shuffling step. The key shuffling step comprises performing an unlinkable one-to-one mapping between the plurality of first node identities and a plurality of second node identities. Each of the plurality of second node identities comprises a second verification key and a second signature key, in particular a blinded verification key and a blinded signature key of a public-key signature scheme.

[0112] At a step 330, which may be denoted as consensus step 330, the distributed network 100 performs the consensus protocol with a subset of the plurality of second node identities, in particular with a subset of the blinded node identities. The consensus protocol may be in particular a proof-of-stake consensus protocol on transactions to be written on the distributed network 100.

[0113] At a step 340, which may be denoted as revealing step 340, the nodes 10 of the distributed network 100 reveal their second node identities, in particular their blinded node identities.

[0114] According to embodiments, the key shuffling step 320, the consensus step 330 and the revealing step 340 are repeated, in particular regularly repeated.

[0115] The method steps may be in particular performed in a subsequent order during subsequent epochs.

[0116] FIG. 4 shows a node identity structure of network nodes of a network according to an embodiment of the invention, e.g. of the network 100 as shown in FIG. 1.

[0117] Each of the plurality of network nodes 10 comprises a stake identity stid, 401. The stake identity stid, 401 comprises a stake verification key pk.sub.stid and a stake signature key sk.sub.stid of a public-key signature scheme.

[0118] The network 100 is configured to certify permanent node identities 402, of the respective nodes 10 by the corresponding stake identities stid, 401. The permanent node identities 402 may be in the following also denoted as permanent node identities pnid. The permanent node identities 402, pnid comprise a permanent verification key pk.sub.perm and a permanent signature key sk.sub.perm of a public-key signature scheme.

[0119] The stake verification key pk.sub.stid may be in particular a Schnorr public key.

[0120] The network 100 is further configured to assign a network identity netid, 403 to each of the plurality of permanent node identities.

[0121] According to one embodiment, as illustrated by a full arrow, the network identity netid,403 may be certified by the corresponding permanent node identity pnid, 402. The network identity netid,403 comprises a network verification key pk.sub.netid and a network signature key sk.sub.netid of a public-key signature scheme.

[0122] According to another embodiment, as illustrated by a dotted arrow, the network identity netid,403 may be certified by the corresponding stake identity stid, 401.

[0123] The network identity netid,403 certifies a TLS certificate 404 according to the Transport Layer Security standard. The TLS certificate comprises as network identity netid the network verification key pk.sub.netid and a network address, in particular an Internet Protocol (IP) address.

[0124] The network 100 is configured to perform a key shuffling step in order to create blinded node identities.

[0125] The key shuffling step takes as input all the permanent node identities pnid, 402 of all the nodes 10 of the network 100 and performs an unlinkable one-to-one mapping between the permanent node identities pnid, 402 and a corresponding number of blinded node identities 410, bnid. Each of the blinded node identities bnid comprises a blinded verification key pk.sub.bnid and a blinded signature key sk.sub.bnid of a public-key signature scheme.

[0126] The key shuffling step may be regularly repeated, e.g. at regular time intervals.

[0127] In the example of FIG. 4, two key shuffling steps are shown. A first key shuffling step has generated blinded node identities 410(1), bnid(1) and a second key shuffling step has generated blinded node identities 410(2), bnid(2).

[0128] FIG. 5 illustrates an exemplary example of a key shuffling step according to embodiments of the invention.

[0129] The key shuffling step receives as input a plurality of n first verification keys (public keys) pk.sub.1, pk.sub.2, . . . , pk.sub.n. The first verification keys (public keys) pk.sub.1, pk.sub.2, . . . , pk.sub.n may be in particular embodied as permanent verification keys of permanent node identities.

[0130] The key shuffling step produces as output a plurality of n second verification keys (public keys) pk.sub.1′, pk.sub.2′, . . . , pk.sub.n′. The verification keys (public keys) pk.sub.1′, pk.sub.2′, . . . , pk.sub.n′ may be in particular embodied as blinded verification keys of blinded node identities.

[0131] The key shuffling step performs a mapping between the plurality of n first verification keys pk.sub.1, pk.sub.2, . . . , pk.sub.n and the plurality of n second verification keys pk.sub.1′, pk.sub.2′, . . . , pk.sub.n′ that is firstly unlinkable. This means that the respective links between the first verification keys and the second verification keys as illustrated by the dotted arrows are blinded or in other words anonymous and only known to the respective owner of the respective first verification key. Furthermore, the mapping is a one-to-one mapping, i.e. each of the n first verification keys pk.sub.1, pk.sub.2, . . . , pk.sub.n is mapped only to a single one of the n second verification keys pk.sub.1′, pk.sub.2′, . . . , pk.sub.n′.

[0132] FIG. 6 shows a node identity structure 600 of network nodes of a network according to an embodiment of the invention, e.g. of the network 100 as shown in FIG. 1.

[0133] Each of the plurality of network nodes 10 comprises a stake identity stid, 601. The stake identity stid, 601 comprises a stake verification key pk.sub.stid and a stake signature key sk.sub.stid of a public-key signature scheme.

[0134] The network 100 is configured to certify permanent node identities 602, pnid of the respective nodes 10 by the corresponding stake identities stid, 601. The permanent node identities 602, pnid comprise a permanent verification key pk.sub.perm and a permanent signature key sk.sub.perm of a public-key signature scheme.

[0135] The network 100 is configured to perform a key shuffling step in order to create blinded node identities bnid (i).

[0136] The key shuffling step takes as input all the permanent node identities pnid, 602 of all the nodes 10 of the network 100 and performs an unlinkable one-to-one mapping between the permanent node identities pnid, 602 and a corresponding number of blinded node identities 610, bnid. Each of the blinded node identities 610, bnid comprises a blinded verification key pk.sub.bnid and a blinded signature key sk.sub.bnid of a public-key signature scheme.

[0137] The network having the node identity structure of FIG. 6 performs as another key shuffling step an unlinkable one-to-one mapping between the plurality of blinded node identities 610, bnid and a plurality of blinded network identities 620, bnetid. Each of the plurality of blinded network identities 620, bnetid comprises a blinded network verification key pk.sub.bnetid and a blinded network signature key sk.sub.bnetid. According to embodiments, the blinded network verification key pk.sub.betid and the blinded network signature key sk.sub.bnetid are keys of a public-key signature and encryption scheme, such as e.g. RSA. This allows to use the blinded network verification key/signature key pair for signing as well as encryption.

[0138] After performing the key shuffle step, all blinded network identities bnetid may be assigned to a vertex of a gossip graph, so that each node can look up the bnetids of its neighbors. If a node i with blinded network identity bnetid.sub.i has a gossip neighbor j with blinded network identity bnetid.sub.j, then node i computes the ciphertext

c.sub.i,j←Enc(bnetid.sub.j(IP.sub.i)),

[0139] signs it with bnetid.sub.i, and posts the signed ciphertext on the chain. IP denotes the Internet Protocol address. Node j may then verify its neighbor's signature and decrypt the ciphertext to recover its neighbor's IP address.

[0140] One advantage to generate blinded network identities is that network nodes may be assigned to shards based on their blinded node identity. By shuffling only the blinded node identity assigned to a specific shard, one obtains network identities for just the nodes assigned to that shard, without having to know which permanent node identities are assigned to the shard.

[0141] FIG. 7 shows a node identity structure 700 of network nodes of a network according to an embodiment of the invention, e.g. of the network 100 as shown in FIG. 1.

[0142] The node identity structure corresponds partly to the node identity structure 600 of FIG. 6 and comprises accordingly a stake identity stid, 601, a permanent node identity 602, pnid and blinded node identities bnid 610.

[0143] However, in contrast to the node identity structure of FIG. 6, the node identity structure of FIG. 7 performs as another key shuffle step an unlinkable one-to-one mapping between the plurality of permanent node identities 610, pnid and a plurality of blinded network identities 720, bnetid.

[0144] FIG. 8 shows a time diagram or in other words a timeline of the key shuffling and revealing steps according to an embodiment of the invention.

[0145] At a step 801, corresponding to an epoch i−2, blind node identities bnids are generated through an execution of the key shuffle protocol, using the permanent node identities pnids as input.

[0146] At a step 802, in epoch i−1, members of a committee are elected, e.g. by the use of a random beacon. This partitions the blinded node identities bnids into committees: The members of the committees perform a distributed key generation (DKG) protocol to determine their transaction keys.

[0147] At a step 803, corresponding to the epoch i, the members of the committee perform the consensus protocol with the blinded node identities bnids.

[0148] At a step 804, corresponding to an epoch i+1, all nodes reveal the link between their permanent node identity pnid and their blind identity bnid. Any rewards or penalizations that a bnid accumulated during epoch i can then be applied to the corresponding permanent node identity pnid or to the stake identity stid. Any node that fails to reveal its blind node identity is assumed to be part of the misbehaving nodes and may be penalized accordingly, e.g., by applying the maximum penalization that was acquired by any bnid(i) during the previous epoch.

[0149] According to embodiments, if the stake of a node that misbehaved in epoch i is taken away entirely, then that node may still be participating in the consensus protocol until epoch i+2, because its permanent node identity pnid can only be removed from the input of the key shuffle for bnid(i+3). However, it will be excluded from any consensus activities after epoch i+2.

[0150] According to embodiments of the invention there may be used a plurality of protocols for performing the key shuffling step. In the following FIGS. 7 to 9 some preferred protocols according to embodiments of the invention will be described in more detail.

[0151] FIG. 9 illustrates on a high level a protocol for performing the key shuffling step according to an embodiment of the invention. The protocol uses a cryptographic mix network. The mix network may be constructed through a sequence of shuffles, where each shuffle of a list of verification/public keys pk.sub.1, . . . , pk.sub.N is a re-randomized new list of verification/public keys pk.sub.1′, . . . , pk.sub.N. ′ in a permuted order.

[0152] According to this embodiment, m random nodes are selected that will act as mix servers or in other words mixers, taking turns in mixing all node identities. By taking m large enough so that one can expect that at least one of the chosen mix servers is honest, an adversary will not be able to track identities through the mixing process.

[0153] More particularly, for the illustrated example of FIG. 9 it is assumed that the underlying network comprises a plurality of n network nodes, wherein the n network nodes comprise permanent node identities pnid.sub.1, . . . , pnid.sub.n. The permanent node identities pnid.sub.1, . . . , pnid.sub.n are embodied as public keys/permanent verification keys of a public key signature scheme, wherein

pnid.sub.1=g.sup.sk.sup.1,pnid.sub.2=g.sup.sk.sup.2, . . . ,pnid.sub.n=g.sup.sk.sup.n;

[0154] wherein g is a base of a group, in particular of an elliptic curve group, and sk.sub.i, sk.sub.2, . . . sk.sub.n are the corresponding secret keys/signature keys.

[0155] The key shuffling step comprises a step of electing, by the plurality of permanent node identities pnid.sub.1, . . . , pnid.sub.n a plurality of mixers M.sub.1, M.sub.2, . . . , M.sub.m as a subset of the permanent node identities. The plurality of mixers M.sub.1, M.sub.2, . . . , M.sub.m are arranged at a specified order from 1 to m.

[0156] The first mixer M.sub.1 receives as input list the permanent verification keys of the plurality of permanent node identities pnid.sub.1, . . . , pnid.sub.n. It then chooses a secret exponent r.sub.1 and performs a re-randomization of the input list by means of the secret exponent r.sub.1 as follows:

pk.sub.1,1=pk.sub.π.sub.1.sub.(1).sup.r.sup.1pk.sub.1,2=pk.sub.π.sub.1.sub.(2).sup.r.sup.1. . . pk.sub.1,n=pk.sub.π.sub.1.sub.(n).sup.r.sup.1

[0157] Furthermore, it performs a permutation π.sub.1 of the re-randomized input list, computes R.sub.1=g.sup.r.sup.1 and computes a zero-knowledge proof ZKP(r.sub.1, π.sub.1) proving that the re-randomization and the permutation has been computed correctly.

[0158] The re-randomization and permutation step is then subsequently performed by all of the other mixers M.sub.2, . . . , M.sub.m, wherein each subsequent mixer receives as input list the output list of the previous mixer. Additionally, each mixer computes a publicly verifiable proof of shuffle showing that the randomization and permutation were performed correctly. The proof is published on chain together with the list of re-randomized keys and the commitment of the randomness used. The soundness of the proof of shuffle guarantees that it is unfeasible for a misbehaving mixer to compute an accepting proof.

[0159] The output list of the last mixer of the specified order establishes then the plurality of blinded nodeidentities. In this example, the last mixer M.sub.m outputs the blinded node identities bnid.sub.1, . . . , bnid.sub.n as follows:

bnid.sub.1=pk.sub.m-1,π.sub.m.sub.(1).sup.r.sup.m, . . . ,bnid.sub.n=pk.sub.m-1,π.sub.m.sub.(n).sup.r.sup.m,

[0160] wherein

[0161] bnid.sub.1=R.sub.m.sup.sk.sup.π(n) and bnid.sub.n=R.sub.m.sup.sk.sup.π(n).

[0162] In addition, the last mixer M.sub.m computes the zero knowledge proof ZKP(r.sub.m,π.sub.m) and adds it to the output list.

[0163] The plurality of mixers comprises a predefined minimum number m of mixers. The minimum number m of mixers is taken large enough so that one can expect that at least one of the chosen mixers is honest. According to embodiments, a minimum number m of 20, 50 or 100 mixers may be chosen.

[0164] According to embodiments, further key-shuffling/mixing steps may use the plurality of blinded node identities as input and accordingly elect by the plurality of blinded node identities that have been computed in a previous epoch a plurality of mixers as a subset of the blinded node identities.

[0165] Embodiments of the invention may use a broadcast communication channel that proceeds in rounds, so that each participant has the opportunity to provide an input in each round. At the end of every round, all participants receive all inputs provided during that round.

[0166] According to embodiments, a blockchain may be used as communication channel. According to embodiments, each round of the channel corresponds to a sequence of finalized blocks that is long enough so that at least one of the blockmakers must have been honest.

[0167] According to embodiments, the key shuffle step as illustrated in FIG. 9 is associated with a subsequent identity revealing step during which the link between the permanent node identities and their current blinded node identities must be disclosed.

[0168] According to embodiments the identity revealing step may use a threshold decryption committee. More particularly, in a new epoch, the first time a user uses his new blinded node identity, the protocol may require him to publish also a threshold encryption of his permanent node identity, together with a proof of consistency of his blinded node identity. At the end of an epoch, the committee could simply publish the secret key associated with the threshold decryption scheme. In case a blinded node identity has misbehaved during the epoch, the associated permanent node identity can be recovered and punished.

[0169] FIG. 10 shows a high-level illustration of another protocol for performing the key shuffling step according to an embodiment of the invention.

[0170] The key shuffling protocol as illustrated in FIG. 10 is based on blind signatures. According to embodiments, Boldyreva's blind signatures may be used as disclosed in Boldyreva A. (2003), Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Desmedt Y. G. (eds) Public Key Cryptography—PKC 2003. PKC 2003. Lecture Notes in Computer Science, vol 2567. Springer, Berlin, Heidelberg.

[0171] Boldyreva's blind signatures are a blind variant of BLS signatures as described in Boneh, D., Lynn, B. & Shacham, H. J Cryptology (2004) 17: 297, https://doi.org/10.1007/s00145-004-0314-9.

[0172] However, it should be noted that the protocol of FIG. 10 may be generally applied to any blind signature scheme that has the additional property that, given the transcript of a blind signing protocol, anyone can check whether the signer misbehaved.

[0173] On a very high level, according to the protocol of this embodiment every node obtains a blindly signed certificate on a freshly generated public key which is then used as the blinded node identity.

[0174] At the start of the key-shuffling step, a trusted party 1010 is randomly selected as blind signer of the certificates, identified by his current blinded verification/blinded public key bpk of his blinded node identity bnid. The blind signer generates a fresh BLS key pair and posts the public key on the chain, signed under his bnid.

[0175] A plurality of n nodes 1020 have permanent node identities comprising public keys pk.sub.1, . . . , pk.sub.n. At a first step, the plurality of n nodes generate a fresh signature key pair (pk.sub.i′, sk.sub.i′) and use the verification key/public key pk.sub.i′ to be their new blinded node identity bnid.sub.i′.

[0176] They then perform an on-chain execution of the blind BLS signature protocol using bnid.sub.i′ as the message, whereby they authenticate their first move β.sub.i=H(bnid.sub.i′).sup.r of the blind signature protocol by signing it with their permanent node identity pnid.sub.i.

[0177] The blind signer 1010 verifies that all first moves are correctly signed by a registered permanent node identity pnid, and that each pnid authenticates at most one first move. PNIDs that posted multiple first moves are penalized and excluded from the protocol.

[0178] The blind signer 1010 performs then a blind signature BSign for all valid requests, signed with his current bnid and posts them on the chain.

[0179] In case the blind signer 1010 misbehaves by posting an incorrect response or not posting any response to a valid request β.sub.i, then the blind signer 1010 is penalized and the nodes restart the protocol with a new blind signer.

[0180] All nodes then compute their blinded node identity certificate cert.sub.i by unblinding γ.sub.i and they post (bnid.sub.i′; cert.sub.i) to the chain.

[0181] If more valid pairs ((bnid.sub.i′; cert.sub.i) are posted to the chain than the number of valid requests β.sub.i were posted to the chain earlier, then the blind signer 1010 is penalized and the protocol is repeated with a new blind signer. Otherwise, the bnid.sub.i′ from the valid pairs are used as the new blinded node identities.

[0182] FIG. 11 shows a high-level illustration of another protocol for performing the key shuffling step according to an embodiment of the invention. The protocol shown in FIG. 11 uses a threshold group signature scheme with attributes, as can for example be derived from the Pointcheval-Sanders signature scheme as disclosed e.g. in David Pointcheval, Olivier Sanders, Short Randomizable Signatures, Kazue Sako, The Cryptographers' Track at the RSA Conference 2016, February 2016, San Francisco, United States. Springer Verlag, CT-RSA 2016, LNCS (9610), pp. 111-126, 2016.

[0183] In a group signature scheme, a group manager issues credentials to group members, who then use these credentials to sign messages. The signatures are such that nobody except a dedicated opening authority can tell which group member signed the message.

[0184] In a threshold group signature scheme, the roles of group manager and opening authority are distributed over an issuance committee and an opening committee, a threshold of whom must collaborate to issue a credential or to reveal who created a certain signature, respectively.

[0185] A threshold group signature scheme with attributes additionally enables the issuance committee to bind the issued credential to an attribute that the group member may or may not reveal when signing a message.

[0186] FIG. 11 depicts how a key shuffle can be built from a threshold group signature with attributes. In a first step 1101, all nodes 1110 of the network (depicted in the middle of the figure) generate their permanent node identities as pnid.sub.i=g.sup.ski.

[0187] In a second step 1102, an issuance committee 1120 (depicted on the left of the figure) then blindly issues credentials to all nodes with an attribute that is equal to their secret key sk.sub.i, meaning that each node obtains a credential for attribute sk.sub.i, but the issuance committee 1120 doesn't learn sk.sub.i in the process.

[0188] In a third step 1103, depicted on the right in the figure, each node 1110 publishes a unique pseudonym π.sub.i=H (epoch).sup.ski, where H is a hash function and epoch is the sequence number of the epoch when the blinded identities have to become active, and uses its credential on sk.sub.i to publish a signature on the pseudonym π.sub.i and a zero-knowledge proof that π.sub.i=H(epoch).sup.ski was correctly computed for the value of sk.sub.i that is embedded as an attribute in the credential.

[0189] Note that the pseudonym π.sub.i is uniquely derived from the secret key sk.sub.i, but for anyone who only knows the permanent node identity pnid.sub.i=g.sup.ski but not the secret key sk.sub.i, it is cryptographically impossible to determine which pseudonym corresponds to which permanent node identity.

[0190] In a further step, each node 1110 may according to embodiments either directly use the pseudonym π.sub.i as its blinded node identity bnid.sub.i, or it may generate a fresh signature key pair, may set the public verification key to be its blinded node identity bnid.sub.i, and may publish bnid.sub.i together with a zero-knowledge proof that it knows the secret key sk.sub.i underlying the pseudonym π.sub.i.

[0191] Referring now to FIG. 12, a more detailed block diagram of a network node 10 according to embodiments of the invention is shown, e.g. of the network 100 of FIG. 1 The network node 10 establishes a computing node that may perform computing functions and may hence may be generally embodied as computing system or computer. The network node 10 may be e.g. a server computer. The network node 10 may be configured to perform a computer-implemented method for performing a consensus protocol, in particular a proof-of-stake consensus protocol of a blockchain network. The network node 10 may be operational with numerous other general purpose or special purpose computing system environments or configurations.

[0192] The network node 10 may be described in the general context of computer system-executable instructions, such as program modules, being executed by a computer system. Generally, program modules may include routines, programs, objects, components, logic, data structures, and so on that perform particular tasks or implement particular abstract data types. The network node 10 is shown in the form of a general-purpose computing device. The components of network node 10 may include, but are not limited to, one or more processors or processing units 15, a system memory 20, and a bus 16 that couples various system components including system memory 20 to processor 15.

[0193] Bus 16 represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus.

[0194] Network node 10 typically includes a variety of computer system readable media. Such media may be any available media that is accessible by network node 10, and it includes both volatile and non-volatile media, removable and non-removable media.

[0195] System memory 20 can include computer system readable media in the form of volatile memory, such as random access memory (RAM) 21 and/or cache memory 22. Network node 10 may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, storage system 23 can be provided for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a “hard drive”). Although not shown, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a “floppy disk”), and an optical disk drive for reading from or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM or other optical media can be provided. In such instances, each can be connected to bus 16 by one or more data media interfaces. As will be further depicted and described below, memory 20 may include at least one computer program product having a set (e.g., at least one) of program modules that are configured to carry out the functions of embodiments of the invention.

[0196] Program/utility 30, having a set (at least one) of program modules 31, may be stored in memory 20 by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules 31 generally carry out the functions and/or methodologies of embodiments of the invention as described herein. Program modules 31 may carry out in particular one or more steps of a computer-implemented method for performing a consensus protocol in a distributed network, e.g. of one or more steps of the methods as described above.

[0197] Network node 10 may also communicate with one or more external devices 17 such as a keyboard or a pointing device as well as a display 18. Such communication can occur via Input/Output (I/O) interfaces 19. Still yet, network node 10 can communicate with one or more networks 40 such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter 41. According to embodiments the network 40 may be in particular a distributed network comprising a plurality of network nodes 10, e.g. the network 100 as shown in FIG. 1. As depicted, network adapter 41 communicates with the other components of network node 10 via bus 16. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with network node 10.

[0198] FIG. 13 shows a gossip graph 1300 according to an embodiment of the invention. The gossip graph may model a distributed network and comprises vertices 1310 and edges 1311. The gossip graph 1300 is embodied as a 3-regular graph. Accordingly, each vertex has 3 neighbors. The exemplary gossip graph 1300 comprises 8 vertices numbered from 1 to 8. A blinded network identity bnetid.sub.i is mapped randomly to each of the vertices 1 to 8 of the graph. Such a mapping may be in particular performed after a key-shuffle step.

[0199] Information between the vertices 1310 may be disseminated by means of a gossip protocol.

[0200] More particularly, each vertex/node can look up the bnetids of its neighbors. As an example, vertex 3 with blinded network identity bnetid.sub.7 has gossip neighbors 2, 4 and 8 with blinded network identities bnetids, bnetid.sub.4 and bnetids, respectively.

[0201] As an example for the communication between vertex 3 and vertex 2, vertex 3 may encrypt its network address (IP address) with the network encryption key of the blinded network identity bnetid.sub.5 of vertex 2, sign the encrypted network address with its own network signature key of the blinded network identity bnetid.sub.7 and provide its signed and encrypted network address to vertex 2.

[0202] FIG. 14 shows a node identity structure 1400 of network nodes of a network according to an embodiment of the invention, e.g. of the network 100 as shown in FIG. 1.

[0203] The node identity structure corresponds partly to the node identity structure 400 of FIG. 6 and comprises a stake identity stid, 1401, a permanent node identity 1402, pnid and blinded node identities bnid, 1410.

[0204] In contrast to the node identity structure of FIG. 4, the node identity structure of FIG. 14 performs as a further key shuffle step an unlinkable one-to-one mapping between the plurality of blinded node identities bnid(i) that have been generated in a previous key shuffling step and a plurality of further blinded node identities bnid(i+1). In other words, after the first key shuffling step that has performed a shuffling from the permanent node identities, the further key shuffling step uses the blinded node identities of the previous key shuffling step as input.

[0205] Aspects of the present invention may be embodied as a system, in particular a network for performing a consensus protocol, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention.

[0206] The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire.

[0207] Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device.

[0208] Computer readable program instructions for carrying out operations of the present invention may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the “C” programming language or similar programming languages.

[0209] Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, networks, apparatus (systems), and computer program products according to embodiments of the invention.

[0210] Computer readable program instructions according to embodiments of the invention may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks.

[0211] The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed on the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks.

[0212] The flowchart and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of networks, systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved.

[0213] In the following section we disclose further cryptographic details according to embodiments of the invention, in particular further cryptographic details of the exemplary key-shuffling protocols that have been described above with reference to FIGS. 9-11.

[0214] At first, we recall some basic definitions and constructions.

[0215] Let G be a multiplicative group of prime q, where q is a prime of bitlength k (e.g., k=256), and let g be a generator of the group G.

[0216] Threshold encryption allows a set of n participants to agree on a common encryption public key pk=g.sup.x so that none of them knows the actual decryption key x, but any subset of t or more of the n participants can jointly decrypt ciphertexts.

[0217] The keys may be in particular generated using a distributed key generation procedure as disclosed e.g. in Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin: Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. J. Cryptology 20(1): 51-83, 2007. At the end of this procedure, each participant i=1, . . . , n obtains a secret share s.sub.i=p(i) mod q, where p(X)=x+a.sub.1 X+ . . . +a.sub.t-1 X.sup.t-1 is a polynomial with random coefficients x, a.sub.1, . . . , a.sub.t-1. All participants obtain the public key pk=g.sup.x as well as values B.sub.1=g.sup.a.sub.1, . . . , B.sub.t-1=g.sup.a.sub.t-1.

[0218] To encrypt a message m∈G, one chooses a random value r from Z.sub.q and returns C=(g.sup.r, X.sup.r.Math.m).

[0219] To decrypt a ciphertext C=(C.sub.1, C.sub.2), participant i computes R.sub.i=C.sub.1.sup.si and creates a zero-knowledge proof

ZKP{(s.sub.i):R.sub.i=C.sub.1.sup.si and g.sup.s.sub.i=π.sub.k=1, . . . ,tB.sub.k.sup.i.sup.k}

and publishes R.sub.i and the zero-knowledge proof. As soon as at least t values with valid proofs are published, all can compute

pk.sup.r=πR.sub.i.sup.λi(0)

where

λ.sub.i(X)=π.sub.j≠i(X−j)/(i−j)mod q

and output

m=C.sub.2/pk.sup.r.

[0220] In the following, detailed embodiments of the protocol based on mixers as illustrated in FIG. 9 are given. Mixers may also be denoted as mix servers.

[0221] Protocols according to embodiments of the invention may use in particular a non-interactive zero-knowledge proof system that proves the correctness of a key shuffle. Each mixer M.sub.τ receives as input (R.sub.τ-1, pk.sub.τ-1,1, . . . , pk.sub.τ-1,N) from the previous mixer and returns (R.sub.τ:=R.sub.τ-1.sup.r, pk.sub.τ,1, . . . , pk.sub.τ,N) together with a proof attesting that the output keys are a shuffle of the ones in the input. More precisely, mixer M.sub.τ provides a proof for the following relation:

[00001]${ℛ}_{\mathrm{Sh}}=\left\{\begin{array}{c}\left(u,w\right)=\left(\left({\left\{{\mathrm{pk}}_{\tau -1,i}\right\}}_{i\in \left[N\right]},{\left\{{\mathrm{pk}}_{\tau ,j}\right\}}_{j\in \left[N\right]},R_{\tau -1},R_{\tau }\right),\left(r,\pi \right)\right):\\ \begin{array}{ccc}{\mathrm{pk}}_{\tau ,i},{\mathrm{pk}}_{\tau ,j},R_{\tau -1},R_{\tau }\in \mathrm{��},& r\in {\mathbb{Z}}_q,& \pi \in {.Math.}_N,\end{array}\\ \begin{array}{cc}{R}_{\tau }=R_{\tau -1}^r& {\mathrm{pk}}_{\tau -1,i}^r={\mathrm{pk}}_{\tau ,\pi \left(i\right)}\end{array}\end{array}\right\}$

where [N]={1, . . . , } and Σ.sub.N is the set of all permutations over [N]. We refer to the proof generation algorithm of this relation as PROVER.sub.Sh and to the verification algorithm as VERIFIER.sub.Sh.

[0222] Setup. First, all nodes agree on any setup parameters (e.g., common reference strings or hash functions) that are needed for the proof of shuffle .sub.Sh.

[0223] Let the permanent node identities be given by public keys pk.sub.1, . . . , pk.sub.N such that pk.sub.i=g.sup.sk.sup.i. Associated to his public key pk, each node includes a self-signed certificate of the form cert.sub.i=(h.sub.i, c.sub.i, s.sub.i) that is computed as

h.sub.i←H.sub.0(pk.sub.i).sup.sk.sup.i

ρ.sub.i←.sub.R.sub.q

t.sub.i,1←g.sup.ρi;t.sub.i,2←H.sub.0(pk.sub.i).sup.ρi

c.sub.i←H.sub.1(g,pk.sub.i,H.sub.0(pk.sub.i),h.sub.i,t.sub.i,1,t.sub.i,2)

s.sub.i←ρ.sub.i+c.sub.i.Math.sk.sub.i mod q

[0224] The certificate is verified by checking that

c.sub.i=H.sub.1(g,pk.sub.i,H.sub.0(pk.sub.i),h.sub.i,g.sup.s.sup.i.Math.pk.sub.i.sup.−c.sup.i,H.sub.0(pk.sub.i).sup.s.sup.i.Math.h.sub.i.sup.−c.sup.i).

[0225] According to embodiments, the nodes agree on a selection of mixers M.sub.1, . . . , M.sub.m chosen randomly from the pool of nodes.

[0226] The number of mixers should be such that the probability that all chosen mixers are corrupt is negligible. The mixers could be chosen based on the output of a common random beacon, or according to preferred embodiments, the block proposers for particular block heights could be designated to act as mixers.

[0227] The nodes also agree on a subset of protocol participants of a consensus protocol that form an opening committee.

[0228] The members of the opening committee perform a distributed key generation protocol to jointly generate a t-out-of-n threshold public key pk.sub.e=g.sup.sk.sup.e so that each member has a secret share of the corresponding secret key sk.sub.e. Here, n and t are chosen such that there is a negligible probability that t or more of the n members are corrupt, and such that one can safely assume that t of the n members will be available to participate in the revealing protocol when required.

[0229] Mixing. Each mix server/mixer will re-randomize and randomly permute the list of public keys that it receives from the previous mix server.

[0230] More particularly, the input of the first mix server M.sub.1 is the list of long-term node identities (pk.sub.1, . . . , pk.sub.N), and the input of the τ-th mix server contains (R.sub.τ-1, pk.sub.τ1,1, . . . , pk.sub.τ-1,N) produced by M.sub.τ-1. Letting R.sub.0←g and pk.sub.0,i←pk.sub.i, server M.sub.τ proceeds as follows:

M.sub.τ(R.sub.τ-1,pk.sub.τ-1,1, . . . ,pk.sub.τ-1,N):r.sub.τ,ρ.sub.τ←.sub.R.sub.q

R.sub.τ←R.sub.τ-1.sup.r.sup.τ

h.sub.τ←H.sub.0(R.sub.τ).sup.r.sup.τ

t.sub.τ,1←R.sub.τ-1.sup.ρ.sup.τ;t.sub.τ,2←H.sub.0(R.sub.τ).sup.ρ.sup.τ

c.sub.τ←H.sub.1(R.sub.τ-1,R.sub.τ,H.sub.0(R.sub.τ),h.sub.τ,t.sub.i,1,t.sub.i,2)

s.sub.τ←ρ.sub.T+c.sub.τ.Math.r.sub.τ mod q

Choose a random permutation τ.sub.τ over {1, . . . , N}

[0231] For j=1, . . . , N do pk.sub.τ,j←pk.sub.τ-1,π.sub.τ.sub.(j).sup.r.sup.τ

π.sub.Sh,τ←.sub.RPROVER.sub.Sh(({pk.sub.τ-1,i}.sub.i∈[N],{pk.sub.τ,i}.sub.i∈[N],R.sub.τ-1,R.sub.τ),(r.sub.τ,π.sub.τ))

[0232] Sign and broadcast (R.sub.τ, h.sub.τ, c.sub.τ, s.sub.τ, π.sub.Sh,τ, pk.sub.i,1, . . . , pk.sub.i,N)

[0233] Verification. After each round of mixing, the block proposer and/or notarizers verify the output of the last mix server (R.sub.τ, h.sub.τ, c.sub.τ, s.sub.τ, π.sub.Sh,τ, pk.sub.τ,1, . . . , pk.sub.τ,N) by checking that VERIFIER.sub.Sh(({pk.sub.τ-1,i}.sub.i∈[N], {pk.sub.τ,i}.sub.i∈[N], R.sub.τ-1, R.sub.τ), π.sub.Sh)=1 and that

c.sub.τ=H.sub.1(R.sub.i-1,R.sub.τ,H.sub.0(R.sub.τ),h.sub.τ,R.sub.i-1.sup.s.sup.τ.Math.R.sub.τ.sup.−c.sup.τ,H.sub.0(R.sub.τ).sup.s.sup.τ.Math.h.sub.τ.sup.−c).

[0234] If any of these check fails, then this mixing round may be deemed invalid. At this point, according to embodiments one could either ignore the output of this mixer and let the (τ+1)st mixer proceed on the output of the (τ−1)st mixer (R.sub.τ-1,pk.sub.τ-1,1, . . . , pk.sub.τ-1,N), or according to other embodiments one could choose a new protocol participant to take up the role of M.sub.τ until a valid round of mixing has been performed.

[0235] Final output. Let (R.sub.m, h.sub.m, c.sub.m, s.sub.m, π.sub.Sh,m,pk.sub.m,1, . . . , pk.sub.m,N) be the output of the last mixing server M.sub.m. If we let g′←R.sub.m and let (pk′.sub.1, . . . , pk′.sub.N)←(pk.sub.m,1, . . . , pk.sub.m,N), then for each protocol participant with original public key pk.sub.i=g.sup.sk.sup.i, there will be exactly one public key pk′j=g′.sup.sk.sup.i in the final output.

[0236] Signing. The node may take pk′.sub.j as its new blinded node identity (BNID), using it to create Schnorr signatures using g′ as generator, rather than g.

[0237] The first time that a protocol participant creates a signature with its new BNID, however, it adds according to embodiments a verifiable encryption under pk.sub.e of its original key pk.sub.i while proving that it has the same secret key as pk′.sub.j, i.e.,

r,ρ.sub.1,ρ.sub.2←.sub.R.sub.q

C.sub.1←g.sup.r

C.sub.2←pk.sub.e.sup.r.Math.pk.sub.i

t.sub.1←g.sup.ρ.sup.1

t.sub.2←pk.sub.e.sup.ρ.sup.1.Math.g.sup.ρ.sup.2

t.sub.3←g′ρ.sub.2

c←H.sub.1(C.sub.1,g,C.sub.2,pk.sub.e,g,g′,pk′.sub.j,t.sub.1,t.sub.2,t.sub.3)

s.sub.1←ρ.sub.1+c.Math.r mod q

s.sub.2←ρ.sub.2+c.Math.sk.sub.i mod q

Return (C.sub.1, C.sub.2, c, s.sub.1, s.sub.2)

[0238] Verification. Signatures under a public key pk′.sub.j may be verified as normal Schnorr signatures using generator g′. In a first signature of a protocol participant under the new key pk′.sub.j, one may additionally check according to embodiments that the verifiable encryption is valid by checking that

c=H.sub.1(C.sub.1,g,C.sub.2,pk.sub.e,g,g′,pk′.sub.j,g.sup.s.sup.1C.sub.1.sup.−c,pk.sub.e.sup.s.sup.1g.sup.s.sup.2C.sub.2.sup.−c,g′.sup.s.sup.2pk′.sub.j.sup.−c).

[0239] Reveal. When a protocol participant voluntarily wants to reveal the link between its old key pk.sub.i and its new key pk′.sub.j, it may create a proof that both are based on the same secret key as follows:

ρ←.sub.R.sub.q

t.sub.1←g.sup.ρ

t.sub.2←g′ρ

c←H.sub.1(pk.sub.i,g,pk′.sub.j,g′,t.sub.1,t.sub.2)

s←ρ+c.Math.sk.sub.i mod q

Return (c,s)

[0240] This proof can be verified by checking that

c=H.sub.1(pk.sub.i,g,pk′.sub.j,g′,g.sup.spk.sub.i.sup.−c,g′.sup.spk′.sub.j.sup.−c).

[0241] While there are shown and described presently preferred embodiments of the invention, it is to be distinctly understood that the invention is not limited thereto but may be otherwise variously embodied and practiced within the scope of the following claims.