Preventing replay attacks for winning tickets

[yondonfu]

We need to prevent recipients from cashing in the same winning ticket on-chain multiples times - each winning ticket can only be cashed in once.

One way to defend against replay attacks is to have the contract maintain a mapping of ticket IDs corresponding to cashed tickets. We can define a ticket ID as the hash of all the relevant metadata in the ticket including the sender specified random nonce so each ticket ID should be unique. When a recipient cashes in a winning ticket, the contract will check if the ticket ID has already been used and if so, the transaction will revert.

The downside of this solution is that it adds an additional 20000 gas for an SSTORE whenever a recipient cashes a winning ticket thereby increasing the transaction cost.

Other ways to defend against replay attacks include:

• Instead of storing the ticket ID on-chain the contract just emits an event containing the ticket ID. If we assume that the recipients have some economic value staked either inside or outside (i.e. if the probabilistic payment contract is used as a part of a larger contract system) then anyone that submits a ticket ID that was used twice can penalize the recipient that replayed the ticket ID. This would require either a challenge period after a winning ticket is initially submitted or the sender would just lose funds from the replay attack, but the attacker would be slashed later on once the evidence of a replay is submitted.
• Instead of storing each ticket ID in an on-chain mapping we could use a cryptographic accumulator that supports proofs of non-membership - the accumulator would be represented by a short value stored in the contract and can be used along with a proof of non-membership to demonstrate that a ticket ID has not yet been used. Merkle trees are probably not a good candidate because updating the Merkle tree requires knowledge of all the existing leaves and keeping track of all the leaves on-chain would be more expensive than the single SSTORE required for the original on-chain mapping solution. RSA accumulators might work because they support updates without knowledge of the other members of the set, but these are not as well explored for usage in contracts (research is picking up though with their proposed usage in Plasma Cash). We would need to figure out if using such an accumulator and verifying a proof of non-membership is cheap enough such that it is makes sense to use an accumulator instead of an on-chain mapping.

The original solution should work for an initial implementation and research into optimizations can be left for subsequent iterations.

[dob]

I'd be in favor of adding the extra gas cost for the SSTORE initially, and then considering optimizations later. I'm not sure if the potentially heavy cryptographic operations would be cheaper than the SSTORE anyway.

One other optimization idea is to include an optional incentive to remove expired data from storage (which should provide gas refunds). For any tickets you cashed previously that have been expired, remove their entry from the mapping in the same call as cashing your ticket, and reduce the cost.