# 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

f\in \mathbb{F}^d[X];

6/14/2023Dmitry Khovratovich Problem: whenever we implement an algorithm that works over $Z_{N}$, with $N=2^{16}$ or $N=2^{32}$, we need to reduce all computations modulo $N$ and range-check all variables against $N$. These operations are expensive. We suggest a new scheme that implements the mod-$N$ arithmetic without range checks. 1. State of the art: Simplified Plonk Notation: $N =2^n$. First recall (and simplify) how Plonk arranges its witness.

11/18/20221. Notation $n$ -- ring degree (512 or 1024) $q$ -- modulus $=12289 = 3\cdot 2^{12}+1$ $\widehat{\beta} = \lfloor\beta^2\rfloor$ -- max norm (34 034 726 or 70 265 242) $\phi=X^n+1$ 2. Single Signature Verification Inputs:

9/7/2022Zedger tokens are a class of assets that exist in the Dusk blockchain. They are specific in the privacy of transfers and ownership: regular blockchain users can't figure out the balances of other individuals. 1. Genealogy There are several versions of Zedger tokens, each with different functionality. For each asset its governance shall decide which version to use. Upgrade is possible but difficult. This document describes the following versions: Minimal, denoted by ZedMin which supports: Asset transfers between users;

8/15/2022
Published on ** HackMD**