# Threshold Plume Nullification

> Author: Mike - December 2024
>
> This is Mike's experimental maths. There are no security proofs.
> There's some hand-waving. No one's looked at it.

---

[Plume](https://eprint.iacr.org/2022/1255) enables a user to nullify a note, without passing their nullifier secret key into the circuit.

This Threshold Plume idea enables a collection of people to agree to generate the nullifier for a given note.

More precisely, a group of `n` people are given secret shares of some nullifier secret key. If at least `t` of them (where `t` <= `n`) come together, they can generate the nullifier for a given note, _without ever learning the shared nullifier secret_. Let's call it `(n, t)`-threshold plume nullification.

This has the following features:
- A dumb Aztec smart contract can be given a sense of "ownership" of notes, enabling escrow use cases. (Technically it's the group of `n` people whose shared public key "owns" the notes, but if you squint, you can think of this as a good approximation of the smart contract owning the notes).
- A collection of `t` people can come together to nullify a note.
- A smart contract's "plume verifier" function looks identical to the one-player plume verifier function, which is very clean.

We piggy-back on [FROST](https://eprint.iacr.org/2020/852.pdf), to achieve this. Other threshold schnorr schemes could be used as a basis, similarly.

Basically, in the same way that a Schnorr signature scheme can be extended to be a threshold scheme, we can copy that approach and extend a Chaum-Pedersen scheme to be a threshold scheme (Plume is like a Chaum-Pedersen proof in the context of nullification).

---

## Plume

Here I quickly explain Plume, in order to establish the notation that will be used in the Threshold explanation further below. All hail additive notation. The choice of letters is to align with [FROST](https://eprint.iacr.org/2020/852.pdf), rather than with [Plume](https://eprint.iacr.org/2022/1255), because it'll make it easier to follow all the threshold stuff below.

> Edit after writing: There's also some Aztec stuff bleeding into this explanation (like using the base field for scalars instead of the scalar field) - don't get too tied up in that because it's not important for achieving threshold plume - I don't want it to detract from the main ideas I want to convey in this doc.

### Notation

Additive notation.

A dot $\cdot$ is used for field multiplication and group scalar multiplication. The context should make it clear.

I try to reserve capital letters be points, so lower-case letters are for everything else (like field elements).

$q$ is used for base field moduli.
$r$ is used for scalar field moduli.
$_{gr}$ is for grumpkin.
$_{bn}$ is for altBN-254.
The size of a Noir native field is $|\texttt{Field}|$.
$|\texttt{Field}| = q_{gr} = r_{bn} < q_{bn} = r_{gr}$.
$G \in \mathbb{G}_{gr}$ a grumpkin generator point.

> Edit after writing: In Aztec, we like to work with elements in $\texttt{Field} = \mathbb{F}_{q_{gr}}$. Even Grumpkin secret keys (which should technically be part of the Grumpkin scalar field $\mathbb{F}_{r_{gr}}$), are derived as the output of snark-friendly hashing, so are elements of $\mathbb{F}_{q_{gr}}$. This results in a negligible reduction in security, in exchange for fewer constraints.
>
> Below, we'll often define secret keys as an element of $\mathbb{F}_{q_{gr}}$, because it's efficient to derive secrets as the output of a snark-friendly hash, which outputs an element of $\mathbb{F}_{q_{gr}}$.
>
> We'll then use such secret keys in scalar multiplications with Grumpkin points.
> Strictly speaking, such scalars in Grumpkin scalar multiplication should be in $\mathbb{F}_{r_{gr}}$.
> A potential consequence of using elements of $\mathbb{F}_{q_{gr}}$ as secret keys could be that the resulting public keys are not uniformly-distributed in the Grumpkin group, so we should check this.
> From an old chat with Patrick: The distribution of such public keys will have a statistical distance of $\frac{2(r - q)}{r}$ from uniform.
> It turns out that $\frac{1}{2^{126}} < \frac{2(r - q)}{r} < \frac{1}{2^{125}}$, so the statistical distance from uniform is broadly negligible, especially considering that the AltBN254 curve has fewer than 125-bits of security.

$H2C: \mathbb{F}_{q_{gr}} \to \mathbb{G}_{gr}$ a hash-to-curve function.
$h: \mathbb{F}^?_{q_{gr}} \to \mathbb{F}_{q_{gr}}$ the poseidon2 hash, which is efficient in Noir.

We define a field conversion function $f_{r_{gr}}: \mathbb{F}_{q_{gr}} \to \mathbb{F}_{r_{gr}}$ to help us cheekily scalar-multiply grumpkin points by elements of the grumpkin base field. It's a nice lossless mapping, since $q_{gr} < r_{gr}$.

### Keys

Secret key: $$s \in \mathbb{F}_{q_{gr}}$$

Public key:

$$
\begin{align}
Y &:= f_{r_{gr}}(s) \cdot G \\
\end{align}
$$

for a generator $G \in \mathbb{G}_{gr}$.

### Nullifier

With plume, the prover provides a nullifier $N$ to the circuit, with a dleq proof that the correct discrete log $s$ was used relative to $Y$.

> In Aztec, the Plume message $m$ will always be a commitment to a note.

For a note hash $m \in \mathbb{F}_{q_{gr}}$, its nullifier $N$ is defined as follows:

$H := H2C(m, Y)$

$N = s \cdot H$

### Prover

To prove correct derivation of the nullifier, relative to $m$, $Y$:

The user computes:

$Y := s \cdot G$
$N := s \cdot H$
$R := k \cdot G$, for random $k \in \mathbb{F}_{r_{gr}}$
$R' := k \cdot H$

Challenge $c = h(G, H, Y, N, R, R') \in \mathbb{F}_{q_{gr}}$

> Notice the lazy notation: technically, $h()$ takes elements of $\mathbb{F}_{q_{gr}}$, and I'm lazily passing points into this function, because it's more legible and less to write. I do that all over the place. Mentally replace these points with some serialization of these points.

$z = k - f_{r_{gr}}(s) \cdot f_{r_{gr}}(c) \mod r_{gr}$

Share: $N, R, R', z$. The values $Y, m, G$ are known to the verifier already.

### Verifier

The verifier (the snark circuit) does:

$H = H2C(m, Y)$

Challenge $c = h(G, H, Y, N, R, R') \in \mathbb{F}_{q_{gr}}$

Assert: $R == z \cdot G + f_{r_{gr}}(c) \cdot Y$
Assert: $R' == z \cdot H + f_{r_{gr}}(c) \cdot N$

If these checks pass, the nullifier is $N$.

---

## Threshold Plume

I'm going to try to align notation to [FROST](https://eprint.iacr.org/2020/852.pdf) instead of Plume, since FROST is a lot more involved, so hopefully it can be more-easily compared side-by-side with FROST. The new Plume stuff is highlighted in $\color{red}{red}$.

### Notation

We use additive notation. Elliptic curve points are (mostly) capital letters.

$n$ - # potential signing participants.
$t$ - threshold # signing participants.
$i$ - participant identifier for participant $P_i$, $i \in {1,...,n}$
$P_i$ - the $i$-th participant.
$G$ - a generator point in $\mathbb{G}$
$s_i$ - the secret share for $P_i$.
$Y_i = s_i \cdot G$.
$\alpha$ is the number of participants who choose to sign ($t \leq \alpha \leq n$).
$Y$ - the group's public key, for the particular group of $\alpha$ participants who choose to sign.
$S = {p_1,...,p_{\alpha}}$ the set of participant identifiers for the $\alpha$ participants who choose to sign.
$\lambda_i = \prod_{j = 1, j \neq i}^{\alpha} \frac{p_j}{p_j - p_i}$ - the Lagrange coefficient that participant $P_i$ will use to interpolate over $S$.

> Some notes:
> The fiat-shamir challenges could be slightly incorrect at the mo, e.g. missing data that should be included, or including superfuous data. The ordering of data in those hashes is also inconsistent and gross at the moment.

### KeyGen

#### Round 1

Here, we establish for each $P_i$: their secret share $s_i$; the corresponding public key $Y_i$, and the group's shared public key $Y$.

1. Each $P_i$:
- Samples $t$ random values $a_{i,0},...,a_{i,(t-1)} \in \mathbb{F}$.
- Derives poly $f_i(x) = \sum_{j=0}^{t-1} a_{i,j} \cdot x^j$.
- Note: $a_{i,0} = f_i(0)$ will be $P_i$'s secret share _for this KeyGen process only; not for the later signing process_.
2. $P_i$ _commits_ to the coefficients $\{a_{i,j}\}_{j\in\{0..(t-1)\}}$ by computing a vector $\vec{C}_i = [\phi_{i,0},...\phi_{i,(t-1)}]$, where $\phi_{i,j} := a_{i,j} \cdot G$.
3. $P_i$ computes a proof of knowledge of discrete log, $\sigma_i$, for their shared secret $a_{i,0}$, relative to commitment $\phi_{i,0}$.
- $k \gets \mathbb{F}$ random.
- $R_i = k \cdot G$
- $c_i = h(i, \Phi, \phi_{i,0}, R_i)$, where $\Phi$ is some contextual data.
- $\mu_i = k + a_{i,0} \cdot c$
- $\sigma_i = (R_i, \mu_i)$
4. $P_i$ broadcasts the vector $\vec{C}_i$ and the pok $\sigma_i$ to all other participants.
5. Upon receiving $(R_l, \mu_l)$ from all other participants $1 \leq l \leq n$, $l \neq i$, participant $P_i$ verifies $\sigma_l$ by computing $c_l$ and checking $R_l \stackrel{?}{=} \mu_l \cdot G - c_l \cdot \phi_{l,0}$. If successful, $\sigma_l$ can then be discarded, and $\vec{C}_i$ retained for the next round.

#### Round 2

Each participant $P_i$ now has $n$ vectors $\{ \vec{C}_l \}_{l \in \{1,...,n\}}$.

1. Each $P_i$ evaluates their secret poly $f_i(x)$ at the identifiers of all other participants. That is, $P_i$ computes Shamir secret shares $\{ f_i(l) \}_{l \in \{1,...,n\}}$ and sends $(l, f_i(l))$ to participant $P_l$.
- This means each $P_i$ receives $\{ f_l(i) \}_{l \in \{1,...,n\}}$ altogether.
- $P_i$ keeps $f_i(i)$ secret, to themselves.
2. Each $P_i$ verifies their received shares $\{ f_l(i) \}_{l \in \{1,...,n\}}$:
- $f_l(i) \cdot G \stackrel{?}{=} \sum_{k=0}^{t-1}i^k \cdot \phi_{l,k}$
- (Note, by defn: $f_l(i) = \sum_{k=0}^{t-1}a_{l,k} \cdot i^k$, but $P_i$ doesn't have access to the underlying $a_{l,k}$'s; only to their commitments $\phi_{l,k}$.)
3. **Finally, we can compute $P_i$'s long-lived secret share $s_i$** as:
- $s_i = \sum_{l=1}^{n} f_l(i)$
4. **And we can compute $Y_i, Y$**:
- $Y_i = s_i \cdot G$, participant $P_i$'s public key (or "public verification share").
- $Y = \sum_{l=1}^{n} \phi_{l,0}$, the group's public key.
- It's worth noting, that by design, no one knows the discrete log of $Y$. It is technically equal to $s = \sum_{l=1}^{n} a_{l,0}$, but no one divulges their $a_{l,0}$.

> **Discard the meanings of $k, R_i, c_i, \sigma_i$**; those letters will be used again in a different way below.

### Signing

#### Preprocessing

Each signature requires a nonce. The group precomputes a list of nonces ahead of time. They can repeat this step whenever they run out of fresh nonces.

$\pi$ - the number of fresh nonces we want to create.
$L_i$ - the contribution from participant $P_i$ towards the; a list of nonces that we will populate here.

1. $P_i$ initialises a list $L_i$. For $j$ in ${1,...,\pi}$:
a. Sample single-use nonces $(d_{i,j}, e_{i,j}) \gets \mathbb{F} \times \mathbb{F}$. These nonces are _secret_ to $P_i$.
b. $(D_{i,j}, E_{i,j}) = (d_{i,j} \cdot G, e_{i,j} \cdot G)$.
c. $P_i$ stores $d_{i,j}, e_{i,j}, D_{i,j}, E_{i,j}$ for later, to use when signing.
d. Push $(D_{i,j}, E_{i,j})$ to the list $L_i$.
2. Publish $L_i$; the list of all committed one-time-use pairs of nonce shares that $P_i$ has generated.

#### Sign

Let SA be the **signature aggregator**.
SA can be anyone, including one of the $P_i$'s.

Recall:
- $S = {p_1,...,p_{\alpha}}$ is the set of participant identifiers for the $\alpha$ participants who choose to sign.
- $s_i$ is $P_i$'s long-living secret share.
- $Y$ is the group public key.

$h_1, h_2$ are hash functions to $\mathbb{F^*}$.

Suppose we have a message $m$ (a note hash, in the context of plume nullification).

Let $\color{red}{ H = H2C(m, Y) \in \mathbb{G} }$ be the point generated by hashing the message and the group's public key, as explained in Plume.

In the KeyGen step, the participants computed a shared public key $Y$ wrt G. For Plume, they also need to compute a shared nullifier $\color{red}{N}$ wrt $\color{red}{H}$. Luckily, we don't need as much communication as the KeyGen step, because we don't need to establish any more shared secrets.

Recall that $Y = \sum_{l=1}^{n} \phi_{l,0}$; a sum that is contributed-to by _all_ $n$ participants. This poses a problem when we think about threshold nullification. We don't want $n$ contributors; we want only $\alpha$ participants (where $t \leq \alpha \leq n$) to compute a nullifier $N$ for any given message. Thankfully, we can make use of the trick to convert an additive secret into a Shamir secret.

$Y = \sum_{l=1}^{n} \phi_{l,0} = \sum_{l=1}^{n} a_{l,0} \cdot G = \sum_{l=1}^{n} f_l(0) \cdot G = \sum_{j \in S} (f_j(0) \cdot \lambda_j) \cdot G$. (That final equality is not obvious; see the appendix).

So $Y$ _can_ actually be expressed as a sum which is only contributed-to by the $\alpha$ signers. Hence we can similarly derive our nullifier $N$ in this way, so that it too can only be contributed-to by the $\alpha$ signers:

$\color{red}{ N = \sum_{j \in S} (f_j(0) \cdot \lambda_j) \cdot H }$

In the preprocessing step, SA was given lists $\{ L_i \}_{i \in \{1..n\}}$.

SA pops the next nonce pair from the list of each of the $\alpha$ participants who will partake in this next signing operation:

$B = [(i, D_i, E_i)]_{i \in S}$.

But we need nonce commitments that not only relate to $G$, but also to $\color{red}{H}$. So we need to repeat some of the preprocessing stuff, but at signature time, for this specific $\color{red}{H}$. You'll see this in the steps below.

1. SA constructs $B$.
- They also compute $\color{red}{ H = H2C(m, Y)}$
3. For each $i \in S$, SA sends $P_i$ the tuple $(m, B, \color{red}{H})$.
- "Here's the message $m$. I have popped these nonces $B$ as the collection of nonce pairs (collected from all to-be signers of this message). You will need this information to perform your part in signing".
4. Given $(m, B, \color{red}{H})$, each $P_i$ validates $m$ (out of scope of this doc), and checks $(D_l, E_l)$ for every element of $B$, as follows:
- $P_i$ must also generate nonces specific to $\color{red}{H}$:
- $\color{red}{ (D'_i, E'_i) = (d_i \cdot H, e_i \cdot H) }$
- $\color{red}{TODO}$: $P_i$ needs to prove to SA that the same $d_i, e_i$ were used to compute $(D'_i, E'_i)$, as were used for $D_i, E_i$. This is simple, albeit a faff to write here.
- Let $\color{red}{B'}$ be defined like $B$, but for the nonces $\color{red}{ (D'_i, E'_i) }$ derived using $\color{red}{H}$.
5. $\rho_l = h_1(l, m, B, \color{red}{B'}, \color{red}{H})$, $\forall l \in S$.
$R_l = D_l + \rho_l \cdot E_l$
$R = \sum_{l \in S} R_l$
$\color{red}{ R'_l = D'_l + \rho_l \cdot E'_l }$
$\color{red}{ R' = \sum_{l \in S} R'_l }$
Challenge $c = h_2(R, Y, \color{red}{H, R', N}, m)$
5. $P_i$ computes their "response" to the challenge, using their long-lived secret share $s_i$, and their private discrete logs of $D_i$ and $E_i$:
- $z_i = d_i + (e_i \cdot \rho_i) + (\lambda_i \cdot s_i) \cdot c \in \mathbb{F}$.
5. NOT A STEP IN FROST:
- Recall that $Y_i := s_i \cdot G$.
- Compute the corresponding $\color{red}{ N_i := s_i * H}$.
- $P_i$ can provide to the SA a dleq proof that $\color{red}{N_i}$ and $Y_i$ share the same discrete log $s_i$:
- $\color{red}{k_i \gets \mathbb{F}}$ random
- $\color{red}{Q_i := k_i \cdot G}$
- $\color{red}{Q'_i := k_i \cdot H}$
- $\color{red}{c_i = h(i, \Phi, Q_i, Y_i, H, Q'_i, N_i, m)}$
- $\color{red}{\mu_i = k_i + s_i \cdot c_i}$
- $\color{red}{\sigma_i = (Q_i, Q'_i, N_i, \mu_i)}$
7. $P_i$ deletes nonce material $d_i, e_i, D_i, E_i, D'_i, E'_i$, to ensure they don't use these values again.
$P_i$ sends $z_i, \color{red}{N_i}, \sigma_i$ to SA.
7. The signature aggregator SA does the following, to aggregate the signatures:
- For each $P_i$, verify the dleq proof $\color{red}{\sigma_i}$, as a way of verifying the correctness of $\color{red}{N_i}$:
- Re-derive: $\color{red}{c_i = h(i, \Phi, Q_i, Y_i, H, Q'_i, N_i, m)}$. Then check:
- $\color{red}{Q_i \stackrel{?}{=} \mu_i \cdot G - c_i \cdot Y_i}$
- $\color{red}{Q'_i \stackrel{?}{=} \mu_i \cdot H - c_i \cdot N_i}$
- If these checks succeed, then $N_i$ can be used to derive $N$.
- Let $\color{red}{N := \sum_{i \in S} \lambda_i \cdot N_i}$
- Notice: $\sum_{i \in S} \lambda_i \cdot N_i = \sum_{i \in S} (\lambda_i \cdot s_i) \cdot H$
- $= \sum_{l = 1}^n f_l(i) \cdot H$. This isn't obvious. See the appendix.
- Personally re-derive:
$\rho_l = h_1(l, m, B, \color{red}{B'}, \color{red}{H})$, $\forall l \in S$.
$R_i = D_i + \rho_i \cdot E_i$
$R = R = \sum_{i \in S} R_i$
$\color{red}{ R'_l = D'_l + \rho_l \cdot E'_l }$
$\color{red}{ R' = \sum_{l \in S} R'_l }$
Challenge $c = h_2(R, Y, \color{red}{H, R', N}, m)$
- Validate each response:
$R_i \stackrel{?}{=} z_i \cdot G - (c \cdot \lambda_i) \cdot Y_i$
- To see why these should be equal, expand the scalars of $G$:
- LHS: $d_i + (e_i \cdot \rho_i)$
- RHS: $(d_i + (e_i \cdot \rho_i) + (\lambda_i \cdot s_i) \cdot c) - (c \cdot \lambda_i) \cdot s_i$
- $\color{red}{ R'_i \stackrel{?}{=} z_i \cdot G - (c \cdot \lambda_i) \cdot N_i }$ (recall that $P_i$ had to especially compute and share $N_i = s_i \cdot H$).
- Compute the group's response $z = \sum_{i \in S} z_i$
- Publish $\sigma = (\color{red}{H, R', N}, R, z)$, along with $m$.

#### To verify:

Given $(\sigma = (\color{red}{H, R', N}, R, z), m)$ (and given prior knowledge of the group's public key $Y$):
- $c = h_2(R, Y, \color{red}{H, R', N}, m)$
- $R \stackrel{?}{=} z \cdot G - c \cdot Y$
- $\color{red} { R' \stackrel{?}{=} z \cdot H - c \cdot N }$

## Appendix

**Converting between additive and shamir secrets:**

The group's public key is $Y$. No one knows the discrete log, $s$, of $Y$. It is technically equal to $s = \sum_{i=1}^{n} a_{i,0}$, but no one divulged their $a_{i,0}$.

Recall from keygen:
- $f_i(x) = \sum_{j=0}^{t-1} a_{i,j} \cdot x^j$.
- $s_i = \sum_{l=1}^n f_l(i) = \sum_{l=1}^n ( \sum_{j \in S} a_{i,j} \cdot i^j )$
- $f_i(0) = a_{i,0}$.
- So since $s = \sum_{i=1}^{n} a_{i,0}$, also $s = \sum_{i=1}^{n} f_i(0)$.
- In fact, if you consider $s$ as the evaluation of some polynomial $f(x)$ at 0 (i.e. $s = f(0)$), then we can construct this polynomial $f(x)$ to be the polynomial which interpolates the sums of the $f_i(x)$ polynomials over the set $S$. I.e. interpolating the desired evaluation points: $\sum_{i=1}^{n} f_i(0), \sum_{i=1}^{n} f_i(p_1),..., \sum_{i=1}^{n} f_i(p_\alpha)$, for $S = \{p_1,...,p_\alpha\}$.
- We can use lagrange interpolation to get such an $f(x)$:
- $f(x) := \sum_{j \in S} ( \sum_{i \in S} f_i(j) )\cdot l_j(x)$
- where $l_i(x) = \prod_{j = 1, j \neq i}^{\alpha} \frac{x - p_j}{p_i - p_j}$ are Lagrange polynomials.
- Recall, the Lagrange coefficients $\{ \lambda_i \}$ are the evaluations $\{ l_i(0) \}$:
- $\lambda_i = \prod_{j = 1, j \neq i}^{\alpha} \frac{p_j}{p_j - p_i}$
- So: $f(0) = \sum_{j \in S} ( \sum_{i \in S} f_i(j) )\cdot l_j(0)$
$= \sum_{j \in S} ( \sum_{i \in S} f_i(j) )\cdot \lambda_j = \sum_{j \in S} s_j \cdot \lambda_j$
- So $s =: f(0) = \sum_{j \in S} s_j \cdot \lambda_j$
- So $Y = s \cdot G = (\sum_{j \in S} s_j \cdot \lambda_j) \cdot G$

That's a really nice result. The additive secret $s = \sum_{i=1}^{n} a_{i,0}$ (computed by all $n$ participants) can also be computed as a shamir secret $s = \sum_{j \in S} (s_j \cdot \lambda_j)$ (computed by just the $\alpha$ signers in $S$).

We use this fact to enable just the $\alpha$ signers in $S$ to compute the nullifier $N = s \cdot H = (\sum_{j \in S} s_j \cdot \lambda_j) \cdot H$. This means the nullifier can be computed by $t$ participants instead of $n$ participants, even if some of the original $n$ participants drop out. Obviously, we can't have too many drop outs; we always need $>= t$ signers. If too many of the original $n$ drop out, there are secret re-sharing schemes that can introduce new signers.

**Exploring why the final Verifier's check suffices:**

If we return to the equality that the validator checks, and explore the scalars (or "exponents" if you're used to multiplicative syntax) of $G$:

$R \stackrel{?}{=} z \cdot G - c \cdot Y$

LHS:
DL of $R$ is: $\sum_{i \in S} d_i + (e_i \cdot \rho_i)$

RHS:
DL of $z$ is: $\sum_{i \in S} d_i + (e_i \cdot \rho_i) + (\lambda_i \cdot s_i) \cdot c$
DL of $- c \cdot Y$ is: $- c \cdot (\sum_{i \in S} s_i \cdot \lambda_i)$ (from the exposition just above).

And you can see how it all cancels. Yay!