# Navigators Season 3: Starter Grants Proposal Template

## Overview

This proposal focuses on an **operation-wise** approach to designing and implementing a matrix operations library in o1js[^3][^6], enabling advanced zero-knowledge (ZK) computations for cryptographic circuits. We provide robust and efficient methods for a range of fundamental matrix operations.

## Objectives

1. Build a specialized o1js matrix library around finite-field arithmetic.
2. Deliver essential matrix operations—addition, multiplication, inversion, transpose, determinant, element-wise products, trace, and adjoint.
3. Integrate zero-knowledge proof compatibility and developer-friendly APIs.
4. Provide tests, benchmarks, and documentation to support real-world cryptographic use cases.
5. Research o1js, Protokit, and other Mina-related frameworks to ensure seamless integration.

## Operation-Wise Implementation Plan

### Matrix Addition
- Create functions for element-wise addition, ensuring dimension validation.
- Implement modular addition via Field additions in o1js to guarantee consistency for ZK computations.

### Matrix Subtraction
- Mirror the approach used in addition.
- Handle negative values with finite-field logic to keep proofs consistent.

### Matrix Multiplication
1. **Standard Matrix Multiplication**
- Multiply two matrices using repeated dot products and partial summations.

2. **Hadamard (Element-Wise) Product**
- Allow element-wise multiplication for equally sized matrices.
- Useful in feature weighting and image masking, aligned with zero-knowledge proofs[^7].

### Matrix Inversion
- Implement an algorithm that computes the inverse (e.g., Gaussian elimination or adjoint-based) under finite-field constraints.
- Provide safe-fail conditions when the matrix is not invertible.

### Matrix Determinant
- Compute the determinant of square matrices with a suitable factorization approach.
- Ensure the method supports typical ZK usage by balancing performance and constraint counts.

### Matrix Transpose
- Build a lightweight transpose function to flip dimensions.
- Useful in higher-level operations for rearranging data in advanced proofs.

### Matrix Trace
- Calculate the trace by summing the diagonal elements of a square matrix under modular arithmetic[^5].
- Enable verification or inclusion in proof statements for trace-based constraints.

### Matrix Adjoint (Adjugate)
- Implement adjoint computation via cofactors and matrix transposition[^3].
- Incorporate a streamlined path for matrix inversion by dividing the adjoint by the determinant when feasible.

### Block Matrix Operations
- Facilitate partitioning large matrices into sub-blocks for parallel operations.
- Integrate block-based multiplication to optimize performance in select proof scenarios.

## Zero-Knowledge Proof Compatibility
- Embed transformations that enable in-circuit verification of specific operations (e.g., checking if matrix multiplication or inversion is correct).
- Provide pluggable proof checks to allow developers to selectively prove or verify steps like trace or determinant evaluations.

## Grant Project Outline

| Milestone | Description | Deliverable |
|:-------------------------|:----------------------------------------------------------------------------------------------|:-----------------------------------------------------------|
| Research & Specification | Investigate o1js, Protokit, and Mina frameworks; finalize API design and confirm field ops | Detailed spec and test plan |
| Core Module Completion | Implement operations: Add, Subtract, Transpose, Basic Multiply | Beta package release with initial tests |
| Advanced Operations | Extend to Inversion, Determinant, Block Ops, Hadamard, Trace, Adjoint | Full suite of operations using native field methods |
| ZK Proof Integration | Integrate proof capabilities; measure constraint usage | Demo with in-circuit matrix checks (multiplication, trace, adjoint) |
| Documentation & Outreach | Publish docs, examples, and usage tutorials | GitHub repository, hackmd tutorials |

## Budget and Timeline

- **Duration**: 1 month total, aligned with the milestones listed above.
- **Budget**: 15,000 MINA
- **Cost Estimates**:
- Development & Testing: ~40%
- Documentation & Education: ~25%
- Research & Proof Integration: ~25%
- Miscellaneous (project management, overhead): ~10%

## Potential Impact

- **Expanded ZK Ecosystem**: Smoother integration of matrix operations for Mina Protocol or other o1js frameworks[^6].
- **Developer Adoption**: Straightforward APIs mirroring established libraries[^1][^2].
- **Educational Resource**: Demonstrates best practices for field-based linear algebra in cryptographic settings.

## Conclusion

This proposal structures the O1JS Matrix Operations Library around individual operations—streamlining addition, multiplication, trace, adjoint, and more. By adopting finite-field arithmetic methods[^3], it ensures that each operation is both proof-friendly and resistant to typical numeric issues. Coupled with a clear set of APIs, testing frameworks, performance benchmarks, and dedicated research of o1js, Protokit, and other Mina frameworks, our solution will form a critical foundation for zero-knowledge proofs involving linear algebraic computations.

## Team information
- **Vishal Koolkarni**
- Have an experience in o1js
- Worked at ZK startup more than 1 year
- Have done several grants in EF(Ethereum Foundation)

- **Changmin Cho**
- Have an experience in ZKML (Ethcon Korea 2023)
- Have done several grants in EF(Ethereum Foundation), one of them with Vishal
- Interested in Algebraic Topology

- **Yeri Kim**
- Have done with various projects related to Rust language, OpenBSD Kernel
- Have done with various projects with embedded software (e.g. Wearable devices)
- Currently learning ZK, interested in embedded software engineering

[^1]: https://github.com/lichao-wu9/ML-Matrix_JS
[^2]: https://github.com/mljs/matrix
[^3]: https://docs.minaprotocol.com/zkapps/o1js/foreign-fields
[^5]: https://www.geeksforgeeks.org/trace-of-a-matrix/
[^6]: https://docs.minaprotocol.com/zkapps/o1js/basic-concepts
[^7]: https://en.wikipedia.org/wiki/Hadamard_product_(matrices)