# US 2022/0035808 A1 · Blockchain system comprising consensus protocol using search for good approximate solutions to any optimization problem and its computor program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0035808 A1
- Document ID: US20220035808A1
- Status: Published application
- Kind: A1
- Application number: 17/199,504
- Filed: 2021-03-12
- Published: 2022-02-03
- Earliest claimed: 2020-08-01
- Assignees: Proof-of-Search K.K.
- Inventors: Naoki SHIBATA
- Web page: https://patentgrep.com/patent/US20220035808A1

## CPC

- G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases}
- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- G06F 16/2365: {Ensuring data consistency and integrity}
- H04L 9/50: {using hash chains, e.g. blockchains or hash trees}
- H04L 63/12: {Applying verification of the received information (cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The invention comprises a decentralized consensus protocol for blockchains in which the computation can be used to search for good approximate solutions to any optimization problem. This protocol allows the wasted energy to be used for finding approximate solutions to problems submitted by any nodes (called clients). This protocol works in a similar way to proof-of-work, and it makes nodes evaluate a large number of solution candidates to add a new block to the chain. A client provides a search program that implements any search algorithm that finds a good solution by evaluating a large number of solution candidates. The node that finds the best approximate solution is rewarded by the client.

## Claims

### Claim 1

A blockchain system operated by nodes joining a peer-to-peer network, comprising:
a plurality of nodes in which each node has a means to create jobs, to broadcast the jobs to a blockchain and to verify a genuineness of blocks which the node receives from other nodes; and
a plurality of blocks in which each block includes a hash value of the last block in the blockchain and one or more jobs selected from the jobs broadcasted to the blockchain and one or more nonces,
wherein the nonce is a combination of a solution candidate of the optimization problem of a corresponding job in the block or one of the previous blocks and an evaluated value of the solution candidate, and the block is genuine only when the solution candidate and an evaluated value of the solution candidate coincide for each nonce in the block.

### Claim 2 (depends on 1)

The blockchain system of claim 1, wherein
each node has a means to create miniblocks, to broadcast the miniblocks to the blockchain and to verify the genuineness of miniblocks which the node receives from other nodes,
each block includes one or more miniblocks,
each miniblock consists of the hash value of the part of the block other than the miniblocks, an ID of the node that creates the miniblock, an ID of a job selected from the broadcasted jobs, and a nonce,
the miniblock is added to a block only when the hash value of the miniblock begins with a required number of zero bits, and
the block is added to the end of the blockchain only when all the miniblocks corresponding to all the jobs requested have been added to the block.

### Claim 3 (depends on 2)

The blockchain system of claim 2, wherein
each job includes the ID of the node that created the job, an optimization problem of which the node wants to get the best approximate solution, the charge to pay for solving the problem, and an evaluator,
the evaluator is a program which evaluates solution candidates and gives evaluation values, and the node that broadcasted the solution candidate with the highest evaluation value is given the charge of the job.

### Claim 4 (depends on 1)

The blockchain system of claim 1, further comprising:
a function to count the number of steps of the execution to search the solution candidate deterministically,
a function to return the number of steps,
and a function to terminate the program of searching a solution candidate after a specified number of steps executed.

### Claim 5 (depends on 2)

The blockchain system of claim 2, further comprising:
a function to count the number of steps of the execution to search the solution candidate deterministically,
a function to return the number of steps,
and a function to terminate the program of searching a solution candidate after a specified number of steps executed.

### Claim 6 (depends on 3)

The blockchain system of claim 3, further comprising:
a function to count the number of steps of the execution to search the solution candidate deterministically,
a function to return the number of steps,
and a function to terminate the program of searching a solution candidate after a specified number of steps executed.

### Claim 7

A non-transitory computer readable medium including computer program which realizes a blockchain system operated by nodes joining a peer-to-peer network, the blockchain system comprising:
a plurality of nodes in which each node has a means to create jobs, to broadcast the jobs to the blockchain and to verify the genuineness of blocks which the node receives from other nodes; and
a plurality of blocks in which each block includes a hash value of the last block in the blockchain and one or more jobs selected from the jobs broadcasted to the blockchain and one or more nonces,
wherein the nonce is a combination of a solution candidate of an optimization problem of a corresponding job in the block or one of the previous blocks and an evaluated value of the solution candidate, and the block is genuine only when the solution candidate and an evaluated value of the solution candidate coincide for each nonce in the block.

### Claim 8 (depends on 7)

The non-transitory computer readable medium according to claim 7, wherein
each node has a means to create miniblocks, to broadcast the miniblocks to the blockchain and to verify the genuineness of miniblocks which the node receives from other nodes,
each block includes one or more miniblocks,
each miniblock consists of the hash value of the part of the block other than the miniblocks, an ID of the node that creates the miniblock, an ID of a job selected from the broadcasted jobs, and a nonce,
the miniblock is added to a block only when the hash value of the miniblock begins with a required number of zero bits, and
the block is added to the end of the blockchain only when all the miniblocks corresponding to all the jobs requested have been added to the block.

### Claim 9 (depends on 8)

The non-transitory computer readable medium according to claim 8, wherein
each job includes the ID of the node that created the job, an optimization problem of which the node wants to get the best approximate solution, the charge to pay for solving the problem, and an evaluator,
the evaluator is a program which evaluates solution candidates and gives evaluation values, and the node that broadcasted the solution candidate with the highest evaluation value is given the charge of the job.

### Claim 10 (depends on 7)

The non-transitory computer readable medium according to claim 7, further comprising:
a function to count the number of steps of the execution to search the solution candidate deterministically,
a function to return the number of steps,
and a function to terminate the program of searching a solution candidate after a specified number of steps executed.

### Claim 11 (depends on 8)

The non-transitory computer readable medium according to claim 8, further comprising:
a function to count the number of steps of the execution to search the solution candidate deterministically,
a function to return the number of steps,
and a function to terminate the program of searching a solution candidate after a specified number of steps executed.

### Claim 12 (depends on 9)

The non-transitory computer readable medium according to claim 9, further comprising:
a function to count the number of steps of the execution to search the solution candidate deterministically,
a function to return the number of steps,
and a function to terminate the program of searching a solution candidate after a specified number of steps executed.
