[Proposal] Program Registry

[raychu86]

💥 Proposal

This proposal documents an iterative process towards introducing a program registry to store programs on-chain as part of the network consensus mechanism.

There are a few key questions:

1. What type of data structure should the programs be stored in? Merkle Tree? Merkle Trie?
2. What updates to the Inner Circuit will be required?
   • Will require checking the inclusion of the programs in the merkle tree? New programs vs existing programs?
3. Is there a need for a new transaction type for storing programs?
   • Optional fields in transactions? i.e. program_registry_root
4. What is the payment mechanism for storing program?
   • A straw-man approach is to have miners enforce a fee requirement based on the size of the program being stored.
   • Alternative solutions may enforce time requirements for payments.

An example for each program stored on-chain:

pub struct Program {
    // The ID of the program.
    pub id: MerkleTreeDigest<C::ProgramCircuitTreeParameters>,
    // A description or name of the program (specified by the deployer)
    pub description: [u8; 32],
    // The circuit/program represented as an IR.
    pub circuit: <IR>,
}

[apruden2008]

When will we know if the Inner Circuit needs to be modified? Asking since I'm assuming this may affect the timeline of the inner setup. cc @howardwu