@JamesB made a proof-of-concept implementation of a smart contract to verify a Fiat-Shamir, Schnorr zero-knowledge proof in connection with cashing a cheque using an attestation. Basically this surmounts to doing two point multiplications and some additions on an elliptic curve.
The source code can be found here, which internally uses this code for elliptic curve arithmetic. It turns out that this uses 1,483,008 gas, which is about $50. This is clearly way too expensive to be feasible to use in practice, so we need to find some solution to this. It is not feasible to reduce the amount of multiplications needed in the proof, as two is basically as low as possible for a "real" ZK proof.
There are several possible paths to take, and this thread will discuss which of these paths we will take. I will explain the options below:
-
Limit the amount privacy and security features: This involves having cheque/tickets be redeemable using only a secret identifier (that is, not linked to an identifier), reducing the amount of anonymity (in regards to a user's identifier), requiring the user to have an attestation before a cheque or ticket can be issued or only having single use of attestations. These sub-approaches are discussed in more detail below:
-
Non-linked cheques/tickets: This involves the user doing a simple proof of knowledge of the discrete log of
s=g^p
(when using multiplicative group notation). This can be done by simply viewingp
as the private key of an ECDSA signature scheme, wheres
is then the corresponding public key. Thus simply constructing a signature on a unique challenge value, is sufficient to prove knowledge ofp
in relation tos=g^p
. Such a signature can be verified using the intrinsic ecRecover algorithm in Solidity, which only costs 3000 gas. Unfortunately our protocol requires both proving knowledge of a randomp
but also linking it to a not-so-random valueH(i)
linking to a user's identifier such as email. Since we do not wantH(i)
to be public, as this would allow brute-forcing of a user's mail address, this approach can only allow us to prove knowledge of random values of their own. Hence if we use this approach we have to forgo with linking to a user's low-entropy identifier. -
Brute-forceable identifier: The above approach can also be used with
H(i)
if we allow publishings'=g^H(i)
. However, this would allow anyone observing the blockchain to try to either brute-forcei
or checking if a specifici
was used anywhere. This will break a lot of the anonymity that would otherwise be afforded by the blockchain. However, depending on the use-case this might actually be acceptable. -
Sender knowing the user's attestation: This is an extension of suggestion 1 above, where an issuer issues a cheque/ticket to a user, but where the secret used to solve the riddle is the public information of a user's attestation. That is, if the user's attestation is
s=g^p
and the cheque/ticket is assigned to the user with an attestation tos
. -
Single-use attestations: The cheque is still
s=H(i)^p
. The user then proves to the attester that it knowsp
and s.t.s=H(i)^p
and that it has access to the identifieri
. The user also picks a newly randomp'
and proves to the attester that it knows thisp'
s.t.s'=g^p'
. If so, the attester signs a certificate saying that the user with a specific Ethereum address has access to the identifier and secret which was used in the cheque/tickets
. Then the user will then prove that it owns this attestation by proving that it knowsp'
. This can be done by singing a unique challenge usingp'
is a private key and verifying againsts'
stored in the attestation.
-
Non-linked cheques/tickets: This involves the user doing a simple proof of knowledge of the discrete log of
-
Optimise the arithmetic operations: This approach involves changing the underlying library and elliptic curves to something more efficient and thus lowering the price of cheque/ticket validation. @JamesB talked with the people behind Aztec and looking into their benchmarks, it seems that we could expect to reduce the cost of a Schnorr proof to something between 70,000-300,000 gas, which might be cheap enough to be acceptable. However Aztec uses the Weierstrass 254 Barreto-Naehrig (BN254) curve for which a pretty significant weakness has been found last year. Basically the security of this curve is around 90-100 bits. This should be compared to secp256k1 which has around 125 bits security.
One general thing we should keep in mind in case of the ticket case, is the fact that a ticket can be used multiple times and that the actions for which it is used might not be linked to the user's Ethereum address. This means that there are two possible attack vectors on usage that we don't have with the cheque case:
- If there is no penalisation for ticket misuse, then nothing prevents a user from creating an Ethereum burner address (and email address for that matter), buy a ticket, make an attestation and share all the secret information with their friends and hence allowing them to use the ticket as well. This is an inherent issue when something can be used multiple times and the incentives to cheat (i.e. sell multiple copies of a ticket) is less than the potential penalisation (being booted from the event). This problem cannot be fixed cryptographically and must be handled using external mechanism or incentives (say the user must put up an ante for a digital ticket that they will only get back if no ticket misuse has been found during the conference) or that a ticket can only be used once for each digital event.
- If the ticket gets verified on the blockchain and there is no transaction involved based on the Ethereum address in the user's attestation, then a miner can do a man-in-the-middle attack and basically steal the ZK proof the user is doing and front-run them. This is again an inherent problem of how mining works and must again be solved by some external mechanism. For example that a token is always transferred to the user's Ethereum address in connection with a proof, which the user must then transfer back to a conference address in order to finalise a proof that they hold the ticket and their proof has not been front-runner.