JP7757437B2 - Security-enhanced Origination of Blockchain Transactions - Google Patents

Description

This patent application relates generally to network communications and encryption. More particularly, it relates to the communication of blockchain transactions to a blockchain network and the use of cryptographic techniques to obscure the origin of those communications. Obscuring the identity of an originator node associated with the introduction of a transaction in a blockchain network can enhance privacy and security.

In this document, the term "blockchain" is used to include all forms of electronic, computer-based, distributed ledgers. These include consensus-based blockchain and transaction chain technologies, permissioned and unpermissioned ledgers, shared ledgers, and variations thereof. The most widely known application of blockchain technology is the Bitcoin ledger, but other blockchain implementations have been proposed and developed. While Bitcoin may be referenced herein for convenience and illustrative purposes only, it should be noted that the subject matter of this application is not limited to use with the Bitcoin blockchain, and that alternative blockchain implementations and protocols are within the scope of this application. As used herein, the term "Bitcoin" includes all versions of Bitcoin and all variations derived from the Bitcoin protocol.

A blockchain is a peer-to-peer electronic ledger implemented as a computer-based decentralized system, composed of blocks, which are sequentially made up of transactions. Each transaction is a data structure that encodes the transfer of control of digital assets between addresses in the blockchain system and contains at least one input and at least one output. Each block contains the hash of the previous block that is chained together with it to create a permanent, immutable record of all transactions that have been written to the blockchain since its inception.

Blockchains can be used in a wide variety of applications. For example, blockchains can be employed to provide a ledger that reflects ownership of one or more commodities. For example, in the Bitcoin blockchain, the ledger reflects ownership of bitcoins and fractions thereof. Some such commodities may represent underlying units, such as units of computing resources. A blockchain-based ledger that reflects ownership allows commodities to be transferred pseudo-anonymously between parties, and transactions on the blockchain do not contain personally-identifying information about either party.

In particular, the outputs of a given transaction may be sent to an address that corresponds to a particular party's public key. These outputs can be unlocked by a private key that is the counterpart of the public key corresponding to that address, and then used as inputs for further transactions by the associated party.

The permanent or immutable nature of the blockchain means that the address included in a given transaction remains publicly available forever.

To introduce a transaction to the various nodes or computer systems participating in a decentralized system, the transaction must be distributed. This distribution can be done, for example, using a protocol whereby an overlay network is formed using connections between the various nodes participating in the decentralized system. And, a gossip protocol can be used whereby a node distributes a given transaction to its neighbors in the overlay network.

In any event, regardless of how a transaction ultimately propagates within the network, it must be introduced or injected into a decentralized system for distribution. This introduction necessarily requires network communication and may therefore have the side effect of revealing information about the transaction's origin at the network level, such as an Internet Protocol (IP) address. If such information can be correlated by another party to a specific address used on the blockchain, it can be used to construct a party's identity or to track all transactions associated with that party, even if multiple public addresses are used.

It is therefore desirable to provide a solution that allows transactions to be included on the blockchain while obscuring the network origin of the transaction.

Improved solutions like this are now being devised.

The present application provides methods and systems as defined in the accompanying claims.

The present application describes a computer-implemented method that may be implemented by a given proxy node, comprising the steps of receiving, via a computer network, a partially signed transaction generated by an origin node, the transaction including a first input, a first output, and a second output, the first input taking x+r units of computational resources, the first output providing x units toward an output address, and the second output providing d+r units toward one of n multi-signature addresses unlockable using any one of a plurality of second private keys, each second private key associated with a respective one of a plurality of proxy nodes, the plurality of proxy nodes including the given proxy node, and each second private key derivable by a respective one of the plurality of proxy nodes based on a private key of the proxy node's asymmetric encryption key pair and a secret value the proxy node shares with the origin node;
selecting t units, which is the quantity of computational resources to be allocated to the given proxy node for broadcasting the transaction and having it included in a blockchain, and selecting f units, which is the quantity of computational resources to be allocated to a third party for having the transaction included in the blockchain, where f<r and t<(r-f);
digitally signing an updated transaction generated by appending a second input taking d+f units to the transaction;
generating and digitally signing a further transaction using the second private key of the proxy node, the transaction including an input taking d+r units provided from one of the n multi-signature addresses, and an output providing t units to the given proxy node;
and broadcasting the updated transaction and the further transaction in time so that both are included in the same block of the blockchain.

In some implementations, receiving the transaction may include receiving an identifier for the transaction.

In some implementations, the broadcast of the updated transaction and the broadcast of the further transaction may occur substantially simultaneously.

In some implementations, the received identifier for the transaction may be encrypted using the public key of the given proxy node.

In some implementations, the f units, which are the amount of computational resources to be allocated to the third party for including the transaction in the blockchain, may be selected based on instructions received over the computer network. This indication may be received from an originating node.

In some implementations, the f units, which are the amount of computational resources to be allocated to the third party for including the transaction in the blockchain, may be selected based on ensuring that the transaction is included in the next block in the blockchain.

In some implementations, at least one of the f units, which is the amount of computational resources to be allocated to the third party for including the transaction in the blockchain, and the t units, which is the amount of computational resources to be allocated to the given proxy node for broadcasting the transaction, may be further selected based on ensuring that the further transaction is included in the next block in the blockchain.

In some implementations, the originating node has an associated asymmetric cryptographic key pair including a public key and a private key, and the secret value shared between the originating node and the given proxy node can be derived by the originating node based on the private key and the given proxy node's public key, and by the given proxy node based on the private key and the originating node's public key.

In some implementations, the asymmetric encryption key pair may be an elliptic curve key pair. This may mean that the secret value shared between the origin node and a particular proxy node corresponds to an Elliptic Curve Diffie-Hellman (ECDH) key exchange.

The present application further describes a computing device including a processor, memory, a network interface, and a non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by the processor, cause the computing device to perform the methods described above.

The present application further describes a non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by a processor of a computing device, cause the computing device to perform the methods described above.

The present application further describes a computer-implemented method performed by an origin node, the method comprising the steps of: determining a second public key for each of a plurality of proxy nodes based on a first public key associated with the proxy node and a secret value shared between the origin node and the proxy node, wherein a corresponding second private key for each of the proxy nodes can be determined by a given proxy node based on the secret value shared between the origin node and the given proxy node and the first public key associated with and associated with the given proxy node;
generating, by the origination node, a transaction including an input, a first output, and a second output, the input taking x+r units, the first output providing x units to an output address, and the second output providing (+r) units to one of n multi-signature addresses unlockable using any one of the second private keys;
The steps of digitally signing the transaction and distributing the signed transaction to the proxy node via a network are performed.

In some implementations, distributing the signed transaction may include transmitting an identifier of the transaction.

In some implementations, distributing the identifier of the signed transaction to the proxy nodes may include sending a respective instruction related to the identifier of the signed transaction to each of the proxy nodes.

In some implementations, the originating node has an associated asymmetric cryptographic key pair including a public key and a private key, and the secret value shared between the originating node and the given proxy node can be derived by the originating node based on the private key and the given proxy node's public key, and by the given proxy node based on the private key and the originating node's public key.

In some implementations, the asymmetric encryption key pair may be an elliptic curve key pair. Establishing a shared secret value between the origin node and a particular proxy node may correspond to an Elliptic Curve Diffie-Hellman (ECDH) key exchange.

The present application further describes a computing device including a processor, memory, a network interface, and a non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by the processor, cause the computing device to perform the methods described above.

The present application further describes a non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by a processor of a computing device, cause the computing device to perform the methods described above.

Any feature described in relation to one aspect or embodiment of the invention may also be used in relation to one or more other aspects/embodiments. These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter. Embodiments of the invention will now be described, by way of example only, and with reference to the accompanying drawings, in which:
Figure 1 shows an originating node communicating with a blockchain network. Figure 2 shows the origin node of Figure 1 communicating with the blockchain network of Figure 1 through a set of proxy nodes. FIG. 3 illustrates an exemplary computing device. FIG. 4 is a flowchart illustrating one exemplary method such as may be performed by the source node of FIG. FIG. 5 illustrates a blockchain transaction as it may be generated and signed by an originating node according to the exemplary method of FIG. FIG. 6 is a flowchart illustrating one exemplary method, such as may be performed by one or more proxy nodes of FIG. Figure 7 shows an updated version of the blockchain transaction from Figure 5. FIG. 8 illustrates a further blockchain transaction such as may be generated by a proxy node according to the example method of FIG. 6.

Similar reference numbers are used in the drawings to indicate similar elements and features.

In this application, the term "and/or" is intended to cover all possible combinations and sub-combinations of the listed elements, including any one of the listed elements alone, any sub-combination, or all of the elements, and does not necessarily exclude additional elements.

In this application, the phrase "at least one of... or..." is intended to cover any one or more of the listed elements, including only the listed elements, any subcombination, or any one of all of the elements, and does not necessarily exclude additional elements, and does not necessarily require all elements.

Overview Many blockchain-based systems are often considered anonymous. For example, various ledger systems, such as Bitcoin, are often considered anonymous because they allow parties to send and receive units of one or more commodities without disclosing personal or identifying information to the parties. Such systems, however, may be considered pseudo-anonymous rather than anonymous, because the identity of a party is protected only to the extent that the address used by the party in the blockchain is associated with the party's actual identity.

In one particular example, an IP address associated with a particular party may be used to compromise that party's anonymity. For example, a malicious adversary may attempt to link a public key to an IP address so that blockchain transactions involving that party can be traced. Additionally or alternatively, IP address information may be used in an effort to find the party's actual identity by using it as an index to search for information from other sources, such as from internet forums and social media. In such situations, attempted mitigations, such as generating multiple public and private key pairs for different sets of blockchain transactions or participating in a mixing service as a means to increase the anonymity of operations, may not be successful. See, for example, arXiv preprint arXiv:1701.0439 "Dandelion: Redesigning the Bitcoin Network for Anonymity" (2017) by S.B. Venkatakrishnan, G. Fanti, and P. Viswanath, the contents of which are incorporated herein by reference in their entirety.

As mentioned above, in some blockchain applications, transactions may be propagated through an overlay network. Nodes in one such overlay network that are involved in monitoring and diffusing blockchain transactions may be referred to as "supernodes." De-anonymization attacks may be carried out using such "supernodes." For example, in the specific example of the Bitcoin blockchain network, symmetric diffusion across the network allows for a 30% success rate in linking a specific IP to a specific public key using techniques that exploit the graph structure of the peer-to-peer (P2P) overlay network and certain information related to the diffusion of blockchain transactions on that network. See "Deanonymization of clients in Bitcoin P2P network," by A. Biryukov, D. Khovratovich, and I. Pustogarov, in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (pp. 15-29), November 2014. The contents of which are incorporated herein by reference in their entirety.

Beyond the realm of blockchain applications, attempts have been made to make it possible to obscure the IP addresses associated with specific communications. As one example, anonymous relay tools such as Tor offer one of the strongest identity protections currently available, but still exhibit weaknesses and possible drawbacks. A description of Tor can be found, for example, in "Tor: The second-generation onion router" (2004) by R. Dingledine, N. Mathewson, and P. Syverson, from the Naval Research Lab in Washington, DC. Relay systems such as Tor can be vulnerable to traffic analysis attacks. For example, a user's "first-hop" link to Tor and the "last-hop" link from Tor to the user's communication partner can be traced and used to correlate packets. Such attacks could potentially compromise a user's anonymity.

In light of the above, there exists a need to protect or obscure the identities of users in a blockchain network at the level of the underlying network, for example, at the level of the TCP/IP protocol.

Figure 1 shows an originator node 100 communicating with a blockchain network 110.

The source node 100 is a computing device.

Blockchain network 110 is an overlay network composed of communicating computing devices (not shown). For example, blockchain network 110 may be formed from computing devices that communicate in a peer-to-peer (P2P) manner.

In one example, the originating node 100 may be, for example, a Bitcoin node, and the blockchain network 110 may be, for example, the Bitcoin network. In a particular example, the originating node 100 may be, for example, a Bitcoin node that communicates with a supernode (not shown), which is one of the computer systems forming the blockchain network 110.

Because the originating node 100 communicates directly with the blockchain network 110, potentially network-identifying information, such as the originating node's 100 IP address, is exposed to the blockchain network 110. It may be desirable to avoid exposing all or part of such potentially network-identifying information.

In one solution, a separate computer system, acting as a proxy node, can be used to introduce transactions into the blockchain network 110 on behalf of the originating node 100, obscuring network-identifying information, such as the originating node's 100 IP address. Using a proxy node, however, poses a number of technical challenges.

For example, a proxy node could potentially go offline and become unavailable, including before it has begun or completed broadcasting a blockchain transaction.

In another example, a proxy node may become busy or overloaded. A busy or overloaded transaction node may be forced to discard blockchain transactions queued for processing because it introduces unacceptable latency and/or lacks the resources to maintain a large queue.

One or more of these challenges can be overcome by using a group of proxy nodes.

In this way, redundancy can be provided. Using more than one proxy node can make the system more resilient to failures compared to using a single node. In this way, resilience and security are enhanced. Additionally, using more than one proxy node can help to distribute the load. Furthermore, using more than one proxy node can help to further obscure the origin of blockchain transactions, as a single proxy node can be prevented from acting as an agent for the originating node on an ongoing basis.

Providing such an arrangement with multiple proxy nodes, however, can pose many technical challenges.

First, a blockchain transaction may correspond to a transfer of value between addresses. For example, a blockchain transaction may correspond to a transfer of units of computational resources from one or more source addresses to one or more destination addresses. One or more source addresses may be associated with a party corresponding to a source node 100. In a particular example, the blockchain transaction may be a Bitcoin transaction.

When a proxy is used to introduce a blockchain transaction into the network on behalf of an originating node, some amount of blockchain-based resources (e.g., tokens) may be provided to the proxy node in order to successfully communicate the transaction for inclusion in the blockchain. Selecting such an amount may result in undesirable messaging overhead, particularly when the originating node is communicating with one or more proxy nodes, for example, to determine which proxy node will accept the lowest amount. Thus, it is an issue to avoid or limit the messaging overhead associated with establishing the amount to be provided in connection with a particular blockchain transaction.

An issue with using multiple proxy nodes may also be that, in order to successfully communicate a transaction for inclusion in the blockchain, multiple blockchain transactions may need to be generated by the originating node, each transferring a different quantity to an address associated with a particular one of the proxy nodes, if different proxy nodes are requesting that each provide a different quantity to a particular proxy node. Furthermore, even if one of the proxy nodes requests the same quantity as another of the proxy nodes, multiple blockchain transactions may need to be generated, each providing that quantity to an address associated with a particular one of the proxy nodes.

In some blockchain-based systems, such as Bitcoin, once a transaction is broadcast, it still needs to be included in the blockchain by specific computer systems, known as miners, that are responsible for generating new blocks within the blockchain. Miners receive an amount in the form of newly minted Bitcoins to perform the computational work required to "mine" a block. Notably, this means that Bitcoin directly compensates for those computational resources.

Miners may be provided with a mining fee for the inclusion of a particular blockchain transaction in a mined block. This mining fee is reflected as the surplus of a given transaction's inputs over that blockchain transaction's outputs. The minimum fee required for a blockchain transaction to be included in the next block may change over time.

Another issue with providing blockchain transactions to multiple proxies for possible broadcast in a blockchain is that the mining fee required to have a particular blockchain transaction mined for inclusion in the next block may fluctuate during the period between the origin node's creation of the blockchain transaction and the transmission of the blockchain transaction by one or more proxy nodes to the blockchain network. Thus, for an origin node, configuring a blockchain transaction with an appropriate mining fee may require extensive back-and-forth communication or handshakes between the origin node and various proxy nodes. For example, an origin node 100 may configure a blockchain transaction including a particular mining fee and then submit the blockchain transaction to a proxy node for broadcast, but network conditions may then change before the proxy node broadcasts the blockchain transaction, thus resulting in an insufficient mining fee for possible inclusion in the next block. In such a situation, the proxy node may need to submit a new blockchain transaction, for example, with a higher mining fee, which may require further communication with the origin node. This may result in undesirable messaging overhead. Furthermore, the creation of multiple blockchain transactions may unnecessarily consume computational resources at one or more originating and proxy nodes.

In accordance with the present application, multiple proxy nodes may be used to address the drawbacks of using a single proxy node and the issues associated with using multiple proxy nodes. For example, issues including the potential computational and messaging overhead associated with establishing mining fees and the quantity provided to a proxy node for successfully communicating a transaction for inclusion in the blockchain may be addressed. For example, issues associated with establishing mining fees and the quantity provided to a proxy node for successfully communicating a transaction for inclusion in the blockchain may be addressed by allowing both to be selected by a given proxy node.

The high-level schematic diagram in Figure 2 shows an example configuration of how a group of proxy nodes can be used to introduce transactions into the blockchain network 110 on behalf of an originating node 100.

As shown, the originating node 100 communicates with the blockchain network 110 via element 220 and through a set of proxy nodes 230A-C.

Each of the proxy nodes 230A-230C is a computing device. The proxy nodes 230A-230C are in communication with the blockchain network 110. Although three proxy nodes are shown—proxy node 230A, proxy node 230B, and proxy node 230C—this is for illustrative purposes only, and the number of proxy nodes may vary.

Element 220 enables information to be communicated by originating node 100 to one or more of proxy nodes 230A-230C, and vice versa. Element 220 may represent one or more devices, such as a computer system at a well-known network address, that store information sent by one party for forwarding and/or retrieval by one or more other parties. Information stored by such element 220 may be ephemeral and/or may expire after some defined period of time. In another example, element 220 may support network connectivity by originating node 100 communicating with proxy nodes 230A-230C.

As described further below, the originating node 100 may communicate blockchain transactions to the proxy nodes 230A-C for communication to the blockchain network 110. In some embodiments, one or more of the proxy nodes 230A-230C may form part of the blockchain network 110. Additionally or alternatively, one or more of the proxy nodes 230A-230CC may communicate with one or more nodes of the blockchain network 110.

As described above, proxy nodes 230A-230C are configured to relay blockchain transactions to the blockchain network 110, such as on behalf of the originating node 100.

As described further below, the originating node 100 may communicate blockchain transactions to the proxy nodes 230A-C for communication to the blockchain network 110. In some embodiments, one or more of the proxy nodes 230A-230C may form part of the blockchain network 110. Additionally or alternatively, one or more of the proxy nodes 230A-230CC may communicate with one or more nodes of the blockchain network 110.

As described above, proxy nodes 230A-230C are configured to relay transactions to the blockchain network 110, such as on behalf of the originating node 100.

In particular, the originating node 100 can generate a partially signed blockchain transaction that includes a surplus input value that exceeds both the mining fee and the quantity provided to the proxy node for successful communication of the transaction for inclusion in the blockchain. As described further below, one or more of the proxy nodes 230A-230C can then provide additional inputs to the partially signed blockchain transaction to determine the mining fee for the blockchain transaction, and can generate additional blockchain transactions to collect quantities for distribution of the first blockchain transaction to the blockchain network 110.

Figure 3 is a high-level operational diagram of one exemplary computing device 300. In some embodiments, the exemplary computing device 300 may be one or more of the exemplary computer systems described herein, including, for example, the originating node 100 and/or the proxy nodes 230A-C. Each of the originating node 100 and the proxy nodes 230A-C includes software adapted to perform particular functions.

The exemplary computing device 300 includes various modules. For example, as shown, the exemplary computing device 300 may include a processor 310, memory 320, and a network interface 330. As shown, the aforementioned components of the exemplary computing device 300 communicate via a bus 340.

Processor 310 is a hardware processor. Processor 310 may be, for example, one or more of an ARM, Intel x86, or PowerPC processor, etc.

Memory 320 allows data to be stored and retrieved. Memory 320 may include, for example, random access memory, read-only memory, and persistent storage. Persistent storage may be, for example, flash memory, solid-state drives, etc. Read-only memory and persistent storage are non-transitory computer-readable storage media. Computer-readable media may be organized using a file system, such as may be managed by an operating system that governs the overall operation of exemplary computing device 300.

The network interface 330 enables the exemplary computing device 300 to communicate with other computing devices and/or various communication networks, such as, for example, the blockchain network 110 (Figures 1 and 2).

Software containing instructions may be executed by processor 310 from a computer-readable medium. For example, the software may be loaded into random access memory of memory 320 from persistent storage. Additionally or alternatively, the instructions may be executed by processor 310 directly from read-only memory of memory 320.

As described further below, software can adapt an instance of the exemplary computing device 300 to function as one or more of the various computer systems referred to herein, including, for example, the originating node 100 and the proxy nodes 230A-C.

As described above, origin node 100 (FIG. 2) can submit transactions to one or more proxy nodes 230A-230C for distribution to blockchain network 110. The operation of origin node 100 in submitting such blockchain transactions to proxy nodes is described with reference to flowchart 400 of FIG. 4. Operations 410 and beyond are performed by one or more processors of a computing device, such as processor 310 (FIG. 3) of a suitably configured instance of exemplary computing device 300, executing software including computer-executable instructions that may be stored in a computer-readable storage medium, such as the storage of memory 320.

As a pre-requisite to the method illustrated in flowchart 400, origin node 100 exchanges public keys with each of proxy nodes 230A-C. The keys may be exchanged, for example, via element 220 (FIG. 2).

For example, originating node 100 and proxy nodes 230A-C may each generate a public-private key pair and use the public key in the exchange. These associated asymmetric encryption key pairs may be in addition to any other encryption keys that may be associated with the nodes.

As a further prerequisite, the originating node 100 establishes a shared secret value with each of the proxy nodes 230A-230C.

As described further below, the shared secret may be established through the exchange of public keys. Alternatively, establishing the shared secret may involve additional communication and/or computation.

In operation 410, the originating node 100 determines a second public key for each of the proxy nodes 230A-C based on the first public key received in the prerequisite required public key exchange. The second public key is determined based on the first public key and a shared secret, and a corresponding second private key for each proxy node is generated in such a manner that it can be determined by the given proxy node based on the value of the secret shared between the originating node and the given proxy node and the private key corresponding to the first public key. A method for determining the second public key based on the first public key and a potentially used shared secret is described below.

Following the determination of the second public key for each of the proxy nodes 230A-230C, control flow proceeds to operation 420.

In operation 420, the originating node 100 generates a blockchain transaction that includes one input and two outputs. An example of such a blockchain transaction is shown in FIG. 5. As shown, the exemplary blockchain transaction, blockchain transaction 500, includes an input 510, a first output 520, and a second output 530.

Blockchain transaction 500 is intended to transfer x units of a blockchain-based resource to another party via a blockchain-implemented ledger. For ease of illustration, the source and destination addresses are not shown. The units may correspond, for example, to units of a computational resource. The units may be units of a particular resource, such as units expressed in Bitcoin.

It may be that the originating node 100 is willing to provide an additional r unit in order to view the blockchain transaction 500 included in the blockchain.

As shown, both quantities (x + r) units are provided as inputs to the blockchain transaction via input 510. Alternatively, these quantities may be provided via more than one input, for example, if a user wishes to source all or part of x units and r units from different addresses.

The first output 520 provides x units for the output address. The output address may be associated with another party.

The second output 530 provides d+r units to a special address, whereby the quantity provided to that address can be unlocked by any one of the second private keys associated with the proxy nodes 230A-230C. Such a 1-of-n multi-signature address may be generated by the origin node 100 based on the second public key, as determined based on each proxy node's public key and a secret value the proxy node shares with the origin node 100. Details of such multi-signature addresses, particularly in the context of Bitcoin, can be found in "Mastering Bitcoin: Unlocking Digital Cryptocurrencies" (2014) by A.M. Antonopous (O'Reilly Media) (hereinafter "Mastering Bitcoin"), the contents of which are incorporated herein by reference in their entirety. Multi-signature addresses are described in Chapter 5 of "Mastering Bitcoin."

Additional outputs (not shown) may also be included in the blockchain transaction 500, such as additional outputs to recover any remainder resulting from there being more than (x + r) units derived from the source of the input 510.

Notably, the quantity d units included in the second output 530 is an arbitrary quantity, resulting in an imbalance (deficit) of d units in the blockchain transaction 500 between the input 510 compared to the sum of the first output 520 and the second output 530. As explained further below, this allows the originating node 100 to sign the blockchain transaction 500 while ensuring that the blockchain transaction 500 will not be accepted for inclusion in the blockchain without adding one or more additional inputs to ensure that the sum of the inputs for the blockchain transaction exceeds the sum of the outputs.

Returning to Figure 4, following operation 420, control flow proceeds to operation 430.

In operation 430, the originating node 100 digitally signs the blockchain transaction 500. As described above, the blockchain transaction 500 is incomplete because the sum of its outputs exceeds the sum of its inputs. The originating node 100 signs the blockchain transaction in such a way that no further outputs can be added to the blockchain transaction 500, but all outputs—i.e., including the first output 520 and the second output 530—and the input 510 can be signed so that further inputs can be added. For example, if the blockchain transaction 500 is a Bitcoin transaction, the originating node 100 may sign the blockchain transaction 500 using the flags SIGHASH_ALL|SIGHASH_ANYONECANPAY.

Following operation 430, control flow proceeds to operation 440.

In operation 440, the originating node 100 distributes the signed blockchain transaction 500 to the proxy nodes 230A-C. In some embodiments, the originating node 100 may communicate the blockchain transaction 500 via element 220. Notably, because the blockchain transaction 500 is signed, the transaction identifier (txid) associated with the blockchain transaction is unique. Thus, the originating node may communicate the txid to the proxy nodes 230A-C, for example, via element 220. In another example, the originating node may communicate respective instructions related to the txid to each of the proxy nodes 230A-230C. Additionally or alternatively, the blockchain transaction 500 may be communicated in some other manner, such as by serializing it into a format for transmission to the proxy nodes 230A-230C. The blockchain transaction 500 and/or the txid may be transmitted in encrypted form. For example, one or both may be encrypted and distributed to each proxy node 230A-230C using that proxy node's public key. In a particular example, the received identifier for the blockchain transaction 500 may be encrypted using the public key of a given proxy node.

As described above, proxy nodes 230A-C receive blockchain transactions 500 from origin node 100 for distribution to blockchain network 110. One exemplary operation of proxy nodes 230A-230C for distribution of blockchain transactions to blockchain network 110 is described with reference to flowchart 600 of FIG. 6. Operations 610 and thereafter are performed by one or more processors of a computing device, such as processor 310 (FIG. 3) of a suitably configured instance of exemplary computing device 300, executing software including computer-executable instructions that may be stored in a computer-readable storage medium, such as the storage of memory 320.

The method illustrated in flowchart 600 has similar prerequisites to the method illustrated in flowchart 400 (FIG. 4): that the proxy node has exchanged public keys with origin node 100 (FIG. 2), which may occur, for example, via element 220 (FIG. 2), and that the exemplary proxy node has established a shared secret value with origin node 100. Thus, origin node 100 and proxy node each have an associated asymmetric key pair consisting of the node's exchanged public key and its associated private key.

In operation 610, the proxy node receives the blockchain transaction 500 (Figure 5) from the origin node. As described above, the blockchain transaction 500 is partially signed by the origin node 100 and includes a first input taking x+r units, a first output providing x units to an output address, and a second output providing d+r units to one of n multi-signature addresses unlockable using any one of the sets of second private keys associated with the proxy nodes 230A-230C. The proxy node can derive its second private key based on a private key corresponding to the public key exchanged with the origin node 100 as a prerequisite and a secret value the proxy node shares with the origin node.

The blockchain transaction 500 may be received by receiving an identifier associated with the blockchain transaction 500. The identifier may be, for example, the transaction identifier (txid) of the blockchain transaction 500. Additionally or alternatively, the blockchain transaction 500 may be received in some other format, such as a serialized format, and may need to be deserialized, for example. Additionally or alternatively, the blockchain transaction 500 may be received in an encrypted format. For example, the originating node 100 may perform the encryption using a public key associated with the proxy node. In a particular example, the encryption may use a public key that the proxy node exchanged with the originating node 100 as a prerequisite, or in another example, a second public key corresponding to the proxy node's second private key. The proxy node may decrypt the blockchain transaction 500 or its identifier using a private key corresponding to the public key associated with the proxy node.

Following operation 610, flow control proceeds to operation 620.

In operation 620, the proxy node selects a number of quantities to be used in updating the blockchain transaction 500 and, if the blockchain transaction 500 is successfully included in the blockchain, in constructing a further transaction to provide the quantity to the proxy node.

In particular, the proxy node broadcasts the blockchain transaction 500 and selects an amount, t units, to be allocated to the proxy node for including the blockchain transaction 500 in the blockchain.

In addition, the proxy node selects an amount, f, to be allocated to a third-party for including the blockchain transaction 500 in the blockchain. The amount, f, may be expressed in units of computational resources and, therefore, may be an amount of f units of computational resources. For example, in the case of the Bitcoin blockchain, f units may correspond to a mining fee to be paid to a miner for including the blockchain transaction 500 in the blockchain.

The amount f may be selected based on an instruction received over a computer network. For example, if the amount f corresponds to computational resources, the amount f of computational resources to be allocated to a third party for including the transaction in the blockchain may be selected based on an instruction received over a computer network. Such an indication may be received from an originating node. Additionally or alternatively, the amount f may be selected based on ensuring that the blockchain transaction is included in the next block in the blockchain. For example, a web service may be consulted to determine an amount that, when selected as the amount f, ensures with a desired probability or likelihood that the blockchain transaction 500 will be included in the next block in the blockchain.

Notably, the quantity f must be less than r—that is, f<r. Otherwise, the proxy node will not net-receive the quantity for including the blockchain transaction 500 in the blockchain, or may even contribute its own resources (units) toward including the blockchain transaction 500 in the blockchain.

The type of output to which x units are sent by first output 520 may affect the mining fee required to include the updated blockchain transaction 700 (described further below) in the blockchain. Thus, one or both of the first and second outputs may have a known form to assist the proxy node in selecting the amount f.

As explained further below, the proxy node generates further transactions to provide t units, depending on the blockchain transaction 500 (and further blockchain transactions) included in the blockchain. This is because a quantity—e.g., a mining fee for a miner in the case of Bitcoin—may also need to be provided to include the further transaction in the blockchain. The quantity t may also be selected to allow this quantity to be paid from the r units provided by the first input of the blockchain transaction 500. In other words, t < (r - f).

Following the selection of the quantity in operation 620, control flow proceeds to operation 630.

In operation 630, an updated form of blockchain transaction 500 is generated. In particular, as described above, blockchain transaction 500 is unsuitable for inclusion in the blockchain because the sum of its outputs exceeds its inputs. Thus, in operation 630, updated blockchain transaction 700, shown in FIG. 7, is generated based on blockchain transaction 500 (FIG. 5). In particular, updated blockchain transaction 700 is generated by adding a second input 710, taking d+f units, to blockchain transaction 500. Notably, the d units function to balance the d units in second output 530. The f units, as described above, provide for inclusion of updated blockchain transaction 700 in the blockchain—e.g., mining fees in the case of Bitcoin.

The proxy node also signs the updated blockchain transaction 700 to sign the second input 710. For example, if the updated blockchain transaction 700 is a Bitcoin transaction, the proxy node may sign the updated blockchain transaction 700 with the flags SIGHASH_ALL|SIGHASH_ANYONECANPAY. This additional cryptographic signature has the side effect of causing the updated blockchain transaction 700 to have a different transaction ID (txid) than the blockchain transaction 500.

As a result of having an input that sums at least all of the outputs, and given that all of these inputs and outputs are signed, the updated blockchain transaction 700 is in a suitable form for inclusion in the blockchain.

Returning to FIG. 6, following operation 630, control flow proceeds to operation 640.

In operation 640, a further blockchain transaction 800 is generated and digitally signed, as described above. In particular, the proxy node generates and digitally signs the further blockchain transaction 800, as shown in FIG. 8. The further blockchain transaction 800 includes an input 810 that takes d+r units provided from one of the n multi-signature addresses of the second output 530 of the blockchain transaction 700 (FIG. 7) and is unlocked using the proxy node's second private key, which is derived based on the proxy node's public key exchanged with the origin node 100 in the precondition and the private key corresponding to the secret value the proxy node shares with the origin node 100. The further blockchain transaction 800 also includes an output 820 providing t units for an address, such as may be selected by the proxy node. In effect, the t units are a quantity for the proxy node only if the updated blockchain transaction 700 (and the further blockchain transaction 800) are included in the blockchain. Notably, the difference between t and d+r—i.e., t−d−r—may be the quantity for including the blockchain transaction 800 in the blockchain (e.g., the mining fee for miners when the blockchain network 110 is the Bitcoin network). Thus, one or both of the quantity f and the quantity t may be selected such that the quantity t−d−r allows for the further blockchain transaction 800 to be included in the next block in the blockchain.

Returning to FIG. 6, following operation 640, control flow proceeds to operation 650.

In operation 650, both blockchain transaction 700 and blockchain transaction 800 are broadcast to the blockchain network 110 by the proxy node. The broadcast of the updated blockchain transaction 700 and the further blockchain transaction 800 may be timed so that they can be included in the same block of the blockchain. For example, the updated blockchain transaction 700 and the further blockchain transaction 800 may be broadcast simultaneously/close to succession. Advantageously, the quantities f and t-d-r are such that the updated blockchain transaction 700 and the further blockchain transaction 800 will be included in the next block in the blockchain, and if their broadcasts are so timed, then both transactions may be included in the same, next block of the blockchain.

As described above, origin node 100 may send blockchain transaction 500 to each of proxy nodes 230A-230C. Accordingly, each proxy node 230A-230C may generate its own version of updated blockchain transaction 700 and blockchain transaction 800. Notably, each instance of updated blockchain transaction 700 has a different txid due to the different format of second input 710. More notably, however, each of these versions of updated blockchain transaction 700 has a first input, input 510, identical to input 510 of blockchain transaction 500, and thus derives unspent transaction outputs from the same source as input 510. Accordingly, each of these versions of updated blockchain transaction 700 appears to blockchain network 110 as a double-spending attack (i.e., the transfer of the same fraction of a particular token to different parties) against the other versions of updated blockchain transaction 700. However, most blockchain-based ledgers, such as Bitcoin, advantageously prevent double-spending, so that only one instance of an updated blockchain transaction 700 is included in the blockchain.

Different instances of the blockchain network 110 may resolve double spends in different ways, favoring a particular version of the updated blockchain transaction 700 among various versions. For example, a node (e.g., a miner) constructing a blockchain block may choose the first block it sees. In the case of Bitcoin, multiple versions of the updated blockchain transaction 700 may be temporarily stored in memory (a so-called "mempool") at the mining node, and the miner will select the updated blockchain transaction 700 that has the highest mining fee for the miner to include in the next block. Notably, due to the relationship between the quantities r, f, and t, this also has the side effect of selecting the version of the updated blockchain transaction 700 that originates from the proxy node that selects the lowest value of t. More information about mempools is provided in Chapter 8 of "Mastering Bitcoin" (see above for citations).

Notably, once the updated blockchain transaction 700 is included in the blockchain, the transaction ID of the updated blockchain transaction 700 becomes publicly available. This means that any one of the proxy nodes 230A-230C (even if it is not the proxy node that sent the version of the updated blockchain transaction 700 included in the blockchain) may consume the transaction output. However, this concern can be mitigated by generating an additional blockchain transaction 800 before distributing the updated blockchain transaction 700, by broadcasting both the updated blockchain transaction 700 and the additional blockchain transaction 800 simultaneously, and, if necessary, by providing a quantity (e.g., a mining fee) to ensure that both the updated blockchain transaction 700 and the additional blockchain transaction 800 are included in the same (next) block.

Although the above description includes only a single source node—source node 100—it may be the case that multiple source nodes communicate with each of proxy nodes 230A-230C. Advantageously, proxy nodes 230A-230C may be able to exchange the public key of the same key pair with each of such multiple source nodes.

Setting Prerequisites As mentioned above, both the methods illustrated in flowchart 400 (FIG. 4) and flowchart 600 (FIG. 6) require that the originating node 100 has exchanged public keys with each of the proxy nodes 230A-C, and that the originating node 100 shares a respective secret value with each one of the proxy nodes 230A-C.

The originating node 100 and each of the proxy nodes 230A-230C can generate a random elliptic curve public-private key pair. The public keys of the elliptic curve key pair can be exchanged.

In particular, the source node 100 can choose a random private key _xA and publish a corresponding public key P _A =x _A ×G.

Similarly, each proxy node 230A-230C may select a random private key y _B,i and may publish a corresponding public key Q _B,i =y _B,i ×G.

Using this information, the origin node 100 can determine a secret value, c _i , to be shared with each of the proxy nodes 230A-C. c _i = H(x _A × Q _B,i ), where H is a cryptographic hash function, e.g., a member of the SHA-2 family. Similarly, each of the proxy nodes 230A-230C can similarly determine a secret value to share with the origin node 100 as c _i = H(P _A × y _B,i ) = H(x _A × Q _B,i ). Equality is due to the homomorphic property of elliptic curves. Notably, the above steps for establishing a shared secret value between the origin node and a particular proxy node correspond to an Elliptic Curve Diffie-Hellman (ECDH) key exchange.

The origin node 100 may also determine a further public key for each of the proxy nodes 230A-230C based on the secret value shared with the given proxy node and its published public key. In particular, such further public key (corresponding to the second public key described above) may be calculated as Q' _B,i = Q _B,i + c _i × G. Conveniently, the second public key is generated by the origin node 100, but the corresponding private key S _B,i (corresponding to the "second private key" described above) can only be determined by the corresponding proxy node. In particular, a proxy node can determine the second private key based on its private key y _B,i and the secret value that the proxy node shares with the origin node 100, where S _B,i = (y _B,i + c _i ).

Alternatives for establishing preconditions may also be used. For example, a classic Diffie-Hellman key exchange (based on the discrete logarithm problem) could be performed by the originating node 100 with each of the proxy nodes 230A-230C to establish a respective shared value with each proxy node. Public keys may also be exchanged in some other manner. For example, public keys may be exchanged directly, or alternatively, may be exchanged over a secure channel, such as over a secure channel, as may be established in addition to the classic Diffie-Hellman key exchange described above.

It should be noted that the above-described embodiments are illustrative rather than limiting of the subject matter of the present application, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the present invention as defined by the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The words "comprising" and "comprises", etc., do not exclude the presence of elements or steps other than those listed in any claim or the specification as a whole. As used herein, "comprises" means "includes or consists of" and "comprising" means "including or consisting of." The singular reference of an element does not exclude the plural reference of such element, and vice versa. The subject matter of the present application can be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In a device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

100 Originating node 110 Blockchain network 220 Elements 230A, 230B, 230C Proxy node 300 Computing device 310 Processor 320 Memory 330 Network interface 500 Blockchain transaction 510 Input 520 First output 530 Second output 700 Blockchain transaction 710 Second input 800 Blockchain transaction 810 Input 820 Output

Claims (20)

1. A computer-implemented method, comprising:
receiving, via a computer network, a transaction generated and partially signed by at least one originating node;
the transaction includes at least one first input, a first output, and a second output;
the at least one first input provides (x+r) units of computational resource;
the first output provides x units to an output address, and the second output provides (d+r) units to one of n multi-signature addresses unlockable using any one of a plurality of second private keys;
each of the second private keys is associated with a respective one of a plurality of proxy nodes;
the plurality of proxy nodes includes the given proxy node; and
each said second private key may be derived by a respective one of said plurality of proxy nodes based on a private key of an asymmetric encryption key pair of said proxy node and a secret value that said proxy node shares with said origin node ;
Further inputs may be added to the partially signed transaction, but further outputs may not be added to the partially signed transaction;
Steps and
selecting t units, which is the amount of computational resources to be allocated to the given proxy node for broadcasting the transaction and having it included in a blockchain; and selecting f units, which is the amount of computational resources to be allocated to a third party for having the transaction included in the blockchain ;
digitally signing an updated transaction generated by appending a second input to the transaction, the second input taking ( d+f) units;
generating and digitally signing a further transaction using the second private key of the proxy node, the transaction including an input taking (d+r) units provided from one of the n multi-signature addresses, and an output providing t units to the given proxy node;
broadcasting the updated transaction and the further transaction in time so that both are included in the same block of the blockchain;
A method comprising: receiving the transaction includes receiving an identifier of the transaction;
The method of claim 1. the broadcast of the updated transaction and the broadcast of the further transaction occur substantially simultaneously;
The method according to claim 1 or 2. the received identifier of the transaction is encrypted using the public key of the given proxy node;
4. The method according to any one of claims 1 to 3. the f units, which are the amount of computational resources to be allocated to the third party for including the transaction in the blockchain, are selected based on instructions received via the computer network;
5. The method according to any one of claims 1 to 4. the indication is received from the source node;
The method of claim 5. the f units, which are the amount of computational resources to be allocated to the third party for including the transaction in the blockchain, are selected based on having the transaction included in a next block in the blockchain;
7. The method according to any one of claims 1 to 6. At least one of the f units, which is the amount of computational resources to be allocated to the third party for including the transaction in the blockchain, and the t units, which is the amount of computational resources to be allocated to the given proxy node for broadcasting the transaction, is further selected based on including the further transaction in a next block in the blockchain.
8. The method according to any one of claims 1 to 7. the originating node has an associated asymmetric cryptographic key pair including a public key and a private key; and
the secret value shared between the origin node and the given proxy node can be derived by the origin node based on a private key and the public key of the given proxy node, and by the given proxy node based on a private key and the public key of the origin node;
9. The method according to any one of claims 1 to 8. the asymmetric encryption key pair is an elliptic curve key pair; and
Establishing a shared secret value between the originating node and a particular proxy node corresponds to an Elliptic Curve Diffie-Hellman (ECDH) key exchange.
10. The method according to any one of claims 1 to 9. 1. A computing device comprising:
a processor;
Memory and
A network interface,
a non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by the processor, cause the computing device to perform the method of any one of claims 1 to 10; and
a computing device, A non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by a processor of a computing device, cause the computing device to perform the method of any one of claims 1 to 10. 1. A computer-implemented method comprising:
determining a second public key for each of a plurality of proxy nodes based on a first public key associated with the proxy node and a secret value shared between the origin node and the proxy node;
a corresponding second private key for each of the proxy nodes may be determined by a given proxy node based on a secret value shared between the origin node and the given proxy node and the first public key associated with the given proxy node;
Steps and
generating, by the source node, a transaction including at least one first input, a first output, and a second output;
the at least one first input provides (x+r) units;
the first output provides x units toward an output address, and the second output provides (d+r) units toward one of n multi-signature addresses that can be unlocked using any one of the second private keys.
Steps and
digitally signing the transaction ;
Additional inputs can be added to a signed transaction, but additional outputs cannot be added to the signed transaction.
Steps and
distributing the signed transaction to the proxy nodes over a network;
How to perform. Distributing the signed transaction comprises:
transmitting an identifier of the transaction;
The method of claim 13. Distributing the identifier of the signed transaction to the proxy nodes includes:
sending a respective instruction to each of the proxy nodes relating to the identifier of the signed transaction;
15. The method of claim 14. each instruction sent to a given one of the proxy nodes is encrypted using the public key of the proxy node;
16. The method of claim 15. the originating node has an associated asymmetric cryptographic key pair including a public key and a private key; and
the secret value shared between the origin node and the given proxy node can be derived by the origin node based on a private key and the public key of the given proxy node, and by the given proxy node based on a private key and the public key of the origin node;
17. The method of any one of claims 13 to 16. the asymmetric encryption key pair is an elliptic curve key pair; and
Establishing a shared secret value between the originating node and a particular proxy node corresponds to an Elliptic Curve Diffie-Hellman (ECDH) key exchange.
18. The method of claim 17. 1. A computing device comprising:
a processor;
Memory and
A network interface,
a non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by the processor, cause the computing device to perform the method of any one of claims 13 to 18; and
a computing device, A non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by a processor of a computing device, cause the computing device to perform the method of any one of claims 13 to 18.