ZKP NFT drop

Project overview

Generate a random number for fair NFT distribution using a multi-party ZKP commit-reveal scheme such that only 1 minter has to be honest for the randomness to be unbiased.

Discord contact username: ismaeldm#6744

SLIDES

Inspiration

We observed that some NFT projects face a problem where they use on-chain randomness to distribute NFTs with traits of varying rarity. Yet, on-chain randomness is a poor source of entropy. Miners who collude with an attacker may easily manipulate the random value used to distribute NFTs and give the attacker the most rare NFTs, which is unfair to other market participants. Another attack is to submit and cancel mint transactions until one mints an ultra-rare NFT.

One solution commonly proposed, such as by Paradigm, is to use a third-party Verifiable Random Function service (such as Chainlink VRF) to obtain this random value. We believe, however, that the community deserves an alternative that does not rely on a third party. Even if there is a good third-party solution, an NFT team may not wish to use it. In such a case, whatever their reasons, they should be able to choose a different method to generate this random value.

We also observed that zero-knowledge proofs (ZKPs) on Ethereum are a very useful skill and we are motivated to use this hackathon to learn how to write ZKPs and smart contracts that use them.

What it does

Our approach is to have the team and each minter commit to a secret value, and reveal it later. We use a ZKP to prove the correctness of multiple revealed values in a single transaction, allowing users and the team to save gas. Only one minter needs be honest for our approach to work.

Our scheme is fully described in this document.

How we built it

We used a variety of languages and developer tools:

Name	What it was used for
Solidity	Ethereum smart contracts
Hardhat	Smart contract development and testing
circom v2	ZK circuits
circom-helper	Circuit development and testing
snarkjs / rapidsnark	Proof generation
zkey-manager	Proving key generation

We adopted code from open-source projects including the following:

Project	Components
Minimum Anti-Collusion Infrastructure	Incremental Merkle Tree contract, circuits, and library

Challenges we ran into

ZKPs are complex and a require a lot of deep domain knowledge. As such, we prepared for the hackathon by practicing how to write and test circom circuits (e.g. writing a circuit which allows a prover to prove that a list of input signals is sorted).
When figuring out how our system should work, we spent a lot of time finding and addressing potential vulnerabilities. For instance, we had to ensure that the last NFT minter would not be able to influence the random number. To prevent this attack, we added a randomness submission deadline such that only one minter needs to withhold their secret random number until after the deadline, so the last minter has no way to unduly bias the result.
We had tried to address the last-minter attack by applying a block hash not known in advance, but decided against this approach. The reason for this is that if all minters collude, there is no point randomising the distribution as they can simply redistribute the NFTs among themselves. Furthermore, we wanted to keep the project simple and manageable for this hackathon, so we removed this mechanism from our scheme.

Accomplishments that we're proud of

Finished project in time, writing all circuits, contracts and tests
Managed to create a script that demonstrates the functionality
Kept a cheerful and motivating environment all the time
We were mindful of our time and energy and planned accordingly

What we learned

How to write circuits in circom, generate proofs, and verify them in Ethereum.
The utility of Merkle trees as a mechanism to prove knowledge of many values without the high gas cost of passing them into the verifier contract function as public inputs.