Incomplete, rough draft of whitepaper I was composing...
Bitcoin Proof-of-work and Block ChainIn the seminal Bitcoin whitepaper[1] Satoshi somewhat obscured the
essential weakness of financial institutions that they are captured by the asymmetrical vested interests of society described by Olsen[2] which is to the detriment of individual empowerment. Ultimately it is the lack of
anonymity of the institutions and transactions which allows society to identify them and thus the asymmetrical vested interests to capture them. Instead Satoshi emphasized transaction reversibility as the problem, but which is rather a sometimes desireable feature that is not necessarily incompatible with anonymity in all cases.
Financial transactions must be recorded in a public or private ledger trusted by both the spender and the recipient, otherwise funds could be unspent or double-spent to a plurality of recipients. To provide a ledger that can't be captured, Satoshi described a proof-of-work (PoW) scheme where transaction peers communicating over the network compete to be the first to solve a computational puzzle which is unique for each block of transactions added to a public ledger. The security of this ledger against double-spends has three (3)
essential requirements.
1. The computational puzzle can't be preimaged, i.e. nothing can be known about solving the puzzle until the prior block's puzzle is solved.
2. Without at least 50% of the aggregate computational power of all transaction peers, it is not possible to create a modified chain of blocks starting from any present or past block, which would contain more blocks than the block chain controlled by the remaining cooperating peers. Thus the longer chain is trusted.
3. The block chain is cryptographically linked in forward order, such that the historical proof-of-work and transactions can be independently verified at any time in the future. Thus the transaction peers may leave and rejoin the network at will without need for a trusted centralized storage.
Note security point #1 eliminates from consideration PoW schemes in which the puzzle is some real-world computational work because the puzzles are known a priori and are thus pre-imageable. Non-PoW voting and membership schemes disqualify because the ordering of designation of authority (to decide which transactions are in each block) to transaction peers is pre-imageable, or requires peers trusted by reputation which is centralizing on a slippery slope towards Olsen capture.
Bitcoin's blockchain stores sender(s) signed hashes of the transaction data, which includes the nonce transaction id and hash(es) of the destination public key(s). The monetary value of each hash of the public key is computed from the transactions history. Satoshi suggested pruning historical transactions from the blockchain which are no longer relevant to computation and security of the set of unspent coins (a.k.a. Unspent Transaction Output Set or UTXO).[3] Note hashes of destination public keys[4] obscure the asymmetric public key cryptography from attempted attacks until a spend transaction is sent from the public key. However, this is not sufficient to assure with the same confidence as for symmetric key cryptography that an attack can't occur once the spend transaction is sent.[5]
Mini-Block ChainThe pruned Merkel transaction tree is not the most compact data structure possible, because an additional hash must be stored for each branch of the tree to each unpruned transaction[3], sender signature(s) are stored for each unspent coin, and transactions can't be pruned until all outputs are spent.[6] Note these transaction peers resource requirements only apply to startup download bandwidth, startup verification DRAM, and ongoing disk space, because the UXTO balances and hashes of each unspent coin address can be kept ongoing in DRAM without the signatures.
However if the public key account balances are separately stored, then the signatures only need to be kept for N blocks, where N is high enough to guarantee with sufficient probability that the peer's current chain won't be orphaned by a competing fork that gains more than N blocks x difficulty to become the accepted chain. For example in Bitcoin miner coinbase transactions can't be spent for 100 blocks[7].
A separate "proof chain"[8] linked since the genesis block is necessary, otherwise an attacker could utilize unlimited time to construct a fake chain with more than N blocks x difficulty. Note each PoW puzzle solution difficulty (i.e. the number of zero bits in the block's hash) is independent of the transaction data in the block, thus constructing a fake proof chain requires the same historical resources as the legitimate proof chain. Including a hash of the account balances in the corresponding block links their veracity to the longest chain. If an attacker creates fake account balances that have a hash that agrees with some block, and is able to outpace the difficulty of the rest of the legitimate peers, it could erase preexisting and create new account balances.[9] Thus the 50+% attack would be more dangerous. However this can be mitigated to the same extent that Bitcoin does with community resources to store the entire block chain transaction history linked from the genesis block. These super peers with sufficient resources would be entrusted to detect and show the proof of a 50+% attack.
To help insure that transaction signatures are not replayed, transaction inputs could be entirely spent to outputs which include a new address for the change. Signing a hash of the transaction which included a nonce (e.g. the transaction id in Bitcoin) would not be secure for the transaction peers which don't download the entire community transaction block chain history. Note the replay could still occur if the fully spent input address was ever sent a sufficient balance again. Signing a hash of the transaction which included the block id and allowed the transaction to appear once in any one of the M (where M <= N) blocks that followed, is probably a superior solution.
The transactions would not need to be stored in a Merkel tree since the only reason for doing so is to be able to verify remaining transactions against the block header after pruning and to support simplified payment verification[10] which is unnecessary because fully verifying peers would have optimized resource requirements. The data structure for the account balances has to meet certain requirements.[11]
The DRAM and download footprint would be dominated by the account balances data structure.[12] To eliminate the useless proliferation of public keys, the block chain would not accept transactions that create non-zero balances less than some quantity of coin (e.g. 0.01 BTC).
Since transaction sender signature size becomes an insignificant factor (except for the super peers), the relatively insecure ECDSA of Bitcoin can be replaced with Lamport signatures with extraordinary long key lengths, e.g. 4096 bit.[5]
AnonymityAll known existing solutions for anonymizing the IP address, e.g. Tor, I2P darknet, anoncoin, etc., are not secure against timing attacks.[13] Assuming that problem is solved, then a remaining problem is how to delink spends from other spends. Paradigms which mix coins from numerous identities only provide plausible deniability since the hashes of the addresses of all the input coins are in the public record, and the probability of deniability is reduced by the percentage of inputs provided by an attacker or participants who leak their identity to their outputs. Decentralized mixers are difficult to design to be resistant to DoS attackers, although Zerocoin might be a solution.[14] It is possible that some vendors might not accept coins that originated from mixers due to "know your customer" anti-money laundering concerns.[15] Thus the most robust solution is to obtain coins anonymously with small values. This can be done by mining coins, or anonymously receiving payment in coins. Unless the attacker has a list of all the customers, by giving a unique destination address to each customer then it is impossible to correlate that these coins belong to the same vendor. If coins can be anonymously converted into cash or mining hardware, they can be anonymized.
1-Confirmation TransactionsTo successful double-spend or unspend, the theft transaction needs to be placed in a block that will become orphaned and the winning chain must be obscured from the merchant accepting the 1-confirmation transaction. There is no reliable way to accomplish this attack on every attempt without 50+% of the PoW resources. So for small ticket items where rare theft is tolerable, the merchant can accept 1-confirmation transactions. An improvement would be to punish any transaction which overdraws the sender's balance, by charging a percentage fine of the balance that is not given to anyone (don't want to reward miners for this beyond the transaction fee which must be less than the fine, since the attacker may be the miner). When the attack succeeds, there won't be any balance to punish. However, since the attack doesn't succeed every time, then the punishment would further discourage the attack.
[1] Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System", 1. Introduction
[2] Eric S. Raymond, "Some Iron Laws of Political Economics", Armed and Dangerous blog
[3] Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System", 7. Reclaiming Disk Space
[4]
https://en.bitcoin.it/wiki/Protocol_specification#Addresses[5] AnonyMint, "How is same signed transaction not reusable, also quantum security of ECDSA?",
https://bitcointalksearch.org/topic/how-is-same-signed-transaction-not-reusable-also-quantum-security-of-ecdsa-309594[6]
https://bitcointalksearch.org/topic/m.2268831[7]
https://bitcointalksearch.org/topic/m.1546809[8] J.D. Bruce, "Mini-Blockchain Project wiki, Proof Chain",
http://bitfreak.info/mbc-wiki/index.php?title=Proof_chain[9]
http://bitfreak.info/mbc-wiki/index.php?title=Weaknesses_and_attack_vectors#The_Secret_Chain_Attack[10] Satoshi Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System", 8. Simplified Payment Verification
[11] J.D. Bruce, "Mini-Blockchain Project wiki, Account Tree Structure",
http://bitfreak.info/mbc-wiki/index.php?title=Account_tree#Requirements_of_Account_Tree_Structure[12]
https://bitcointalksearch.org/topic/m.2556839[13]
https://bitcointalksearch.org/topic/m.3109291[14]
https://bitcointalksearch.org/topic/coinjoin-bitcoin-privacy-for-the-real-world-279249[15]
https://bitcointalksearch.org/topic/m.2318052