Restrict usage of unconstrained functions to within unsafe blocks

[TomAFrench]

Problem

It's currently not obvious when we're calling an unconstrained function (and introducing unconstrained values into the circuit). It's then quite difficult to rule out that any under-constrained bugs exist as any function call is a potential source.

This would be easier if we could limit the potential surface for this class of bugs such that Noir developers only need to worry about them when dealing with unconstrained functions and the compiler will flag up when this is the case.

Potential Solution

Noir code which makes use of unconstrained functions can be thought of as analogous to unsafe Rust. In Rust, unsafe blocks can be used to temporarily allow breaking some of the compiler's guarantees around memory safety before passing a value back to safe Rust which can be handled similarly to any other safe value (assuming that the code ran in the unsafe block is correct).

If we map this concept over to Noir, we can temporarily break the compiler guarantee that the prover will be constrained to follow the specified logic. Like in unsafe Rust, if we were to write entirely safe code in an unsafe block then it's equivalent to if the block was safe, so an unsafe block in Noir should still lay down constraints except it should also allow introducing unsafe values to the circuit (through unconstrained function calls).

An example of how it can be used

fn is_valid_impl(context: &mut PrivateContext, message_field: Field) -> pub bool {
    // Load public key from storage
    let storage = Storage::init(Context::private(context));
    let public_key = storage.public_key.get_note();

    // Load auth witness
    let witness: [Field; 64] = get_auth_witness(message_field);
    let mut signature: [u8; 64] = [0; 64];
    for i in 0..64 {
        signature[i] = witness[i] as u8;
    }

    // Verify payload signature using Ethereum's signing scheme
    // Note that noir expects the hash of the message/challenge as input to the ECDSA verification.
    let hashed_message: [u8; 32] = std::hash::sha256(message_field.to_be_bytes(32));
    let verification = std::ecdsa_secp256k1::verify_signature(public_key.x, public_key.y, signature, hashed_message);
    assert(verification == true);

    true
}

With the addition of unsafe blocks this could look something like:

fn is_valid_impl(context: &mut PrivateContext, message_field: Field) -> pub bool {
    // Load public key from storage
    let storage = Storage::init(Context::private(context));
    let public_key = storage.public_key.get_note();

    // Note that noir expects the hash of the message/challenge as input to the ECDSA verification.
    let hashed_message: [u8; 32] = std::hash::sha256(message_field.to_be_bytes(32));

    unsafe {
        // Safety: Prover must provide an ECDSA signature over `hashed_message` which matches the stored public key.
        
        // Load auth witness
        let witness: [Field; 64] = get_auth_witness(message_field);
        let mut signature: [u8; 64] = [0; 64];
        for i in 0..64 {
            signature[i] = witness[i] as u8;
        }

        // Verify payload signature using Ethereum's signing scheme
        let verification = std::ecdsa_secp256k1::verify_signature(public_key.x, public_key.y, signature, hashed_message);
        assert(verification == true);
    };

    true
}

Similarly to in Rust we could add a lint which requires that unsafe blocks must contain a safety comment which explains why the code is sound.

---

I've got a messy implementation of this in #4429 which adds an unsafe flag to blocks and then during type checking we throw an error if we perform an unconstrained function call inside a constrained function but outside of an unsafe block.

[TomAFrench]

cc @nventuro and @spalladino as you two were interested in this feature during the offsite.

[spalladino]

Thanks for exploring this Tom! unsafe looks nice, but it feels too coarse, as in a lot of things can happen within an unsafe block. What I had in mind was something at the variable level, like:

fn is_valid_impl(context: &mut PrivateContext, message_field: Field) -> pub bool {
    // Load public key from storage
    let storage = Storage::init(Context::private(context));
    let public_key = storage.public_key.get_note();

    // Load auth witness, assigned to an unconstrained variable, since the return value of get_auth_witness is unconstrained.
    let unconstrained witness: [Field; 64] = get_auth_witness(message_field);
    // Since we are assigning from an unconstrained variable, signature needs to be unconstrained as well.
    let mut unconstrained signature: [u8; 64] = [0; 64];
    for i in 0..64 {
        signature[i] = witness[i] as u8;
    }

    let hashed_message: [u8; 32] = std::hash::sha256(message_field.to_be_bytes(32));
    // verify_signature should accept an "unconstrained" signature variable and return a constrained verification result
    let verification = std::ecdsa_secp256k1::verify_signature(public_key.x, public_key.y, signature, hashed_message);
    
    // The return value from the function needs to be a constrained variable, since it's not declare as unconstrained in the return type
    verification
}

It requires more effort, but I think it can help in identifying exactly which variables are requiring constraining, and which methods can do that constraining.

However, I'm not sure if it really works: how do you define when you have properly "constrained" something? For instance, if you load a set of notes from the user DB in an Aztec contract, what do you need to do to constrain them? In principle, you should check that: 1) they have a corresponding commitment in the note hash tree, 2) they have not been nullified, 3) they belong to the current contract, 4) they match the filters you used when requesting them. So when do you flag the set of notes returned as "constrained"? When all 4 are checked? Sorry, I ended up rambling as usual.

[TomAFrench]

I think it can help in identifying exactly which variables are requiring constraining, and which methods can do that constraining.
...
how do you define when you have properly "constrained" something?

This is my main concern on having something that's scoped to variables (and so is interwoven with safe variables). Determining when something is safe requires too much knowledge about the user's intentions for the language to do reliably.

For a simple example, we have U128 division. We receive unconstrained q and r and then constrain them against a and b so they should be safe right?

 fn div(self: Self, b: U128) -> U128 {
        let (q,r) = self.unconstrained_div(b);
        let a = b * q + r;
        assert_eq(self, a);
        q
    }

Except I've removed the assert(r < b) constraint which makes this safe. I don't think we then can really ever automatically determine that a value has been properly constrained and so can't list certain functions as safe like you have for verify_signature.

[TomAFrench]

I think the best we can do is to force a user to highlight that they're bringing in unsafe values and encourage them to group together a comment explaining why it's being used in a safe way along with any constraints which enforce this.

[jfecher]

adds an unsafe flag to blocks and then during type checking we throw an error if we perform an unconstrained function call inside a constrained function but outside of an unsafe block.

Do we have a similar check when using higher-order functions? If we want to properly track these I think we may need to separate the types of constrained and unconstrained functions.

[spalladino]

I think the best we can do is to force a user to highlight that they're bringing in unsafe values and encourage them to group together a comment explaining why it's being used in a safe way along with any constraints which enforce this.

Yep, I think you're right, tainting doesn't fit the bill here.

[TomAFrench]

Hmm, I hadn't really considered this. I'd expect that the behaviour in my draft currently is that passing an unconstrained function into a hof would fail unless the hof includes an unsafe block when it's actually called.

I can make sure to add some test cases to ensure this is behaving how we want it to.

[fcarreiro]

Would it make sense to do it at the variable level, but not try to detect constraining, but ask the dev to explicitly use let a_prime = a.has_been_constrained() and use that new variable which now doesn't have the marking "unconstrained"?

[nventuro]

Would it make sense to do it at the variable level, but not try to detect constraining, but ask the dev to explicitly use let a_prime = a.has_been_constrained() and use that new variable which now doesn't have the marking "unconstrained"?

So unconstrained functions would return unconstrained values, which can then be passed to regular contrained functions and be converted to constrained values?

[TomAFrench]

Would it make sense to do it at the variable level, but not try to detect constraining, but ask the dev to explicitly use let a_prime = a.has_been_constrained() and use that new variable which now doesn't have the marking "unconstrained"?

This can be done entirely in user code, aztec could implement the below struct and use it as a return type for its unconstrained functions.

struct Unconstrained<T> {
    value: T
}

impl<T> Unconstrained<T> {
    fn new(value: T) -> Self {
        Unconstrained { value }
    }

    fn mark_safe() -> T {
        self.value
    }
}

If we were to go this route then I'd want to see it in usage to see the effects before considering adding it into the language by default.

[spalladino]

Legends <3