# Obfuscating Witnesses in Folded Nova Instances

In the [Nova Whitepaper](https://eprint.iacr.org/2021/370.pdf), it is explicitly stated that Nova is not Zero Knowledge (section 5.1):

> Note that Nova is not a zero-knowledge IVC scheme, as that would additionally
require an IVC proof to be zero-knowledge (in Nova’s case, an IVC proof does
not hide witnesses associated with steps of the incremental computation). This
difference is immaterial in the context of a single prover since it can use Nova’s
auxiliary zkSNARK to provide a zero-knowledge proof of knowledge of a valid
IVC proof; we leave it to future work to achieve zero-knowledge IVC

But what about multiple provers contributing to the construction of a folded Nova proof? We assert that we can take advantage of how an iteration's witness is folded into the running witness by folding two instances together for each party's contribution:
- Fold 1 (logic step): perform expected logic
- Fold 2 ([chaff](https://en.wikipedia.org/wiki/Chaff_(countermeasure)) step): use random data for private inputs, multiplex away computations out and pipe public values through to next fold

### Assertion

It is quite apparent that, given $(U_i, W_i)$ with knowledge of $(U_{i-1}, W_{i-1})$, can we recover $(u_{i-1}, w_{i-1})$. However, our assertion is:

**Given $(U_i, W_i)$ with no knowledge of $(U_{i-1}, W_{i-1})$ but knowledge of $(U_{i-2}, W_{i-2})$, we cannot recover $(u_{i-2}, w_{i-2})$. Note that $z_i$ will be the same as $z_{i-1}$**

*Note: $U_i = i-1$ invocations of folding, where $u_i$ is $i^{th}$ instance such that: $U_i ← fold(U_{i-1} + u_i)$*

### Folded Witness
$E$: "Slack"/ error vector that absorbs cross term $r · (AZ_1 ◦ BZ_2 + AZ_2 ◦ BZ_1)$
$r$: random challenge
$u$: Scalar that absorbs factor of $r$ in $CZ_1 + r^2 · CZ_2$ ($u ← u1 + r · u2$)

Compute T Normally
$T = AZ_1 ◦ B_Z2 + AZ_2 ◦ BZ_1 - u_1 * CZ_2 - u_2 + CZ_1$

Folding
$E ← E_1 + r · T + r^2 · E_2$
$r_E ← r_{E_1} + r · r_T + r^2 · r_{E_2}$
$W ← W_1 + r · W_2$
$r_W ← r_{W_1} + r · r_{W_2}$

$W_{n-2} = w_{n-2} + r_{n-2} · W_{n-3}$
$W_{n-1} = w_{n-1} + r_{n-1} · W_{n-2}$
$W_{n} = w_{n} + r_n · W_{n-1}$

Note that, accoring to Section 4.2, $r$ is defined as $r ← ρ(vk, u1, u2, \bar{T} )$.

To retrieve $w_{n-1}$, one has access to ($r_n, W_n$) and ($r_{n-2}, W_{n-2}$). It should not be reasonable to retrieve $w_{n-1}$ given only these values to work with when random elements are used in $w_{n-1}$

(proof needed)

$\dfrac{W_{n} - (w_{n} + r_n · (r_{n-1} · W_{n-2}))}{r_n} = w_{n-1}$

$\dfrac{W_{n} - (?_{w_n} + r_n · (?_{r_{n-1}} · W_{n-2}))}{r_n} = w_{n-1}$

### Forking Lemma
In section 4.1
> We prove knowledge soundness via the forking lemma (Lemma 1) by showing that the extractor can produce the initial witnesses given three accepting transcripts and the corresponding folded witnesses. Specifically, the extractor uses all three transcripts to compute $E_i$ and $r_{E_i}$ , and any two transcripts to compute $W_i$ and $r_{W_i}$ for $i ∈ \{1, 2\}$. The choice of which two transcripts does not matter due to the binding property of the commitment scheme.

For $W_i$ where $i > 2$ it appears that a prover would need to construct 3 different proofs for the same increment for an adversary to be able to extract the original witness. However, for $W_i$ where $i ∈ \{1, 2\}$, the claim is "the choice of which two transcripts does not matter due to the binding property of the commitment scheme".

In our originally proposed scheme, the origin of an IVC proof would only construct one folding proof (logic + chaff) $U_1$. Thus, we must additionally pad the start of the IVC with an additional chaff step. Since the originator will only share $U_2$, counterparties should be unable to extract the original witness when this measure is taken.