Handle invalid Addresses

[nventuro]

#8969 will require computing the Point that backs an AztecAddress from its x coordinate, but the x coordinate might not be in the curve in the first place. If this happens, then we won't be able to do elliptic curve math on it, so we need an escape hatch.

Since we define addresses as values that represent the x coordinate of a point in the curve, these address values are truly invalid, and cannot be used for anything. No decryption can be done with them, nor can they do things such as nullify notes since they won't be able to compute this invalid x coord. Therefore, it is fine to simply skip whatever action needed to be done to avoid King of the Hill attack vectors. For example, in the case of sending a note we should not send it at all.

This means that we should likely change AztecAddress::to_point so that it results something like an Option, to handle the invalid derivation scenario.

[iAmMichaelConnor]

Some hopefully helpful theory:

For grumpkin, $y^2 = x^3 - 17$. There exist values $x \in \mathbb{F}$ for which no $y$ satisfies this equation. What does that mean? If we take some $x$, and we compute $t = x^3 - 17$, then $\sqrt{t}$ does not exist in $\mathbb{F}$.

Why don't square roots always exist in prime finite fields? They just don't.
Take $\mathbb{F}_7 = {0, 1, 2, 3, 4, 5, 6}$. $0^2 = 0$, $1^2 = 1$, $2^2 = 4$, $3^2 = 9 = 2$, $4^2 = 16 = 2$, $5^2 = 25 = 4$, $6^2 = 36 = 1$. None of the answers were 3 or 5, so 3 and 5 have no square root in $\mathbb{F}_7$.
So in our context, if we shrunk our field to $\mathbb{F}_7$, and someone said "My address is 3", then for $x = 3$, $x^3 - 17 = 27 - 17 = 10 = 3$, and we just showed that $3$ has no square root in $\mathbb{F}_7$, so address=3 is an invalid address in that finite field.

In a circuit, how can we efficiently demonstrate that an address $x$ is invalid? We compute $t = x^3 - 17$ and then we pass $t$ into the sqrt function below to check whether it has a square root, and return it if it does.

This code (from another project I was working on) should do it:

global KNOWN_NON_RESIDUE = 5;

unconstrained fn __sqrt(x: Field) -> (bool, Field) {
    let is_sq = std::ec::is_square(x);
    let mut maybe_sqrt = 0;
    if is_sq {
        maybe_sqrt = std::ec::sqrt(x);
        assert(maybe_sqrt * maybe_sqrt == x); // to catch bugs
    } else {
        // If x a non-residue, x * KNOWN_NON_RESIDUE will be a residue, since -1 * -1 = 1 when considering their legendre symbols.
        let demo_not_square = x * KNOWN_NON_RESIDUE;
        maybe_sqrt = std::ec::sqrt(demo_not_square);
        assert(maybe_sqrt * maybe_sqrt == demo_not_square); // to catch bugs
    }
    (is_sq, maybe_sqrt)
}

fn sqrt(x: Field) -> (bool, Field) {
    let (is_sq, maybe_sqrt) = __sqrt(x);
    let mut out: (bool, Field) = (false, 0);
    if is_sq {
        let sqrt = maybe_sqrt;
        assert(sqrt * sqrt == x);
        out = (true, sqrt);
    } else {
        let not_sqrt = maybe_sqrt;
        let demo_x_not_square = x * KNOWN_NON_RESIDUE;
        // Given that this is square, it implies x is not square.
        assert(not_sqrt * not_sqrt == demo_x_not_square);
    }
    out
}

Saying a value $t \in \mathbb{F}$ is a "quadratic non residue" is basically a mathsy way of saying "$t$ does not have a square root". Conversely, saying a value "is a quadratic residue" effectively means it does have a square root.

If you take a known non-residue (5 is a non-residue in the Noir Field), then:

"Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue."

In other words:
If we learn that $t$ is square, from the unconstrained function, then we can provide its square root to the constrained function.
If we learn that $t$ is not a square, from the unconstrained function, then we cannot provide its square root. But we can compute t * KNOWN_NON_RESIDUE, the result of which, according to the rule above, is a residue. So we can provide the square root of t * KNOWN_NON_RESIDUE as a way of demonstrating that $t$ has no square root in this case!