Statement proof and verification

1 . A computer implemented method of providing proof that a statement is true while keeping a secret input to the statement a secret, the method performed on a computing device and comprising:

generating a zero knowledge proof using a public input, the secret input, and a proving key linked to an augmented verification circuit,

wherein the augmented verification circuit comprises (i) a verification circuit arranged to receive the public input and secret input, supply the secret input to a function circuit representing the statement to generate a function circuit output, and determine whether the public input corresponds to the function circuit output; and (ii) a multiplicative gate arranged to receive the secret input and a dummy value; and

wherein the zero knowledge proof comprises a batched commitment to inputs of multiplicative gates of the augmented verification circuit, the batched commitment generated using a first vector comprising n components from a finite group of data elements, wherein each of the n components of the first vector correspond to a respective input of the multiplicative gates of the augmented verification circuit and one of the n components of the first vector is at a position which corresponds to an input wire of the dummy multiplicative gate which is arranged to receive the secret input, and wherein the secret input is a discrete logarithm of a public element of said finite group of data elements; and

transmitting the zero knowledge proof to a verifying computing device to enable the verifying computing device to verify that the computing device has knowledge of the secret input.

2 . The computer implemented method of claim 1 , wherein the batched commitment is a batched Pedersen commitment.

3 . The computer implemented method of claim 1 , wherein the finite group of data elements are of an elliptic curve.

4 . The computer implemented method of claim 3 , wherein the public element of said finite group of data elements is a public key and the secret input is a signing key.

5 . The computer implemented method of claim 1 , wherein the method further comprises proving that the secret input is the discrete logarithm of the public element.

6 . The computer implemented method of claim 5 , wherein proving that the secret input is the discrete logarithm of the public element comprises:

generating a further batched commitment, and transmitting the further batched commitment to the verifying computing device;

receiving a random challenge from the verifying computing device;

generating a response to the random challenge, and transmitting the response to the verifying computing device to prove that the secret input is the discrete logarithm of the public element.

7 . The computer implemented method of claim 6 , wherein the further batched commitment is a batched Pedersen commitment.

8 . The computer implemented method of claim 6 , wherein generating the further batched commitment comprises:

generating a second vector comprising n components, wherein a component of the second vector at a predetermined position, corresponding to the position in the first vector, is set to zero; and

generating the further batched commitment by committing to the second vector.

9 . The computer implemented method of claim 8 , wherein remaining components of the second vector are random values.

10 . The computer implemented method of claim 8 , wherein the finite group of data elements are of an elliptic curve, and generating the further batched commitment to the second vector uses a commitment key vector comprising n components from the finite group of data elements and one of the n components of the commitment key vector is a base point of the elliptic curve at a predetermined position which corresponds to the position in the first vector, the public element obtained by multiplying said base point with the secret input.

11 . The computer implemented method of claim 8 , wherein in response to receiving the random challenge, the method comprises:

modifying the first vector by replacing the secret input at said position with a zero to generate a modified first vector;

wherein the response comprises a response vector generated by combining the modified first vector with the second vector using the random challenge; and

transmitting the response to the verifying computing device.

12 . The computer implemented method of claim 11 , wherein the method further comprises combining a random element used to generate the batched commitment with a further random element of the further batched commitment to generate a combined random element, wherein the response comprises the combined random element.

13 . The computer implemented method of claim 1 , wherein the method comprises transmitting the statement to the verifying computing device.

14 . A computer implemented method of verifying that a statement is true without knowledge of a secret input to the statement, the method performed on a computing device and comprising:

receiving a zero knowledge proof from a proving computing device;

obtaining the statement;

verifying that the zero knowledge proof is valid using the zero knowledge proof, a public input and a verification key linked to an augmented verification circuit,

wherein the augmented verification circuit comprises (i) a verification circuit arranged to receive the public input and secret input, supply the secret input to a function circuit representing the statement to generate a function circuit output, and determine whether the public input corresponds to the function circuit output; and (ii) a multiplicative gate arranged to receive the secret input and a dummy value; and

wherein the zero knowledge proof comprises a batched commitment to inputs of multiplicative gates of the augmented verification circuit, the batched commitment generated using a first vector comprising n components from a finite group of data elements, wherein each of the n components of the first vector correspond to a respective input of the multiplicative gates of the augmented verification circuit and one of the n components of the first vector is at a position which corresponds to an input wire of the dummy multiplicative gate which is arranged to receive the secret input, and wherein the secret input is a discrete logarithm of a public element of said finite group of data elements; and

determining that the proving computing device has knowledge of the secret input based on said verifying.

15 . The computer implemented method of claim 1 , wherein an output of the multiplicative gate is not linked to the verification circuit.

16 . The computer implemented method of claim 1 , wherein the function circuit implements a hash function and, preferably, an SHA-256 hash function.

17 . A non-transitory computer readable storage medium comprising computer readable instructions that, when read by a computing device, cause the computing device to perform a method of providing proof that a statement is true while keeping a secret input to the statement a secret, the method performed on a computing device and comprising:

generating a zero knowledge proof using a public input, the secret input, and a proving key linked to an augmented verification circuit,

wherein the augmented verification circuit comprises (i) a verification circuit arranged to receive the public input and secret input, supply the secret input to a function circuit representing the statement to generate a function circuit output, and determine whether the public input corresponds to the function circuit output; and (ii) a multiplicative gate arranged to receive the secret input and a dummy value; and

wherein the zero knowledge proof comprises a batched commitment to inputs of multiplicative gates of the augmented verification circuit, the batched commitment generated using a first vector comprising n components from a finite group of data elements, wherein each of the n components of the first vector correspond to a respective input of the multiplicative gates of the augmented verification circuit and one of the n components of the first vector is at a position which corresponds to an input wire of the dummy multiplicative gate which is arranged to receive the secret input, and wherein the secret input is a discrete logarithm of a public element of said finite group of data elements; and

transmitting the zero knowledge proof to a verifying computing device to enable the verifying computing device to verify that the computing device has knowledge of the secret input.

18 . A computing device comprising a processor and memory, the memory storing instructions that, when executed by the processor cause the computing device to perform a method of providing proof that a statement is true while keeping a secret input to the statement a secret, the method performed on a computing device and comprising:

generating a zero knowledge proof using a public input, the secret input, and a proving key linked to an augmented verification circuit,

wherein the augmented verification circuit comprises (i) a verification circuit arranged to receive the public input and secret input, supply the secret input to a function circuit representing the statement to generate a function circuit output, and determine whether the public input corresponds to the function circuit output; and (ii) a multiplicative gate arranged to receive the secret input and a dummy value; and

wherein the zero knowledge proof comprises a batched commitment to inputs of multiplicative gates of the augmented verification circuit, the batched commitment generated using a first vector comprising n components from a finite group of data elements, wherein each of the n components of the first vector correspond to a respective input of the multiplicative gates of the augmented verification circuit and one of the n components of the first vector is at a position which corresponds to an input wire of the dummy multiplicative gate which is arranged to receive the secret input, and wherein the secret input is a discrete logarithm of a public element of said finite group of data elements; and

transmitting the zero knowledge proof to a verifying computing device to enable the verifying computing device to verify that the computing device has knowledge of the secret input.