Detailed Technical Workflow for summa MST

[yagnadeepxo]

Summary

This issue outlines an advanced technical description of how our zero-knowledge proof circuit is initialized, processes data, and ultimately exposes certain values as public inputs. It aims to provide a clear, detailed understanding of the procedures and cryptographic mechanisms involved.

Initialization Phase

The circuit begins with setup of its core components: MerkleSumTreeChip, PoseidonChip, and RangeCheckChip. Each chip is configured to use specific columns (advice, fixed, selector) based on their operational needs. This initial step ensures that the foundation is laid for secure and accurate cryptographic processing.

Witness Assignment Protocol

During this phase, the circuit assigns witness values (like usernames and balances) to advice columns. This is a critical step as it prepares the data for the cryptographic computations that follow, ensuring that user inputs are correctly integrated into the circuit's workflow.

Cryptographic Hash Computations

Using the PoseidonChip, the circuit performs hash calculations necessary for building the Merkle sum tree. The Poseidon hash function takes inputs from advice columns and, if needed, uses fixed columns for the constants. This stage is essential for maintaining the cryptographic integrity of the operations.

Merkle Tree Operational Mechanics

The circuit executes specific operations for the Merkle sum tree, including swapping sibling hashes based on swap bits (using selector columns for conditional logic) and summing balances at each level. These operations are crucial for the correct structuring and functionality of the Merkle sum tree.

Range Check Implementations

Before or after hashing, the circuit conducts range checks on data, particularly balances, with the RangeCheckChip. This step is vital for ensuring data validity. Selector columns might be used to conditionally enable these checks, adding a layer of security and data integrity to the circuit.

Preparation and Exposure of Public Inputs

After completing all computations, the circuit prepares the final hash values (like the root hash of the Merkle sum tree) to be exposed as public inputs. This involves carefully placing these values into specific columns designated for public inputs, which is crucial for the proof's verification process. This step allows the verifier to check the proof's validity without accessing the underlying data directly.

Optimizations

Batch Hashing with SIMD

When computing hashes, especially for the nodes of a Merkle tree, SIMD(Single Instruction Multiple Data) can process multiple hash inputs simultaneously, reducing the overall computation time.

Parallel Processing

Leverage Rust's concurrency model to perform parallel processing of independent tasks using Rayon, such as Merkle tree leaf computations or range checks.