Wednesday, September 23: Checkup 2 (was originally scheduled for Monday, September 21). See previous class notes for details on what is covered.
Friday, October 9: Problem Set 2 (moved from original deadline of October 2). Problem Set 2 will be posted later this week.
Monday, October 19: Midterm Exam


You can subscribe to the course calendar. This has updated information on deadlines and office hours.

If you want to receive course website updates by email, you can subscribe to the RSS feed using a RSS reader or an emailing service like or Blogtrottr. The feed address is

We generally will avoid sending out emails to the class, and will assume you are observing the website closely.

Note: ink markings may not appear in the embedded viewer. To see them, download the slides.

Exploring Blocks

version4Block version information
prev_block32Hash of the previous block
merkle_root32Hash of Merkle tree of all transactions
timestamp4When block was created (overflows in 2106)
bits4Difficulty target used for this block
nonce4Nonce found to generate this block

Merkle Trees

Ralph Merkle, Publishing a New Idea. Includes his cs244 project proposal (“Discussion: No, I am not joking.“) and ACM rejection letter (“I am sorry to have to inform you that the paper is not in the main stream of present cryptography thinking and I would not recommend that it be published…“). (some comments removed)

// HashMerkleBranches takes two hashes, treated as the left and right tree
// nodes, and returns the hash of their concatenation. 
func HashMerkleBranches(left *btcwire.ShaHash, right *btcwire.ShaHash) *btcwire.ShaHash {
   var sha [btcwire.HashSize * 2]byte
   copy(sha[:btcwire.HashSize], left.Bytes())
   copy(sha[btcwire.HashSize:], right.Bytes())
   newSha, _ := btcwire.NewShaHash(btcwire.DoubleSha256(sha[:]))
   return newSha

func BuildMerkleTreeStore(transactions []*btcutil.Tx) []*btcwire.ShaHash {
    nextPoT := nextPowerOfTwo(len(transactions))
    arraySize := nextPoT*2 - 1
    merkles := make([]*btcwire.ShaHash, arraySize)

    // Create the base transaction shas and populate the array with them.
    for i, tx := range transactions { merkles[i] = tx.Sha() }

    // Start the array offset after the last transaction and adjusted to the
    // next power of two.
    offset := nextPoT
    for i := 0; i < arraySize-1; i += 2 {
        switch {
           case merkles[i] == nil: 
              merkles[offset] = nil

           case merkles[i+1] == nil:
              newSha := HashMerkleBranches(merkles[i], merkles[i])
              merkles[offset] = newSha
              newSha := HashMerkleBranches(merkles[i], merkles[i+1])
              merkles[offset] = newSha
    return merkles

What is needed to verify T2 in Hroot?

What must be recomputed if T3 is replaced?

What must be computed if a new node, T5, is added?

How many SHA-256 hashes must be computed to verify Block 375474?

Mining Cost

The measured time to compute one SHA-256 hash on my EC2 node (2.5 GHz processor) is 750 ns. Approximately how many instructions execute to compute on SHA-256 hash?

Assumption. SHA-256 produces a uniform random output. (We know this is not really true, but it is a reasonable approximation, and necessary for the analysis.) So, we can model SHA-256 on any (new) input x as drawing randomly from 2256 possible outputs:

      SHA-256(x) ← [0, 2256)

$ Target = \frac{T_{max}}{Difficulty}$
$ T_{max} \approx 2^{224}$

Current Bitcoin Difficulty = 59,335,351,234


Why is energy/hash so much less for custom ASICs?

In an ASIC, it is possible to build an XOR using 4 transistors. How many transistors have to flip to do an XOR on a general purpose processor like an Intel i7?

More Reading
Comments powered by Disqus