Status update & RFC: ZEC-NAM shielded airdrop protocol

After a hiatus period, the Heliax team would like to update you on the status of the Shielded Airdrop Protocol and share with you our latest reflections and plans. The goal of this post is twofold:

  1. To update you, the Zcash community, on our latest work, and
  2. To open up an opportunity for you to provide technical feedback so we can focus our efforts accordingly.

Your help can maximize the utility of our work, so we look forward to reviewing your feedback; it has a proven positive impact on this project. Throughout this post we are going to mark in with :red_circle: what we look forward to discussing with you the most.

Post Structure

This post is going to describe a Shielded Airdrop Transaction Structure as it would happen between Sapling and the Multi Asset Shielded Pool (MASP) and also Orchard and the MASP. Here we will:

  1. Point out what statements are present in the Shielded Airdrop Transaction Structure, and propose an abstract specification of such statements.
  2. Refer to an abstract specification of a Balance and Binding Signature, purposefully created for the Shielded Airdrop Protocol.
  3. Describe the an airdrop transaction structure, showing how statements and signatures are put together to create a verifiable transaction structure.
  4. Give an outlook on possible future developments.

On notation: When variables or symbols are introduced without definition, their definition follows Zcash and MASP specifications.

Historical context

A thorough review from Zcash cryptographers pointed out a flaw in the previous iteration of our protocol design, here shown as it was on Apr 3, 2024, right before it was reviewed. For context, we would like to redirect the interested reader to:

To say it briefly, our scheme revealed nullifiers of unspent zcash notes, in turn breaking non-linkability between note commitments and nullifier set. This constituted a privacy leak for Zcash users involved in the shielded airdrop protocol.

Updeted protocol requirements

For the current iteration of the Shielded Airdrop Protocol, version 2.0, we set the following requirements:

Protocol requirement 1

Fix the privacy leakage of the previous protocol design iteration.

Protocol requirement 2

Design a shielded airdrop transaction structure involving both: Zcash Orchard pool and MASP; Zcash Sapling pool and MASP.

Non membership proofs

To comply with protocol requirement 1 we introduce non-membership proofs over the Nullifier Set in our statements. After describing their functioning here, we are going to specify how they fit in the Statements later in this document. A non-membership proof is used to produce statements that guarantee that the prover knows a nullifier that does not belong to the public set of revealed nullifiers. In both Sapling and Orchard, the Nullifier Set is a set of N Field Elements:

\mathcal{N} = \mathsf{\{{nf}_1\ , {nf}_2 , ... {nf}_N\}}

Let us call \mathsf{nf_{unspent}} the nullifier of a unspent note.

Both constructions can be described as a statement in which a prover assures that given as primary input:

  1. A function over \mathcal{N}.

The prover knows the auxiliary input:

  1. \mathsf{nf_{unspent}}.

Such that:

Non-membership check: \mathsf{nf_{unspent}} \not\subset \mathcal{N}.

We discuss two approaches to a non-membership proof of this kind:

  1. One can prove that the nullifier belongs to the complement set of revealed nullfiers: since nullifiers are arbitrary finite field elements, the set of all possible non-spent nullifiers in well-defined. We refer to this as the Complement set approach.
  2. One can prove that the nullifier is different to every single nullifier of the nullfier set, treating the published nullifier effectively set as a blacklist which users prove they do not belong to. We refer to this as the Not-blacklisted approach.

:red_circle: We see both as plausible solutions, and we still have to evaluate the tradeoffs between the two.

Complement set approach

A “nullifier non-membership tree” is a Merkle tree of sorted disjoint (start, end) pairs representing the gaps between the elements of \mathcal{N}. That is, the union of the regions start…=end is exactly the complement of the set of \mathcal{N}. We call the root of such tree \mathsf{rt^{excl}}, and \mathsf{path^{excl}} a path.

The statement than assures that given a primary input:

Orchard Sapling
\mathsf{rt^{excl}} ⦂ \{ 0 .. q_{\mathbb{P}}-1 \} \mathsf{rt^{excl}} ⦂ \mathbb{B}^{[\ell_{Merkle}^{Sapling}]}

The prover knows an auxiliary input:

Orchard Sapling
\mathsf{path^{excl}} ⦂ \{ 0 .. q_{\mathbb{P}}-1 \}^{[\mathsf{MerkleDepth^{excl}}]} \mathsf{path^{excl} ⦂ \mathbb{B}^{[\ell_{Merkle}^{Sapling}][MerkleDepth^{excl}]}}
\mathsf{pos^{excl}} ⦂ \{ 0 .. 2^{\mathsf{MerkleDepth^{excl}}}\!-1 \} \mathsf{pos^{excl}} ⦂ \{ 0 .. 2^{\mathsf{MerkleDepth^{excl}}}\!-1 \}
\mathsf{start} ⦂ \{ 0 .. 2^{\mathsf{MerkleDepth^{Orchard}}}\!-1 \} \mathsf{start} ⦂ \{ 0 .. 2^{\mathsf{MerkleDepth^{Sapling}}}\!-1 \}
\mathsf{end} ⦂ \{ 0 .. 2^{\mathsf{MerkleDepth^{Orchard}}}\!-1 \} \mathsf{end} ⦂ \{ 0 .. 2^{\mathsf{MerkleDepth^{Sapling}}}\!-1 \}
\mathsf{nf_{unspent}} ⦂\{ 0 .. 2^{\ell^{\mathsf{Orchard}}_{\mathsf{scalar}}}-1 \} \mathsf{nf_{unspent}} ⦂\mathbb{B^{Y^{[\ell_{\mathsf{PRFnfSapling}}/8]}}}

Such that the following conditions hold:

  • Merkle path validity for (\mathsf{start}, \mathsf{end}) \hspace{0.5em} (\mathsf{path^{excl}}, \mathsf{pos^{excl}}) is a valid Merkle path of depth \mathsf{MerkleDepth^{excl}}, as defined in § 4.9 ‘Merkle Path Validity’ in Zcash specs, from \mathsf{excl} to the anchor \mathsf{rt^{excl}}, where \mathsf{excl} = \mathsf{MerkleCRH^{Pool}}(\mathsf{MerkleDepth^{excl}}, \mathsf{start}, \mathsf{end}).
  • Nullifier in excluded range \hspace{0.5em} \mathsf{start} \leq \mathsf{nf_{unspent}} \leq \mathsf{end}.

:red_circle: Not-blacklisted approach

The belonging of nullifier set elements to a prime order group allow us to frame a polynomial evaluation argument efficiently as a circuit satisfiability one. Such statement can be proved using Groth16 when we are concerned with Sapling and Halo 2 when we are with Orchard.

Our goal is again to prove knowledge of a nullifier such that \mathsf{nf_{unspent}} \not\subset \mathcal{N} .

Let us consider the following polynomial over the finite field that contains the revealed nullifiers:

P(X) = \prod_{i=1}^{N}(X-\mathsf{nf_{i}})

Given:

v = P(\mathsf{nf_{unspent}})
w = v^{-1}

We can construct a circuit that proves that:

  1. Polynomial evaluation v = P(\mathsf{nf_{unspent}})
  2. inverse correctness w * v = 1

Indeed, if \mathsf{nf_{unspent}} \subset \mathcal{N} then P(\mathsf{nf_{unspent}}) = 0 and it is not possible to find any w such that w * v = 1.

Airdrop nullifier

To comply with protocol requirement 1 we introduce the notion of an “airdrop nullifier”. An “airdrop nullifier” is a value derived from a note, with similar cryptographic properties to its standard nullifier. It is distinct from and unlinkable from the standard nullifier. In an Shielded Airdrop Transaction the alternate nullifier will be revealed in place of the actual note nullifier, to prevent double-claims. We also introduce an Airdrop nullifier set, which accumulates all the Airdrop nullifiers that are revealed in airdrop transactions. Airdrop nullifier are specified as:

In Sapling:
\mathsf{PRF^{nfSAir}_{nk\star}}(\rho\star) = BLAKE2s\text{-}256(\texttt{"MASP\_alt"},
\phantom{\mathsf{PRF^{nfSAir}_{nk\star}}(\rho\star) = BLAKE2s\text{-}256(}\boxed{\mathsf{LESBS2OP_{256}(nk\star)}}\boxed{\mathsf{LESBS2OP_{256}(\rho\star)}})
\mathsf{nf_{Air}^{Sapling}} = PRF^{nfSAir}_{nk\star}(\rho\star)
\phantom{\mathsf{nf_{Air}^{Sapling}}} = \mathsf{DeriveAirdropNullifier_{nk}^{Sapling}(\rho)}

:red_circle: In Orchard:
\mathcal{K}^{Airdrop} := GroupHash^{\mathbb{P}}(\texttt{"MASP:Airdrop", "K"})
\mathsf{PRF^{nfSAir}_{nk}}(\rho) = PoseidonHash(nk, \rho)
\mathsf{nf_{Air}^{Orchard}} = Extract_{\mathbb{P}}( ((PRF^{nfSAir}_{nk}(\rho) + \psi) \bmod q \cdot \mathbb{P}||\mathcal{K}^{Airdrop}+cm))
\phantom{\mathsf{nf_{Air}^{Orchard}}} = \mathsf{DeriveAirdropNullifier^{Orchard}_{nk}}(\texttt{p}, \texttt{\psi}, \mathsf{cm})

Statements

In the following statements \mathsf{old} is used to refer to the notes (eith in Sapling or Orchard) that are being you to claim an airdrop reward.

Claim Statement (Orchard or Sapling)

A valid instance of a Claim statement, \pi, assures that given a primary input:

Orchard Sapling
\mathsf{rt^{Orchard}} ⦂ \{ 0 .. q_{\mathbb{P}}-1 \} \mathsf{rt^{Sapling} ⦂ \mathbb{B}^{[\ell_{Merkle}^{Sapling}]}}
\mathsf{cv^{Orchard}} ⦂ \mathsf{ValueCommit^{Orchard}.Output} \mathsf{cv^{old} ⦂ ValueCommitment^{Sapling}.Output}
\mathsf{nf_{Air}^{Orchard} } ⦂ \{0..q_{\mathbb{P}}-1\} \mathsf{nf_{Air}^{Sapling} ⦂ \mathbb{B}^{[\ell_{PRFnfSapling}]}}
\mathsf{rk} ⦂ \mathsf{SpendAuthSig^{Orchard}.Public} \mathsf{rk ⦂ SpendAuthSig^{Sapling}.Public}
\mathcal{N} \mathcal{N}

The prover knows an auxiliary private input:

Orchard Sapling
\mathsf{path} ⦂ \{ 0 .. q_{\mathbb{P}}-1 \}^{[\mathsf{MerkleDepth^{Orchard}}]} \mathsf{path ⦂ \mathbb{B}^{[\ell_{Merkle}^{Sapling}][MerkleDepth^{Sapling}]}}
\mathsf{pos} ⦂ \{ 0 .. 2^{\mathsf{MerkleDepth^{Orchard}}}\!-1 \} \mathsf{g_d ⦂ \mathbb{J}}
\mathsf{g_d^{old}} ⦂ \mathbb{P}^* \mathsf{pk_d ⦂ \mathbb{J}}
\mathsf{pk_d^{old}} ⦂ \mathbb{P}^* \mathsf{v^{old} ⦂ \{ 0..2^{\ell_{value}} -1\}}
\mathsf{v^{old}} ⦂ { 0 .. 2^{\ell_{\mathsf{value}}}-1 } \mathsf{rcv^{old} ⦂ \{ 0..2^{\ell^{Sapling}_{scalar}} -1\}}
\text{ρ}^{\mathsf{old}} ⦂ \mathbb{F}_{q_{\mathbb{P}}} \mathsf{cm^{old} ⦂ \mathbb{J}}
\text{φ}^{\mathsf{old}} ⦂ \mathbb{F}_{q_{\mathbb{P}}} \mathsf{rcm^{old} ⦂ \{ 0..2^{\ell^{Sapling}_{scalar}} -1\}}
\mathsf{rcm^{old}} ⦂ { 0 .. 2^{\ell^{\mathsf{Orchard}}{\mathsf{scalar}}}-1 } \mathsf{\alpha ⦂ \{ 0..2^{\ell^{Sapling}_{scalar}} -1\}}
\mathsf{cm^{old}} ⦂ \mathbb{P} \mathsf{ak ⦂ SpendAuthSig.Public}
\mathsf{nf^{old}} ⦂ \{ 0 .. q_{\mathbb{P}}-1 \} \mathsf{nsk ⦂ \{ 0..2^{\ell^{Sapling}_{scalar}} -1\}}
\alpha ⦂ \{ 0 .. 2^{\ell^{\mathsf{Orchard}}{\mathsf{scalar}}}-1 \} -
\mathsf{ak}^{\mathbb{P}} ⦂ \mathbb{P}^* -
\mathsf{nk} ⦂ \mathbb{F}_{q_{\mathbb{P}}} -
\mathsf{rivk} ⦂ \mathsf{Commit^{ivk}.Trapdoor} -
\mathsf{rcv} ⦂ \{ 0 .. 2^{\ell^{\mathsf{Orchard}}{\mathsf{scalar}}}-1 \} -
\mathsf{nf_{unspent}^{old}} ⦂ \{0..q_{\mathbb{P}}-1\} \mathsf{nf_{unspent}^{old}}⦂ \mathbb{B}^{[\ell_{PRFnfSapling}]}

Such that the following conditions hold:

Orchard Sapling
Note commitment integrity \hspace{0.5em} \mathsf{NoteCommit^{Orchard}_{rcm^{old}}}(\mathsf{repr}_{\mathbb{P}}(\mathsf{g_d^{old}}), \mathsf{repr}_{\mathbb{P}}(\mathsf{pk_d^{old}}), \mathsf{v^{old}}, \text{ρ}^{\mathsf{old}}, \text{φ}^{\mathsf{old}}) \in \{ \mathsf{cm^{old}}, \bot \} \hspace{0.5em} \mathsf{NoteCommit^{Sapling}_{rcm^{old}}}(\mathsf{repr}_{\mathbb{J}}(\mathsf{g_d}), \mathsf{repr}_{\mathbb{J}}(\mathsf{pk_d}), \mathsf{v^{old}} )
Merkle path validity Either \mathsf{v^{old} = 0} or (\mathsf{path}, \mathsf{pos}) is a valid Merkle path of depth \mathsf{MerkleDepth^{Orchard}}, as defined in § 4.9 ‘Merkle Path Validity’, from \mathsf{cm^{old}} to the anchor \mathsf{rt^{Orchard}}. Either \mathsf{v^{old} = 0}, or \mathsf{(path, pos)} is a valid Merkle Path of depth \mathsf{MerkleDepth^{Sapling}}, as defined in the original Sapling specification, from \mathsf{cm_{u}=Extract_{\mathbb{J}^{(r)}}(cm^{old})} to the anchor \mathsf{rt}
Value commitment integrity \hspace{0.5em} \mathsf{cv} = \mathsf{ValueCommit^{Orchard}_{rcv}}(\mathsf{v^{old}}). \hspace{0.5em} \mathsf{cv^{old}} = \mathsf{ValueCommit^{old}_{rcv}}(\mathsf{v^{old}}).
Small order checks - \hspace{0.5em} \mathsf{g_d} and \mathsf{ak} are not of small order, i.e. [h_{\mathbb{J}}]\mathsf{g_d}\neq \mathcal{O}_{\mathbb{J}} and [h_{\mathbb{J}}]\mathsf{ak}\neq \mathcal{O}_{\mathbb{J}}.
Nullifier integrity \hspace{0.5em} \mathsf{nf^{old}} = \mathsf{DeriveNullifier_{nk}}(\text{ρ}^{\mathsf{old}}, \text{φ}^{\mathsf{old}}, \mathsf{cm^{old}}). \hspace{0.5em} \mathsf{nf^{old} = PRF_{nk\star}^{nfSapling}(\rho\star)} where \hspace{2.5em} \mathsf{nk\star = repr_{\mathbb{J}}([nsk]\mathcal{H})} \hspace{2.5em} \mathsf{\rho\star = repr_{\mathbb{J}}(MixingPedersenHash(cm^{Sapling}, pos))}
Spend authority \hspace{0.5em} \mathsf{rk} = \mathsf{SpendAuthSig^{Orchard}.RandomizePublic}(\alpha, \mathsf{ak}^{\mathbb{P}}). \hspace{0.5em} \mathsf{rk = SpendAuthoritySig.RandomizePublic(\alpha, ak )}.
Diversifier address integrity \hspace{0.5em} \mathsf{ivk} = \bot or \mathsf{pk_d^{old}} = [\mathsf{ivk}]\, \mathsf{g_d^{old}} where \mathsf{ivk} = \mathsf{Commit^{ivk}_{rivk}}(\mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}^{\mathbb{P}}), \mathsf{nk}). \hspace{0.5em} \mathsf{pk_d = [ivk]g_d} where \hspace{2.5em} \mathsf{ivk = CRH^{ivk}(ak\star,nk\star)} \hspace{2.5em} \mathsf{ak\star = repr_\mathbb{J}(ak)}.
Non-membership check As defined above As defined above
Airdrop nullifier integrity \hspace{0.5em} \mathsf{nf_{Air}^{Orchard}} = \mathsf{DeriveAirdropNullifier_{nk}^{Orchard}}(\text{ρ}^{\mathsf{old}}, \text{φ}^{\mathsf{old}}, \mathsf{cm^{old}}). \hspace{0.5em} \mathsf{nf_{Air}^{Sapling} = DeriveAirdropNullifier_{nk}^{Sapling}}(\text{ρ}^{\mathsf{old}})

Output Statement

The Output Circuit is defined in § 0.12.3 ‘Output Statement (MASP)’ of the Multi-Asset Shielded Pool Specification.

Convert Statement

The Convert Statement is defined in § 0.12.5 ‘Convert Statement’ of the Multi-Asset Shielded Pool Specification.
Within the MASP protocol, the Convert Statement allows for a shileded burn-and-mint conversion between assets of different types, according to a predetermined, public, fixed ratio. Broadly speaking, in this context is used to burn a proof of ownership of zcash asset to mint an airdrop reward.

Equivalence Statement

To comply with Protocol requirement 2 we introduce the Equivalence Statement. The Equivalence Statement allows the conversion between a \mathsf{ValueCommitment} in Sapling and one in Orchard by proving they are equivalent, i.e. they are commitments to the same value.

A valid instance of the Equivalence Stament assures that given as primary input:

  1. \mathsf{cv^{Sapling} : ValueCommit^{Sapling}.Output}
  2. \mathsf{cv^{Orchard} : ValueCommit^{Orchard}.Output}

the prover knows as auxiliary input:

  1. \mathsf{v: \{0..MAX\_MONEY\}}
  2. \mathsf{rcv^{Sapling} : ValueCommit^{Sapling}.Trapdoor}
  3. \mathsf{rcv^{Orchard} : ValueCommit^{Orchard}.Trapdoor}

such that:

  1. \mathsf{cv^{Sapling} = ValueCommit^{Sapling}(rcv^{Sapling}, v)}
  2. \mathsf{cv^{Orchard} = ValueCommit^{Orchard}(rcv^{Orchard}, v)}

Notes on circuit implentation of the Equivalence Statement

  1. Such statement can be proven using either in Halo2 or Groth16.
  2. A circuit implementing the Equivalence Statement would use non-native field arithmetics.

Binding and Balance Signature

The signature specification can be found here. This part of the protocol is left unchanged from the previous protocol design iteration.

Create an Shielded Airdrop Transaction

Here we are going to mark with :green_circle: steps that are specific to Sapling and with :large_blue_circle: steps that are specific to Orchard. :green_circle: and :large_blue_circle: steps are alternative.
To create a valid Shielded Airdrop Transaction Structure an actor must:

  1. Generate a Output Description tuple \mathsf{(cv^{MASP}, cm^{MASP}, epk, C^{enc}, C^{out}, \pi_{ZKOuput})} as described in § 0.11.1 ‘Sending Notes (Sapling)’ of the MASP Specification.
    • :green_circle: Generate a Sapling Claim Description tuple \mathsf{(cv^{Sapling}, rt^{Sapling}, nf_{Air}^{Sapling}, rk^{Sapling}, \mathcal{N}, \pi_{ClaimSapling}, spendAuthSig^{Sapling})}
    • :large_blue_circle: Generate a Orchard Claim Description tuple \mathsf{(cv^{Orchard}, rt^{Orchard}, nf_{Air}^{Orchard}, rk^{Orchard}, \mathcal{N}, \pi_{ClaimOrchard}, spendAuthSig^{Orchard})}
    • :large_blue_circle: Generate a Equivalence Description tuple \mathsf{(cv^{Sapling}, cv^{Orchard}, \pi_{Equivalence})}
  2. Generate a Convert Description Tuple \mathsf{(rt^{Convert}, cv^{mint}, \pi_{Convert})}
  3. Generate an Airdrop Binding Signature \mathsf{bindingSigAirdrop}.

A Shielded Airdrop Transaction Structure would be composed by the set of descriptions above together with the Airdrop Binding Signature.

A Shielded Airdrop Transaction Structure constitutes a valid Shielded Airdrop Transaction is valid if:

  1. All the statemetns proofs present in the transaction are valid.
  2. All the signatures are valid.
  3. The Airdrop nullifier reveald is not in the Airdrop nullifier set.
  4. :large_blue_circle: \mathsf{cv^{Orchard}} given as a public input to the Equivalence statement and \mathsf{cv^{Orchard}} given as a public input to the Claim statement are equal.

Conclusions and outlook

To the best of our knowledge, there are no further Protocol requirements that this design iteration is not meeting and would require a further “Shielded Airdrop protocol 3.0” protocol update. What we have interest in further researching is:

  1. A more efficient and implementation friendly shielded airdrop protocol.
  2. :red_circle: Applications of the shielded airdrop protocol mechanisms outside the scope of a shielded airdrop. We are interested in exploring how we can leverage these techniques so that Zcash users can leverage our work here for governance purposes.
  3. Anything that comes up from discussions on this post.

  1. N.b. the github link referenced in the discussion above was pointing to the version previously linked, Apr 3, 2024. ↩︎

19 Likes