Nouns NFT contract analysis

The objective of this document is to describe how we use the current Nouns NFT Smart Contract to allow prove of delegation and token ownership for voting

Ownership Proof of a single NFT

The checkpoint system (described below) will most likely not be needed. To prove that an account had the right to vote for a given token_id at a certain block:

(1) if no delegation, prove that at the correct block:

ownerOf[token_id] == account
_delegates[account] == 0x0

(2) if the a delegator has delegated his/her token to an account, prove that at the correct block:

ownerOf[token_id] == delegator
_delegates[delegator] == account

Contract Review

Nouns' Token Contract implemented the ERC721 standard (aka NFT) with slight modification to allow voting.

In particular, they use the modified version of ERC721Checkpointable from Compound Lab's to generate checkpoints of token balance. This allows their token contract to have balance history, much like MiniMi did for ERC20 standard.

The contract maintains the current map between delegators and delegates via the _delegatesmapping. It is not possible to delegate individual tokens, an entry in that mapping means that all NFTs held are delegated.

/// @notice A record of each accounts delegate
mapping(address => address) private _delegates;

The contract also maintains the full history of voting power of each address via the following data structures, of which the checkpoints mapping is the most important one:

/// @notice A checkpoint for marking number of votes from a given block
struct Checkpoint {
    uint32 fromBlock;
    uint96 votes;
}

/// @notice A record of votes checkpoints for each account, by index
mapping(address => mapping(uint32 => Checkpoint)) public checkpoints;

/// @notice The number of checkpoints for each account
mapping(address => uint32) public numCheckpoints;

For a given account acct, and a given checkpoint index id, the voting power is given by checkpoints[acct][id].votes and the corresponding block by checkpoints[acct][id].fromBlock.

The latest checkpoint index (assuming there are any checkpoints), is numCheckpoints - 1. It allows us to see the current amount of voting power the delegate has. Note that the token owner is listed as their own delegate by default.

The checkpoints map is updated at each token transfer and each change of delegation. This means that by accessing the last checkpoint before the voting has started we can see how many tokens the delegate had delegated to them.

Given a past block number, the voting power of an address at that block can be obtained via the following function:

function getPriorVotes(address account, uint256 blockNumber) public view returns (uint96)

This function has a loop that repeats \(O(log_2(nCheckpoints))\) times on average, as every iteration cuts down the range being searched by 2. This means that as the number of checkpoints associated with an address incrases, this function will also slowly consume more gas if called from within the smart contract.

Storage Proof of Voting Power

Given an election, the voting power of the account is the amount of voting tokens the address had delegated to it just before the election.

We can generate a storage proof based on the Ethereum state at the block when the election has started. Assume we wish to prove that address acct had Z voting power at that block. We find the value Y of numCheckpoints[acct] at that block, which is the number of checkpoints for that account. We then require the following storage proofs:

• Proof of the correct number of checkpoints: numCheckpoints[acct] == Y
• Proof of the voting power: checkpoints[acct][Y-1].votes == Z

Only these two storage proofs are required, independently of the amount of voting power.

Storage Trie Depth

On Ethereum, every contract has a Merkle Pratricia Trie that stores the contract’s data. The trie depth corresponds to the number of Keccak hashes that has to be computed in order to generate an Ethereum storage proof in Noir.

By 2 Mar 2023, the depth of storageProof (EIP-1186 Merkle proof) fetched for owners and delegates from the Nouns contract are as follows:

Most of the proofs are 4-5 levels deep and are at most 7 levels deep, with the root element being shared between all. The elements can be pretty large themselves (~533bytes) for the larger ones.

With minimal tooling for computing the keys for kv store, it's currently possible to get all the proofs via requests to Infura in <15 seconds on a slow to basic connection.