succinct_open_source_challenge.md

Succinct Open Source Challenge

Working with variable length computations in a circuit is tricky because of the requirement to have a fixed computational graph. This challenge is to implement variable length SHA256 as a circuit. The circuit should have a public input called input_bytes: a fixed size array of size 10 with 32 byte entries. The other public input should be length: how many of the array entries should be hashed. The circuit output should be the sha256 hash of the first length entries in the array. You should only hash length * 32 bytes, and do not hash any extra zero bytes (this is the tricky part to figure out)! Golang pseudocode below:

func VariableLengthHash(input_bytes [10][32]byte, length int) [32]byte {
	// Concatenate the bytes
	var concatenatedBytes []byte
	for i := 0; i < length; i++ {
		concatenatedBytes = append(concatenatedBytes, input_bytes[i]...)
	}

	// Compute SHA256 hash
	hash := sha256.Sum256(concatenatedBytes)

	return hash
}

Feel free to use any proving system of your choice. There is a naive solution and an optimized solution, so try to minimize your constraint count! We have provided helpful links for both circom and plonky2. When complete, send us a link to a Github repository or a Gist/pastebin of your implementation to opensource@succinct.xyz along with a short writeup describing the approach.

Circom resources

When using circom, you can get started by pasting the starter template into https://zkrepl.dev/, an online IDE for circom. There are other helpful resources below.

• Circom starter template: https://gist.github.com/puma314/1169dd0d6116c6282383858bea8b5430
• Main circom repo: https://github.com/iden3/circom
• Main circom tutorial: https://docs.circom.io/
• Circom sha256 implementation: https://github.com/iden3/circomlib/tree/master/circuits/sha256
• Online IDE for circom: https://zkrepl.dev/

Plonky2 Resources (Rust-based proving framework)

• Main plonky2 repo: https://github.com/mir-protocol/plonky2
• Here is an open-source implementation of sha256: https://github.com/succinctlabs/btc-warp/blob/main/src/circuits/sha256.rs
• Here are examples of circuits: https://github.com/mir-protocol/plonky2/blob/main/plonky2/examples/fibonacci.rs