# Zedger Math <style> .ui-infobar, #doc.markdown-body { max-width: 1200px; } </style> ## 1. Notation * Group elements (curve points) are capitals $K,R,P,\ldots$ * Scalars (field elements) are lowercase $s,k,\ldots$ * Scalar multiplication in the group is $[k]P$. * Vectors are bold: $\mathbf{D}$. * Tuples: $\mathcal{C}$ ## 2. Components ### 2.1 Cryptographic Primitives * Curve $\mathbf{E}$ defined over field $\mathbb{F}_q$ (supposedly BN254) with group of prime order $\mathbb{F}_r$; * Public keys $K$ are group elements (curve points); * Authenticated encryption scheme $\mathcal{E}_k$, concretely AES-GCM. * Public key encryption scheme $P_{K}$. * Hash functions $H_i(\cdots)$ which can be instantiated as $H(i||\cdots)$: * $H_1$ for hashing to curve (1 argument) * $H_2$ for diversifiers (1 argument) * $H_3$ for spending secret key (1 argument); * $H_6$ for note commitments (1 tuple as argument); * $H_9$ for nullifiers (1 tuple as argument). * Schnorr signatures $\sigma_{G,K}(m)$ where $G$ is a generator, $K$ is a public key, and $m$ is a message. ### 2.2 Transactions #### 2.2.1 Contents The transaction primary data contain * asset value; * owner public key * owner base generator * blinder. * dividend timestamp; * dividend accrued. A smart contract additionally adds the following data: * transaction timestamp; * cumulative dividend; * forced transfer flag. Formally $$\mathcal{D} = (v=assetValue,G=base,K=pubKey,r= blinder, t=dividendTimestamp, d=dividendAccrued). $$ Here $v,r,t,d$ values are from $\mathbb{F}_r$. Auxiliary data, which is needed to make a transfer, includes * Position $p$. ### 2.4 Nullifier Nullifiers are 160-bit values. #### Computation Nullifier is computed as $$ N = H_9 ([k_s]K,p), $$ where $k_s$ is the secret key of $K$ and $p$ is position. Note that the nullifier can't be computed by a note sender as they don't know $k_s$. ## 3. Setup ### 3.1 Users Each user: * Derives seed $s$ from a set of 12 mnemonic words according to BIP39. * Computes spending key $k_s = H_3(s)$ ### 3.2 Inspector Inspector prepares and publishes their public key $K_I$. ## 4. Interaction ### 4.1 Address Exchange To generate a recipient address a user: * Generates diversifier $d=H_2(r=random)$ and diversified base $G=H_1(d)$; * Generates spending public key $K = [k]G$. Recipient address is $(G,K)$. All addresses must be submitted to the smart contract to form a whitelist. ## 5. Functionality ### 5.1 Transfer #### 5.1.1 Content For each output transaction $D_O$ Sender proceeds as: * obtain recipient address $(G,K)$; * Select value $v$; * Compute dividend data $t,d$; * Generate random blinder $r$; * Generate ephemeral secret $e$; * Generate ephemeral address $A=[e]G$ * Generate encryption key $k_x=H_5([e]K)$ * Construct $\widehat{D} = \{v,G,K,r,t,d\}$; * Prepares ciphertext $\mathcal{C} = E_{k_x}(\widehat{D})$. * Prepares Inspector ciphertext $\mathcal{C}_{I} = P_{K_I}(k_x)$ * Transaction $D_O$ is $(A,\mathcal{C},H_6(\widehat{D}))$ Sender collects the following notes for transmission: * $N_1$ input transactions $\mathbf{D}_I$ (with position $p$ included); * $N_2$ output transactions $\mathbf{D}_O$. Sender additionally obtains: * Recent tree root $R_{old}$ where all input notes reside. * Transaction timestamp $t_0$. * Cumulative dividend $x_0$ for time $t_0$. #### 5.1.2 Preparation Sender creates * Nullifiers $\mathbf{N}$ for input notes. * Output context $Z = H_{10}(\mathbf{D}_O )$ . * Proof $\Pi$: $$ \Pi_S[\mathbf{N},R_{old},t_0 ]:\; \mathbf{D}_I\in R_{old} \;\&\;\mathbf{N} = H_9([k_s]\mathbf{K},\mathbf{p})\;\&\;\{\sigma_{\mathbf{K}}(\mathcal{D},Z)\}_{\mathcal{D}\in\mathbf{D}_I} \;\&\;\mathrm{Balance}(\mathbf{D}_I,\mathbf{D}_O) \;\&\;\mathrm{Inspect}(\mathbf{D}_O) $$ Proof additionally verifies that the transaction is not spent manually. Full transfer data is $$ \mathcal{T} = (\mathbf{D}_O,R_{old},\Pi_S,\mathbf{N}) $$ Balance rules: \begin{align} \sum_i D_{I,i}[v] = \sum_j D_{O,j}[v];\\ \sum_i \left(D_{I,i}[d]+(t_0-D_{I,i}[t])(x_{0}-D_{I,i}[x]) \right)= \sum_j D_{O,j}[d];\\ \end{align} Inspection rules: * All $D_O$ data are encrypted on inspector's key. #### 5.1.3 Receival Input: spending key $k$. For transaction $T=(A,\mathcal{C})$: 1. Compute viewing decryption key $k_x = H_5([k_v]A)$ 2. Decrypt $G,\widehat{D}=\mathcal{E}_{k_x}^{-1}(\mathcal{C})$. 3. Check if $[k]\widehat{D}[G]=K$. #### 5.1.4 Smart contract actions 1. Verify proofs 2. Check that new nullifiers are unique and add those to the list. 3. Add new transactions to the tree together with timestamps $t$ and dividend cumulative payment $x$. ### 5.2 Registry 1. Decrypt all transactions on Inspector's key. ### 5.3 Mint 1. A new transaction is created in cleartext and is added to the tree. ### 5.4 Burn 1. An old transaction is nullified without a matching output transcation. ### 5.5 Forced Transfer 1. A flag is changed at some tree leaf. ### 5.6 Dividend Withdrawal 1. An output transaction $D_O$: * is public; * contains an external Dusk address $A$. * token value is zero. 2. Then the dividend amount $D_O[d]$ of this transaction is sent by the contract to $A$. ### 5.7 Voting #### 5.7.1 Setup The governance creates a private-public key pair $(k,K=[k]G)$ (once for all votes). It can be done with threshold decryption. Each poll allows voting with some number $v<V_0$. #### 5.7.2 Vote In order to cast a vote with value $v$ associated with transaction $\mathcal{T}$, Alice creates an ElGamal ciphertext with randomness $r$ $$ C = ([r]G,[r]K+[v]G). $$ and sends it to the smart contract with $(\pi,N_V)$ where: * $N_V$ is a nullifier for transaction $\mathcal{T}$; * $\pi$ is a proof that * a nullifier corresponds to some transaction in the tree; * the vote $v$ matches the transaction (e.g. its amount). #### 5.7.3 Count In order to count the votes, Governance proceeds as follows: * Sum all submitted $C_i$ thus getting $C_{sum} = ([r']G,[r']K + [v']G)$ where $r'$ is a sum of randomnesses and $v'$ is the sum of votes; * Decrypt $C_{sum}$ as $[v']G = C_2 - [k]C_1$ where $k$ is the Governance key; * Find $v'$ by bruteforce with complexity $\sqrt{V}$ where $V$ is the maximal total amount of votes. ### 5.8 Dividend payout 1. Sets a new payout date $t$ and amount $a$ to the future. 2. The first transaction after $t$ modifies the cumulative dividend amount. ## 6. Swap ### 6.1 Transactions Token 1: $$ \begin{cases} I_1: M, w_1\\ I_2: M, w_2=(X_M-w_1) \end{cases} \longrightarrow \begin{cases} O_1: T, v_1\\ O_2: M, X_M-v_1 \end{cases} $$ Token 2: $$ \begin{cases} I_3: T, w_3\\ I_4: T, w_4=X_T-w_3 \end{cases} \longrightarrow \begin{cases} O_3: T, X_T-v_2\\ O_4: M, v_2 \end{cases} $$ ### 6.2 Requirements Maker requirements: * $a O_1[V] \leq b O_4[V]$. Enforced in Swap SNARK * $O_2[K]=M$. Swap * $O_4[K]=M$. Swap * Inputs $I_1,I_2$ to spend. Enforced in Token 1 contract. * 2 outputs in T1 tx. Swap. * 2 outputs in T2 tx. Swap Taker requirements: * $O_1:\, V=v_1,\; K=T$: Swap * $O_3:\, V=X_T-v_2,\; K=T$: Swap * Inputs $I_3,I_4$ to spend. Enforced in Token 2 contract. * 2 outputs in T1: Ver1 * 2 outputs in T2: Ver2 ### 6.3 Contract Swap ``` struct publicInputs { //for publicInputs1,publicInputs2 list verifyingContracts; //contracts that check signatures nullifier1, nullifier2; //nullifiers ciphertext; //encrypted transaction root; //recent coin tree root outputHash1; // output sealed coins outputHash2; } fn swap(publicInputs1,publicInputs2,proof1,proof2,proof3){ //check that the second verifying contract is this one for both signatures assert(publicInputs1.verifyingContracts[2] == publicInputs2.verifyingContracts[2] == this ) //check that the token contracts are the same in both signatures assert(publicInputs1.verifyingContracts[1] == publicInputs2.verifyingContracts[3]) assert(publicInputs1.verifyingContracts[3] == publicInputs2.verifyingContracts[1]) publicInputs3 = { publicInputs1.verifyingContracts; //the contracts both the taker and the maker signed -- T1 and SWap and T2 publicInputs1.outputHash1; publicInputs1.outputHash2; publicInputs2.outputHash1; publicInputs2.outputHash2; } assert(verifySNARK(publicInputs3,proof3)) //check that swap conditions are satisfied //atomically make two other transfers publicInputs1.verifyingContracts[1].transfer(publicInputs1,proof1); publicInputs2.verifyingContracts[1].transfer(publicInputs2,proof2); } fn verifySNARK(publicInputs,proof) { SNARK{ public verifyingContracts; public outputHash1; public outputHash2; public outputHash3; public outputHash4; private makerSignature; private takerSignature; private hashM1; //Hash of metadata for token 1 contract signed by maker. private hashT1; //Hash of metadata for token 2 contract signed by taker. private output1; //full output coin private output2; private output3; private output4; //maker data private price = {a,b}; //Maker: swap condition assert(price.a*output1.v <= price.b*output4.v) //Maker: recipient assert(output2.K == output4.K) //Maker: signature check dataM = (a,b,output2.K) assert(SchnorrSignatureVerify( Key, Data={verifyingContracts[1],hashM1,verifyingContracts[2],hash(dataM),verifyingContracts[3]}, makerSignature)) //Taker: recipient assert(output1.K == output3.K) //Taker: signature check dataT = (output1.K,output1.V,output3.V) assert(SchnorrSignatureVerify( Key, Data={verifyingContracts[3],hashT1,verifyingContracts[2],hash(dataT),verifyingContracts[1]}, takerSignature)) //Output check assert(hash(output1)==outputHash1) assert(hash(output2)==outputHash2 assert(hash(output3)==outputHash3) assert(hash(output4)==outputHash4) } } ``` ### 6.4 Contract Token 1,2 ``` struct publicInputs { list verifyingContracts; //contracts that check signatures nullifier1, nullifier2; //nullifiers ciphertext; //encrypted transaction root; //recent coin tree root outputHash1; // output sealed coins outputHash2; } fn transfer(publicInputs, proof) { assert( publicInputs.verifyingContracts == (this, msg.sender, someContract) //swap case OR publicInputs.verifyingContracts == this ) //regular transfer //checking paths and right of spending assert(verifySNARK(publicInputs,proof)) //checking nullifiers and adding to the tree assert(publicInputs.nullifier1 not in the nullifier list); addNullifier(publicInputs.nullifier1) assert(publicInputs.nullifier2 not in the nullifier list); addNullifier(publicInputs.nullifier2) addCoin(publicInputs.outputHash1) addCoin(publicInputs.outputHash2) } fn verifySNARK(proof) SNARK{ public verifyingContracts; public nullifier1; public nullifier2; public ciphertext; public root; public outputHash1; public outputHash2; private Signature; //Signature of inputs owner (for swap&t1 -- Maker, for swap&t2 -- Taker) private hashExt; //Hash of metadata for another contract signed by spender. Each contract verifies only one hash private inputsVerified; //bitmask which inputs are asserted by signature private outputsVerified; private input1; //full input coin private input2; private output1; //full output coin private output2; private nullifierProof1; //Schnorr proof of knowledge of discrete log for the nullifier private nullifierProof2; private merklePath1; //path for input1 private merklePath2; private KYCProof1; //whitelist proof for recipient private KYCProof2; //Selecting input data that is asserted by signature inputData = (input1 & inputsVerified[1]) || (input2 & inputsVerified[2]); //Selecting output data that is asserted by signature outputData = (output1 & outputsVerified[1]) || (output2 & outputsVerified[2]); Data1 = (inputData,outputData); assert(input1[K]==input2[K]);//spending from the same key if(verifyingContracts.len==1) assert(SchnorrSignatureVerify( Key, Data={verifyingContracts[1],hash(Data1)}, Signature)) else assert(SchnorrSignatureVerify( Key, Data={verifyingContracts[1],hash(Data1),verifyingContracts[2],hashExt,verifyingContracts[3]}, Signature)) assert(input1.v+input2.v==output1.v+output2.v); //sum of inputs equals sum of outputs assert(SchnorrDlogProof(input1[K],nullifier1,nullifierProof1)); //nullifier is computed correctly assert(SchnorrDlogProof(input2[K],nullifier2,nullifierProof2)); //Ciphertext contains enough information for auditor and recipient (!) assert(CorrectEncryption(input1, input2, output1, output2, ciphertext)); //Input verification assert(MerkleProofVerify(hash(input1),merklePath1,root)) assert(MerkleProofVerify(hash(input2),merklePath2,root)) //Output check assert(hash(output1)==outputHash1) assert(hash(output2)==outputHash2) //Whitelist check assert(recipientKYCVerify(output1[K], KYCProof1)) assert(recipientKYCVerify(output2[K], KYCProof2)) } ``` ### 6.5 Regular transfer flow at contract T1 1. Spender selects inputs $I_1,I_2$ to spend and constructs outputs $O_1,O_2$. 2. Spender creates nullifiers, output hashes, nullifier proofs, input tree proofs, auditor proofs. They also create and encrypt a transaction. 3. Spender signs data $D$ with * `verifyingContracts=(T1)` * bitmasks inputsVerified and outputsVerified are all true * inputs, outputs, nullifier proofs, input proofs, auditor proofs -- as constructed. 4. Spender creates SNARK `proof`. 5. Spender calls `transfer` at T1 with `verifyingContracts=(T1)` and `proof`. ### 6.6 Swap flow with contracts Swap, T1, T2 1. Maker selects contract T1 to spend and inputs $I_1,I_2$ there of total amount $X_M$. 2. Maker selects swap condition $(a,b)$. 3. Maker creates a signature $\sigma_M$ where asserts: * The contracts to be called: `verifyingContracts=(T1,Swap,T2)` * Conditions for T1: hash of inputs and outputs where outputs are cleared by the bitmask. * Conditions for Swap: swap condition and recipient key $K_M$. 4. Maker creates nullifiers for $I_1,I_2$ and tree proofs as supplementary data $D$. Maker also adds full information about $I_1,I_2$ to $D$. 6. Maker publishes the swap condition $S$ and data $D$. 7. Taker decides how many tokens $v_1$ of T1 they receive, and how many $v_2$ tokens of T2 they give. 8. Taker selects inputs $I_3,I_4$ of $T_2$ of total $X_T$. 9. Taker creates outputs $O_1,O_3$ that go to $K_T$, and $O_2,O_4$ that go to Maker ($K_M$). 10. Taker creates a signature $\sigma_T$ where asserts: * The contracts to be called: `verifyingContracts=(T2,Swap,T1)` * Conditions for T2: hash of inputs and outputs. The bitmasks are all true. * Conditions for Swap: value and key $K_T$ for $O_1$, same for $O_3$. Note that this determines the values for $O_2,O_4$. 11. Taker creates a spending proof $\pi_1$ for T1 using maker signature $\sigma_M$, maker data $D$ and outputs $O_1,O_2$. 12. Taker creates a spending proof $\pi_2$ for T2 using their knowledge of $I_3,I_4$, their signature $\sigma_T$, and outputs $O_3,O_4$. 13. Taker creates a swap proof $\pi_s$ using all outputs and signatures $\sigma_M,\sigma_T$. 14. Taker calls `swap` at Swap submitting publicInputs for both T1 and T2 and proofs $\pi_1,\pi_2,\pi_s$. 15. The Swap contracts checks $\pi_s$ and calls `transfer` of T1. 16. T1 executes transfer. 17. The Swap calls `transfer` of T2. 18. T2 executes transfer. END