An NFT with Huff, using polynomials over a finite field of the largest 20-byte prime, instead of mappings.

huffd1 is a non-fungible token implementation in Huff, where the ownership of a token is given by the evaluation of a polynomial $P(x)$, defined over the finite field of prime order $p = 2^{160} - 47$, the largest 160-bit prime:

$$ p = \mathtt{0xff}\ldots\mathtt{ffd1} $$

Notice the final hexadecimals, which is where the name of the project comes from. The degree of the polynomial is equal to total supply minus one, so for $n$ tokens we have a polynomial $P$:

$$ P \in \mathbb{F}_{\mathtt{0xff}\ldots\mathtt{ffd1}}^{n-1}[X] $$

At contract deployment, all tokens are owned by the contract owner; and as a result the main polynomial is simply a constant polynomial equal to the owner address $P(x) = \mathtt{owner}$.

To transfer a token, we simply have to find the difference between the sender and recipient addresses, multiply that value with the basis polynomial of the respective token, and add that to the main polynomial. See transfer subsection below for more details.

The stack comments are written in reverse order:

opcode // [top-N, ..., top-1, top]
pop    // [top-N, ..., top-1]
0x01   // [top-N, ..., top-1, 0x01]

unlike the usual order described in the Style Guide.

Let's describe each function of huffd1:

To find the owner of a token $t$, simply evaluate $P(t)$ and the result will be a 160-bit number corresponding to the owner address. We use Horner's method to efficiently evaluate our polynomial.

Initially, all tokens are owned by the contract deployer, which can be represented by the constant polynomial that is equal to the owner address.

To find the balance of an address, iterate over all tokens and call ownerOf, counting the number of matching addresses along the way.

To transfer a token $t$ from address $a \to b$, update $P(x)$ to be $P(x) + L_t(x)(b - a)$. Here, $L_t(x)$ is the Lagrange basis of the token, defined as a polynomial that is equal to 1 at $t$ and 0 on all other points. These polynomials are computed before deploying the contract, and are stored within the contract bytecode.

We have a Sage script that can export the basis polynomials, one for each token id, as a codetable where the coefficients of each polynomial are concatenated.

// basis polynomials coefficients
#define table Basis {
  // 0x...
}

// number of tokens
#define constant TOTAL_SUPPLY = 0xa

// number of bytes per coefficient
#define constant COEFF_SIZE = 0x14

// order of the finite field
#define constant ORDER = 0xffffffffffffffffffffffffffffffffffffffd1

Using these, we can load polynomials from the code table.

The codetable grows pretty large for 20-byte coefficient size, and may easily get past the 24KB maximum contract size. To be more specific, for coefficient size S and total supply N, you will have N polynomials with N coefficients each, with S bytes per coefficient, resulting in total number of bytes of N * N * S.

This operation results in multiplying the coefficients of $L_t(x)$ with $(b - a)$ which we will do via MULMOD, and afterwards summation of the coefficients of $P(x)$ and the resulting polynomial from previous step, using ADDMOD.

Also note that $-a$ is obtained by $p-a$ where $p$ is the order of the finite field.

Returns the string "Huffd1".

Returns the string "FFD1".

You can use the following commands for testing.

# run all tests
forge t -vvv

# run a specific test
forge t -vvv --mc Polynomial
forge t -vvv --mc Huffd1

I use -vvv to see reverts in detail.

• This project was done for the Huff hackathon!

• This is a very inefficient contract both in contract size and gas usage, and was done mostly for the nerd-snipability factors of using polynomials instead of mappings.

• We can implement approvals with another polynomial too, but time did not permit. Also, there are many optimizations to do in many different places within the code.

• We could also use $p = 2^{160} + 7$, but I wanted all coefficients to be strictly 160-bits, which is not the case with that prime. In fact, the concept works for any prime order, but we would like to use an order that can fit almost all the addresses while being as large as an address.

• Maybe use foundry FFI to generate the basis polynomials during contract creation?