Method and system for providing a proof-of-work

1. A method for providing a proof-of-work, the method comprising:

a) computing, by a verification computing device (VCD), a first linear feedback shift register sequence (LFSR-S) using a first polynomial having a first degree and computing, by the VCD, a second LFSR-S based on a second polynomial, wherein the polynomials are computed such that the first polynomial divides the second polynomial,

b.1) generating, by the VCD, elements of the second LFSR-S based on initial state parameters and corresponding coefficients of the second LFSR-S, wherein the initial state parameters and corresponding coefficients, in conjunction, at least partially determine the second LFSR-S,

b.2) transmitting, by the VCD, the elements and the corresponding coefficients of the second LFSR-S to a proving computing device (PCD),

c) transmitting a challenge, generated by the VCD using the elements of the second LFSR-S, to the PCD,

d) recursively computing, by the PCD, all elements of the first LFSR-S by using the transmitted elements and coefficients of the second LFSR-S,

e) computing a solution for the received challenge based on the computed elements of the first LFSR-S and transmitting the solution to the VCD, and

f) providing a proof-of-work by verifying, by the VCD, the transmitted solution by:

recomputing a solution to the challenge using initial state parameters and coefficients of the first LFSR-S, and

comparing the computed solution of the PCD with the recomputed solution of the VCD.

2. The method according to claim 1 , wherein the second polynomial is computed by the VCD prior to the first polynomial.

3. The method according to claim 1 , wherein the lengths of the first and second LFSR-S are computed by the VCD such that the lengths are identical.

4. The method according to claim 1 , wherein the challenge comprises a computation of a product of a first set and a distinct second sets.

5. The method according to claim 1 , wherein initial state and coefficients of the second LSFR-S are selected such that the second LSFR-S has a period equal or greater than the period of the first LSFR-S.

6. The method according to claim 1 , wherein the elements of the first LSFR-S are computed with a common base and exponents, the exponents being initial state parameters of the first LSFR-S.

7. The method according to claim 1 , wherein a plurality of challenges is generated and a plurality of solutions is computed.

8. A system for providing a proof-of-work, comprising a verification computing device (VCD) and a proving computing device (PCD),

the VCD being adapted to:

compute a first linear feedback shift register sequence (LFSR-S) using a first polynomial having a first degree and computing, a second LFSR-S based on a second polynomial, wherein the polynomials are computed such that the first polynomial divides the second polynomial,

generate elements of the second LFSR-S based on initial state parameters and corresponding coefficients of the second LFSR-S, wherein the initial state parameters and corresponding coefficients, in conjunction, at least partially determine the second LFSR-S,

transmit the elements of the second LFSR-S to the PCD,

transmit a challenge, generated by the VCD using the elements of the second LFSR-S, to the PCD, and

provide a proof-of-work by verifying, a transmitted solution by:

recomputing a solution to the challenge using initial state parameters and coefficients of the first LFSR-S, and

comparing a computed solution of the PCD with the recomputed solution, and

the PCD being adapted to:

recursively compute all elements of the first LFSR-S by using the transmitted elements of the second LFSR-S, and

compute a solution for the received challenge based on the computed elements of the first LFSR-S and transmitting the solution to the VCD.

9. A non-transitory computer readable medium storing a program causing a computer to execute a method for providing a proof-of-work, the method comprising:

a) computing a first linear feedback shift register sequence (LFSR-S) using a first polynomial having a first degree and computing a second LFSR-S based on a second polynomial, wherein the polynomials are computed such that the first polynomial divides the second polynomial,

b.1) generating elements of the second LFSR-S based on initial state parameters and corresponding coefficients of the second LFSR-S, wherein the initial state parameters and corresponding coefficients, in conjunction, at least partially determine the second LFSR-S,

b.2) providing, to a proving computing device (PCD), the elements of the second LFSR-S,

c) providing, to the PCD, a challenge using the elements of the second LFSR-S,

d) recursively computing all elements of the first LFSR-S by using the provided elements of the second LFSR-S,

e) computing a solution for the received challenge based on the computed elements of the first LFSR-S, and

f) generating a proof-of-work by verifying the solution by:

recomputing a solution to the challenge using initial state parameters and coefficients of the first LFSR-S, and

comparing the computed solution with the recomputed solution.

10. A verification computing device (VCD) comprising one or more hardware processors adapted to:

compute a first linear feedback shift register sequence (LFSR-S) using a first polynomial having a first degree and computing a second LFSR-S based on a second polynomial, wherein the polynomials are computed such that the first polynomial divides the second polynomial,

generate elements of the second LFSR-S based on initial state parameters and corresponding coefficients of the initial state parameters, wherein the initial state parameters and corresponding coefficients, in conjunction, at least partially determine the second LFSR-S,

transmit the elements of the second LFSR-S to a proving computing device (PCD),

transmit a challenge, generated by the VCD using the elements of the second LFSR-S, to the PCD, and

generate a proof-of-work by verifying a received solution by:

recomputing a solution to the challenge using initial state parameters and coefficients of the first LFSR-S, and

comparing a computed solution of the PCD with the recomputed solution of the VCD.

11. A method, performed by a verification computing device (VCD), comprising:

A1) computing a first linear feedback shift register sequence (LFSR-S) using a first polynomial having a first degree and computing a second LFSR-S based on a second polynomial, wherein the polynomials are computed such that the first polynomial divides the second polynomial,

A2) generating elements of the second LFSR-S based on initial state parameters of the second LFSR-S, wherein the initial state parameters at least partially determine the second LFSR-S,

B1) providing the elements of the second LFSR-S to a proving computing device (PCD),

C1) providing a challenge to the PCD, wherein the challenge is generated using the elements of the second LFSR-S, and

D1) generating a proof-of-work by verifying a received solution by:

recomputing a solution to the challenge using initial state parameters and coefficients of the first LFSR-S, and

comparing the received solution with the recomputed solution.

12. A non-transitory computer readable medium storing a program causing a computer to execute a process, the process comprising:

A1) computing a first linear feedback shift register sequence (LFSR-S) using a first polynomial having a first degree and computing a second LFSR-S based on a second polynomial, wherein the polynomials are computed such that the first polynomial divides the second polynomial,

A2) generating elements of the second LFSR-S based on initial state parameters of the second LFSR-S, wherein the initial state parameters at least partially determine the second LFSR-S,

B1) providing, to a proving computing device (PCD), elements generated by a function on input of a number of initial state parameters of the second LFSR-S,

C1) providing, to the PCD, a challenge that is based on the elements of the second LFSR-S, and

D1) generating a proof-of-work by verifying a received solution by:

recomputing a solution to the challenge using initial state parameters and coefficients of the first LFSR-S, and

comparing the received solution with the recomputed solution.

13. The method of claim 1 , wherein the second LFSR-S is over a finite field F, the initial state parameters (s 1 , . . . , s λ ) are structured such that (s 1 , . . . , s λ )ϵF λ , and the coefficients (c 1 , . . . , c λ ) are structured such that (c 1 , . . . , c λ )ϵF, wherein λ is a positive integer length of the second LFSR-S.

14. The method of claim 13 , wherein the elements of the second LFSR-S are expressed as s t+λ+1 and defined according to the following formula in which t≥0:

s

t

+

λ

+

1

:=

∑

i

=

1

λ

⁢

c

i

*

s

t

+

i

.

15. A verification computing device comprising one or more hardware processors, which alone or in combination, are configured to perform the method of 11 .