Toy Example

We will demonstrate Ligetron with the use of a toy example: the edit distance program. In this example, we will consider two parties, the prover and the verifier, that both have access to a public string B. Furthermore, the prover holds a private string A. Suppose now that the prover wants to prove to the verifier that its string A is within an edit distance of n from string B. Naturally, the prover could simply reveal string A to the verifier, but this would violate its privacy. Below, we demonstrate how Ligetron allows the prover to prove the statement to the verifier without revealing anything but the fact that the statement is true.

Note

Naturally, if the verifier accepts the proof, they learn that strings A and B are close, which leaks some information about the private string A. However, this is a property of the statement being proven rather than a limitation of the proof system. Ligetron allows us to maximize privacy given the constraints of what we're trying to prove.

Implementation

The program takes two strings as input: one private (string A) and one public (string B). It calculates the edit distance between them (how many character changes needed to transform one into the other), and proves that the distance is less than 5 without revealing the private string.

The program accepts the following inputs:

• Argument [1]: <str> Input text A (private string)
• Argument [2]: <str> Input text B (public string)
• Argument [3]: <i64> Length of input text A
• Argument [4]: <i64> Length of input text B

C++

#include <ligetron/api.h>

int minDistance(const char* word1, const char* word2, int m, int n) {
    int pre;
    int cur[n + 1];

    for (int j = 0; j <= n; j++) {
        cur[j] = j;
    }

    for (int i = 1; i <= m; i++) {
        pre = cur[0];
        cur[0] = i;
        for (int j = 1; j <= n; j++) {
            int temp = cur[j];
            bool cond = word1[i - 1] == word2[j - 1];
            cur[j] = oblivious_if(cond,
                                  pre,
                                  oblivious_min(pre, oblivious_min(cur[j - 1], cur[j])) + 1);
            pre = temp;
        }
    }
    return cur[n];
}

int main(int argc, char *argv[]) {
    int dist = minDistance(argv[1],
                           argv[2],
                           *reinterpret_cast<const int*>(argv[3]),
                           *reinterpret_cast<const int*>(argv[4]));

    assert_one(dist < 5);
    return 0;
}

Rust

use ligetron::*;

fn min_distance(word1: *const i8, word2: *const i8, m : usize, n : usize) -> i32 {
    let mut pre: i32;
    let mut cur:Vec<i32> = vec![0; n + 1];

    for j in 0..=n {
        cur[j] = j as i32;
    }

    for i in 1..=m {
        pre = cur[0];
        cur[0] = i as i32;
        for j in 1..=n {
            unsafe {
                let temp = cur[j];
                let cond = *(word1.add(i - 1)) == *(word2.add(j - 1));
                let minimum = oblivious_min(pre, oblivious_min(cur[j - 1], cur[j])) + 1;

                cur[j] = oblivious_if(cond, pre, minimum);
                pre = temp;
            }
        }
    }

    cur[n]
}

fn main() {
    let args = get_args();

    let len1: usize = args.get_as_int(3).try_into().unwrap();
    let len2: usize = args.get_as_int(4).try_into().unwrap();

    let dist = min_distance(args.get_as_c_str(1), args.get_as_c_str(2), len1, len2);

    assert_one(dist < 5);
}

Argument Handling

Ligetron passes arguments as raw memory pointers. In C++, you cast and dereference them directly. In Rust, the SDK provides helper functions like get_as_int() and get_as_c_str().

Key Concepts

Assertions: Defining What You're Proving

The assert_one(condition) function creates a constraint that must be satisfied for the proof to be valid. In this example, assert_one(dist < 5) proves that string A is within edit distance 5 of string B. If the condition is false, proof generation fails; you cannot create a valid proof for a false statement.

Oblivious Operations: Preserving Privacy

Notice the special functions oblivious_if and oblivious_min in the edit distance calculation:

• oblivious_if(condition, if_true, if_false): Executes both branches and selects the result without revealing which branch was taken
• oblivious_min(a, b): Finds the minimum of two values without revealing which was smaller

These operations are crucial for zero-knowledge proofs. Regular if statements or comparisons would leak information about private string A through the program's execution path. Oblivious operations ensure the execution trace looks the same regardless of the witness content; the verifier sees only that the computation happened, not what values were involved.

What the Proof Reveals

The proof demonstrates that distance < 5 is true, but reveals nothing else about string A. The verifier learns:

• ✓ String A exists and is close to string B (within 5 edits)
• ✗ The actual content of string A
• ✗ The exact edit distance (only that it's less than 5)
• ✗ Which characters differ between the strings

Try It Yourself

This exact edit distance example is available on the Ligetron Platform, where you can:

• Write code using the Ligetron API without setting up a development environment locally
• See proof generation metrics in real-time
• Experiment with different input strings
• Modify the distance threshold and see how it affects the proof
• View and edit the complete source code

What's Next?

Now that you've seen a concrete example, you can:

• Learn about the Ligero protocol that powers the system
• Understand how the ZK-VM works under the hood
• Explore the development guide to build your own applications