Gas issue when cashing a Cheque/proving ownership of an Attestation

Implementations
#1

@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:

  1. 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:

    1. 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 viewing p as the private key of an ECDSA signature scheme, where s is then the corresponding public key. Thus simply constructing a signature on a unique challenge value, is sufficient to prove knowledge of p in relation to s=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 random p but also linking it to a not-so-random value H(i) linking to a user's identifier such as email. Since we do not want H(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.
    2. Brute-forceable identifier: The above approach can also be used with H(i) if we allow publishing s'=g^H(i). However, this would allow anyone observing the blockchain to try to either brute-force i or checking if a specific i 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.
    3. 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 to s.
    4. Single-use attestations: The cheque is still s=H(i)^p. The user then proves to the attester that it knows p and s.t. s=H(i)^p and that it has access to the identifier i. The user also picks a newly random p' and proves to the attester that it knows this p' 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/ticket s. Then the user will then prove that it owns this attestation by proving that it knows p'. This can be done by singing a unique challenge using p' is a private key and verifying against s' stored in the attestation.

  2. 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:

  1. 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.
  2. 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.
#2

In general I think the most promising approach for the DevCon ticket case is to go with 1.4, because in this scenario a single-use would mean that one attestation is needed, which would most likely also be the case even if we used the expensive cryptographic approach we have now. However, since tickets will be sent directly to users' mails, maybe approach 1.1. is actually sufficient? The users are implicitly getting an "attestation" of their mail address when they buy a ticket since this is also the channel where the user will receive the ticket and its associated secret information. Still, approach 1.1. cannot work if DevCon allows bulk purchases of tickets, since they must then be redistributed to their individual users from the mail address of the user who purchased the bulk. @weiwu.zhang do you know if that is the case?

In regards to cheques, the single-use attestation makes less sense since we don't want users to get a new attestation every time they get a new cheque. However we could imagine a combination of 1.3 and 1.4: Basically a single-use attestation for the first cheque. But then if the user already has an attestation, the sender of a cheque would look that up and assign a cheque to that attestation. Of course, in that case a cheque in its basic form does not make much sense since the sender could just transfer the Ether or tokens directly. But if the cheque needs to be part of some other smart contract logic, then sending a cheque even though the user already has an attested Ethereum address would still make a lot of sense.

#3

After discussion with @weiwu.zhang I should point out that when I talk about a user's key above, I don't mean their Ethereum key, but instead a new key derived from the user's secret information which is part of the ticket or the attestation. The reason for calling it an ECDSA key is that using ECDSA this allows us to prove knowledge of the secret using the intrinsic ecRecover operation very cheaply, compared to doing a standard Schnorr ZK proof of knowledge.

#4

One thing we should be aware of is that in this solution (i.e. path 1.4) we now open up the possibility of the Attestation authority to falsely certify tickets. That is, it can make an attestation to anyone allowing to use any ticket. Thus in this model we add significantly more trust to the Attestation Authority.

#5

Why not use the precompiled contract's bn curve EIP-1108: Reduce alt_bn128 precompile gas costs.

After reading you code, I saw 2 ecMul ops and 1 ecAdd op, it just costs 6000*2+150=12150 gas if you use alt_bn128.

BTW, do you really need 125 bits security?

#6

Ah, cool! I did not know about that proposal! But is it accepted? But even if it is, even just using the EIP-196 they link to as the current state could be used. (I am not a blockchain-expert so the whole flow of EIPs and evolution of Ethereum is not something I know about.)

Ideally we should have at least 120 bits security, but you could argue that the 90-100 bits of security afforded by BN254 is sufficient. In particular taking into account this is the curve being used in many different blockchain applications.

#7

It has been activated on Istanbul fork. Bn256AddGasIstanbul

#8

@JamesB will it be possible for us to simply use this instruction?