FIRST EDITIONS IN ORIGINAL WRAPS OF THE FOUNDATIONS OF BITCOIN’S BLOCKCHAIN ALGORITHM, INCLUDING THE CONCEPTS OF BYZANTINE FAULTS, THE BYZANTINE GENERALS PROBLEM, PROOF-OF-WORK, & SOFTWARE ABLE TO TOLERATE BYZANTINE FAULTS.
The creation of a system like Bitcoin -- one both distributed and reliable -- is exceptionally problematic. The issues that arise are not specific to crypto currencies and instead apply to any form of distributed system where there is no central control enforcing trust. This issue has become known as the Byzantine Generals Problem (BGP) and it was first described in 1980 in the first paper offered here (Pease, Shostak, and Lamport); the trio then generalized, proposed, and solved BGP in their 1982 second paper also included here.
Prior to the 1980 paper, it was generally assumed that a three processor system could tolerate one faulty processor. The 1980 paper shows that ‘Byzantine” faults’ – be they malicious attacks, operator mistakes, source congruency, or software errors – are any failures where the failing device seems to behave in an arbitrary way as opposed to just ceasing to function. In such a scenario, faulty nodes exhibit arbitrary behavior presenting different symptoms to different observers, sometimes making it unclear as to whether or not a component has even failed. Here the authors prove in such a scenario -- Byzantine faults causing a processor to send inconsistent information to other processors -- the assumption that a three-processor system/algorithm can tolerate one faulty processor no longer holds true (1980).
In search of a method by which computer networks could handle conflicting information in order to make the right decisions, the authors developed The Byzantine Generals Problem (BGP). They envisioned the problem of receiving conflicting requests from computers as that of Byzantine generals trying to coordinate decisions despite differing information: “We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement. The generals must have an algorithm to guarantee that (A) All loyal generals decide upon the same plan of action and (B) A small number of traitors cannot cause the loyal generals to adopt a bad plan” (1982).
The authors proposed a BGP solution algorithm or technique that can tolerate Byzantine faults (beginning with the need to first reach consensus amongst ‘the generals’ as to which component has failed in the first place).
Another BGP solution was presented with Bitcoin’s novel proof-of-work system in which “the problem [was solved] by utilizing a public decentralized proof-of-work chain in order to reach a consensus on ownership of units of the currency” (ibid). “The bitcoin network works in parallel to generate a blockchain with proof-of-work allowing the system to overcome Byzantine failures and reach a coherent global view of the system's state” (Wikipedia).
That ‘proof-of-work’ system or protocol is the subject of the 3rd paper included here. In it, Dwork and Naor invent the concept, proposing ‘proof of work’ as a piece of data which is difficult (time-consuming, costly) to produce but easy for other to verify. The fourth document (Castro and Liscov) describes the first practical software implementation of a byzantine fault tolerance algorithm able to tolerate Byzantine faults. Item #1247
CONDITION: Two ACM documents: individual issues in original wraps, fine condition save for library stamp on each front wrap. Crypto '92 document: pristine condition in original paper wraps. Third Symposium document: two small stickers on front wrap, otherwise in pristine original paper wraps.