Thin down stdlib to the minimum necessary and move code into external libraries.

[TomAFrench]

Problem

With various grant projects we've set the final step as "acceptance into the Noir standard library", this is problematic for a couple of reasons:

• It signals a transfer of "ownership" over the code from the grantee to the Noir language team.
  • These Noir developers are the best placed people to support, maintain and extend these libraries so we don't want to give the impression that we're "taking away" their code. They wrote it so they should be able to keep their name on it.
  • Similarly we can't / don't want to force a grantee to maintain a library if they don't want to, but a new maintainer's barrier to entry when forking an external library is much lower than making PRs to the stdlib.
• It prevents any breaking changes to these libraries without a breaking change to the standard library (and then to Noir itself) @kevaundray shared this discussion thread on a fat vs thin rust standard library.
• We're artificially restricting the number of Noir repositories in the wild, making Noir look like a less used language than it is.

Proposed solution

We should restrict the usage of the stdlib to only be the most common of functions and functions which are required to be in the stdlib (e.g. black box function definitions). Everything else should be spun out into libraries which have their own separate versioning.

• merkle.nr can be spun out into noir-lang/merkle (I've pushed an initial version of this to https://github.com/TomAFrench/noir-merkle which can be transferred to the org)
• ~~sha256.nr~~, sha512.nr, hash/poseidon.nr should be broken out into a noir-lang/hashes monorepo similar to https://github.com/RustCrypto/hashes.
  • This is complicated a little by some of the hash implementations in the stdlib being alternatives for black box functions, e.g. sha256. These fallback implementations would have to stay inside the standard library imo.
  • This also requires us to support git dependencies where the noir package doesn't live at the repository root. We'll then either have to allow specifying a relative path in a git dependency or preferably implement #794.
• ec.nr can spun out into noir-lang/elliptic-curves.

Pushing out these functions from the stdlib forces us to deal with remote dependencies much more than when everything is in the stdlib. This is a good opportunity for dogfooding and allows us to strengthen our integration tests.

Alternatives considered

We can retain these functions in the standard library and have it grow over time (continuously?). This will likely be a backwards compatibility nightmare in future.

Additional context

No response

Submission Checklist

• [X] Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

### Tasks
- [ ] https://github.com/noir-lang/noir/issues/4857
- [ ] https://github.com/noir-lang/noir/issues/4845
- [ ] https://github.com/noir-lang/noir/issues/4858

[kevaundray]

This is complicated a little by some of the hash implementations in the stdlib being alternatives for black box functions, e.g. sha256. These fallback implementations would have to stay inside the standard library imo.

I think we should figure out a better way to do this because:

• We have fallback mechanisms in noir and in acvm (Not the end of the world)
• The fallback mechanism makes it such that we cannot compile a Noir program without a backend (since we need to know what exactly should have fallbacks and replce them if we can)
• There will be functions like poseidon whom may live in the noir-lang/hashes for now, but will be moved into the stdlib when we make poseidon a hash function.

The last point is undesirable since it means that the stdlib can still grow over time based on the opcodes that ACIR introduces.

The second point could probably be mitigated by pre-compiling the fallback functions and then once Noir has compiled ACIR, we then have a pass which replaces the opcodes which cannot be supported. A middle-ground would be to somehow only introduce the concept of fallbacks when you get to the SSA stage.

In general, I'd like for us to not need to maintain any of these fallback functions and have the community be responsible for this. The only thing we maintain are simple functions which are useful for a range of context's and stable.

One solution for moving these out is to allow users to override the fallbacks by maybe passing in --override-sha256 or give the user the ability to conditional compile in the Noir source code.

[TomAFrench]

In general, I'd like for us to not need to maintain any of these fallback functions and have the community be responsible for this. The only thing we maintain are simple functions which are useful for a range of context's and stable.

Agreed, it's definitely suboptimal that adding new blackbox functions results in the stdlib growing.

I don't think that we need to be concerned with precompiling fallback ACIR for this issue however. It's just an issue of communicating what code we insert in place of the bb function but that can happen either in the frontend or inside the ACVM compiler.

If we we're going to fallback to functions which are implemented outside of the stdlib then it should be done by the user themselves rather than having a canonical fallback. Having a stdlib with a dependency tree is weird imo (why I favoured keeping them inside the stdlib) so having the user specify it themselves makes it explicit (along with the benefit of avoiding downloading a bunch of unnecessary dependencies).

[kevaundray]

In general, I'd like for us to not need to maintain any of these fallback functions and have the community be responsible for this. The only thing we maintain are simple functions which are useful for a range of context's and stable.

Agreed, it's definitely suboptimal that adding new blackbox functions results in the stdlib growing.

I don't think that we need to be concerned with precompiling fallback ACIR for this issue however. It's just an issue of communicating what code we insert in place of the bb function but that can happen either in the frontend or inside the ACVM compiler.

If we we're going to fallback to functions which are implemented outside of the stdlib then it should be done by the user themselves rather than having a canonical fallback. Having a stdlib with a dependency tree is weird imo so having the user specify it themselves makes it explicit (along with the benefit of avoiding downloading a bunch of unnecessary dependencies).

Yeah if it's done on the frontend then having the user do it explicitly is a good strategy. I like that method since it means we do absolutely nothing and the user can replace the black box function with whatever they choose; could even replace it with a function which does nothing.

^ A variant of this feature may be able to stand on it own merit.

The advantage of having acvm do it, is that different frontends can use it and other functions placed in acvm-stdlib, and there will be one place where we do fallbacks

[joss-aztec]

Relatedly, I've been profiling the parser a little, and the inclusion of noir_stdlib/src/hash/poseidon/bn254/consts.nr alone adds over 2 seconds to the compile time of a program. (I suspect we could be representing field literals more efficiently.)

[TomAFrench]

Note that we've removed the concept of fallback functions so we can push forward on this a little more easily.