PoC: Investigate state transition proofs

[rymnc]

Problem

The rln-contract is stateless, i.e we do not store the whole tree onchain, but we only store the commitments, and emit them as events for users to sync from scratch.

For users who just want to verify proofs, they have to sync the whole tree to know the current root

Proposed solution

We make use of a "merkle state transition proof" where we accept a merkle proof of the state before making an insertion, and the merkle proof of the state after the insertion. This will allow having the root of the new state onchain, while maintaining lower gas costs than having the whole tree onchain.

The proposed state transition circuit is as follows -

pragma circom 2.1.0;

include "./utils.circom";
include "../node_modules/circomlib/circuits/poseidon.circom";
include "../node_modules/circomlib/circuits/comparators.circom";

template RLNStateTransition(DEPTH, LIMIT_BIT_SIZE) {
    // Private signals
    signal input identitySecret;
    signal input userMessageLimit;
    signal input newPathElements[DEPTH];
    signal input newIdentityPathIndex[DEPTH];

    // Public signals
    signal input previousRoot;
    signal input previousRateCommitment;
    signal input pathElements[DEPTH];
    signal input identityPathIndex[DEPTH];

    // Outputs
    signal output newRoot;
    signal output rateCommitment;

    signal identityCommitment <== Poseidon(1)([identitySecret]);
    rateCommitment <== Poseidon(2)([identityCommitment, userMessageLimit]);

    newRoot <== MerkleTreeInclusionProof(DEPTH)(rateCommitment, identityPathIndex, pathElements);
    // old root calculation
    signal oldRoot <== MerkleTreeInclusionProof(DEPTH)(previousRateCommitment, identityPathIndex, pathElements);

    // ensures the old root != new root
    signal isEq <== IsEqual()([oldRoot, newRoot]);
    isEq === 0;
}

component main { public [previousRoot, pathElements, identityPathIndex] } = RLNStateTransition(20, 16);

[rymnc]

As per internal discussion, this feature will not be pursued since only one state transition proof may be accepted per block, and it would require an indexer to accept and aggregate registrations to the membership set.