Halo2 combina tecnologías de esquemas de commitment (commitment schemes), como FRI y KZG, con las últimas versiones de Plonk. Esto proporciona escalabilidad y expresividad, gracias a las nuevas funcionalidades que incluyen Custom Gates y Rotación. En la actualidad, Halo2 es utilizado por la PSE (exploraciones de escalabilidad y privacidad de Ethereum) y Scroll Layer 2, donde lo empleamos para crear pruebas ZK de transacciones de EVM a nivel de bytecode.
En esta sesión vamos a realizar dos versiones de un circuito para probar la computación del fibonacci. Una versión sin optimizar y otra versión donde con ayuda de la rotación de la Rotación logramos reducir el tamaño del circuito.
Antes de iniciar
Para ejecutar este proyecto necesitarás instalar Rust y CMake. Si estás usando linux lo puedes hacer con los comandos siguientes.
apt install cmake build-essential
Preparativos del proyecto de rust
Podemos usar Halo2 desde un proyecto tradicional de Rust. Para iniciar creamos el archivo Cargo.toml
donde indicamos el punto de entrada y las dependencias.
Cargo.toml
[package]
name = "fibonacci"
version = "0.1.0"
edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[lib]
name = "halo2_examples"
path = "src/lib.rs"
[features]
dev-graph = ["halo2_proofs/dev-graph", "plotters"]
[dependencies]
halo2_proofs = { git = "https://github.com/zcash/halo2.git", rev = "a898d65ae3ad3d41987666f6a03cfc15edae01c4"}
plotters = { version = "0.3.0", optional = true }
tabbycat = { version = "0.1", features = ["attributes"], optional = true }
En este proyecto mostraremos crearemos dos versiones de fibonacci, una optimizada y otra sin optimizar. Para eso creamos un archivo intermediario que nos permitirá ejecutar ambas versiones.
src/lib.rs
mod fibonacci_unoptimized;
mod fibonacci_optimized;
Fibonacci versión no optimizada
Ahora a continuación colocamos la versión sin optimizar del circuito de Fibonacci sin optimizar.
src/fibonacci_unoptimized.rs
use std::marker::PhantomData;
use halo2_proofs::{arithmetic::FieldExt, circuit::*, plonk::*, poly::Rotation};
#[derive(Debug, Clone)]
struct FibonacciConfig {
pub col_a: Column<Advice>,
pub col_b: Column<Advice>,
pub col_c: Column<Advice>,
pub selector: Selector,
pub instance: Column<Instance>,
}
#[derive(Debug, Clone)]
struct FibonacciChip<F: FieldExt> {
config: FibonacciConfig,
_marker: PhantomData<F>,
}
impl<F: FieldExt> FibonacciChip<F> {
pub fn construct(config: FibonacciConfig) -> Self {
Self {
config,
_marker: PhantomData,
}
}
pub fn configure(meta: &mut ConstraintSystem<F>) -> FibonacciConfig {
let col_a = meta.advice_column();
let col_b = meta.advice_column();
let col_c = meta.advice_column();
let selector = meta.selector();
let instance = meta.instance_column();
meta.enable_equality(col_a);
meta.enable_equality(col_b);
meta.enable_equality(col_c);
meta.enable_equality(instance);
meta.create_gate("add", |meta| {
//
// col_a | col_b | col_c | selector
// a b c s
//
let s = meta.query_selector(selector);
let a = meta.query_advice(col_a, Rotation::cur());
let b = meta.query_advice(col_b, Rotation::cur());
let c = meta.query_advice(col_c, Rotation::cur());
vec![s * (a + b - c)]
});
FibonacciConfig {
col_a,
col_b,
col_c,
selector,
instance,
}
}
#[allow(clippy::type_complexity)]
pub fn assign_first_row(
&self,
mut layouter: impl Layouter<F>,
) -> Result<(AssignedCell<F, F>, AssignedCell<F, F>, AssignedCell<F, F>), Error> {
layouter.assign_region(
|| "first row",
|mut region| {
self.config.selector.enable(&mut region, 0)?;
let a_cell = region.assign_advice_from_instance(
|| "f(0)",
self.config.instance,
0,
self.config.col_a,
0)?;
let b_cell = region.assign_advice_from_instance(
|| "f(1)",
self.config.instance,
1,
self.config.col_b,
0)?;
let c_cell = region.assign_advice(
|| "a + b",
self.config.col_c,
0,
|| a_cell.value().copied() + b_cell.value(),
)?;
Ok((a_cell, b_cell, c_cell))
},
)
}
pub fn assign_row(
&self,
mut layouter: impl Layouter<F>,
prev_b: &AssignedCell<F, F>,
prev_c: &AssignedCell<F, F>,
) -> Result<AssignedCell<F, F>, Error> {
layouter.assign_region(
|| "next row",
|mut region| {
self.config.selector.enable(&mut region, 0)?;
// Copy the value from b & c in previous row to a & b in current row
prev_b.copy_advice(
|| "a",
&mut region,
self.config.col_a,
0,
)?;
prev_c.copy_advice(
|| "b",
&mut region,
self.config.col_b,
0,
)?;
let c_cell = region.assign_advice(
|| "c",
self.config.col_c,
0,
|| prev_b.value().copied() + prev_c.value(),
)?;
Ok(c_cell)
},
)
}
pub fn expose_public(
&self,
mut layouter: impl Layouter<F>,
cell: &AssignedCell<F, F>,
row: usize,
) -> Result<(), Error> {
layouter.constrain_instance(cell.cell(), self.config.instance, row)
}
}
#[derive(Default)]
struct MyCircuit<F>(PhantomData<F>);
impl<F: FieldExt> Circuit<F> for MyCircuit<F> {
type Config = FibonacciConfig;
type FloorPlanner = SimpleFloorPlanner;
fn without_witnesses(&self) -> Self {
Self::default()
}
fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
FibonacciChip::configure(meta)
}
fn synthesize(
&self,
config: Self::Config,
mut layouter: impl Layouter<F>,
) -> Result<(), Error> {
let chip = FibonacciChip::construct(config);
let (_, mut prev_b, mut prev_c) =
chip.assign_first_row(layouter.namespace(|| "first row"))?;
for _i in 3..10 {
let c_cell = chip.assign_row(layouter.namespace(|| "next row"), &prev_b, &prev_c)?;
prev_b = prev_c;
prev_c = c_cell;
}
chip.expose_public(layouter.namespace(|| "out"), &prev_c, 2)?;
Ok(())
}
}
#[cfg(test)]
mod tests {
use std::marker::PhantomData;
use super::MyCircuit;
use halo2_proofs::{dev::MockProver, pasta::Fp};
#[test]
fn fibonacci_example1() {
let k = 4;
let a = Fp::from(1); // F[0]
let b = Fp::from(1); // F[1]
let out = Fp::from(55); // F[9]
let circuit = MyCircuit(PhantomData);
let mut public_input = vec![a, b, out];
let prover = MockProver::run(k, &circuit, vec![public_input.clone()]).unwrap();
prover.assert_satisfied();
public_input[2] += Fp::one();
let _prover = MockProver::run(k, &circuit, vec![public_input]).unwrap();
// uncomment the following line and the assert will fail
// _prover.assert_satisfied();
}
#[cfg(feature = "dev-graph")]
#[test]
fn plot_fibonacci_unoptimized() {
use plotters::prelude::*;
let root = BitMapBackend::new("fibonacci_unoptimized.png", (1024, 3096)).into_drawing_area();
root.fill(&WHITE).unwrap();
let root = root.titled("Fibonacci Unoptimized Layout", ("sans-serif", 60)).unwrap();
let circuit = MyCircuit::<Fp>(PhantomData);
halo2_proofs::dev::CircuitLayout::default()
.render(4, &circuit, &root)
.unwrap();
}
}
Versión optimizada del fibonacci
Seguidamente colocamos la versión optimizada donde nos servimos de la rotación para comprimir el circuito.
src/fibonacci_optimized.rs
use halo2_proofs::{arithmetic::FieldExt, circuit::*, plonk::*, poly::Rotation};
use std::marker::PhantomData;
#[derive(Debug, Clone)]
struct ACell<F: FieldExt>(AssignedCell<F, F>);
#[derive(Debug, Clone)]
struct FibonacciConfig {
advice: Column<Advice>,
selector: Selector,
instance: Column<Instance>,
}
#[derive(Debug, Clone)]
struct FibonacciChip<F: FieldExt> {
config: FibonacciConfig,
_marker: PhantomData<F>,
}
impl<F: FieldExt> FibonacciChip<F> {
pub fn construct(config: FibonacciConfig) -> Self {
Self {
config,
_marker: PhantomData,
}
}
pub fn configure(
meta: &mut ConstraintSystem<F>,
advice: Column<Advice>,
instance: Column<Instance>,
) -> FibonacciConfig {
let selector = meta.selector();
meta.enable_equality(advice);
meta.enable_equality(instance);
meta.create_gate("add", |meta| {
//
// advice | selector
// a | s
// b |
// c |
//
let s = meta.query_selector(selector);
let a = meta.query_advice(advice, Rotation::cur());
let b = meta.query_advice(advice, Rotation::next());
let c = meta.query_advice(advice, Rotation(2));
vec![s * (a + b - c)]
});
FibonacciConfig {
advice,
selector,
instance,
}
}
pub fn assign(
&self,
mut layouter: impl Layouter<F>,
nrows: usize,
) -> Result<AssignedCell<F, F>, Error> {
layouter.assign_region(
|| "entire fibonacci table",
|mut region| {
self.config.selector.enable(&mut region, 0)?;
self.config.selector.enable(&mut region, 1)?;
let mut a_cell = region.assign_advice_from_instance(
|| "1",
self.config.instance,
0,
self.config.advice,
0,
)?;
let mut b_cell = region.assign_advice_from_instance(
|| "1",
self.config.instance,
1,
self.config.advice,
1,
)?;
for row in 2..nrows {
if row < nrows - 2 {
self.config.selector.enable(&mut region, row)?;
}
let c_cell = region.assign_advice(
|| "advice",
self.config.advice,
row,
|| a_cell.value().copied() + b_cell.value(),
)?;
a_cell = b_cell;
b_cell = c_cell;
}
Ok(b_cell)
},
)
}
pub fn expose_public(
&self,
mut layouter: impl Layouter<F>,
cell: AssignedCell<F, F>,
row: usize,
) -> Result<(), Error> {
layouter.constrain_instance(cell.cell(), self.config.instance, row)
}
}
#[derive(Default)]
struct MyCircuit<F>(PhantomData<F>);
impl<F: FieldExt> Circuit<F> for MyCircuit<F> {
type Config = FibonacciConfig;
type FloorPlanner = SimpleFloorPlanner;
fn without_witnesses(&self) -> Self {
Self::default()
}
fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
let advice = meta.advice_column();
let instance = meta.instance_column();
FibonacciChip::configure(meta, advice, instance)
}
fn synthesize(
&self,
config: Self::Config,
mut layouter: impl Layouter<F>,
) -> Result<(), Error> {
let chip = FibonacciChip::construct(config);
let out_cell = chip.assign(layouter.namespace(|| "entire table"), 10)?;
chip.expose_public(layouter.namespace(|| "out"), out_cell, 2)?;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::MyCircuit;
use std::marker::PhantomData;
use halo2_proofs::{dev::MockProver, pasta::Fp};
#[test]
fn fibonacci_example2() {
let k = 4;
let a = Fp::from(1); // F[0]
let b = Fp::from(1); // F[1]
let out = Fp::from(55); // F[9]
let circuit = MyCircuit(PhantomData);
let mut public_input = vec![a, b, out];
let prover = MockProver::run(k, &circuit, vec![public_input.clone()]).unwrap();
prover.assert_satisfied();
public_input[2] += Fp::one();
let _prover = MockProver::run(k, &circuit, vec![public_input]).unwrap();
// uncomment the following line and the assert will fail
// _prover.assert_satisfied();
}
#[cfg(feature = "dev-graph")]
#[test]
fn plot_fibonacci_optimized() {
use plotters::prelude::*;
let root = BitMapBackend::new("fibonacci_optimized.png", (1024, 3096)).into_drawing_area();
root.fill(&WHITE).unwrap();
let root = root.titled("Fibonacci Optimized Layout", ("sans-serif", 60)).unwrap();
let circuit = MyCircuit::<Fp>(PhantomData);
halo2_proofs::dev::CircuitLayout::default()
.render(4, &circuit, &root)
.unwrap();
}
}
Compilar y generar el gráfico
Ahora estamos listos para compilar los circuitos y probarlo. Halo2 incluye librerías para visualizar gráficas de circuitos donde podremos comparar la compresión. Para hacerlo ejecuta los siguientes comandos.
cargo build
cargo test --all-features -- --nocapture plot_fibonacci_unoptimized
cargo test --all-features -- --nocapture plot_fibonacci_optimized
Ahora podrás ver la diferencia en fibonacci_optimized.png
y fibonacci_unoptimized.png
. Como los que muestro a continuación.
Como puedes observar en el gráfico, la versión no optimizada del circuito de fibonacci usamos 4 columnas.
Luego de optimizar, usamos únicamente 2 columnas.
Links recomendados sobre Halo2
Video tutoriales sobre fibonacci en Plonk:
- Intro a HALO2-ce: https://www.youtube.com/watch?v=60lkR8DZKUA
- Tutorial de 0xParc: https://learn.0xparc.org/halo2/
Pizarras sobre las bases de Halo2 y Plonk:
- Plonk: https://www.youtube.com/watch?v=Uldlq35Se3k
- Halo2: https://www.youtube.com/watch?v=RaEs5mnXIhY
Tutoriales en blogposts:
- Crear una dapp de Halo2 con frotend en WASM: https://medium.com/@yujiangtham/building-a-zero-knowledge-web-app-with-halo-2-and-wasm-part-1-80858c8d16ee
¿Qué se viene en ZK?
- Lanzamiento de Aztec v3 L2: https://medium.com/aztec-protocol/introducing-noir-the-universal-language-of-zero-knowledge-ff43f38d86d9
- Nova, folding, y VDFs: https://www.youtube.com/watch?v=SwonTtOQzAk
- ¡Scroll está próximo a lanzar!: https://scroll.io/
¡Felicidades y gracias por completar esta serie de Workshops!
Asegúrate de seguir a @Layer2es y a Filosofía Código para mantenerte al tanto de los avances en Layer 2 y desarrollo en blockchain.
Top comments (0)