# Fair NFT minting

I propose to hack on this idea at ETHLisbon.

## The problem

Many NFT projects feature NFTs with traits. Some traits are rarer than others, which makes them more valuable. Many NFT projects also distribute NFTs to minters at a constant mint price. To do so in an unbiased manner, projects need a source of fair randomness. Otherwise, a sophisticated attacker may use various techniques to mint rare NFTs for themselves and make a disproportionate profit.

To generate on-chain randomness, however, is very hard. A poor solution is to make a smart contract use the current block hash, but this is highly inadvisable as a miner may easily manipulate this value. For instance, a malicious minter may bribe a miner to produce a block hash which will result in them receiving an extremely rare and valuable NFT when they perform a mint transaction.

## Existing solutions

A popular solution is the Chainlink VRF service. Projects pay LINK tokens to Chainlink, which in turn generates a random number using a verifiable random function (VRF), and then calls the project's contract with the result.

## Why a new approach is useful

We have nothing against Chainlink's VRF solution but it would be good for the ecosystem if teams can enjoy more choices. Teams that do not wish to use Chainlink VRF, for any reason whatsoever, should have an alternative.

## Our approach

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.

## Technical details

There are two actors in this protocol:

1. the NFT team ("the team")
2. the minters

To begin the process, the team deploys a smart contract. The contract contains the following storage variables:

| Name | Type | Set by |
|-|-|-|
| `mintDeadlineBlock` | `uint256` | Constructor |
| `root` | `uint256` | Contract function |
| `result` | `uint256` | Contract function |

In the contract constructor, the team generates a random number `r` and inserts `h(r)` in the Merkle tree, updating `root`.

Each minter then generates a random number `s`, and sends a transaction to the contract with the following:
- `m` ETH, which is the constant mint price.
- `h(s)`, which is the hash of `s`, represented as an `uint256` value.

The contract inserts each `h(s)` in a Merkle tree with root `root` if the current block number is less than or equal to `mintDeadlineBlock`.

After `mintDeadlineBlock`, each minter sends `s` to the team. As long as at least 1 minter does this after `mintDeadlineBlock`, this protocol should be collusion-resistant.

Finally, the team generates a zero-knowledge proof (ZKP) and submits it to the contract. The ZKP proves the following:
- The team knows the preimage `r` of the hash `h(r)`.
- For each `h(s)` value, the prover knows the preimage `s`.
- The prover knows a valid Merkle root to each leaf in the Merkle tree.
- The prover knows an output `result` value which is the hash onion of `r` and all `s` values.
- To illustrate, a hash onion of the values `[r, s1, s2, s3]` is `h(h(h(s3, r), s2), s1)`.

The output signal `result` stored in the contract and used to randomly distribute NFTs using the Fisher-Yates shuffling algorithm.

## Why ZKPs are good for this use case

A single ZKP can allow the team to prove that they know multiple (or even all) the `s` values. If there there is a high number of minters, the team or minters can save gas as the verification cost is constant.

## Downsides

- To work around the hackerthon's time constraints, we limited our system to use a shallow Merkle tree, and compute the Merkle root in the circuit from *all* leaves. While this restricts the maximum number of minters due to the high number of circuit constraints and proving time, the solution is to verify the leaves in batches.
- Every minter must submit their `s` value. At least one honest minter must do so after the deadline. This may not be user-friendly.
- The process requires an additional step from each minter.
- The mint function may be expensive if the protocol uses a snark-friendly hash function like Poseidon.
- One way to alleviate the gas cost is to simply store each value, and have the team pay the gas needed to generate the Merkle root. This may be out of scope of this hackerthon.
- Another solution is to use SHA256 for the Merkle tree, which is cheap in the EVM, but expensive for the prover. That said, circom 2 is very fast and a circuit that hashes 10 values using SHA256 (1230305 constraints) only requires 24 seconds to compile, though the resulting proving key will be extremely large (more than 1GB).

## Collusion resistance properties

For the result to be unbiased, only one minter has to not collude with the team and other minters. To not collude, this minter must only reveal their secret `s` after the minting deadline.

- If the team colludes with all the minters
- The whole process is compromised if everyone colludes, but there is no point for the team to use this method. They might as well directly distribute the NFTs to the minters.
- If all the minters collude, but not with the team
- Since the team's `r` value is not known by the minters, the result is an unbiased random value.the result is an unbiased random value.
- If the team colludes with **all but one** minters
- If at least 1 minter withholds their `s` value, the result is an unbiased random value.
- At least 1 honest minter must reveal their `s` value only after the beacon deadline so that colluding minters cannot select `s` values that bias the result.