This repository contains implementations of the Collatz sequence using different backends: Plonky3 and Winterfell.

The Collatz sequence is a sequence of numbers defined by the following rules:

1. Start with any positive integer n.
2. If n is 1, stop.
3. If n is even, divide it by 2.
4. If n is odd, multiply it by 3 and add 1.

The Collatz conjecture states that for any positive integer n, the sequence will eventually reach 1.

This repo shows how to implement a proof of knowledge of a valid Collatz sequence using different frameworks.

Specifically, we prove that we know a sequence of numbers that is a valid Collatz sequence, and we know how many steps it takes to reach 1.

Public inputs:

• Starting value
• Length of the sequence

Implemented using the Plonky3 backend for defining the AIR constraints. We use p3-uni-stark as the proving system in the example.

Run the example with:

cargo run -p plonky3-collatz

Implemented using the Winterfell backend for defining the AIR constraints.

Run the example with:

cargo run -p winterfell-collatz

The AIR constraints for the Collatz conjecture were originally described by StarkWare in the Arithmetization I article. Those constraints, however, only attested to the knowledge of correct series of values in the Collatz sequence. Here, we also add the number of steps in that sequence as public input, and convince the verifier that the provided number of steps for a given starting value is correct. This is arguably more useful, for the rare occasion you want to convince someone of the validity of your Collatz computation.

Repo structure inspired by the Fibonacci example by @BrianSeong99, combined with the examples in the Winterfell repo.

This code is provided for experimental and educational purposes only. It has not been audited and should not be used in production environments or for any security-critical applications. Use at your own risk.