recursive proof composition

ZKProof Standards 5.5

1 Aug 2023

agenda

1. overview
1. motivation
2. constructions

​

1. comparison
1. recursion threshold
2. zero-knowledgeness
3. support for lookup arguments
4. security and cryptographic assumptions
1. future work
1. tooling & interfaces
2. benchmarking
3. standards & specifications

agenda

1. overview
1. motivation
2. constructions

​

1. comparison
1. recursion threshold
2. zero-knowledgeness
3. support for lookup arguments
4. security and cryptographic assumptions
1. future work
1. tooling & interfaces
2. benchmarking
3. standards & specifications

V₀

V

P

a recursive proof is a proof that enforces the accepting computation of the proof system’s own verifier

π

overview: motivation

shrinking proof size

π_C

V₀

V

C

π_R

overview: motivation

https://github.com/mir-protocol/plonky2/blob/main/plonky2/examples/bench_recursion.rs#L183

​

// Start with a dummy proof of specified size

let inner = dummy_proof::<F, C, D>(config, log2_inner_size)?;

let (_, _, cd) = &inner;

​

∏_dummy

V_dummy

shrinking proof size

overview: motivation

​

// Start with a dummy proof of specified size

let inner = dummy_proof::<F, C, D>(config, log2_inner_size)?;

let (_, _, cd) = &inner;

​

// Recursively verify the proof

let middle = recursive_proof::<F, C, C, D>(&inner, config, None)?;

let (_, _, cd) = &middle;

​

∏_dummy

∏₀

V_dummy

V₀

Initial proof degree 16384 = 2^14

Degree before blinding & padding: 4028

Degree after blinding & padding: 4096

shrinking proof size

https://github.com/mir-protocol/plonky2/blob/main/plonky2/examples/bench_recursion.rs#L183

overview: motivation

​

// Start with a dummy proof of specified size

let inner = dummy_proof::<F, C, D>(config, log2_inner_size)?;

let (_, _, cd) = &inner;

​

// Recursively verify the proof

let middle = recursive_proof::<F, C, C, D>(&inner, config, None)?;

let (_, _, cd) = &middle;

​

// Add a second layer of recursion to shrink the proof size further

let outer = recursive_proof::<F, C, C, D>(&middle, config, None)?;

let (proof, vd, cd) = &outer;

∏_dummy

∏₀

∏₁

V_dummy

V₀

V₁

Single recursion proof degree 4096 = 2^12

Degree before blinding & padding: 3849

Degree after blinding & padding: 4096

Initial proof degree 16384 = 2^14

Degree before blinding & padding: 4028

Degree after blinding & padding: 4096

shrinking proof size

https://github.com/mir-protocol/plonky2/blob/main/plonky2/examples/bench_recursion.rs#L183

overview: motivation

∏_dummy

∏₀

∏₁

V_dummy

V₀

V₁

Double recursion proof degree 4096 = 2^12

Proof length: 127184 bytes

0.2511s to compress proof

Compressed proof length: 115708 bytes

Single recursion proof degree 4096 = 2^12

Degree before blinding & padding: 3849

Degree after blinding & padding: 4096

Initial proof degree 16384 = 2^14

Degree before blinding & padding: 4028

Degree after blinding & padding: 4096

shrinking proof size

https://github.com/mir-protocol/plonky2/blob/main/plonky2/examples/bench_recursion.rs#L183

overview: motivation

shrinking proof size

overview: motivation

each column j corresponds to a Lagrange interpolation polynomial p_j(X)�evaluating to p_j(⍵ⁱ) = x_ij, where ⍵ is the n^th primitive root of unity.

x_ij

shrinking proof size

overview: motivation

wide circuit

π_wide

fast prover

large proof

shrinking proof size

overview: motivation

wide circuit

π_wide

fast prover

large proof

narrow circuit

π_narrow

slow prover

tiny proof

shrinking proof size

overview: motivation

wide circuit

π_wide

fast prover

large proof

verifier in narrow circuit

π_narrow

slow prover

tiny proof

shrinking proof size

overview: motivation

STARK prover circuit

π_STARK

fast prover

large proof

shrinking proof size

overview: motivation

STARK prover circuit

π_STARK

fast prover

large proof

Groth16 prover circuit

π_Groth16

slow prover

tiny proof

shrinking proof size

overview: motivation

STARK prover circuit

π_STARK

fast prover

large proof

STARK verifier in Groth16 prover circuit

π_Groth16

slow prover

tiny proof

shrinking proof size

overview: motivation

STARK prover circuit

π_STARK

STARK verifier in Groth16 prover circuit

π_Groth16

slow prover

tiny proof

STARK prover circuit

π_STARK

shrinking proof size

overview: motivation

STARK prover circuit

π_STARK

STARK verifier in Groth16 prover circuit

π_Groth16

slow prover

tiny proof

STARK prover circuit

π_STARK

shrinking proof size

overview: motivation

F’

F’

F’

F⁽³⁾

z₀

π₃,z₃

Π₀, z₀

break large circuit into N repetitions of smaller circuit: reduces prover space complexity

Π₁, z₁

Π₂, z₂

Π₃, z₃

incrementally verifiable computation

overview: motivation

applications:

​

• verify chain of N blocks with a single proof (e.g. Mina Protocol )
• verify N steps of program in virtual machine (e.g. RISC Zero )
• verify inference of an N-layer neural network (e.g. Zator 🐊)

F’

F’

F’

…

F’

Π₀, z₀

Π₁, z₁

Π₂, z₂

Π_N, z_N

incrementally verifiable computation

overview: motivation

a blockchain in which each block can be verified in constant time regardless of the number of prior blocks in the history

tx₀

tx₁

tx₂

tx₃

tx₄

σ(tx₀)

σ(tx₁)

σ(tx₂)

σ(tx₃)

σ(tx₄)

full node

e.g. succinct blockchain

overview: motivation

a blockchain in which each block can be verified in constant time regardless of the number of prior blocks in the history

e.g. succinct blockchain

tx₀

tx₁

tx₂

tx₃

tx₄

σ(tx₀)

σ(tx₁)

σ(tx₂)

σ(tx₃)

σ(tx₄)

full node

light client

assume correct

overview: motivation

a blockchain in which each block can be verified in constant time regardless of the number of prior blocks in the history

e.g. succinct blockchain

tx₀

tx₁

tx₂

tx₃

tx₄

σ(tx₀)

σ(tx₁)

σ(tx₂)

σ(tx₃)

σ(tx₄)

full node

light client

π₀

"σ(tx₀) is a valid state transition"

π₁

"σ(tx₁) is a valid state transition, and π₀ is correct"

π₂

π₃

π₄

"σ(tx₂) is a valid state transition, and π₁ is correct"

"σ(tx₃) is a valid state transition, and π₂ is correct"

the state transitions up to this block are correct

overview: motivation

verifiable delay function [BBBF18]: a sequential computation that is slow to compute but efficient to verify

f

f

f

f

x

f(x)

f²(x)

f³(x)

f⁴(x)

"f⁴(input) = output"

evaluator

π^f₄

prover

e.g. parallelising the VDF prover

overview: motivation

verifiable delay function [BBBF18]: a sequential computation that is slow to compute but efficient to verify

f

f

f

f

x

f(x)

f²(x)

f³(x)

f⁴(x)

π^f

π^f

π^f

π^f

"f(input) = output"

π^r

π^r

π^r

"the previous two proofs were correct"

"the previous two proofs were correct"

evaluator

e.g. parallelising the VDF prover

overview: motivation

proof-carrying data

image from https://people.eecs.berkeley.edu/~alexch/docs/CT10.pdf

overview: motivation

proof-carrying data

e.g. MapReduce [CTV15]

overview: constructions

overview: constructions

proof-carrying data (PCD)

non-uniform IVC (NIVC)

full recursion

accumulation scheme

incrementally verifiable computation (IVC)

atomic accumulation

split accumulation / folding scheme

[Val08]

[KS22]

[BCMS20]

[BCLMS21]

[BGH19]

[Chi10]

[BCTV14]

overview: constructions

overview: constructions

proof-carrying data (PCD)

non-uniform IVC (NIVC)

full recursion

accumulation scheme

incrementally verifiable computation (IVC)

atomic accumulation

split accumulation / folding scheme

[Val08]

[KS22]

[BCMS20]

[BCLMS21]

[BGH19]

[Chi10]

[BCTV14]

overview: constructions

overview: constructions

full recursion

z_i

z_i+1

π_i

π_i+1

w_i

V(π_i) = 1

z_i+1 = F(z_i; w_i)

IVC prover

SNARK.Verify

overview: constructions

overview: constructions

full recursion

z_i

z_i+1

π_i

π_i+1

R

SNARK.Prove

w_i

V(π_i) = 1

z_i+1 = F(z_i; w_i)

π_i+1

IVC prover

SNARK.Verify

overview: constructions

overview: constructions

full recursion

z_i

z_i+1

π_i

π_i+1

R

SNARK.Prove

SNARK.Prove

R

w_i

w_i+1

V(π_i) = 1

z_i+1 = F(z_i; w_i)

π_i+1

V(π_i+1) = 1

z_i+2 = F(z_i+1; w_i+1)

IVC prover

IVC prover

SNARK.Verify

SNARK.Verify

overview: constructions

overview: constructions

full recursion

z_i

z_i+1

π_i

π_i+1

R

SNARK.Prove

SNARK.Prove

R

z_i+2

π_i+2

w_i

w_i+1

V(π_i) = 1

z_i+1 = F(z_i; w_i)

π_i+1

V(π_i+1) = 1

z_i+2 = F(z_i+1; w_i+1)

π_i+2

IVC prover

IVC prover

SNARK.Verify

SNARK.Verify

overview: constructions

overview: constructions

full recursion

z_i

z_i+1

π_i

π_i+1

R

SNARK.Prove

SNARK.Prove

R

z_i+2

π_i+2

w_i

w_i+1

V(π_i) = 1

z_i+1 = F(z_i; w_i)

π_i+1

V(π_i+1) = 1

z_i+2 = F(z_i+1; w_i+1)

π_i+2

IVC prover

IVC prover

IVC verifier

z_n

π_n

z₀

0/1

SNARK.Verify

SNARK.Verify

overview: constructions

full recursion: small-field FRI

image from https://www.risczero.com/news/continuations

overview: constructions

full recursion: small-field FRI

image from https://www.risczero.com/news/continuations

overview: constructions

full recursion: pairings over a cycle of elliptic curves [BCTV14]

z_i

π_q

F

V

R

SNARK.Prove

V

SNARK.Prove

F

R

z_i+1

π_r

w_i

𝔽_q

𝔽_r

w_i

e.g. MNT4/6 curves

overview: constructions

full recursion: pairings over a cycle of elliptic curves [BCTV14]

z_i

π_q

F

V

R

SNARK.Prove

V

SNARK.Prove

F

R

z_i+1

π_r

w_i

𝔽_q

𝔽_r

w_i

e.g. MNT4/6 curves

high concrete cost of pairing check!

overview: constructions

overview: constructions

proof-carrying data (PCD)

non-uniform IVC (NIVC)

full recursion

accumulation scheme

incrementally verifiable computation (IVC)

atomic accumulation

split accumulation / folding scheme

[Val08]

[KS22]

[BCMS20]

[BCLMS21]

[BGH19]

[Chi10]

[BCTV14]

overview: constructions

overview: constructions

atomic accumulation

z_i

z_i+1

w_i

overview: constructions

overview: constructions

atomic accumulation

z_i

z_i+1

IVC prover

π_i

π_i+1

acc_i

acc_i+1

accumulation prover

w_i

overview: constructions

overview: constructions

atomic accumulation

z_i

z_i+1

IVC prover

π_i

π_i+1

accumulation verifier

w_i

acc_i

acc_i+1

overview: constructions

overview: constructions

atomic accumulation

z_i

z_i+1

IVC prover

π_i

π_i+1

R

SNARK.Prove

w_i

acc_i

acc_i+1

overview: constructions

overview: constructions

atomic accumulation

IVC verifier

z_i

z_i+1

IVC prover

π_i

π_i+1

R

SNARK.Prove

w_i

acc_i

acc_i+1

overview: constructions

overview: constructions

atomic accumulation

z_i

z_i+1

IVC prover

π_i

π_i+1

R

SNARK.Prove

w_i

IVC verifier

z_i+1

SNARK.Verify

acc_i

acc_i+1

overview: constructions

overview: constructions

proof-carrying data (PCD)

non-uniform IVC (NIVC)

full recursion

accumulation scheme

incrementally verifiable computation (IVC)

atomic accumulation

split accumulation / folding scheme

[Val08]

[KS22]

[BCMS20]

[BCLMS21]

[BGH19]

[Chi10]

[BCTV14]

overview: constructions

overview: constructions

overview: constructions

split accumulation / folding

z_i

z_i+1

w_i

overview: constructions

overview: constructions

overview: constructions

split accumulation / folding

z_i

z_i+1

IVC prover

π_i

a_i

a_i+1

w_i

overview: constructions

overview: constructions

overview: constructions

split accumulation / folding

z_i

z_i+1

IVC prover

π_i

a_i

π_x,i

π_w,i

a_x,i

a_w,i

w_i

a_i+1

overview: constructions

overview: constructions

overview: constructions

split accumulation / folding

z_i

z_i+1

IVC prover

π_i

a_i

a_i+1

R

π_x,i

π_w,i

a_x,i

a_w,i

w_i

overview: constructions

overview: constructions

overview: constructions

split accumulation / folding

z_i

z_i+1

IVC prover

π_i

π_i+1

a_i

a_i+1

R

SNARK.Prove

IVC verifier

π_x,i

π_w,i

a_x,i

a_w,i

w_i

overview: constructions

overview: constructions

overview: constructions

split accumulation / folding

z_i

z_i+1

IVC prover

π_i

π_i+1

a_i

a_i+1

R

SNARK.Prove

IVC verifier

NARK.Verify

π_x,i

π_w,i

a_x,i

a_w,i

w_i

overview: constructions

overview: constructions

overview: constructions

z_i

z_i+1

w_i

w_i+1

F_j (w_i,z_i) = z_i+1

non-uniform IVC (NIVC)

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

pc_i+1

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

π_i

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

π_i+1

pc_i+1

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

π_i

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

π_i+1

pc_i+1

u_i claims the correctness of the i^th step

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

π_i

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

π_i+1

pc_i+1

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1

u_i claims the correctness of the i^th step

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

π_i

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

π_i+1

pc_i+1

u_i claims the correctness of the i^th step

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

π_i

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

π_i+1

u_i+1

pc_i+1

u_i claims the correctness of the i^th step

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

π_i

. . .

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

U_i[j]

. . .

π_i+1

. . .

u_i+1

U_i+1[j]

. . .

pc_i+1

u_i claims the correctness of the i^th step

U_i[j] attests to all prior i -1 iterations of F'_j

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1

overview: constructions

overview: constructions

overview: constructions

non-uniform IVC (NIVC)

π_i

. . .

pc_i

z_i

F'_j

z_i+1

w_i

w_i+1

U_i[j]

. . .

π_i+1

. . .

u_i+1

U_i+1[j]

. . .

pc_i+1

verifier:

​

• φ(w_i,z_i, pc_i) = pc_i+1
• check that U_i, pc_i are contained in�public output of u_i
• fold u_i into U_i[pc_i ]

u_i claims the correctness of the i^th step

U_i[j] attests to all prior i -1 iterations of F'_j

agenda

1. overview
1. motivation
2. constructions

​

1. comparison
1. recursion threshold
2. zero-knowledgeness
3. support for lookup arguments
4. security and cryptographic assumptions
1. future work
1. tooling & interfaces
2. benchmarking
3. standards & specifications

comparison: implementations

shrinking proof size

IVC / PCD

full recursion

accumulation scheme / folding

• plonky3
• Miden
• RISC Zero

• Mina
• Nova

• plonky2 gnark verifier
• halo2 FRI gadget
• Polygon Hermez

comparison: recursion threshold

comparison: recursion threshold

comparison: recursion threshold

taken from Nico Mohnblatt’s presentation

comparison: recursion threshold

taken from Nico Mohnblatt’s presentation

comparison: recursion threshold

taken from Nico Mohnblatt’s presentation

need additively homomorphic commitments!

comparison: security & cryptographic assumptions

U_i-2

fold

u_i-2

U_i-1

comparison: security & cryptographic assumptions

U_i-2

fold

u_i-2

U_i-1

u_i-1

comparison: security & cryptographic assumptions

fold

U_i-2

fold

u_i-2

U_i-1

u_i-1

comparison: security & cryptographic assumptions

U_i-2

U_i-1

U_i

fold

fold

u_i-2

u_i-1

u_i

comparison: security & cryptographic assumptions

U_i-2

U_i

fold

fold

u_i-2

u_i-1

u_i

what if i provide a random U’ instead?

U_i-1

comparison: security & cryptographic assumptions

U_i-2

U_i

fold

fold

u_i-2

u_i-1

u_i

U_i-1

.x = H(U_i-1)

check that u_i-1 involved a fold which produced U_i-1

what if i provide a random U’ instead?

comparison: security & cryptographic assumptions

U_i-2

U_i

fold

fold

u_i-2

u_i-1

U_i-1

.x = H(U_i-1)

check that u_i-1 involved a fold which produced U_i-1;

load new folding result U_i into new instance u_i.

u_i.x = H(U_i)

what if i provide a random U’ instead?

comparison: security & cryptographic assumptions

U_i+1

fold

u_i+1.x = H(U_i+1)

U_i-2

U_i-1

U_i

fold

fold

u_i-2.x = H(U_i-2)

u_i-1.x = H(U_i-1)

u_i.x = H(U_i)

check that u_i-1 involved a fold which produced U_i-1;

load new folding result U_i into new instance u_i.

this forms a hash chain ⇒ incremental computation

U_i+1

fold

u_i+1.x = H(U_i+1)

U_i-2

U_i-1

U_i

fold

fold

u_i-2.x = H(U_i-2)

u_i-1.x = H(U_i-1)

u_i.x = H(U_i)

these are in the wrong field!

U_i+1

fold

u_i+1.x = H(U_i+1)

U_i-2

U_i-1

U_i

fold

fold

u_i-2.x = H(U_i-2)

u_i-1.x = H(U_i-1)

u_i.x = H(U_i)

these are in the wrong field!

let’s use elliptic curve cycles

U_i⁽²⁾

fold

u_i⁽¹⁾.x = H₁(U_i⁽²⁾)

U_i-1⁽²⁾

U_i-1⁽¹⁾

fold

fold

u_i-2⁽²⁾.x = H₂(U_i-2⁽¹⁾)

u_i-1⁽¹⁾.x = H₁(U_i-1⁽²⁾)

u_i-1⁽²⁾.x = H₂(U_i-1⁽¹⁾)

let’s use elliptic curve cycles

(and superscript by cycle index)

U_i-2⁽²⁾

U_i-2⁽¹⁾

U_i⁽²⁾

fold

u_i⁽¹⁾

U_i-1⁽²⁾

U_i-1⁽¹⁾

fold

fold

u_i-2⁽²⁾

u_i-1⁽¹⁾

u_i-1⁽²⁾

let’s use elliptic curve cycles

(and superscript by cycle index)

(and reformat for readability)

U_i-2⁽²⁾

U_i-2⁽¹⁾

.x = H₂(U_i-2⁽¹⁾)

.x = H₁(U_i-1⁽²⁾)

.x = H₂(U_i-1⁽¹⁾)

.x = H₁(U_i⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_i-2⁽²⁾

U_i-2⁽¹⁾

.x = H₂(U_i-2⁽¹⁾)

.x = H₁(U_i⁽²⁾)

no access to U_i-1⁽²⁾, can’t check hash

U_i-1⁽¹⁾

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_i-2⁽²⁾

U_i-2⁽¹⁾

.x = H₂(U_i-2⁽¹⁾)

.x = H₁(U_i⁽²⁾)

no access to U_i-1⁽²⁾, can’t check hash

U_i-1⁽¹⁾

“copy” over to next curve!

.x = H₁(U_i-1⁽²⁾)

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = u_i-1⁽¹⁾.x

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_i-2⁽²⁾

U_i-2⁽¹⁾

.x = H₂(U_i-2⁽¹⁾)

.x = H₁(U_i⁽²⁾)

U_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = u_i-1⁽¹⁾.x₁

.x₀ = u_i-2⁽²⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

“copy” over to next curve!

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_i-2⁽²⁾

U_i-2⁽¹⁾

.x₁ = H₂(U_i-2⁽¹⁾)

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = u_i-2⁽²⁾.x₁

.x₀ = u_i-2⁽¹⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i-1⁽²⁾.x₁

fold

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_i-2⁽²⁾

U_i-2⁽¹⁾

.x₁ = H₂(U_i-2⁽¹⁾)

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = u_i-2⁽²⁾.x₁

.x₀ = u_i-2⁽¹⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i-1⁽²⁾.x₁

U_i⁽¹⁾

.x₀ = u_i⁽¹⁾.x₁

u_i⁽²⁾

.x₁ = H₂(U_i⁽¹⁾)

fold

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_i-2⁽²⁾

U_i-2⁽¹⁾

.x₁ = H₂(U_i-2⁽¹⁾)

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = u_i-2⁽²⁾.x₁

.x₀ = u_i-2⁽¹⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i-1⁽²⁾.x₁

U_i⁽¹⁾

.x₀ = u_i⁽¹⁾.x₁

u_i⁽²⁾

.x₁ = H₂(U_i⁽¹⁾)

fold

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_⟂⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_⟂⁽¹⁾

.x₁ = H₂(U_i-2⁽¹⁾)

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = H₂(U_⟂⁽¹⁾)

.x₀ = u_i-2⁽¹⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i-1⁽²⁾.x₁

U_i⁽¹⁾

.x₀ = u_i⁽¹⁾.x₁

u_i⁽²⁾

.x₁ = H₂(U_i⁽¹⁾)

U_i-2⁽²⁾

fold

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_⟂⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_⟂⁽¹⁾

.x₁ = H₂(U_i-2⁽¹⁾)

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = H₂(U_⟂⁽¹⁾)

.x₀ = u_i-2⁽¹⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i-1⁽²⁾.x₁

U_i⁽¹⁾

.x₀ = u_i⁽¹⁾.x₁

u_i⁽²⁾

.x₁ = H₂(U_i⁽¹⁾)

U_i-2⁽²⁾

fold

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_⟂⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

fold

u_i-2⁽²⁾

U_⟂⁽¹⁾

.x₁ = H₂(U_i-2⁽¹⁾)

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_⟂⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = H₂(U_⟂⁽¹⁾)

.x₀ = u_i-2⁽¹⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i-1⁽²⁾.x₁

U_i⁽¹⁾

.x₀ = u_i⁽¹⁾.x₁

u_i⁽²⁾

.x₁ = H₂(U_i⁽¹⁾)

U_i-2⁽²⁾

fold

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold

U_⟂⁽¹⁾

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_⟂⁽¹⁾)

.x₀ = u_i-2⁽²⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i-1⁽²⁾.x₁

U_i⁽¹⁾

.x₀ = u_i⁽¹⁾.x₁

u_i⁽²⁾

.x₁ = H₂(U_i⁽¹⁾)

U_i⁽¹⁾

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

U_i⁽²⁾

fold

fold

U_i-2⁽¹⁾

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = u_i-2⁽²⁾.x₁

u_i⁽²⁾.x₀ = H₁(U_i⁽²⁾) was not checked!

.x₀ = u_i⁽¹⁾.x₁

.x₁ = H₁(U_i⁽²⁾)

u_i⁽¹⁾

.x₀ = u_i-1⁽²⁾.x₁

U_i⁽¹⁾

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

U_i⁽²⁾

fold

fold

U_i-2⁽¹⁾

U_i-1⁽¹⁾

u_i-1⁽²⁾

U_i-1⁽²⁾

u_i-1⁽¹⁾

.x₁ = H₂(U_i-1⁽¹⁾)

.x₀ = u_i-2⁽²⁾.x₁

u_i⁽²⁾.x₀ = H₁(U_i⁽²⁾) was not checked!

instead, u_i⁽¹⁾.x₁, u_i⁽²⁾.x₁ were checked

.x₁ = H₁(U_i⁽²⁾)

.x₀ = u_i⁽¹⁾.x₁

u_i⁽¹⁾

.x₀ = u_i-1⁽²⁾.x₁

fold

.x₀ = u_i-1⁽¹⁾.x₁

.x₁ = H₁(U_i-1⁽²⁾)

U_i⁽²⁾

fold

u_i⁽¹⁾

fold