mirror of
https://github.com/qwang98/PyChiquito.git
synced 2026-04-22 03:00:16 -04:00
09ef47ad6a
* updated tutorial * update tutorial * new error emerge after updating submodule, was fully debugged previously * updated rust bindings and formatted python files * minor * updated submodule * cargo fmt * cleaned latest merge main; debugged and updated all tutorial files * addressed leo's comments' * removed num_step_instances * updated dependencies and deleted unwanted functions
90 lines
4.9 KiB
Plaintext
90 lines
4.9 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"attachments": {},
|
|
"cell_type": "markdown",
|
|
"id": "14a9a617-1c05-40c8-b4ef-3cc2fbcf99fe",
|
|
"metadata": {},
|
|
"source": [
|
|
"# Part 3: Fibonacci Example\n",
|
|
"The best learning is by doing, In this Chapter, we will walk through the [fibonacci.py](https://github.com/qwang98/PyChiquito/blob/main/pychiquito/fibonacci.py) example.\n",
|
|
"# Chapter 1: Fibonacci and Chiquito Concepts\n",
|
|
"The Fibonacci series is an infinite series, starting from \"1\" and \"1\", in which every number in the series is the sum of two numbers preceding it in the series. The first few rounds for the Fibonacci series are:\n",
|
|
"- 1 + 1 = 2\n",
|
|
"- 1 + 2 = 3\n",
|
|
"- 2 + 3 = 5\n",
|
|
"- 3 + 5 = 8\n",
|
|
"\n",
|
|
"Therefore, to express these mathematical equations, we need three variables \"a\", \"b\", and \"c\", which we call \"signals\" in Chiquito. Because zero knowledge proofs typically express mathematical equations in the matrix form, we construct the following table:\n",
|
|
"\n",
|
|
"||Signals||\n",
|
|
"| :-: | :-: | :-: |\n",
|
|
"| a | b | c |\n",
|
|
"| 1 | 1 | 2 |\n",
|
|
"| 1 | 2 | 3 |\n",
|
|
"| 2 | 3 | 5 |\n",
|
|
"| 3 | 5 | 8 |\n",
|
|
"|| ... ||\n",
|
|
"\n",
|
|
"Besides assigning values to these signals, we also need to define the mathematical relationships among them, which we call \"constraints\" in Chiquito. For each row:\n",
|
|
"- a + b == c\n",
|
|
"- b = a in the next row\n",
|
|
"- c = b in the next row\n",
|
|
"\n",
|
|
"||Signals|||Setups||\n",
|
|
"| :-: | :-: | :-: | :-: | :-: | :-: |\n",
|
|
"| a | b | c | constraint 1 | constraint 2 | constraint 3 |\n",
|
|
"| 1 | 1 | 2 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| 1 | 2 | 3 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| 2 | 3 | 5 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| 3 | 5 | 8 | a + b == c | b == a.next | c == b.next |\n",
|
|
"|| ... ||| ... ||\n",
|
|
"\n",
|
|
"Chiquito is a step-based language for constructing zero knowledge circuits, which means that instead of expressing all signals and constraints above as one entirety, we separate them into smaller chunks, called \"step instances\". In this example, each row, together with its signals and constraints, are collectively called a \"step instance\". We add indices for these step instances to the table, starting from 0:\n",
|
|
"\n",
|
|
"| Step Instance Index || Signals ||| Setups ||\n",
|
|
"| :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n",
|
|
"|| a | b | c | constraint 1 | constraint 2 | constraint 3 |\n",
|
|
"| 0 | 1 | 1 | 2 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| 1 | 1 | 2 | 3 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| 2 | 2 | 3 | 5 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| 3 | 3 | 5 | 8 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| ... || ... ||| ... ||\n",
|
|
"\n",
|
|
"Note that these 4 step instances share the same signals and constraints, although not the same value assignments for signals. They are essentially different instantiations of the same signals and constraints, or different \"step instances\" of the same \"step type\". In Chiquito, we define signals and constraints in \"step types\" and we generate \"witness assignments\" for signal values. \"Step types\" with \"witness assignments\" become \"step instances\". In the example above, we have 4 step instances but only 1 step type, defined as the same 3 signals and 3 constraints. For simplicity, we call this single step type \"fibo step\", also added to the table below:\n",
|
|
"| Step Type | Step Instance Index || Signals ||| Setups ||\n",
|
|
"| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n",
|
|
"||| a | b | c | constraint 1 | constraint 2 | constraint 3 |\n",
|
|
"| fibo step | 0 | 1 | 1 | 2 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| fibo step | 1 | 1 | 2 | 3 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| fibo step | 2 | 2 | 3 | 5 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| fibo step | 3 | 3 | 5 | 8 | a + b == c | b == a.next | c == b.next |\n",
|
|
"| ... | ... || ... ||| ... ||\n",
|
|
"\n",
|
|
"As a recap, to construct a Fibonacci circuit, we need three signals-\"a\", \"b\", and \"c\". In Chiquito, \"circuit\" is a set of constraints that signals of the circuit need to satisfy. Each Chiquito circuit is composed of multiple \"step instances\", which are instantiations of \"step types\". Each \"step type\" contains a subset of signals and constraints that these signals need to satisfy. "
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "pychiquito_kernel",
|
|
"language": "python",
|
|
"name": "pychiquito_kernel"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 3
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython3",
|
|
"version": "3.11.4"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|