1  # Sapling payment scheme
  2  
  3  Sapling is a type of transaction which hides both the sender and
  4  receiver data, as well as the amount transacted. This means it allows
  5  a fully private transaction between two addresses.
  6  
  7  Generally, the Sapling payment scheme consists of two ZK proofs -
  8  **mint** and **burn**. We use the mint proof to create a new _coin_
  9  $C$, and we use the burn proof to spend a previously minted _coin_.
 10  
 11  ## Mint proof
 12  
 13  ```zkas
 14  {{#include ../../../../proof/mint.zk}}
 15  ```
 16  
 17  As you can see, the `Mint` proof basically consists of three
 18  operations.  First one is hashing the _coin_ $C$, and after that,
 19  we create _Pedersen commitments_[^1] for both the coin's **value**
 20  and the coin's **token ID**. On top of the zkas code, we've declared
 21  two constant values that we are going to use for multiplication in
 22  the commitments.
 23  
 24  The `constrain_instance` call can take any of our assigned variables
 25  and enforce a _public input_. Public inputs are an array (or vector)
 26  of revealed values used by verifiers to verify a zero knowledge
 27  proof. In the above case of the Mint proof, since we have five calls to
 28  `constrain_instance`, we would also have an array of five elements that
 29  represent these public inputs. The array's order **must match** the
 30  order of the `constrain_instance` calls since they will be constrained
 31  by their index in the array (which is incremented for every call).
 32  
 33  In other words, the vector of public inputs could look like this:
 34  
 35  ```
 36  let public_inputs = vec![
 37      coin,
 38      *value_coords.x(),
 39      *value_coords.y(),
 40      *token_coords.x(),
 41      *token_coords.y(),
 42  ];
 43  ```
 44  
 45  And then the Verifier uses these public inputs to verify a given zero
 46  knowledge proof.
 47  
 48  ### Coin
 49  
 50  During the **Mint** phase we create a new coin $C$, which is bound
 51  to the public key $P$. The coin $C$ is publicly revealed on the
 52  blockchain and added to the Merkle tree.
 53  
 54  Let $v$ be the coin's value, $t$ be the token ID, $\rho$ be the unique
 55  serial number for the coin, and $r_C$ be a random blinding value. We
 56  create a commitment (hash) of these elements and produce the coin $C$
 57  in zero-knowledge:
 58  
 59  $$ C = H(P, v, t, \rho, r_C)$$
 60  
 61  An interesting thing to keep in mind is that this commitment is
 62  extensible, so one could fit an arbitrary amount of different
 63  attributes inside it.
 64  
 65  ### Value and token commitments
 66  
 67  To have some value $v$ for our coin, we ensure it's greater than
 68  zero, and then we can create a Pedersen commitment $V$ where $r_V$
 69  is the blinding factor for the commitment, and $G_1$ and $G_2$ are
 70  two predefined generators:
 71  
 72  $$ v > 0 $$
 73  $$ V = vG_1 + r_VG_2 $$
 74  
 75  The token ID can be thought of as an attribute we append to our coin
 76  so we can have a differentiation of assets we are working with. In
 77  practice, this allows us to work with different tokens, using the
 78  same zero-knowledge proof circuit. For this token ID, we can also
 79  build a Pedersen commitment $T$ where $t$ is the token ID, $r_T$
 80  is the blinding factor, and $G_1$ and $G_2$ are predefined generators:
 81  
 82  $$ T = tG_1 + r_TG_2 $$
 83  
 84  ## Pseudo-code
 85  
 86  Knowing this we can extend our pseudo-code and build the
 87  before-mentioned public inputs for the circuit:
 88  
 89  ```rust
 90  let bincode = include_bytes!("../proof/mint.zk.bin");
 91  let zkbin = ZkBinary::decode(bincode)?;
 92  
 93  // ======
 94  // Prover
 95  // ======
 96  
 97  // Witness values
 98  let value = 42;
 99  let token_id = pallas::Base::random(&mut OsRng);
100  let value_blind = pallas::Scalar::random(&mut OsRng);
101  let token_blind = pallas::Scalar::random(&mut OsRng);
102  let serial = pallas::Base::random(&mut OsRng);
103  let public_key = PublicKey::from_secret(SecretKey::random(&mut OsRng));
104  let (pub_x, pub_y) = public_key.xy();
105  
106  let prover_witnesses = vec![
107      Witness::Base(Value::known(pub_x)),
108      Witness::Base(Value::known(pub_y)),
109      Witness::Base(Value::known(pallas::Base::from(value))),
110      Witness::Base(Value::known(token_id)),
111      Witness::Base(Value::known(serial)),
112      Witness::Scalar(Value::known(value_blind)),
113      Witness::Scalar(Value::known(token_blind)),
114  ];
115  
116  // Create the public inputs
117  let msgs = [pub_x, pub_y, pallas::Base::from(value), token_id, serial];
118  let coin = poseidon_hash(msgs);
119  
120  let value_commit = pedersen_commitment_u64(value, value_blind);
121  let value_coords = value_commit.to_affine().coordinates().unwrap();
122  
123  let token_commit = pedersen_commitment_base(token_id, token_blind);
124  let token_coords = token_commit.to_affine().coordinates().unwrap();
125  
126  let public_inputs = vec![
127      coin,
128      *value_coords.x(),
129      *value_coords.y(),
130      *token_coords.x(),
131      *token_coords.y(),
132  ];
133  
134  // Create the circuit
135  let circuit = ZkCircuit::new(prover_witnesses, zkbin.clone());
136  
137  let proving_key = ProvingKey::build(13, &circuit);
138  let proof = Proof::create(&proving_key, &[circuit], &public_inputs, &mut OsRng)?;
139  
140  // ========
141  // Verifier
142  // ========
143  
144  // Construct empty witnesses
145  let verifier_witnesses = empty_witnesses(&zkbin);
146  
147  // Create the circuit
148  let circuit = ZkCircuit::new(verifier_witnesses, zkbin);
149  
150  let verifying_key = VerifyingKey::build(13, &circuit);
151  proof.verify(&verifying_key, &public_inputs)?;
152  ```
153  
154  ## Burn
155  
156  ```zkas
157  {{#include ../../../../proof/burn.zk}}
158  ```
159  
160  The `Burn` proof consists of operations similar to the `Mint` proof,
161  with the addition of a _Merkle root_[^2] calculation. In the same
162  manner, we are doing a Poseidon hash instance, we're building Pedersen
163  commitments for the value and token ID, and finally we're doing a
164  public key derivation.
165  
166  In this case, our vector of public inputs could look like:
167  
168  ```
169  let public_inputs = vec![
170      nullifier,
171      *value_coords.x(),
172      *value_coords.y(),
173      *token_coords.x(),
174      *token_coords.y(),
175      merkle_root,
176      *sig_coords.x(),
177      *sig_coords.y(),
178  ];
179  ```
180  
181  ### Nullifier
182  
183  When we spend the coin, we must ensure that the value of the coin
184  cannot be double spent. We call this the _Burn_ phase. The process
185  relies on a nullifier $N$, which we create using the secret key $x$
186  for the public key $P$ and a unique random serial $\rho$. Nullifiers
187  are unique per coin and prevent double spending:
188  
189  $$ N = H(x, \rho) $$
190  
191  
192  ### Merkle root
193  
194  We check that the merkle root corresponds to a coin which is in the
195  Merkle tree $R$
196  
197  $$ C = H(P, v, t, \rho, r_C) $$
198  $$ C \in R $$
199  
200  ### Value and token commitments
201  
202  Just like we calculated these for the `Mint` proof, we do the same
203  here:
204  
205  $$ v > 0 $$
206  $$ V = vG_1 + r_VG_2 $$
207  $$ T = tG_1 + r_TG_2 $$
208  
209  
210  ## Public key derivation
211  
212  We check that the secret key $x$ corresponds to a public key $P$.
213  Usually, we do public key derivation my multiplying our secret key
214  with a genera tor $G$, which results in a public key:
215  
216  $$ P = xG $$
217  
218  
219  ## Pseudo-code
220  
221  Knowing this we can extend our pseudo-code and build the
222  before-mentioned public inputs for the circuit:
223  
224  ```rust
225  let bincode = include_bytes!("../proof/burn.zk.bin");
226  let zkbin = ZkBinary::decode(bincode)?;
227  
228  // ======
229  // Prover
230  // ======
231  
232  // Witness values
233  let value = 42;
234  let token_id = pallas::Base::random(&mut OsRng);
235  let value_blind = pallas::Scalar::random(&mut OsRng);
236  let token_blind = pallas::Scalar::random(&mut OsRng);
237  let serial = pallas::Base::random(&mut OsRng);
238  let secret = SecretKey::random(&mut OsRng);
239  let sig_secret = SecretKey::random(&mut OsRng);
240  
241  // Build the coin
242  let coin2 = {
243      let (pub_x, pub_y) = PublicKey::from_secret(secret).xy();
244      let messages = [pub_x, pub_y, pallas::Base::from(value), token_id, serial];
245      poseidon_hash(messages)
246  };
247  
248  // Fill the merkle tree with some random coins that we want to witness,
249  // and also add the above coin.
250  let mut tree = BridgeTree::<MerkleNode, 32>::new(100);
251  let coin0 = pallas::Base::random(&mut OsRng);
252  let coin1 = pallas::Base::random(&mut OsRng);
253  let coin3 = pallas::Base::random(&mut OsRng);
254  
255  tree.append(&MerkleNode::from(coin0));
256  tree.witness();
257  tree.append(&MerkleNode::from(coin1));
258  tree.append(&MerkleNode::from(coin2));
259  let leaf_pos = tree.witness().unwrap();
260  tree.append(&MerkleNode::from(coin3));
261  tree.witness();
262  
263  let root = tree.root(0).unwrap();
264  let merkle_path = tree.authentication_path(leaf_pos, &root).unwrap();
265  let leaf_pos: u64 = leaf_pos.into();
266  
267  let prover_witnesses = vec![
268      Witness::Base(Value::known(secret.inner())),
269      Witness::Base(Value::known(serial)),
270      Witness::Base(Value::known(pallas::Base::from(value))),
271      Witness::Base(Value::known(token_id)),
272      Witness::Scalar(Value::known(value_blind)),
273      Witness::Scalar(Value::known(token_blind)),
274      Witness::Uint32(Value::known(leaf_pos.try_into().unwrap())),
275      Witness::MerklePath(Value::known(merkle_path.try_into().unwrap())),
276      Witness::Base(Value::known(sig_secret.inner())),
277  ];
278  
279  // Create the public inputs
280  let nullifier = Nullifier::from(poseidon_hash::<2>([secret.inner(), serial]));
281  
282  let value_commit = pedersen_commitment_u64(value, value_blind);
283  let value_coords = value_commit.to_affine().coordinates().unwrap();
284  
285  let token_commit = pedersen_commitment_base(token_id, token_blind);
286  let token_coords = token_commit.to_affine().coordinates().unwrap();
287  
288  let sig_pubkey = PublicKey::from_secret(sig_secret);
289  let (sig_x, sig_y) = sig_pubkey.xy();
290  
291  let merkle_root = tree.root(0).unwrap();
292  
293  let public_inputs = vec![
294      nullifier.inner(),
295      *value_coords.x(),
296      *value_coords.y(),
297      *token_coords.x(),
298      *token_coords.y(),
299      merkle_root.inner(),
300      sig_x,
301      sig_y,
302  ];
303  
304  // Create the circuit
305  let circuit = ZkCircuit::new(prover_witnesses, zkbin.clone());
306  
307  let proving_key = ProvingKey::build(13, &circuit);
308  let proof = Proof::create(&proving_key, &[circuit], &public_inputs, &mut OsRng)?;
309  
310  // ========
311  // Verifier
312  // ========
313  
314  // Construct empty witnesses
315  let verifier_witnesses = empty_witnesses(&zkbin);
316  
317  // Create the circuit
318  let circuit = ZkCircuit::new(verifier_witnesses, zkbin);
319  
320  let verifying_key = VerifyingKey::build(13, &circuit);
321  proof.verify(&verifying_key, &public_inputs)?;
322  ```
323  
324  [^1]: See section 3: _The Commitment Scheme_ of Torben Pryds Pedersen's
325      [paper on Non-Interactive and
326      Information-Theoretic Secure Verifiable Secret
327      Sharing](https://link.springer.com/content/pdf/10.1007%2F3-540-46766-1_9.pdf)
328  
329  [^2]: [Merkle tree on Wikipedia](https://en.wikipedia.org/wiki/Merkle_tree)