/coinjoin-sudoku

Primary LanguagePHPMIT LicenseMIT

coinjoin-sudoku

Description

A set of tools used for identifying CoinJoin transactions in the Bitcoin blockchain and attacking the privacy afforded by those transactions.

Currently, the only form of heuristic used by this tool is intra-transaction analysis of CoinJoin trasactions that leak information through poor matching of input to output values, leading to a deceptively small anonymity set. This is accomplished through brute forcing of the possible summations between inputs and outputs, less a few small improvements in efficiency. The time to required to perform this analysis is an expoential function of the number of inputs and outputs; it is related to the Subset-Sum problem from complexity theory.

This tool was used to perform the research published at this advisory: http://coinjoinsudoku.com/

Author

Kristov Atlas Twitter: @kristovatlas Email: firstname lastname @gmail.com www: http://kristovatlas.com

HOW-TO

Finding SharedCoin transactions in the Blockchain

SharedCoin is a service offered by Blockchain.info that implements a protocol based on CoinJoin. At some points during its history, it has been vulnerable to sudoku analysis. This script will search for transactions that look like they could be SharedCoin transactions. It currently utilizes the Blockchain.info API rather than a local copy of the blocckahin, which makes the code simpler and saves on storage but is many times slower as API query rate is the bottleneck at a typical rate of 87 transactions processed per minute when using an API key.

  1. Open findSharedCoinTxs.php and change the $startingBlockHash variable to the hash of a block that you would like to start searching from. Currently, this code can only scan backwards in the blockchain. You can also set $numTransactionsToExamine to set a maximum number of candidate transaction that should be considered as possible SharedCoin transactions.

  2. Set the number of seconds to sleep between queries by setting NUM_SEC_DELAY_BEFORE_REQUEST in ThrottledDomReader.php and NUM_SEC_DELAY_BEFORE_REQUEST in ThrottledJSONReader.php. Also, if you wish to use an API key, you can specify that in BlockchainInfoBlockReader.php with the BLOCKCHAIN_INFO_BLOCK_URL_API_KEY variable and in BlockchainInfoTxReader.php with the BLOCKCHAIN_INFO_TX_JSON_API_KEY variable. If you are not going to specify an API key, a reasonable throttle to set between queries to avoid IP bans is 6 seconds.

  3. Run php findSharedCoinTxs.php

Results will be printed to stdout upon completion, as well as saved in a log file of the form 'scdump_yyyy-mm-dd hh-mm-ss.log'.

Analyzing CoinJoin transactions

TODO

Pre-computing permutations

There are two scripts for pre-computing permutations that are required for this tool's sudoku anaylsis. runSetSearch.php will begin pre-computation from scratch. The larger the number of elements you are trying to permute, the longer this computation will take, and so this project also provides runSetSearchAfterFileLoad.php, which can open up a log file previously generated by runSetSearch.php and resume progress, rather than starting over again entirely.

TODO

Unit Tests

TODO

Description of Heuristic

This heuristic relies first on precomputation of permutations. Some of the permutations that I have already precomputed are contained in the /data/permutations/ directory.

TODO

Futue Improvements

TODO