SYSTEM AND METHOD FOR PROVIDING SHARED HASH ENGINES ARCHITECTURE FOR A BITCOIN BLOCK CHAIN

Abstract

A method and system for sharing hash calculations across N parallel mining threads, the method comprising: finding N Merkle root hash values that have identical marginal portions of a predetermined size, calculating a corresponding mid-state hash for each of the N Merkle root hash values, and transmitting the N Merkle root hash values along with the corresponding mid-state values to the N parallel mining threads.

Claims

1. A method for sharing hash calculations across N parallel mining threads, the method comprising: finding N Merkle root hash values that have identical marginal portions of a predetermined size; calculating a corresponding mid-state hash for each of the N Merkle root hash values; and transmitting the N Merkle root hash values along with the corresponding mid-state values to the N parallel mining threads.

2. The method according to claim 1, further comprising producing by a CPU Merkle packets that include Merkle tree branches and provides them to a Merkle generator.

3. The method according to claim 1, further comprising receiving by a Merkle generator a Merkle packet from a CPU, performing a Merkle root hash algorithm and looking for winner Merkle root hashes that have identical marginal portions.

4. The method according to claim 3, further comprising: receiving a Merkle packet from a CPU and storing it in a Merkle memory; reading the Merkle memory and feeding a hash engine with Merkle branch data, each time with a new extra nonce; performing Merkle hash calculations and checking, for a certain extra nonce value, if the Merkle hash value is a winner Merkle hash value; and sending winner Merkle hash values to a Merkle generator manager, which is further configured to send them to the CPU.

5. The method according to claim 3, further comprising: transmitting winner Merkle hash values to the CPU; adding the winner Merkle hash values to a collision table to collect batches of N Merkle Winners; and when a batch of N Merkle Winners is formed, forwarding the batch to the N parallel mining threads.

6. The method according to claim 1, further comprising: receive job packets from the CPU and to forward the job packets to an engine controller of a multithreading engine; producing signatures by iterations over a defined range of nonces; and for a produced signature, checking if the signature is valid.

7. The method according to claim 6, wherein the producing of signatures further comprises: producing N first-stage hashes respective to received N different mid-states; and producing a signature by a second-stage hash for at least one of the N first-stage hashes.

8. A system for sharing hash calculations across N parallel mining threads, the system comprising: a central processing unit (CPU), the CPU comprises a Merkle generator to find N Merkle root hash values that have identical marginal portions of a predetermined size and calculate a corresponding mid-state hash for each of the N Merkle root hash values; and an N-thread parallel engine to process the N Merkle root hash values in parallel.

9. The system according to claim 9, wherein the CPU produces Merkle packets that include Merkle tree branches and provides them to the Merkle generator.

10. The system according to claim 9, wherein the Merkle generator receives a Merkle packet from the CPU, performs a Merkle root hash algorithm and looks for winner Merkle root hashes that have identical marginal portions.

11. The system according to claim 9, wherein the Merkle generator comprises: a Merkle generator manager configured to initiate a Merkle scan process; a Merkle memory, wherein the Merkle generator is configured to receive a Merkle packet from the CPU and store it in the Merkle memory; a block feeder; and a hash engine, wherein the block feeder is configured to read the Merkle memory and feed the hash engine with Merkle branch data, each time with a new extra nonce, and wherein the hash engine is configured to perform Merkle hash calculations and check, for a certain extra nonce value, if the Merkle hash value is a winner Merkle hash value, and to send winner Merkle hash values to the Merkle generator manager, which is further configured to send them to the CPU.

12. The system according to claim 9, wherein the N-thread parallel engine comprises: an engines manager; and at least one multithreading engine, comprising: an engine controller; and an engine core, wherein the engines manager is configured to receive job packets from the CPU and to forward the job packets to the engine controller, and wherein the engine core is configured to receive the respective N different mid-states along with the shared marginal portion and to produce signatures by iterations over a defined range of nonces.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0027] For a better understanding of embodiments of the invention and to show how the same may be carried into effect, reference will now be made, purely by way of example, to the accompanying drawings in which like numerals designate corresponding elements or sections throughout.

[0028] In the accompanying drawings:

[0029] FIG. 1 is a schematic illustration of a block header structure and the signature process in accordance with the prior art;

[0030] FIG. 2 is a schematic flowchart illustration of a method for sharing hash calculations across N parallel mining engines, according to some embodiments of the present invention;

[0031] FIG. 3 is a schematic illustration of a system for sharing hash calculations across N parallel mining engines, according to some embodiments of the present invention;

[0032] FIG. 4 is an exemplary schematic illustration of a Merkle packet that is provided by the CPU to the Merkle generator according to some embodiments of the present invention;

[0033] FIG. 5 is a schematic illustration of a Merkle generator according to some embodiments of the present invention;

[0034] FIG. 6 is a schematic illustration of a method for handling winner Merkle hash values according to some embodiments of the present invention;

[0035] FIG. 7 is a schematic illustration of an exemplary mining engines system according to some embodiments of the present invention; and

[0036] FIG. 8 is a schematic flowchart illustration of a mining process according to some embodiments of the present invention.

[0037] The drawings together with the following detailed description make apparent to those skilled in the art how the invention may be embodied in practice.

DETAILED DESCRIPTION OF THE INVENTION

[0038] With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of the preferred embodiments of the present invention only, and are presented in the cause of providing what is believed to be the most useful and readily understood description of the principles and conceptual aspects of the invention. In this regard, no attempt is made to show structural details of the invention in more detail than is necessary for a fundamental understanding of the invention, the description taken with the drawings making apparent to those skilled in the art how the several forms of the invention may be embodied in practice.

[0039] Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not limited in its application to the details of construction and the arrangement of the components set forth in the following description or illustrated in the drawings. The invention is applicable to other embodiments or of being practiced or carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting.

[0040] Embodiments of the present invention provide a system and method for parallel processing of shared data across hash engines, thus providing a more efficient mining process that consumes less processing power and/or enables faster mining with the same processing power.

[0041] Reference is now made to FIG. 2, which is a schematic flowchart illustration of a method for sharing hash calculations across N parallel mining engines, according to some embodiments of the present invention. As discussed above, the block header is divided to two chunks, and a hash Merkle root is divided between the two chunks. The first chunk includes a main portion of the hash Merkle root and the second chunk includes a marginal portion of the hash Merkle root of a predetermined size, for example the last 32 bits of the hash Merkle root.

[0042] The method may include, as indicated in block 110, finding N Merkle root hash values that have identical marginal portions of a predetermined size. Since the identical marginal portions are included in the second header chunk, while the main, varying, portion of the

[0043] Merkle root hash values are included in the first header chunk, a different mid-state hash may be calculated by the host computer for each of the N Merkle root hash values, as indicated in block 120. Then, as indicated in block 130, the N Merkle root hash values may be transmitted along with the corresponding mid-state values to the N engines (or to an engine that can support the N mining threads in parallel). Alternatively, in some embodiments, the engines may receive along with the corresponding mid-state values only the corresponding marginal portion of the Merkle root hash values instead of receiving the entire hash Merkle root values.

[0044] In the hashing process by the engine, the data being processed is the second chunk of the block header, which may be shared by the parallel engines/threads, for example by shared data pipe, e.g. shared expander logic. Since the marginal portion of the Merkle root hash values is shared between the parallel engines/threads, each of the parallel engines, or each of the parallel mining threads, has a reduced amount of data to process and thus, for example, requires less processing power. For example, when shared between N engines, the required expander logic is reduced by (N−1)/N.

[0045] Reference is now made to FIG. 3, which is a schematic illustration of a system 200 for sharing hash calculations across N parallel mining engines, according to some embodiments of the present invention. The system may include a central processing unit (CPU) 10 that includes a Merkle generator 12, which may be software or hardware, such as a Merkle root hash application-specific integrated circuit (ASIC). The system further includes N parallel mining engines 14 (or an N-thread parallel engine 14).

[0046] CPU 10 produces Merkle packets that include Merkle tree branches and provides them to Merkle generator 12. FIG. 4 is an exemplary schematic illustration of a Merkle packet 30 that is provided by the CPU to the Merkle generator according to some embodiments of the present invention. Merkle packet 30 may include Merkle branch hash values 32, chunks of the coinbase transaction 34, extra nonce 36 that is used by the Merkle generator to scan for collisions, and some additional required data 38 such as, for example, offsets and pointers used for orientation within the packet.

[0047] Merkle generator 12 may receive a Merkle packet from CPU 10, perform a Merkle root hash algorithm and look for Merkle root hashes that have a collision potential. A collision may occur, for example, whenever a marginal portion of the Merkle root hash value equals a certain predetermined value, and thus, for example, Merkle generator 12 can find N hash Merkle root values with the same marginal portion. Such hash Merkle root hash values may be defined as “winner” or “win” Merkle hash values. In some embodiments, a Merkle hash is considered a win Merkle hash if the K MSbits (most significant bits) of the marginal portion equal a certain predetermined value.

[0048] Reference is now made to FIG. 5, which is a schematic illustration of a Merkle generator 60 according to some embodiments of the present invention. The Merkle generator may include a Merkle generator manager 62, a Merkle memory 63, a block feeder 65 and a hash engine 68. Merkle generator 60 may receive a Merkle packet as described in detail above, including a Merkle branch and a coinbase transaction, and save the data in Merkle memory 63. Merkle generator manager 62 may initiate the Merkle scan process. In the scan process, block feeder 65 may read Merkle memory 63 and feed hash engine 68 with new Merkle branch data, each time with a new extra nonce. Hash engine 68 may perform Merkle hash calculations and check, for a certain extra nonce value, if the Merkle hash value is a win Merkle hash value. The win Merkle hash values are sent to Merkle generator manager 62, which sends them by a FIFO queue to the CPU.

[0049] Reference is now made to FIG. 6, which is a schematic illustration of a method for handling winner Merkle hash values according to some embodiments of the present invention. As shown in block 510, each time a winner Merkle hash value is found, it is added to a queue, for example, a first in first out (FIFO) queue, to be transferred to the CPU. A found winner Merkle hash value is sent to the CPU in a winner packet including the winner Merkle branch hash value and the respective extra nonce, or only the marginal portion of the winner Merkle branch hash value and the respective extra nonce.

[0050] As shown in block 520, once received by the CPU, the CPU adds the winner Merkle hash value to a collision table, to collect batches of N Merkle Winners. As shown in block 530, when a batch of N Merkle Winners is formed, the batch is forwarded to the N parallel mining engines shown in FIG. 3. The CPU collects winner Merkle hash values and once N winner Merkle hash values are found, the CPU sends a job packet to the N engines (or an engine supporting N parallel jobs), the job packet includes the respective N different mid-states along with the N winner Merkle hash values or along with the marginal portions only, for example with identifications of the respective Merkle hash values, such as the respective extra nonces. Additionally, in some embodiments of the present invention, a job packet may include a nonce range for the engines to scan. Additionally a job packet may include the additional block header data.

[0051] Reference is now made to FIG. 7, which is a schematic illustration of an exemplary mining engines system 700 according to some embodiments of the present invention. Mining engines system 700 may include an engines manager 710 and at least one multithreading engine 720, i.e. an engine that supporting N parallel jobs. System 700 may include, for example, up to 64 such multithreading engines. Multithreading engine 720 may include an engine controller 722 and engine core 724.

[0052] Reference is now made to FIG. 8, which is a schematic flowchart illustration of a mining process according to some embodiments of the present invention. As indicated in block 810, engines manager 710 may receive the job packets and forward the job packets to engine controller 722 of multithreading engine 720, for example by a FIFO queue. As indicated in block 820, engine controller 722 may initiate a job process by engine core 724. As indicated in block 830, engine core 724 may receive the respective N different mid-states along with the shared marginal portion and produce signatures by iterations over a defined range of nonce values. For a certain nonce value, two stages may be performed. As indicated in block 840, in a first stage N respective first-stage hashes are produced, for example in parallel, based on the N respective mid-states and using a shared data pipe (e.g., shared expander logic) between the N parallel threads. As indicated in block 850, a second stage of the process may include N parallel processes. In each of the N parallel processes, the engine core may produce a signature by a second-stage hash for one of the N first-stage hashes. In the second stage, a full process is done without sharing of data. As indicated in block 860, in case the signature is valid, the block chain may be signed. Then, the nonce is incremented and the process returns to the first stage, in which N respective first-stage hashes are produced and so on.

[0053] In the above description, an embodiment is an example or implementation of the inventions. The various appearances of “one embodiment,” “an embodiment” or “some embodiments” do not necessarily all refer to the same embodiments.

[0054] Although various features of the invention may be described in the context of a single embodiment, the features may also be provided separately or in any suitable combination. Conversely, although the invention may be described herein in the context of separate embodiments for clarity, the invention may also be implemented in a single embodiment.

[0055] Reference in the specification to “some embodiments”, “an embodiment”, “one embodiment” or “other embodiments” means that a particular feature, structure, or characteristic described in connection with the embodiments is included in at least some embodiments, but not necessarily all embodiments, of the inventions.

[0056] It is to be understood that the phraseology and terminology employed herein is not to be construed as limiting and are for descriptive purpose only.

[0057] The principles and uses of the teachings of the present invention may be better understood with reference to the accompanying description, figures and examples.

[0058] It is to be understood that the details set forth herein do not construe a limitation to an application of the invention.

[0059] Furthermore, it is to be understood that the invention can be carried out or practiced in various ways and that the invention can be implemented in embodiments other than the ones outlined in the description above.

[0060] It is to be understood that the terms “including”, “comprising”, “consisting” and grammatical variants thereof do not preclude the addition of one or more components, features, steps, or integers or groups thereof and that the terms are to be construed as specifying components, features, steps or integers.

[0061] If the specification or claims refer to “an additional” element, that does not preclude there being more than one of the additional element.

[0062] It is to be understood that where the claims or specification refer to “a” or “an” element, such reference is not be construed that there is only one of that element.

[0063] It is to be understood that where the specification states that a component, feature, structure, or characteristic “may”, “might”, “can” or “could” be included, that particular component, feature, structure, or characteristic is not required to be included.

[0064] The descriptions, examples, methods and materials presented in the claims and the specification are not to be construed as limiting but rather as illustrative only.

[0065] Meanings of technical and scientific terms used herein are to be commonly understood as by one of ordinary skill in the art to which the invention belongs, unless otherwise defined.

[0066] The present invention may be implemented in the testing or practice with methods and materials equivalent or similar to those described herein.

[0067] While the invention has been described with respect to a limited number of embodiments, these should not be construed as limitations on the scope of the invention, but rather as exemplifications of some of the preferred embodiments. Other possible variations, modifications, and applications are also within the scope of the invention.