Grant Application - ZEC-NAM shielded airdrop protocol

Community Grants Applications
24

Dear Zcash Community,

We report on the completion of milestone 1 for the ZEC-NAM shielded airdrop protocol. In this first of four milestones, the focus has been on the Zcash side regarding specification and implementation, closely following the design and discussions from, see [1].

The core functionality in this milestone is the generation of a chain snapshot frozen at a given height to be used as the public parameters for the airdrop. In addition, we have the specification and implementation of airdrop nullifiers, used for protection against airdrop double-claims.

For verifying airdrop claims, the public parameters include for a given height:

  1. Merkle-root of Sapling note commitments,

  2. Merkle-root of Orchard note commitments,

  3. Merkle-root committing to the gaps of sorted Sapling nullifiers, and

  4. Merkle-root committing to the gaps of sorted Orchard nullifiers.

To claim an airdrop, one furthermore needs the explicit nullifier gaps for Sapling and Orchard, to prove a given note was not spent, via a Merkle non-membership proof as described below:

Merkle Non-Membership Proofs

Let S=\{x_1,...,x_n\} be the set of nullifiers sorted by integer value such that

0 < x_1 < … < x_i < x_{i+1} < … < x_n < \textsf{U256::MAX}

Define the complement gaps G_0=(0,x_1), G_1=(x_1,x_2), G_2=(x_2,x_3), … , G_n=(x_n,\textsf{MAX}) as open intervals between values (a,b) such that a and b are excluded. From each gap, we compute a Merkle leaf L_i = H(pp || G_i) given public parameters pp and a hash function H to be fixed later - in the current implementation the pp are empty and H=\textsf{SHA-256}. This naturally defines a Merkle root and standard Merkle-paths used for proving inclusion of a leaf.

A non-membership proof for any nullifier y in the open interval G_i = (a,b) is

(L_i, merklePath(L_i), intervalProof)

Here intervalProof is used to verify the statement a<y<b. The verification of the interval proof together with the Merkle path guarantees a given gap between spent nullifiers is valid for this snapshot, and that the claimed nullifier y was indeed in this gap.

We note the use of 0 and \textsf{U256::MAX} as fixed gap-bounds, which imply nullifiers with these special-case values cannot be used to prove non-membership, and therefore cannot be used to claim airdrops. Further, checking if y is also a valid field element (e.g. y<p) must be done separately. The intervalProof is to be specified in the next phase using appropriate zk-systems.

Airdrop Nullifiers

To guard against airdrop double-claims while ensuring user privacy, we derive deterministic airdrop nullifiers from notes while ensuring unlinkability to later spends on Zcash, see also [1].

For Sapling, we derive airdrop nullifiers like standard Sapling nullifiers, but change the pp prefix used by the outer-most hash function for proper domain separation. In more detail, section 5.4.2 (Pseudo Random Functions) in [2] specify Sapling nullifiers as:

\mathsf{PRF^{nfSapling}_{nk^\star}}(\rho^\star) = \mathrm{BLAKE2s\text{-}256}(\text{"Zcash_nf"}, \mathsf{LEBS2OSP_{256}(nk^\star)} \Vert \mathsf{LEBS2OSP_{256}(\rho^\star)})

Here we generalize to below, where {targetS} is a fixed public airdrop target chain parameter:

\mathsf{PRF^{nfSaplingAirdrop}_{nk^\star}}(\rho^\star) = \mathrm{BLAKE2s\text{-}256}(\text{"\{targetS\}"}, \mathsf{LEBS2OSP_{256}(nk^\star)} \Vert \mathsf{LEBS2OSP_{256}(\rho^\star)})

For Orchard, we derive airdrop nullifiers like standard Orchard nullifiers, but change the pp preimage used by the hash generating the curve point for proper domain separation. In more detail, section 4.16 (Computing ρ values and Nulliers) in [3] specify Orchard nullifiers as:

\mathsf{DeriveNullifier}_{\textsf{nk}}(\rho,\psi,\textsf{cm}) = \mathrm{Extract}_{\mathbb{P}}\left(\left[\left(\mathsf{PRF^{nfOrchard}_{nk}}(\rho) + \psi\right) \bmod q_{\mathbb{P}}\right] \cdot \mathcal{K}^{\mathrm{Orchard}} + cm\right)

Here the curve generator \mathcal{K}^\textsf{Orchard} is derived as:

\mathcal{K}^\textsf{Orchard} := \textsf{GroupHash}^\mathbb{P}(\text{“z.cash:Orchard”},\text{“K”})

We use the below, where \text{\{targetO\}} is a fixed public airdrop target chain parameter:

\mathcal{K}^\textsf{Orchard} := \textsf{GroupHash}^\mathbb{P}(\text{"\{targetO\}"},\text{“K”})

An airdrop can be set up with any \text{target}S and \text{targetO}, that must be different from \text{“Zcash_nf"} and \text{“z.cash:Orchard”} respectively.

Implementation

The implementation contains the necessary tools and building blocks to integrate with Zcash, for example generating public airdrop parameters incl. nullifier gaps and resolving note indices.

https://github.com/eigerco/zcash-namada-airdrop/

The implementation primarily consists of two modules:

  • non-membership-proofs: The core library of the implementation. It contains utilities for:

    • Snapshot creation
    • Finding user notes. Takes a viewing key and returns the notes that can be viewed with that key.
    • Create the non-membership proofs

  • airdrop: Orchestrates non-membership-proof functions to provide the necessary functionalities to the users of the airdrop

Summary and Next Steps

In summary, the delivery of milestone 1 marks the primary integration with Zcash as completed, that mainly include snapshot generation, nullifier gaps, locating notes and Merkle-trees.

The next milestone estimated for mid February focuses on using these building blocks to specify and implement the central zero-knowledge proof that a given airdrop claim is valid.

Best regards,

Eiger Co

  1. Status for ZEC-NAM shielded airdrop protocol

  2. Sapling Protocol Specification

  3. Orchard et al. Protocol Specification

9 Likes