Feat: Reveal Substring 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

[Divide-By-0]

Can we add an option for someone to constrain 'only one' or something, meaning that if its on it checks the rest of the string, and if any other substring matches then it returns an argument of 0? Can you also calculate r automatically with fiat shamir on all the inputs? So like the query string, the large string, and the index?

[shreyas-londhe]

@Divide-By-0

Can we add an option for someone to constrain 'only one' or something, meaning that if its on it checks the rest of the string, and if any other substring matches then it returns an argument of 0?

I think these are two different use cases:

1. Proving that a substring exists in a string at an index.
2. Proving that a substring exists in a string.

The current template is optimised to follow Case 1.

What I suggest we can do is, we can have two variations for the two cases. For Case 2, we can use Zac's string search algorithm (https://github.com/noir-lang/noir_string_search) which is efficient for that case.