Blockchain

Field of invention

The present invention relates to a computer-implemented method, in particular a method of transmitting an output to a node of a blockchain. The invention further relates to a method of configuring a blockchain and an apparatus and system for accessing and/or viewing the blockchain.

Background

A verifiable delay function (VDF) is a function that takes a number of sequential steps (and a significant amount of time) to evaluate, yet gives a unique result that can be verified quickly and efficiently. Due to the use of sequential steps, verifiable delay functions can be implemented that require a large computation time to compute, even for parties running many parallel processors. In other words, a verifiable delay function can be used to set a value that cannot be identified for a significant period of time.

In other words, an input value for a verifiable delay function may be disclosed at a first time t; an output value is then found at a time (t+ δ), where δ depends on the verifiable delay function. Between the times t and (t+5) actions may be taken that depend on this output value, where the unique value is only revealed at the time (t+δ). Such a verifiable delay function may be used for a lottery, where contestants purchase tickets between the times t and (t+δ). The output value will not become known (by anyone) until after the purchase of the tickets - and so the value cannot be determined before purchasing tickets - but once the value is known it can be verified that it relates to the input value - and so the value cannot be altered after the purchase of the tickets.

While the calculation of verifiable delay functions cannot be sped up by the use of parallel processors, it is possible that this calculation could be sped up by developing processors that can calculate each sequential step more quickly. A party that controlled such a processor might be able to calculate (in secret) the output value before the time (t+δ) and therefore could know this value before purchasing a ticket for a lottery. This presents a problem for existing implementations of verifiable delay functions.

Summary of the Disclosure

Aspects and embodiments of the present invention are set out in the appended claims. These and other aspects and embodiments of the invention are also described herein.

According to least one aspect of the present disclosure, there is described a computer-implemented method performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; determining a parameter relating to the output value of the verifiable delay function; generating an output in dependence on the parameter; and transmitting the output to a second node of the blockchain.

Preferably, the parameter relates to the determination of the output value.

Variable reward

Preferably, determining the parameter comprises determining one or more of: a calculation time relating to the output value; and a number of steps relating to the output value, preferably the number of steps performed to obtain the output value.

Preferably, generating the output comprises determining a reward for a party involved in the determination of the output value of the verifiable delay function.

Preferably, the method comprises determining a reward for a party involved in the determination of the output value; and outputting the reward to the second node, preferably wherein the reward is dependent on one or more of: a calculation time relating to the output value; and a number of steps relating to the output value, preferably the number of steps performed to obtain the output value.

According to least one aspect of the present disclosure, there is described a computer-implemented method performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; determining one or more of: a calculation time relating to the output value; and a number of steps relating to the output value, preferably the number of steps performed to obtain the output value; determining a reward for a party involved in the determination of the output value in dependence on the calculation time and/or the number of steps; and transmitting the reward to a second node of the blockchain.

Preferably, the reward is a function of the calculation time. Preferably, the reward is a decreasing function of the calculation time. Preferably, the reward is a monotonically decreasing function of the calculation time.

Preferably, the reward is a function of the number of steps. Preferably, the reward is an increasing function of the number of steps. Preferably, the reward is a monotonically increasing function of the number of steps.

Preferably, the reward relates to an expected reward.

Preferably, the reward relates to the determination of a plurality of output values.

Preferably, the reward relates to one or more of: an amount of a cryptocurrency; an eligibility to participate in the building of a consensus on the history of the blockchain; and an eligibility to participate in the addition of a block to the blockchain.

Preferably, the reward is redeemable and/or is realised when the reference is utilised. Preferably, the reward is redeemable and/or is realised when the reference is referenced in a future block of the blockchain. Preferably, the reward is redeemable and/or is realised when a function that is dependent on the output value is executed. Preferably, the reward is redeemable and/or is realised in dependence on a request for the output value being made and/or met.

Preferably, the reward is dependent on one or more of: an amount remaining in a reward pool, preferably wherein the reward pool is a limited reward pool; one or more references to further output values submitted by further nodes of the blockchain, preferably a relative calculation time as compared to the further output values and/or a relative number of steps relating to the output value as compared to the further output values; and a time of submission relating to the reference, preferably a time of submission relative to further submissions of references.

Variable steps

Preferably, determining the parameter comprises determining a calculation time relating to the output value.

Preferably, generating the output comprises determining an updated number of steps relating to a future execution of the verifiable delay function based on the calculation time.

Preferably, the method further comprises: determining a calculation time relating to the output value; determining an updated number of steps relating to a future execution of the verifiable delay function based on the calculation time; and outputting the updated number of steps to a second node of the blockchain.

According to least one aspect of the present disclosure, there is described a computer-implemented being performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; determining a calculation time relating to the output value; determining an updated number of steps relating to a future execution of the verifiable delay function based on the calculation time; and transmitting the updated number of steps to a second node of the blockchain.

Preferably, the updated number of steps is dependent on one or more of: a target minimum calculation time; a target expected calculation time; and a target maximum calculation time.

Preferably, the updated number of steps is arranged so that a future calculation time relating to a future output value exceeds the target minimum calculation time.

Preferably, the updated number of steps is determined based on a target calculation time and a determined time per step.

Preferably, the method further comprises identifying a plurality of calculation times relating to a plurality of output values, and determining the updated number of steps based on the plurality of calculation times.

Preferably, the updated number of steps is determined based on one or more of: the average of the plurality of calculation times; the mean of the plurality of calculation times; the median of the plurality of calculation times; the minimum of the plurality of calculation times; and the maximum of the plurality of calculation times. Preferably, determining an updated number of steps comprises adjusting an existing number of steps. Preferably, the existing number of steps is defined in a previous block of the blockchain. Preferably, the updated number of steps is greater than the existing number of steps if the calculation time is beneath a target calculation time and/or a target minimum calculation time.

Preferably, the blockchain comprises a blockchain with a finite maximum time between the addition of blocks. Preferably, the updated number of steps relates to a calculation time greater than the finite maximum time. Preferably, the updated number of steps relates to a calculation time greater than an expected maximum time relating to the addition of blocks to the blockchain. Preferably, the expected maximum time relates to the probability of a block being added to the blockchain. Preferably, the probability of a block being added to the blockchain in the expected maximum time is at least 90%, at least 95%, at least 99%, and/or at least 99.9%.

Variable acceptable value

Preferably, the method further comprises comparing the output value to an acceptable range of output values; and outputting the reference to the second node of the blockchain in dependence on the output value being within the acceptable range. Preferably, determining the parameter comprises determining an acceptable range of output values.

Preferably, generating the output comprises comparing the output value to the acceptable range of output values.

Preferably, transmitting the output comprises transmitting the output to the second node of the blockchain in dependence on the output value being within the acceptable range of output values;

Preferably, determining the acceptable range of output values comprises identifying the acceptable range of output values in a block of the blockchain.

Preferably, determining the acceptable range of output values comprises deriving the acceptable range in dependence on a calculation time and/or a number of steps relating to the output value. Preferably, determining the acceptable range of output values comprises determining the acceptable range of output values as a function of the number of steps calculated to obtain the output value. Preferably, determining the acceptable range of output values comprises determining the acceptable range of output values as an increasing function of the number of steps calculated to obtain the output value.

Preferably, the acceptable range is dependent on the calculation time and/or a/the number of steps relating to the output value. Preferably, the acceptable range is a function of the number of steps calculated to obtain the output value. Preferably, the acceptable range is an increasing function of the number of steps calculated to obtain the output value.

According to least one aspect of the present disclosure, there is described a computer-implemented being performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; determining an acceptable range of output values in dependence on a calculation time and/or a number of steps relating to the output value; comparing the output value to the acceptable range of output values; and transmitting the reference to a second node of the blockchain in dependence on the output value being within the acceptable range.

Preferably, the acceptable range is a function of the number of steps calculated to obtain the output value. Preferably, the acceptable range is an increasing function of the number of steps calculated to obtain the output value.

Preferably, a minimum number of steps is greater than one. Preferably, a minimum number of steps is substantially greater than one, more preferably greater than ten, yet more preferably greater than one hundred, even more preferably greater than one thousand.

Preferably, the addition of a block to the blockchain is dependent on the output value being within the acceptable range. Preferably, the maximum number of steps is dependent on a target maximum time for the addition of blocks to the blockchain. Preferably, the acceptable range is arranged to include any output value if a/the number of steps is equal to and/or greater than a/the maximum number of steps. Preferably, the acceptable range is arranged to include no output value if a/the number of steps is lower than a/the minimum number of steps.

Preferably, the acceptable range is arranged to increase between a/the minimum number of steps and a/the maximum number of steps.

Preferably, the acceptable range is arranged to increase between a/the minimum number of steps and a/the maximum number of steps based on a polynomial equation.

Preferably, the acceptable range is arranged to increase linearly between a/the minimum number of steps and a/the maximum number of steps.

Preferably, the acceptable range is arranged to increase exponentially between a/the minimum number of steps and a/the maximum number of steps.

General

Preferably, the method comprises determining a number of steps relating to the output value. Preferably, the method comprises determining that the number of steps exceeds a minimum required number of steps. Preferably, the minimum required number of steps is determined based on a previous block of the blockchain. Preferably, the minimum required number of steps and an input value for the verifiable delay function are both determined based on the same previous block of the blockchain.

Preferably, the output value is determined using a number of steps defined in a first previous block of the blockchain; and the output value is determined using an input value defined in a second previous block of the blockchain.

Preferably, the first previous block is an ancestor of the second previous block. Preferably, the first previous block is an immediately previous block of the blockchain.

Preferably, the calculation time is determined based on an input time relating to a block on which the input value is based.

Preferably, the calculation time is determined based on an output time relating to a block in which the reference is recorded.

Preferably, the input time and/or the output time is determined based on a timestamp of the input block and/or the output block.

Preferably, the reference comprises one or more of: the output value; a number of steps relating to the output value; an input value relating to the output value; and one or more intermediate values relating to the output value; a proof relating to the output value (preferably a proof that the output value has been determined based on the verifiable delay function and/or a/the input value); a reference to a plurality of output values; a reference to a share verification contract (SVC); and a reference to a smart contract.

Preferably, the verifiable delay function is configured so that an input value for the verifiable delay function is based on: publicly available information, preferably wherein the input value for the verifiable delay function is based solely on publicly available information; and/or a previous block of the blockchain, preferably wherein the input value comprises a hash of the previous block.

Preferably, the reference is used for one or more of: a random number beacon; a consensus mechanism of the blockchain; a public consensus mechanism of the blockchain; an anti-sybil factor of the blockchain; a proof of work; and a proof of expended computational power.

Preferably, the blockchain comprises a public blockchain and/or a non-permissioned blockchain.

Preferably, outputting the reference comprises one or more of: proposing a block for addition to the blockchain; adding a block to the blockchain; transmitting a message to one or more nodes of the blockchain; validating and/or signing a block of the blockchain; and transmitting a block of the blockchain to one or more nodes of the blockchain. According to an aspect of the present disclosure, there is described a computer-implemented method being performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; outputting the reference to a second node of the blockchain.

Variable steps

Preferably, the method comprises determining a calculation time relating to the output value; determining an updated number of steps relating to a future execution of the verifiable delay function based on the calculation time; and outputting the updated number of steps to a second node of the blockchain.

Preferably, the method comprises identifying a reference to an output value of a verifiable delay function; determining a calculation time relating to the output value; determining an updated number of steps relating to a future execution of the verifiable delay function based on the calculation time; and outputting the updated number of steps to a second node of the blockchain.

Preferably, the method comprises determining a number of steps relating to the output value, preferably the number of steps performed to obtain the output value.

Preferably, the method comprises determining a computation time per step relating to the output value.

Preferably, the updated number of steps is determined based on a target calculation time and a time per step determined in relation to the output value.

Preferably, the method comprises identifying a plurality of calculation times relating to a plurality of references, and determining the updated number of steps based on the plurality of calculation times.

Preferably, the method comprises determining a number of steps relating to the output value.

Preferably, the updated number of steps is determined based on one or more previous calculation times relating to one or more previous output values.

Preferably, the calculation time is determined based on an input time relating to a block on which the input value is based and/or the calculation time is determined based on an output time relating to a block in which the reference is recorded. Preferably, the input time and/or the output time are determined based on a timestamp of the input block and/or the output block.

Preferably, the updated number of steps is determined based on one or more previous numbers of steps relating to one or more previous output values.

Preferably, determining the updated number of steps comprises comparing the calculation time to a target calculation time and/or a target range of calculation times.

Preferably, determining the updated number of steps comprises determining whether the calculation time is less than a minimum target calculation time. Preferably, the minimum target calculation time is determined based on a/the previous block of the blockchain.

Preferably, the updated number of steps is determined based on a/the target calculation time and/or a/the target range of calculation times. Preferably, the updated number of steps is determined based on a difference between the calculation time and the target calculation time.

Preferably a block of the blockchain comprises one or more of: an indication of an operation on which the verifiable delay function is based; an indication of a minimum calculation time relating to the solving verifiable delay function; an indication of a maximum calculation time relating to the solving verifiable delay function; an indication of a target minimum calculation time relating to the solving verifiable delay function; an indication of a target maximum calculation time relating to the solving verifiable delay function; an indication of a target calculation time relating to the solving verifiable delay function; and an indication of a target range of calculation times relating to the solving verifiable delay function.

Preferably, determining an updated number of steps comprises adjusting an existing number of steps. Preferably, the existing number of steps is defined in a previous block of the blockchain. Preferably, the updated number of steps is greater than the existing number of steps if the calculation time is beneath a target calculation time and/or a target minimum calculation time.

Preferably, the method comprises: determining an updated operation relating to a future execution of the verifiable delay function based on the calculation time; and outputting the updated operation to a second node of the blockchain.

Preferably, the method comprises determining an updated difficulty relating to a future execution of the verifiable delay function based on the calculation time; determining an updated parameter relating to the updated difficulty; and outputting the updated parameter to a second node of the blockchain.

According to an aspect of the present disclosure, there is described a computer-implemented method being performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; determining a calculation time relating to the output value; determining an updated difficulty relating to a future execution of the verifiable delay function based on the calculation time; determining an updated parameter relating to the updated difficulty; and outputting the updated parameter to a second node of the blockchain.

Preferably, the blockchain comprises a blockchain with a finite maximum time between the addition of blocks. Preferably, the updated number of steps relates to a calculation time greater than the finite maximum time. Preferably, the acceptable range is an increasing function of the number of steps calculated to obtain the output value.

Preferably, the updated number of steps relates to a calculation time greater than a maximum expected time relating to the addition of blocks to the blockchain.

Variable reward

Preferably, the method comprises determining a reward for a party involved in the determination of the output value; and outputting the reward to the second node.

Preferably, the reward is dependent on one or more of: the calculation time; and a number of steps relating to the output value. Preferably, the reward is dependent on the number of steps calculated to obtain the output value.

According to an aspect of the present disclosure, there is described a computer-implemented method being performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; outputting the reference to a second node of the blockchain; wherein the reward is dependent on one or more of: the calculation time; and a number of steps relating to the output value. Preferably, the reward is dependent on the number of steps calculated to obtain the output value.

Preferably, the reward relates to one or more of: an amount of a cryptocurrency; an eligibility to participate in the building of a consensus on the history of the blockchain; and an eligibility to participate in the addition of a block to the blockchain.

Preferably, determining the reward comprises determining one or more of: a previous reference to the output value; a previous reference to a further output value derived from an/the input value from which the output value is derived.

Preferably, the method comprises determining an eligibility of the node to participate in the addition of a block to the blockchain based on the reference. Preferably, the method comprises defining the node as a proposer and/or a validator for a block of the blockchain. Preferably, the method comprises defining the node as a proposer and/or a validator for a current block and/or a future block.

Variable acceptable value

Preferably, the method comprises comparing the output value to an acceptable range of output values; and outputting the reference to the second node of the blockchain in dependence on the output value being within the acceptable range. Preferably, the acceptable range of output values is defined in a block of the blockchain.

Preferably, the acceptable range is dependent on the calculation time and/or a/the number of steps relating to the reference. Preferably, the acceptable range is a function of the number of steps calculated to obtain the output value.

According to an aspect of the present disclosure, there is described a computer-implemented method being performed by a first node of a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; comparing the output value to an acceptable range of output values; and outputting the reference to a second node of the blockchain in dependence on the output value being within the acceptable range.

Preferably, the acceptable range of output values is defined in a block of the blockchain.

Preferably, the method comprises processing the output value before the comparison to the acceptable range, preferably hashing and/or randomising the output value before the comparison.

Preferably, the method comprises normalising the output value before the comparison to the acceptable range.

Preferably, the method comprises determining an updated acceptable range of values; and outputting the updated acceptable range to the second node.

General

Preferably, reference to the output value comprises the output value.

Preferably, the reference comprises one or more of: a number of steps relating to the output value; an input value relating to the output value; and one or more intermediate relating to the output value.

Preferably, the reference to the output value comprises a proof relating to the output value. Preferably, the reference comprises a proof that the output value has been determined based on the verifiable delay function and/or a/the input value.

Preferably, the method comprises the reference comprises one or more of: a reference to a plurality of output values; a reference to a share verification contract (SVC); and a reference to a smart contract.

Preferably, the method comprises determining a processing capability relating to the calculation of the verifiable delay function based on the calculation time.

Preferably, an input value for the verifiable delay function is based on publicly available information. Preferably, the input value for the verifiable delay function is based solely on publicly available information.

Preferably, an input value for the verifiable delay function is based on a previous block of the blockchain. Preferably, the input value comprises a hash of the previous block. Preferably, the previous block is at least 3 blocks deep in the blockchain, at least 6 blocks deep in the blockchain, and/or at least 10 blocks deep in the blockchain.

Preferably, determining the calculation time comprises one or more of: determining a time that has elapsed since the previous block; and determining a number of blocks that have been added to the blockchain since the previous block.

Preferably, outputting the reference comprises providing a random number beacon.

Preferably, the method comprises determining and/or outputting a winner of a lottery based on the output value.

Preferably, the verifiable delay function is based on a repeated operation, preferably a repeated squaring.

Preferably, the reference to the output value is identified in a header of a block.

Preferably, the reference to the output value is identified in a transaction in a block.

Preferably, the method comprises proposing a block for addition to the blockchain based on the updated number of steps. Preferably, the block comprises information relating to the updated number of steps and/or the block comprises the updated number of steps.

According to an aspect of the present disclosure, there is described a computer-implemented method of configuring a blockchain, the method comprising: configuring the blockchain to require a first node of the blockchain to: identify a reference to an output value of a verifiable delay function; and output the reference to a second node of the blockchain.

Preferably, configuring the blockchain comprises configuring consensus rules for the blockchain.

According to an aspect of the present disclosure, there is described a computer-implemented method of proposing a block for addition to a blockchain, the method comprising: identifying a reference to an output value of a verifiable delay function; and recording the reference in the block of the blockchain. According to an aspect of the present disclosure, there is described a blockchain configured such that before a block is proposed for addition to the blockchain by a node, the node is able to and/or required to: identify a reference to an output value of a verifiable delay function; and include the reference in the block of the blockchain.

According to an aspect of the present disclosure, there is described a computer-implemented method being performed by a first node of a public consensus network, the method comprising: identifying a reference to an output value of a verifiable delay function; and outputting the reference to a second node of the public consensus network.

According to an aspect of the present disclosure, there is described an apparatus arranged to carry out the aforesaid method.

Preferably, the apparatus comprises one or more of: a computer implemented device; a display and/or a speaker; a user input. Preferably, the apparatus is arranged to present information relating to the blockchain in dependence on a user request and/or an event.

Preferably, the apparatus is arranged to identify a reference to an output value of a verifiable delay function; and include the reference in a block of the blockchain.

According to another aspect of the present disclosure, there is described an apparatus arranged to store, access, and/or view the aforesaid blockchain and/or the aforesaid public consensus network.

Preferably, the apparatus is arranged to communicate with at least one other apparatus.

Preferably, the apparatus comprises a node of the blockchain and/or the public consensus network. Preferably, the apparatus is arranged to communicate with another node of the blockchain and/or the public consensus network.

According to another aspect of the present disclosure, there is described a system comprising a plurality of apparatuses arranged to store, access, and/or view the aforesaid blockchain and/or the aforesaid public consensus network.

Preferably, each of the apparatuses are arranged to communicate with each other.

Preferably, each of the apparatuses are arranged to communicate so as to propagate blocks of the blockchain to the other apparatuses. The invention extends to any novel aspects or features described and/or illustrated herein.

Further features of the disclosure are characterised by the other independent and dependent claims.

Any feature in one aspect of the disclosure may be applied to other aspects of the disclosure, in any appropriate combination. In particular, method aspects may be applied to apparatus aspects, and vice versa.

Furthermore, features implemented in hardware may be implemented in software, and vice versa. Any reference to software and hardware features herein should be construed accordingly.

Any apparatus feature as described herein may also be provided as a method feature, and vice versa. As used herein, means plus function features may be expressed alternatively in terms of their corresponding structure, such as a suitably programmed processor and associated memory.

It should also be appreciated that particular combinations of the various features described and defined in any aspects of the disclosure can be implemented and/or supplied and/or used independently.

The disclosure also provides a computer program and a computer program product comprising software code adapted, when executed on a data processing apparatus, to perform any of the methods described herein, including any or all of their component steps.

The disclosure also provides a computer program and a computer program product comprising software code which, when executed on a data processing apparatus, comprises any of the apparatus features described herein.

The disclosure also provides a computer program and a computer program product having an operating system which supports a computer program for carrying out any of the methods described herein and/or for embodying any of the apparatus features described herein. The disclosure also provides a computer readable medium having stored thereon the computer program as aforesaid.

The disclosure also provides a signal carrying the computer program as aforesaid, and a method of transmitting such a signal.

The disclosure extends to methods and/or apparatus substantially as herein described with reference to the accompanying drawings.

The term verifiable delay function (VDF) as used herein typically connotes a function that requires a plurality of sequential calculation steps (e.g. a second step cannot be performed until the output of a first step is known). Such a function can be used so that the determination of an output value of the function takes a significant amount of time; but such a function may also be used for other purposes (e.g. for demonstrating that an amount of processing work has been performed). As an example, a verifiable delay function may require repeated squaring of an input value.

Embodiments of the disclosure are described below, by way of example only, with reference to the accompanying drawings.

Brief Description of the Drawings

Figure 1 shows a blockchain on which the methods disclosed herein can be implemented. Figure 2 illustrates a computer device on which aspects of the disclosed system are implemented. Figure 3 shows a network on which aspects of the disclosed system are implemented.

Figures 4a and 4b show, respectively, a flowcharts for a method of calculating an output value based on a verifiable delay function and a flowchart for a method of verifying this output value.

Figure 5 shows a flowchart for a method of calculating an output value for a verifiable delay function based on a number of steps determined from a block of a blockchain.

Figure 6 shows a flowchart for a method of determining an updated number of steps for a verifiable delay function.

Figure 7 shows a flowchart for a method of transmitting a reference to an output value for a verifiable delay function to a node of a blockchain.

Figure 8 shows an example of a number of steps relating to a verifiable delay function being updated. Figure 9 shows a flowchart for a method of updating an acceptable range of output values for a verifiable delay function.

Figures 10a and 10b show exemplary distributions of the acceptable range of Figure 9.

Detailed Description of the Embodiments

Referring to Figure 1, there is shown a blockchain 10. The blockchain comprises a first block 12, a second block 14, a third block 16, and a fourth block 18. Each block is dependent on the previous block, so that the fourth block depends on the third block, the third block depends on the second block, and the second block depends on the first block. More generally, the nth block of the blockchain depends on the (n-1)th block and thereby depends on each previous block of the blockchain.

In this way, the blockchain 10 is useable to implement an immutable ledger. Any change to a block of the blockchain alters each subsequent block and so is immediately detectable. Typically, each block comprises a hash of the previous block; changing any block of the blockchain 10 will alter the hash of that block and therefore alter the hash of each subsequent block (since the subsequent hashes depend on the altered hash).

Typically, each block comprises a body, which contains a record of transactions within the block, and a header, which comprises information relating to the block. For example, the header may comprise: a value relating to these transactions (e.g. a hash relating to a Merkle tree, which Merkle tree comprises the transactions); a value (e.g. a hash) relating to a previous block and/or a value relating to a proof of work puzzle that has been solved in order to mine the block. Typically, the blockchain 10 comprises a decentralized blockchain and/or a distributed blockchain. More generally, the methods described herein are applicable to distributed ledgers and/or public consensus networks (PCNs), e.g. networks that require a consensus between a plurality of participant nodes.

Typically, each block comprises information regarding a change of state of a variable. In an unspent transaction output (UTXO) blockchain, such as Bitcoin, the block may comprise a series of transactions between two addresses (e.g. between a sender and a recipient). Typically, in UTXO blockchains, the addresses are single use, so that each address is used only a single time as the sender for a transaction. In an account model blockchain, such as Ethereum, the block may comprise a series of state changes for an account (e.g. an account may receive an amount of currency and/or a state of the account may change). The accounts typically persist throughout the blockchain, such that accounts can be referenced repeatedly.

A verifiable delay function may be determined based on a parameter that is recorded on the blockchain 10; for example a verifiable delay function may be determined based on the hash of the nth block of the blockchain. The output value of the verifiable delay function will be fixed at the time of addition of the nth block of the blockchain (since the blockchain is effectively immutable), but this output value will not be determined until a later time, e.g. until the (n+k)th block of the blockchain.

The present disclosure relates to a method of recording characteristics of verifiable delay function calculations on the blockchain 10. In this regard, a potential problem occurs if a party is able to find the output more quickly than expected by developing in secret a more efficient processor for the verifiable delay function. A party that had developed such a processor would be motivated to keep it secret in order to profit from their ability to find the output quickly (e.g. they could win lotteries with entry periods that are based on a quickest publicly-known processor). This profit could be a financial profit; equally, the profit may be technical or may relate to improved access. As examples, a malicious party that can quickly find the output of a verifiable delay function may be able to obtain passcodes to access sensitive material, or may be able to take control of the consensus mechanism of a blockchain. With the present disclosure, parties are able to and/or incentivised to record characteristics of verifiable delay function calculations so that processors for verifiable delay functions are not developed entirely in secret. Viewers of the blockchain are able to identify current processing times for verifiable delay functions so that they are less likely to be surprised by the secret development of an efficient processor.

Referring to Figure 2, the blockchain 10, is configured, added to, and/or viewed using a computer device 2000. In particular, each node that validates transactions is implemented using the computer device 2000. Similarly, each mining or proposing node, which propose blocks for addition to the blockchain, is implemented using the computer device 2000. Furthermore, each viewer of the blockchain accesses the blockchain using the computer device 2000. Nodes, miners, and/or viewers may be implemented on the same computer device.

Each computer device 2000 typically comprises a processor in the form of a CPU 2002, a communication interface 2004, a memory 2006, storage 2008, removable storage 2010 and a user interface 2012 coupled to one another by a bus 2014. The user interface comprises a display 2016 and an input/output device, which in this embodiment is a keyboard 2018 and a mouse 2020.

The CPU 2002 executes instructions, including instructions stored in the memory 2006, the storage 2008, and/or the removable storage 2010.

The communication interface 2004 is typically an Ethernet network adaptor coupling the bus 2014 to an Ethernet socket. The Ethernet socket is coupled to a network, such as the Internet. The communication interlace facilitates communication between the nodes of the blockchains and enables each node to validate and propagate transactions and each miner to propose blocks to the network. It will be appreciated that any other communication medium may be used by the communication interface, such as area networks, infrared communication, and Bluetooth®.

The memory 2006 stores instructions and other information for use by the CPU 2002. The memory is the main memory of the computer device 2000. It usually comprises both Random Access Memory (RAM) and Read Only Memory (ROM).

The storage 2008 provides mass storage for the computer device 2000. In different implementations, the storage is an integral storage device in the form of a hard disk device, a flash memory or some other similar solid state memory device, or an array of such devices. To run a full node of the blockchain 10, that is a node which contains the entirety of the blockchain, the storage is typically required to have a large capacity. The computer device may also be capable of running a partial, or light, node, where the storage 2008 stores only a portion of the blockchain.

The removable storage 2010 provides auxiliary storage for the computer device 2000. In different implementations, the removable storage is a storage medium for a removable storage device, such as an optical disk, for example a Digital Versatile Disk (DVD), a portable flash drive or some other similar portable solid state memory device, or an array of such devices. In other embodiments, the removable storage is remote from the computer device, and comprises a network storage device or a cloud-based storage device.

Each node, miner, and viewer uses a computer device 2000 to implement aspects of the methods and systems as described herein. Typically, the computer device used by each party is specialised; for example miners proposing blocks to be added to a blockchain may use a computer device that comprises an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), or a graphics processing unit (GPU). In some embodiments, the computer device comprises numerous racks of ASICs, FPGAs, or GPUs with a single user interface, where the computer device may be wholly specialised for mining blockchains.

Typically, the computer device 2000 of each node is arranged to receive transactions, to validate these transactions, and then to propagate the validated transactions throughout a network. The computer devices of the miners (which miners may also be nodes) are then able to collate a number of validated transactions into a block; this block can then be proposed for addition to a blockchain. The addition of the proposed block to the blockchain 10 may rely on, for example, providing a proof-of-work (as occurs in e.g. Bitcoin: “Bitcoin: A Peer-to-Peer Electronic Cash System. Nakamoto, S. (2008) https://bitcoin.org/bitcoin.pdf”) or providing a proof-of-stake (as occurs in e.g. Algorand: “ALOGRAND Chen, J. (2017) https ://arxiv.org/pdf/1607.01321.pdf).

In an exemplary usage of the blockchain 10, a node combines a number of transactions into a block, and then proposes this block for addition to the blockchain. Other nodes validate and propagate this block to the users of the blockchain. Once the block is added to the blockchain, a transaction included in this block can be presented to a user, where the information contained in the transaction can be used for a variety of purposes (e.g. to improve the design of machines, to ensure adherence to government regulations, or to identify risky or endangering behaviour). It will be appreciated that while the term transaction is used throughout - and is commonly used in reference to blockchains - each blockchain is more generally capable of the (preferably immutable) storage of information. Therefore, while transactions may relate to a transfer of currency, more generally the transactions in a block may relate to any information and may have no relation to financial transactions.

A computer program product is provided that includes instructions for carrying out aspects of the method(s) described below. The computer program product is stored, at different stages, in any one of the memory 2006, storage device 2008 and removable storage 2010. The storage of the computer program product is non-transitory, except when instructions included in the computer program product are being executed by the CPU 2002, in which case the instructions are sometimes stored temporarily in the CPU or memory. It should also be noted that the removable storage is removable from the computer device 2000, such that the computer program product may be held separately from the computer device from time to time. Different computer program products, or different aspects of a single overall computer program product, are present on the computer devices used by any given miner and/or user of a blockchain.

Referring to Figure 3, the methods disclosed herein are typically implemented in relation to a network 3000, which network is typically arranged to view, add to, and/or configure a blockchain (e.g. the blockchain 10 of Figure 1).

The network 3000 comprises one or more nodes 3002, 3004, 3006, which nodes are arranged to communicate (directly or indirectly) to propagate information. The nodes typically comprise computer devices.

The network 3000 may have one or more of the following properties:

Be a centralised network, in which communications are propagated by a single node (or a group of nodes).

Be a decentralised network, in which nodes of the network are arranged to communicate with each other directly (e.g. not via a central authority). Be a distributed network, where records relating to the network are stored on a plurality of the nodes. This prevents a single node from editing the record (since this editing would be noticed by the other nodes).

Be a permissioned network, where only certain nodes are able to view, access, add to, and/or participate in the building of a consensus on the history of, the blockchain.

Be a non-permissioned network, where all nodes and parties are potentially able to view, access, add to, and/or participate in the building of a consensus on the history of, the blockchain.

Typically, the disclosures herein are implemented on a decentralised, and/or distributed, network. Typically, the disclosures herein are implemented on a non-perm issioned blockchain.

The nodes 3002, 3004, 3006 are arranged to communicate with each other so as to propagate information throughout the network. This information typically comprises blocks of the blockchain. The nodes may be configured differently and/or arranged to provide different services. For example, the network may comprise:

A mining node 3002, which mining node is arranged to propose blocks for addition to the blockchain.

A validating node 3004, which validating node is arranged to validate the blocks proposed by the miner (e.g. confirm that the blocks are correctly formatted and/or comprise valid transactions). A validating node may run a ‘full’ node and comprise a record of the entire blockchain. Such a full validating node may validate a block of the blockchain based on previous blocks of the blockchain (e.g. to ensure that a party transferring an asset does indeed hold that asset). A validating node may run a 'light' or 'partial' node and comprise a record of only a part of the blockchain. Such a partial validating node may validate a block based on the transactions in that block and/or block headers from previous blocks (e.g. to ensure that a hash of the transactions of block corresponds to a value in the header of the block).

A propagating node 3006, which propagating node is arranged to receive information from other nodes and then forward this information to ensure that it reaches other nodes in the network.

More generally, one or more nodes of the network may be arranged to influence a consensus mechanism of the blockchain, to participate in the addition of blocks to the blockchain and/or to propagate blocks throughout the network.

It will be appreciated that nodes may provide a plurality of sen/ices; for example, mining nodes typically also perform validation and propagation.

The methods disclosed herein are typically carried out by one or more of the nodes of the network 3000, so that where the description refers to a 'party', this party is typically one or more of: a node of the network; a group of nodes of the network; and a user that controls one or more nodes of the network.

Typically, nodes and/or parties are implemented on the computer device 2000. The methods described herein may then be performed using the computer device. The methods typically relate to an interaction between computer devices, where information may be transmitted between the computer devices of a plurality of nodes. In particular, information determined at a first computer device (e.g. a first node) may be transmitted to a second computer device (e.g. a second node) and output on the second computer device. Where the information is part of a block of the blockchain, the second computer device may be able to determine that the information is recorded in an immutable manner. The information, and the knowledge that it is recorded in an immutable manner, can affect the actions of the second node and/or the party controlling the second node.

Verifiable delay functions

Verifiable delay functions are functions that require the performance of a plurality of sequential steps. In other words, the (a+1)th step cannot be performed until the ath step has been completed. If the time required to perform each step (or to perform a number of steps) is known, a verifiable delay function can thus be used to demonstrate that an amount of time has passed.

More specifically, a verifiable delay function requires the calculation of a number of sequential steps to calculate and produce a unique output value that can be verified efficiently. The verification time is typically substantially lower than, and/or essentially independent of, the calculation time. Typically, the verifiable delay function is arranged so that the performance of each step takes a similar time, and/or substantially the same time. Therefore, the computation time per step can be determined by dividing the time taken to find the output value (the ‘calculation time’) by the number of steps performed to find the output value.

An exemplary verifiable delay function is described in Figures 4a and 4b. In this example, the verifiable delay function is based on repeated squaring; such repeated squaring must be done sequentially and so cannot be sped up by the use of parallel processors. This method is typically carried out by a computer device.

Referring to Figure 4a, a method 110 of obtaining an output value from an input value based on a verifiable delay function is described. ln a first step 111 , an input value x is determined. Typically, this input value is determined based on the a block of the blockchain 10, for example the input value may be a hash of the blockchain and/or a hash of a block of the blockchain. Determining the input value may then comprise identifying a feature of a block of the blockchain. Typically, the input value is based on a publicly available feature, so that when a block on which the input value is based is added to the blockchain, the input value can be determined by a number of parties at the same time (e.g. each of the nodes of the blockchain). Each of these parties is then able to determine the output value.

In a second step 112, a number of steps T is determined. A verifiable delay function is based on an operation being performed over a number of sequential steps. The determination of how many steps to perform may be fixed, e.g. fixed at the time of defining the verifiable delay function. Equally, the number of steps may be chosen by the party calculating the output value (where output values corresponding to different numbers of steps may be used for different purposes); and/or the number of steps may be determined based on a feature of the blockchain. Typically, the input value and the number of steps are determined based on the same (previous) block of the blockchain. The previous block may be an immediately previous block; however, typically, the previous block from which the input value and/or the number of steps is determined is a previous block that has reached a substantial depth in the blockchain 10 (e.g. a depth of at least 3 blocks, 6 blocks, and/or 10 blocks).

Increasing the number of steps T increases the amount of time taken to determine the output value.

In a third step 113, an output value y is calculated, where y = x ^2T . More specifically, y comprises a number of substeps, relating to repeatedly squaring x. In an example where x = 2 and T = 4, the third step comprises the steps of:

Squaring 2 (2 ² = 4);

Squaring 4 (4 ² = 16);

- Squaring 16 (16 ² = 256);

- Squaring 256 (256 ² = 65536).

Turning then to Figure 4b, a method 120 of proving that the output value has been found is described. The party which finds the output value (e.g. a node of the blockchain) may transmit this value to other parties (e.g. other nodes of the blockchain); these other parties will wish to confirm that this is the correct output value.

If T = 1 , then the claimed output can be checked trivially (e.g. by checking simply whether the claimed output z is equal to x ² ). Assuming that T is greater than one, it is desirable to prove the output value in fewer steps than are required to obtain the output value.

Therefore, according to the method 120 of Figure 4b, in a first step 121 , the prover (the party that claims to have determined the output value) provides to the verifier a claimed output value z and a verifier value v, where v = x ^2T/2 ; assuming that the claimed output value is correct, then z = y = x ^2T = v ^2T/2 ; effectively, v is the value obtained at the halfway mark of the third step 113 of the method 110 of Figure 4a. Using the exemplary values above (where x = 2 and T = 4), v = 16.

In a second step 122, the prover then receives a random modifier r from the verifier. The random modifier is typically selected from a range {1 , ... 2 ^λ ), where λ is a security parameter.

In a third step 123, the prover and the verifier determine the variables p ₁ , p ₂ , and T _new, where p ₁ = x ^r v = x ^{r+ 22T/2}

Using the same values as before (where x = 2, T = 4, v = 16) and using an exemplary r value of 1 :

5

In a fourth step 124, the prover and the verifier return values of p ₁ , p ₂ , and T _new . The returned values p ₁ , p ₂ , and T _new are used to repeat the first to third steps, where:

If T is even (i.e. if T _new has been calculated as T/2), the value of p ₁ is used as a new value for x, the value of p ₂ is used as a new value for z, and the value of T _new is used as a new value for T.

If T is odd (i.e. if T _new has been calculated as (T+1 )/2), the value of p ₁ is used as a new value for x, the value of p ₂ ² is used as a new value for z, and the value of T _new is used as a new value for T.

Using the same exemplary values as before (x = 2, T = 4) and a repeating rvalue of 1 , the method proceeds as below:

Step 1 (as above):

15

Step 2:

20

Step 3

25

By performing the method 120 of Figure 4b, it can be seen that the claimed output z is the correct output, and this output is verified. The verification takes a shorter amount of time than the determination of the output, so that an output that takes a long time to determine can be quickly verified.

It will be appreciated that the above methods and examples are only simple examples (with low numbers and a low number of steps T). Partly due to this there is only a small difference in the number of steps required to obtain the output and the number of steps required to verify a claimed output. The repeated squaring operation and the proof of Figure 4b are similar to methods disclosed by “Simple Verifiable Delay Functions. Pietrzak, K. (2019) https://eprint.iacr.org/2018/627.pdf": an implementation of verifiable delay functions are explained in more depth in this document. This document does not consider many of the aspects of the present implementation, such as the use of an input value and a number of steps that is based on the blockchain.

The method 120 described In Figure 4b Is an Interactive method In which a prover demonstrates a proof to a verifier. This method may equally be performed in a non-interactive manner (e.g. using a Fiat Shamir heuristic). For example, the prover may generate a challenge random number r after each iteration of the third step 113 and perform a similar method. Typically, the party calculating the verifiable delay function determines both an output value (e.g. the random number) and a proof relating to the output value, which proof can then be transmitted to another party (e.g. along with the output value). The proof evidences that the output value has been determined using a given input value and an input number of steps and may be based on a Fiat Shamir heuristic, as mentioned above.

The party calculating the verifiable delay function may provide to another party one or more of: an output value; a number of steps relating to this output value (e.g. the number of steps calculated to obtain the output value); an input value that was used to obtain the output value (this may comprise providing a reference to a previous block of the blockchain); one or more intermediate values useable to verify the calculation of the output value (e.g. the party may provide each of the values of v); and a proof relating to the verifiable delay function and/or the output value.

Typically, the verifiable delay function is set up using a finite abelian group G of unknown order, where the input is subjected to a hash function H that relates to a conversion from bytes to elements of G. Verifiable delay functions are further more detail in “A Survey of Two Verifiable Delay Functions . Boneh, B. etal (2018) “Verifiable Delay Functions. Boneh, B. et al (2019) “Simple Verifiable Delay Functions. Pietrzak, K. (2019) and “Efficient Verifiable Delay Functions. Wesolowski, B. (2019) As has been mentioned above, a particular use of verifiable delay functions is to generate random numbers (where the random number itself cannot be determined for a certain amount of time following the disclosure of the seed/input for the random number). It will be appreciated that other uses of verifiable delay functions exist (e.g. confirming that a certain amount of time has passed since the disclosure of an input value); for the sake of describing the invention, this disclosure focuses mainly on the provision of random numbers. The present disclosure is particularly relevant for verifiable delay functions which have an input that is recorded on the blockchain 10. In particular, an input recorded in the nth block of the blockchain may be used as the input to a verifiable delay function; where an output value for this verifiable delay function may be recorded in the (n+k)th block.

Similarly, in order to record a random number in the nth block of the blockchain 10, a party may use an input value (e.g. a seed) that is based on a previous block of the blockchain. For example, a random number may be calculated as r„ = VDF(b _n _ _s ), where is a value (e.g. a hash) relating to the (n-δ)th block of the blockchain and is the input value for the verifiable delay function.

The random number r _n may then be recorded in the nth block as a transaction and/or an state transition (depending on the type of blockchain); it will be appreciated that these methods could be applied to a blockchain based on unspent transaction outputs (UTXOs), such as Bitcoin, as well as blockchains based on an account model (such as Ethereum). Yet more, aspects of the disclosed methods may be implemented using any public consensus network (e.g. graphchains).

Considering the problem of random number generation - and not limiting this generation to the use of verifiable delay functions - a variety of random number generating functions can be used to obtain the random value from the input value. In particular: a random number may be generated using a common function, which is dependent only on publicly available information (such as the hash of a distributed blockchain); or a random number may be generated using a private function, which is dependent on private information known available only to a limited subset of parties. In such a situation, the random number may be calculated as rl = RNG ^J (b _n ^l _ _s ), where j is a party determining the random number. The conventional generation of a random number (e.g. not based on a verifiable delay function) based on a previous block can provide a number that is difficult to predict or bias. Typically, the hash of a block uploaded by a node of the blockchain is not known until that block is propagated to the other nodes of the blockchain. At this point the random number can be determined by each of these other nodes.

However, with such conventional random number generators, the party that is proposing the block could gain advance knowledge of the random number. More specifically, a party that has generated a valid block for addition to the blockchain 10 (e.g. found a suitable nonce for a proof of work blockchain, such as Bitcoin) might be able to calculate the random number before proposing the block for addition to the blockchain. This party could calculate the random number and then decide not to propose the block if this number is undesirable (e.g. if the number would not lead to the proposing party winning a lottery); this may lead to a different block being added with a different random number. This is termed as the party 'censoring' the block.

Typically, parties proposing blocks for addition to a blockchain obtain a mining reward and/or transaction fees; censoring a valid block would lead to the censoring party losing out on this reward, but this might be worthwhile if the value of a desired random number is sufficiently high.

This problem of censorship occurs mainly where the random number can be determined quickly, so that a party can generate a block, determine quickly whether this will lead to a desirable random number, and then decide whether or not to propagate this block to the other nodes. If the party is not able to determine the random number before another party has proposed a valid block, then the determination is irrelevant and the party might have lost out on a reward for proposing a block.

Therefore, the present disclosure considers the use of a verifiable delay function to generate a random number; this can be used to discourage censorship. The number of steps required for the calculation of the verifiable delay function is based on the expected time for a party to generate a valid block; more specifically, the number of steps required is typically selected so that a party proposing a block containing an input value for the verifiable delay function cannot be confident of determining the random number (e.g. the output value of the verifiable delay function) before another (honest) party has proposed a valid block.

A condition for preventing censorship is defined by the equation: which can be rearranged to: where: τ (F) is the time required to perform the function F. τ(b ⁱ _n ) is the time required for party i to generate a block n of the blockchain. τ(RNG(b ⁱ _n )) is the time taken for party i to calculate a random number based on their generated block n.

According to this condition, the maximum time taken for any participant on the blockchain 10 to generate a block should be less than the sum of the minimum time taken to generate a block and the time taken to determine the random number. In other words, a participant who generates a block in the minimum possible (or plausible) time and then calculates a random number based on this block should only complete the calculation of the random number after another, honest, participant has also generated a block.

The minimum and maximum times taken to generate a block of the blockchain typically depend on a consensus mechanism used by that blockchain. As an example, Bitcoin is based on Nakamoto consensus, where Bitcoin is configured so that a solution to a cryptographic problem is discovered on average every ten minutes. Such a solution is required to propose a block for addition to the Bitcoin blockchain. Theoretically, a solution could be discovered, and an nth block generated, almost immediately after the (n-1 )th block; equally, theoretically it could take years (or longer) for any participant to find a solution for the nth block.

Therefore, more generally, the minimum and maximum times referenced in the above equation may relate to minimum/maximum plausible times and/or minimum/maximum expected times. This can be explained using the example of Bitcoin, where the discovery of solutions to the cryptographic problem follows a Poisson distribution and a solution is found (and a block generated) on average every 10 minutes.

With a Poisson distribution: p(k events in interval t) =

Where r is the number of events per unit time, t is a time period, e is Euler's number, and k is the number of occurrences. Applying this to Bitcoin, the probability of a block being found in a time period t is equal to: p(block found in interval t) = 1 — p (no blocks found in interval t) = 1 — e

Where t is a time in minutes (since on average one block is found every ten minutes).

The probability of generating at least one block is then: for a time period t that is 1 minute: 9.5% for a time period t that is 5 minutes: 39.3% for a time period t that is 10 minutes: 63.2% for a time period t that is 25 minutes: 91.8% for a time period t that is 100 minutes: 99.995%

From this it can be seen that there is only a very small probability that no party will generate a block within a period of one hundred minutes; therefore, if the determination of the random number takes one hundred minutes, then a participant who generates a block and seeks to determine the random number before deciding whether to propose this block for addition to the blockchain will almost certainly not finish the determination before another participant proposes a block to the blockchain (in which case the determination will be useless, since it is based on a block that will not be added to the blockchain). The above example has considered Bitcoin; it will be appreciated that more generally an expected maximum time may be determined that provides a sufficient certainty that an honest participant will generate a block in a time shorter than the time taken to determine the random number.

The 'sufficient' certainty may depend on the use of the random number. Continuing with the example of a small lottery for some hundreds of pounds, a 99.995% certainty may be considered sufficient. Since the participant is likely to forgo mining rewards if they attempt to determine the random number, the expected value of this determination will likely be negative (0.99995 * mining reward > 0.00005 * lottery reward). If the lottery reward were increased, then the sufficient certainty might be greater.

The minimum time taken to generate a block is related to the time taken for the potentially censoring party to generate a block (which will occur before the determination of the random number begins). As a conservative value, this may be taken as zero.

In the above example, where there is no theoretical maximum time for block generation, censorship can be discouraged by arranging for the determination of the random number to take a sufficiently long time. This determination time is typically selected so that the expected value of determining a random number based on a potential block before proposing this block for addition to the blockchain 10 is negative. Therefore, while it is possible for a party to determine the random number before another block is proposed, attempting to do this course of action tends to be disadvantageous for this party.

In some cases, it is desirable to ensure that there is no possibility at all of a malicious party determining the random number before another (honest) party has added a block to the blockchain. This can be achieved by using a blockchain with a finite maximum time between the addition of blocks; an example of such a Blockchain is Algorand. Where there exists a finite maximum time between the addition of blocks to the blockchain, the determination of the random number may be arranged to take longer than this maximum time. This makes it entirely pointless for a party to try to determine the random number before proposing a block for addition to the blockchain.

The present disclosure relates to the use of a verifiable delay function as a part of the random number generation; this provides censorship resistant random number generation. A verifiable delay function is useable to provide a random number generator that takes a long time to provide an output value (e.g. 100 minutes, or 100 hours), while also providing an output value that can be checked quickly for legitimacy.

While the example described above considers a blockchain in which the timing of the addition of blocks to the blockchain follows a Poisson distribution, it will be appreciated that the methods and systems described herein may be implemented on a range of blockchains for which the addition of blocks does not follow a Poisson distribution for example, these methods and systems may be used with a blockchain for which there is a minimum and/or maximum time for addition of blocks to the blockchain. Considering the situation where the random number is generated using a verifiable delay function, the required condition is: or (rearranging this equation): where d(b ⁱ _n ) is an input for the verifiable delay function, which input is based on a block of the blockchain 10. Typically, the input is based on publicly available information so that all nodes of the blockchain are able to determine the input. s(b _n ^l ) is a function that determines the number of computation steps required to determine the output of the verifiable delay function (the random number). The determination of the number of steps is typically based on publicly available information and is typically the same for all participants. In this embodiment, the number of steps is dependent on a block of the blockchain; equally, the number of steps may be a fixed value.

In some embodiments, the number of steps is dependent on the participant executing the verifiable delay function. This enables parity in computing time to be reached between parties with different computation capabilities. τ(VDF ⁱ (...) is the time taken for the party i to calculate the output value for the verifiable delay function. While each party executes the same verifiable delay function, the times taken to determine the output value may differ based on different computing capabilities.

The verifiable delay function is typically arranged so that the fastest participant does not expect to determine the output value to the verifiable delay function before another participant has generated a block. The development of electronics, and in particular the development of computing devices that are optimised for verifiable delay functions means that the time taken for the fastest participant to determine the output value

( τ(VDF ^fastest (...)) is likely to decrease in the future. Therefore, providing a verifiable delay function that is based on present capabilities may lead to problems in the future (e.g. a verifiable delay function that requires five steps might presently take one hundred minutes to run, now might only take ten minutes to run in a few years' time). Equally, providing a verifiable delay function that is future-proof will limit the use in present circumstances (since a verifiable delay function that takes one hundred minutes to run in the future might require fifty steps and might take one thousand minutes to run now - which requires a prohibitive amount of time and computing power for most purposes).

Therefore, according to the present disclosure there is described a method of providing a verifiable delay function in which the number of steps required to find an output value is variable. In particular, there is described a method of providing a verifiable delay function for which a required number of steps is variable and/or is defined in a block of a blockchain. The number of steps required for the verifiable delay function is typically dependent on a previous execution of the verifiable delay function and may be selected as a number of steps that is sufficient to discourage or prevent censorship.

Typically, a reference to the output value of a verifiable delay function is recorded on the blockchain 10, for example there may be a reference recorded in the nth block of the blockchain. This value depends on a previous (n-δ)th block of the blockchain, which previous block provides the input value and the number of steps to be used for the verifiable delay funclion. The value of 5 may be based on a confidence of a block being immutable; e.g. a probability of finality that relates to the probability of a block being included in the eventual longest fork of the blockchain. For example, k and δ may depend on one or more of: a block depth, a number of confirmations, and/or a stake held by validators of a block. Using the example based on a number of confirmations, for Bitcoin 6 confirmations is generally considered sufficient for a block to be effectively immutable, this has a greater than 99.9% probability of finality. Typically, the value of δ depends on a target calculation time, where the required number of steps may be updated in order to maintain a target calculation time as blocks are added to the blockchain.

Where the value of δ is based on a probability of finality, the number of steps is typically selected so that the calculation time for the verifiable delay function is much greater than the expected (or maximum) time required to add δ blocks to the blockchain. This enables parties to only start calculating the verifiable delay function when an input block has reached this depth of finality δ without being heavily disadvantaged compared to those parties who start their calculations as soon as this input block is added to the blockchain.

Referring to Figure 5, there is described a method 130 of determining a verifiable delay function based on a number of steps defined by the blockchain 10. This method is typically performed by (the computer device 2000 of) a node of the blockchain.

In a first step 131 , a number of steps is determined based on a block of the blockchain 10. This number of steps may, for example be defined in a transaction in a block of the blockchain. Equally, the number of steps may be defined in relation to an account of the blockchain and/or in a header of a block of the blockchain.

In a second step 132, the node calculates the output of a verifiable delay function based on the number of steps.

Typically, the input value for the verifiable delay function is based on the block from which the number of steps is determined. However, in some embodiments, these parameters may be determined from different blocks. In particular, the number of steps may be determined from a more recent block than the input value. In other words, the block on which the input is based may be an ancestor of the block from which the number of steps is determined. In some embodiments, the number of steps is determined based on an immediately previous block. This enables the number of steps to be quickly updated without penalising parties who have already started a calculation for an input value. This might be desirable if a step change in computing capability occurs.

In a practical example, when the blockchain 10 is n blocks long a party starts calculating an output value based on the (n-δ)th block using a first number of steps defined in the nth block of the blockchain. By the time the party finds an output value, the blockchain is (n+2) blocks long. Therefore, the party determines a number of steps based on the (n+2)th block of the blockchain. If this second number of steps is the same as (or less than) the first number of steps, the party can record a reference to the output value in the (n+3)th block of the blockchain. If this second number of steps is greater than the first number of steps, the party continues calculating the verifiable delay function until the second number of steps is reached.

While this example considers the number of steps being determined based on a block of the blockchain 10, more generally, a party may be arranged to determine a difficulty for a verifiable delay function based on a block of the blockchain 10. This enables the difficulty of the verifiable delay function to be increased over time as computing capabilities increase.

The difficulty of the verifiable delay function may, for example, relate to the operation of the verifiable delay function that is repeated. Therefore, increasing the difficulty may comprise altering an operation of the verifiable delay function. For example, the method of Figures 4a and 4b has considered a verifiable delay function that is based on repeated squaring; the blockchain may define a different operation that takes more (or less) time to compute.

In practice, once a verifiable delay function is defined parties will likely develop devices that are designed to quickly perform the operation of this verifiable delay function (e.g. repeated squaring). Changing the operation is likely to decrease the efficiency of these devices, and so changing the operation can be used to significantly increase the calculation time of the verifiable delay function.

Typically, the input to the verifiable delay function is based on public and/or common information, e.g. information which is publicly available and/or available to each node of the blockchain 10. This input value may be contained in a header, transaction, or account of a previous block of the blockchain. The use of public information ensures that each party is working towards the same output, this avoids the issue of a party not propagating the output value if the output value is undesirable for this party (since this party will be aware that if they do not propagate the output value another party will).

In some embodiments, the input value is based on private information, which differs between one or more parties. This private information may, for example, comprise a private key relating to the party.

Basing the input value on private information (e.g. information that is known only by a single party) enables a party to censor the output value if the output value is undesirable. Therefore, where the output value is used as a random number the input value is typically based on only public information. The use of private information for the input value may still be useful in some circumstances; in particular, the use of private information enables a plurality of parties to calculate a plurality of (different) output values using input values based on the same block. Therefore, the use of private information can provide a way of evaluating the computing capability of many parties.

Where the input value is based on private information, the input value is typically based on a combination of public information and private information. The use of some public information enables a verifier to verify a starting time (e.g. by identifying a block on which the public information is based).

Typically, the verifiable delay function is arranged to require a number of steps that is defined by a block of the blockchain 10; more specifically, a plurality of blocks (or each block) may define a number of steps that are required. This enables a verifiable delay function to be defined in a first block of the blockchain and this same verifiable delay function to be used from that point onwards, where the number of steps required to find an output value is updated in following blocks of the blockchain. This enables a verifiable delay function that can have a consistent calculation time even as computing capabilities improve.

Typically, the number of steps defined by the block of the blockchain is based on existing computer capabilities, where the number of steps defined by each block may differ. The blockchain 10 may be configured to determine these capabilities (e.g. the nodes of the blockchain may be required to determine these capabilities before proposing a block; this may be defined in the consensus rules of the blockchain). In order to accurately determine the current capabilities, it is desirable to obtain up-to-date information on the solving of an existing verifiable delay function.

Variable steps

Referring to Figure 6, there is described a method 140 of determining a number of steps for a (calculation of a) verifiable delay function based on the time taken to determine an output value for a previous calculation of the verifiable delay function. This method is typically performed by (the computer device 2000 of) a node of the blockchain.

In a first step 141 , a reference to an output value relating to the calculation of a verifiable delay function is identified.

The calculation of the verifiable delay function refers to the determination of an output value based on a repeated operation. In particular, an input value is subjected to a number of sequential operations (e.g. repeated squaring) in order to obtain the output value.

Identifying the reference typically comprises a node of the blockchain 10 identifying this reference in a block of the blockchain.

In a second step 142, a number of steps relating to the output value is identified. Typically, the number of steps comprises the number of times that an operation has been performed.

In a third step 143, a calculation time relating to the verifiable delay function (and the number of steps) is determined. The calculation time relates to the time taken to obtain the output value (e.g. the time taken to calculate the verifiable delay function) and is typically the time taken to perform the identified number of steps. This calculation time is typically determined in units of time, e.g. in seconds and/or minutes, or in terms of a number of blocks that have elapsed in the time taken to find the output value.

In some embodiments, the calculation time is determined based on the timestamps of blocks of the blockchain. In particular, a starting time can be determined based on an input block (the block on which the input to the verifiable delay function is based) and/or a finishing time can be determined based on an output block (the block in which a reference to the output value of the verifiable delay function is recorded). The calculation time may be determined as the difference between the finishing time and the starting time. Typically, blockchains are arranged to prevent manipulation of the timestamps of blocks, and so the use of timestamps of blocks prevents misrepresentation of the calculation time by a party providing an output value.

In a fourth step 144, an updated number of steps for a subsequent calculation of the verifiable delay function is determined based on the calculation time. This updated number of steps is typically selected to maintain a consistent calculation time for the verifiable delay function. In order to determine the updated number of steps, the time taken to perform a single step of the verifiable delay function may be determined; this time can be determined as the total time taken to obtain the output value (the calculation time) divided by the number of steps. Typically, the time taken to perform each step is similar, so the updated number of steps can be determined based on a target calculation time and a determined time per step.

In an example of the use of the method 140 of Figure 6, it may be determined based on the first step 141 , the second step 142, and the third step 143 that the time required to perform a single step of the verifiable delay function has decreased by 20% (as compared to an initial time per step). In order to maintain a consistent calculation time, the number of steps required for a subsequent execution of the verifiable delay function may then be increased by 20%. This updated number of steps is recorded in a block of the blockchain. This updating of the number of steps may occur periodically and/or regularly as computing capabilities improve.

Using the example of a random number generator, the verifiable delay function may be used to generate a random number based on the (n-δ)th block of the blockchain. This random number may be included in a following block of the blockchain. In practice, it may be desirable to have this number included in a specific block of the blockchain (e.g. the nth block) or in a specific range of blocks of the blockchain (e.g. between the (n-2)th block and the (n+2)th block).

Therefore, the calculation times for previous output values (e.g. random numbers) may be analysed. In this regard, it would be expected that as computers improve these times would decrease so that, at a first time, the output value of a verifiable delay function based on an input from the (n-δ)th block and a number of steps S may be determined before, and proposed for inclusion in, the nth block; at a second time the output value of a verifiable delay function based on an input from the (n-δ)th block and based on the same number of steps S may be determined before, and proposed for inclusion in, the (n-1)th block.

At this second time, the blockchain may be configured to increment a counter in the blockchain, which counter relates to a number of required steps for the verifiable delay function. Therefore, following output values of the verifiable delay function will require at least one additional step to have been performed in order to be included in the blockchain. This configuration is typically implemented by altering the transaction rules and/or consensus rules for the blockchain; for example, so that a transaction containing the output value of the verifiable delay function can only be included validly in a block if a specified number of steps have been performed in order to obtain this output value.

As described, the calculation time is typically determined based on timestamps for an input block and/or an output block. This determined calculation time is therefore not equal to the 'true' calculation time. In other words, a party may start calculating the verifiable delay function shortly after the input block is added to the blockchain and may only record the reference to the output value in the output block a short time after the output value has been determined. Therefore, there will be a discrepancy between the determined calculation time and the true calculation time. It is desirable to minimise this discrepancy and so parties are typically incentivised to record the reference in an output block as soon as the output is determined (a method of incentivisation is explained further below). This discourages parties from holding back output values to misrepresent their calculation time (and their computing capability).

Since the determined calculation time is typically greater than the true calculation time, the true time per step is typically overestimated. Therefore, the determination of the updated number of steps may include a scaling factor to account for this overestimation. In simple embodiments, the scaling factor may be a fixed number (e.g. a factor of 1.2). Equally, the scaling factor may be based on the time between the addition of blocks to the blockchain 10. In this regard, a substantial part of the discrepancy between the determined times and the true times may be due to the time taken to record the reference in an output block once the output value has been found.

As mentioned above, it is desirable to base the number of steps for an upcoming calculation of the verifiable delay function on a previous calculation of the verifiable delay function. Therefore, referring to Figure 7, there is described a method 150 of a node of the blockchain 10 determining a reference to an output value to a verifiable delay function. Typically, this comprises a node of the blockchain receiving the reference from another node of the blockchain. the reference may include one or more of: an output value, a number of steps used to calculate the output value, an input value, one or more intermediate values, and a proof that the output value has been calculated using this number of steps and/or a specific input value.

In a first step 151, a reference to an output value for a verifiable delay function is determined. Typically, this comprises a node of the blockchain receiving the reference from another node of the blockchain. Receiving the reference may comprise identifying a transaction including the reference that is proposed for inclusion in a block of the blockchain. Equally, identifying the reference may include identifying the reference in the header of a block that is proposed for addition to the blockchain.

In a second step 152, the reference is transmitted to a further node of the blockchain 10 along with a calculation time relating to the output value. This transmission typically comprises the reference being included in a block that is proposed for addition to the blockchain. The reference may be included in a transaction in the block. Equally, the reference may be included in the block header of the block. The inclusion of the reference in a header of the block may be used in embodiments where the verifiable delay function is used as a puzzle for a Nakamoto consensus (and where the calculation of the verifiable delay function comprises a proof of expended computational power). In this case, a party proposing a block may append the proof for the verifiable delay function to the block header before proposing the block for addition to the blockchain.

The calculation time may be based on the timestamp of an input block and the timestamp of an output block. Therefore, transmitting the calculation time may comprise identifying the input block and/or the output block. Equally, transmitting the calculation time may comprise identifying the input used for the calculation of the verifiable delay function, where the input block can be determined based on this input and the output block can be determined as the block in which the reference is recorded.

With this method, the further node is typically a miner, proposer, validator, and/or signer of a block. The further node may receive the reference and include the reference in a block that the further node is proposing for addition to a blockchain. Furthermore, the node may include an indication of the calculation time (this may comprise a reference to an input block, where the calculation time can be determined based on the timestamps of the input block and the proposed block or based on the timestamp of the input block and a current time). Equally, the further node may receive a block that is being proposed by the node and the further node may validate this block based on the reference.

In this way, references to calculations of the verifiable delay function can be recorded on the blockchain 10. These previous calculations enable an evaluation of existing computing capabilities for this verifiable delay function, for example they enable the determination of the time required to perform a step of the verifiable delay function; this enables a suitable number of steps to be determined for future calculations of the verifiable delay function. Furthermore, the output values may be output and/or presented for other uses, such as random beacons.

Variable reward

In order to obtain an accurate assessment of existing computing capabilities, it is desirable that parties transmit output values for verifiable delay functions as soon as they are found and also that parties start the determination of the output value as soon as the input to the verifiable delay function is known.

Therefore, according to the present disclosure, there is envisaged a blockchain that is configured to provide a reward for the transmission of a reference to a valid output value. Typically, this comprises a party receiving an amount of a cryptocurrency relating to the blockchain 10 (and/or another blockchain) when a reference to a valid output value is transmitted by that party (e.g. included in a transaction for which the party is a sender). In practice, this may comprise publicising a public address that relates to verifiable delay function output values. Parties are then able to make a transaction to this address, which transaction comprises a reference to an output value calculated using the verifiable delay function; the parties may receive a reward once this reference has been received and/or verified.

In some embodiments, the blockchain 10 is configured so that the consensus mechanism and/or an anti-sybil mechanism of the blockchain is based (at least in part) on the determination of the output value. The party providing the reference may then receive a block reward and/or transaction fees. In such embodiments, the calculation of the verifiable delay function typically comprises an element of uncertainty. In particular, the number of steps required to determine an 'acceptable' output value (an output value that leads to a reward and/or the inclusion of a reference to the output value in a block of the blockchain) may have an uncertain element so that one node may find an acceptable output value in S steps and another node may find an acceptable output value in (S+Δ) steps. Such an embodiment is described in more detail further below.

In some embodiments, the number of steps required to record an output value is fixed, where a reward for transmitting the output value is awarded only if the output value has been calculated with this number of steps (or a greater number of steps). Typically, there exists a range of acceptable numbers of steps, where a reward depends on the number of steps calculated to obtain an output value. For example, the reward for an output value relating to five steps may be greater than an output value for three steps.

Typically, there is a limited reward. The reward may be awarded only to the first party that provides an acceptable output value or the reward may be awarded to a plurality of parties providing acceptable output values. The use of a limited reward encourages parties to provide a reference to the output value as soon as possible (which enables an accurate determination of the true calculation time).

An example of the use of the above methods is described with reference to Figure 8. In this example, the blockchain 10 comprises a number of blocks n to (n+13). One or more of the blocks comprises an indication of a number of steps for a verifiable delay function; typically, each block comprises such an indication. This steps herein are typically implemented by the computer device(s) of one or more nodes of the blockchain.

At a first time, in a first step 161, following the addition of the nth block to the blockchain 10, the node determines a number of steps Si to use for the verifiable delay function based on the blockchain. With this example, the nth block of the blockchain indicates that two steps should be used. It will be appreciated that in practice it is likely that many more steps will be used (e.g. Si > 100 or Si >1000).

In a second step 162, an output value is determined for the verifiable delay function based on this number of steps Si.

In a third step 163, a reference to this output value (e.g. the output value and/or the number of steps taken to reach the output value), is recorded on the blockchain 10. This typically comprises the node including the reference in a block that is proposed for addition for the blockchain.

In this example, the output value has been determined within four blocks, so that the reference is recorded in the (n+4)th block.

The blockchain 10 is configured to have a target calculation time (or target calculation time range) for output values. In this example, this target calculation time is greater than four blocks. Therefore, an updated number of steps Sa is determined by the node and, in the (n+5)th block of the blockchain, the updated number of steps Sa is recorded on the blockchain. Specifically an updated value of three steps is recorded in the (n+5)th block.

At a second time, in a fourth step 164, following the addition of the (n+5)th block to the blockchain 10, a number of steps to use for another calculation of the verifiable delay function is again identified based on the blockchain. The (n+5)th block of the blockchain now indicates that Sa, that is three steps, should be used.

In a fifth step 165 and a sixth step 166, an output value is determined for the verifiable delay function based on the updated number of steps Saand this output value, and a reference to the output value is recorded on the blockchain 10. Figure 8 shows that due to the increased number of steps required it takes longer for this second output value to be found, and so the second output value is not recorded on the blockchain until the (n+11 )th block.

This method can therefore be used to maintain a target calculation time for a verifiable delay function as computer technology develops.

In some embodiments, the verifiable delay function is used as part of an anti-sybil mechanism; in particular, the calculation of output values for the verifiable delay function may be used as a proof of work or a proof of expended computational power, where only parties that have provided output values are eligible to contribute to the building of a consensus on the history of a blockchain 10 (e.g. to participate in the addition of blocks to the blockchain) and/or where only parties that have provided output values are eligible to receive rewards relating to the blockchain (e.g. block rewards). In particular, parties maybe allocated a number of signatures in adynamic membership multi-signature (DMMS) based on an amount and/or difficulty (e.g. number of steps) of output values submitted by that party.

Equally, the role of a party in the addition of a future block to the blockchain 10 may be defined based on the submission of references to output values, e.g. a node of the blockchain may be defined as a block proposer for and/or validator of a currenl or future block based on this submission. This may comprise the party that first provides a suitable reference (e.g. a reference to an output value calculated using the target number of steps) being selected as a block proposer. More generally, the ability of parties to contribute to the building of a consensus on the history of a blockchain may depend on the provision of references to output values.

Where the verifiable delay function is used as an anti-sybil factor for the blockchain, it may be beneficial to ensure that at least one output value is available for each block of the blockchain. The steps described in relation to Figure 8 may still be carried out, where, for example: a node of the blockchain 10 provides a reference to an output value that is used as a proof of work the nth block. This output value is based on an input value taken from the (n-δ)th block and relates to T ₁ steps (where T ₁ is defined in the (n-δ)th block). If δ is less than a desired value, then an increased number of steps T ₃ = ( T ₁ +Δ) is defined in the nth block.

10 There is typically some lag before this increased number of steps becomes relevant. Therefore, a node of the blockchain (which may be the first node, but is typically a different node) can provide another reference to an output value that is used as a proof of work the (n+1)th block. This output value uses an input value taken from the (n+1-δ)th block and relates to T ₂ steps (where T ₂ is defined in the (n+1 -δ)th block). Typically, δ is significantly greater than one. Therefore, T ₂ = T ₁ .

Eventually, the blockchain reaches a length where the input value for the verifiable delay function is taken from the nth block. Here the output value (e.g. for the (n+δ)th block) will be based on the nth block and on a value T ₃ that is defined in the nth block, where T ₃ > T ₁ .

The verifiable delay function may also be used with other types of blockchains, such as proof of stake blockchains, byzantine agreement blockchains, and proof of activity blockchains. Proof of activity blockchains are described in more detail in “Proof of Activity: Extending Bitcoin's Proof of Work via Proof of Stake. Bentov et al. (2014) With proof of activity blockchains a party may be required to submit a reference to an output value and/or a proof before being eligible to participate in the building of a consensus on the history of the blockchain 10, e.g. the addition of blocks to the blockchain. This may comprise the pool of possible participants being based on submissions and/or this may comprise a party that has been selected to participate in the addition of a block having a certain amount of time to submit a proof and/or output value.

The blockchain 10 may be configured to target a certain value of δ and or have a certain range of target δ values, δ relates to a calculation time required to determine an acceptable output value, which acceptable output value may be an output value calculated using a target number of calculation steps.

The nodes of the blockchain may be arranged to determine the value of δ for each block (e.g. determine on which block the input value for a certain output value is based) and increase or decrease the target number of steps accordingly, where this updated target number of steps is recorded on the blockchain. The value of δ may be determined over a number of blocks, since the time taken to determine that output value may not be constant; for example, where the required number of steps is equal to two steps, it may take somewhere between two and four blocks to find an output value to the verifiable delay function. Therefore an average (or median, or minimum) calculation time for a certain number of output values may be determined and used to determine the updated number of steps. Typically, the minimum calculation time is considered, where every time δ drops below a certain value the number of steps is increased.

The output values considered in this determination typically relate to previously calculated output values. In this regard, the calculation time may be determined as the difference between the timestamps of an input block and an output block. The determination of the updated number of steps may be based on output values in a proposed block (where this proposed block is the output block); however, this requires an estimation of the timestamp of the proposed block before the proposed block is included on the blockchain. Therefore, typically the determination of the updated number of steps is based on output values that are referenced in previous blocks of the blockchain. These previous blocks may comprise previous blocks of less than a certain depth (to ensure that the updated number of steps is relevant) and/or blocks of greater than a certain depth (e.g. where these blocks have passed a confirmation period). Therefore, the determination of the updated number of steps may depend on output values referenced between the blocks b _n _ _α and b _n _ _β , where α relates to a maximum depth and is typically less than 100 blocks, 50 blocks, and/or 20 blocks, and β relates to a minimum depth and is typically less than 3 blocks, 6 blocks, and/or 10 blocks. The number of steps may be incremented by one each time δ drops below a target minimum value of blocks δ _min . In some embodiments, an estimation of the (minimum) time per step (and/or the time per marginal computation step) is determined and the number of steps is updated based on this estimation. For example, the number of steps may be increased such that the determination of an acceptable output value is expected to require a target maximum value of blocks δ _max (where δ _max > δ,™). δ _min and/or δ _max may be defined in the blockchain 10 (e.g. when the verifiable delay function is first implemented on the blockchain). This enables the maintenance of a calculation time that is between an upper bound δ _max and a lower bound δ _min , where these bounds may be selected so that the number of steps is updated only occasionally.

Since there is typically a reward - and more typically a limited reward - provided for the provision of a reference to an output value (e.g. a mining reward and/or an eligibility to participate in the addition of future blocks), parties are incentivised to provide references to outputs value as soon as they are calculated. This enables an accurate evaluation of existing computing capability to be continuously determined and therefore enables an appropriate updated number of steps to be continuously determined.

Variable acceptable value

The above embodiments have considered an embodiment in which there is a reward for providing an output value for the verifiable delay function. This incentivises parties to provide output values in a timely manner. However, one problem with this is that it could lead to a single party with the best computing capability determining each output value first; this could dissuade other parties from getting involved (and from improving their own technology). Partly as a way to dissuade this, the determination of an acceptable output value using the verifiable delay function may have an element of uncertainty. This encourages a range of parties with comparable computing resources to attempt to determine output value for the verifiable delay function.

The element of uncertainty refers to an element that makes a first calculator of an acceptable output value unpredictable - the element may or may not result in equal opportunities for each party calculating the verifiable delay function. For example, a function that determines an acceptable value may comprise a weighting against past solvers in which solvers of previous blocks are required to perform more steps to reach an acceptable output value. Such a weighting may, for example, be based on the output values referenced in the previous fifty blocks of the blockchain 10 (where parties may need to provide a unique identifier to be eligible to provide an output value).

Typically, a minimum number of steps ( S _min ) required to provide an acceptable output value is recorded on the blockchain 10. An acceptable output value must then relate to a number of steps S that is greater than or equal to S _min (S ≥ S _min ) and to a value that is between a certain range. For example, the output value may need to be calculated using at least five computation steps and may need to be less than 0.1.

Typically, the acceptable output value is based on the number of calculation steps and/or is a function of the number of steps, for example if five steps are calculated the output value may need to be less than 0.1 and if six steps are calculated the output value may need to be less than 0.2. Typically, a range of acceptable output values is arranged to increase with the number of steps.

This method may be used with a maximum number of calculation steps, where this maximum number may be set by appropriately setting the range of acceptable output values; if a maximum number of steps S _max have been calculated, any output value may be acceptable. In particular, where this method is used as part of a consensus mechanism, the provision of a maximum number of steps enables an acceptable output value to be found in a predictable amount of time (to avoid an unintended slowdown of the blockchain 10).

In some embodiments, the output of the verifiable delay function is further processed before being compared to an acceptable value. For example the provided output value may be hashed and/or may be used as the input to a random number generator (e.g. a Mersenne twister). This step can be used to ensure that the value compared to the acceptable value is randomly distributed (e.g. so that the leading digit of the compared value is equally distributed between 0 and 9). The output value that is recorded on the blockchain may be the original output value and/or the processed output value. Referring to Figure 9, a method 170 of recording on the blockchain 100 a reference to an output value based on an element of uncertainty is described. This method is typically performed by a party participating in the addition of a block to the blockchain, such as a block generator, proposer, validator, and/or signer.

In a first step 171, an output value relating to a verifiable delay function is identified. This may comprise a node receiving a reference to the output value as part of a transaction, which transaction is proposed for inclusion in a block of the blockchain 10.

In a second step 172, the number of steps performed to obtain this output value is identified.

In a third step 173, it is determined whether the output value is within an acceptable range of values given the number of steps used to calculate this output value. This may comprise determining whether the number of steps is greater than a required minimum number of steps (where no values are acceptable beneath this minimum number of steps). Typically, the acceptable range is defined in the blockchain 10, where the acceptable range may be updated based on previous output values (and previous calculation times).

In a fourth step 174, if the output value is within the acceptable range of values, a reference to the output value is recorded on the blockchain. The number of steps required to obtain the output and/or the computation time per step may then be evaluated in order to determine whether the parameters for the verifiable delay function (e.g. the minimum number of steps S _min and/or the range of acceptable values should be updated).

The party that has calculated the output value may receive a reward for this calculation. This reward is typically recorded in a block of the blockchain 10 in which the reference to the output value is recorded.

In an optional fifth step 175, the acceptable range is updated if it is determined that the verifiable delay function has been solved too quickly (or too slowly). This determination is typically based on a minimum desired calculation time and/or an average calculation time over a number of blocks. It will be appreciated that the acceptable range may be used to define a minimum and/or maximum number of steps (e.g. by setting no output values to be acceptable below the minimum number of steps S _min ).

In some embodiments, the reference is not recorded on the blockchain 10. However, this can cast doubt on the determination of the updated acceptable range and/or the updated number of steps since without the reference other nodes may be unable to check that the updates are appropriate. So it tends to be desirable to record the reference on the blockchain.

Referring to Figures 10a and 10b, examples of acceptable values are described.

Typically, the output value is normalised before comparison to an acceptable value so that the output value is always between 0 and 1. Using the exemplary figures described with reference to Figure 4a, this may lead to values of:

4/10 = 0.4 (at T = 1);

16/100 = 0.16 (atT = 2);

256/1000 = 0.256 (at T = 3); 65536/100000 = 0.65536 (at T = 4);

It will be appreciated that these values are based on a low input seed and low numbers of squaring (and so, for example, the leading digit of the fourth value could be predicted based on the leading digit of the third value). In practice, the input value is typically based on a preceding block of the blockchain and a large number of steps are typically required. Furthermore, typically the operation required by the verifiable delay function is based on modular arithmetic (e.g. it is not a simple squaring operation). Therefore, the value at each step is effectively randomly distributed (where the digits of this value cannot be reliably predicted before the operation has been performed). Nevertheless, the output value may be hashed and/or randomised using a random number generator before comparison to the acceptable value.

It will be appreciated that a normalisation step is not necessary. This normalisation step is used primarily so that the acceptable range is always between 0 and 1 (and this enables the use of a constant acceptable value range as the required number of calculation steps increases); however, in practice, the acceptable range may be between any two values. Referring to Figure 10a, the acceptable values for the output value may be linearly dependent on the number of steps calculated between a minimum number of steps ( S _min ) and a maximum number of steps ( S _max ). Typically, the acceptable value relates to a range, so that for example, any value between 0 and 1 is acceptable at S™ and any value between 0 and 0.5 is acceptable at This distribution provides an average number of steps required to

5 find an acceptable value of S _ave

Referring to Figure 10a, the acceptable range of values for the output value may be nonlinearly and/or exponentially dependent on the number of steps calculated between a minimum number of steps (Tmm) and a maximum number of steps (T _max ), for example there may be an exponential relationship between the acceptable value and the number of steps. This distribution provides an average number of steps required to find an acceptable value of While the examples given in Figures 10a and 10b have an acceptable value that is 1 at and/or above a maximum number of steps S _max , it will be appreciated that this is not necessary. The acceptable value may be below 1 at any number of steps, so that a party is never certain to achieve an acceptable value. Such an implementation increases the uncertainty for each party, which may be beneficial in some circumstances. However, this also prevents the provision of a maximum time to find an acceptable output value, and so is disadvantageous in other circumstances. Typically, the distribution has the following properties:

Where: S _min is a minimum number of steps. S _max is a maximum number of steps. r(S) is an output value determined after S steps of calculation.

AV(S) is an acceptable value (and/or range) for S steps of calculation.

The above properties may relate to:

No value being acceptable beneath a minimum number of steps S _min .

The average number of steps taken to find an acceptable value being equal to a target number of steps S _target . The cumulative distribution function for the finding of an acceptable value being 1 at the maximum number of steps S _max ; in other words, an acceptable output value will always be found at or before the maximum number of steps S _max . The values S _min , S _max , S _target , and/or AV(S) may be defined in a block of the blockchain. Typically, S _min , S _max , and/or S _target are defined in one or more blocks of the blockchain and are updated based on the calculation times for previous output values. S _min is typically greater than one. In some embodiments, there are a number of possible input values (e.g. different hashes of an input block). Therefore, if S _min is one (or is low), instead of performing a large number of steps a party may simply try the first step repeatedly with different input values, e.g. restart the calculation of the verifiable delay function if an acceptable output is not found quickly. This can lead to a calculation time for the verifiable delay function being overestimated. Having a substantial minimum number of steps discourages this behaviour. S _max is typically a finite value, so that it is guaranteed that an acceptable value will be found after a maximum number of steps. A maximum calculation time for the verifiable delay function can then be determined based on an estimation of a computation time per step.

This is particularly advantageous where the addition of blocks to the blockchain 10 is based on the verifiable delay function, for example where the calculation of the verifiable delay function is used as a proof of work. In such instances, the maximum number of steps S _max can be used to set a maximum time between the addition of blocks to the blockchain. This enables censorship resistance to be guaranteed so long as the number of steps to obtain a censorship resistant output value is greater than this number of steps S _max .

In an example, a second block may be added to the blockchain based on the calculation of an acceptable output value, which output value relates to an input value from a first block. The maximum time taken for the calculation of such an acceptable output value (and thus for the addition of a block) is related to the maximum number of steps required to find an acceptable output value S _max . A censorship resistant random number can then be calculated using an input value based on the first block and a number of steps that is greater than the maximum number of steps required to find an acceptable output value S _max ·

It will be appreciated that any of (or none of) S _min , S _max and S _target may be defined in the blockchain. The inclusion of each of these values has benefits even if the other values are included. For example, an implementation of the blockchain may only have a defined value of S _min (to prevent users restarting the calculation of the verifiable delay function) or may only have a defined value of S _max (to guarantee censorship resistance).

The probability of the output value being an acceptable value may increase from 0% to 100% between S _min and S _max as shown in the exemplary distributions of Figures 10a and 10b. More generally, the acceptable value may depend on the verifiable delay function used and may be any function of the number of steps. Indeed, the acceptable value may be independent of the number of steps.

In some embodiments, it is desirable to include an output value in each and every block of the blockchain. Therefore, the use of a range of possible steps may be seen as problematic (since the calculation time is not guaranteed). In such embodiments, a plurality of parties may be able to propose an output value to a block based on a number of calculation steps, where a winning output value may be selected from the submissions. This winning output value may be determined based on one or more of: a relative number of steps calculated (of all submissions) and/or a proximity to an acceptable output value. Typically, there are a plurality of parties calculating the verifiable delay function at any one time, so it is likely that an acceptable output value will be available for each block.

In some embodiments, the determination of an output value for a verifiable delay function is used as part of an antisybil factor and/or consensus mechanism; more generally, the output value may be recorded on the blockchain 10. In some embodiments, one or more output values - and/or proof of the determination of one or more output values - are recorded on a block of the blockchain and a reward is provided for these values. This reward may be a financial reward (e.g. an amount of a cryptocurrency) and/or a probability of participation in the building of a consensus on the history of the blockchain. In some embodiments, the blockchain is configured so that the probability of a party being eligible to contribute to the building of a consensus on the history of a blockchain (e.g. the probability of a party being eligible to be selected to participate in the addition of a block to the blockchain) is dependent on that party determining (optionally, acceptable) output values. For example, each of the nodes of the blockchain may be capable of providing references to output values, and a proposer for a subsequent block of the blockchain may be selected from the pool of nodes that have provided references to acceptable output values. The probability of a party being selected (or more generally a reward for a party for providing an output value) may depend on one or more of

A number of output values determined.

A difficulty of each output value (e.g. the number of steps calculated to obtain the output value).

The input value on which the output value is based.

A use of the output value (e.g. if the output value is used in a lottery, the provider may be rewarded).

Typically, each output value is required to begin from a different seed (e.g. to avoid a party taking a previous output value, calculating a further step, and submitting the new output value). To this end, there may be a plurality of possible inputs for each block and/or the party utilising the verifiable delay output may be able to apply a modifier to the input based on a previous block. This enables multiple parties to calculate (and benefit from) output values based on a given previous block and so incentivises parties to determine an output value even if they are not confident they will be the first determiner. The modifier applied is typically a publicly available modifier, such as a public key relating to the party determining the output value.

Proof that a party has calculated the verifiable delay function may be supplied in the form of a share verification contract (SVC). As an example, a share verification contract may comprise a smart contract which can verify the validity of a group of proofs and/or output values submitted to the contract (verification may be probabilistic). Here, the requirement is that it should not be possible, on average, to profit from submission of invalid output values. In this context, validity of a proof requires that:

The output value corresponds to an input value based on a previous block of the blockchain.

The output value is not a duplicate of a previously submitted output value.

Typically, validity of a proof requires the calculation of the output value to relate to at least a minimum number of steps.

Typically, validity of a proof requires each output value referenced in a share verification contract to relate to the same number of steps. This enables a computation time per step to be determined based on the number of referenced output values and the number of steps per output value. Such a determination may be difficult (or impossible) if output values are referenced that relate to different numbers of steps.

SVCs are explained in more detail in “Loi Luu, Yaron Velner, Jason Teutsch, and Prateek Saxena. Smartpool: Practical decentralized pooled mining. In 26 ^th {USENIX} Security Symposium ({USENIX} Security 17), pages 1409 - 1426, 2017”.

Similarly, proof that a party has calculated the verifiable delay function may be provided to a smart contract recorded on the blockchain. This smart contract may be arranged to provide a reward in return for the provision of the proof.

In some embodiments, there is a limited reward available for the submission of output values (e.g. a maximum block reward and/or a maximum number of eligible participants for a future block). This incentivises parties to provide output values as soon as they are determined.

A plurality of parties submitting a reference to an output value may be able to claim a portion of the reward, where only a certain number of submissions (and/or a certain number of submissions relating to a certain number of steps) receive a portion of the reward. There may be a different reward pool available for a plurality of numbers of steps (e.g. so that the pool of rewards for output values relating to four steps is distinct from the pool of rewards for output values relating to three steps).

The reward receiving by a party submitting a reference may be based on the block on which the input value to the verifiable delay function is based, so that parties submitting output values and/or proofs based on the nth block may be able to receive a reward for recording a proof in any of the blocks after the nth block. This reward is typically limited to reward prompt recording of proofs, where the reward is eventually exhausted and parties submitting references after this exhaustion are not rewarded. In some embodiments, there is a limited period during which a reward can be claimed; this period may be based on an expected calculation time and/or on the time at which a first acceptable output value is received.

In some embodiments, there is a limited time available for claiming a reward; for example, there may only be a reward for output values submitted within a certain number of blocks from an input block (the block on which the input value for the verifiable delay function is based). This certain number of blocks may be based on a maximum expected calculation time, which can be determined from previous calculations of the verifiable delay function. Similarly, there may only be a reward for verifiable delay functions that relate to a certain number of steps, e.g. a number of steps equal to or less than a maximum number of steps S _max . This discourages parties from persisting with the calculation of the verifiable delay function beyond a certain point (where the computing power available for the last step may differ from that available for the first step, thus reducing the accuracy of a determination of the computation time per step).

The reward may depend on an expected calculation time, where a greater reward is awarded for providing a reference to an output value relating to a calculation time that is less than the expected calculation time (as compared to a reference to an output value relating to a calculation time that is less than the expected calculation time).

In some embodiments, the reward is a function of the calculation time. Typically, the reward is a decreasing function of the calculation time, where lower calculation times result in a higher reward. The reward may then depend on an improvement relative to the expected calculation time, e.g. so that similar percentage increases in calculation time lead to similar rewards. This encourages parties to provide references to output values as soon as those output values have been calculated. More specifically, the reward may be a monotonically decreasing function of the calculation time. In some embodiments, the reward is a function of the number of steps performed to calculate the output value. Typically, the reward is an increasing function of the calculation time, where a higher number of steps results in a higher reward. More specifically, the reward may be a monotonically increasing function of the number of steps.

In some embodiments, the output value is used as a random beacon. In such embodiments, it can be beneficial to allow the recording of multiple output values relating to different numbers of steps. A high number of steps is useable where the random beacon is used for a valuable purpose, e.g. a lottery with a high winning value, whereas an output value based on a lower number of steps, which can be determined more quickly, can be used for less valuable purposes.

In a practical example, the purchase period of lottery tickets for a lottery based on a (n-δ)th block, and verifiable delay function that uses S steps may start as soon as the (n-5)th block has been added to the blockchain (or once it has reached a certain block depth). This number of steps S is related to a minimum calculation time of δ blocks, so that all participants are confident that no output value will be determined before the addition of the nth block. The purchase period may then close at the (n-1)th block, and winners are decided when an acceptable output value is determined; considering the exemplary distributions, this acceptable output value may be recorded in the nth block or in a following block. Typically, the range of acceptable outputs is selected so that participants are confident that the acceptable output value will be recorded before a (n+n)th block. The values of each of these parameters (δ, S, η) can be selected based on the use of the output value (e.g. on the value of the lottery prize). The incentive of a party to censor an output value (and not propose it for addition to the blockchain) depends on the lottery reward; therefore, low-value, frequently- run, lotteries may use low values of δ, S, and η, whereas higher value lotteries may use high values of 5, S, and η.

It will be appreciated that while a lottery may relate to a financial lottery (with a monetary prize), lotteries may be run for a variety of other purposes. For example, the lottery may relate to a chance of a node being selected to participate in the addition of a future block to the blockchain.

In some embodiments, the reward for providing an output value is dependent on that output value being used. For example, a party wishing to use a random number may need to pay the party that calculated that random number. This can be achieved using smart contracts and/or operation codes on the blockchain. For example, an operation code OP_RAND may be defined that uses an output value recorded in a present block as a random number. The use of this operation code within a transaction may result in an amount of transaction fees being transmitted to the provider of the random number.

More specifically, a first party that wishes to use a random number may transmit a transaction to a node that comprises a request for a random number (e.g. OP_RAND). The node may then include this transaction in a proposed block. At a similar time, the node may receive an output value for the verifiable delay function from a second party. The node may then use this output value as the random number - since this output value will not be known to the first party at the time of the request. The second party may then receive fees from the first party. The request may also request a certainty of the random number, e.g. a required number of steps and/or a required calculation time relating to the output value.

In another example, the first party may use a transaction to request the use of an output value whose input value is determined by a certain block (e.g. the block in which the transaction is included). Typically, this transaction references a smart contract to guarantee fee will be paid when the output value is determined. This transaction requesting the use of the output value may be included in an (n-δ)th block. A number of parties then attempt to find an acceptable output value using an input value based on this (n-δ)th block until one party succeeds. A reference to the calculated output value is then recorded in the nth block of the blockchain. This leads to the provider of the calculated output value obtaining a reward. This can be used to run a lottery, where parties are able to purchase tickets (e.g. guess the output value) in between the (n-6)th block and the nth block, and where the initial smart contract may define a reward to be awarded to a winning party once the calculated output value is recorded. Such a lottery may provide a financial reward or may, for example, select a proposer of the next block. Here, each of the nodes of the blockchain may be automatically entered into the lottery (e.g. based on a public key relating to these nodes), where the proposer of each block is based on a lottery run in the preceding block.

In some embodiments a time to drain mechanism is used to distribute rewards based on output values and/or proofs for the verifiable delay function. With a time to drain mechanism, fees are distributed whenever a following block and/or proof of work solution references the output value and/or a block containing the output value. Time to drain mechanisms are described in more detail in “Blockchain-Free Cryptocurrencies: A Framework for Truly Decentralised Fast Transactions. Boyen et al. (2016)

Alternatives and modifications

Various other modifications will be apparent to those skilled in the art. For example, the detailed description has primarily considered the verifiable delay function being used with a proof of work anti-sybil factor and/or consensus mechanism. The verifiable delay mechanism may equally be used with other factors/mechanisms; for example, the verifiable delay function may be used with a proof of stake anti-sybil factor. As with proof of work, in this circumstance the submission of proofs and/or output functions relating to the verifiable delay function may still result in an award being awarded to the party providing the output value. The award may be monetary and/or may relate to the probability of a party being eligible to participate in the addition of a block to the blockchain 100.

While the detailed description has primarily considered the transfer of a digital asset, it will be appreciated that more generally ‘transactions’ may relate to the storage of any form of information. The blockchain 10 may for example store information relating to the behaviour of a party.

The information stored on the blockchain 10 may be used to present an output to a user and/or to trigger an alarm. For example, the presence of a particular record on the blockchain may result in an alert being generated and displayed to a relevant party. Further, one or more parties may be able to view records stored on the blockchain(s), where these records may inform decisions made by those parties. As examples, the records may enable governments to enforce laws, parents to supervise the activities of their children, or companies to develop more efficient products. In general, the blockchains enable parties to take action based on recorded information, where this information is typically recorded in an immutable manner.

While the detailed description has primarily given examples with reference to Bitcoin, it will be appreciated that the disclosed systems and methods are equally applicable to other blockchain implementations, where appropriate modifications may be required to take into account differing consensus mechanisms and capabilities.

While the detailed description has primarily described the methods being applied to blockchains, it will be appreciated that the methods and systems described herein may be applied to any public consensus network (PCN) and/or distributed consensus network (DCN), e.g. blockchains, graphchains, Directed Acyclic Graph (DAG), Avalanche, and the internet of things. In such embodiments, the PCN may not comprise blocks, so that where information has been described as being contained in a block or a block header, more generally such information may be included in, or contained in, a PCN.

This method may be used in existing blockchains. For example, the verifiable delay function may be defined in a transaction and/or in reference to an account, where this transaction/account can be referenced in following blocks of the blockchain.

The method may, for example, be used to replace the verifiable random function used by Algorand to generate seed values.

It will be understood that the present invention has been described above purely by way of example, and modifications of detail can be made within the scope of the invention.

Reference numerals appearing in the claims are by way of illustration only and shall have no limiting effect on the scope of the claims.