Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
SNICKER BIP draft

  BIP: ??
  Layer: Applications
  Title: SNICKER - Simple Non-Interactive Coinjoin with Keys for Encryption Reused
  Author: Adam Gibson <AdamISZ@protonmail.com>
  Comments-Summary: No comments yet.
  Comments-URI: -
  Status: Proposed
  Type: Informational
  Created: -
  License: BSD-2-Clause

Table of Contents

Abstract

SNICKER (Simple Non-Interactive Coinjoin with Keys for Encryption Reused) is a simple method for allowing the creation of a two party coinjoin without any synchronisation or interaction between the participants. It relies on the idea of reused keys (either reused addresses, or identification of ownership of signed inputs and thus pubkeys in signatures). The address reuse scenario may mean that this is suitable as a privacy repair mechanism, but it would likely be used more broadly as a method for opportunistic coinjoin requiring literally zero user (inter)action within wallets. The implementation requirements for wallet developers are minimal.

For a discursive treatment of the idea, see the original blog post[1] (although any conflicting details are superseded by this document).

The purpose of this document is to standardise those features of the protocol which could be shared across wallets.

Copyright

This BIP is licensed under the 2-clause BSD license.

Motivation

Existing use of CoinJoin [2] is very valuable in creating sets of utxos in an obfuscated/mixed state, leveraging to the maximum what has sometimes been called the "intrinsic fungibility" of Bitcoin.

As well as past systems such as SharedCoin[3] and DarkWallet[4], we have, as of writing in mid-2019, JoinMarket[5], Wasabi Wallet[6] and Samourai's[7] tools Whirlpool and Stowaway. Coinshuffle[8] is an example of an arguably more powerful cryptographic protocol to achieve similar goals, although as of writing is not in production use on Bitcoin.

The most difficult thing about these CoinJoin protocols and systems is that they require coordination between participants, which can be difficult in any case, but is *especially* difficult when we want to ensure a strong level of anonymity for the participants. A logical way to ameliorate this problem is to have a coordinating server to create CoinJoin transactions, but this is a tradeoff which degrades the privacy guarantees of the user (even if very subtly), and can also be fragile to attack (central point of failure). Giving any detailed information to a server over a network connection is problematic, even when those connections are over an anonymising network like Tor.

On the other hand with no controlling central party, Sybil attacks can be quite effective in damaging the viability of such protocols in various ways - jamming the protocol, snooping the network level, Sybilling to swamp the participant and break or severely damage the privacy boost he was trying to achieve, or in cases like Joinmarket, damaging the economic incentive model.

SNICKER tries to occupy a radically different position in the landscape of tradeoffs here. No coordination or synchronisation is needed between users, all that is needed is one side to broadcast encrypted data, and the other side to receive it. The reception could happen over radio or satellite, so that it's basically physically impossible for anyone to know what happened (this is not a suggestion; just illustrating how important the broadcast element is). The SNICKER coinjoin model is very limited, as laid out in this document (2 party only!), but it's considered that for some scenarios, this is a worthwhile tradeoff because all of the coordination issues are no longer applicable.

Conceptual summary

The basic idea is for one party, using information only from the blockchain, to create a partially signed coinjoin transaction, deducing an output for a second party without their involvement, then encrypting that proposal and broadcasting it to the world in some way. Note the proposal is for a 2 party coinjoin (more parties is theoretically possible but much more complex). Such proposals can be constructed based on making inferences from public keys seen on the blockchain - either from address reuse or simply extracted from transaction inputs. Notice that multiple proposals with the same input utxos is not problematic. Whether such proposals will be taken up (i.e. downloaded from some server, decrypted, co signed and broadcast onto the Bitcoin network) will depend on whether the proposal is valid (i.e. whether keys were correctly identified), whether the counterparty is aware of the proposal, and whether they are willing to do the coinjoin. For the latter, economic incentives are relevant.

Identification of candidates

For the former of the two points just mentioned, it'll be important for the first party (the "Proposer") to find candidates with some reasonable (even if low) probability. This could be bootstrapped by choosing on-chain keys participating in transactions with certain flags (for example: Joinmarket transactions). Over time, this could be supplanted by searching for transactions which themselves are already SNICKER (hence "bootstrap" - after some time SNICKER txs could spread into a large graph).

We will see in the Specification below, that there are two ways proposed for making this identification - address reuse or inference of co-ownership of pubkeys in transaction inputs. It is worthy of note here that another option without address reuse will exist if and when Taproot[9] is activated on the Bitcoin network, since in that case the scriptPubKey will expose the pubkey directly.

Specification

Here we seek to standardise certain features, to make it feasible for a wallet software developer to create an implementation of SNICKER that is compatible with other wallets.

It is noted however that due to the scanning/searching nature of the behaviour of the Proposer, it may be that wallet developers would find focusing only on the Receiver side of the specification is more practical (or, occasionally, vice versa).

Definition of Terms

  • Proposer - scans the blockchain for relevant information, then creates a partially signed coinjoin transaction and publishes an encrypted version of it on the bulletin board.
  • Receiver - discovers the encrypted version of the partially signed coinjoin transaction on the bulletin board (or otherwise) and decrypts it, co-signs it (if desirable) and broadcasts it onto the Bitcoin network.
  • Bulletin board - Any public read/writable location, ideally publishing to it and reading from it should be anonymous, so a good example is a Tor hidden service.
  • c - the tweak used to generate a new destination for the Receiver (32 byte group element, encoded as for private keys).
  • C - ciphertext
  • ECDH(P, Q) - outputs a 32 byte shared secret between owners of P and Q, defined the following operations:
    • given a secp256k1 pubkey P with known privkey p and a second secp256k1 pubkey Q:
    • perform scalar multiplication to derive a new pubkey: p * Q
    • serialize this pubkey as for Bitcoin (so, 02 or 03 are prepended to the x-coordinate and the complete serialization is exactly 33 bytes)
    • Calculate the 32 byte **shared secret** S as: S = SHA256(serialized pubkey from previous step)
    • Note that this process is that followed by the libsecp256k1 ECDH module[10]
  • ECIES-E(P, m) - outputs an encryption of message m to secp256k1 public key P, defined by the following operations[11]:
    • construct a new secp256k1 pubkey R from a newly generated privkey r.
    • perform scalar multiplication to derive a new pubkey S: S = r * P
    • serialize both these pubkeys as for Bitcoin (so, 02 or 03 are prepended to the x-coordinate and the complete serialization is exactly 33 bytes). Call these R-ser, S-ser.
    • calculate K = SHA512(S-ser)
    • Set IV equal to the first 16 bytes of K. Set K-AES to the second 16 bytes of K. Set K-MAC to the last 32 bytes of K.
    • Perform AES128 encryption of the message m with IV IV and encryption key K-AES. Use PKCS 7 as the padding method and CBC as the block cipher mode. Let the ciphertext output be C = AES128-CBC(IV, K-AES, m).
    • Calculate a MAC using HMAC-SHA256 with the key K-MAC to find mac = HMAC-SHA256(K-MAC, C).
    • Concatenate to find the output bytestring, first prepending 4 magic bytes BIE1 or 0x42494531 : o = 4 magic bytes || R-ser || C || mac.
    • Finally, the output can optionally be base64 encoded for transfer. Note that this algorithm, including the specific magic bytes, conforms to that used currently by Electrum[12].
  • ECIES-D(p, o) - outputs the decryption of an ECIES output o, assuming it had been encrypted to the pubkey P for which p (which the decryptor must possess) is the privkey.
    • base64 decode o if necessary.
    • check that the decoded o has first four bytes 0x42494531 and reject otherwise.
    • deserialize bytes 5 to 37 into a secp256k1 pubkey object R; reject if this operation fails.
    • perform scalar multiplication to derive a new pubkey S: S = p * R
    • serialize S and R as for Bitcoin (so, 02 or 03 are prepended to the x-coordinate and the complete serialization is exactly 33 bytes). Call these R-ser, S-ser.
    • calculate K = SHA512(S-ser)
    • Set IV equal to the first 16 bytes of K. Set K-AES to the second 16 bytes of K. Set K-MAC to last 32 bytes of K.
    • split the remaining bytes of o into two sections: the last 32 bytes and the bytes from byte 38. The first is called mac and the second is called C (ciphertext).
    • First check that mac is a valid mac on C with the key K-MAC: mac ?= HMAC-SHA256(K-MAC, C). Reject if false.
    • Perform AES128 decryption of the ciphertext C with IV IV and decryption key K-AES. Use PKCS 7 as the padding method and CBC as the block cipher mode. The final plaintext output of decryption, m, is then: m = AES128-CBC(IV, K-AES, C).
We cover the two types of SNICKER separately, starting with the simpler but perhaps less interesting version - address reuse.

SNICKER Protocol Version 00 - Reused Keys

Proposer actions

The Proposer will need to identify a set of addresses which are reused (specifically, has an unspent output currently existing, and previously spent from at least once). This could be global or restricted in some way (e.g. recency of usage, specific wallet type etc.), and may be found via direct blockchain scanning.

For each reused address A, he will find the public key P_A from the/a previous spend. He will then take these steps:

  • Find one and only one utxo of his own to spend, whose bitcoin value is greater than or equal to: value of utxo owned by A, plus approximately the transaction fee for a 2-in 3-out transaction.
  • Construct a new tweak c (see "Terms" above), using specifically this method (The reason for this specific method will be made clear here):
    • First, take the public key of the utxo input chosen in the previous step, call it Q, and its corresponding private key q.
    • Calculate c = ECDH(Q, P_A)
  • Construct a new destination address using pubkey P_A + cG and of the same address type as A.
  • Construct a transaction with inputs: (existing utxo owned by A, his own utxo owned by Q) and outputs: (P_A + cG, his own freshly generated output addresses O1 and O2). The amounts will be such that each party (Proposer, Receiver) receives back approximately what they put into the transaction, but the acceptability of the amount is for the Receiver to decide. O1 MUST receive exactly the same amount as P_A+cG and O2 should contain the change required to balance for the Proposer.
  • He signs the transaction for his own input, so it is partially signed.
  • He serializes the partially signed transaction and the tweak value c according to the serialization specification below, calling this serialization M, he outputs and publishes a **Proposal**: ECIES-E(P_A, M).
  • He publishes this Proposal (as according to definitions, it should be base64 encoded) to the Bulletin board.
These steps can be repeated for every address A. Note: he can if he wishes continue to reuse the same input utxo for each of these proposals, since if the Receivers find that it is already spent, there is no harm done. This would be a kind of "first come, first served".

Format of transaction Proposal

The proposer constructs the message m before encryption as follows:

  1. 7 bytes: magic, binary 'SNICKER' i.e. 0x534e49434b4552
  2. 2 bytes: version, specifically:
    • First byte is a version, currently only 00 and 01 are defined (see below for Version 01). So here this MUST be the byte 0x00.
    • Second byte represents a set of flags. For version 00 and 01 no flags are defined and so this value MUST be 0x00.
  3. 32 bytes: tweak value c calculated as explained above. This MUST be a valid element of the additive group of integers modulo N (where N is secp256k1's N), i.e. it must be a valid raw private key in the Bitcoin sense. The encoding must be a big endian serialization of the 256 bit integer. Note this must be fixed width i.e. always 32 bytes.
  4. Variable size: A partially signed bitcoin transaction according to the specifications of PSBT, as specified in BIP174[13]. Note that this should be the binary serialized variant and not the base64 encoded variant. See next subsection on rules for the content of this PSBT.
Partially signed transaction

The Proposer can be flexible in some aspects of creation of the transaction proposal above, but these conditions must be met for BOTH Version 00 and Version 01, note that the list may substantially differ for other versions. Note that explicit choices are always preferred here, since multiple implementations could otherwise risk creating watermarks from individual Proposers.

  1. (see subsection 'A note on address types' below). At least one output MUST have ScriptPubkey: for Version 00, (address type as for P) using single public key: P + cG
  2. Transaction version MUST be 02
  3. Transaction locktime MUST be 0, and sequence numbers MUST be 0xffffffff. Opt-in RBF[14] is probably not practical in this type of protocol, so the proposal here requires using the simplest (default) values.
  4. There MUST be AT LEAST TWO outputs with the exact same output value in satoshis, and one of those outputs must be the one to the Receiver as specified in item 1 above.
  5. There MUST be ONLY ONE input that the Receiver currently owns. This must be the/a utxo that is controlled by (address version of P) P.
  6. The Bitcoin transaction fee applied to the proposed transaction is not restricted; the Receiver will decide if it is acceptable or not.
  7. The ONE input NOT owned by the Receiver (see above) MUST be finalized as per the terminology of BIP174, that is to say, it must have fields 0x07 finalized scriptSig and/or 0x08 finalized scriptWitness completed and valid.
  8. The inputs and outputs should be ordered according to BIP69[15]. Note that current usage on the network is split between random ordering and BIP69 deterministic random, here the latter is chosen since it's observable and checkable by the receiver.

A note on address types

The spirit of the proposal as defined here for Versions 00 and 01 is that the new output created by the Proposer for the Receiver should be of the same type as the input being consumed, to somewhat improve privacy, but mostly to ensure that the wallet will be able to understand the new utxo created. However this could get quite complicated in case of customised scriptPubKeys created by more advanced wallets. Hence for simplicity we assume that addresses for which utxos are being consumed MUST be of one of the standard single key types, that is:

  • P2PKH (i.e. '1' addresses)
  • P2WPKH (segwit native single key, bech32 addresses)
  • P2SH-P2WPKH ('3' addresses wrapping segwit native p2wpkh)
Handling multisig or custom scripts including e.g. locktimes is currently considered out of scope but could in principle be added in future versions.

Receiver actions

The Receiver will need to keep a record of addresses (and corresponding keys) that he has reused. Let's call these addresses A as above.

The Receiver checks the Bulletin board periodically. He downloads all encrypted blobs that might be relevant (applying filters if the Bulletin board supports this, see section on Bulletin Board below).

For each blob (after being base64 decoded), calling the binary blob o, he should attempt to decrypt according to ECIES-D(p_A, o) where p_A is the private key of address A. As well as performing the checks defined in that operation, he can also check:

  1. Whether the first 7 bytes match the required SNICKER magic bytes: 0x534e49434b4552
  2. Whether the version is or is not 0x00.
If those checks pass, he should find the value c, and a valid partially signed bitcoin transaction serialization. He then performs the following checks:
  1. Optional; if not included, the second option in "Storage of Keys" below MUST NOT be assumed to be available (i.e. if not included, the wallet MUST import the new keys and MUST inform the user that persistent wallets are required for funds recovery):
    1. For the public key of the finalized input in the PSBT, call the pubkey Q, calculate c = ECDH(Q, P_A) and check if it matches c. If not, reject.
  2. Is one of the destination addresses, the address of the pubkey P_A + cG, with the same address type as A.
  3. Ensure that he has safely stored or imported the private key of the new output: x+c in the wallet before broadcast of the transaction.
  4. Receiver software must be cognizant of the fact that it is operating on untrusted input. The mere fact of a MAC check passing does not in this case prove anything at all about 'honest' behaviour, since the counterparty is using an entirely ephemeral and untrusted key. In particular it will be vital that the BIP174 parser does not have any vulnerabilities to malicious input.
  5. After storing the passed c-value and on successful parsing of the PSBT into an in-memory transaction proposal, the Receiver software should:
    • Check that the transaction version is 02, locktime is 0 and input sequence numbers are 0xffffffff.
    • Validate the signatures that must exist and be finalized on one input. This is to ensure that the Proposer spends their own coins, and not yours.
    • Check Receiver's ownership of the unsigned input (remembering that Proposers may have only guessed this and could be wrong). Obviously reject if un-owned.
    • Reconstruct the destination - from P+cG - P is already available at this point since we needed it to decrypt the proposal. Apply the same address type to recreate the scriptPubKey, as was mentioned above in "A note on address types".
    • Check the spent amount against the received amount. The Receiver is free to make their own judgement about the minimum amount of satoshis he receives as (satoshis received minus satoshis spent), it could be less than zero, or more; he should consider the network fee in his calculations of course. This decision can be considered as something set by the free market.
    • Assess whether the fee provided to the bitcoin network is suitable. If the transaction is highly desired for some reason, CPFP can be used to bump the fee but a reminder that RBF cannot, because the two sides cannot cooperate to sign a new version.
Note that there isn't really a need to check unspent-ness of inputs, at least strictly: the Receiver is technically in a race with other Receivers to broadcast the Coinjoin, and doesn't have any way to know if any other Receivers are likely to take up the offer. There is no risk of funds loss due to spend conflicts. He may, however, want to avoid this situation, and in which case he should at least check for the unspentness of inputs at the time of signing and broadcasting.

Assuming all checks pass the Receiver software can co-sign to complete the PSBT, then convert it to Bitcoin network serialization, and broadcast it onto the network, either automatically or based on user input. Implementors are reminded of the point made above, that the private key of the newly created utxo must be stored/imported in advance of broadcast.

Storage of Keys

New outputs created by SNICKER coinjoins are not directly controlled by a wallet's existing HD tree. Due to the ECDH mechanism used to create the tweaks for these keys, the Receiver wallet has two options:

  1. Import and persist - The newly created outputs pay to (address of) P + cG, which have corresponding private keys (x+c), where x is the private key of P. Most simply, the wallet MAY store these new keys separately (leaving the wallet free to ignore the original tweak value c), using an import function, which is already present in many wallets. This does of course leave the user unable to access the funds in the case of recovery from only a BIP32 master secret, so may often be considered insufficient.
  2. Re-derive from blockchain history - Because the tweak values c were derived via ECDH between pubkeys of addresses contained within the SNICKER coinjoin, and if the Receiver verified that this derivation was performed correctly at the time of construction of the coinjoin, it will be possible to find all utxos created via this mechanism using (a) the BIP32 master secret and (b) access to historical blockchain data:
    1. Using the master secret and the wallet's HD path, derive addresses as normal
    2. Use the blockchain to find all transactions that spend from any key in this HD wallet (i.e. all historical transactions, in general). For each spent output owned by us, check if the spending transaction fits the pattern of a SNICKER coinjoin (two equal sized outputs is enough of a check, since false positives are not a problem).
    3. For each of those transactions, check, for each of the two equal sized outputs, whether one destination address can be regenerated from by taking c found in the method described above, and reconstructing a pubkey P_A + cG where P_A is the Receiver-owned (and previously reused) key, and then constructing the scriptPubKey from that.
The second option is clearly desirable, but may present meaningful additional complexity depending on the nature of the wallet. If the former is used it MUST be communicated to the user that funds are at risk if they lose their wallet persistence.

SNICKER Protocol Version 01 - Inferred Ownership

The requirements for Proposer and Receiver in Version 01 are the same as those for in Version 00 except where specifically contradicted, or added, in this section.

Here the general concept is: follow the same steps as above, but use the public key from the scriptSig (or witness for segwit) for single key redemptions, thus not requiring address reuse. This introduces a new consideration: the Proposer must guess or infer co-ownership of the input exposing said pubkey, and outputs.

This last point is the reason that, even though Version 01 is much more attractive than Version 00, since it does not require previous address reuse, it is nevertheless a little more complex for both sides to implement, and also the additional inference means the probability of success of any one proposal may be significantly reduced.

Proposer actions

The proposer will need to identify a set of transactions for which he has a degree of plausibility (here unspecified) that at least one input is associated with a certain (currently) unspent output. For the sake of plausibility that the proposal will be taken up, he may need to filter according to various other criteria - does the transaction appear to be from a certain wallet, is there some other form of advertisement of "ready to do SNICKER" either embedded in the transaction itself or on some other bulletin board, is the transaction sufficiently recent etc. etc.

It is worthy of note that in the "canonical" case of a two output transaction, the Proposer can try both outputs with any one input; one of the two will almost always be correct.

Assuming he finds a set of such txs T, each one will have a corresponding input I (note: not a utxo, because this already spent) for which he extracts the pubkey P_I from either the scriptSig or the witness, and there will be a corresponding output which is unspent (see previous paragraphs), whose address we denote as A.

He will then take these steps (similar but not identical to previous - clarity is preferred here, so nothing is omitted, even if repeated):

  • Find one and only one utxo of his own to spend, whose bitcoin value is greater than or equal to: value of utxo owned by A, plus approximately the transaction fee for a 2-in 3-out transaction.
  • Construct a new tweak c (see "Terms" above), using specifically this method (The reason for this specific method was made clear here):
    • First, take the public key of the utxo input chosen in the previous step, call it Q, and its corresponding private key q.
    • Calculate c = ECDH(Q, P_I).
  • Construct a new destination address using pubkey P_I + cG and of the same address type as A.
  • Construct a transaction with inputs: (utxo owned by A, his own utxo owned by Q) and outputs: (P_I + cG, with address type as for A, his own freshly generated output addresses O1 and O2). The amounts will be such that each party (Proposer, Receiver) receives back approximately what they put into the transaction, but the acceptability of the amount is for the Receiver to decide. O1 MUST receive exactly the same amount as P_I+cG and O2 should contain the change required to balance for the Proposer.
  • He signs the transaction for his own input, so it is partially signed.
  • He serializes the partially signed transaction and the tweak value c according to the serialization specification here, calling this serialization M, he outputs and publishes a Proposal: ECIES-E(P_I, M).
  • He publishes this Proposal (as according to definitions, it should be base64 encoded) to the Bulletin board.

Receiver actions

The Receiver actions are as for Version 00, except:

  1. The Receiver will be keeping track of all used keys/addresses, and not only reused ones, as candidates for proposals.
  2. (Trivial) the Version byte check uses 0x01 not 0x00.
  3. As explained above in the Proposer actions section for Version 01, the value of c is calculated with c = ECDH(Q, P_I). However the same comments as for Version 00 apply here in the Receiver's choice of whether to use recoverable keys.

Implementation of the Bulletin Board

This is not a matter of any protocol-level consensus and so no specification is strictly required outside the format of encrypted proposal, which is already done.

Before continuing it is worthy of note that such a Bulletin Board is not strictly necessary and SNICKER as defined in this BIP can still be carried out without any server, just through ad-hoc connections; as long as the transaction proposal format is standardised, wallets could still create such coinjoins.

Here we will only note some possible, natural implementation approaches, and issues with them:

General point: anonymity

We earlier mentioned the possibility of using a Tor Hidden Service for this purpose, which seems practical, but in any case network level anonymity for the Proposers who upload and the Receivers who download is more or less essential, as otherwise monitoring (especially by the Bulletin Board) may link the participants in CoinJoins to other metadata, other Bitcoin transactions etc.

Now we'll discuss the possible mechanics of the Bulletin Board's storage of proposals:

"Flat" storage

The simplest possible approach is for the Bulletin board to accept any and all encrypted blobs and store them in a flat list. This would require Receivers to download ALL proposals and check each of them against each candidate key P. This has a large advantage, namely that the Receiver reveals nothing through their network traffic. But this approach obviously could suffer from both scalability issues (Receiver computation time, bandwidth) and (related) spam attacks since there is no way to restrict fake proposals.

Indexed to keys

A step up from this (and likely, necessary) is to publish the intended P value in plaintext to the bulletin board, along with the encrypted transaction proposal. This could be considered a privacy leak, however, when we consider that SNICKER of Version 00 or 01 types will be identifiable as such on the blockchain, the existence of a public record of a Proposer choosing such a key is probably not an issue. Also multiple proposals to keys will not be distinguishable due to the encryption, and moreover if the proposal is not taken up, nothing is leaked other than the intent of an unknown party to do a coinjoin with a key that they do not own. With indexing of this type, the Receiver's action is hugely easier, since they will only need to download proposals directly relevant reducing their bandwidth and computation requirements. However, they still need to keep track of all P candidates in advance, of course. Also notably, they could obfuscate their actions somewhat by downloading proposals for a selection of keys, and not just their own.

Anti-spam prevention

Even with indexing, the problem of near-infinite fake proposals to clog the bulletin board "channel" still exists. This can be prevented with either (a) hashcash[16] (grind the ephemeral key for ECIES for example), (b)fidelity bonds similar to the idea proposed by Chris Belcher for Joinmarket[17], (c) direct payments to a server for the right to post proposals or (d) proposals only allowed to be made by the Bulletin Board owner or some fixed group. All of these ideas may be possible; but not using any of them would almost certainly lead to a death-by-spam in any reasonably popular public system.

Future improvements

The Versions 00 and 01 as explained above were intended to be (a) as simple as possible and (b) adhering to existing standards wherever possible. Much more variability and customization is possible and could be implemented in higher version numbers and using flags for additional features. Some ideas:

  • More efficient variants - if bandwidth is a concern we could reduce the size of proposals, principally by not using the PSBT full format but rather a custom tx and signature transfer format, trading off flexibility for small size. Both SNICKER magic bytes and even tweaks could be removed (tweaks could be inferred from ECDH shared secrets).
  • SNICKER as payments - if a payer was willing to wait a little longer than normal, a new variant of SNICKER may have a particularly good incentive alignment - the payer-Proposer could incentivise the Receiver to enable the payment of a fixed amount of the Proposer's choosing to a destination by adding a little to the Receiver's outputs. This would not fit in Versions 00 and 01 as current since it would require two outputs for the Receiver.
  • Use other features of Bitcoin like OP_RETURN or sign-to-contract or possibly "stealth addresses" to allow flagging of individual transactions or utxos as SNICKER candidates (improving discovery) (it is worth noting that pretty much any 'watermark' in existing transactions, like CoinJoins of various types, as well as address reuse, could be used today as such a discovery feature).
  • Allow SNICKER on more complex/custom scriptPubKey types than those listed above.
  • Allow more complex transaction structures.
  • More than 2 party joins based on multiple proposal transfers - a significantly more complex protocol.

Backwards Compatibility

SNICKER has no backwards compatibility concerns with respect to Bitcoin and is a purely optional client-side wallet feature.

Test Vectors

ECDH TVs

TODO

ECIES TVs

TODO

Transaction proposal TVs

TODO

Credits

Thanks in particular to @fivepiece (github) aka arubi (IRC freenode) who came up with many ideas here including specifically Version 01, and many others who offered thoughts on this concept.

References

  1. ^ https://joinmarket.me/blog/blog/snicker/
  2. ^ https://bitcointalk.org/index.php?topic=279249.0
  3. ^ https://en.bitcoin.it/wiki/Shared_coin - warning, link outdated, this system is defunct
  4. ^ https://github.com/darkwallet/darkwallet - as for previous, this is now defunct
  5. ^ https://github.com/Joinmarket-Org/joinmarket-clientserver
  6. ^ https://github.com/zkSNACKs/WalletWasabi
  7. ^ https://github.com/Samourai-Wallet
  8. ^ https://bitcointalk.org/index.php?topic=1497271 for announcement and https://www.ndss-symposium.org/ndss2017/ndss-2017-programme/p2p-mixing-and-unlinkable-bitcoin-transactions/ for latest version
  9. ^ https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki#Constructing_and_spending_Taproot_outputs
  10. ^ ECDH implementation in libsecp256k1: https://github.com/bitcoin/bitcoin/blob/master/src/secp256k1/src/modules/ecdh/main_impl.h
  11. ^ https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme
  12. ^ https://github.com/spesmilo/electrum/blob/fd5b1acdc896fbe86d585b2e721edde7a357afc3/electrum/ecc.py#L277-L292
  13. ^ https://github.com/bitcoin/bips/blob/master/bip-0174.mediawiki
  14. ^ https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki
  15. ^ https://github.com/bitcoin/bips/blob/master/bip-0069.mediawiki
  16. ^ http://hashcash.org/
  17. ^ https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-July/017169.html

@fivepiece

This comment has been minimized.

Copy link

commented Aug 23, 2019

Re. reconstruction of k by the receiver (snicker version 1) I think whether they use deterministic processes or not is not so important, and the k value doesn't need to be stored even if it's random. A receiver wallet just needs to know its own private keys and be able to regenerate the sighash that was used in funding his utxo, and it can just recover k = 1/s * (z + r*d) where z is that sighash and d is the funding transaction's private key.

I see in "Future improvements" that tweaks can also just be ECDH secrets to avoid the need of transmission, this is nice because it also avoids the need to store the c values in the wallet at all (suppose the ecdh is between proposer's and receiver's pubkeys from their utxos, or some other public info), which helps a lot with wallet recovery from seed.

@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Aug 23, 2019

Re. reconstruction of k by the receiver (snicker version 1) I think whether they use deterministic processes or not is not so important, and the k value doesn't need to be stored even if it's random. A receiver wallet just needs to know its own private keys and be able to regenerate the sighash that was used in funding his utxo, and it can just recover k = 1/s * (z + r*d) where z is that sighash and d is the funding transaction's private key.

i think this is a very good point, I didn't think about the exact mechanism for "recovery" of k enough.

The wallet should probably just store history of txs or txids then either (a) use a lookup on the blockchain to reconstruct via full transaction, using the signature and reconstructing the sighash, and using the privkey or maybe (b) actually just always store the historical transactions(?) and reconstruct locally.
Both of those are more involved than just storing the k value but obviously that's not really safe and/or annoying to keep safe.
Another thought i had though was that it might be easier to go from transaction+privkey -> k than via the mechanism you propose, simply because most wallets will already have that in their code, whereas reconstructing k via (R,s,d,H(m)) will require new crypto code.
Your main point is very valid though: that even if k is generated non-deterministically it's still entirely possible to reconstruct it from tx data + private key which will always be accessible.

@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Aug 23, 2019

I see in "Future improvements" that tweaks can also just be ECDH secrets to avoid the need of transmission, this is nice because it also avoids the need to store the c values in the wallet at all (suppose the ecdh is between proposer's and receiver's pubkeys from their utxos, or some other public info), which helps a lot with wallet recovery from seed.

I'm much less clear about this second point.

Clearly the proposed future upgrade of using something like H(shared ECDH secret) as the c value can save space in the transaction proposal. Btw see here and further discussion in-thread, idea is from @lontivero but as I mention there, others thought of it before.

But: I don't see how you can avoid transferring an ephemeral pubkey for the ECDH the proposer is completely unknown to the receiver and we want to keep it that way, so i don't think there's a way for the receiver to infer a pubkey. they need it right at the start, to decrypt, after all (if it were the other way round, we could somehow use a pubkey that the Proposer included in the transaction, but that's no good since you need this key before you decrypt the transaction proposal).

Edit: I'm sorry, now I write that out, it is perhaps clearer what you mean. I think it's this: after the transaction proposal has been taken up, and a coinjoin signed and broadcast, then the user could in future reconstruct the destination (R+cG) based on the value of c coming from a pubkey in the transaction, which is also the pubkey used for ECDH. This is a very interesting/promising direction, to have all private keys entirely reconstructable from scratch by a wallet (by using HD keys plus blockhain scan), but I see a problem: if the Proposer uses one of his input utxo pubkeys as his ECDH ephemeral key, the problem is that that key is provided in plaintext in the proposal (ECIES magic || ECDH pubkey || ciphertext), so it would leak info to passive observers.

@fivepiece

This comment has been minimized.

Copy link

commented Aug 23, 2019

then the user could in future reconstruct the destination (R+cG) based on the value of c coming from a pubkey in the transaction

Right, that's what I meant. Sorry for being unclear :)
But

which is also the pubkey used for ECDH

This doesn't have to be true. I was thinking that a second ECDH (unrelated to the ECIES) for constructing c can be done with one of Proposer's funding pubkeys and Receiver's pubkey, that are both only in ciphertext.
Basically the Receiver could:
For each of the Proposer's pubkeys used in the partially signed CJ, do ECDH to obtain a c' value, then check if that c'*G added to his own pubkey is equal to a pubkey in the CJ's output.
If it is, then c' is the c, and it should also be recoverable in the future when the CJ is on chain.
Apologies if I'm missing some fundamental issue with this or if it's still unclear.

@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Aug 23, 2019

Yes, I see. And this works for the same reason the previous proposal works: that an ECDH shared secret is not derivable by third parties.

So, I've been thinking about this for a bit, and I'm inclined to go in this direction:

  • Derive the tweak c in the way you propose: with the other pubkey coming from one of the inputs of the tx (using ECDH and hashing the shared secret) and not being either (a) a completely random tweak or (b) taken as a hash of the ECIES ephemeral key
  • However, do include that tweak c explicitly as the first field of the encrypted proposal.

My reasoning: the only disadvantage of including c explicitly is 32 bytes of space, which is not nothing (it may be 10% of the proposal, likely a bit smaller), but is also not a huge deal. For one, it serves as a sanity check that both sides are following the same rules. Also, there is a significant advantage for the wallet developer: they can treat the new output R+cG as just an imported key k+c, which most already have infrastructure to deal with (and as mentioned above, they have infrastructure to recalculate k, given the transaction), without doing another ECDH (I admit: this is not in theory a problem, since they already did ECDH for ECIES; but more complex code all the same) and they can do so whether or not they go to the trouble of implementing a recovery mechanism; but they now know that it at least is possible.

The recovery mechanism's a bit fiddly, mostly because it needs blockchain access: consider that if you start from zero information except your HD master secret, you can only scan forward through keys ... on its own that obviously doesn't pick up these k+c keys, so you would have to look at every spent output from a key within the HD tree, and check if that spending transaction is a coinjoin, then check the pubkeys in the inputs to see if any of them match any outputs. It's quite involved and more to the point, it's quite far outside what wallets usually do.

Hence I think the best is to use your suggested mechanism but still make c explicit.

@fivepiece

This comment has been minimized.

Copy link

commented Aug 23, 2019

Yea I see why it's lucrative to encode c explicitly, but I'm wondering :

it serves as a sanity check that both sides are following the same rules

&&

they can treat the new output R+cG as just an imported key

I'm not sure if these two are compatible. Suppose our Proposer includes a c value that truly works for R+cG, but is otherwise not really a product of the ECDH - the Receiver has no way of knowing that the protocol was deviated from without actually trying ECDH himself... I think.
If c is not a product of ECDH then Receiver risks loss of funds if he doesn't back it up.


you can only scan forward through keys ... on its own that obviously doesn't pick up these k+c keys

Why wouldn't it though? Say we do start from 0, then all (really just gap size) keys known by the wallet come from the seed.

  1. As a payment to a key is discovered on chain, the wallet saves the utxo. - this is the standard mechanism for all wallets.

  2. At some point, the utxo is spent. The wallet knows which of its pubkeys was used in the spend, and can ECDH with any unknown pubkeys in the spend to try funding a c that is valid for a pubkey in the output. (if there are no unknown pubkeys, then it's probably not a snicker CJ)

  3. If it finds one, add the k+c as a privkey and the CJ spend as a new utxo and GOTO (1)

Maybe it's possible to also safely standardize which of the Proposer pubkeys in the PSBT is used for the ECDH without losing security so Receiver doesn't need to try all of them.

@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Aug 23, 2019

Yea I see why it's lucrative to encode c explicitly, but I'm wondering :

it serves as a sanity check that both sides are following the same rules

&&

they can treat the new output R+cG as just an imported key

I'm not sure if these two are compatible. Suppose our Proposer includes a c value that truly works for R+cG, but is otherwise not really a product of the ECDH - the Receiver has no way of knowing that the protocol was deviated from without actually trying ECDH himself... I think.
If c is not a product of ECDH then Receiver risks loss of funds if he doesn't back it up.

Yes you clarify an important point there: there's a huge footgun if a wallet developer somehow assumed, without calculating, that c values were derived in a recoverable fashion. I had more in mind that at some point they might decide to switch to the recoverable form in future. But also that there's somehow a spectrum that a wallet developer could fall in and shift over time. They might decide it's best to do both, or just decide they never want to bother with recovery and stick only with imported keys. Either way my first point about "sanity check" is either weak or as you suggest, misleading.

you can only scan forward through keys ... on its own that obviously doesn't pick up these k+c keys

Why wouldn't it though? Say we do start from 0, then all (really just gap size) keys known by the wallet come from the seed.

1. As a payment to a key is discovered on chain, the wallet saves the utxo.  - this is the standard mechanism for all wallets.

2. At some point, the utxo is spent.  The wallet knows which of its pubkeys was used in the spend, and can ECDH with any unknown pubkeys in the spend to try funding a `c` that is valid for a pubkey in the output.  (if there are no unknown pubkeys, then it's probably not a snicker CJ)

3. If it finds one, add the `k+c` as a privkey and the CJ spend as a new utxo and GOTO (1)

Maybe it's possible to also safely standardize which of the Proposer pubkeys in the PSBT is used for the ECDH without losing security so Receiver doesn't need to try all of them.

Well we're not differing hugely here but: it's not a valid assumption that wallet recovery via scanning always involves looking at every historical transaction. It's possible to just query Core and find out which addresses have been used, apply a scanning algorithm respecting gaps to reach the "end", then match up those addresses with current utxos. This way you just know what exists and what's been used but not the historical transactions. There are doubtless many ways to sync.
But overall, you're describing what I had in mind, but you're seeing it as 'simple', I think whether it'd be seen as simple/straightforward may just depend on the wallet.

@fivepiece

This comment has been minimized.

Copy link

commented Aug 24, 2019

Ah yes you're absolutely right. I was only thinking about the most trivial way to scan\recover.
I see your point.

@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Aug 25, 2019

@fivepiece i've overhauled the structure quite a bit today, it's certainly not finished (some formatting snafus to clear up, at least); see if what i'm saying about the construction of c makes sense to you, cheers.

@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Aug 26, 2019

Noting down a technical annoyance here so it's not forgotten:

Electrum originally implemented ECIES with magic bytes BIE1 and using sha512(shared secret) to create 64 bytes of key material, splitting it 16 IV, 16 AES, 32 MAC and then used hmac-sha256as the mac with that MAC key.
Here I was trying to stick to the ECDH implementation used in libsecp256k1 (which although it has custom hash function support, that would be an annoyance for implementers not wanting to create new binding code), and stick to SHA256 where possible, so I switched to a key generation in two sha256 steps with a counter, and then still used hmac-sha256 as the mac function. But I haven't changed the magic bytes from 'BIE1'. At this point I'm not at all sure what to do, other than of course any of these variants should be fine.

@fivepiece

This comment has been minimized.

Copy link

commented Aug 26, 2019

I read through version 27 first, then refreshed and saw that a few updates with additions were made so I read through those too. LGTM :)

@fivepiece

This comment has been minimized.

Copy link

commented Aug 27, 2019

I was going over some past notes related to snicker v1 - the reasoning I had back then for using the R from the signature was that some scriptPubKeys (really P2PK and bare multisig) don't carry the public key in the redeemscript.
Re-thinking about it in the context of this BIP, P2PK is not supported in snicker and I believe that bare multisig outputs are non-standard for a while now - it seems that using the public key itself instead of R would be easier to implement.

Pros :

  • No need to parse DER for extracting the x-coordinate - the public key is "static" within the standard scripts that the BIP supports
  • No need to save k, or add functionality for recovering it later - the wallet just needs to be able to recover normal HD private keys

Cons : ??

@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Aug 29, 2019

As discussed - I agree. I see no cons at all. I've updated the doc to reflect this (and it's nice of course that it actually removed more than it added).

I also modified the ECIES to be in line with what Electrum (since it only requires sha512 that everyone will have, and it doesn't conflict with libsecp since that doesn't have ECIES, but does of course have multiplication which is all you need other than the hash function).

Other than that just some minor edits. At some point I should probably "publish" this to .. the mailing list?

@fivepiece

This comment has been minimized.

Copy link

commented Aug 29, 2019

Future improvements :: Flagging SNICKER candidates - it might be possible to flag TXs using the nlocktime field if otherwise unused by some value like SNK# where # is a bit field used for and\or snicker version and application flags for potential Proposers,

The same applies for the nsequence field.

@elichai

This comment has been minimized.

Copy link

commented Sep 2, 2019

Without diving into the actual details of this BIP, a couple of questions:
Why this weird ECIES scheme?

  1. Why CBC? why??.There's so much research on this. please don't use CBC for anything new.
    use AES-GCM preferably 256bit.
    Using AES-GCM is also a replacement for the HMAC, means you don't need the weird padding, has good hardware support and is highly recommended right now.
@AdamISZ

This comment has been minimized.

Copy link
Owner Author

commented Sep 3, 2019

@elichai

I anticipated this question (and not only because you already asked it on IRC :) )

Why this weird ECIES scheme?

Well, it's linked to in the draft, but, it's because it's the only currently extant encryption protocol with bitcoin keys in the Bitcoin ecosystem - Electrum uses exactly this protocol. Now, on the one hand, that's not the same as it being used in Core, on the other, Electrum is a pretty big and established part of the ecosystem.
A lot of my reasoning here and in the rest of the document are based on me trying to avoid inventing anything new.

That argument isn't very strong though, I agree there.

Why CBC? why??.There's so much research on this. please don't use CBC for anything new.
use AES-GCM preferably 256bit.

I'm quite familiar with this. I'd point out that the severe failings of CBC combined with something like PKCS7, in the context of TLS aren't applicable here because we're not in a client server context. The classic decryption oracle (and in particular padding oracle) attacks like that of Vaudenay and the later variants don't apply because there is no server oracle here to query.
Does that mean I think it's a good idea to use it when we have a modern authenticated encryption scheme which bypasses any such concerns anyway? Not really. I basically agree with you.
But: AES-CBC is being used almost everywhere for wallet encryption. I see it in Bitcoin Core, in Electrum, and I'm pretty sure I've seen it in several other codebases.
While this is not encryption of data at rest, it's also not encryption of data in a client-server context.

All of these reasons aside, I still agree with you though; there's not enough of a good reason to avoid using a modern standard rather than an old one which is a bit broken, even if not obviously broken in this context.

If you want to add more thoughts on it, like concretely an ECIES construction with AES-GCM (or where to go to find one), it'd be appreciated.

@elichai

This comment has been minimized.

Copy link

commented Sep 3, 2019

As you said I'm not convinced by that argument.

As for ECIES with AES-GCM? take the shared secret from ECDH, use that as a key, and get a random IV. that's it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.