Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Shielded values, splitting and joining #24

Open
HarryR opened this issue Jul 11, 2018 · 2 comments
Open

Shielded values, splitting and joining #24

HarryR opened this issue Jul 11, 2018 · 2 comments

Comments

@HarryR
Copy link

HarryR commented Jul 11, 2018

While a mixer with fixed denominations is a good starting point, without the ability to shield the total value, or splitting and joining coins it has limited use and has side-channel leaks which reveal the total amount of value being transferred (e.g. a 10 ETH transaction requires 10 separate transactions, rather than 1).

Is there a solution that works with the current proving code which would allow for the total value to be shielded, for coins to be split and joined etc. as long as the total value doesn't change (e.g. split a 1 ETH coin into two 0.5 ETH coins).

@barryWhiteHat
Copy link
Owner

#Sheilded values
are only really of use once you do do splitting and joining otherwise they destroy your anonymity set with the following heuristic. Track the balances going in and going out. The out going transaction of value X belongs to the user who most recently deposited value X.

Spliiting and joining

So there are some problems with this. In a zksnark it is quite difficult to do splitting and joining beacuse you cannot do a < or > easily. You can do it by using a binary circuit but that adds alot of constarints and complexity.

The other reason I did not add this in mixmus is that I thought people would not use it due to the gas costs. I thought they would use it just like zcash and do a single mix. and then move their coins.

I do plan to add shielded value, splitting and joining but in a separate project that uses a side chain to make the transactions cheaper.

@HarryR
Copy link
Author

HarryR commented Jul 16, 2018

It's not difficult to do splitting or joining with zkSNARKs, and the number of constraints for a binary adder with carry etc. is trivial in comparison to even one round of SHA256.

The following is a (pseudocode) specification for the contracts to do splitting and joining while keeping the values occluded. Taken with inspiration from: https://github.com/ConsenSys/zero-knowledge-proofs/

However, this diverges slightly from the merkle tree proof in miximus which avoids revealing exactly which coin was spent, instead this mechanism reveals which coin was spent - making the SNARK circuit much simpler (e.g. no Merkle tree proof) - but hides the values of what was spent.

Simple non-anonymous Deposit & Withdraw

  • The value field is private, unless it's the first deposit, then the value is known
  • With the initial deposit you provide a SNARK proof of SHA256(public(value)||private(secret)) == public(key_image) - the value and key_image are provided as public inputs.
  • To spend withdraw a coin you provide the key_image and the value, with a SNARK proof that you know the secret of the key image.
  • Up until this point, there is real anonymity, values are known, the spender is known etc.

Each key_image spend is tracked on-chain using a simple mapping(), this makes double-spend protection much easier as it's an on-chain database lookup.

Deposit / Withdraw circuit

def deposit_or_withdraw_circuit(public_value, private_secret, public_keyimage):
    return public_keyimage == HASH(public_value, private_secret)

Splitting coins, with shielded value

In this example you want to spend a coin, and split it into one or more coins, the value of the input coin you spent isn't revealed, nor is the individual value of output coins:

  • To spend the input, you provide the key_image and the value, with a SNARK proof as per the Deposit / Withdraw circuit above.
  • To create the outputs you provide the key images

Split circuit

def split_circuit(public_in_value, private_in_secret, public_in_keyimage, public_out1_keyimage, private_out1_value, private_out1_secret, public_out2_keyimage, private_out2_value, private_out2_secret):
    if HASH(public_in_value, private_in_secret) == pub lic_in_keyimage:
        if (private_out1_value + private_out2_value) == public_in_value:
            # XXX: the adder circuit needs to abort if the `carry` flag is triggered, to avoid overflows
            out1_ok = HASH(private_out1_value, private_out1_secret) == public_out1_keyimage
            out2_ok = HASH(private_out2_value, private_out2_secret) == public_out2_keyimage 
            return out1_ok and out2_ok

Join circuit

def join_circuit(public_in1_keyimage, private_in1_value, private_in1_secret, public_in2_keyimage, private_in1_value, private_in1_secret, public_out_keyimage, private_out_secret):
    if HASH(private_in1_value, private_in1_secret) == public_in1_keyimage:
        if HASH(private_in2_value, private_in2_secret) == public_in2_keyimage:
            # XXX: the adder circuit needs to abort if the `carry` flag is triggered, to avoid overflows
            out_value = (private_in1_value + private_in2_value) 
            return HASH(out_value, private_out_secret) == public_out_keyimage

Enhanced Anonymity

If the initial split circuit takes a merkle path proof for the input coin, then which coin is being split is unknown to the observer.

However, this requires two types of coins:

  • Fully anonymous (requires merkle tree insertion & proof), known value
  • With public key image (for tracking), unknown value

If you spend a fully anonymous coin, then split it into key-image-tracked coins then the anonymity of the key-image-tracked coins is greatly enhanced because it increases the anonymity set of to 1-of-any .

Key-image-tracked coins can still be linked together, but a the correct security protocol their value and origin will be unknown.

The problem is that the merkle tree proof is an expensive circuit.

TODO: more details

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants