Amazingly thorough, Peter. Thanks so much!

-wendell

hivewallet.com | twitter.com/hivewallet | pgp: B7179FA88C498718

On Dec 19, 2013, at 8:17 AM, Peter Todd wrote:

> Here's my draft. I don't claim this to be "official", but I think this
> should represent the consensus we've come to at the DarkWallet
> Hackathon; I'm writing it up as an email in part to preserve a record of
> that consensus.
> 
> 
> * General Principles
> 
> We believe in decentralization, user-defined privacy, education as
> opposed to "magic", and security based on openness rather than just
> trust. We consider users who are individuals as well as the needs of
> businesses such as merchants and exchanges. We recognize that often the
> more people who use privacy protection technologies such as CoinJoin,
> the better protected we all are.
> 
> 
> * Privacy
> 
> Bitcoin inherently makes the flow of money visible, however it does not
> require that flow to have real-world identities attached, or even for
> that matter, pseudonyms. We see this as an unfortunate flaw in the
> Bitcoin protocol that is to be corrected; the Satoshi whitepaper itself
> included one such correction by outlining how avoiding address re-use
> helped preserve privacy.
> 
> 
> ** Threat model
> 
> We assume a worst-case sophisticated state-level attacker with the goal
> of deanonymizing and otherwise subverting Bitcoin users. Such an
> attacker can be assumed to control up to 100% of the Bitcoin relay
> network as well as have the ability to wiretap up to 100% of the
> node-to-node traffic. (for nodes that they do not control) Such
> attackers are however constrained by politics and budget. We assume they
> use their ability to conduct MITM attacks sparingly - for instance by
> subverting certificate authorities - due to the risk of detection. (note
> how such attackers may be more willing to use detectable attacks in the
> future now that their activities are public knowledge) We also assume
> that while their budgets for individual targets may be very large, the
> equally large number of targets required for en-mass survailance leads
> to relatively low budgets per target. In particular note how the 51%
> assumption assumes that the overall "economic value" of Bitcoin to its
> participants is greater than the attacker's budget by some margin.
> 
> 
> ** Address re-use
> 
> Wallet software SHALL avoid address re-use. New addresses will be used
> for all change and users will be encouraged through the user-interface
> and other measures to use new addresses for every payment to the wallet.
> 
> 
> ** CoinJoin
> 
> With CoinJoin the more users that make use of it, the larger the
> anonymity set and the better protected user privacy is. Thus we
> encourage wallet software to agressively make trade-offs between
> absolute privacy and usability; compromise is not a dirty word.
> 
> Wallet software SHALL implement basic two-party mix functionality and
> MAY implement more sophisticated CoinJoin functionality such as n-party
> mixes. CoinJoin SHALL be the default way that all transactions are sent.
> Wallet authors are cautioned that more sophisticated functionality may
> be more secure in theory, but if users do not use it the functionality
> is wasted; focus on the general case first and only then try to improve.
> 
> 
> *** Two-Party Mixes
> 
> The most basic form of CoinJoin is for two parties to author a
> transaction. A key distinction between a 2 party mix and an n-party mix
> is that in the two party case both parties automatically learn the
> other's inputs and outputs by simple elimination; sophisticated
> cryptographic blinding protocols are useless. To an external attacker
> each transaction doubles the size of the anonymity set: the coins may
> have come from one party or the other and the attacker has no way of
> knowing which. (modulo value analysis, which will be discussed later)
> 
> 
> *** n-party Mixes and Blinding
> 
> If two parties can jointly author a transaction, n parties can too.
> Without special effort this has the disadvantage of revealing the input
> to output mapping to all parties. Various cryptographic blinding schemes
> have been proposed to fix this problem, either with multi-party
> computational techniques, or by making use of multiple communication
> channels along with a robust anti-DoS scheme. In either case, for now we
> reject such schemes as complex and inconvenient and prioritize robust
> two-party mixing. However we do take the existance of such schemes into
> account; note how a n-party mix can act as a single party in a two-party
> mix scheme.
> 
> 
> *** Four-stage two-party mix protocol
> 
> <on the wiki>
> 
> 
> *** Defeating value analysis
> 
> Attackers can make good guesses at the mapping of inputs to outputs
> based on value. For instance with two inputs of 3 and 5, and fours
> outputs of 1.4, 1.6, 2.4 and 2.6 the attacker can easily map inputs to
> outputs based on what values match up, in this case 3 split into 1.6 and
> 1.4, and 5 split into 2.4 and 2.6
> 
> 
> **** Value Matching
> 
> Not all CoinJoin users need their transactions to have specific output
> amounts; some users simply need to move money from one place to another
> but do not need a specific amount moved or at a specific time. These
> users can assist users with more stringent requirements by matching the
> input or output values they request. As a general principle wallets
> SHOULD make these anonymity optimizations possible by allowing users to
> schedule transactions to complete by a specific time and/or allow users
> to specify that they do not wish the transaction to happen unless
> CoinJoin is used.
> 
> With four-stage two-party mixes the Alice, who advertised a desire to do
> a transaction first, can easily do ths by picking the transaction output
> amounts only after Bob replies with his desired inputs and outputs, and
> picking those amounts so they match Bob's. (or some combination of Bob's
> outputs)
> 
> 
> **** Merge Avoidance
> 
> Merge avoidance is the practice of avoiding the merging of multiple
> transaction inputs into a single new transaction output, thus implying a
> common relationship between those inputs. The most primitive form of
> merge avoidance is to create multiple individual transactions, each
> moving single transaction input to an output. (or perhaps some small
> number) This is of course inefficient, and appears to have only been
> proposed as a means to still allow for coin blacklists to function while
> preserving some financial privacy.
> 
> Combined with CoinJoin however merge avoidance becomes much more
> powerful. For instance even in its most simple form multiple parties can
> combine their merge-avoiding transaction sets, giving even transactions
> without actual counterparties a useful measure of plausible deniability.
> 
> In addition the underlyng features that make merge-avoidance possible -
> the ability of a recipient to designate they are willing to receive
> payments made to multiple addresses - synergisticly make very
> sophisticated value matching strategies possible.
> 
> 
> ***** Cut-thru payments
> 
> Related to merge avoidance the idea of a cut-thru payment is that if an
> intermediary is both a debitor and a creditor, with sophisticated
> payment protocols they can request incoming payments to directly pay
> outgoing liabilities, skipping them as an intermediary. While premature
> to implement this feature now, it is worth thinking about for the future.
> 
> 
> ** Tor
> 
> While Tor isn't perfect there is real-world evidence - specifically the
> Snowden leaks - that it works well enough to be considered a worthy
> adversary by state-level attackers. Wallets MUST suppoort the basic
> proxy options that allow the Tor proxy - or some other similar
> technology - to be used for privacy enhancement and SHOULD make use of
> Tor-specific features such as hidden services.
> 
> 
> * Decentralization
> 
> ** Fees
> 
> In a decentralized system distinguishing DoS attackers from legitimate
> users is at best difficult, at worst impossible. Wallets that do not
> provide users with the ability to set fees, both when a transaction is
> created initially and after initial broadcast, do their users a
> disservice by taking away a vital method of responding to an attack:
> outspending the attacker.
> 
> Wallets MUST give users the ability to set the fee per KB they are
> willing to pay for their transactions. Wallets SHOULD allow users to
> change that fee after the fact via transction replacement. Wallets MAY
> additionally implement fee estimation techniques, such as watching what
> transactions in the mempool are finally mined, or using estimates
> provided by miners. However it must be recognized that such data is
> inherently unreliable, and this may become a problem in practice in the
> future; giving users robust ways to alter fees after the fact will make
> lying about fee data - perhaps to push fees upwards - less advantageous.
> 
> Note that the current direction of the Bitcoin Foundation maintained
> reference implementation is weakly towards a pure estimation scheme;
> deployment of full nodes supporting replacement and support from miners
> is a precondition to doing things correctly.
> 
> 
> *** Fees and privacy
> 
> Where there is a trade-off between fees and privacy - such as with merge
> avoidance strategies - users should be given options to specify how much
> extra they are willing to pay for extra privacy. Wallets SHOULD default
> to being willing to pay some extra, perhaps 25% more over the basic fee.
> 
> 
> ** SPV, full nodes and partial nodes
> 
> Wallet software SHOULD whenever possible blur the distinctions between
> full UTXO set nodes, SPV nodes, and partial UTXO set nodes. In addition
> to those three basic categories there is also the question of whether or
> not a node stores archival blockchain data, something that all three
> categories of nodes can participate in.
> 
> Instead how a node contributes back to the health of the network should
> be a function of what resources it has available to it. Of course in
> some cases, like a phone wallet, that won't be very much, but for
> desktop or business usage the resources available can be significant in
> both bandwidth and storage capacity.
> 
> 
> *** Relaying data
> 
> **** Blocks and blockheaders
> 
> Any node can safely relay blocks and block headers, where "safely" is
> defined as SPV-level security. Our threat model implies that we don't
> trust random peers on the network, thus we are not relying on them for
> block validity; as a SPV node we are relying on miners to do validity
> checking for us. In short feel free to relay data that you yourself
> would trust.
> 
> 
> **** Transactions
> 
> Remember that relaying transactions has a DoS-attack risk; the Bitcoin
> model relies entirely on mining fees and/or priority as the limited
> resource to prevent DoS attacks. Thus at present nodes SHOULD NOT relay
> transactions if they do not have an up-to-date copy of the relevant
> parts of the UTXO set spent by the transaction. (relaying transactions
> spending only inputs in a partial UTXO set is acceptable):
> 
> 
> **** Block-header diversity
> 
> Wallet software MUST make it possible to get block-header information
> from a diverse set of sources. These sources SHOULD comprise more than
> just peers on a single P2P network. Remember that it is acceptable to
> use even centralized sources in addition to decentralized ones for
> blockheader data - knowing that a miner did the work required to create
> a block header is always valuable information. (for reasonable amounts
> of work) For instance the author's block headers over twitter project -
> while an April Fools joke - is equally a perfectly reasonable backup
> source of blockheader data.
> 
> 
> ** Updating wallets from blockchain data
> 
> In an ideal world wallets wouldn't need to sync their state with
> blockchain data at all: pervasive use of payment protocols would have
> senders send txout proofs directly to recipients. But that's not the
> case. Instead wallet implementations sync themselves from the
> blockchain, and when bandwidth limited this becomes a tradeoff between
> bandwidth and privacy: your transactions hide in the anonymity set of
> the false positives matched by the filter.
> 
> 
> *** Bloom filters
> 
> The current implementation for SPV nodes is to simply give peers a bloom
> filter; the false-positives make the anonymity set. For n peers this has
> O(n) cost when a new block comes in; Bloom filters are cheap to test
> against and this system works reasonably well.
> 
> However, for archival blockchain data bloom filters are seriously
> flawed: every block has to be read from disk in full, the bloom filter
> matched, and some (potentially very small!) subset sent to the peer. n
> peers. The result is high IO load on the node relative to the client,
> enabling easy DoS attacks.
> 
> Wallet software SHOULD NOT implement only Bloom filters, however using
> them when availalbe is acceptable. Note how the Bloom filter design has
> at best O(n^2) scaling ruling it out for large-blocksize future
> scenarios.
> 
> 
> *** Prefix filters
> 
> TXO or UTXO data can be easily indexed by in radix trees with log2(k)
> lookup cost per query. We can take advantage of the fact that the query
> keys need not be provided in full by only providing partial keys.
> Because scriptPubKeys are randomly distributed a prefix n bits long has
> an anonymity set of roughly 1/2^n * # of transactions in total.
> 
> Wallet software SHOULD implement prefix filters and SHOULD use them in
> preference to bloom filters whenever available. Wallet software that
> currently uses full-key filtering - e.g. Electrum - MUST be upgraded to
> support prefix filters in the future.
> 
> Wallet software MUST NOT assume that matching anyting other than
> H(scriptPubkey) is possible. This applies to bloom filter matches as
> well.
> 
> In the future miners may commit to either the TXO set in conjunction
> with per-block lookup trees, or possibly the full UTXO set. In either
> case many of the leading designs may be implemented with only
> H(scriptPubKey) lookup capability for reasons of scalability.
> 
> 
> * Security
> 
> Bitcoin wallet software is unprecedented in how they provide attackers
> targets that are highly profitable to attack and highly liquid. (note
> the irony here!) A succesfull attack that injects malicious theft
> routines into either sourcecode or binaries can steal thousands of
> Bitcoins in one go, and the attacks target is you and your team.
> Following basic good practices for robust code is a start, but it's far
> from enough.
> 
> 
> ** Source-code integrity
> 
> Sourcecode MUST be maintained using a revision control system that
> provides strong integrity guarantees; git is recommended.
> 
> Sourcecode MUST be PGP signed on a regular basis. Releases MUST be
> signed - in git this is accomplished by signing the release tag.
> Individual commits SHOULD be signed, particularly if source-code used in
> day-to-day development is kept on an untrusted server, e.g. github.
> Recovering from a server compromise is made significantly easier if
> every commit is securely signed.
> 
> 
> ** Binary integrity
> 
> All things being equal it is better to use an interpreted language
> rather than a compiled one; auditing the former is significantly easier
> than the latter. Similarly, all things being equal, do not distribute
> binaries of your software - have end-users compile binaries themselves.
> 
> Of course all things are not equal, and frequently compiled languages
> and distributing binaries is the correct choice. If that is the case
> deterministic build systems MUST be used when possible; if using them is
> not possible take great care with the process by which binaries are
> created and try to create long-term plans to move to a deterministic
> build system in the future.
> 
> 
> ** PGP
> 
> Developers of wallet software MUST make use of PGP and participate in
> the web-of-trust. Developers MUST advertise their PGP fingerprint
> widely, for instance on personal websites, forum profiles, business
> cards etc. simultaneously. Multiple paths by which someone can find a
> fingerprint claimed to be of some developer make subterfuge easier to
> detect and more costly to carry out. When possible it is highly
> recommended to attach these advertisements to real-world, physical,
> actions. For instance the author has included his PGP fingerprint in
> highly public, videotaped, talks he has given at conferences. He has
> also created a videotaped statement of his PGP key that was timestamped
> in the Bitcoin blockchain. While it certainly is possible for such
> artifacts to be faked, doing so convincingly is expensive, labour
> intensive, and error prone.
> 
> Developers SHOULD sign as much communication as practical. Sourcecode is
> one form; your emails to development lists and between each other are
> another. Signing both leaves a large body of widely distributed work,
> all tied to your identity. (it's highly unfortunate that nearly all
> publicly available mail archives do not make mail accessible to the
> public in such a way as to allow verification of PGP signatures; often
> even inline signatures are broken for various reasons)
> 
> 
> *** Increasing adoption of PGP
> 
> Keep in mind that end-users very rarely verify PGP fingerprints at all,
> let alone correctly - the above advice with regard to PGP is currently
> mostly useful in allowing *other developers* the tools they need to
> verify the integrity of your code. For instance, in the event of a
> suspected compromise consistantly signed code allows anyone competent in
> the use of PGP to quickly evaluate the situation, and if warrented,
> inform less sophisticated users through traditional measures such as the
> media.
> 
> While this is somewhat out of scope for this document the "DarkWallet
> effort" should include work to make PGP more user-friendly and a better
> experience. But that does *not* have to mean "making PGP easier for
> grama", right now "making PGP easier for Joe Wallet Developer" is a
> laudable goal. For instance understanding and using the web-of-trust
> sucks right now. How can we make that experience better for a user who
> understands the basics of cryptography?
> 
> 
> ** SSL/Certificate authorties
> 
> While certificate authorities are notoriously bad at the job they are
> supposed to be doing the CA system is still better than nothing - use it
> where appropriate. For instance if you have a website advertising your
> software, use https rather than http.
> 
> 
> ** Multi-factor spend authorization, AKA multisig wallets
> 
> <mainly discussed at the conference in terms of multiple individuals
> controlling funds, which is out of scope for this document>
> 
> Assuming any individual device is uncompromised is risky; wallet
> software SHOULD support some form of multi-factor protection of some or
> all wallet funds. Note that this is a weak "should"; mainly we want to
> ensure that users have options to keep large quantities of funds secure;
> accepting higher risks for smaller quantities is an acceptable
> trade-off.
> 
> FIXME: go into more detail.
> 
> 
> *** P2SH
> 
> Wallet software MUST support paying funds to P2SH addresses.
> 
> 
> ** Payment Integrity
> 
> Multi-factor wallets protect your funds from being spent without your
> knowledge, but they provide no assurance about where those funds went; a
> Bitcoin address is not an identity. A payment protocol, such as BIP70,
> is needed.
> 
> Wallet software SHOULD support BIP70. Yes, there are (justified)
> concerns about its current dependence on the certificate authority
> system, but those concerns should be addressed by a combination of
> fixing that system, and extending BIP70 with different and better
> identity verification options.
> 
> However, remember that in the absense of multi-factor wallets the "know
> who you are paying" protections of BIP70 are actually pretty much
> useless; malware that defeats the payment protocol locally is not much
> different than malware that silently rewrites Bitcoin addresses. There
> are other motivations for the BIP70 version of the payment protocol, but
> whether or not they are actually interesting for users is an open
> question; it was not designed by user-experience experts. Thus wallet
> authors should consider supporting a low priority for now.
> 
> 
> -- 
> 'peter'[:-1]@petertodd.org
> 000000000000000f9102d27cfd61ea9e8bb324593593ca3ce6ba53153ff251b3