Cryptographic Schemes

PoseidonHash Function

Poseidon is a circuit friendly permutation hash function described in the paper GKRRS2019.

Our usage matches that of the halo2 library. Namely using a sponge configuration with addition which defines the function $$\text{PoseidonHash}:{\mathbb{F}}_p\times \cdots \times {\mathbb{F}}_p\to {\mathbb{F}}_p$$

Bulla Commitments

Given an abstract hash function such as PoseidonHash, we use a variant of the commit-and-reveal scheme to define anonymized representations of objects on chain. Contracts then operate with these anonymous representations which we call bullas.

Let $\text{Params}\in {\mathbb{F}}_p^n$ represent object parameters, then we can define $$\text{Bulla}:{\mathbb{F}}_p^n\times {\mathbb{F}}_p\to {\mathbb{F}}_p$$ $$\text{Bulla}(\text{Params},b)=\text{PoseidonHash}(\text{Params},b)$$ where $b\in {\mathbb{F}}_p$ is a random blinding factor.

Then the bulla (on chain anonymized representation) can be used in contracts with ZK proofs to construct statements on $\text{Params}$.

Pallas and Vesta

DarkFi uses the elliptic curves Pallas and Vesta that form a 2-cycle. We denote Pallas by $ₚ$ and Vesta by $ᵥ$. Set the following values:

$$p=0x40000000000000000000000000000000224698fc094cf91b992d30ed00000001$$ $$q=0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001$$

We now construct the base field for each curve $K_p$ and $K_v$ as $K_p={\mathbb{F}}_p$ and $K_v={\mathbb{F}}_q$. Let $f=y^2-(x^2+5)\in Z[x,y]$ be the Weierstrauss normal form of an elliptic curve. We define $f_p=f\mathrm{mod}{K}_p$ and $f_v=f\mathrm{mod}{K}_v$. Then we instantiate Pallas as $E_p=V(f_p)$ and $E_v=V(f_v)$. Now we note the 2-cycle behaviour as

$$\#V(f_p)=q$$ $$\#V(f_v)=p$$

An additional projective point at infinity $\infty$ is added to the curve.

Let $P_p$ be the group of points with $\infty$ on $E_p$.

Let $P_v$ be the group of points with $\infty$ on $E_v$.

Arithmetic is mainly done in circuits with ${\mathbb{F}}_p$ and $E_p$.

Coordinate Extractor for Pallas

Let $P_p,\infty ,{\mathbb{F}}_p$ be defined as above.

Define $\mathcal{X}:P_p\to {\mathbb{F}}_p$ such that $$\mathcal{X}({\infty }_{E_p})=0$$ $$\mathcal{X}((x,y))=x$$ $$\mathcal{Y}({\infty }_{E_p})=0$$ $$\mathcal{Y}((x,y))=y$$

Note: There is no $P=(0,y)\in E_p$ so $\mathcal{X}(P)=0⟹P=\infty$. Likewise there is no $P=(x,0)\in E_p$ so $\mathcal{Y}(P)=0⟹P=\infty$.

Hashing to ${\mathbb{F}}_p$

Define ${\mathbb{B}}^{64}2{\mathbb{F}}_p:{\mathbb{B}}^{64}\to {\mathbb{F}}_p$ as the matching decoding of ${\mathbb{F}}_p$ modulo the canonical class in little endian byte format.

Let there by a uniform hash function $h:X\to [0,r)$ with $r\ne p$, and a map $\sigma :[0,r)\to [0,p)$ converting to the canonical representation of the class in $Z/⟨p⟩$.

Let $s=\sigma \circ h$ be the composition of functions, then $s$ has a non-uniform range. However increasing the size of $r$ relative to $p$ diminises the statistical significance of any overlap. For this reason we define the conversion from ${\mathbb{B}}^{64}$ for hash functions.

PubKey Derivation

Let $G_N\in P_p$ be the constant NULLIFIER_K defined in src/sdk/src/crypto/constants/fixed_bases/nullifier_k.rs. Since the scalar field of $P_p$ is prime, all points in the group except the identity are generators.

We declare the function ${\text{Lift}}_q(x):{\mathbb{F}}_p\to {\mathbb{F}}_v$. This map is injective since $\{0,p-1\}\subset \{0,q-1\}$.

Define the function $$\text{DerivePubKey}:{\mathbb{F}}_p\to P_p$$ $$\text{DerivePubKey}(x)={\text{Lift}}_q(x)G_N$$

Point Serialization

The maximum value of ${\mathbb{F}}_p$ fits within 255 bits, with the last bit of ${\mathbb{B}}^{32}$ being unused. We use this bit to store the sign of the $y$-coordinate.

We compute the sign of $y=\mathcal{Y}(P)$ for $P\in P_p$ by dividing ${\mathbb{F}}_p$ into even and odd sets. Let $\text{sgn}(y)=y\mathrm{mod}2$.

We define $P_{p}2{\mathbb{B}}^{32}:P_p\to {\mathbb{B}}^{32}$ as follows. Let $P\in P_p$, then

$$P_{p}2{\mathbb{B}}^{32}=\{\begin{array}{ll}N2{\mathbb{B}}^{32}(0)& \text{if }P=\infty \\ N2{\mathbb{B}}^{32}(\mathcal{X}(P)+2^{255}\text{sgn}(\mathcal{Y}(P))& \text{otherwise}\end{array}$$

Security note: apart from the case when $P=\infty$, this function is mostly constant time. In cases such as key agreement, where constant time decryption is desirable and $P\ne \infty$ is mostly guaranteed, this provides a strong approximation.

Group Hash

Let $\text{GroupHash}:{\mathbb{B}}^{\ast }\times {\mathbb{B}}^{\ast }\to P_p$ be the hash to curve function defined in ZCash Protocol Spec, section 5.4.9.8. The first input element acts as the domain separator to distinguish uses of the group hash for different purposes, while the second input is the actual message.

The main components are:

• An isogeny map ${\text{iso\_map}}^{\mathbb{G}}:\text{iso-}\mathbb{G}\to \mathbb{G}$ which is a group homomorphism from $P_p$ to a curve $\text{iso-}{P}_p$ with $a_{\text{iso-}{P}_p},b_{\text{iso-}{P}_p}\ne 0$ which is required by the group hash. See IETF: Simplified SWU for AB == 0.
• hash_to_field implementation which maps a byte array to the scalar field ${\mathbb{F}}_q$.
• map_to_curve_simple_swu(u) which maps $u\in {\mathbb{F}}_q$ to a curve point $\text{iso-}{P}_p$.

Then $\text{GroupHash}(D,M)$ is calculated as follows:

Let $\text{DST}=D||\text{"-pallas\_XMD:BLAKE2b\_SSWU\_RO\_"}$

Assert $\text{len}(DST)\le 255$

Let $(u_1,u_2)=\text{hash\_to\_field}(M,\text{DST})$

For $i\in [2]$

  Let $Q_i=\text{map\_to\_curve\_simple\_swu}(u_i)$

Return ${\text{iso\_map}}^{P_p}(Q_1+Q_2)$

BLAKE2b Hash Function

BLAKE2 is defined by ANWW2013. Define the BLAKE2b variant as $${\text{BLAKE2b}}_n:{\mathbb{B}}^{\ast }\to {\mathbb{B}}^n$$

Homomorphic Pedersen Commitments

Let $\text{GroupHash}$ be defined as in Group Hash.

Let ${\text{Lift}}_q$ be defined as in Pubkey Derivation.

When instantiating value commitments, we require the homomorphic property.

Define: $$G_V=\text{GroupHash}(\text{"z.cash:Orchard-cv"},\text{"v"})$$ $$G_B=\text{GroupHash}(\text{"z.cash:Orchard-cv"},\text{"r"})$$ $$\text{PedersenCommit}:{\mathbb{F}}_p\times {\mathbb{F}}_v\to P_p$$ $$\text{PedersenCommit}(v,b)={\text{Lift}}_q(v)G_V+b{G}_B$$

This scheme is a computationally binding and perfectly hiding commitment scheme.

Incremental Merkle Tree

Let ${\ell }^M=32$ be the merkle depth.

The incremental merkle tree is fixed depth of ${\ell }^M$ used to store ${\mathbb{F}}_p$ items. It is an append-only set for which items can be proved to be inside within ZK. The root value is a commitment to the entire tree.

Denote combining two nodes to produce a parent by the operator $\oplus :{\mathbb{F}}_p\times {\mathbb{F}}_p\to {\mathbb{F}}_p$. Denote by ${\oplus }_b$ where $b\in Z_2$, the function which swaps both arguments before calling $\oplus$, that is $${\oplus }_b(X_1,X_2)=\{\begin{array}{ll}\oplus (X_1,X_2)& \text{if }b=0\\ \oplus (X_1,X_2)& \text{if }b=1\end{array}$$

We correspondingly define the types $$\text{MerklePos}=Z_2^{{\ell }^M}$$ $$\text{MerklePath}={\mathbb{F}}_p^{{\ell }^M}$$ and a function to calculate the root given a leaf, its position and the path, $$\text{MerkleRoot}:\text{MerklePos}\times \text{MerklePath}\times {\mathbb{F}}_p\to {\mathbb{F}}_p$$ $$\text{MerkleRoot}(\mathbf{p},\mathbf{\Pi },\mathcal{B})={\oplus }_{p_{{\ell }^M}}(\dots ,{\oplus }_{p_2}({\pi }_2,{\oplus }_{p_1}({\pi }_1,\mathcal{B}))\dots )$$

Symmetric Encryption

Let $\text{Sym}$ be an authenticated one-time symmetric encryption scheme instantiated as AEAD_CHACHA20_POLY1305 from RFC 7539. We use a nonce of $N2{\mathbb{B}}^{12}(0)$ with a 32-byte key.

Let $K={\mathbb{B}}^{32}$ represent keys, $N={\mathbb{B}}^{\ast }$ for plaintext data and $C={\mathbb{B}}^{\ast }$ for ciphertexts.

$\text{Sym}.\text{Encrypt}:K\times N\to C$ is the encryption algorithm.

$\text{Sym}.\text{Decrypt}:K\times C\to N\cup \{\perp \}$ is the decryption algorithm, such that for any $k\in K$ and $p\in P$, we have $$\text{Sym}.\text{Decrypt}(k,\text{Sym}.\text{Encrypt}(k,p))=p$$ we use $\perp$ to represent the decryption of an invalid ciphertext.

Security requirement: $\text{Sym}$ must be one-time secure. One-time here means that an honest protocol participant will almost surely encrypt only one message with a given key; however, the adversary may make many adaptive chosen ciphertext queries for a given key.

Key Agreement

Let ${\mathbb{F}}_p,P_p,{\text{Lift}}_q$ be defined as in the section Pallas and Vesta.

A key agreement scheme is a cryptographic protocol in which two parties agree on a shared secret, each using their private key and the other party's public key.

Let $\text{KeyAgree}:{\mathbb{F}}_p\times P_p\to P_p$ be defined as $\text{KeyAgree}(x,P)={\text{Lift}}_q(x)P$.

Key Derivation

Let ${\text{BLAKE2b}}_n$ be defined as in the section BLAKE2b Hash Function.

Let $P_p,P_{p}2{\mathbb{B}}^{32}$ be defined as in the section Pallas and Vesta.

A Key Derivation Function is defined for a particular key agreement scheme and authenticated one-time symmetric encryption scheme; it takes the shared secret produced by the key agreement and additional arguments, and derives a key suitable for the encryption scheme.

$\text{KDF}$ takes as input the shared Diffie-Hellman secret $x$ and the ephemeral public key $\text{EPK}$. It derives keys for use with $\text{Sym}.\text{Encrypt}$. $$\text{KDF}:P_p\times P_p\to {\mathbb{B}}^{32}$$ $$\text{KDF}(P,\text{EPK})={\text{BLAKE2b}}_{32}(P_{p}2{\mathbb{B}}^{32}(P)||P_{p}2{\mathbb{B}}^{32}(\text{EPK}))$$

In-band Secret Distribution

Let $\text{Sym}.\text{Encrypt},\text{Sym}.\text{Decrypt}$ be defined as in the section Symmetric Encryption.

Let $\text{KeyAgree}$ be defined as in the section Key Agreement.

Let $\text{KDF}$ be defined as in the section Key Derivation.

Let ${\mathbb{F}}_p,P_p,\text{DerivePubKey}$ be defined as in the section Pallas and Vesta.

To transmit secrets securely to a recipient without requiring an out-of-band communication channel, we use the key derivation function together with symmetric encryption.

Denote ${\text{AeadEncNote}}_n=(E,C)$ where $E$ is the space of ephemeral public keys and $C$ is the ciphertext space.

See AeadEncryptedNote in src/sdk/src/crypto/note.rs.

Encryption

We let $P\in P_p$ denote the recipient's public key. Let $\text{note}\in N={\mathbb{B}}^{\ast }$ denote the plaintext note to be encrypted.

Let $\text{esk}\in {\mathbb{F}}_p$ be the randomly generated ephemeral secret key.

Let $\text{EPK}=\text{DerivePubKey}(\text{esk})\in P_p$

Let $\text{shared\_secret}=\text{KeyAgree}(\text{esk},P)$

Let $k=\text{KDF}(\text{shared\_secret},\text{EPK})$

Let $c=\text{Sym}.\text{Encrypt}(k,\text{note})$

Return $c$

Decryption

We denote the recipient's secret key with $x\in {\mathbb{F}}_p$. Let $c\in C={\mathbb{B}}^{\ast }$ denote the ciphertext note to be decrypted.

The recipient receives the ephemeral public key $\text{EPK}\in P_p$ used to decrypt the ciphertext note $c$.

Let $\text{shared\_secret}=\text{KeyAgree}(x,\text{EPK})$

Let $k=\text{KDF}(\text{shared\_secret},\text{EPK})$

Let $\text{note}=\text{Sym}.\text{Decrypt}(k,c)$. If $\text{note}=\perp$ then return $\perp$, otherwise return $\text{note}$.

Verifiable In-Band Secret Distribution

Let $\text{PoseidonHash}$ be defined as in the section PoseidonHash Function.

This scheme is verifiable inside ZK using the Pallas and Vesta curves.

Let $n\in N$. Denote the plaintext space $N_k$ and ciphertext $C_k$ with $N_k=C_k={\mathbb{F}}_p^k$ where $k\in N$.

Denote ${\text{ElGamalEncNote}}_k=(E,C_k)$ where $E$ is the space of ephemeral public keys and $C$ is the ciphertext space.

See ElGamalEncryptedNote in src/sdk/src/crypto/note.rs.

Encryption

We let $P\in P_p$ denote the recipient's public key. Let $\mathbf{n}\in N$ denote the plaintext note to be encrypted.

Define $\text{ElGamal}.\text{Encrypt}:N_k\times {\mathbb{F}}_p\times P_p\to C_k\times P_p$ by $\text{ElGamal}.\text{Encrypt}(\mathbf{n},P)$ as follows:

Let $\text{esk}\in {\mathbb{F}}_p$ be the randomly generated ephemeral secret key.

Let $\text{EPK}=\text{DerivePubKey}(\text{esk})\in P_p$

Let $\text{shared\_secret}=\text{KeyAgree}(\text{esk},P)$

Let $k=\text{PoseidonHash}(\mathcal{X}(\text{shared\_secret}),\mathcal{Y}(\text{shared\_secret}))$

For $i\in [k]$ then compute:

  Let $b_i=\text{PoseidonHash}(k,i)$

  Let $c_i={\text{note}}_i+b_i$

Return $(\mathbf{c},\text{EPK})$ where $\mathbf{c}=(c_i)$

Decryption

We denote the recipient's secret key with $x\in {\mathbb{F}}_p$. The recipient receives the ephemeral public key $\text{EPK}\in P_p$ used to decrypt the ciphertext note $\mathbf{c}\in C_k$.

Define $\text{ElGamal}.\text{Decrypt}:C_k\times {\mathbb{F}}_p\times P_p\to N_k$ by $\text{ElGamal}.\text{Decrypt}(\mathbf{c},x,\text{EPK})$ as follows:

Let $\text{shared\_secret}=\text{KeyAgree}(x,\text{EPK})$

Let $k=\text{PoseidonHash}(\mathcal{X}(\text{shared\_secret}),\mathcal{Y}(\text{shared\_secret}))$

For $i\in [k]$ then compute:

  Let $b_i=\text{PoseidonHash}(k,i)$

  Let $n_i=c_i-b_i$

Return $\mathbf{n}=(n_i)$