Week 1: Cryptographic and Distributed Computational Building Blocks

• :
  • Some bureaucracy and introductions.
  • Please send your instructor e-mail (at jonathan@poritz.net) with the following information:
    1. Your name.
    2. Your e-mail address.
    3. Your year at RU.
    4. What you intend to do after RU, in so far as you have an idea.
    5. Past computer science and math classes you've had.
    6. The reason you are taking this course.
    7. Anything else about you that you think I should know.
    17. [Optional:] The name of a good book you have read recently.
  • Some content we discussed, morning:
    • History of money.
    • What are desiderata for money?
      1. All units of money are fungible — that is, they can all be exchanged if they have the same value. No 1 bill has any more or less value than any other 1$ bill.
      2. it "represents value"
      3. Cash money maybe has some level of anonymity in its use.
      4. It is hard to counterfeit.
      5. It is hard to self-counterfeit, i.e., you cannot spend the same dollar more than once. To do so would be to double-spend, which we want to prevent.
      6. ...more desiderata later, particularly for electronic forms of money....
  • Morning programming project:
    1. You may program in C++ or Python — choose whichever you prefer.
    2. Form teams of 2-4 students who can work together and, in particular, are willing to work in the same language.
    3. Write and test code for simple communication over the Internet with sockets. This should result in programs Alice and Bob which can be run on separate machines, at separate IP addresses, and which take user input on both machines and turn it into discussion over the network.
    4. ...But: network issues made this difficult. However, hopefully a good start was made which will enable quick progress when those issues are resolved.
  • Some content we discussed, afternoon:
    • crypto terminology:
      • encrypt
      • decrypt
      • cleartext [plaintext], message space
      • ciphertext
      • key, key space
      • Caesar cipher, Vigenère cipher, one-time pad
    • these types of cryptosystems are called symmetric cryptosystems (because of the symmetry between the encryption key and the decryption key) and all raise the significant practical issue of key distribution
    • names of symmetric cryptosystems in wide use:
      • DES, the Data Encryption Standard, dating from the 1970s, accepted as a US Government standard in 1977, although developed by a mostly open process; now considered obsolete and insecure
      • for a while, people used 3DES ["triple-DES"] as a replacement
      • current standard is AES, the Advanced Encryption Standard
  • Afternoon programming project:
    1. Improve Alice and Bob by adding cryptography. That is, first get familiar with a crypto library — for symmetric/private-key crypto — in whichever language you are using. Then make sure that the network traffic between Alice and Bob is encrypted.
    2. This will require key generation and key sharing. Do the sharing in the following somewhat silly fashion: Have Alice generate the key and send it in the clear to Bob as their first message.
    3. Time permitting, write a third program Charlie, which will be on a third networked machine, to which Alice and Bob also open channels, that gets copies of all of their traffic and prints it to standard out.
    4. ...Because of our ongoing network issues, this mostly became a project in writing the code simply for encryption and decryption on a single machine. Again, hopefully we will be able to plug such a cryptosuite into other programs that do network communication, once our network problems are cleared up.
• :
  • Some content we discussed, morning:
    • more on symmetric crypto, particularly:
    • block vs stream ciphers
    • deterministic encryption
    • [cryptographic] salt
    • chosen-plaintext attacks
    • block-chaining to make the entire ciphertext change when a local change is made.
    • some on DES and AES ... the fact that symmetric crypto
  • Morning programming project:
    1. make three programs, in whichever environment you like:
       1. key_gen() to generate a key of whichever type is appropriate for the cryptosystem you are using
       2. <string> encrypt(<string> cleartext, <key-object> key) which outputs the ciphertext for a given cleartext and key
       3. <string> decrypt(<string> ciphertext, <key-object> key) which outputs the cleartext for a given ciphertext and key
       Do this for the Vigenère cryptosystem.
    2. Repeat the above for the AES cryptosystem — use a crypto library appropriate to Python or C++; see the suggestions on this page.
    3. Investigate whether the AES implementation of AES you use is deterministic or not. If it is deterministic, add some random salt yourself to make a non-deterministic version yourself.
  • Some content we discussed, afternoon:
    • intro to asymmetric crypto, particularly:
    • general idea of asymmetric [or public-key] cryptosystem
    • a feasible algorithm [function], i.e., one which can be computed in an amount of time which is bounded by a polynomial function of the
    • [cryptographic] one-way functions
    • RSA uses the one-way function multiplication, whose inverse is
  • Afternoon programming project:
    1. Add a version to this morning's cryptosuite which uses the RSA primitives in an open library (for the programming language of your choice).
    2. Send jonathan@poritz.net a message encrypted with the public key to be found here.
• :
  • Some content we discussed, morning:
    • block cipher chaining modes and the role of the IV
    • getting digital signatures from an asymmetric cryptosystem
    • some practicalities of asymmetric cryptosystems (and, therefore, digital signature systems):
      1. protection against the man-in-the-middle attack: certificates
      2. keyservers
      3. web of trust and key signing parties
      4. the importance of key security — so, e.g. use a secure operating system, always use full disk encryption, etc.
      5. the importance of good randomness [e.g., we should all really use a system like Diceware]
      6. GnuPG
      7. OpenPGP
      8. Mailvelope.com
      9. Enigmail.
  • Morning programming project:
    1. use your RSA code from yesterday afternoon to build a digital signature system, which has the two functions:
       1. <string> sign(<string> message, <key-object> key) which outputs the signature with respect to the given [private] key on the given message
       2. <bool> verify(<string> message, <string> signature, <string> key) which tells if the given signature is valid for the given key on the given message
    2. [time permitting] install some of the practical tools mentioned in lecture today and send your instructor your [public, of course!] key to be posted on this website, then sign documents or emails, download each other's keys and verify each other's signatures, and send each other encrypted emails
  • Some content we discussed, afternoon:
    • [cryptographic] hash function
    • some history of hash functions
    • the Merkle-Damgârd construction
    • uses of hash functions:
      1. for shorter digital signatures
      2. for protected data structures like a block chain
      3. the idea of so-called "trusted" computing
      4. for proof of work
    • formal desiderata for cryptographic hash functions:
      1. ease of computation: computing $H(x)$ is feasible (recall that means its computation time is bounded by a polynomial function of the input size)
      2. pre-image resistance: given a value $t$, it is infeasible to find an $m$ such that $H(m)=t$.
      3. second pre-image resistance: given a value $m_1$, it is infeasible to find another $m_2$ such that $H(m_2)=H(m_1)$.
      4. collision resistance: it is infeasible to find two inputs (messages) $m_1$ and $m_2$ such that $H(m_1)=H(m_2)$.
      5. hiding: if $r$ is chosen from a distribution which has high min-entropy, then it is infeasible to find $x$ given $H(r+x)$.
      6. puzzle-friendliness: given any $t$ of bit length $n$, if $k$ is chosen from a distribution with high min-entropy, then it is infeasible to find $x$ such that $H(k+x)=t$ in time which is subexponential in $n$.
  • Afternoon programming project:
    1. get a hash function working from a standard crypto library: it should take as [byte or character] string as input and produce a fixed-size hash
    2. set up a proof of work:
       1. run your hash function many times on a many 256 bit inputs (use the output each time as the next input, or increment the input, as a 256-bit integer), in order to estimate how long it takes your computer to compute each individual SHA256.
       2. make a program <128-long bit string> <void> work(<128-long bit string> prefix, <int> len) which returns a bit string which when appended to the given prefix and used as input to SHA256 produces an output whose last len bits are all 0.
       3. using the first result above, figure out how big a len you need to require in order to make a proof of work that takes 10 minutes
• :
  • Some content we discussed, morning:
    • Commitment schemes. Alice wants to be able to make a public assertion of some message $m$ ... but without telling the message. At least, she wants to make a public statement that others can see but which doesn't reveal the message $m$ to which she is committing, but then later she can make another public statement which reveals the original message as well as proves that her previous commitment was indeed to that message $m$.
      • The scheme should be hiding in the sense that Alice's public statement during the commit phase reveals no information about the message $m$.
      • It should also be binding in the sense that it is not feasible for Alice to make public data during the reveal phase which would seem to work for any verifier Bob but which would be for a different message $m^\prime$ from the one to which she first was supposed to be committing.
      Here is one way to make a commitment scheme for a message $m$ out of a cryptographic hash function $h$:
      1. Alice picks a fairly large random nonce $r$, computes the value $c=h(m+r)$ (where "${}+{}$" is concatenation), and publishes $c$.
      2. To reveal, Alice publishes $m$ and $r$. Bob can check that Alice was not lying about her commitment to $m$ by seeing if $c==h(m+r)$.
    • Flipping a coin over the Internet. That is, Alice and Bob want to run (honestly!) a protocol which produces a shared random boolean value, which neither of them can force to have one value or even simply predict. Here is a simple way to do this:
      1. Alice randomly and privately picks a bit $b_A$.
      2. Bob randomly and privately picks a bit $b_B$.
      3. Alice runs the commit algorithm (from immediately above) with message "$b_A$" and gives Bob the public commitment.
      4. Bob runs the commit algorithm with message "$b_B$" and gives Alice the public commitment.
      5. Both Alice and Bob run the reveal on their previous commitment.
      6. The shared random coin is $b_A\oplus b_B$ ("${}\oplus{}$ here is addition mod 2 or, equivalently, XOR")
      Here is a famous early description of a different shared random coin protocol.
    • Leader election.
    • Threshold cryptology: Suppose Alice wants to communicate with Bob using asymmetric crypto, but actually the role of Bob is being played by a collection of agents Bob₁, ..., Bob_n. All of the Bobs could share the same public/private key pair and Alice could send the same message to all of them, or they could all have their own pairs, and she could send a message to the group which has versions for each Bob. But suppose she doesn't trust the individual Bobs to do the right thing, so she wants to send a message which has the property that it can only be decrypted when at least $k$ of the Bobs (but any group of $k$ Bobs!) work together on the decryption, where $k$ is some integer satisfying $1\le k\le n$.
      Such a thing would be called a $(k,n)$ threshold cryptosystem. What follows is a very naive, inefficient way to implement such a thing in the case $k=2$:
      1. The key_gen() consists of every Bob running his own, independent key_gen() for some asymmetric cryptosystem they all like. The group public key will consist of all of their respective public keys, published together; call them $\{(k^1_e,k^2_d),\dots,(k^n_e,k^n_d)\}$, where $(k^i_e,k^i_d)$ is the key pair for Bob_i.
      2. The encrypt Alice runs on message $m$ consists of
         1. She picks as a nonce a random key $r$ for some fixed symmetric cryptosystem such as AES.
         2. She encrypts her message $m$ under that chosen symmetric cryptosystem with that key, getting ciphertext $c$.
         3. For all $i$ and $j$ satisfying $1\le i<j\le n$, she computes $r_{ij}=e_{k^i_e}(e_{k^j_e}(r))$.
         4. Alice's encrypted message consists of the concatenation of $c$ and all of these $r_{ij}$s.
      3. The decrypt operation goes like this:
         1. Every correctly operating Bob_i decrypts each $r_{ij}$ with his $k^i_d$, for all other values $j$ satisfying $1\le j\le n$ and $j>i$, and sends it to the respective Bob_i.
         2. Any Bob_j with $j>i$ will have received some $d_{k^i_d}(r_{ij})=e_{k^i_e}(e_{k^j_e}(r))=e_{k^j_e}(r)$ and can compute $d_{k^j_d}(e_{k^j_e}(r))=r$, and can therefore use this $r$ to decrypt the $c$ and send the resulting cleartext $m$ to all the other Bobs.
      It should be fairly clear how to generalize this to larger values of $k$. See also, e.g., this explanation for a much more efficient scheme than the one described here.
  • Morning or afternoon programming project: Please do the following tasks, in any order, between this morning and this afternoon
    1. Write a UDP reflection server which will be run on a wired server on campus. It should take two integers as input, to tell the port numbers it will reflect from and to. It will then run as long as it can, redirecting the incoming UDP datagrams from the input to output ports.
       Actually, while it it slightly less appropriate from the point of view of the kinds of protocols we will run in this course, you could also use TCP, if you prefer. Make at least one of your programs from earlier this week work (test it, show it off!) between two different laptops in the classroom, by using the reflection server. [Actually, Ragnar points out that this description in terms of in and out ports is a bit inappropriate, since probably there will be bi-directional communications going on over these ports. It would be better to think of the ports as associated with roles, so one could be called Alice and the other Bob, for example.]
    2. Write programs which flips a coin over the Internet: two programs which talk to each other (best would be over the reflection server, but you could test on only one machine first, if your reflection server is not ready) and come to a shared, random coin.
    3. Make your proof-of-work program from yesterday accept input over the network, by accepting the prefix and len inputs over the net and replying with the winning suffix back over the net. The other end of the connection should have a user interface which takes those inputs from the terminal and sends them to the computational client on the other end of the network connection, and when it gets the response back, it checks that the suffix does indeed solve the desired problem.
       Tomorrow, we should run a race, where a prefix and len are announced, and we see which team gets the response
  • Some content we discussed, afternoon: Some background on theoretical understanding of distributed systems.
    • a distributed system is a model with nodes that can perform computations and that are on a network through which they can exchange messages.
    • Different things may go wrong with a distributed system: crashes and network latency are just slowing down nodes and links, but there can also be network corruption and either accidental or malicious failure of nodes to follow protocols. One makes particular models and assumptions for these particular cases.
    • A major goal — clearly something very desirable for data and protocols which are to represent currency — is that all of the nodes execute the same instructions, in the same order.
    • ...more on basic definitions from the theory of distributed systems will appear in the near future in this space...
  • Afternoon programming project:
    1. Continue with the morning work; see above.
    2. Think about — and write down! — a threshold signature scheme where signatures are produced by a committee but can be checked by anyone on the Internet. Design a scheme whereby $k$ out of the $n$ Bobs must work together in order for the Bob group to produce a valid signature. [Hint: this could be a matter of simply running the above-described threshold cryptosystem backward.]
• :
  • Some content we discussed, morning:
    • some basic definitions and notation from the number theory which is so often used in crypto reviewed here; see Yet Another Introductory Number Theory Textbook, for example. a list of the terms we
  • Morning programming project:
    1. Make sure your proof-of-work code is ready for the race this afternoon, running with Ragnar's race monitor server.
    2. If that is done, write a program which computes the inverse mod $n$ <int> inv(<int> a, <int> n) of an input $a$, using the Extended Euclidean Algorithm (for which, see Yet Another Introductory Number Theory Textbook, among many other references) — particularly if you have never programmed the EAA before. If you have, instead skip to:
    3. Implement a fast modular exponentiator, whose output <int> power(<int> g, <int> k, <int> n) is $g^k\mod{n}$.
  • Jumping right into the Afternoon programming project:
    1. A competition for fastest proof-of-work implementation: Fabulous prizes offered — at least one satoshi!!

Week 2: [Starting a] Deep Dive into Electronic Currencies

• :
  • Some content we discussed, morning (M118):
    • Some discussion of projects, structure of the rest of the course, then...
    • First try at an electronic currency.
    • Since electronic data is easy to copy, the issues are to avoid theft, printing [creation] of too much money, and double-spending.
    • For the first try, it is fairly easy to solve two out of these three by using a trusted third party [TTP]. Think of this as the bank or the government.
    • [After all, most of today's non-electronic currencies are based not on the values of something like gold — those were commodity currencies — but instead simply on the users' faith in the power of their governments — these are fiat currencies, so called because it is the exercise of arbitrary power which creates and maintains them, like the power of the deity in the Judeo-Christian tradition, who supposed said "Fiat lux" (in the Latin version) and made light in a previously dark universe.]
    • Let's make a very naive currency based on an all-powerful central bank.
  • Morning programming project:
    1. Write code to implement an extremely naive electronic currency based on an all-powerful trusted third party, Big Brother Bob, who keeps track of the money owned by individuals. Here are parameters:
       • BBB starts with a config file containing a list of customer identities and how many BigBucks [BB\$s] they start out with.
       • BBB will be a process which listens to terminal input and, when asked, creates an output file in the same format as the config file, saying how much each customer currently has in the bank. The idea is that this file can be saved when the bank is turned off and then used when the economy starts again the next morning.
       • Another thing BBB can do, upon request, is dump (on the terminal) a list of all transactions it has seen that session. Possibly this could take options in the form of restricting to a dump of all transactions to, or from, a particular client.
       • In additon, BBB will listen to a particular port and service payment requests. These will come from a particular client which declares its ID, the amount to paid, the payee ID, and so on.
       • Each customer will be another process, which communicates with BBB by talking to the port on which BBB listens. Customers can issue two kinds of requests to BBB:
         1. A payment authorization or the form I am customer with ID $I$, start a transfer of BB\$$x$ to ID $J$. This should return either false if the payer does not have sufficient funds, or a unique transaction ID $t$ if successful.
         2. A payment verification of the form I am customer with ID $J$, did ID $I$ transfer BB\$$x$ to me in transaction with transaction ID $t$? which returns a boolean.
       • Customer behavior will be decided by listening to keyboard input, in which the user specifies to each customer when to send how much and to whom (presumably, this is a client at a store, paying for a good or service), and to check if that money has been transferred (presumably upon the successful transfer of money, the good or service will be delivered).
  • Some content we discussed, afternoon (M118):
    • We can add some security and privacy to even the incredibly naive TTP protocol, but using asymmetric crypto. Everyone needs to make a key pair at the beginning, and then:
      • Every communication from part X to Y (where both X and Y can be clients, and one could be the TTP), should be encrypted under the recipient's public key, for privacy, and signed with the sender's private key, for authentication.
    • It makes sense when doing this type of TTP-based protocol, to use the public key of a client (or, for a shorter alternative, the hash of the public) as client ID.
    • Adding the above encryption and authentication prevents:
      • theft no one can use the money in the account with the TTP associated with some client ID.
      • counterfeiting: no one will be able to use — create transactions that others will accept in the real world — this currency except for those who have a valid client ID and have in their account with the TTP at least the amount they are promising to pay in the transaction
      • double-spending: no client is able to spend "the same" currency units twice, the TTP will not authorize more payments than the total amount in the clients account.
    • What, then, are the problems with this approach? Here are a few:
      • Big Brother is watching: The TTP knows everything: how much each client has in their account, who they paid, how much, and when. This is perhaps a privacy concern...?
      • Big Brother is in charge: The TTP can, in this model, prevent someone from using their money, or another person from ever getting paid. The TTP can move money around their accounts (basically by answering pay requests and payment verification requests as if money were in different amounts in different accounts from what the clients think). The TTP can increase or decrease the total money supply, in a similar way.
      • Big Brother is one: The TTP is a single point of failure, without which the entire economy comes to a complete halt.
      However, if the trust in the TTP is justified — so it doesn't watch or take charge — then the protection against counterfeiting and double-spending makes for a fairly reasonable system.
    • After all, the algorithm just described is essentially what credit card companies and the inter-banking electronic fund transfer system use.
  • Afternoon programming project:
    1. Implement the asymmetric crypto-enable version of Big Brother Cash. That is:,
       • The set-up phase must include asymmetric key pair generation for every participant.
       • Clients need to sign and encrypt all of their communications.
       • All receivers of message must decrypt them and check their signatures.
• :
  • Some content we discussed, morning (M113):
    • What are IDs in our system? To play in the economy game, as we have started to define and code it, a player's ID is their public key. We may have broken the direct connection in code, but there is no need to: we may as well use
    • Electronic currency systems such as the one we are building are not anonymous, they are pseudonymous. This has some privacy protections, but they are not really so good, in the end, because long-term pseudonyms can be correlated with real-world identities fairly easily. And how long that "long-term" has to be turns out to be far shorter than one might first imagine.
    • One way to increase the anonymity given by pseudonyms is to allow easy creation of new pseudoynms.
    • Many new pseudonyms are even more useful, if payments can be made mixing many small pieces of input and output. For this reason, we should allow a good electronic currency to be finely [but not infinitely] divisible, and transactions should be allowed to have multiple inputs and outputs.
    • ...Although we don't want to make possible so much anonymity in our electronic currency system that it actually encourages use as a money-laundering system.
  • Morning programming project:
    1. Finish polishing/debugging code from yesterday.
    2. Refactor (#1 for today): make sure your client IDs are the hashes of the client's public key, everywhere in your code and data structures.
    3. Functionality increase (#1 for today): Design and implement a new command for the Big Brother Bank: new_client which creates a new bank client. It should take the public key of the new identity, create an account for that client which starts with BB\$0, and return a boolean indicating the success of the operation. [E.g.,, creation should fail if that ID already exists.]
    4. Functionality increase (#2 for today): Expand the payment authorization to allow multiple input and multiple output accounts. Correspondingly change the payment verification to take only one client ID, a transaction ID, and a number BB\$ as input, and to return a boolean telling of that transaction resulted in a payment of that number of BB\$s to that client ID.
  • Current snapshot of BigBrotherBucks economic system interface:
    • Two types of actors:
      1. the main server, a trusted third party we shall call the Big Brother Bank [BBB] which maintains state and authorizes all payments.
      2. a arbitrary number of clients which issue payment orders and/or payment verification requests, both to the BBB
      Every actor has an asymmetric cryptosystem key pair. A client's ID is the hash of its public key.
    • BBB accepts the following requests:
      • bool new_client(public_key key)
        which takes a public key and creates a new account, starting with BB\$0, for the client whose ID is the hash of key. Returns false if there already exists a client with that ID, otherwise true.

      • transactionID authorize(int n, int m,
                                ID in1, int x1, ..., ID inn, int xn,
                                ID out1, int y1, ..., ID outm, int ym,
                                sig s1, ..., sig sn)

        which checks if the multi-input and -output transaction is valid, and, if so, performs the corresponding deductions from input accounts and deposits to output accounts, and returns a new, unique transactionID, otherwise returns null.

        A proposed transaction is valid if

        • all of the IDs in1, ..., inn, out1, ..., outm are recognized client IDs,
        • x1+...+xn = y1+...+ym (so total input of BB\$s equals total output),
        • for all j in the range 1≤j≤n, sj is a valid signature on the concatenation of the byte representations of n, m, in1, x1, ..., inn, xn, out1, y1, ..., outm, ym
        • for all j in the range 1≤j≤n, xj is no more than the amount the BBB has in the account for inj.
      • bool verify(ID out, int x, transactionID t) which returns true if the transaction with the given transactionID resulted in a payment of BB\$x to the client ID out.
    • Every communication from a client C to another entity E should be encrypted with E's public key, signed with C's private key, and then have C's ID prepended to the message before it is transmitted. All message recipients should check the signatures on their messages and flag an error if it does not verify.
    • Every communication from BBB to a client should behave like communications from a client, except it doesn't need to prepend its ID.
  • Some content we discussed, afternoon (M118):
    • Trusted Third Parties might make us nervous, in certain circumstances, so much of the cryptocurrency literature is about preserving the security and privacy guarantees of the protocol from yesterday afternoon, but without giving over the control to a TTP.
    • The ideas is to replace the TTP with a shared, authenticated data structure that contains a history of all transactions that have been accepted so far.
    • We have a good candidate for this data structure: a block chain. That is, it will be a linked list, where each data block contains a hash pointer to the previous block. Hash pointers are references to other blocks not by the location (in memory or somehow), but instead by the hash of that other block.
    • In particular, we can start by requiring the TTP to keep a block chain of all the transactions it has accepted. This would then be available to auditing -- preventing (some kinds of) malicious acts on the part of the TTP, such as creating new money or inappropriately giving money to, or taking it away from, some individuals.
    • Block chains all have a genesis block, the first block everyone has. It is important that everyone who wants to work with a block chain has a copy of the genesis block (or at least its hash). The hash pointer in the genesis block should be some special value, to indicate that it doesn't point to some other block.
  • Afternoon programming project:
    1. BBB should keep a block chain of all valid transactions and have a new method audit.
    2. Specifically, the genesis block of this BB\$ system should have a special transaction, which would be illegal in any other circumstance. It should have zero inputs and one output, which will be the hash of one basic identity which is built into the whole system. For our BB\$ example, please use a public key you keep for the founder's ID, a particular one you build when you build your software. The special transaction in the genesis block should put BB\$1,000,000 into the account. Then this account can move various amounts into other accounts as you create them, and this will be easy for you to do since you have the private key to sign such transactions.
    3. Next, when BBB receives valid transaction requests from clients who have BB\$ in the system, it should add a block to the block chain for each such transaction, which contains all of the information about the transaction. In particular, it should have all of the inputs to the authorize method, in the same order. Preceding that information, should be a hash pointer, being the hash of the entire previous block (including its hash pointer, in turn).
    4. The hash pointer in the genesis block of this BBB block chain should have a special, recognizable value. How about using the value 17?
    5. Note that if you keep block chain blocks in a database, then the keys can be the values of the hash pointers and the associated data will be the block as described above. If, instead, you are keeping the block chain in memory, you will an actual pointer to the previous block, in addition to the hash pointer, which is just the hash of that previous block. Do be sure not to include the physical (RAM) pointer when you hash a block to make a hash pointer to it -- that would be implementation and process dependent, while we want the block chain to be independent of such details.
    6. The audit method needs to traverse the entire block chain, making sure that every transaction makes sense and is valid, and that all coins come from that original supply created in the genesis block.
• :
  • Some content we discussed, morning (M118):
    • Discussion of the meaning of the condition imposed (too casually, perhaps!) yesterday that for all transactions, sum of inputs equals sum of outputs.
    • With this insight, we conclude that anyone can verify the block chain. In short, what need is there, really, of the TTP?
    • We will discuss later how to agree upon the contents of the block chain, but if there is a globally agreed version of that data structure, all of the other work can be done by the clients!
    • Note, we will no longer encrypt all communications — although we will still sign them to indicate approval of proposed transactions — which decreases some of our privacy, but the hope is that the amount of anonymity provided by operating in this economy via public keys as IDs will be enough.
    • Let's make a new protocol, a new currency in which the judgement, evaluation, and authorization roles of the Big Brother Bank are almost entirely gone — we're really going to use the central bank, in this version, as the holder of the block chain; later, we'll replicate it across all participants, completely removing the TTP, at which point we will have the problem of making sure it is globally consistent.

      Let's call this next version of our toy electronic economy Block Chain Bucks [BCB with currency denoted BC\$]. It will have a central server, the Block Chain Bank [BCB] which maintains the transaction block chain, manages insertions to that chain, and responds to queries about the success of transactions which are on the chain.

      BCB should maintain a valid block chain which has one transaction per block. The validity conditions are as follows:

      1. For the genesis block, the hash pointer to the previous block is the special value 17, the list of participant IDs contains just the founder's ID, with input value BC\$0 and output value of the total size of the BCB economy, say BC\$1000000, and no signature. This block is declared to be valid, as a special case of the block verification code.
      2. Non-genesis blocks have the following fields:
         • A hash value, the hash pointer to the previous block. [Remember, this is just the hash of that previous block. You can then use it as a key in a database look-up or Python dictionary (or Perl "hash") to get the value, which is that entire previous block — including that previous block's own hash pointer to its previous block! Or, if you are storing the block chain in some other way, you will need an additional pointer (to an address in RAM, for example) to the previous block, which, however, should not be part of the official data of the block used to make the hash point in the next block.]
         • An int field, specifying the number n of participants in the transaction.
         • A list ID1, ..., IDn of the IDs, of clients involved in this transaction.
         • A list start1, ..., startn, end1, ..., endn, of ints, being the input and output BC\$ values owned by each ID involved in the transaction, meaning that each IDj owned startj BC\$ just before the transaction and owns endj BC\$ just after the transaction.
           For validity, we require that start1 + ... + startn = end1 + ... + endn and that none of the values of the startj or endj are negative.
           The expectation is that for all j, endj≠startj, although that is not actually required. [Having an IDj which did not change values of BC\$s, so endj = startj, would mean that the actor IDj approved of the transaction, even if she didn't have a direct financial stake it it — maybe this was the guardian of a minor involved in a transaction, who needed to sign off on the transaction, for example.]
         • A list s1, ..., sn of signatures, where sj is the signature under IDj's private key of the concatenation of the bytes for n, ID1, ..., IDn, (end1-start1), ..., (endn-startn).
      3. Between blocks we require that: in a transaction $T$, for each starting value startj corresponding to an identity IDj, the ending value endk in the most recent transaction before $T$ where for some k, the identity IDk in that past transaction was the same as IDj in $T$, satisfies endk=startj. [Meaning that the number of BB\$ doesn't change between successive valid blocks in which it is a transaction participant.] If there is no previous such transaction in which the identity IDj appears, then this startj must be 0. [Meaning that new identities start with BC\$0.]

      Note that, as we have designed the transaction block chain here, the current number of BB\$ owned by some actor is the value of endj for the most recent transaction on the block chain for which that actor's ID is one of the ones in the transaction, say it is IDj.

      BCB will still have a central bank, which we will call the Block Chain Bank [BCBa]. When it starts, it will make a founder's ID and create the genesis block. After that, it will handle the following requests:

      • bool new_client(public_key key)
        which learns the public key of a new actor in the BCB system, whose ID will be the hash of the public key. The key itself must be recorded, so that future signatures from this identity can be verified.
        Returns false if there already exists an actor with that ID, otherwise true.

      • hashval authorize(int n,
                          hashval ID1, ..., hashval IDn,
                          int Δ1, ..., int Δn,
                          sig s1, ..., sig sn)

        which checks if the multi-input and -output transaction is valid, and, if so, returns the hash of the corresponding block chain transaction block; otherwise returns null.

        A new block chain block is created as follows:

        1. Start with the n of the authorize call.
        2. Next, for each j in the range from 1 to r, do the following:
           • Find the most recent transaction block on the block chain which has IDj as an involved ID, say it was block $B$.
           • If there is no such transaction (so, this is the first time that identity appears in the block chain), set startj=0.
           • Use the end value for IDj in that block $B$ as the value of startj.
           • Set endj=startj+Δj.
        3. Add start1, ..., startn, end1, ..., endn, sig1, ..., sign to the new block.
        4. Also add the hash pointer to the previous block.
        Then all the tests for the validity of the block chain, with this new block, are performed. If any fail, discard this new block and return from the authorize with value false, otherwise accept this block as the new end of the block chain and return with value true.
      • bool verify(ID out, int x, transactionID t) which returns true if the transaction with the given transactionID resulted in a payment of BB\$x to the client ID out.
  • Morning programming project:
    1. Implement the BCB system described above. Reuse as much code as you can!
  • Some content we discussed, afternoon (M118):
    • A valid block chain can be distributed to all players in this economy, with some reduction in anonymity, perhaps, but its internal structure still prevents counterfeiting and stealing (so long as users keep their private keys secure). Double-spending will also be prevented by making sure there is a global consensus algorithm running which recognizes a single, valid version of the block chain, replicated on everyone's machines.
    • The way this is done is that some players, called miners look for a nonce to add to each block which will make the hash of the whole block+nonce have a certain number of trailing zeros — it is proof of work of the kind we have seen before.
    • The difficulty level is chosen so that globally, only about one block is accepted every ten minutes. This means that it is very hard for two versions of the block chain to grow very far, even on widely separated network nodes, as a bad actor must convince people to make happen, if that actor wants to double-spend some coins.
    • To encourage people to do this mining work, the winner of the proof of work contest for any block which gets onto the global block chain can be the recipient of a new kind of transaction added to the blocks which creates some mining reward coins out of thin air (so, this reward transaction has no input, just output).
    • Note that in the Bitcoin protocol, blocks do not consist of a single transaction, but instead they are a Merkle tree of transactions which individual users want to get recognized and have therefore broadcast to the whole Bitcoin network.
    • Note also that Bitcoin has specific parts of its protocol designed to adapt the level of difficulty required in the proof of work so that it continues to take ten minutes, on average, for the global pool of miners to authorize a new block. The Bitcoin protocol also reduces (by half) the mining reward every so many blocks. However, there is also a mechanism for transactions to include a small transaction fee (in Bitcoin, of course!) which is credited to whoever is the winning miner.
    • We will not implement this distributed block chain with incentivized mining today.
  • Afternoon programming project:
    1. Surely, this will simply be a continuation of the morning's work on implementation of the BCB system.
• :
  • Today was mostly a catch-up day on our projects for an implementation of a block chain-based cryptocurrency ... although the version we are implement does not have a Bitcoin-like proof-of-work consensus algorithm. Instead, we are putting the maintenance of the transaction block chain in the hands of a third party. We have three versions of that project, as follows:
  • v0: This was what was described on the whiteboard in class yesterday. Some things were not completely specified or worked out.
  • v1: This was a more complete specification, detailed above in yesterday's (Wednesday's) morning discussion description.
    Truth to tell, even that description is missing a complete description of how public keys are distributed, but students can choose their own approach to this. Three obvious choices would be:
    1. Make all identities as part of initialization, distribute the corresponding public keys by hand. This is a little inelegant, but emulating the broadcasting of identities that real cryptocurrencies use is a communication-related task we are trying to avoid.
    2. Add functionality to the central server (the bank BCBa): it already is supposed to take a call of the form new_client(public_key key) which established a new ID. It could also take a call of the form get_public_key(hashval ID) which takes an ID as input and returns the associated public key. This seems to put more power in the hands of the bank, which is what we are trying to move away from, but really BCBa is coming to play more or less the role only of the network (handling communications, consensus, etc.)
    3. Simply tack on to the end of the transaction record the needed public keys. While this would be effective and easy to do, it violates a fundamental design stance with respect to public key crypto: do not distribute the keys in the same way that they are used. To do so is to design in the largest possible vulnerability to a man-in-the-middle attack
  • v2: The final version of BlockChainBucks should reduced the role of the bank to be merely that of creating, maintaining, and distributing the block chain while the clients will do their own proposals (to the bank) of new block chain blocks, maintenance of a local copy of the block chain, and use of the block chain itself to contain transaction authorizations, on the payer side, and verifications, on the payee side. Here is a little more detail:
    • On start-up, the BCBa and all clients will each have a copy of the genesis block, and therefore know its hash pointer.
    • The BCBa will service the following requests:
      • bool new_client(public_key key) registers a new identity with the BC network, returns either the corresponding ID (which is a hashval) or null if this public key has already been registered.
      • public_key get_public_key(hashval ID) returns the public key of a registered client with the given ID, or null if that ID is not recognized.
      • hasval get_current_chain_tail_pointer() returns the hash pointer of the current tail of the block chain.
      • block_data get_block(hashval pointer) returns the contents of the block with the given hash pointer, or null if the pointer is not recognized.
      • bool put_block(block_data block) sees if the given block would make a valid block chain if it were appended to the block chain (checking the conditions described above in yesterday's discussion and that the hash pointer in this new block points to the current last block on the block chain) and, if so, adding it there.
    • Clients now will start by registering themselves with a new_client call. Then, when acting as a payer, they will
      • First make sure they have an up-to-date copy of the block chain, and that it is valid.
      • Next, they will build a valid block which would describe the proposed transaction. Note that validity is based on knowledge of the current state of the block chain, and thus can fail asynchronously, if another client gets a change in to the block chain with this client is processing.
      • They will issue a put_block with this new proposed block. If it fails, repeat the construction and put_block until it succeeds. Upon success, a hash pointer to this block can be sent to the payee in the role of a transaction ID.
    • When clients act as a payee, they will
      • First make sure they have an up-to-date copy of the block chain, and that it is valid.
      • Make sure that the block whose transaction ID was sent by the payer is indeed now on the block chain.
      • If not, wait and then try again. (Or fail, and notify the payer that this transaction was not accepted?)
      • Test that block to see if it does indeed encode the desired transaction. If so, return success.
    • When a client wants to update its view of the block chain, it would
      1. Do get_current_chain_tail_pointer() and see if it is equal to that client's view of its current chain tail.
      2. If so, terminate.
      3. If not, repeatedly do get_block, starting with that newer BCBa version of the block chain tail pointer and ending when the newly acquired block's hash pointer to the previous block is pointing to the client's pre-update version of the hash pointer to the current block chain tail.
    • This then should be a version of a cryptocurrency which does everything that real such currencies do, except for maintaining the consensus transaction block chain.
• :
  • Some content we discussed, morning (M209):
    • More discussion of proof-of-work approaches to block chain consensus. In particular, discussion of the design of the example such program on which you will start working this morning.
  • Morning programming project:
    1. Program the proof-of-work block-chain consensus for an on-line collaborative counter. The goal here is to have a number of peers competing to contribute to a block chain whose data blob contains only their name and an integer which is larger than the value in the last block on the consensus block chain.
    2. A valid block will have
       • a hash pointer to the previous block of the chain
       • a string field for a comment or the name of the proposer
       • a timestamp, in the form of milliseconds since the Unix epoch (which was the start of 1 January 1970)
       • a counter value, which must be larger than the value in previous block of the chain
       • a target difficulty level, which should either be fixed by everywhere in your code, or, for your amusement, you can try various ways that the difficulty level might change in response to information available at the time of block creation, such as its counter value, the timestamp, or the differences between time stamps of some blocks, etc.
       • a nonce which, when concatenated with the rest of the block data, yields a has which has the target difficulty level's worth of 0s at the end (or beginning, if you prefer) of the hash value
    3. To get started, execution should go as follows:
       • Individual clients should, at any given time, have a local view of the block chain. They would spend most of their time trying to find the nonce to make a valid next block on that chain.
       • If, while doing that work, client A receives a notification that client B has extended the block chain, then A should stop its current search, update its view of the block chain, and start the search over again for a valid next block.
       • If client A does successfully complete the search, finding a winning nonce, it updates its own block chain and transmits copies of that block to all other running clients.
    4. There seems to be concurrency going on here. It is up to you how you will do it. Here are some possibilities:
       • If you are very comfortable with sockets, you could have separate clients running on separate machines and communicating with each other over the network (we can run a reflection server for you to avoid the packet filtering happening in the local wifi network, if you need it). Then each machine would have its own processes and variables or databases or whatever you use to store the block chain.
         • Note: there is still a small concurrency issue happening in this "separate clients on separate machines" version, since we want a process to be interrupted by other processes, potentially, when they are faster in getting to the next valid block.
       • You could run everything as separate processes on one machine, leaving the operating system to interleave execution. you then have the issue of inter-process communication. One way to handle that would be to put messages that are to be thought of as being broadcast by one client to all other into some file. Perhaps then each client has to lock this file before writing to it.
         • There is still the issue of how processes notify each other of their personal success. Implicitly, we are assuming that when a process does so, it interrupts the other running processes, which you have to figure out how to do in this model.
       • Lastly, you could do this all within one process, by using threading (in Python) or forking (in C++). Then inter-process communication is done by variables held in common between different threads, although there is still the question of when and how one thread can notify another thread of something asynchronously.
       By the way, a cheap way to avoid the scary issue of having separate clients interrupt each other for notifications would be to have each client go its merry way as if it were alone, but it could check some sort of semaphore for status change once every 1000 times (or whatever number you like) through its main proof-of-work loop. Using this cheap way of avoiding many problems with asynchrony still means that you would probably need a locking mechanism for updating the semaphore or at least other, larger blocks of data shared between processes.
    5. What are the failure modes of this approach?
       Add code which catches these failures and run until you get one.
       See how varying all available parameters changes the frequency of those failures you can catch.
       
    6. The long run would be to write a version which handles all potential failures gracefully, using the cryptocurrency-like approach of growing separate, valid local copies of the block chain and always abandoning a local branch in favor of one being created by a peer if that peer's branch is longer than your own.
  • Afternoon (M209):
    • Almost certainly there will be a lot more to do to finish the morning's project.
    • A good "finished" version of this project, or of any other programming project for this course, should follow the guidelines outlined below of what it means for a project to be done.

Week 3: Extensions, Practicalities, and Student Presentations

• :
  • We're in M113 all day today.
  • Mostly today is a work day for presentations. Make sure you have done and understood the readings for your topic, worked out with the rest of your team what you want to say and who will say it, and have thought of (and implemented, if necessary) the technical demo of your topic, or other highly detailed technical content which will be part of your presentation. Make notes, slides, handouts, etc., as appropriate.
  • If the presentation is in a very good state, you can spend some time finishing/polishing the projects from earlier in this course. In particular, a project is done if:
    • The code is clean — debugged!! — and at has at least some comments and/or documentation.
    • Instructions are provided for how to configure, install, and operate your code.
    • Whatever is necessary for another person (your instructor or, let's say, another Trusted Third Party) to run the code through some examples, which show its functionality and robustness against easy errors or attacks, is provided.
    • All of the above is sent to your instructor.
  • Some new content we discussed in the morning:
    • The issue of keeping cryptocurrencies democratic: Nakamoto, in the original paper proposing the Bitcoin protocol, said that

      Proof-of-work is essentially one-CPU-one-vote.

      This has been a value of the cryptocurrency community since the beginning, akin to the centrality of idea of decentralization (if you will forgive the pun) authority, rejecting TTPs. The fear is, however, that big players will be able to make the large up-front investment necessary to create and install large quantities of application-specific integrated circuits [ASICs] — special chips which can run through potential nonces for the SHA-based proof-of-work faster than anyone else can on a general-purpose CPU or even GPU adapted for mining.
    • Note that this fear is not merely theoretical: it is known that large (profitable) mining operations do use ASICs
    • One approach to keeping a cryptocurrency democratic is to find a way to make up-front investments less valuable. Two methods which have been tried are:
      • Memory-driven proofs-of-work: The idea here is that memory is already a mature hardware technology and everyone has equal access to the best memory chips. So a proof of work whose cost was driven by memory would be available to all investors equally. An example of this would be to use as a new hash function in the proof of work something that is basically SHA, but employed in such a way that pre-computing many values would give great advantage. As a consequence, the main cost of computing this function would be driven by the memory, not the hardware (potentially an ASIC) for computing the SHA part.
        The scrypt algorithm is an example. For this, a parameter N is chosen. Initialization is done as

        V = buffer of size N
        V[0] = <seed>
        for i=1 to N-1
          V[i] = sha256(V[i-1])

        Then, on input X, do the following

        for i=1 to N
          j = X mod N
          X = sha256(X ⊕ V[j])

        The output is again in X.
        • Unfortunately, this particular replacement hash function seems to have, strangely enough, allowed an even greater speed-up when implemented in ASICs than plain SHA256...
        • Another problem is that this function is, in theory, also memory-intensive just to verify. This can have a significant impact on usability, such as by making light-weight wallets less convenient.
      • Another idea is simply to change the hash function used in the cryptocurrency protocol, perhaps changing it frequently enough that investments in ASICs would be unwise because they would not produce hardware that had much of an expected useful lifetime. It is necessary, however, to have very strong cryptographic hash functions to plug in with each change.
        For example, there is a proposal to use a hash function called X11 which is (pretty much) just the composition of all of the currently unbroken hash functions which were submitted as part of the NIST global competition which resulted in the SHA3 standard. X11 has not been implemented in ASIC at this time, so far as is generally known.
    • Another replacement for the proof of work doing the useless work of computing lots of SHAs would be one based on a more interesting problem. This turns out to be harder than it seems, because it is important to have difficult computation but fairly quick verification (sounds sort of like NP problems, doesn't it?). Here are two examples:
      • A cryptographic proof that an individual miner has a copy of part of a valuable global database that should be kept in redundant, verified copies around the 'net can be built into a proof of work. This is based on Merkle trees and therefor we may here about it in one of the student projects this week. It is the idea behind the altcoin Permacoin.
      • A problem in number theory, searching for certain particular sets of prime numbers, can be built into an amusing proof of work. The resulting altcoin is called Primecoin.
        • A Cunninham chain is a sequence of prime numbers $p_1,\dots,p_k$ such that for each $1<j≤k$, we have $p_j=2p_{j-1}+1$ (so, $k$ primes where each is nearly the double of the previous one).
        • Now fix $n, m, k\in\NN$. On input of a bit string $x$, look for a Cunningham chain $p_1,\dots,p_k$ satisfying
          • the first $m$ bits of $p_1$ are the same as the first $m$ bits of $x$ and
          • $n-1<\log_2(p_1)<n$ (so the bit length of $p_1$ is $n$)
        • This problem takes time which grows polynomialy in $n$ and exponentially in $k$, so it makes for some very fine-tuned proofs of work.
• :
  • Some content we discussed, morning (M117):
    • Introduction to the idea of proof of stake, to replace (or at least modify) proof of work. We concede that the rich will get richer, in the sense that in a cryptocoin-based economy, whoever has a lot of cryptocoin now, can buy more hardware to do more mining and accumulate more coins, more quickly. So if this is given, we might as well reduce the computational cost of finding the nonce which will validate a new block, if only to reduce the energy waste in mining, based on how many coins the miner already has.
    • One approach is based on the coin age, which is (basically) product of the number of coins and their age. For various reasons including game theory and performance consequences, the precise details of what the formula should be is the subject of much debate.
    • Whatever the formula we use for coin age, the idea is to make a new kind of transaction which consumes the coin age and has the consequence of allowing a lower difficulty to be accepted as valid in a newly mined block.
    • Cryptocurrencies which have, or have proposed, at least a partly proof of stake-based system include Peercoin,, Ethereum, ShadowCash, Nxt, BlackCoin, NuShares/NuBits, Qora,and Nav Coin.
    • Note that there is the fear in systems like this that there is more of an incentive to attempt to fork the block chain, since the miner trying to build a fork will only truly loose the coin age along one branch, whichever is ultimately accepted into the global consensus block chain. In response to this, the designers of Ethereum have proposed an algorithm called slasher (see this description) which punishes those who try to create these forks.
  • Morning programming project:
    1. If your mining code from last Friday is not yet in good shape, please finish it. In particular, we want:
       • It doesn't ever crash.
       • It detects if/when the block chain has forked and then when the fork is resolved, if you have gotten that far; or when it has gotten to an illegal state, if you haven't handled forking.
       • It collects information on the length of the consensus block chain and if, when, and for how long, the chain forks, over time.
       • Make some graphs of this data, using your favorite graphing tool (if you have no favorite, gnuplot is a nice one for Linux that many scientists use; or Desmos is very easy to use and produces great output
       • Make graphs of the above variables over time, for different values of the constant, global difficulty level, and for different numbers of actors.
    2. With a clean, working mining program, add in some of today's ideas: non-constant difficulties! Here are some ways to try that
       • Try various different, non-constant difficulties depending upon things like the time since each particular client has last gotten a block on the chain, the counter value, some other client-maintained number representing the number of coins it currently owns.
       • For the purpose of this exercise, all clients should simply trust that the the others are making well-formed blocks and for example, its statement of how many coins it owns at that time is correct and true.
       • You could have some of these other parameters passed into the block chain by putting them in the comment field of you blocks. Then other clients could check the validity of a new block against whatever formula you are using for the difficulty function, applied to the information extracted from that comment string.
    3. Then, make more graphs like the ones from above.
    4. Another fun thing to do is to implement a Byzantine peer in this protocol. Make one — or more — peers which do not follow the rules by proposing invalid blocks or even just sending improperly formatted messages to its other peers, perhaps at a very high rate (some kind of DOS attack...).
  • Afternoon activities (still in M117):
    • Our first presentation, by Anna and Guðbjörn, on Failure Modes, is today at 1pm. Don't be late!
    • For presentations, please send your instructor e-mail (at jonathan@poritz.net) both
      • a new idea/fact/formula/algorithm/etc. that you learned in this presentation, and
      • a question you have after seeing the presentation, about the specific material it described, or how that material connects with something else. [You may also ask that question in class.]
      For both, give as precise and clear an explanation as you can.
    • After the presentation, please continue work on the morning programming project described above.
• :
  • Some content we discussed, morning (M117):
    • Suppose we have a secret $S$ which we wish to share among $n$ collaborators for safety and redundancy. But we are worried that by spreading out the secret, we have also provided a greater attack surface (as the security people describe it), in the sense that there are more places which have information about $S$ that a potential attacker could try to compromise. We therefore decide that the secret shares — the pieces of information we give to each collaborator — should not individually reveal the secret, but in combination. This motivates the following definition.
    • Let $S$ be a secret integer value. For natural numbers $k$ and $n$ with $k\le n$, a $(k,n)$-Secret Sharing Scheme is an method to create $n$ integer values $S_1,\dots,S_n$, called the shares, with the property that $S$ can be reconstructed from any $k$ of these shares while knowledge of any group of $k-1$ shares yields no information about $S$.
    • The secret sharing scheme due to Shamir uses as its basic underlying principle the fact that a polynomial of degree $d$ is determined by its values at $d+1$ points, but not its values at set of fewer points. So Shamir puts the secret $S$ as the constant coefficient of a polynomial of degree $k-1$ whose other coefficients are chosen randomly. Then the values of this polynomial for $n$ distinct values of $x$ are the $n$ shares to be given to the collaborators. To reconstruct the secret from $k$ shares, he figures out the formula for the polynomial, based on any $k$ points.
      • Here's one way to think about how to do that. Suppose we are given points $(x_1,y_1),\dots,(x_k,y_k)$ all of whose $x$ coordinates are distinct and want to find the polynomial of degree $k-1$ which passes through those points.

        Well, look at a term like $$ \prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x) $$ This is a polynomial of degree $k-1$ whose value when $x$ equals any of the $x_\ell$ is zero except for the case of $x=x_j$, when it is non-zero (remember the $x_1,\dots,x_k$ are all distinct).

        We can make that non-zero value at $x=x_j$ be $y_j$ by multiplying by the correct constant, as $$ \left[\frac{y_j}{\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x_j)}\right]\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x) $$ (the term in the square brackets here is a constant, while the other term is a polynomial of degree $k-1$).

        So this one expression is a polynomial of degree $k-1$ with value 0 at all of the $x_\ell$ except for $x_j$, where it's value is $y_j$. If we then add these up for all values of $j$ from $1$ to $k$, since all of them are 0 at each $x_j$ except for one which has the value $y_j$, we will have a polynomial with the behavior we were looking for, $$ \sum_{j=1}^k\left(\left[\frac{y_j}{\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x_j)}\right]\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x)\right) = \sum_{j=1}^k\left(\frac{y_j \prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x)}{\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x_j)}\right) , $$

        and of course there is a unique polynomial with those desired properties, so this one must be it!

        Note if we are interested in the constant coefficient $a_0$ of this polynomial, we can find it just by plugging in $x=0$ to that formula, giving $$ a_0 = \sum_{j=1}^k\left(\frac{y_j \prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-0)}{\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x_j)}\right) = \sum_{j=1}^k\left(\frac{y_j \prod\limits_{\ell=1\\\ell\neq j}^{k}x_\ell}{\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x_j)}\right) . $$

        This can be useful in the Shamir secret-sharing scheme, although to avoid precision issues with the divisions in the formula, we work in some $\ZZ^*_p$ where $p$ is a large prime. All elements such a $\ZZ^*_p$ have multiplicative inverses, so that everything can be represented by integer values and division can be done with perfect precision.

  • Morning programming project:
    1. A secret sharing implementation should have two programs:

       1. (p, S1, ..., Sn) = get_shares(k, n, S)

          where inputs are natural numbers representing the $k$ and $n$ of a $(k,n)$-secret sharing scheme and the secret $S$ itself, and the output is a tuple representing general information needed by all shares (here, $p$, for "parameter"), and the $n$ shares.

       2. S = combine(k, n, p, S1, ..., Sk)

          where the inputs are the values $k$ and $n$ of the $(k,n)$-secret sharing, the $p$ parameters generated by get_shares, and $k$ of the shares, while the output is the recombined secret.
    2. Shamir's scheme worked as follows:
       1. For get_shares:
          1. Start by picking a prime $p$ bigger than $k$, $n$, and $S$, and do all arithmetic in $\ZZ^*_p$; that is, after every integer operation in what follows, take the result mod $p$.
          2. Generate $k-1$ random numbers $a_1, \dots, a_{k-1}$ each of the same bit length as $S$.
          3. Define the polynomial $q(x) = S+a_1 x +a_2 x^2 + \dots + a_{k-1} x^{k-1}$.
          4. Define for $1\le j\le n$ the $j^{th}$ share as the pair $S_j=(j, q(j))$.
          5. Output $p$ and the shares $S_1,\dots,S_n$.
          6. In practical uses, each collaborator (participating server) gets $p$, $k$, $n$, and one of the shares $S_j$.
       2. For combine:
          1. Use the input $p$ to specify in which $\ZZ^*_p$ to work. That is, for all arithmetic that follows, reduce mod $p$ after every operation, and do divisions like $a/b$ by multiplying $a\cdot b^{-1}$ and reducing mod $p$, where $b^{-1}$ is the multiplicative inverse mod $p$ of $b$.
             • Recall that the multiplicative inverse $b^{-1}$ mod $p$ of a number $b$ can be found with the Extended Euclidean Algorithm [EEA]. So if you run the EEA on two numbers $b$ and $p$, it will return values $g$, $x$, and $y$, where $g=gcd(a,p)$ and $xa+yp=g$. For our uses here (since $p$ is prime), the gcd will always be 1, and that $x$ will be $b^{-1}$.
          2. The secret is given by $$ S = \sum_{j=1}^k \left(\frac{y_j \prod\limits_{\ell=1\\\ell\neq j}^k{x_\ell}}{\prod\limits_{\ell=1\\\ell\neq j}^{k}(x_\ell-x_j)}\right)\ . $$
       3. It would be very cool to make a practical version of this scheme:
          1. The input would be a string and values for $k$ and $n$.
          2. The secret sharing protocol would be run on each byte of the input string separately. All those secrets would use the same prime $p$ — fix some value for $p$ which is larger than the largest unsigned int stored in a byte.
          3. Then $k$ and $n$ will have to be less than this $p$, but that should be of little practical consequence.
          4. The output secret share for each character of the input string might be an unprintable byte, so print it out as two hex digits.
          5. Note: actually, the share for each input character might be more than one byte, if the modulus $p$ is larger than $256$. After all, to get the shares, one does arithmetic in $\ZZ^*_p$, which will result in data values up to $p-1$, so we won't have single bytes unless $p\le256$. So it might be a good idea for this code exercise to use a prime $p$ which is as large as possible but still not more than 256, such as $p=251$. [Note: this issue was pointed out by Atli. Thanks!]
          6. The entire output for each share $S_j$ should indicate the $p$, $k$, $n$, $j$, and that string of pairs of hex digits. Print all of these out with some white space separating values to be giving to each collaborator, so the output can be printed on paper and each collaborator tears of their part.
          7. The reassembly program has to invert this process of hex digits to unsigned int bytes to original secret ASCII characters which would be assembled and printed out.
       4. The above scheme does leak with every share, at least as just described as a practical technique, the length of the secret string. Can you think of a way to hide that length?
  • Some content we discussed, afternoon (M117):
    • Our second presentation, by Atli and Patrekur, on Merkle Trees, is today at 1:17pm. Don't be late!
  • Afternoon programming project:
    1. Finish secret sharing implementation.
• :
  • Morning activities (M117):
    • Our third presentation, by Joy, Leonardo, and Marco, on Paxos, is today at 10am. Don't be late!
    • Discussing Script: code as transaction contents in Bitcoin. Some interesting features:
      1. It's a stack-oriented, supposedly based on the [quite antique, at this point in time] language Forth.
      2. Transactions are not, in Bitcoin, just simple records saying one identity transfers so many BTC to another. Instead, think of the output of one transaction as locking some BTC in such a way that another agent can, as part of the input of a future transaction, unlock those coins.
      3. The simplest version of this is when Alice simply locks the BTC in question to the public key of Bob — this is just a way she pays Bob those coins. But more elaborate uses are also possible.
      4. One thing is requiring a multisign (otherwise known as a threshold signature). This can be useful for example if the output of one trasaction from the buyer of some good, Alice, to seller Bob is not completed to either of their satisfactions. So long as they involved a mutually trusted third party Charlie and put a $(2,3)$-multisg verification in the locking output of the payment transaction, Bob will only be able to spend those BTC in the future if he can convince either Alice or Charlie to provide a signature. Alice will do so if she is happy with the goods she received. If she is not, she will refuse -- but Bob could get paid anyway so long as he could convince Charlie that the goods were indeed delivered and did have the properties that was agreed upon, so that Charlie would provide the second, validating signature.
      5. As just one last interesting example of a use of Script (although there are many more!), there is an operation called OP_RETURN, which takes some data on the stack ... but never executes as valid. That is, using it in a lock makes something that has a data payload but that cannot ever be unlocked. This has the consequence of making a valid transaction output which burns some (presumably small amount of) BTC and has the side-effect of putting the argument data on the permanent, global, consensus block chain. This could be a way of publicly registering some (small) piece of information.

         This is somewhat controversial in the Bitcoin community. Some people think it is a nice new use of the block chain. Others think that it will lead to horrible "block chain bloat."

      6. Here is a good reference for the Script.
  • Afternoon activities (M117):
    • Our fourth and final presentation, by Hugo, Ivar, and Ragnar, on Elliptic Curve Crypto, is today at 1:17pm. Don't be late!
• :
  • Morning activities (M117):
    • Future prospects, altcoins, and other "revolutionary changes to the global economic system coming from the block chain."
    • Here is an example of some very grand claims for the block chain.
    • A cool tool for detailed study of Bitcoin: blockchain.info/.
    • And the bitcoin wiki is a great resource with papers, definitions, explanations, links to software, etc., etc.
    • Here is a nice list of a bunch of current altcoins.
    • An interesting article on (mostly) traditional security problems' consequences for the bitcoin wallet: Bitcoin Self-Defense, Part I: Wallet Protection
    • Here is a description of an altcoin whose proof of work involves demonstrating participation in a DDOS attack and here is the technical paper.
  • Morning programming project:
    1. Finish any outstanding programming projects.
  • Afternoon activities (M117):
    • Field trip to a dark alley in Reykjavik in order to buy some Bitcoin with cash, then return to the university to use this BTC to buy something on the 'net.
  • Afternoon programming project:
    1. Really finish any outstanding programming projects.

After Week 3: To Be Turned In

Each student must do the following:

1. For each of the presentations, send your instructor e-mail (at jonathan@poritz.net) both
   1. a new idea/fact/formula/algorithm/etc. that you learned in this presentation, and
   2. a question you have after seeing the presentation, about the specific material it described, or how that material connects with something else.
   For both, give as precise and clear an explanation as you can.
2. If you were involved in a team that did a presentation, send your instructor the following
   1. any presentation materials you used (in PDF format, please!),
   2. any code you made for your presentation, and
   3. a list of the references you consulted, if it is not already in the materials you sent as a., above.
3. Make sure you have sent your instructor code for either the Block Chain Bucks project [final description on Thursday of the second week of this class; hopefully in version v2 or at least v1], or the model mining project [description on Friday of the second week of this class, with refinements on Tuesday of the third week].
4. Also, send your instructor at least one other smaller programming project, from the first week of the class — signatures, encrypted chat, etc. — and one from the last week — implement scrypt, something which searches for Cunninham chains, or a secret sharing tool.
5. For any code you send to submit as requested above, this is what it means for them to be "done":
   • The code is clean — debugged!! — and at has at least some comments and/or documentation.
   • Instructions are provided for how to configure, install, and operate your code.
   • Provide whatever is necessary for another person (your instructor or, let's say, another Trusted Third Party) to run the code through some examples that show its range of functionality.