Bits To Bitcoin: How Our Digital Stuff Works

Description

An accessible guide to our digital infrastructure, explaining the basics of operating systems, networks, security, and other topics for the general reader. Most of us feel at home in front of a computer; we own smartphones, tablets, and laptops; we look things up online and check social media to see what our friends are doing. But we may be a bit fuzzy about how any of this really works. In Bits to Bitcoin, Mark Stuart Day offers an accessible guide to our digital infrastructure, explaining the basics of operating systems, networks, security, and related topics for the general reader. He takes the reader from a single process to multiple processes that interact with each other; he explores processes that fail and processes that overcome failures; and he examines processes that attack each other or defend themselves against attacks. Day tells us that steps are digital but ramps are analog; that computation is about “doing something with stuff” and that both the “stuff” and the “doing” can be digital. He explains timesharing, deadlock, and thrashing; virtual memory and virtual machines; packets and networks; resources and servers; secret keys and public keys; Moore's law and Thompson's hack. He describes how building in redundancy guards against failure and how endpoints communicate across the Internet. He explains why programs crash or have other bugs, why they are attacked by viruses, and why those problems are hard to fix. Finally, after examining secrets, trust, and cheating, he explains the mechanisms that allow the Bitcoin system to record money transfers accurately while fending off attacks. Contents......Page 8 Preface......Page 10 Acknowledgments......Page 14 1. Introduction......Page 16 I. Single Process......Page 18 2. Steps......Page 20 Bits......Page 23 Noise......Page 24 Is Computation Physical?......Page 25 Weighing Programs......Page 26 Analog/Digital Conversion......Page 27 Born Digital......Page 31 3. Processes......Page 32 Reading as a Process......Page 33 Turing Machines......Page 34 Infinite Processes......Page 37 Execution......Page 38 Effective Construction......Page 39 Hardware vs. Software......Page 40 Uniformity Gives Speed......Page 41 Moore’s Law and Uniformity......Page 42 4. Names......Page 46 What’s in a Name?......Page 47 Quoting......Page 49 Sentence Patterns......Page 52 Lambda......Page 53 5. Recursion......Page 56 Factorial......Page 57 The House That Jack Built......Page 58 Finite and Infinite......Page 61 All Software Is Flawed......Page 64 Discrete States......Page 65 Testing......Page 66 Massive Scale......Page 67 Doubling......Page 68 Branching......Page 69 Malleability......Page 70 Making Things Worse......Page 72 Requirements......Page 73 Specifications......Page 75 Implementation......Page 77 Environment......Page 80 Big Problems......Page 81 Computational Complexity......Page 82 Ignoring Constants......Page 83 Categories of Complexity......Page 84 Uncomputability......Page 86 Formal Logic......Page 87 No Solution to Hilbert’s Problem......Page 88 Russell’s Paradox......Page 89 Building a Paradox......Page 90 The Halting Problem......Page 91 II. Interacting Processes......Page 94 8. Coordination......Page 96 Multiple Books and Multiple Readers......Page 97 Deadlock......Page 98 Gridlock......Page 99 Detecting Deadlock......Page 100 Breaking Deadlock......Page 101 Livelock......Page 102 Thrashing......Page 103 9. State, Change, and Equality......Page 104 Stateless vs. Stateful......Page 105 Assignment......Page 106 Referential Transparency......Page 107 Is State Necessary?......Page 108 Same Object vs. Different Object......Page 110 Lost Update......Page 116 Two Processes, in Detail......Page 117 Interleaving......Page 118 Multiprocessing and Multiprogramming......Page 119 Some Example Interleavings......Page 120 Is This a Real Problem?......Page 122 Mutual Exclusion......Page 123 Using a Lock......Page 124 11. Interrupts......Page 126 The Unpredictable Environment......Page 127 Check, Check, Check …......Page 128 Interrupts and Handlers......Page 131 Shared Services......Page 132 Frequent Check, Rare Problem......Page 133 Protecting Memory......Page 135 System Calls......Page 136 12. Virtualization......Page 138 Managing Storage......Page 139 Virtual Memory......Page 141 Virtual Addresses and Real Addresses......Page 142 Virtual Machines......Page 144 Sharing Servers......Page 146 Building a Hypervisor......Page 148 13. Separation......Page 150 Autonomy......Page 151 Standards......Page 152 Distance Revisited......Page 153 Light Is Slow......Page 154 Is Anyone There?......Page 155 The Order of Events......Page 157 Reaching Agreement......Page 159 Heartbeats......Page 161 Are Earth-Size Distances Small?......Page 163 14. Packets......Page 166 Compression......Page 167 Incompressible Data......Page 168 15. Browsing......Page 170 Programs in Browsers......Page 172 Naming Resources......Page 173 Hierarchical Names......Page 174 Shorter Names......Page 176 Naming Servers......Page 177 Finding Servers......Page 178 Caching......Page 181 Talking to the Server......Page 184 Structure vs. Presentation......Page 185 Forms......Page 186 Escaping......Page 187 Searching Searches......Page 188 III. Unstoppable Processes......Page 190 Reliability vs. Availability......Page 192 Fail-Stop......Page 194 Spares......Page 195 Error Correction......Page 196 Error Detection......Page 197 Storage and Failure......Page 200 Flash......Page 202 Injury vs. Death......Page 203 Logging vs. Replication......Page 204 Stable Storage......Page 206 RAID......Page 207 Independent Failures?......Page 208 Common-Mode Failure......Page 209 Failure Rates......Page 210 Specifications Revisited......Page 214 Consistent Comparison......Page 215 Comparing Results......Page 217 Byzantine Failure......Page 219 Guaranteed Delivery?......Page 222 The End-to-End Principle......Page 223 Acknowledgment and Retransmission......Page 224 Multiple Acknowledgments and Negative Acknowledgments......Page 225 Congestion Collapse......Page 226 Congestion Control......Page 228 Cheating on Congestion Control......Page 229 19. Inside the Cloud......Page 232 Wires and Jacks......Page 233 Router......Page 234 Ethernet......Page 236 Interconnecting Networks......Page 237 Internet Protocol (IP)......Page 238 Routing as a Network Service......Page 239 DHCP......Page 242 Advertising......Page 243 Longer Routes......Page 244 Scaling Up......Page 245 IP Address Notation......Page 246 Distributed Management......Page 248 Network Address Translation (NAT)......Page 249 Routing Failure......Page 251 Interconnecting Different Routing......Page 252 Spraying Requests......Page 256 Tiers......Page 259 Geographic Distribution......Page 261 Cloud Computing and Big Data......Page 264 IV. Defending Processes......Page 266 Defending: An Overview......Page 268 Viruses......Page 269 Single-Purpose vs. Multipurpose......Page 270 Extensibility and Viruses......Page 272 Preventing Viruses......Page 273 Detecting Viruses......Page 275 22. Thompson’s Hack......Page 278 Translating High-Level Language......Page 279 Thompson’s Hack: Simple Version......Page 280 Thompson’s Hack: The Real Thing......Page 283 Assessing the Danger......Page 285 23. Secrets......Page 288 Secrets Are the Solution......Page 290 Steganography......Page 291 Cryptography......Page 292 Shared Secrets and One-Time Pads......Page 293 Key Exchange......Page 295 Public Key......Page 296 Multiplying and Factoring......Page 298 Messages via Multiplication......Page 299 Proving Identity Remotely......Page 300 24. Secure Channel, Key Distribution, and Certificates......Page 304 Why Is This Worthwhile?......Page 306 Secure Channel, Refined......Page 307 Key Distribution Center (KDC)......Page 309 Scaling up Key Distribution......Page 311 Certificates......Page 312 Cryptography for Integrity......Page 313 Revocation......Page 315 Root CAs and Hierarchies......Page 317 Trust Problems......Page 319 Ledgers......Page 322 Special Roles vs. Ordinary Participants......Page 324 Guarantor......Page 325 Bitcoin......Page 326 Distributed Ledger......Page 327 26. Bitcoin Mechanisms......Page 330 Unforgeable Transactions......Page 331 Unforgeable History......Page 333 Bitcoin Puzzles......Page 337 Hash Functions......Page 339 Hashing Data......Page 340 Moving Time Forward......Page 341 The Crowd Foils Cheating......Page 342 Rewards via Mining......Page 343 Pollution and Bitcoin......Page 344 Mining and Value......Page 345 Bootstrapping Value......Page 346 Bitcoin and Governance......Page 347 Significance of Bitcoin......Page 348 27. Looking Back......Page 350 Index of Metaphors and Examples......Page 352 Subject Index......Page 356