Integrate Falcon DSA into Miden VM

[Al-Kindi-0]

As the Falcon DSA is practically done #1000, we need to add some support for it to be useful. Things are still not clear but I think that we should think about supporting the following flow:

1. Given as input, via the operand stack, a digest of a public key PK and a digest of a message MSG, the VM receives via the advice provider the pre-image of PK, which is the coefficients of a polynomial h.
2. A signature composed of a nonce NONCE and a signature represented as a polynomial s2, also via the advice provider.
3. A polynomial pi representing the product of h and s2 in $\mathbb{Z}_Q[x]$ where $Q$ is the Miden prime.

The MASM code implementing the verification procedure will then go one to:

1. Check that h hashes to PK.
2. Compute the polynomial c that is the hash-to-point of NONCE || MSG using RPO.
3. Check that pi is indeed the product of h and s2 in $\mathbb{Z}_Q[x]$.

The main question, I believe, is how to accommodate the above flow using the current infrastructure or whether there is a need for something more.

[bobbinth]

Here is my very preliminary thinking on this:

First, we'd need to introduce a new advice injector - maybe something like adv.push_falconsig (or maybe adv.push_sig.rpofalcon512). This injector would put the values of $h$ and $s_2$ onto the advice stack.

Second, we'd need to modify the advice provider to help with signature generation. One option for this is to add falcon_sign() method to the AdviceProvider trait. This method could look as follows:

fn falcon_sign(&self, pub_key: Word, msg: Word) -> Result<Vec<Felt>, ExecutionError>

Where the returned vector would be a concatenation of $h$ and $s_2$.

The default implementation of this method could panic or maybe try to look up the relevant private key in the advice map and generate the signature. A more "production-grade" implementation would probably override this method so that private key is not stored in the advice provider.

One question with this approach is whether having a method specifically for Falcon signature is too "narrow". In the future we will probably have other signature schemes, and maybe it makes sense to make this a bit more general from the start. For example, the method could be something like:

fn sign(&self, alg: SignatureKind, pub_key: Word, msg: Word) -> Result<Vec<Felt>, ExecutionError>

Where, SignatureKind could be:

pub enum SignatureKind {
    RpoFalcon512,
}

[Al-Kindi-0]

Makes sense!
One thing that is still not clear to me is how would the scenario where the VM requests a signature from a 3rd party work in the above.

[bobbinth]

I was thinking that in such cases we'd need to provide a specialized implementation of the advice provider which overrides the sign (or falcon_sign) method.

For example, let's say we are implementing a wallet which needs to make a call to some external component (via an RPC or something else) to generate a signature. We'd create a new AdviceProvider implementation in which we'd replace the default implementation of sign with an implementation which makes a call to this external component according to the interfaces this component exposes.

[Al-Kindi-0]

That clarifies things, thank you!

[bobbinth]

Closed by #1068.