optimize LogUp challenge in IVC

background

In pull-request read-write lookup offline-memory-checking logUp-based implementation in (Super)Nova R1CS discussion, one of remains question is to optimise the cost of random oracle circuit in IVC. This post try to address the issue and propose a design.

Design rationale

One of the nice property to derive challenge via random oracle in folding IVC is we can decouple random oracle into function composition, and relax one or more of function to loose property, e.g. one of them not nessesary to satisify indifferentiable from a random oracle, while still keep overall composition result indifferentiable from random oracle. With relaxation, we implement relaxed function in IVC step circuit, while in the final SNARK pass accumuation result to another random oracle function to get the challenge which indifferentiable from random oracle.

Random Oracle

Terminology cited from Proving the correct execution of concurrent services in zero-knowledge

Giving

$\mathfrak{H}=\varphi (R(x))$,

with below

• $x\in {\mathbb{F}}^n$
• $R:{\mathbb{F}}^n\to \mathbb{F}$ is collision resistent encoding

R even can be non-uniform, and not indifferentiable from a random oracle

• $\varphi :\mathbb{F}\to \mathbb{F}$ is random oracle

Then

$\mathfrak{H}$ is random oracle

reference proof https://hackmd.io/@2DQ_BR_sTUOyIfPms3lGVw/r1TNUj8q6

collision resistent encoding function R design

In each step circuit, we know how many read/write it will have. Per read/write we need to encoding

$(a,v_{prev},v,t_{prev},t)$ 5 field elements and accumulated with prev acc value to obtain new acc and pass to next round.

To design a collision resistent hash, and with idea from pedersen hash, we can design as below: in setup phase we can pre-generate random ordered-set field values

$[f_0,f_1,...f_n]$, for

$f_0,f_2,...f_n\in \mathbb{F}$.

In zkVM setting, one step circuit in SuperNova might represent one opcode. Each opcode read/write are bounded. Giving max read/write num is

$k$,

$n=5\times k$.

Question:

$f_i$ need to be prime?

Giving

$(a,v_{prev},v,t_{prev},t)$, we decompose each field value into bit decomposition and concat all as

$bits$ = bit(

$a$) || bit(

$v_{prev}$) || bit(

$v$) || bit(

$t_{prev}$) || bit(

$t$)

Then we can encode batched field values

$(a,v_{prev},v,t_{prev},t)$ into an order matter single field value, assume bit concated value lead to j bits

$$acc=ac{c}_{prev}+R(bits,[f_i])=ac{c}_{prev}+{\mathrm{\Sigma }}_{i=0}^j{b}_i\times f_i$$ where

$b_i$ is the bit value of

$bits$ in index

$i$

In R1CS, This formula can be represented in just 1 R1CS constraint.

collision resistent encoding on batched read/write in a single step

To encode batched of read/write in step circuit, it's naturally viewing it as encoding vector

$(a_0,v_{0,prev},v_0,t_{0,prev},t_0,a_1,v_{1,prev},v_1,t_{1,prev},t_1,...)$ from its bits representation

$bits$ = bit(

$a_0$) || bit(

$v_{0,prev}$) || bit(

$v_0$) || bit(

$t_{0,prev}$) || bit(

$t_0$) || bit(

$a_1$) || bit(

$v_{1,prev}$) || bit(

$v_1$) || bit(

$t_{1,prev}$) || bit(

$t_1$) || …

Notice with these design, it retain the order matters feature, such that if we exchange any 2 field value from vector it lead to different encoding field value.

So the length of pre-generated constant random field set

$[f_i]$ need to cover max bits length in step circuit.

collision resistent encoding order matters across steps

For encoded acc value we can passed it to next step to aggregate to next acc value. However we need to account for one order matters scenario.

Giving vector folding step m

$(v_{m,0},v_{m,1},...)$

and step n = m+1

$(v_{n,0},v_{n,1},...)$

Then

$$acc=ac{c}_{prev}+R(bit{s}_m,[f_i])+R(bit{s}_n,[f_i])$$

When a unhonest prover exchange 2 field value in different step yet same position, e.g.

$v_{m,1}$ with

$v_{n,1}$, then the new acc value will remain unchanged, imply function R is not collision resistent with order matter.

To address this issue, we introduce step variable into accumulation formula as

$$acc=ac{c}_{prev}\times c+R(bits,[f_i])$$

where

$c\in F$ represent current

$c_{th}$ folding step in Nova, and

$c$ starting from 1.

Another alternative design is

$ac{c}_{prev}^c$, to raise

$ac{c}_{prev}$ to power

$c$

R collision resistent analysis

Below we will infer the probability for such collision exist

define

• prime field
  $\mathbb{F}$ with
  $p$ bits prime
• $n!=1\times 2\times 3...\times n$
• m < n,
  $(m,n)!=m\times (m+1)\times (m+2)...\times n$
• $l$ is max bit length of read/write absortion
• $[f_i]$ is the pseudorandom generated fields set,
  $f_i\in \mathbb{F},i\in l$
• $N$ is total number of folding steps

base case

$l$=2

To prove R is collision resistent, firstly we analyze

$l$ = 2 case, and

$[f_1,f_2]$ field set

Then it's equivalent to find

$k_i\in \mathbb{F},k_i>0$, such that

$k_1\times f_1+k_2\times f_2=0\to k_1=neg(k_2\times f_2)\times f_1^{-1}$

Giving Encoding function R

$$acc=ac{c}_{prev}\times c+R(bits,[f_i]),c\in [1..N]$$

And define set

$S=\{(m,N)!|m\in [1...N]\}$, subset

$S^{\prime }\subset S$

Let

$$k^{\prime }=\sum _{a_i\in S^{\prime },S^{\prime }\subset S}{a}_i$$

Subset

$S^{\prime }$ got

$2^N$ choices, each can derived respective

$k^{\prime }$. So there are

$2^N$ possible

$k^{\prime }$.

It implies for

$k_2$ we have

$2^N$ choice, after

$k_2$ settle down,

$k_1$ so got

$2^N$ choice.

The probability for

$k_1,k_2$ overlapping (collision) is

$$\frac{2^N+2^N}{2^p}$$

For example, giving folding steps

$N=2^{10}$.

$p$ is 255 bit. Then the probability for collision exist

$2^{11-255}$

General case

$l$ > 2

For

$l$ > 2, it is equivalent to find

$\mathrm{\exists }k>0$, such that

$$k_1\times f_1+k_2\times f_2+k_3\times f_3+...+k_l\times f_l=0$$

We can rewrite as

$$k_1=neg(k_2\times f_2+k_3\times f_3+...+k_l\times f_l)\times f_1^{-1}$$

Combination of

$k_2,k_3,k_4,...,k_l$ lead to

$$2^{(l-1)\times N}$$

choice.

Similarly,

$k_1$ also got

$2^N$ choice

And the probability for collision exist is

$$\frac{2^N+2^{(l-1)\times N}}{2^p}$$

other notes

Speical notice above analysis just prove the probability of collision exist. We still need to search solition space and verify to find it. To verify a candidate, we need to do efficient factorial decomposition, means given

$k$, find

$b_1,b_2,b_3,...b_N\in [0,1]$ such that

$$k=\sum _{i\in N}{b}_i\ast i!$$

naive bruce-force search take

$O(2^N)$ time complexity, not sure is there any efficient other algorithm .

Cost analysis for R function in step circuit

Giving example

• address
  $a$ max 32 bits, accounting for 4G address
• value
  $v$ max 64 bits.
• max read-write ts across folding is 32 bits.
• max folding step is 64 bits

Then in R1CS

name	Decomposition into Bits	collision resistent R
#R1CS constraints	32 + 1 from address a 64 + 1 from value v 32 + 1 from ts 33 + 65 x 2 + 33 x 2 = 229. giving k reads/writes overall cost 229 x k	1
#R1CS vars	32 from address a bit 64 from value v bits 32 from ts bits 32 + 64 x 2 + 32 x 2 = 224 Giving k reads/writes, overall cost 224 x k	1

So the overall challenge cost are growing linear with number of read/write in step circuit, while still remain agnostic to table size |T|

random oracle in final SNARK

We can choose any random oracle candidate

$\varphi$ e.g. poseidon hash in final SNARK.

The final challenge (r,

$\gamma$)

$$r=\varphi (final\mathrm{\_}acc)=$$

and

$$\gamma =\varphi (r)$$