Bitcoin Forum

Bitcoin Improvement Proposal #2112
Ownership: 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.

(continued...)

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.

(Continued...)

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.

(End.)

You cannot just make your own BIP and call it 2112. You need to email genjix and he'll assign you a BIP number and help with copy-editing the document. Although first you should email the mailing list with your proposal.

You might have something there but I didn't really understand it at all.

Any chance you could describe what you want to achieve in a simpler style ?

He just did.

If you are talking about a new root block, you want to start a new blockchain then right?  Is this about Bitcoin or a new alt-chain?  How is it compatible with existing coins if it requires a new genesis block?

Do you have the technical abilities to write this LISP client yourself?  If not, who do you propose to do it?  Does Gavin know LISP?

Do you think the LISP client can be written perfectly the first time, never needing revision?  Won't it be locked in forever, killing the whole chain if a bug is ever found?

Sorry if these are dumb questions, a lot of this is over my head.

Interesting. I've already got this working within our own (not yet publicly released) bitcoin-derived protocol. We also chose LISP as the language for writing "chain definitions", as we call them but I like your phrasing better, as well as replacing the opcode-based scripting system for transactions. We're also using the bittorrent protocol for the P2P overlay network and DHT capabilities, so I can report that works well (and better than bitcoin, I believe, although we haven't the metrics yet). I would add that the prospectus could include rules for accepting or rejecting future modifications. That's how we're handling it, combined with a PKI infrastructure.

What are the advantages of the bittorrent protocol over bitcoin's current P2P scheme?

It isn't really bittorent versus bitcoin. The early bittorrent implementations had the same problem: you had to run one executable per active torrent and open one port per each active torrent. It is more of a "quality of the implementation" issue.

The discussion why DHT is better than IRC or BT trackers has been done so many times that I won't repeat it here.

Thanks for the heads up. Good luck in your venture. I'll revise my proposal to flesh out the details and make it more readable to a broader group of people than just persons having oridinary skill in the art (http://en.wikipedia.org/wiki/Person_having_ordinary_skill_in_the_art).

Are you planning to patent this?

IMO this doesn't sound like a good thing.

It bloats all future client implementations with a complex interpreter, raises the bar of transaction rule-verification to the mathematical elite, encourages closed source clients, further strongly couples the protocol to the default client and removes the ability for the block chain to fork in a democratic manor.

Can I assume that you are a fan of the Canadian rock band Rush?

:)


Cheers,

Ian.

90125!

:)

Thank you for your valuable input.

• It bloats all future client implementations with a complex interpreter

The LISP interpreter is probably 2nd or 3rd smallest interpreter possible: smallest is MUMPS, LISP and Forth vie over the 2nd and the 3rd position. BASIC and Javascript are for sure bigger and more complex than LISP. I still think that LISP with a lean theorem prover as a checker is a better choice than a C++ implementation of an RPN calculator and Gavin's wish for a fuzzer to thoroughly test that calculator.

• raises the bar of transaction rule-verification to the mathematical elite

This is very true. However in 21st century this elite no longer have any financial barrier to entry. The required curricula are available for free online, e.g. http://mitpress.mit.edu/sicp/full-text/book/book.html . The other important observation of the elitism of LISP are the original Yahoo! stores. They were all created with LISP back end. They came out as one of the first e-commerce platforms, were always very secure (anyone heard about any exploits for Yahoo! stores?) and had one of the lowest barriers to entry.

• encourages closed source clients

This point is both true and false, depending on the timeline. Lets compare Bitcoin implementation to the web browsers. Currently Bitcoin is in the stage of NCSA Mosaic. Then Netscape Navigator became a de-facto leader by including a client-side interpreter, among other things. Then the whole web exploded and we now have competing open and closed source implementations.

• further strongly couples the protocol to the default client

Initially probably yes. It really raises the barrier to entry for less-than-competent software vendors. I personally think that this will be a good thing: the quarter-brained client implementations are a plague in the Bitcoin-sphere. Later on the things will change: if there's at least one client that is fully ACID and embeddable then the overall software quality expectation will rise to the level demanded by the serious financial applications.

• removes the ability for the block chain to fork in a democratic manor

This is simply untrue. My BIP actually encourages forking and provides tools to do it in a very safe manner. It also facilitates re-joining of the forks that a willing to do so. It supports all forms of self-governance: democracy, republic, autocracy, corporatism, etc. It all depends on the contents of the initial prospectus.

• No matter what I need to edit my BIP to improve its readability

One thing that needs to be repeated: this BIP isn't an urgent thing. It just shows one possible way forward for Bitcoin. I don't expect it to receive any significant attention until at least one or two knees in the coin-generation curve are behind us.

Sorry for the necro-thread, but this is an interesting proposal that I hadn't noticed before.


Bitcoin has never really been a democracy, even though it has democratic aspects.  "Demos Kratos" means "people power".  In Bitcoin, the end-users don't have a vote;  only miners do.  So the average people are disenfranchised.  Fiat currencies like the US dollar are, on paper at least, more similar to democracies, with a set rate of inflation tied to population growth effecting wealth redistribution, and with the banking system acting as very corrupt election organizers to distribute these newly-printed "votes", ie. dollars, to each person.  Regardless, democracies are unsustainable anyways, which is the reason that...

The current Bitcoin network is instead similar to a Republic.  "Rei Publica" means the "public things".  That would be the blockchain.  This exists in balance with the "private things", the private keys held by end-users.  Access to the "public things" occurs via the miners, acting as contracted representatives of end-users and ultimately voting in proportion to hashing power on all matters concerning the public blockchain.

It seems to me that your proposal creates more of a technocracy than anything.  It's an interesting, and flexible, technocracy, frighteningly so in certain aspects.  But the defining feature seems to be its deliberate lack of any coherent political philosophy with regards to who, or even what, ultimately controls the Bitcoin network, and how.

Actually this sounds like an excellent idea. How much sense would it make to further expand it in order to mix bitcoin-securities straight in the blockchain?

I don't think that the extension would be needed. Bitcoin-denominated-securities could be supported with just a separate "digital prospectus". Such a prospectus could even do cross-blockchains validation to support truely atomic transactions.

But again: this is a long-term proposal. Lots of water will have to flow in the Alpheus and Peneus rivers to clean filth from the Augeas' stables of cryptocurrencies.

Thank you all for your comments.

I had a hard time determining from the proposal what problem it was intended to solve.

I also was unable to find where it defines the jargon and neologisms it uses.  To most people, a "digital prospectus" is a document that describes a financial security for potential buyers, available as a PDF download.  It is apparent that this isn't the intended meaning here, and the proposal lacks a definition for what alternate meaning should be understood for this term (as well as numerous other terms).  An improved revision to this proposal would spend its first paragraph concisely describing the benefit expected to be derived from considering the proposal beyond anticipated usefulness in hypothetical patent litigation.

Yeah, you are 100% right. As written the document pretty much assumes that the reader has a Master of Science in Computer Engineering or equivalent and some past experience reading patent applications in the relevant field.

The more plain-spoken description of "digital prospectus" is: a cryptographically signed machine-executable description of the rules of the block validity. As opposed of the solemny sworn human-language statements of the core development group that they aren't going to materially change the rules for the valid blocks.

As with all "far-looking forward statements" the readability here is low. But the law is what it is and readability comes second after unambiguity.

I'm planning to re-edit the document in the future, once I collect enough feedback how to do it without transoforming it into a meaningless marketing drivel. It isn't an offer to sell anything.

Edit: and by the way, here's the pointer with explanation why it stays 2112 as opposed to the number that it go assigned.

https://bitcointalk.org/index.php?topic=61575.msg723630#msg723630

If you only want comments, suggestions, and ridicule from others with the same particular degree and experience, you ought to consider adding those specific qualifications to your signature line directing us here so that others outside of your assumed audience don't have to waste their time with it.

Little old lowly me, the main ridicule I'd have to offer is that your ability to convey ideas in written form sucks balls and is definitely not on par with the technical aptitude you claim, and that your principal point you seem to be looking to make (if your insistence on a vanity BIP number doesn't make that strikingly clear) is that you consider yourself a badass.

I assume he means a prospectus embedded in the genesis block. So a new block chain would be a sort of IPO with the contract locked in  forevermore.

Well, not "locked forevermore". The only thing locked like this is "root prospectus". Every implementation would need to support "prospectus ammendments" that form tree branches. So every "digital security" is defined by a pair (hash(root prospectus),hash(tip of branch steming from the root)).

http://en.wikipedia.org/wiki/Tree_(data_structure)

Edit: I guess the point of this can be summarized: it makes the changes to the algorithms explicit and verifiable in linear time, very much like git does to any general source code.

Edit2: Also, like git and like normal securities exchanges this will allow for orderly and verifiable backtracking and reversal, once the "economic majority" decides that certain branch of the prospectus was erroneous, fraudulent or otherwise undesired.

Just musing if Coq, Haskell or even Fortran are worth a look ...

Ah come now, it's not that bad is it.

Another proposed language was Lua. Apparently it rapidly spreads in the computer science departments in Latin America. Unfortunately I'm illiterate in both Portugese and Spanish, so I can't read the most recent research papers.

I took "suck balls" as a sort of backhanded compliment from Casascius. If he really wanted to put me down, he would've written e.g. "sucks dead Easter bunnies through a bent straw" or "could suck-start a Harley through the exhaust pipe."

English is a virtual minefield of smoothly readable, but ambiguous sentences, e.g. pharmacist dispensed with accuracy.

I suggested recently that the 8.1 patch be evolved (which hard codes certain parameters for all clients), is evolved into a schema validation engine for the protocol and transactions, so that the behavior of the node and client has prescribed and defined edges, defineed by a computable  definition.

Different words form yours, same basic concept - a core interpreter that validates protocol and transactions and is the agreed, reference, signed implementation that is authoritative for testing, QA, interop and attestation of client validity.

if it comes real, I up vote for lisp...not like emacs one but a Foss one

Emacs is FOSS. However, I would never write software in elisp other than simple utility snippets for use in Emacs. There are several FOSS Common Lisp implementations available. Personally I prefer SBCL. Common Lisp is an ANSI/ISO standard so you don't get into the creeping featurism that you have in many of the dictator languages, like Python (where the semantics suddenly change even though the syntax is the same). Lisp was a dictator language in 1958 but became a standard in 1994.

But why an interpreter? There are quite a few open source Common Lisp compilers out there. Of course they also include an interpreter and compiler since you at any point can dynamically build a s-expr and call eval (eval (cons '+ '(1 2 3))) or even (progn (defun somefun () (+ 1 2 3)) (compile 'somefun) (list (somefun) (compiled-function-p #'somefun)))

When writing Lisp code is quite common to design a domain specific language (DSL) on top of Common Lisp to fit the problem domain. Macros are quite handy in this process. Then you describe the problem using the DSL.

There are some open source Common Lisp based formal tools available, like ACL2: http://www.cs.utexas.edu/~moore/acl2/  (http://www.cs.utexas.edu/~moore/acl2/) ACL2 was used by AMD to prove the floating point operations in some earlier CPU design, etc. A quite fascinating piece of software IMHO.

What you have in mind is being realized by tauchain

https://bitcointalk.org/index.php?topic=950309.0

No, really no. The similarities are superficial only.

To clarify the difference I'm saying that this project/idea is scoped to be fully implemented in approximately 1MB of executable code. Somewhat limited implementation could probably be made on the historical CPUs like Intel 8086 or Hitachi HD64180. Fully featured implementation will for sure fit in a CPU with 16MB of address space like Intel 80286 or Zilog eZ80 (the new one, not the historical Z80) or the modern compatibles to the historical PDP-11/LSI-11. Basically any CPU supporting multiple banked/segmented 64kB address spaces is the satisfactory target.

The segmented/banked 16-bit-ness is not a requirement. The implementation could as well use the modern flat 32-bit or 64-bit addressing. However it is my experience that explicitly segmented 16-bit address spaces are a great aid in enforcing security and safety of the code. They are also aids in mechanical proving of the code correctness (even if only partial proofs).

I'm not actually advocating the use of those historical CPUs running with clocks in the single MHz range. I'm thinking of drop-in cores to be synthesized using modern FPGA or ASIC processes with the modern clock rate of high hundreds of MHz . The physical package of such cryptographic kernel device would be similar to the (nano-)SIM card or (micro-)SD card.

The supporting blockchain data is a different story. It would have to be either local storage in the present terabyte ranges or a networked access to the remote storage at single megabits per second speeds.

Edit: Anyway, I've read the tauchain whitepaper as well as all the 18 pages of the tauchain thread with interest. Thank you very much.