Skip to content

Instantly share code, notes, and snippets.

@fyookball
Last active September 8, 2019 10:42
Show Gist options
  • Save fyookball/a6d38317b2a439c38caa6a17c3dd128b to your computer and use it in GitHub Desktop.
Save fyookball/a6d38317b2a439c38caa6a17c3dd128b to your computer and use it in GitHub Desktop.
Sharded Input Proofs for Cash Fusion

Sharded Input Proofs for Cash Fusion

Introduction

Cash Shuffle is a powerful tool for cycling a coin through many joined transactions. However, after shuffling a wallet, a user will inevitably wish to consolidate coins, and for this another tool is needed.

We need a method to coordinate coinjoin transactions with multiple inputs per user. This is inherently challenging because we want to hide input linkages while simultaneously attempting to blame/ban users who don't sign all their inputs.

This scheme takes a "sharding" approach whereby each player gives each other player only 1 input to verify.
(Assume we have 10 players using 9 outputs each). If it can be successfully implemented, this would be an improvement over schemes that trust the servers with information about linkages between inputs. In the long run, that trust could create pressure and incentives for bad actors to compromise servers.

Starting Out

First, all players will register on the pool and obtain a session key, which they can use to sign messages. The players then proceed to covertly announce their inputs, followed by covertly providing signatures for all inputs. If all inputs are provided and signed for, we are done. Otherwise, we continue.

Note that the convert announcement of inputs is problematic to do via the standard layered encryption method (repeated for multiple inputs) because it would be a huge DOS attack surface. Instead, participants should broadcast their inputs to the server over TOR. Although this is a slightly weaker method with regards to the server itself, it makes the implementation easy and speeds up the overall process greatly, which directly impacts DOS protection.

Salted Hashes of Inputs

Each player will create a set of salted hashes of their transaction inputs, with a separate secret salt value for each input. Once the hashes are computed, they can be ordered, ascending numerically, which provides an immutable ordered list that will be broadcast to the other players. This must be done prior to the next step (the sharding grid) so that players can't change the order after the fact.

The ordered list provides a distinct position for each input (e.g. Alice's "first" input and "second" input).

Setting up the Sharding Grid

We need a deterministically random way to create an ordering of the players. It needs to be random and also done after the players have announced all their inputs, in order to mitigate simple collusion attacks. (For example, if Zed and Zeeter are bad actors colluding, then it may be possible for Zed to exclude an input that Zeeter claims is present. With randomness, then Zed only has a 1/9 chance to pull off this attack.)

Here is one way to create the ordered list: Each player submits a random number to the server, and the server itself also chooses a random number. All the numbers are summed, and the sum is then hashed. In addition, we hash each random number separately. Then we run an XOR bitwise operation on each individual hash with the hashed sum to obtain a final score for each player. Finally, we sort the scores in ascending order.

Since we already established an input order for each player (with no prior knowledge of the player order), we can then utilize a simple rule: each input is encrypted and sent for verification to the player with a corresponding relative index (the sending players' index plus the index of their input using modular arithmetic). For example, suppose we had only 3 players and Alice is player 1, Bob is player 2, and Carol is player 3. Alice sends input 1 to Bob, input 2 to Carol, etc. Bob sends his input 1 to Carol, and his input 2 to Alice. Carol sends her input 1 to Alice and input 2 to Bob.

Note that this scheme is recommended to start with 10 players and 9 inputs, but could decrement to 9 and 8, or 8 and 7, etc under a blame management scheme in the protocol.

Ephemeral Keypairs for each Input

If the total number of inputs for all players is n, then we need to generate n emphemeral key pairs. Each private key will be generated by the player who is validating the input. So if Bob is required to validate A1 (Alice's first input), he will generate an ephemeral key pair and publish the public key for all the players. Only Alice will be using the public key to encrypt her input for Bob.

Alice will send her input information (her UTXO), and the secret salt value required to re-generate the announced hashed value, to Bob.

To ensure others cannot use Alice's public key (available to all) to impersonate Alice, is that all messages from players should also be signed by each player's session key. The reason that we need to make the public keys for all emphemeral pairs known to all participants is so we can assign blame, as we will see later.

If Bob cannot validate a proper salt value and valid UTXO...OR if he detects a violation of the ordering rules, he ends the round and assigns blame to Alice.

Standardized Input Amounts

Standardized input amounts were previously proposed in STAT as a way to handle "weakness from uniqueness". They are also necessary here, otherwise a player would be unable to prove that they contributed sufficient input funds.

Fees

Ideally, fees can be covertly announced to avoid any additional linkage issues between other inputs. Each player would contribute one small input to cover the fee and expect no change. For now the suggested approach is not complicate development by enforcing fees. Instead, simply include the proper fee in the software. In the unlikely event a transaction is underfunded, it can be guided along with Child-pays-for-Parent.

In the future, a straightforward (although non-trivial) scheme to enforce fees would be to replicate the same structure, with each player having one other deterministically random player verifying they paid a fee.

Assigning Blame

In this scheme, every input is validated by somebody (except the fees). The validation must check if the UTXO is valid and of the correct standard amount. The input plus the salt must match what was previously announced.

Suppose a dispute arises. Let's say that Bob maliciously blames Alice and says her input is fake. Now Alice must prove it is real, which she can do by sharing her input and secret salt for that input with everyone, which can be used by everyone to independently derive the hashed value that was previously announced. If she can do that, Blame is assigned to Bob and all of his inputs.

If Alice's input was really fake and she couldn't it prove it to Bob privately, then Bob will announce so, and Alice again won't be able to prove it publicly either, and she will be assigned blame.

What if Alice pretends to fake it and intentionally leads Bob to blame her. Could she then proceed to prove it publicly, causing others to ban Bob? No, because all messages are sent to all, although encrypted with ephemeral keys so that only the verifying party and the input owner know what is being verified. When blame is assigned, the accusing party reveals both their input and the ephemeral private key so that others know who is telling the truth.

Processing Blame

Because blame accusations require revealing an input, it is best to minimize them. Each player revealing only one input reveals no additional information about any linkages. If a player only has 1 person to blame, then the protocol behavior is clear: blame the bad actor.

There are different ways to handle multiple bad inputs. One is simply to just blame one of the 2 bad actors, and any blame will cause the protocol to start the round over without the bad actor, either by adding a new participant or shrinking the pool size. If there are multiple attackers, the chances are decent that multiple defenders will report them. And even if not, it will just cause the round to shrink one step at a time, if using that strategy.

Other more complex schemes could be derived based on revealing additional inputs (and blame) to a subset of participants. These kinds of schemes need to be mindful of "reverse attacks" where an innocent user is too easily blamed.

Protocol Phases

Phase 1. Registration on the Pool

Message 1A (from client): (<“REGISTER”>)

Message 1B (from server): (<“POOL READY”><POOL_SESSION_ID>)

Players connect to and register on the pool. The server should wait until all 10 users are registered on the pool before sending message 1B. Once there are enough players, fusion can begin. Also, the server should apply the proper blame filter from the previous round(s) and refuse to register a player with a banned IP.

Phase 2. Prepare Inputs and Ephemeral Keys

The client will take their list of their own inputs, serialize each one, generate a unique random salt (of sufficient size to prevent any grinding attacks) for each input, and then a salted hash for each input.

Each input needs to be of the correct size for the pool. For example, 10 inputs of 0.1 BCH each.

In addition, each player will create 9 ephemeral encryption keys, one for each input they will validate.

Phase 3. Announce Inputs, Ephemeral Keys, and Ordering

In this phase, each player will announce their list of (hashed) inputs, and also a list of 9 ephemeral keys, one for each input that they must validate. The list of hashes should be already sorted lexicographically. Each player should also create a “main” ephemeral public key which will be used later for blame.

Note that one of these "9 inputs" is actually an output, leaving 8 inputs. The ninth is the output address, but it still has an ephemeral key that validates it. It is necessary to include the output in this process rather than announcing it. This is because the protocol relies on revealing some information to other participants, and thus we need to keep the output ownership equally obscured. Also note that there are no change addresses used here.

The above sharding grid and description should be re-edited to include this clarification of validating 8 inputs and 1 output.

Message 3A (from client): <POOL_SESSION_ID>

<INPUT 1>...<INPUT 9>...

Once the server has received message 3A from all players, it sends message 3B, announcing all input hashes and ephemeral keys (“the payload”) for all players.

We also need to establish a random ordering of the players. This can be left to the server with a minimal amount of added trust, since the server is already essentially being trusted to be non-disruptive. Future versions can remove this trust by generating a random ordering via secret numbers, using additional steps.

The order number of each player can be announced in this message:

Message 3B (from server): <POOL_SESSION_ID><PAYLOAD_PLAYER 1><ORDER OF PLAYER 1>...<PAYLOAD_PLAYER 9><ORDER OF PLAYER 9>

Please note if any player fails to send a correct Message 3A, blame is assigned to that player and the round aborts.

Phase 4. Covert announcement of inputs

Once message 3B has been received, each client should covertly announce their inputs (using TOR), and only the POOL_ID, sending 9 different instances (one for each input) of the following message:

Message 4A (from client): <POOL_SESSION_ID>

Note these are the actual transactions, not hashes of transactions.

Phase 5. Announcement of unsigned transaction

Once all the inputs have been gathered from all players, they should be announced to everyone

Message 5A (from server): <POOL_SESSION_ID>

Note that even if the transactions is missing inputs at this point, we still continue to phase 6, because we need to collect signatures in order to process blame.

Phase 6. Covert announcement of signatures

In this phase, players should convertly announce their transaction signatures (using TOR), sending 9 different signatures (one for each input) using the following message:

Message 6A (from client) <POOL_SESSION_ID>

Note that there is an index that is passed along with the signature so it is clear which signature belongs to which input.

Phase 7. Sharing the signatures

Once all the signatures are collected, they can be rebroadcast to all players.

Message 7A (from server) <INPUT INDEX 1><SIGNATURE 1>....

Phase 8. Send Proofs

Each player will create 9 “proofs”. Each proof shall consist of a serialized input that is encrypted by the appropriate player’s key. This is based on the sharding grid, using the previously announced list of hashes and the ordering of players.

Message 8A (from client): <POOL_SESSION_ID>

<PROOF 1>...<PROOF 9>

Then the server sends to all:

Message 8B (from server): <POOL_SESSION_ID><MAIN PUBKEY Player 1><PROOF 1>...<PROOF 9>...<MAIN PUBKEY Player 10><PROOF 1>...PROOF 9>

Phase 9. Validate Proofs

The client will extract the proofs that it is responsible for, and checks each one. If it finds no problems, it will assemble the transaction and broadcast it to the BCH network.

If it finds a problem, it assigns blame.

Phase 10. Assign Blame

First the client notifies the server:

Message 10A (from client): <POOL_SESSION_ID>

Then the server notifies all clients with a similar message:

Message 10B(from server) <POOL_SESSION_ID>

Note that if the server receives several instance of Message 10A, it only needs to pick one, and should only pick one input to be blamed (for example the lowest one by lexicographical order)

Phase 11. Refute Blame

If Alice blames Bob, but Bob is innocent, Bob can refute the blame, while counter-blaming the accuser (Alice). He does that by sharing his ephemeral private key.

Message 11A (from client): <POOL_SESSION_ID>

The server can then rebroadcast the same message

Message 12A (from server): <POOL_SESSION_ID>

Phase 12: Process Blame

If the server sends message 10B, blaming one of the players, and it isn’t refuted after n seconds, then the blamed is guilty. The client should locate the input of the guilty party that they are validating and report it to the server:

Message 12A (from client): <POOL_SESSION_ID>

The server can use this information to ban those inputs in future rounds, but should take care to check if the reported inputs correspond via the sharding grid to the input that was originally blamed.

Once blame is assigned, the round can start over minus the offender, either as a set of 10 players or decrementing to 9, 8, 7, etc.

Edge Cases for "Extra" Inputs or Outputs

Insufficient inputs or outputs are relatively straightforward in terms of blame. Extra inputs could be ignored because they only add money to the transaction. Extra outputs can also be ignored if we can identify the correct ones, but this may requires special handling or extra steps.

@markblundeberg
Copy link

For list randomization: it's best if all sources (players and server) commit to their numbers and share commitments, before the numbers themselves are revealed. Otherwise the person who goes last can choose their random number to tweak the final result.

@fyookball
Copy link
Author

fyookball commented May 1, 2019

@markblundeberg The server choosing a random number prevents the necessity of that, but as you pointed out, then why not just have the server generate a random number and use that (since we would now be trusting the server not to engage in grinding attacks for the purposes of collusion). In practice, we may do this although your (other) suggestion posted here to use commitments is slightly stronger (at the cost of complexity). edit: for clarity.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment