owned this note
owned this note
Published
Linked with GitHub
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:
```rust!
ownerOf[token_id] == account
_delegates[account] == 0x0
```
(1) if the a `delegator` has delegated his/her token to an `account`, prove that at the correct block:
```rust!
ownerOf[token_id] == delegator
_delegates[delegator] == account
```
# Contract Review
Nouns' [Token Contract](https://etherscan.io/token/0x9c8ff314c9bc7f6e59a9d9225fb22946427edc03#code) implemented the ERC721 standard (aka NFT) with slight modification to allow voting.
In particular, they use the modified version of [ERC721Checkpointable](https://github.com/compound-finance/compound-protocol/blob/ae4388e780a8d596d97619d9704a931a2752c2bc/contracts/Governance/Comp.sol) from Compound Lab's to generate checkpoints of token balance. This allows their token contract to have balance history, much like [MiniMi](https://etherscan.io/token/0x9c8ff314c9bc7f6e59a9d9225fb22946427edc03#code) did for ERC20 standard.
The contract maintains the current map between delegators and delegates via the `_delegates`mapping. It is not possible to delegate individual tokens, an entry in that mapping means that all NFTs held are delegated.
```solidity!
/// @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:
```solidity!
/// @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:
```solidity!
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:
![](https://cdn.discordapp.com/attachments/1074682696292372551/1080874037804277890/image.png)
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.