Day Mark Stuart - Bits to bitcoin: how our digital stuff works

Bits to Bitcoin

How Our Digital Stuff Works

with illustrations by C. A. Jennings

The MIT Press

Cambridge, Massachusetts

London, England

2018 Mark Stuart Day

All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.

This book was set in Stone Serif by Westchester Publishing Services. Printed and bound in the United States of America.

Excerpt from The Wizard of Oz granted courtesy of Warner Bros. Entertainment Inc.

Library of Congress Cataloging-in-Publication Data

Names: Day, Mark Stuart, author. | Jennings, C. A., illustrator.

Title: Bits to bitcoin : how our digital stuff works / Mark Stuart Day ; illustrated by C.A. Jennings.

Description: Cambridge, MA : MIT Press, [2018] | Includes index.

Identifiers: LCCN 2017046504 | ISBN 9780262037938 (pbk. : alk. paper)

Subjects: LCSH: Computer science--Popular works.

Classification: LCC QA76 .D3333327 2018 | DDC 004--dc23 LC record available at https://lccn.loc.gov/2017046504

: Pay no attention to that man behind the curtain! The great Oz has spoken!

Dorothy (pulling back curtain): Who are you?

: Oh I I am the great and powerful Wizard of Oz.

Dorothy: You are? I dont believe you.

: Well, Im afraid its true. Theres no other wizard except me.

From The Wizard of Oz (1939)

Contents

List of Figures

A stair and a ramp with the same slope.

Different relationships between ramp and stair.

Making steps smaller.

Noise added into an analog signal is hard to separate out.

Noise added into a digital signal is easier to separate out.

A sine wave.

Adding together multiple sine waves for a more complex wave.

Increasing sample frequency produces a more accurate reconstruction.

Pages and sentences.

Sentences and words.

Cheat sheet and scratch pad.

Turing machine.

A finite process and an infinite process.

A name and the named person.

Gesturing instead of using a name.

Three different names for five.

The parts of an expression.

A two-way choice.

Multiple levels of choice.

A waits for B.

A cycle of waiting, A and B are deadlocked.

Six processes in a deadlock.

Different kinds of equality.

x and y are equal now and forever with the value 3.

x and y name the same mutable cell containing 3.

x and y name the same mutable cell, now containing 17.

x and y name different mutable cells, both containing 3.

x and y name different mutable cells with different values.

Two different interleavings of the same steps.

Four steps as the programmer sees them.

The same four steps, a possible execution.

The same four steps with some possible interrupt times.

A keyboard and its associated cell.

Typing the letter T

The boxes need to be stored in the available spaces.

One solution to the box storage problem.

Two virtual address spaces sharing one real address space.

Two processes sharing a single machine via an operating system.

Two operating systems sharing a single machine via a hypervisor.

Different processes in different operating systems on one machine.

An interplanetary game of Marco Polo.

Message ordering among 4 widely separated people.

Normal operation vs. failover.

Bad failover caused by lack of communication.

Unwanted duplicate copies caused by bad failover.

The user-facing and network-facing parts of a browser.

A hierarchy identifying some American locations.

The directory for com.

The directory for google.com.

Looking up www.google.com.

Using a cache for faster lookup.

High reliability, low availability.

High availability, low reliability.

The ideal: high reliability and high availability.

Cross section of vinyl record in use.

Cross section of optical disk (CD/DVD) in use.

Cross section of magnetic disk in use.

Different kinds of updating.

Writing stable storage.

Misled by average depth.

This hardly ever happens.

Combining diverse computations to produce a single result.

Are diverse computations valuable?

Two communicating endpoints and a network cloud.

Two communicating endpoints and various network devices.

BlueBox and RedBox are connected to the simple router.

Connecting the routers to form a simple internet.

The evolution of routing tables.

A quad.

Connecting networks with different routing mechanisms.

Three interconnected Autonomous Systems.

Spraying requests.

Three tiers between user and stored data.

Each tier may have a different numbers of servers.

A single request may have a complex path.

Serving global clients from a single site.

Serving global clients from multiple sites.

Compiler cc translates an ordinary program.

Compiler cc translates itself.

Compiler cc translates the operating system.

Compiler HC translates the operating system, naughtily.

Compiler H2C translates itself.

Compiler H2C translates cc, naughtily.

Key in shared-secret cryptography.

Keys in public-key cryptography.

Alice proves her identity to Bob.

A key distribution center (KDC).

Signing data.

Checking the validity of signed data.

Alice and Bob and ledger, starting state.

Alice and Bob and ledger, final state.

Whole-log signature, two-item log.

Whole-log signature, three-item log.

Altering the log while its unprotected.

Nested signatures, one-item log.

Nested signatures, two-item log.

Chained signatures, one-item log.

Chained signatures, two-item log.

Single-bit change in item 1 breaks signature 1.

Recomputed signature 1 breaks signature 2.

List of Tables

Some examples of how problem sizes grow with n

Reliability vs. Availability

Simple bit-doubling code: senders actions

Simple bit-doubling code: receivers actions

Preface

As a high school student in the late 1970s, I wrote an article for the school newspaper explaining what a personal computer could do. Among its other virtues, it could store recipes. That wasnt wrongit just doesnt seem like the first thing youd choose to say about a modern computer.

Back in those days, it was easy to perceive that something important was happening, but we couldnt quite see all the way to todays capabilities. Since we now have an abundance of devices and services using computers and communications, there is no longer any need to argue for the value of computers. Indeed, the challenge now is getting people to disconnect from their mobile phones, tablets, music players, and laptops long enough to discuss the merits of something else.

Alongside the evolution of computers from bizarre novelty to ubiquitous necessity, theres been a substantial amount of discovery and invention. In roughly the same way that it was once useful to explain what computers were, I think its now useful to explain something about the larger context of computer systems and infrastructure.