GB2548802A

GB2548802A - Methods for creating and verifying an electronic user identity

Info

Publication number: GB2548802A
Application number: GB1604789.6A
Authority: GB
Inventors: Chu Hector
Original assignee: Bitcred Ltd
Current assignee: Bitcred Ltd
Priority date: 2016-03-22
Filing date: 2016-03-22
Publication date: 2017-10-04
Also published as: GB201604789D0

Abstract

Methods are disclosed for creating a verifiable electronic user identity using a blockchain data structure, together with processes for verifying a user identity created by such methods. A method of creating a user identity comprises generating a new address on a data processor (106), sending the new address to a user's electronic device (120) via an external network, determining with the data processor that there is a first transaction on a blockchain stored on a peer-to-peer network (114), or queued for inclusion in the blockchain, wherein the new address is an output of the first transaction and a user address is an input of the first transaction, detecting the current height of the blockchain, and sending to a data store a user identity for the user comprising the user address that was an input of the first transaction and a height value dependent on the current height of the blockchain.

Description

Title: Methods for Creating and Verifying an Electronic User Identity Field of the Disclosure

The present disclosure relates to methods for creating a verifiable electronic user identity and processes for verifying a user identity created by such methods.

Background to the Disclosure A known method of creating a verifiable user identity is public-key authentication. Suppose that users A and B want to form an electronic relationship or binding such that at any time later, A may verify the identity of B for authentication purposes. This can be accomplished through the use of public-key cryptography, which is well-known technology that will not be described in detail here. B sends A his public key over a secure channel. At a later time A sends B a “challenge”. B proves who he says he is by encrypting the challenge (or a hash of it) with his private key and sending the result back to A. A verifies B's identity by decrypting the challenge with the public key and verifying that the result matches the challenge.

This protocol may be defeated by what is known as a “man-in-the-middle” attack (“MitM”), for which no general solution is known. A workaround currently employed on the web is Transport Layer Security (better known as HTTPS) where trust is mutually derived from a set of third-parties known as certificate authorities (CAs).

Summary of the Disclosure

The present disclosure provides a computer-implemented method of creating a verifiable electronic user identity, the method using an electronic data processor and an electronic data store and comprising the steps of: a) generating a new address on the data processor; b) sending the new address from the data processor to a user’s electronic device via an external network; c) determining with the data processor that there is a first transaction on a blockchain stored on a peer-to-peer network, or queued for inclusion in the blockchain, wherein the new address is an output of the first transaction and a user address is an input of the first transaction; d) detecting with the data processor the current height of the blockchain; and e) sending to the data store a user identity for the user comprising the user address that was an input of the first transaction and a height value dependent on the current height of the blockchain.

In this way, a method enabling a user to establish his identity electronically and securely is provided. The method achieves this using a blockchain data structure.

Providing that the new address is truly new and is not disclosed to anyone other than the user, the first transaction demonstrates that the user address is under the control of the user to which the new address was sent. A key advantage over public-key authentication is that a user identity created in accordance with the present disclosure may be transferred completely and securely to a third party (that is, B in the example above may transfer his identity to someone else without the involvement of A, such that A will be able to discover the transfer later and authenticate the third party). The transfer may be complete in the sense that, after the transfer, the transferor is no longer able to use the identity.

Also, a user identity created in accordance with the present disclosure may enable a user to verify his identity with a third party without needing to provide a username; use of the user identity alone may be sufficient.

In a preferred embodiment, the user identity sent to the electronic data store includes the new address. This “new address” may provide a useful and convenient way to refer to the new user identity. It may be used to refer to the identity, irrespective of whether the identity has been transferred to a new owner or not.

Preferably, the method includes the steps of determining a second transaction output value with the data processor, sending the second transaction output value from the data processor to the user’s electronic device via the external network, generating after step c) a second transaction with the data processor which sends the second transaction output value, wherein the user address is an output of the second transaction, and outputting the second transaction from the data processor for addition to the blockchain. In this way, confirmation that the user identity has been successfully established may be included on the blockchain in a manner detectable by the user.

The new address may be the input, or one of the inputs of the second transaction. Alternatively, another address may be used. The second transaction may be detected by the user with reference to the second transaction output value.

In a preferred embodiment, the method includes determining a first transaction output value with the data processor, and sending the first transaction output value from the data processor to the user’s electronic device via the external network, wherein it is determined in step c) that the first transaction sent the first transaction output value. Specifying a particular value for the first transaction may provide added assurance that the first transaction is correctly identified.

According to a further implementation, the method includes the steps of: - prior to step a), receiving with the data processor a request for a verifiable user identity from a requester’s electronic device via the external network; and - after step e), sending the user identity to the requester’s electronic device via the external network.

In this manner a user identity may be created by a service provider in response to a request from a customer. The new user identity sent to the requester may include the “new address” referred to above. The service provider (or the requester) may store additional data specific to the requester (and/or the requester’s purpose for the user identity) in association with the “new address”. A method of authentication is disclosed which is an implementation of a challenge-response protocol (the response being a digital signature of the challenge) over a blockchain data structure. A data structure representing a verifiable user identity is created (also referred to here as an “address graph”) using transaction graphs recorded on the blockchain. It is used to represent an identity, and may be formed from a starting block height “H” and root address.

For every “child address” in an address graph extending from the root address, there exists a chain of transactions (with height >=H) paying from the root address to the child address. An address graph is terminated when it is transferred, as discussed below.

The present disclosure also provides a method of verifying a user identity created using a method described herein. The verification method uses an electronic data processor and an electronic data store and comprises the steps of: i) generating a third transaction output value with the data processor; ii) sending the third transaction output value from the data processor to the user’s electronic device via the external network; iii) determining with the data processor that a third transaction is on the blockchain, or queued for inclusion in the blockchain, which sent the third transaction output value after the sending step ii) above; and iv) identifying with the data processor a chain of transactions on the blockchain which leads back from the third transaction to a user address of a user identity in the data store.

The term “chain of transactions” is used herein to refer to a series of transactions linked together in the sense that a common address exists between the outputs of one transaction and the inputs of the next transaction in the chain. It may therefore be seen as a chain of addresses linked by the presence of transactions between consecutive addresses in the chain of addresses. The transactions of a chain of transactions do not therefore need to have any dependencies on each other, that is, it is not essential for the next transaction to spend the output of the preceding one in the chain.

Preferably, at least one (or more preferably each) transaction of the chain of transactions occurs at a height in the blockchain which is greater than the height which corresponds to the height value of the user identity (that is, a height in the blockchain greater than the “current height” identified when the user identity was created, and on which the height value is dependent).

It will be appreciated that transactions queued for inclusion in a blockchain are usually treated as having an infinite height. They would therefore always be considered to occur at a height greater than that of the user identity.

Accordingly, a user identity may be authenticated by issuing a transaction (response) that extends its address graph. The transaction outputs a value known by the challenger in advance so that it may be filtered from the unconfirmed transaction stream of the blockchain peer-to-peer network and linked back to the identity's address graph. A primary advantage of creating a user identity over a blockchain as described herein is that the user identity may be securely transferred. A user identity created as described here may be transferred by effectively redefining its address graph. This may preferably be achieved with a specially crafted transaction that contains an output that loops back to the initial root address associated with the user identity. The root address of the address graph can then be redefined as a new address that is under different ownership.

The data processor may determine in step iii) that the third transaction output was sent from a first user address to a second, different user address. Using a different address (which may be under the control of the same user) to receive the transaction output may be preferable to increase privacy, since it may be less obvious to an outsider that someone made a transaction to himself if the sending and receiving addresses are different.

The method may include a further step of storing in the electronic data store a record identifying the chain of transactions found in step iv). Alternatively, the method may include a step of storing in the data store a record identifying a set of addresses which form a chain of addresses in the chain of transactions found in step iv). These records may be used to respond more readily to a future challenge to the identity concerned.

It may be more expedient to store the chain of addresses from the third transaction output to the user address. This set of addresses for a given user identity may be enlarged by subsequent challenge operations. Since the addresses in this set of addresses are known to have paths (that is, chains of transactions) linking to them from the user address, subsequent challenge operations may be made more efficient by checking for a path from the third transaction output to an address in the stored set, as this implies the existence of a path to the user address.

According to a further embodiment of the present disclosure, a user identity which has been transferred may be verified by carrying out a verification method as described above and then, after identification step iv), identifying with the data processor a fourth transaction on the blockchain which comprises first and second outputs, of which the first output leads back to the user address of the stored user identity and the second output leads to a further user address, wherein there is a chain of transactions formed by transactions on the blockchain which leads back from the fourth transaction to the user address of the stored user identity; and replacing the stored user identity in the data store with a further stored user identity, wherein the further stored user identity comprises the further user address and a further height value dependent on the height in the blockchain of the fourth transaction. A user identity which has been the subject of a further transfer may be verified by an additional step of identifying with the data processor a chain of transactions, the chain being formed by transactions on the blockchain or queued for inclusion in the blockchain, which leads back from the third transaction to the further user address of the further stored user identity in the data store. Preferably, at least one (or more preferably each) transaction of the chain of transactions occurs at a height in the blockchain which is greater than the height value of the further user identity.

In a further preferred embodiment, the verification method may include the step that after the fourth transaction is identified but before replacing the stored user identity in the data store, the data processor determines that there is not a fifth transaction at the same height as the fourth transaction that also comprises first and second outputs, of which the first output leads back to the user address of the stored user identity and the second output leads to another user address, wherein there is a claim of transactions formed by transactions on the blockchain which leads back from the fifth transaction to the user address of the stored user identity.

By way of example, the fourth transaction may be a transfer of user credentials from a user identity B to user identity C. According to the further preferred embodiment, the data processor checks that there is not a transfer from B to another user identity D (the “fifth transaction”) at the same height as B to C, as that would make ownership of the user credentials ambiguous.

According to a still further preferred embodiment, the verification method includes the steps of: after the fourth transaction is identified but before replacing the stored user identity in the data store, determining with the data processor that there is a sixth transaction on the blockchain which comprises first and second outputs, of which the first output leads back to the further user address of the further stored user identity and the second output leads to a further further user address, that there is a chain of transactions formed by transactions on the blockchain which leads back from the sixth transaction to the further user address of the further stored user identity, and that the further further user address does not match any of the previously seen further user addresses including the user address of the stored user identity; and replacing the further stored user identity in the data store with a further further stored user identity, wherein the further further stored user identity comprises the further further user address and a further further height value dependent on the height in the blockchain of the sixth transaction.

In this manner, the method checks that where there is a transfer on the blockchain from user identity C (in the example above) to another user identity E (the “sixth transaction”), that the user address of E is not the same as any of the previously seen further user addresses (including the user address of the stored user identity). This serves to check that E does not belong to the set of user addresses detected in the chain of transfers from the user address to C (that is, it does not equal B or C in this example), as this would create a cycle in the chain of transfers which would be potentially ambiguous. If this is not the case, then the method records in the data store that the credentials have been validly transferred from C to E. However, a chain of transfer transactions of user credentials from B to C to E to F and then back to B would be detected by this method (with the transfer from F to B corresponding to the “sixth transaction” and B to C to the “fourth transaction”) and may be disallowed as possibly introducing ambiguity in the ownership of the credentials.

In a yet further preferred embodiment of the verification method, the data processor determines that the further further user address does not match any of the previously seen further user addresses including the user address of the stored user identity and that the fourth transaction comprising the first output that leads back to the further user address or the user address of the stored user identity is at the same height as the sixth transaction.

Accordingly, the embodiment defined immediately above is modified to make an additional check that a cycle in the chain of transfers has not been created which is formed by transactions at the same height in the blockchain. For example, a chain of transfer transactions of user credentials from B to C to E to F and then back to B, with each of these transfers at the same height in the blockchain, would be detected by this method and may be disallowed as definitely introducing ambiguity in the ownership of the credentials.

The method may include the steps of: prior to step i), receiving with the data processor a request for verification of a user’s identity from a requester’s electronic device via the external network; and after step iv), sending a response to the requester’s electronic device via the external network indicating that the identity of the user has been verified.

Accordingly, a service provider may verify a user identity in response to a request from a customer.

Also disclosed are systems, devices, and software associated with the present methods.

Brief description of the Drawings

Prior art and embodiments according to the present disclosure will now be described by way of example and with reference to the accompanying schematic drawings, wherein:

Figure lisa diagram to illustrate the ordering of blocks in a blockchain;

Figure 2 is a diagram representing two inter-related transactions on a blockchain;

Figure 3 is a diagram illustrating an address graph formed from the two transactions shown in Figure 2;

Figure 4 is a diagram representing an address graph depicting a bind operation according to an embodiment of the invention;

Figure 5 is a diagram representing an address graph depicting a challenge operation in relation to the binding depicted in Figure 4;

Figure 6 is a diagram illustrating an address graph depicting a transfer operation associated with the binding depicted in Figure 4;

Figure 7 is a block diagram illustrating a computer-implemented system according to an embodiment of the present invention;

Figure 8 is a block diagram illustrating another computer-implemented system for carrying out an embodiment of the invention;

Figure 9 is a block diagram illustrating steps involved in the creation of a user identity according to an embodiment of the invention; and

Figure 10 is a block diagram illustrating steps involved in verifying a user identity according to an embodiment of the invention.

Detailed Description

The present disclosure provides methods which utilise a known type of computer-implemented structure for recording transactions referred to as a “blockchain”. A blockchain (or block chain) establishes a partial ordering over the set of transactions contained within it. That is, a transaction either comes before another (in a time-based ordering known as “height”), or they conceptually occur simultaneously. The ordering is given by the height of the blocks containing the transactions, the blocks themselves being totally ordered by this relation. Figure 1 shows three blocks numbered “n-2”, “n-1” and “n” of increasing height from n-2 to n.

Transactions have an additional partial ordering that is defined by their inputs and outputs. For instance, a transaction's input may use the output of another transaction. In the example shown in Figure 2, a first transaction, Tl, has two inputs A and B, and two outputs C and D. A second transaction, T2, has C as an input and two outputs E and F. The second transaction T2 comes after or is dependent upon the preceding transaction Tl, as it uses the output C from Tl. This ordering must match the ordering imposed by the blockchain. For example if a transaction T2 depends on a transaction ΤΙ, T2 cannot precede T1 in the blockchain (but they may appear within the same block).

In order to prevent double usage of amounts tracked using the blockchain, the blockchain imposes an additional rule: if T2 does depend on an output of Tl, there cannot be a transaction T3 that depends on the same output also.

The present disclosure seeks to make advantageous use of these properties of blockchains

One feature to note is that history going further back along the blockchain becomes exponentially harder to revise. Thus transactions entering the blockchain eventually become permanent.

The digital currency “Bitcoin” is the first known implementation and application of a blockchain. Its blockchain is maintained by a peer-to-peer network of miners utilising cryptographic proof-of-work. The present disclosure may be implemented using Bitcoin, but may in principle utilise any blockchain-like system.

Address

The term “address” is used herein with the meaning commonly used in the context of blockchain networks, namely an identifier utilising a standard format associated with the blockchain concerned. More particularly, it may be used to mean a transaction output utilising a standard script format.

The two main kinds of address used on the Bitcoin network are a “public key hash” (PKH) and a “pay-to-script hash” (P2SH).

Address graphs

For the purposes of the present disclosure, transactions may be considered to have one or more input addresses and one or more output addresses. Each transaction may be viewed as defining links or edges in a graph, where every input address has a directed edge towards each output address. For instance Figure 3 depicts such an “address graph” formed from the two transactions shown in Figure 2 involving addresses A to F.

We can define such graphs over a blockchain by considering all transactions occurring on or after a certain block height. The present disclosure principally refers to address graphs specified by a pair of values: a root address and a height limit. Address graphs may be seen as synonymous with user identities.

Bind operation

Two entities or parties denoted as “Alice” and “Bob” may form a binding over the blockchain according to the present disclosure with the following procedure.

Alice generates a new address, in the form of a public key for example (preferably a public key hash (PKH)), that she controls. Alice also determines an amount X that must be paid to that address. Alice sends the address and the value of amount X to Bob. She stipulates upfront that if she receives the amount X she will send an amount Y in return to the address sending the amount X. Bob must follow this protocol in order to bind one of his addresses with that of Alice's. Figure 4 depicts this mechanism, whereby the dotted line delineates the boundary of Bob's address graph. This step is equivalent to Bob giving Alice his public key, which in this case is a PKH.

Note that a man-in-the-middle may fool Alice and Bob here. Apart from this consideration, by constraining the amount X that Alice can receive she increases her confidence that the identity of the address that pays her is indeed Bob. If Alice's address is not disclosed to anyone else then this also serves to have the same effect. By constraining the amount Y that she will pay in return, Bob will have increased confidence that the binding was confirmed and that the identity of the other address is Alice.

In a preferred embodiment, the transaction that pays to Bob depends on the transaction that pays to Alice, thereby proving that Alice has control of her address. Bob can verify independently that this condition is satisfied.

Both parties may lose out on only a network relay fee (an amount paid to the blockchain network in order that the transaction is relayed from node to node of the blockchain network), provided that the range of values that amount X can take is the same as amount Y, and both are uniformly distributed.

On conclusion of the operation Alice records her and Bob's addresses together with a height value dependent on the current height of the blockchain (such as the current height plus one). Bob's address and the height value form an address graph for Bob's identity, which will be needed by Alice to validate his identity in a challenge operation.

Challenge operation

Sometime later if Bob wants to prove his identity to Alice, they may follow the following procedure: Alice stipulates an amount X' that the other party must pay to themselves (the amount X' chosen such that it doesn't match that of any of Alice's other challenges that are occurring simultaneously). Bob then dutifully obliges. Assuming the transaction has enough of a fee to be flooded across the network, Alice should see Bob's transaction by virtue of that fact that it pays amount X' (in other words she is filtering the stream of new transactions by those that pay amount X'). Still, for any such transaction that she observes she is yet to discover if there is an identity behind it that she already knows about.

She needs to follow the following algorithm or similar: she has a database of bindings representing user identities, and she wants to know if the observed transaction derives from any one of them. She starts by forming the set S of all addresses of the other parties that she knows about. She must also know how far back to look in the blockchain - this will be up to and including the minimum H of the heights recorded against each of the records in Alice’s database.

Alice then takes the input addresses of the observed transaction and, for each one, attempts to find a path in the address graph back to the set S of addresses formed earlier. That is, for a given address, see if it is in S; if not, find all the addresses with an edge directed towards the address currently under consideration (notwithstanding the height limit H), and recursively examine each address found thus. Loops in the graph may not be followed, as this may be to the detriment of the termination of the algorithm. Preferably, Alice's own addresses should be excluded from consideration, that is, paths via them may be disregarded, as they would not form part of the various user identities.

Optimisations of the preceding algorithm may comprise pre-calculation or caching of the address graphs, parallel processing of address graphs using multiple threads/processors/nodes via OpenMP, MPI or MapReduce, for example, or remembering any path found for inclusion in the set S next time around.

If a path back to the set S is found, the path finding algorithm needs to be repeated but with just the single address graph associated in the database with the discovered identity. The actual address graph limited by the correct block height is used in this step (rather than the height limit H which is a minimum of the heights of all the address graphs). If a path is not found under this new criteria, the operation proceeds by removing that address graph from further consideration and the algorithm is repeated from the top starting by forming the set S without that identity.

Figure 5 shows an example of the challenge operation tracing a path through an address graph, from the transaction paying X' back up towards the root of the address graph B. The bind operation anchoring the address graph to A is also shown, and the dotted line again delineates the boundary of B's address graph.

In this way, Alice may identify and verify the address graph and hence the identity of the other party to the challenge. Extra steps may be carried out if the identity has been transferred to another party, as discussed below.

Transfer operation A user identity may be transferred to another party according to the present disclosure by creating a loop in its address graph. This is accomplished by sending a transaction from the identity's wallet as in the challenge operation, but the outputs of the transaction need to be specially chosen. In a preferred implementation, one output transfers an amount to the root of the address graph (so that transfers can be discovered easily) while the other output transfers to the address to which the identity is being transferred.

Figure 6 depicts this mechanism following on from the events leading up to Figure 5. X" is a second challenge operation, during which a path is again traced back to B; this time however a loop in the address graph is discovered at B, of which the other output of the looping transaction points to the root of the new address graph C. The dotted lines delineate the boundaries of the old and new address graphs.

It is preferable to wait for one confirmation (that is, until the transaction is included in a block of the blockchain) after a transfer of an identity before attempting to challenge it in order to ensure that there were no other transfers of that identity at the same block height. Otherwise the target address of the transfer might be ambiguous.

It is also preferable to check for any transfer cycles occurring within the same block (for example, A transfers to B transfers to A) which is also ambiguous. This is due to the fact that two transactions occurring at the same block height are considered to have occurred simultaneously provided that one does not depend on the other.

An ambiguous transfer may be used to indicate invalidation or revocation of an identity. Preferably, this may only be performed by the owner of the identity.

The challenge operation may determine when any identity it finds has been transferred. To do this, it may perform the following steps: find all transactions in the address graph paying to the root, excluding from consideration the bind operation transaction and transactions that do not pay to two unique addresses (one of which must be the root of the address graph). If no such transactions exist then the identity' has not been transferred and is deemed to have been authenticated.

Otherwise the transactions are ranked in order of increasing block height. Then the earliest confirmed transaction is taken. If there is more than one possibility (that is, there is more than one transaction with the earliest block height) then the transfer is potentially ambiguous. Any transfer cycle occurring within the same block height should also be flagged.

Provided that only a single transaction satisfies the above requirements, the address graph for the identity is redefined to be that which is rooted at the transfer destination address, commencing from the block height of the transaction. The challenge operation then restarts from the top, starting by forming the set S taking into account the new address graph and disregarding the old one.

Computer-implemented entities involved in carrying out a preferred embodiment of the invention are shown in Figure 7. A user wishing to create and use a verifiable user identity according to the present disclosure possesses a blockchain wallet 100. In the embodiment of Figure 7, the wallet is implemented in software on the user’s computing device. It will be appreciated that blockchain wallets may be implemented in various ways, for example as software, hardware or in printed form. This is discussed further below.

The blockchain wallet 100 is communicatively coupled to an external network such as the Internet. It is coupled via the external network which provides a link 102 to a server hosting a website 104. The website provides an interface via which the user is able to interact with the identity authentication system.

The website is communicatively coupled to an authentication server 106 over a link 108. Authentication server 106 is in turn communicatively coupled to a server 110 which is running software that configures it as a full node of the blockchain. This server is coupled to the authentication server over a link 112. The other nodes of the blockchain are running on other servers, which like server 110 are coupled to the external network, with the set of node servers together forming the blockchain peer-to-peer network 114. The blockchain wallet 100 is able to communicate with the blockchain network 114 via the external network over a link 116 and the full node server 110 is coupled to the blockchain network via the external network over a link 118.

Figure 8 shows a system configuration similar to that of Figure 7 which has been modified in accordance with an alternative embodiment of the invention. The website-based interface of Figure 7 has been replaced in the embodiment of Figure 8 by a mobile app-based interface. The user is able to interact with the authentication system via an app able to run on the user’s mobile computing device 120 such as a smartphone for example. The mobile computing device also runs the user’s blockchain wallet 100.

The user’s mobile computing device 120 is communicatively coupled to a resource server 122 via a link 124 over the external network. The resource server 122 is in turn communicatively coupled to the authentication server 106 via a link 126. The mobile app 121 forms the “front end” of the interface between the user and the authentication system with the resource server providing the corresponding “back end” interface with the authentication server 106.

The resource server may hold access controlled data which may be supplied to the mobile app front end upon successful authentication.

In a further alternative embodiment of the invention, the mobile app front end and the blockchain wallet functions may be combined into a single app, such that the front end is able to perform the steps involving the blockchain wallet automatically without the user’s involvement.

The bind, challenge and transfer algorithms may be executed on a server computer, consisting of a processor, disk and memory, and connected to the public Internet via a networking device. In addition, the computer may run (or have access to a computer 110 running) an up-to-date version of the full node software of a peer of the blockchain peer-to-peer network. The disk stores the blockchain data structure and the memory stores a pool of unconfirmed transactions as they occur on the network. The processor performs validation of blocks and transactions in order to maintain the integrity of its copy of the blockchain. All full nodes on the network store a shared, common history of the blockchain. A party requesting a user identity in accordance with the present disclosure may use the functions of a standard blockchain wallet 100 to create and send transactions that move values out of the wallet, and to receive and process transactions directed towards the wallet's addresses that move values into the wallet. Wallet software is available for desktop computers and mobile devices such as phones and tablets. Specialised hardware wallets may also be used which offer added security of the signing keys. The wallet will necessarily be connected to the public Internet in order to interface with the blockchain 114, either directly (as a full node) or indirectly via a third-party service. A party creating and verifying user identities according to the present disclosure may communicate with a user via some form of website 104. The website may run over SSL for greater security. The website may run on the same computer as the bind, challenge and transfer algorithms as well as the full node, as all three pieces of software work most efficiently when they can communicate with each other locally. The dashed line 130 around servers 104, 106 and 110 in Figures 7 to 10 denotes this possible implementation. Nevertheless it is possible for all three to run on different computers. The bind, challenge and transfer algorithms and full node may be operated by a service provider as a "software as a service" (SaaS). A service provider may carry out one or more of the following processes: a) generate a new address and unique amount X for the bind algorithm, and automatically send amount Y on behalf of the client when amount X is received at the address, returning the root address and minimum height of the new address graph to the client; b) generate a unique amount X' for the challenge algorithm and filter the new transaction stream for transactions paying amount X', attempting to link them back to a set of address graphs (root addresses with minimum heights) supplied by the client of the service; alternatively the address graphs may be stored by the service under the client's account and retrieved by the service for use by the challenge and transfer algorithms; and c) in the course of performing b) process all transfer transactions by means of the transfer algorithm. All of these functions require access to an up-to-date copy of the blockchain, and in order to possess this and to receive the new transaction stream the service may run a full node itself.

Figure 9 depicts a preferred sequence of interactions that occur using the various components and their interconnections as described above in relation to Figure 7 for the case of the bind operation. Figure 10 does the same for the challenge operation. The transfer algorithm runs as part of the challenge operation to handle the case when a transfer transaction is detected on the blockchain.

The interactions shown in Figure 9 consist of the following: 1. Website server 104 initiates the bind algorithm by sending a signal to the authentication server 106 to indicate that a new binding is required; 2. Website server 104 receives a bind address and amounts X, Y from the authentication server; 3. Website server 104 sends the bind address and the amounts X, Y to the user; 4. User broadcasts bind transaction on the P2P network 114 by sending the amount X to the bind address; 5. Full node 110 receives the stream of unconfirmed transactions from the network 114; 6. Authentication server 106 receives the user’s transaction; 7. Authentication server 106 sends a response transaction sending amount Y to the user’s address; 8. Full node 110 broadcasts the response transaction on the P2P network 114; and 9. The response transaction is received by the user, completing the operation.

The interactions shown in Figure 10 consist of the following: 1. Website server 104 initiates the challenge algorithm; 2. Authentication server 106 sends an amount X’ to the website server 104; 3. Website server 104 sends the amount X’ to the user; 4. The user broadcasts a challenge transaction on the P2P network 114 sending the amount X’ to themselves; 5. Full node 110 receives the stream of unconfirmed transactions from the P2P network 114 including the user’s challenge transaction; 6. Authentication server 106 receives the user’s transaction; 7. Authentication server 106 consults the blockchain data on full node 110 to link the user’s transaction to their address graph; 8. Authentication server 106 notifies the website server 104 of user’s identity; and 9. Website server 104 communicates to the user that they are authenticated.

Aspects of the present disclosure may be embodied as a computer method, computer system, or computer program product. Accordingly, aspects of the present disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, aspects of the present disclosure may take the form of a computer program product embodied in a computer-readable recording medium (or media) having computer readable program code/instructions embodied thereon.

Any combination of computer-readable media may be utilized. Computer-readable media can be a computer-readable signal medium and/or a computer-readable non-transitory storage medium. A computer-readable storage medium may include an electronic, magnetic, optical, electromagnetic, infrared, and/or semiconductor system, apparatus, or device, or any suitable combination of these. More specific examples of a computer-readable storage medium may include the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, flash memory such as a USB stick or SD card, and/or any suitable combination of these and/or the like. In the context of this disclosure, a computer-readable storage medium may include any suitable tangible medium that can contain or store a program for use by or in connection with an instruction execution system, apparatus, or device. A computer-readable signal medium may include a propagated data signal with computer-readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, and/or any suitable combination thereof. A computer-readable signal medium may include any computer-readable medium that is not a computer-readable storage medium and that is capable of communicating, propagating, or transporting a program for use by or in connection with an instruction execution system, apparatus, or device.

Program code embodied on a computer-readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fibre cable, RF, and/or the like, and/or any suitable combination of these.

In embodiments described above, several devices are shown as server computers. However, these devices may include, without limitation, one or more personal computers, mobile computing devices such as personal digital assistants (PDAs), tablets, and smart phones. Similarly, a user’s computing device may include, for example, one or more personal computers, network computers, and/or mobile computing devices such as personal digital assistants (PDAs), and smart phones. These devices may be interconnected through wired, wireless, optical, and other appropriate communication links.

Claims

1. A computer-implemented method of creating a verifiable electronic user identity, the method using an electronic data processor and an electronic data store and comprising the steps of: a) generating a new address on the data processor; b) sending the new address from the data processor to a user’s electronic device via an external network; c) determining with the data processor that there is a first transaction on a blockchain stored on a peer-to-peer network, or queued for inclusion in the blockchain, wherein the new address is an output of the first transaction and a user address is an input of the first transaction; d) detecting with the data processor the current height of the blockchain; and e) sending to the data store a user identity for the user comprising the user address that was an input of the first transaction and a height value dependent on the current height of the blockchain.

2. The method of claim 1, wherein the user identity sent to the data store includes the new address.

3. The method of claim 1 or 2 including the steps of determining a second transaction output value with the data processor, sending the second transaction output value from the data processor to the user’s electronic device via the external network, generating after step c) a second transaction with the data processor which sends the second transaction output value, wherein the user address is an output of the second transaction, and outputting the second transaction from the data processor for addition to the blockchain.

4. The method of claim 3, wherein the new address is an input of the second transaction.

5. The method of claim 3 or 4, including determining a first transaction output value with the data processor, and sending the first transaction output value from the data processor to the user’s electronic device via the external network, wherein it is determined in step c) that the first transaction sent the first transaction output value.

6. The method of any preceding claim including the steps of: - prior to step a), receiving with the data processor a request for a verifiable user identity from a requester’s electronic device via the external network; and - after step e), sending the user identity to the requester’s electronic device via the external network.

7. The computer-implemented method of verifying the identify of a user having a user identity created using a method of any preceding claim, the verification method using an electronic data processor and an electronic data store and comprising the steps of: i) generating a third transaction output value with the data processor; ii) sending the third transaction output value from the data processor to the user’s electronic device via the external network; iii) determining with the data processor that a third transaction is on the blockchain, or queued for inclusion in the blockchain, which sent the third transaction output value after the sending step ii) above; and iv) identifying with the data processor a chain of transactions, the chain being formed by transactions on the blockchain or queued for inclusion in the blockchain, which leads back from the third transaction to a user address of a user identity in the data store.

8. The method of claim 7, wherein at least one of the transactions of the chain of transactions occurs at a height in the blockchain which is greater than the height which corresponds to the height value of the user identity.

9. The method of claim 8, wherein each transaction of the chain of transactions occurs at a height in the blockchain which is greater than the height which corresponds to the height value of the user identity.

10. The method of any of claims 7 to 9, wherein the data processor determines in step iii) that the third transaction output was sent from a first user address to a second, different user address.

11. The method of any of claims 7 to 10 including a step of storing in the data store a record identifying the chain of transactions found in step iv).

12. The method of any of claims 7 to 11 including a step of storing in the data store a record identifying a set of addresses which form a chain of addresses in the chain of transactions found in step iv).

13. The method of any of claims 7 to 12 including the steps of: after identification step iv), identifying with the data processor a fourth transaction on the blockchain which comprises first and second outputs, of which the first output leads back to the user address of the stored user identity' and the second output leads to a further user address, wherein there is a chain of transactions formed by transactions on the blockchain which leads back from the fourth transaction to the user address of the stored user identity; and - replacing the stored user identity in the data store with a further stored user identity, wherein the further stored user identity comprises the further user address and a further height value dependent on the height in the blockchain of the fourth transaction.

14. The method of claim 13, wherein at least one of the transactions of the chain of transactions including the fourth transaction occurs at a height in the blockchain which is greater than the height which corresponds to the height value of the user identity.

15. The method of claim 14, wherein each transaction of the chain of transactions including the fourth transaction occurs at a height in the blockchain which is greater than the height which corresponds to the height value of the user identity.

16. The method of any of claims 13 to 15, including the step that: after the fourth transaction is identified but before replacing the stored user identity in the data store, the data processor determines that there is not a fifth transaction at the same height as the fourth transaction that also comprises first and second outputs, of which the first output leads back to the user address of the stored user identity and the second output leads to another user address, wherein there is a claim of transactions formed by transactions on the blockchain which leads back from the fifth transaction to the user address of the stored user identity.

17. The method of any of claims 13 to 16, including the steps of: after the fourth transaction is identified but before replacing the stored user identity in the data store, determining with the data processor that there is a sixth transaction on the blockchain which comprises first and second outputs, of which the first output leads back to the further user address of the further stored user identity and the second output leads to a further further user address, that there is a chain of transactions formed by transactions on the blockchain which leads back from the sixth transaction to the further user address of the further stored user identity, and that the further further user address does not match any of the previously seen further user addresses including the user address of the stored user identity; and replacing the further stored user identity in the data store with a further further stored user identity, wherein the further further stored user identity comprises the further further user address and a further further height value dependent on the height in the blockchain of the sixth transaction.

18. The method of claim 17, wherein the data processor determines that the further further user address does not match any of the previously seen further user addresses including the user address of the stored user identity and that the fourth transaction comprising the first output that leads back to the further user address or the user address of the stored user identity is at the same height as the sixth transaction.

19 The method of claim 17 or claim 18, wherein at least one of the transactions of the chain of transactions including the sixth transaction occurs at a height in the blockchain which is greater than the height which corresponds to the further height value of the further user identity.

20. The method of claim 19, wherein each transaction of the chain of transactions including the sixth transaction occurs at a height in the blockchain which is greater than the height which corresponds to the further height value of the further user identity.

21. The method of any of claims 13 to 20, including the step of: - identifying with the data processor a chain of transactions, the chain being formed by transactions on the blockchain or queued for inclusion in the blockchain, which leads back from the third transaction to the further user address of the further stored user identity in the data store.

22. The method of claim 21, wherein at least one of the transactions of the chain of transactions occurs at a height in the blockchain which is greater than the height which corresponds to the height value of the further stored user identity.

23. The method of claim 22, wherein each transaction of the chain of transactions occurs at a height in the blockchain which is greater than the height which corresponds to the height value of the further stored user identity.

24. The method of any of claims 7 to 23 including the steps of: - prior to step i), receiving with the data processor a request for verification of a user’s identity from a requester’s electronic device via the external network; and - after step iv), sending a response to the requester’s electronic device via the external network indicating that the identity of the user has been verified.

25. A computer-readable recording medium storing computer interpretable instructions for causing a data processor to perform the method of any preceding claim.

26. A computing device comprising an electronic data store including computer interpretable instructions that, when executed, direct the computing device to perform the method of any preceding claim, and an electronic data processor.

27. A computer-implemented method of creating a verifiable user identity' substantially as described herein with reference to the accompanying drawings.

28. A computer-implemented method of verifying a user identity substantially as described herein with reference to the accompanying drawings.

29. A computing device programmed to create a verifiable user identity substantially as described herein with reference to the accompanying drawings.

30. A computing device programmed to verify a user identity substantially as described herein with reference to the accompanying drawings.