# 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