Raised in #4 by @uivlis

* G1 elements in proof: 2
* G2 elements in proof: 1
* Proof size in bits: 1019
terminate called after throwing an instance of 'boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::property_tree::ptree_bad_path> >'
  what():  No such node (gammaABC)
Aborted
make[1]: *** [test] Error 134
make[1]: Leaving directory `/home/ubuntu/workspace/python'
make: *** [python-test] Error 2

Presumably originates from:

• https://github.com/HarryR/ethsnarks-miximus/blob/master/python/miximus.py#L119
• https://github.com/HarryR/ethsnarks-miximus/blob/master/python/test/test_miximus.py#L44

The Python code passes a JSON blob to the native verifier containing the verification key.

Two ways to debug this would be:

1. In https://github.com/HarryR/ethsnarks-miximus/blob/master/python/miximus.py#L116 add a print statement for self._vk.to_json().encode('ascii')
2. In https://github.com/HarryR/ethsnarks-miximus/blob/master/circuit/miximus.cpp#L314 add a print statement for vk_json

This would verify that the JSON is in the correct format in Python, and verify that it's being received correctly by the C++ library.

He said the first error he ran into was:
TypeError: the JSON object must be str, not 'bytes' in line 110 from miximus.py. I changed

return Proof.from_json(data)

into

return Proof.from_json(data.decode('ascii'))

It would be nice to add this extra complexity so that we have a single general snark that can be used for mixing plus a bunch of other anon signaling stuff.

This would include adding

1. external nullifiers
2. signal
3. signal_variables

We would also need another hash of external_nullifier and nullifier. Tho this hash function is already added https://github.com/HarryR/ethsnarks/issues/72#issuecomment-436457227

An issue may exist with Miximus as it is now, taken from: https://ethresear.ch/t/anonymous-reputation-risking-and-burning/3926/2

@khovratovich comments

I started reading “How Miximus works” and noticed you use nullifiers to prevent double spending. However if nullifier can be chosen arbitrarily, there is a potential front-run vulnerability: an attacker sees your nullifier before the transaction is mined and tries to slip in with his own leaf and the same nullifier, trying to spend it immediately.
This attack applies to Zerocoin, but in Zerocash/Zcash it was fixed by requiring the nullifier be deterministic function of the recipient public key. You can do something similar.

@yondonfu comments

For Miximus, instead of using external_nullifier, perhaps you can define nullifier = H(nullifier_secret) and use nullifier_secret as a private input in the circuit while keeping nullifier as a public input. The zkSNARK proof would then also demonstrate that you know the pre-image for nullifier allowing you to withdraw from the contract. An attacker doesn’t gain anything from front-running your withdraw tx because even though he/she can create a leaf with the same nullifier, he/she will not be able to withdraw it without knowing the pre-image for nullifier.

The circuit for Miximus is currently:

spend_hash = H(spend_preimage_var, nullifier_var)
leaf_hash = H(nullifier_var, spend_hash)
assert merkle_authenticate(path_var, address_bits, leaf_hash)

The leaf can be inserted by a third party without knowing the spend preimage. However they do know what the nullifier is so they can track if and when the leaf has been spent.

However, when publishing a proof the nullifier can be replayed, somebody can insert a new leaf with the same nullifier then withdraw it - denying the original leaf owner the opportunity to withdraw their own leaf.

The nullifier_var is specified by the withdrawer

So, there are possibly 2 problems:

1. When the depositor and withdrawer are different parties, the depositor knows when it has been withdrawn - this leaks information.
2. The nullifier can be replayed by an observer

In an ideal world the following statements are true:

• When the depositor and withdrawer are different parties, the depositor must not know when their deposit has been withdrawn
• When a depositor makes the deposit, the owner of the spend key must be able to observe that the deposit which only then can withdraw has been made.
• Any observer cannot be able to associate the deposit and withdraw by observing the nullifier and leaf hash
• When a withdraw is made, no observer will be able to deny them, via front-running, the ability to withdraw their funds.

The preimage to the leaf is never revealed to the public - but the leaf is public knowledge an observed by everybody. The constituents of the leaf are known only by the two parties of the transaction.

Can we fix this? yondonfu suggests using a secret for the nullifier, which is known between only the two parties of the transaction, which fixes the second problem, for example:

spend_hash = H(spend_preimage_var, nullifier_secret)
leaf_hash = H(nullifier_secret, spend_hash)
assert merkle_authenticate(path_var, address_bits, leaf_hash)
assert H(nullifier_secret) == nullifier_var

But, what about the first problem? Making it so that the depositor cannot know when their deposit has been withdrawn?

TODO: add pseudocode into miximus.hpp

As per: https://hackmd.io/@HWeNw8hNRimMm2m2GH56Cw/rJj9hEJTN?type=view

The interface proposed is more agnostic to the underlying crypto being used:

The mixer has two functions:

• deposit(bytes32 commitment) payable verifies that DENOMINATION ETH (eg. 1 ETH) was sent along with the call, and if so it adds the commitment to a list of commitments. It also maintains a Merkle tree of all commitments to far that uses some SNARK-friendly hash function (even Pedersen to start off would be ok).
• withdraw(address destination, bytes proof) verifies that (i) proof is a valid ZK-SNARK that proves that destination and some commitment in the tree are related to each other (eg. destination = H(commitment + salt)) but does not reveal which commitment the witness corresponds to, and (ii) destination has not yet been used. Upon success, it pays out DENOMINATION - FEE to the destination and FEE to msg.sender

We should adjust the interface used by Miximus to adhere to this specification.

Instead of just supporting ETH, it should be possible to deposit & withdraw multiple different token types.

It should also be possible to perform atomic swaps between tokens, internally.

i am on ubuntu 20.04 , all steps work fine except for the 'make' step

when i execute the make command, i get this error

When I try to compile on macOS Mojave it gave error, however it works fine on Ubuntu 18.04.

make CMAKE=cmake

This will have error "gmp.h" not found. But when I test with a simple cpp program with "#include <gmp.h>", it works fine and can find the gmp.h.

Currently the proof is bound to the msg.sender parameter, the money is withdrawn to this address.

This means a relay service can't be used because there is no separate transfer address who will receive the funds, nor is there a way of specifying how much of a cut the relayer will receive from the withdraw.

We need to create a clear and concise specification for the Miximus / Semaphore circuit so it can externally and more formally validated.

• LongsightF implementation
• LongsightF parameters, parameter choices
• Merkle tree construction using LongsightF, with shorter individual rounds but equivalent rounds given height of tree
• Leaf hash semantics for both Miximus and Semaphore
• Anonymity properties, breakdown of the guarantees and how they are achieved

Need to put this into a markdown file, with appropriate diagrams, so that it can be made into a PDF file for general distribution.

Need to reference relevant academic papers specifically for the safety of LongsightF in the tree construction. (TODO: dig these out from UOWHF research, Merkle-Damgård construct etc.)

LongsightF implementation

TODO: circuit diagram for round function

Number of constraints

Parameters

For the leaf:

• LongsightF-r322-e5
• Rounds: 322
• Exponent: 5

For tree nodes:

• LongsightF-r12-e5
• Rounds: 12
• Exponent: 5
• Tree height: 29

Tree construction

Where H_n() is the LongsightF-r12-e5 function for nodes.
Where H_l() is the LongsightF-r322-e5 function for leafs.

• leaf_i = H_l(A_i, H_l(B_i, C_i))
• node_... = H_n(leaf_i, leaf_i+1)
• node_... = H_n(node_..., node_...)

Leaf Hash Semantics

Miximus and Semaphore have different semantics, namely Semaphore requires an additional property which Miximus doesn't.

Each leaf requires the following properties:

• One component of the hash, T, serves as a unique tag, this prevents double spends, double voting etc.
• leaf is public, given leaf and knowledge of A, no participant other than the spender should be able to know that T is related to A or leaf.
• Note: why is there a separate A when the hash could just be H(C, T) where C is a random Nonce?

The leaf construction is:

• B = H(C, T)
• leaf = H(A, B)

With Miximus each leaf can only be used once.

With Semaphore the leaf may be used multiple times, so the tag needs to be mixed with the unique parameters for that specific signal type.

Truffle seems to frequently break in really really dumb ways.

Candidates to replace truffle:

• https://github.com/embark-framework/embark (JS based)

The Miximus circuit is lacking functionality which allows tokens to be 'fungible'.

Currently each leaf is of a fixed denomination, if that denomination is 1 ETH then you need to make 10 transactions to make a 10 ETH payment. And if you want to make a 0.1 ETH payment, then you're out of luck.

This ticket proposes a mechanism to make deposits, payments and withdraws of arbitrary values, meaning that you're not constrained to using coins of a specific denomination.

Currently, with fixed denominations, you must deposit that denomination and in return the smart-contract inserts a leaf into the tree. Because the smart contract enforces the deposit values we know that every leaf is of a specific value, and nullifying a leaf allows that value to be withdrawn (and optionally transferred to another person, by immediately creating another leaf).

By introducing the notion of arbitrary values, it means that each leaf can have a different value, and the zkSNARK circuit must strictly enforce the value. The following modifications to how Miximus works allows for arbitrary values to be exchanged:

New leaf format (ish):

leaf = H(value || nullifier_hashed)

• Deposit
  • zkSNARK proof is provided that the leaf which will be inserted into the tree matches the deposit amount
  • Inserts leaf into tree
• Split
  • Spends a leaf, by proving knowledge of its nullifier
  • Inserts two new leaves
  • Ensures the sum of the two new leave is equal to the spent leaf
• Join
  • Spends two leaves, by proving knowledge of their nullifiers
  • Nullifies the two leaves
  • Inserts one new leaf
  • Verifies the value of the new leaf is the sum of the two spent leaves
• Withdraw
  • Proves knowledge of one nullifier
  • Proves the withdrawn amount is equal to the value of the leaf

Use cases:

• To send a payment to somebody you perform a Split transaction, which spends one of your unspent outputs and creates two new leaves - one owned by you for your change, and another owned by the recipient of the payment.
• To aggregate incoming payments into a single leaf you perform a 'Join' transaction

Problems:

• The join/split process could allow correlation of payments

Questions:

• Is there a way to avoid having to consolidate funds using a 'join' transaction?

I am a user, I want to use Miximus, I have tokens or Ether which I want to convert into anonymised tokens. How do I do this?

Once my tokens have been anonymised I need to withdraw them again, to convert them back to the original tokens or Ether that I originally deposited. I should also be able to give these anonymised tokens to other people, without revealing that it was I that deposited them. As a user, should it be possible to lose access to my anonymised tokens even though I still have the private key for my Ethereum account?

We need to make a proof of concept application which uses Miximus and allows users to do common tasks, like deposit, withdraw, transfer etc.

There is JavaScript code which uses node-ffi and web3 to perform deposits/withdraws: https://github.com/HarryR/ethsnarks-miximus/blob/master/solidity/test/TestMiximus.js

And Python code to use the native module to create proofs: https://github.com/HarryR/ethsnarks-miximus/blob/master/python/test/test_miximus.py

Using either of these, can a proof-of-concept application be created that allows people to use Miximus more easily?

How does this work as a command-line application?

The command-line app needs to connect to an Ethereum full node, it needs to store state, provide a mechanism for converting currency into anonymised tokens, and provide a mechanism for converting the anonymous tokens back in to the original currency.

e.g.

$ miximus deposit 10 ETH
 - Deposited
$ miximus balance
 - 10 ETH
$ miximus send 5 ETH <my-friend>
 - Sent
$ miximus balance
 - 5 ETH

Then as

$ miximus balance
 - 3 ETH
$ miximus withdraw 3 ETH
 - Withdrawn 3 ETH
$ miximus balance
 - 0 ETH

Then as me again:

$ miximus withdraw 5 ETH
 - Withdrawn 5 ETH
$ miximus balance
 - None

There is a problem with this 'ideal user flow' - at any given point in time you know exactly what your balance is, you can send money to others, and withdraw an arbitrary amount. This matches the account model of Ethereum (and most other wallets) by creating a useful abstraction regardless of the number of underlying transactions, for example with Bitcoin you have N UXTOs which represent your balance.

This makes anonymity difficult because with a UXTO model your account can be correlated to determine the exact value of a transfer - e.g. if I do 10 transactions with a fixed coin size of 1ETH then 'they' know I'm sending 10 ETH to somebody.

Technical Challenges

How do you have an account-style model with anonymous tokens?

Following on from ZCash you need a split and join circuit, in addition to an arbitrary value for the transactions.

For example, you deposit 10 ETH, you now have a single token worth 10 ETH. You can then transfer 5 ETH to a friend by using a 'split transaction' where you take a single input and output two new coins. To receive the coins you need to use a Join transaction to combine your current balance with the new input. If 100 people send coins to you, you'd need to perform 100 join transactions to collect it all into a single account.

The alternative is a UXTO model where your available funds exist as separate coins, however in that case if you had denominations of 0.3, 0.5 and 0.2 you'd have to create a join transaction with 3 inputs and 1 output. This becomes a problem when the circuit is of a fixed size.

Compromise between usable and perfect

In a perfect world the zkSNARK circuit could join an unlimited number of inputs into an unlimited number of outputs, this is technically possible if you were to process the merkle tree update for spendable coins within the circuit - but that limits everybody to 1 transaction per block otherwise everybody else gets rejected due to conflicts.

What is the worst case though?

In the Withdraw contract, we must verify that all inputs are within the snark scalar field to avoid aliasing.

For example, there may be multiple uint256 values which wrap-around to produce the same point after scalar multiply, all of these are outside of the field.

Re:

• https://github.com/argentlabs/hopper/issues/9
• semaphore-protocol/semaphore#16
• HarryR/ethsnarks#140

This will be fixed upstream in Ethsnarks.