Feat: Substring Match Template

[shreyas-londhe]

Description

This PR introduces a new circom template called SubstringMatch that verifies if a given substring exists within a larger string at a specified index.

The SubstringMatch template uses a Random Linear Combination (RLC) approach to perform efficient substring comparisons. This method allows for constant-time verification regardless of the input string length, making it suitable for use in zk-SNARKs.

Type of Change

• [x] New feature (non-breaking change which adds functionality)
• [x] This change requires a documentation update

Functionality and Usage Example

The SubstringMatch template takes the following parameters and inputs:

• Parameters:

  • maxLength: The maximum length of the input string
  • maxSubstringLength: The maximum length of the substring to be matched

• Inputs:

  • in: An array of ASCII values representing the input string
  • startIndex: The starting index of the substring in the input string
  • revealedString: An array of ASCII values representing the substring to be matched
  • r: A random value used for the RLC calculation

• Output:

  • isValid: A signal that is 1 if the substring matches at the given index, 0 otherwise

Example usage:

pragma circom 2.1.6;

include "substring-match.circom";

template Example() {
  var maxLength = 100;
  var maxSubstringLength = 20;
  
  component substringMatch = SubstringMatch(maxLength, maxSubstringLength);
  
  // Input string: "Hello, World!"
  substringMatch.in <== [72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33, 0, 0, ...]; // Padded with zeros
  
  // Start index: 7 (position of "W")
  substringMatch.startIndex <== 7;
  
  // Substring to match: "World"
  substringMatch.revealedString <== [87, 111, 114, 108, 100, 0, 0, ...]; // Padded with zeros
  
  // Random value for RLC
  substringMatch.r <== 123456789;
  
  // The output will be 1 (true) because "World" is found at index 7 in "Hello, World!"
  signal output result;
  
  result <== substringMatch.isValid;
}

This example demonstrates how to use the SubstringMatch template to verify that the substring "World" exists within the string "Hello, World!" starting at index 7.

Checklist:

• [x] I have discussed with the team prior to submitting this PR
• [x] I have performed a self-review of my code
• [x] I have commented my code, particularly in hard-to-understand areas
• [x] My changes generate no new warnings
• [x] New and existing unit tests pass locally with my changes