Patent Description:
Further aspects relate to a computer-implemented method, a node of a distributed network and a corresponding computer program product.

In distributed networks a plurality of nodes are arranged in a distributed fashion. In distributed networks computing, software and data are spread out across the plurality of nodes. The nodes establish computing resources and the distributed networks may use distributed computing techniques.

An example of distributed networks are blockchain networks. Blockchain networks are consensus-based, electronic ledgers based on blocks. Each block comprises transactions and other information. Furthermore, each block contains a hash of the previous block so that blocks become chained together to create a permanent, unalterable record of all transactions which have been written to the blockchain. Transactions may call small programs known e.g. as smart contracts.

In order for a transaction to be written to the blockchain, it must be "validated" and agreed upon by the network. In other words, the network nodes have to reach consensus on blocks to be written to the blockchain. Such a consensus may be achieved by various consensus protocols.

In one type of blockchain networks, consensus is achieved by using a proof-of-work algorithm.

Another type of consensus protocols is based on a proof-of-stake algorithm. Such proof-of-stake protocols have the advantage that they do not require time-consuming and energy-intensive computing. In proof-of-stake based blockchain networks e.g. the creator of the next block is chosen via combinations of random selection as well as the stake of the respective node in the network.

Apart from cryptocurrencies, distributed networks may be used for various other applications.

In particular, they may be used for providing decentralized and distributed computing capabilities and services.

The document "<NPL> provides an overview of a secure, performant and flexible consensus mechanism of the Dfinity blockchain computer.

The document by <NPL> discloses a secure and scalable Proof-of-Notarized-Work Based Consensus Mechanism.

One challenge of such distributed networks which provide distributed computing services is to provide randomness to the nodes of a replicated computing cluster in a secure and efficient way.

Accordingly, one object of an aspect of the invention is to provide a distributed network having an advantageous mechanism for providing randomness to the nodes of a replicated computing cluster.

According to an embodiment of a first aspect of the invention there is provided a distributed network which comprises a replicated computing cluster. The replicated computing cluster comprises a plurality of nodes, wherein each of the plurality of nodes of the replicated computing cluster is configured to run a replica and each of the replicas is configured to run one or more computational units. The replicated computing cluster is configured to perform consecutive consensus rounds to reach a consensus on a sequence of payloads and to perform consecutive processing rounds comprising a consecutive processing of the sequence of payloads in a deterministic and replicated manner. The distributed network is characterized in that the replicated computing cluster is configured to perform consecutive computations of a random seed for each of the payloads of the sequence of payloads and to use the random seed of a respective payload of the sequence of payloads to provide randomness to the payload. The respective computation of the random seed for a respective payload is performed only after a consensus on the respective payload has been reached.

Such an embodied method allows the provision of randomness to the replicas of a replicated computing cluster in a secure way, in particular in a way that cannot be biased by adversaries. This allows the replicas and in particular the computational units which run on the replicas to perform computations based on the randomness in a replicated setting in a secure manner.

According to the embodied method, each of the replicas performs processing rounds and processes during each of the processing rounds a payload that has been allocated/assigned to the respective processing round. The payload of a processing round may comprise a plurality of payload instances or in other words transactions. The payload instances may be embodied in particular as messages that shall be processed by the replicated computing cluster.

The replicated computing cluster computes for each of the payloads of the consecutive processing rounds a random seed. Hence each payload and each of the processing rounds has a corresponding random seed which can be used to provide randomness to the payload. The randomness may be used e.g. to respond to randomness requests of the payload.

The computation of the random seed for a respective payload is performed only after the consensus on the respective payload has been reached. As soon as the consensus on a respective payload has been reached, it is ensured that the payload cannot be changed anymore by an adversary and that the randomness computed afterwards is independent from the payload.

According to embodiments, the distributed network is configured to perform the computation of the random seed by performing a threshold-signature protocol on a predefined input value of a respective processing round. This creates a threshold-signature on the predefined input value. The threshold-signature is then used as random seed for a corresponding payload.

Such a threshold-signature is an efficient and secure solution for providing randomness for a replicated computing cluster. This is based in particular on the property of the threshold signature that its value is unpredictable until a threshold number of signature shares have been executed on the predefined input value by the replicas of the replicated computing cluster.

According to embodiments, the consecutive processing rounds are numbered with a consecutive processing round number and the predefined input value of a respective processing round is the processing round number. The processing round number may be generally any kind of number, in particular an integer.

This is an efficient and reliable scheme to pre-agree on or predefine in advance the input value of the threshold signature.

According to another embodiment, the predefined input value of the threshold-signature protocol is the threshold-signature being created in the previous processing round.

According to such an embodiment the random seeds are chained together and form a chain of input values.

According to embodiments, the threshold-signature protocol is the Boneh-Lynn-Shacham (BLS)-signature protocol.

According to embodiments, the distributed network is configured to perform a distributed key generation protocol for or by the plurality of nodes of the replicated computing cluster. The distributed key generation protocol generates a verification key of a public-key threshold signature scheme and a set of corresponding secret key shares for the nodes of the replicated computing cluster. As a result each of the nodes of the replicated computing cluster has an individual secret key share which can be used to participate in the threshold-signature protocol and execute a signature share on the predefined input value.

According to another embodiment, the distributed network may be configured to perform the computation of the random seed by performing a coin-flipping protocol.

According to an embodiment, the distributed network is configured to perform a consecutive processing of input blocks of a blockchain. Each of the input blocks comprises a payload of the sequence of payloads.

According to such an embodiment the blocks and hence also the payloads are chained together. This makes the payloads resistant to modification. More particularly, the blocks and its payloads cannot be altered retroactively without alteration of all subsequent blocks.

According to embodiments each of the replicas is configured to process during each of the consecutive processing rounds a batch comprising the payload of the respective processing round and a random seed. Such a batchwise processing facilitates an efficient and fast data processing. According to such an embodiment each batch comprises a pair of a payload and a random seed. These pairs are then used during the corresponding processing round for the processing of the payload and for responses to payload requests.

According to an embodiment, the distributed network comprises a consensus layer and a messaging layer. The consensus layer is configured to perform a consensus protocol for reaching consensus on the respective payloads of the sequence of payloads to be processed by the replicated computing cluster, to perform the computation of the random seeds and to provide the payloads and the random seeds to the messaging layer.

The messaging layer serves as upper layer and orchestrates a batchwise processing of the batches.

The consensus layer may be configured to deliver the batch of a respective processing round to the messaging layer once a consensus on the corresponding payload has been reached and once the corresponding random seed has been computed.

According to embodiments, the processing rounds comprise consecutive processing round numbers X and the distributed network is configured to start to compute a random seed RSx+<NUM> for the batch of a subsequent processing round X+<NUM> after a consensus on the payload for a given processing round X has been reached. The distributed network may be further configured to collect during the processing of the given processing round X randomness requests of payload instances and to provide responses to the randomness requests of the payload instances of the given processing round X in the subsequent processing round X+<NUM> based on the random seed RSx+<NUM>.

According to such an embodiment the payload instances of a given payload which require randomness are not served in the given processing round, but they have to wait for the next processing round for a response to their randomness requests. In other words, randomness requests are handled in an asynchronous manner. The processing round number may be generally any kind of number, in particular an integer. In a given processing round X, the replicated computing cluster collects all randomness requests and in the subsequent processing round X+<NUM> responses to the randomness requests of processing round X are provided which derive their randomness from the random seed of processing round X+<NUM>. Since the random seed of processing round X+<NUM> was created after a consensus on the payload X has been reached, the random seed X+<NUM> is not bias-able by the payload X.

Such an embodiment keeps the latency of the replicated computing cluster minimal. As usually the computation of the random seed takes less time than the reaching of a consensus on the next payload, a batch X can usually be immediately delivered from the consensus layer to the messaging layer as soon as a consensus on the respective payload has been reached.

According to embodiments, the distributed network may be configured to add the responses to the randomness requests to an induction pool of the messaging layer.

According to another embodiment, the processing rounds comprise consecutive processing round numbers X and the distributed network is configured to start to compute a random seed RSX for the batch of a processing round X after a consensus on the payload for the processing round X has been reached. After computing the random seed it is added to the batch of the processing round X. The distributed network, more particularly the replicas of the replicated computing cluster, provide a response to randomness requests of the payload instances of the processing round X based on the random seed RSX.

According to such an embodiment the payload instances of a given payload which require randomness are served in the same given processing round. In other words, randomness requests are handled in a synchronous manner. This comes at the cost of some latency, as the random seed can only be computed after a consensus on the payload of the respective processing round has been reached.

According to embodiments, the distributed network is configured to derive during a respective processing round a plurality of random values from the random seed of the respective processing round. In this respect, the random seed provides an initial randomness which serves as the basis for deriving further randomness. Accordingly, each of the randomness request of a given payload may receive a different randomness.

According to embodiments, the distributed network is configured to run a pseudorandom number generator. The pseudorandom number generator is configured to use the random seed of a respective processing round as input seed value.

According to an embodiment of another aspect a computer-implemented method for operating a distributed network is provided.

According to an embodiment of another aspect of the invention, a node of a distributed network is provided. The node is configured to participate in the consensus rounds, to perform the consecutive processing rounds, to participate in the consecutive computations of a random seed and to use the random seed of a respective payload. Participating in the consensus rounds may include being an active party of the corresponding consensus protocol. Participating in the computations of a random seed may include e.g. being an active party of the threshold-signature protocol.

According to an embodiment of another aspect of the invention, a computer program product for operating a distributed network is provided. The computer program product comprises a computer readable storage medium having program instructions embodied therewith, the program instructions executable by one or more of a plurality of nodes of the distributed network to cause the one or more of the plurality of nodes to perform steps of the method aspect of the invention.

Features and advantages of one aspect of the invention may be applied to the other aspects of the invention as appropriate.

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

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

According to embodiments, distributed networks may be 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.

A computational unit may be defined as a piece of software that is running on the network and which has its own unit/round state. According to embodiments, a computational unit may be defined as a deterministic program.

A verification key: a bit-string of a public key signature scheme intended to be widely publicized. A verification key may also be denoted as public key and may be used e.g. for the verification of digital signatures of the public key signature scheme.

A public-key signature scheme according to embodiments of the invention may comprise e.g. keys of a public-key signature and encryption scheme such as RSA or keys of a public-key signature scheme such as Schnorr or DSA.

Secret key (sk): a bit-string related to a public key, in particular a verification key, enabling some cryptographic operation, in particular digitally signing a message.

Distributed key generation (DKG): a protocol enabling a set of dealers to create a public key, in particular a verification key, and provide a set of receivers with a secret key share of the corresponding secret key.

(n,t)-threshold key/threshold secret key: Such a threshold key has a threshold t and a number of secret key shares s1,. ,sn such that any t secret key shares enable reconstruction of the secret key, while t-<NUM> shares do not suffice to determine the secret key.

A threshold-signature protocol is a protocol for executing a threshold signature, wherein any t secret key shares enable the execution of a valid threshold-signature under the threshold public key/verification key, while t-<NUM> shares do not suffice to execute a valid signature.

According to embodiments, the Feldman protocol [Fel87], joint Feldman protocol [Ped91] and the GJKR protocol [GJKR99] may be used as distributed key generation protocols. These protocols are e.g. published as follows:
[Fel87] Paul Feldman. A practical scheme for non-interactive verifiable secret sharing.

According to embodiments, the signature protocol as described e.g. in the document <NPL>, may be used as threshold-signature protocol.

A coin flipping protocol may be defined as a protocol which allows mutually distrustful parties to generate a common unbiased random value, guaranteeing that even if a predefined threshold number of the parties is malicious, they cannot bias the random value.

Such a coin-flipping protocol may be embodied e.g. as the protocol as described in:.

A pseudorandom number generator (PRNG) is module for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. As the generated sequence of numbers is determined by an initial seed value, the sequence is not truly random, but pseudorandom.

<FIG> shows an exemplary block diagram of a distributed network <NUM> according to an embodiment of the invention.

The distributed network <NUM> comprises a plurality of nodes <NUM>, which may also be denoted as network nodes <NUM>. The plurality of nodes <NUM> are assigned to a plurality of replicated computing clusters <NUM>. The replicated computing clusters <NUM> establish subnetworks and may be in the following also denoted as subnetworks <NUM>. In the example of <FIG>, four subnetworks <NUM> denoted with SNA, SNB, SNC and SND are provided.

Each of the plurality of subnetworks <NUM> is configured to run a set of computational units on each node <NUM> of the respective subnetwork <NUM>. According to embodiments, a computational unit shall be understood as a piece of software, in particular as a piece of software that comprises or has its own unit state.

The network <NUM> comprises communication links <NUM> for intra-subnetwork communication within the respective subnetwork <NUM>, in particular for intra-subnetwork unit-to-unit messages to be exchanged between computational units assigned to the same subnetwork.

Furthermore, the network <NUM> comprises communication links <NUM> for inter-subnetwork communication between different ones of the subnetworks <NUM>, in particular for inter-subnetwork unit-to-unit messages to be exchanged between computational units assigned to different subnetworks.

Accordingly, the communication links <NUM> may also be denoted as intra-subnetwork or Peer-to-Peer (P2P) communication links and the communication links <NUM> may also be denoted as inter-subnetwork or Subnetwork-to-Subnetwork (SN2SN) communications links.

According to embodiments, a unit state shall be understood as all the data or information that is used by the computational unit, in particular the data that the computational unit stores in variables, but also data the computational units get from remote calls. The computational units may be in particular embodied as stateful computational units, i.e. the computational units are designed according to embodiments to remember preceding events or user interactions.

According to embodiments of the invention the subnetworks <NUM> are configured to replicate the set of computational units across the respective subnetwork <NUM>. More particularly, the subnetworks <NUM> are configured to replicate the unit state of the computational units across the respective subnetwork <NUM>.

The network <NUM> may be in particular a proof-of-stake blockchain network.

The distributed network <NUM> comprises a central control unit CCU, <NUM>. The central control unit <NUM> may comprise a central registry <NUM> to provide network control information to the nodes of the network.

<FIG> illustrates in a more detailed way computational units <NUM> running on nodes <NUM> of the network <NUM>. The network <NUM> is configured to assign each of the computational units which are running on the network <NUM> to one of the plurality of replicated computing clusters/subnetworks, in this example to one of the subnetworks SNA, SNB, SNC or SND according to a subnetwork-assignment. The subnetwork-assignment of the distributed network <NUM> creates an assigned subset of the whole set of computational units for each of the subnetworks SNA, SNB, SNC and SND.

More particularly, <FIG> shows on the left side <NUM> a node <NUM> of the subnetwork SNA of <FIG>. The subnetwork assignment of the distributed network <NUM> has assigned a subset of four computational units <NUM> to the subnetwork SNA more particularly the subset of computational units CUA1, CUA2, CUA3 and CUA4. The assigned subset of computational units CUA1, CUA2, CUA3 and CUA4 runs on each node <NUM> of the subnetwork SNA and establishes a replica <NUM>. Furthermore, the assigned subset of computational units CUA1, CUA2, CUA3 and CUA4 is replicated across the whole subnetwork SNA such that each of the computational units CUA1, CUA2, CUA3 and CUA4 traverses the same chain of unit states. This may be implemented in particular by performing an active replication in space of the unit state of the computational units CUA1, CUA2, CUA3 and CUA4 on each of the nodes <NUM> of the subnetwork SNA.

Furthermore, <FIG> shows on the right side <NUM> a node <NUM> of the subnetwork SNB of <FIG>. The subnetwork assignment of the distributed network <NUM> has assigned a subset of <NUM> computational units <NUM> to the subnetwork SNB, more particularly the assigned subset of computational units CUB1, CUB2 and CUB3. The assigned subset of computational units CUB1, CUB2 and CUB3 runs on each node <NUM> of the subnetwork SNB, is replicated across the whole subnetwork SNB and establishes replicas <NUM>.

<FIG> illustrates the creation of blocks in distributed networks according to embodiments of the invention. The blocks may be in particular input blocks which are to be processed by the computational units of the replicas of a replicated computing cluster. The input blocks which are to be processed by the replicated computing cluster have been agreed upon by a consensus subset of the respective nodes/replicas of the replicated computing cluster.

In this exemplary embodiment three input blocks <NUM>, <NUM> and <NUM> are illustrated. Block <NUM> comprises a plurality of transactions of a payload X, namely the transactions T_X. <NUM>, T_X. <NUM>, and possibly further transactions indicated with dots. Block <NUM> comprises also a plurality of transactions of a payload X+<NUM>, namely the transactions T_X+<NUM>, T_X+<NUM>,and possibly further transactions indicated with dots. Block <NUM> also comprises a plurality of transactions of a payload X+<NUM>, namely the transactions T_X+<NUM>, T X. <NUM>+<NUM>,and possibly further transactions indicated with dots. According to embodiments, the input blocks <NUM>, <NUM> and <NUM> may be chained together. More particularly, each of the blocks may comprise a block hash of the previous block. This cryptographically ties the current block to the previous block(s).

According to embodiments the transactions may be denoted as payload instances. According to embodiments the transaction may be messages which are to be executed by the nodes/replicas of the replicated computing cluster.

According to embodiments, the input blocks <NUM>, <NUM> and <NUM> may be created by a proof-of-stake consensus-protocol.

However, it should be noted that the input blocks generated by the consensus component do not need to be chained together according to embodiments. Rather any consensus protocol that reaches some kind of consensus between the nodes on the transactions of the payload may be used according to embodiments.

<FIG> illustrates a batchwise processing of batches of two consecutive processing rounds X and X+<NUM> according to an embodiment of the invention. More particularly, at the processing round X a batch <NUM> is processed. The batch <NUM> comprises a payload X and a random seed RSX which establishes a randomness X. The processing round X takes a former state X-<NUM> as input and provides as a result a state X. Likewise, in the next processing round X+<NUM> a batch X+<NUM> comprising a payload X+<NUM> and a random seed RSx+<NUM> establishing a randomness X+<NUM> is processed.

By this batchwise or blockwise processing, the replicas traverse a chain of round states of state heights X-<NUM>, X, X+<NUM>,.

<FIG> shows a layer model <NUM> illustrating main layers of a distributed network according to embodiments. The layer model <NUM> comprises an execution layer <NUM> which is configured to provide an execution environment for the execution of payloads, in particular (execution) messages. The layer model <NUM> further comprises a messaging layer <NUM> which is configured to serve as an upper layer for communication of the network. More particularly, the messaging layer <NUM> is configured to route inter-subnet messages between computational units of different subnets. Furthermore, the messaging layer <NUM> is configured to route (ingress) messages from users of the network to computational units of the network.

The layer model <NUM> further comprises a plurality of consensus layers <NUM> which are configured to perform a consensus protocol for reaching consensus on the respective payloads of the sequence of payloads to be processed by a corresponding replicated computing cluster. The may include to receive inter-subnet messages from different subnets as well as ingress messages and to organize them, in particular by agreeing on a processing order, in a sequence of input blocks which are then further processed by the respective subnet/replicated computing cluster. The consensus layers <NUM> are further configured to compute the random seeds for the payloads of the respective processing rounds.

In addition, the layer model <NUM> comprises a peer-to-peer (P2P) layer <NUM> that is configured to organize and drive communication between the nodes of a single subnet/replicated computing cluster.

<FIG> shows a schematic block diagram of protocol components <NUM> of a client <NUM> of a replicated computing cluster/subnet.

Full arrows in <FIG> are related to unit-to-unit messages and ingress messages. Dashed arrows relate to system information.

The protocol components <NUM> comprise a messaging component <NUM> which is configured to run the messaging protocol and an execution component <NUM> configured to run an execution protocol for executing messages, in particular for executing unit-to-unit messages and/or ingress messages. The protocol components <NUM> further comprise a consensus component <NUM> configured to run a consensus protocol, a networking component <NUM> configured to run a networking protocol, a state manager component <NUM> configured to run a state manager protocol, an X-Net component <NUM> configured to run a cross-subnet transfer protocol and an ingress message handler component <NUM> configured to handle ingress message received from an external user of the network. The protocol components <NUM> comprise in addition a crypto-component <NUM>. The crypto-component <NUM> co-operates with a security component <NUM>. Furthermore, a reader component <NUM> may provide information of the network such as the assignment of nodes to subnets, node public keys, assignment of computational units to subnets etc..

The messaging component <NUM> and the execution component <NUM> are configured such that all computation, data and state in these components is identically replicated across all nodes of the respective subnet, more particularly all honest nodes of the respective subnet. This is indicated by the wave-pattern background of these components.

Such an identical replication is achieved according to embodiments on the one hand by virtue of the consensus component <NUM> that ensures that the stream of inputs to the messaging component <NUM> is agreed upon by the respective subnet and thus identical for all nodes, more particularly by all honest nodes. On the other hand, this is achieved by the fact that the messaging component <NUM> and the execution component <NUM> are configured to perform a deterministic and replicated computation.

The X-Net Transfer component <NUM> sends message streams to other subnets and receives message streams from other subnets.

The execution component <NUM> receives from the messaging component <NUM> a unit state of the computational unit and an incoming message for the computational unit, and returns an outgoing message and the updated unit state of the computational unit.

The state manager component <NUM> comprises a certification component 65a. The certification component 65a is configured to certify the output streams of the respective subnet.

<FIG> illustrates a communication mechanism between the consensus layer <NUM> and the messaging layer <NUM> as described with reference to <FIG>. According to the embodiment shown in <FIG>, the consensus layer <NUM> provides batches <NUM> comprising the payloads from finalized input blocks and random seeds to the messaging layer <NUM>. A finalized input block shall be understood as an input block on which the replicas have reached a (final) consensus. Upon receipt the messaging layer <NUM> orchestrates then the batchwise processing of the batches <NUM>. The consensus layer <NUM> delivers according to embodiments the batches <NUM> of a respective processing round to the messaging layer <NUM> once a consensus on the corresponding payload has been reached and once the corresponding random seed has been computed. According to other embodiments the payload and the random seed of a respective processing round may also be delivered separately by the consensus layer <NUM> to the messaging layer <NUM> and then executed upon receipt of both as a batch during the corresponding processing round.

<FIG> shows an exemplary timing diagram of the consensus mechanism and the computation of the random seed according to an embodiment of the invention.

At first, at a step <NUM>, the replicas of a replicated computing cluster agree by means of a consensus protocol on a payload X, e.g. by agreeing on an input block X or in other words by reaching a (final) consensus on the input block X. As mentioned, such an input block may be referred to as a finalized input block. Then, only after reaching a consensus on the payload X, the replicas compute, at a step <NUM>, a random seed RSX. Thereafter, a corresponding batch X comprising the payload X and the random seed RSX may be provided by the consensus layer <NUM> to the messaging layer <NUM>.

This timing scheme is repeated for the subsequent batches. Accordingly, at a step <NUM>, it is at first agreed on the payload X+<NUM> and only thereafter, at a step <NUM>, it is started to compute the random seed RSX+<NUM>.

According to such a scheme the random seed RSX may be used for the payload X or in other words the random seed RSX may be used during the corresponding processing of the payload X for randomness requests of the payload X. Hence the random seed of a batch may be used for the payload of the same batch in a synchronous manner. This has the advantage that the payloads of a respective batch can be served immediately with the randomness provided within the same batch. However, this advantage may come at the cost of some latency due to the sequential computing of the payload and the random seed.

<FIG> shows an exemplary timing diagram of the consensus mechanism and the computation of the random seed according to another embodiment of the invention.

According to such an embodiment the random seed RSX for the batch X is computed in parallel to performing the consensus protocol for reaching consensus on the payload of batch X. More particularly, as soon as the replicated computing cluster has reached a consensus on the payload of the batch X, the replicated computing cluster starts to compute a random seed RSX+<NUM> for the batch X+<NUM> of a subsequent processing round X+<NUM>.

Accordingly, at a step <NUM>, the replicas of a replicated computing cluster compute the random seed RSX for batch X. In parallel, the replicas perform, at a step <NUM>, a consensus protocol to agree on a payload X. The step <NUM> may be already started as soon as the replicas have reached consensus on the payload X-<NUM> of the previous batch X-<NUM> (not shown). As usually the computation of the random seed is shorter than the reaching of a consensus on a payload/input block, the randomness/random seed for the batch X is usually already available when the consensus on the corresponding payload X has been reached. Then, as soon as the consensus on the payload X has been reached, the replicas may start, at a step <NUM>, with the computation of the next random seed RSX+<NUM>. And again, in parallel, the replicas may perform, at a step <NUM>, a consensus protocol to agree on a payload X+<NUM>.

As according to such an embodiment the computation of the random seed RSX of a batch X may or often will be finished before an agreement on the corresponding block X of the batch X has been reached, the random seed RSX is not used to provide randomness for the processing of the payload X, but only for the processing of the next payload X+<NUM>.

Accordingly, during the processing of the given processing round X, randomness requests of the payload instances, e.g. of messages, of the payload X are collected. Then, in the subsequent processing round X+<NUM>, the random seed RSX+<NUM> is used to provide randomness for the messages of the payload X which require randomness. Hence according to such an embodiment the messages of the payload X which do not require randomness may be processed immediately, while the messages which require randomness have to wait for responses on their randomness requests. The responses to the randomness requests of the payload instances of the given processing round X are provided in the subsequent processing round X+<NUM> based on the random seed RSX+<NUM>. And as the random seed RSX+<NUM> has been computed after an agreement has been reached on the payload X, the random seed RSX+<NUM> cannot be biased by the payload X.

As computing the random seed typically takes less time than reaching agreement on a payload, a batch X can be delivered and processed as soon as the corresponding payload X has been finally agreed upon. This provides advantages in terms of latency.

<FIG> shows a flow chart of methods steps of a computer-implemented method for processing a sequence of payloads by a plurality of replicas in a replicated manner.

The method performs regularly, at loops <NUM>, a consensus protocol to reach a consensus on input blocks comprising a payload that shall be executed by a respective replicated computing cluster, in particular by a subnetwork. The consensus protocol may be performed by a consensus subset of the nodes/replicas of the network, in particular by a consensus subset of a subnetwork. The loop <NUM> comprises steps <NUM> at which the nodes/replicas of the consensus subset reach a consensus on a new input block and a corresponding payload. The input blocks may be numbered with an increasing height index N. N may be an increasing integer, i.e. e.g. <NUM>, <NUM>, <NUM>, <NUM>. The height index may also be denoted as block height.

As soon as the replicas have reached a consensus on an input block X and its corresponding payload X, the replicas start, at a step <NUM>, to compute a random seed RSX for a batch X of a corresponding processing round X. Once the random seed RSX has been computed, the consensus layer delivers, at a step <NUM>, the batch X comprising the payload X and the random seed RSX to the messaging layer.

Then, at a step <NUM>, the replicas process batch X and process the payload X and randomness requests of the payload X with the randomness/random seed RSX.

<FIG> shows an embodiment of keys <NUM> which may be generated by a distributed threshold key generation protocol. The keys <NUM> may be used by the nodes of a replicated computing cluster to perform a threshold-signature protocol and to sign a predefined input value with a threshold-signature. Such a threshold-signature may be used according to embodiments to compute the random seed. More particularly, the threshold-signature on the input value may be used as random seed.

It is assumed for this example that a number N of nodes participate in the distributed key generation protocol. Each of the N nodes have a secret key share ski, wherein i = <NUM>,. The N nodes have generated jointly a common public key pk, wherein a predefined threshold, e.g. at least two thirds or a third of the nodes need to use their secret key shares to create a joint signature σpk on the predefined input value. The public verification key pk can then be used to verify the joint signature. According to embodiments the threshold-signature may be executed on the respective processing round number X as predefined input value. According to other embodiments, the threshold-signature of a previous processing round may be used as input value for the threshold-signature of the next processing round.

Referring now to <FIG>, a flow chart of methods steps of a computer-implemented method for processing a sequence of payloads by a plurality of replicas in a replicated manner is shown. The method performs regularly, at loops <NUM>, a consensus protocol to reach a consensus on input blocks comprising a payload that shall be executed by a respective replicated computing cluster, in particular by a subnetwork. The loops <NUM> comprises steps <NUM> at which the nodes/replicas of the consensus subset reach a consensus on a new input block X. The input blocks may be numbered with an increasing height index X corresponding to a processing round number.

Once the consensus on an input block X has been reached, the replicated computing cluster provides, at a step <NUM>, a corresponding batch X comprising the payload of the input block X and a random seed RSX to the messaging layer <NUM> of the network (see <FIG>). The random seed RSX has been computed beforehand and/or in parallel to the execution of the consensus protocol for the input block X.

At a step <NUM>, the replicas process the payload of batch X and randomness requests RR from the previous batch X-<NUM>. More particularly, the randomness requests RR of the payload instances, e.g. the messages, of the previous batch X-<NUM> receive as response a randomness which is based on the random seed RSX of the current batch X. The responses may be added to an induction pool of the messaging layer <NUM>.

Furthermore, at a step <NUM>, the randomness requests of payload instances of the current batch X are collected. Step <NUM> may be performed in parallel to step <NUM>.

The steps <NUM>, <NUM> and <NUM> establish a processing round X of a plurality of consecutive processing rounds.

Furthermore, as soon as a consensus on the input block X has been reached, the replicas start, at a step <NUM>, to compute a random seed RSX+<NUM> for the batch of a subsequent processing round X+<NUM>. At a subsequent step <NUM> the consensus layer <NUM> provides the random seed RSX+<NUM> for the next batch X+<NUM>. The steps <NUM> and <NUM> may be performed in parallel to the processing round X.

At a step <NUM>, the consensus protocol reaches a consensus on the next input block X+<NUM>. This triggers on the one hand, at a step <NUM>, the computation of the random seed RSX+<NUM> of the subsequent batch X+<NUM>. In addition, it triggers the next processing round X+<NUM>. The latter includes, at a step <NUM>, the providing of a batch X+<NUM> to the messaging layer <NUM>. The batch X+<NUM> comprises the random seed RSX+<NUM> which has been already computed at step <NUM>.

At a step <NUM>, the replicas process the payload of batch X+<NUM> and randomness requests RR from the previous batch X. More particularly, the randomness requests RR of the payload instances of the previous batch X receive as response a randomness which is based on the random seed RSX+<NUM> of the batch X+<NUM>.

Furthermore, at a step <NUM>, the randomness requests of payload instances of the batch X+<NUM> are collected. These randomness requests will receive a response in the next processing round X+<NUM>.

The above described scheme may then be iterated as long as desired.

Referring now to <FIG>, a more detailed block diagram of a network node <NUM> according to embodiments of the invention is shown, e.g. of the network <NUM> of <FIG>. The network node <NUM> establishes a computing node that may perform computing functions and may hence be generally embodied as computing system or computer. The network node <NUM> may be e.g. a server computer. The network node <NUM> may be configured to perform a computer-implemented method for operating a distributed network. The network node <NUM> may be operational with numerous other general purpose or special purpose computing system environments or configurations.

The network node <NUM> 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 <NUM> is shown in the form of a general-purpose computing device. The components of network node <NUM> may include, but are not limited to, one or more processors or processing units <NUM>, a system memory <NUM>, and a bus <NUM> that couples various system components including system memory <NUM> to processor <NUM>.

Bus <NUM> 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.

Network node <NUM> typically includes a variety of computer system readable media.

System memory <NUM> can include computer system readable media in the form of volatile memory, such as random access memory (RAM) <NUM> and/or cache memory <NUM>. Network node <NUM> may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, storage system <NUM> 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 <NUM> by one or more data media interfaces. As will be further depicted and described below, memory <NUM> 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.

Program/utility <NUM>, having a set (at least one) of program modules <NUM>, may be stored in memory <NUM> 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 <NUM> generally carry out the functions and/or methodologies of embodiments of the invention as described herein. Program modules <NUM> may carry out in particular one or more steps of a computer-implemented method for operating a distributed network e.g. of one or more steps of the methods as described above.

Network node <NUM> may also communicate with one or more external devices <NUM> such as a keyboard or a pointing device as well as a display <NUM>. Such communication can occur via Input/Output (I/O) interfaces <NUM>. Still yet, network node <NUM> can communicate with one or more networks <NUM> 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 <NUM>. According to embodiments the network <NUM> may be in particular a distributed network comprising a plurality of network nodes <NUM>, e.g. the network <NUM> as shown in <FIG>. As depicted, network adapter <NUM> communicates with the other components of network node <NUM> via bus <NUM>. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with network node <NUM>.

Aspects of the present invention may be embodied as a system, in particular a distributed network comprising a plurality of subnetworks, a method, and/or a computer program product.

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.

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.

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.

Claim 1:
A distributed network (<NUM>), the distributed network (<NUM>) comprising a replicated computing cluster (<NUM>), the replicated computing cluster (<NUM>) comprising a plurality of nodes (<NUM>), wherein each of the plurality of nodes (<NUM>) of the replicated computing cluster (<NUM>) is configured to run a replica (<NUM>) and each of the replicas (<NUM>) is configured to run one or more computational units (<NUM>); the replicated computing cluster (<NUM>) being configured to
perform consecutive consensus rounds to reach a consensus on a sequence of payloads;
perform consecutive processing rounds comprising a consecutive processing of the sequence of payloads in a deterministic and replicated manner; wherein the distributed network is characterized in that the replicated computing cluster (<NUM>) is configured to
perform consecutive computations of a random seed for each of the payloads of the sequence of payloads; and
use the random seed of a respective payload of the sequence of payloads to provide randomness to the payload; wherein
the respective computation of the random seed for a respective payload is performed only after a consensus on the respective payload has been reached.