BIP 0016

From Bitcoin Wiki
Revision as of 17:37, 18 December 2011 by 2112 (talk | contribs) (initial raw copy from the
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Bitcoin Improvement Proposal 0016

Author: 2112

Copyright: Public domain

Status: Draft -> Deferred

Type: Informational

The purpose of this document is purely informative and not normative. It aims to spread to the wider cryptographic community the various improvements to the well-known Bitcoin design that would address some limitations of the existing implementation that prevent its wider adoption. The proposed changes are far-reaching and as such are not suitable for immediate implementation. They are so extensive that it is certain that a complete reimplementation will be required. No matter what is the immediate fate of this proposal, I’m remaining hopeful that the ideas explained will remain public domain knowledge and will serve as a prior-art counterclaim in any future patent litigation.

The centerpiece of this proposal is the idea of “digital prospectus”: a program whose main functionality is to do perform a verification of the submitted blocks and transactions. This program will be cryptographically hashed and will become a “root prospectus hash” in this proposal and an equivalent of the newspaper headline in the present Bitcoin genesis block. In addition the “root prospectus hash” will become the identifier for the “digital financial security” in the transactional transport protocols. As such it will replace 4-byte integer 1 in the current Bitcoin protocol.

The choice of the programming language for the “digital prospectus” needs to be made early. The primary requirement is that the language needs to have very strong theoretical underpinnings: it must be able to efficiently express its own interpreter and there must be existing programs that are capable of proving simple theorems expressed in this language. It seems to me that some dialect of LISP would be suitable choice. LISP s-expressions maintain very close relationship between the human-readable text of the program (which will be hashed to form the digital prospectus) and the internal data structures that represent the program and which will be interpreted and verified many times during its lifetime. The runtime efficiency is pretty much immaterial; the properties that are tremendously important are (1) well-defined semantics; (2) the ability of the program to analyze and transform its own text; (3) possibility of secure implementations that are resistant to the cryptographic side-channel attacks like “differential fault analysis”, “differential power analysis”, “timing attack”, etc.

The exact content of the “digital prospectus” would depend on the type of the “digital financial security” that it describes. For the security like Bitcoin it would define the rules for the validity of the block and the transaction. It would exactly specify the fees that need to be paid for the inclusion of the transactions in the block and who is allowed to specify checkpoints for the longest chain of blocks. In the current Bitcoin implementation fees are pretty much left unspecified (with the exception of “dust spam defense”) and two block-chain checkpoints were signed by “fabianhjr”, who is pretty much unknown in the community.

It isn’t assumed that the “digital prospectus” remains constant throughout the whole lifetime of the “digital financial security”. The “root prospectus” will be included in the root signature block. The implementation will provide a means of recording the “digital prospectus amendments” which in effect will patch the original prospectus. Throughout the lifetime of the “digital financial security” there will be many forks and joins in the DAG (directed acyclic graph) of the prospectuses. The acceptance of forks and joins will be left for the approval of the end user. In case of the competing forks it will be up to the end user to decide whom to trust. The choice needs to be made only when transacting, the peer can participate in multiple simultaneous versions of the amended security. There will be an obvious overhead of the storage and network bandwidth, but the user will not have to make any either-or choices unless actually transacting.

On the network transport layer the peers will locate each other using a DHT (distributed hash table) using both “root prospectus hash” as well as an ordered pair of the “root and amended prospectus hashes”. I don’t envision that the peers in the proposed protocol would need to shun any other peers. The peer-to-peer network will resemble more of Bittorrent peer-to-peer network: all peers share the DHT and make direct connections only when interested in the sharing of the particular torrent.

The “digital prospectus” moves the Bitcoin from the equivalent of the “oral contract” to the equivalent of the “written contract”. In the current implementation of Bitcoin there exist an implicit trust in the “core developer team”, their “Satoshi client C++ implementation” and the “consensus of the majority of the miners”. The proposed implementation would spell the requirements exactly and would allow continuing trading of the instruments among those who do not want to trust the consensus of the majority and any future amended prospectuses.

In other words it would change the Bitcoin government from the democracy to the republic. The last but not least change allowed by the existence of the “digital prospectus” will be the change in scripting engine. Currently Bitcoin uses a simple postfix script language implemented as an automaton with a stack but without loops. The “no loop” requirement was to avoid possibly of attacks by infinite loop. I propose that the same programming language that is used to represent the digital prospectus is used to represent the scripts. If the prospectus writer decides to allow general scripting with looping she can include in the prospectus a relatively simple theorem prover: given the script and N inputs does the script return true or false in at most K*N steps, where K is arbitrary constant chosen by the prospectus writer. This is not a general undecidable stopping problem because the theorem prover can return “undecided within C*L steps”, where L is the length of the script and C another arbitrary constant in the prospectus. The strong syntax and semantic checker for scripts also has obvious benefits for software testing.

Another benefit of using LISP (or any similar language) for scripting lies in its transformability. There exist a body of research of ultra-reliable computing that used “SIMD-like” and/or “Hamming distance 3 or higher” coding for error detection and correction. Ultimately no LISP computers were used in the deep space probes because of overall power requirements. For the terrestrial finance transactions the absolute power used by the computer is not really limiting, but the invulnerability to the various side-channel attacks like differential fault analysis becomes a tremendous benefit. Those fault-hardening and SIMD-like transformations could be applied mechanically to the scripts so long as they are represented appropriately.

Obviously Bitcoin stack automaton scripts can be automatically translated to the prefix s-expression notation and undergo the same transformations as above. But I don’t see the benefit it requiring this additional step aside from backward compatibility.

Overall the program implementing the current proposal could be compatible with Bitcoin and all currently existing alternative block-chain currencies, including Litecoin, IxCoin, I0Coin, Tenebrix, and Fairbrix. It would be up to the Bitcoin core development team to commit to the precise rules regarding fees and checkpoints. It could even transact Solidcoin version 2 and would conceivably prevent any closed-source modifications that plague that clone of Bitcoin. The network transport protocols are currently incompatible, but the network adaptation layer would be very simple.

In summary this proposal encompasses three main changes: (1) explicit cryptographically signed and software-executable contract included in the root block, (2) cooperative DHT-based networking protocol that does away with IRC, dedicated ports and 4-byte identifiers, (3) general prefix script notation backed by strong syntax and semantic checkers. Because of this proposal is very far-reaching I suggest that it will be immediately placed in the dormant state. Initially we can work on clarifying its wording, but the full implementation will require a lot of discussion and research. Hopefully the information included here will stay in public domain and will spread amongst the cryptography research community.