Skip to content

Instantly share code, notes, and snippets.

@AdamISZ
Last active April 3, 2023 20:15
  • Star 3 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save AdamISZ/8dc3bbb00ac33e270029fe1cdb52f3f4 to your computer and use it in GitHub Desktop.
SNICKER - Simple Non-Interactive Coinjoins with Keys for Encryption Reused

Simple Non-Interactive Coinjoins with Keys for Encryption Reused

Gist!

Use pubkeys available on the blockchain (in scriptSigs/witnesses) to encrypt messages to owners of those pubkeys, these messages containing partially signed coinjoins. Broadcast these encrypted messages; owners scan for their own messages and broadcast as they choose. This is intended to be fully non-interactive so anyone can propose such transactions, and anyone who can decrypt such a message can choose to co-sign and broadcast.

Basic Coinjoin background

Each input to a transaction requires (for the transaction to be valid) a signature by the owner of the private key (using singular deliberately, restricting consideration to p2pkh or segwit equivalent here) over a message which is ~ the transaction. Each of these signatures can be constructed separately, by separate parties if indeed the private key for each input are owned by separate parties. The "normal" coinjoining process thus involves the following steps (for now, not specifying who carries out each step):

  • Gather all of the inputs - the utxos that will be spent
  • Gather all of the destination addresses to various parties, and the amounts to be paid
  • Distribute a "template" of the transaction to all parties (i.e. the transaction without any signatures)
  • In some order all of the parties sign the transaction; whomever has a transaction with all signatures complete, can broadcast it to the Bitcoin network

There are different protocols one can choose to get all these steps done, ranging from simple to complex. A server can be the coordinating party; blinding can be used to prevent the server knowing input-output mapping. Coinshuffle can be used, creating a kind of onion-routing approach to prevent parties involved knowing the linkages (doesn't require a server to coordinate, but requires more complex interactivity). One of the parties in the join can be the "server", thus that party gains privacy that the others don't (Joinmarket). Etc.

These approaches do require some interactivity; although the difficulties created by any interactivity are considerably ameliorated in a client-server model (see e.g. the old blockchain.info "SharedCoin" model), the serious tradeoff is the server knowing too much, and/or a coordination/waiting problem (which may be considered tolerable; see both SharedCoin and DarkWallet; with a sufficient liquidity pool the waiting may be acceptable).

There are a lot of details to discuss here, but there is always some interactivity (you can only sign once you know the full transaction, assuming no custom sighashing*), and a model with a server is basically always going to be more problematic, especially at scale.

So next we try to construct a way of doing at least simple Coinjoins, in at least some scenarios, without any server requirement or coordination.

Basic design for a SNICKER

We will consider only two parties Alice and Bob, for simplicity; so we are going to try to create only a 2 party coinjoin here. A larger number is deferred for later.

To make the Coinjoin non-interactive, we need it to be the case that Alice can post a message for Bob, without explicitly requesting to create a private message channel with him. This requires encrypting a message that can then be broadcast (e.g. over a p2p network or on a bulletin board).

(In case it isn't clear that either encryption or a private message channel is required, consider that Alice must pass to Bob her signature, which is on only her inputs; if that is seen in public, the input-output linkages are obvious to anyone watching.)

Encryption

To achieve this we need a public key to encrypt a message to Bob. In this "Basic Design" we will assume something naughty on Bob's part: that he has reused an address! Thus, a public key will exist on the blockchain which we assume (not guaranteed but likely; nothing dangerous if he doesn't) he still holds the private key for.

Given this admittedly unfortunate assumption, we can use a simple and established encryption protocol such as ECIES to encrypt a message to the holder of that public key.

Alice, upon finding such a pubkey, call it P_B, and noting the corresponding utxo U_B, will need to send several items to Bob to give him enough material to construct a valid coinjoin without any interaction with herself:

  • Her own utxos (U_A for simplicity)
  • Her proposed destination address(s)
  • Her proposed amounts for output (in some ultra simple form this might be inferrable from the next item)
  • Her proposed bitcoin transaction fee (can be implicit)
  • The full proposed transaction template using U_A and U_B as inputs
  • Her own signature on the transaction using the key for U_A
  • Her proposed destination address for Bob.
Destination

The last point in the above list is of course at first glance not possible, unless you made some ultra dubious assumptions about shared ownership, i.e. if Alice somehow tried to deduce other addresses that Bob already owns (involving more address reuse). I don't dismiss this approach completely but it certainly looks like a bit of an ugly mess to build a system based on that. Instead, we can use a very well known construct in ECC; in English something like "you can tweak a counterparty's pubkey by adding a point that you know the private key for, but you still won't know the private key of the sum". Thus in this case, Alice, given Bob's existing pubkey P_B, which is the one she is using to encrypt the message, can construct a new pubkey:

P_B2 = P_B + k*G

for some 32 byte random value k.

Alice will include the value of k in the encrypted message, so Bob can verify that the newly proposed destination is under his control (again we'll just assume a standard p2pkh address based on P_2, or a segwit equivalent).

Assuming Bob somehow finds this message and successfully decrypts it using the private key of P_B, he now has everything he needs to (if he chooses), sign and broadcast the coinjoin transaction.

A protocol for the most naive version, in broad strokes:

  1. Alice must have the ability to scan the blockchain to some extent; she must find scriptSigs or witnesses containing pubkeys which were later reused in new addresses/scriptPubKeys.
  2. Alice will use some kind of filtering mechanism to decide which are interesting. The most obvious two examples are: amounts under control in Bob's utxos matching her desired range, and perhaps age of utxos (so likely level of activity of user).
  3. Having found a set of potential candidates, for each case P_B, U_B: 3a. Construct a standard formatted message; here is a simple suggestion although in no way definitive:
    8(?) magic bytes and 2 version bytes for the message type
    k-value 32 bytes
    Partially signed transaction in standard Bitcoin serialization
    (optionally padding to some fixed length)

We defer discussing how in practice Bob will get to read the message via decryption till later; but note that if he has done this, he already knows the value of P_B and will thus know also U_B. Then, this format has sufficient information for Bob to evaluate easily. First, he can verify that U_B is in the inputs. Then he can verify that for 1 of the 2 outputs (simple model) has a scriptPubKey corresponding to P_B2 = P_B + k*G. He can then verify the output amounts fit his requirements. Finally he can verify the ECDSA signature provided on U_A (hence "partially signed transaction"). Given this he can, if he chooses, sign on U_B using P_B and broadcast. He must of course keep a permanent record of either k itself or, more likely, the private key k + x (assuming P = x * G).

Typical transaction structure

We have been describing the simplest case: 2 parties, 2 outputs and 2 inputs. There are positives and negatives in this model: it's positive that the transaction is fairly small (low fees). Negatives: trivial point is that 2 of 2 is an inferior coinjoin type in terms of not having privacy with respect to the counterparty. Making a coinjoin with Alice in x, Alice out x, and Bob in y, Bob out y, is ineffective at breaking linkage, under (for now) sensible assumption that this is not a payment from Alice to Bob. To put it another way, if that transaction is known to be a coinjoin, then it is trivial to infer the linkages; and x->x, y->y transactions don't occur otherwise at the moment. There might be ways around this. One approach is to find amounts that are close and fudge the difference with a combination of the bitcoin transaction fee and an incentive a la Joinmarket, and thus resulting in two equal outputs providing fungibility in the traditional coinjoin way.

Issues of practical realisation

This model is very simple in broad strokes. It can probably be implemented into wallets much more easily than a Joinmarket model, because the latter requires maintaining connections to an external messaging server and coordinating with (potentially disruptive) counterparties. The practicality issues here are different, and primarily about scalability.

The instigator (Alice) has to scan the blockchain for candidates. This is an issue, but the scanning work only needs to be done by one party and broadcast. They can simply list in public the keys and utxos where the keys have been reused.

Filtering can be done by Alice (e.g. by amount as already mentioned). Then candidate encrypted transactions can be created. Alice can create as many of these as she likes.

Where should the encrypted transactions be put? On some kind of fixed bulletin board for an initial test of the system, but longer term something more robust would be needed. Open question.

Bob's side - he may be incented to find transactions for himself if the above mentioned model is used for equal sized outs. He can find the encrypted transactions on the above mentioned bulletin board or whatever replaces it. He needs to be able to check if each of these is encrypted one of his public keys that have been reused (his wallet can keep a record of these easily). It's easy to see the scalability problem that could arise here - we could quickly be dealing with huge lists of encrypted records and a huge amount of such scanning. Finding a match occurs where the decryption has the correct initial magic bytes.

Disruptive junk in the encrypted lists: since no one is in charge of this encrypted transaction list, there's nothing stopping someone filling it with junk. One partial solution may be hashcash applied to the ciphertext; whatever the anti-spam mechanism, it has to be very easy to verify against, and not insanely complex or expensive for the creator.

* Sighashing - attempting a non-interactive coinjoin with some interesting use of SIGHASH_SINGLE and SIGHASH_ANYONECANPAY seems at least plausible, although it's not exactly heartening that no one ever uses SIGHASH_SINGLE (and its rules are arcane and restrictive), not to even speak of watermarking. Hopefully the idea expressed here is better.

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