Gnark
For users of the Gnark stack.
This tutorial corresponds to the v0.9.0
version of Gnark with the Groth16 proving scheme and BN254 elliptic curve.
It should also work with v0.8.1
if you're still on an older version.
Introductionβ
We will walk through the process of generating a proof capable of verifying the result of a simple compression algorithm. The complete and finished code can be found here along with other example projects in our sindri-resources repository. You can also check out the Gnark documentation for more general background information on using Gnark.
Compression Algorithmβ
The compression scheme that we'll be implementing is a form of Run-Length Encoding (RLE) with a fixed-length encoding. Here's how this lossless compression algorithm is implemented:
- Scan the input string of bytes sequentially.
- For every distinct byte, record the byte once followed by a count of its consecutive repetitions ranging from 1-9 encoded in ASCII.
For example,
cccc
becomesc4
andF
becomesF1
. - If a byte is repeated more than nine times consecutively, it's chunked into groups.
For instance, twelve repetitions of the byte
b
would be encoded asb9b3
.
The ASCII encoding of a limited 1-9 range was chosen solely to make string representations more understandable for the purpose of this tutorial. You could trivially extend this to a range of 1-256 to take full advantage of the repetition-count bytes and improve the compression ratio.
To get a better feel for the compression algorithm, you can enter different input strings below to see how they're encoded.
Give it a Spin
Enter any input string to see how it's compressed:
rrrrr
r5
kkkkkk
k6
MMM
M3
sssssssss
s9
ssssss
s6
JJJJJJJJJ
J9
JJJJJJJ
J7
r5k6M3s9s6J9J7
While this compression scheme is a toy model, it highlights several foundational principles that underpin more practical algorithms. At its core, the model captures the essence of pattern recognition and substitution, a concept that's central to techniques employed by algorithms like LempelβZivβWelch (LZW), where recurring patterns are substituted with shorter representations. Additionally, the toy algorithm's approach to breaking down and encoding longer sequences mirrors the segmentation seen in Huffman coding, which prioritizes frequent sequences for shorter encodings.
Circuitβ
In the previous section, we described how our toy compression model works in terms of input and output strings. Our circuit will operate on byte arrays of these strings encoded as ASCII. There will be two input variables to the circuit:
Original
- A 100 byte array encoding the input string. This is a secret input to the circuit and need not be disclosed to construct the public witness and verify a proof.Compressed
- A 200 byte array encoding the output string. This is a public input that will be disclosed and is necessary to construct the public witness and verify a proof.
The small annotations in this figure are meant to illustrate how the repetition counts are mapped from ASCII to bytes.
The ASCII character for 3
is encoded as , and all other digits share this offset of .
This was done to make the encoded strings more readable, a more practical compression algorithm would likely be operating directly with bytes in the first place.
Our circuit will verify that some Original
input array which compresses to Compressed
was known at the time of proof generation.
This is a relatively loose constraint, but you can imagine how this might be extended in a real application of a compression circuit to verify that a private uncompressed input with a given public hash input compresses to a public compressed input.
We'll use the Groth16 proving scheme to generate a proof for our circuit.
Circuit Configurationβ
The circuit is organized in a circuit/
directory containing these files.
circuit/
βββ circuit.go
βββ go.mod
βββ go.sum
βββ input.json
βββ sindri.json
The go.mod
and go.sum
files are the standard Go project files for defining a module and locking its dependencies.
These should include any dependencies that your code uses, including any Gnark modules.
For detailed descriptions of the other files, you can click through the different tabs here.
- sindri.json
- Circuit Definition
- From JSON
For any circuit using any framework, you always need a sindri.json
file defining certain metadata about your circuit.
There are a few key pieces of information here that are required:
- The
packageName
andgnarkVersion
must be included and match the values in yourgo.mod
file. - The
curve
andprovingScheme
settings specify the Gnark proving scheme and elliptic curve. - The
circuitStructName
specifies the name of the public interface in your Go package which implements the Gnarkfrontend.Circuit
interface (see: Circuit Structure).
Your circuit package must include a circuit definition in accordance with the Gnark framework documentation.
This means that there must be a .go
file including a struct
which satisfies the Gnark frontend.Circuit
interface and contains both your public and secret input variables as frontend.Variable
fields.
To meet the requirements of the interface, the struct
must have a Define
method defined on it which implements the circuit logic.
Make sure that your circuit's struct
name matches circuitStructName
and the package name matches packageName
in sindri.json
.
Your package must also define a special func FromJson(pathInput string) witness.Witness
function which takes a file input path pointing to a JSON file as a string, then reads in this JSON file and constructs the full witness from the inputs described in the file.
This gives you the opportunity to map a more ergonomic input data format to the final input format required for your circuit.
With our compression circuit, our FromJson()
method allows us to specify the original
input as an ASCII-encoded string instead of an array of byte values (see example-input.json
for an example).
Here is how we implement that mapping and construct the witness.
loading...
We also define a small boilerplate func ReadFromInputPath(pathInput string) (map[string]interface{}, error)
function which this uses to read in the JSON file.
This can be copy and pasted into any Gnark circuit's package because it doesn't depend on the circuit or witness in any way.
Sindri APIβ
We'll walk through the steps to upload your packaged script to Sindri, compile it, generate proofs, and verify proofs.
You can interact with the API in the language of your choice; we'll use JavaScript with form-data
and the axios
request library here.
Each code block can be copy and pasted into a node
REPL sequentially, or you can download the full compile.mjs
script and run it all at once with node compile.mjs
.
The easiest thing to do is to clone the sindri-resrouces repository and work within the gnark/v0.9.0/compress
subdirectory because that will ensure that you have not only the script, but also all of the files necessary for the commands to succeed.
# Clone the Sindri resources repository and move into the `compress` tutorial.
git clone https://github.com/Sindri-Labs/sindri-resources.git
cd sindri-resources/circuit_tutorials/gnark/v0.9.0/compress
You'll need to install a few dependencies before you continue.
# Install dependencies from `package.json` if you've cloned the repo.
npm install
# Or...
# Install them manually.
npm install axios form-data tar
You'll also need your Sindri API key to authenticate all requests to the API, so make sure you have this ready (see #api-authentication).
You can either modify the script to include your API key directly, or set a SINDRI_API_KEY
environment variable before running the compilation script (e.g. by running SINDRI_API_KEY=<my-key> node compile.mjs
).
The first chunk of the script simply imports the dependencies and configures axios
to authenticate with and use the Sindri API.
Upload & Compileβ
To upload and compile our circuit, we first need to create a gzipped tar archive of our circuit directory and upload it to the /circuit/{circuit_id}/create
endpoint.
Our sindri.json
file included in the tarball indicates that the circuitType
is gnark
and that compress
is the name of the circuit.
Uploading this tarball will automatically trigger circuit compilation.
Output - Create Circuit
Circuit ID: 88433990-ca2a-4060-92ec-0acbeff1e3b5
The returned circuit ID can then be used to perform additional operations related to the circuit such as fetching its current state or generating proofs once it has compiled successfully.
In fact, we will immediately use this ID to poll the /circuit/${circuitId}/detail
endpoint until the circuit status
is Ready
.
Output - Circuit Polling
Polling succeeded after 28.4 seconds.
Output - Circuit Detail
{
"circuit_id": "88433990-ca2a-4060-92ec-0acbeff1e3b5",
"circuit_name": "compress",
"circuit_type": "Gnark",
"date_created": "2023-10-26T17:33:00.553Z",
"status": "Ready",
"version": "v1.4.3",
"compute_time": "P0DT00H00M18.553732S",
"compute_times": {
"total": 18.55373217887245,
"queued": 10.540048,
"compile": 11.976261832984164,
"clean_up": 0.00571231497451663,
"file_setup": 0.3128799251280725,
"save_results": 1.6724711069837213,
"extract_code_tarfile": 0.003556526033207774,
"compile_r1cs_and_keygen": 4.582673318916932
},
"curve": "Groth16 bn254",
"degree": null,
"num_constraints": null,
"trusted_setup_file": null,
"verification_key": null,
"error": null
}
After circuit compilation has completed, we're ready to generate proofs for arbitrary circuit inputs.
Proveβ
We can generate new proofs using the /circuit/${circuitId}/prove
endpoint, and then follow a similar polling pattern with /proof/${proofId}/detail
endpoint until status
is Ready
.
Output - Polling
Proof ID: 94de088e-8230-4be0-83b3-3172dfb56990
Polling succeeded after 30.4 seconds.
Output - Proof
{
"proof": "EGYGn6LyytKEF/Lt5yIsG9fORsU9rRHXaEc+RJl+6foJJfF3RTz7JZje5++gYO6UMPSIYOlsbhLYqTL8FPJqRAIZ0pKhUAp/ZqVQ2nf179zApiGVA9XOCZjv6i4UcQ/LEWba72jkZ99CJh+EdUwMRBRAm9QgVtB20PPzyBAPx14V3Owfi6a0miJCfj4CmjEbEZgVIub0TX8y1xQD1JwLsCVwbM3lc8bHS64I21NPf1M3SdCzvB0eRk6rj16xZlzCK0lrO9j3lCdRfcgvh/hzbEScgoeXoOfYHzoD1qu2JQQlOl4Lu80f6eNM2kXVWMzgVHWPDo5WgCgY/YlNLeAFUwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
}
Output - Public Inputs
{
Original: [
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null,
null
],
Compressed: [
114, 53, 107, 54, 77, 51, 115, 63, 74, 64, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0,
"... 100 more items"
]
}
The proof detail response contains everything that we need to verify the proof locally.
Verifyβ
Finally, our compile.mjs
script writes out the full proof detail response to a local JSON file.
The output is quite large because it includes the base64 encoded verifying key and proof, but you can view an example proof-detail-response.json
on GitHub.
The proof detail also contains the public proof inputs as we saw above in #prove, so it has everything we need to verify a proof locally.
Here is a simple Go program which parses the JSON proof detail response content and uses it to reconstruct the proof, verifying key, and public witness using Gnark structs. It then verifies the proof or raises an error if verification fails.
To compile and execute the verification code, you can run the following commands.
# Compile the verification program.
go build -o verify verify.go
# Verify the proof in the JSON response data.
./verify proof-detail-response.json
Output - Proof Verification
14:10:13 DBG verifier done backend=groth16 curve=bn254 took=1.970676
Proof verified successfully.
As the output shows, our proof was verified successfully!