# The code which follows generates a Bitcoin-like block-chain of any length. Each block can contain any amount of data
# in the form of an array of separate strings. On generation, the block's header will consist of a time stamp, a nonce, which
# for now is just a place holder (the number 42), and the head of the Merkle tree of the block's data.

# Following the chain code is a test case with seven blocks and an integrity check. The chain is Marshaled into a file,
# removed from memory, and reread into the program. Then one string in one of the blocks is modified, the Merkle tree is
# updated for compatibility with the modified data, and the header is modified to be consistent with the modified Merkle
# tree. The block's hashed header is even modified to be compatible with the corrupted block. Then the integrity check is
# repeated. This is a fairly sophisticated attack on the block chain, but, as you can see from the test results, readily detectable.
# A more serious attack would successively modify the headers of blocks up to the lead block (one short of the dummy header
# block), but this can't be carried out, because the hashed header of that last data block will be published separately
# from the block, and that is why the block chain cannot be modified (anywhere) without detection.

#! /usr/bin/ruby

require 'digest/sha1'

DUMMY_ARRAY = %w{ Dummy array }

# merkle_tree builds a Merkle tree and returns (and keeps only) the head.
# input -- leaf_data -- The data (lowest level) for the tree as an array of strings
# return -- The tree head as a single hash
def merkle_tree(leaf_data)
  data, next_level, s = Array.new(leaf_data), [], nil
  
  data.collect! { |el| do_hash(el) }
  
  loop do
    loop do
      s = data.shift.to_s
      break if data.empty?
      s += data.shift.to_s
      break if data.empty?
      next_level << do_hash(s)
    end
    next_level << do_hash(s)
    break if next_level.size == 1
    data = Array.new(next_level)
    next_level = []
  end
  next_level[0]
end

# do_hash moves all the hash calls to a single point
# input -- s -- The string to hash
# return -- hash of s
def do_hash(s)
  Digest::SHA1.hexdigest(s)
end

# Block is a Bitcoin-like block but with any (string) data in the form of an array
class Block
  attr_accessor :data_array, :merkle, :header, :cumulative_hash_header, :next_block
  attr_reader :time_stamp, :nonce, :previous_block, :is_first
  
  @header, @next_block, @cumulative_hash_header = nil, nil, nil

  # input -- previous_block -- a pointer back to the preceding block
  # input -- is_first -- true for first block, false otherwise
  # input -- data_array -- the data in the block as a string array
  def initialize(previous_block, is_first, data_array)
    @previous_block, @is_first, @data_array = previous_block, is_first, data_array
    @nonce = 42 # for now
    @time_stamp, @merkle = Time.now.gmtime.to_s, merkle_tree(@data_array)
    @header = @merkle + @time_stamp + @nonce.to_s
    @cumulative_hash_header = do_hash(@header) if is_first
  end
  
  # reset_data_array is used to set the @cumulative_hash_header when a new block is added
  # input -- data_array -- a changed data array is input and an updated @header is calculated from the updated Merkle tree
  def reset_data_array(data_array)
    @data_array = data_array
    @merkle = merkle_tree(@data_array)
    @header = @merkle + @time_stamp + @nonce.to_s
    @cumulative_hash_header = do_hash(previous_block.cumulative_hash_header + @header)
  end
end

# Chain is a Bitcoin-like chain but with arbitrary block (string) data
class Chain
  attr_reader :head, :master_hash
  
  @tail, @chain = nil, nil
  
  # start the Chain with two Blocks, @head being a place holder, but pointing to the second
  # Block, which contains the first array of data
  def initialize(data_array)
    @tail = @chain = Block.new('', true, data_array)
    @head = Block.new(@chain, false, DUMMY_ARRAY)
    @chain.next_block = @head
    @master_hash = @chain.cumulative_hash_header
  end

  # add_block updates the chain with a new block of data
  # input -- in_data_array -- the data for the new block
  def add_block(in_data_array)
    @head.reset_data_array(in_data_array)
    @chain = @head
    @head = Block.new(@chain, false, DUMMY_ARRAY)
    @chain.next_block = @head
    @master_hash = @chain.cumulative_hash_header
   end
  
   # tail_to_head recomputes the master hash for comparison with cumulative hash header
   # return -- a recalculated master hash
   def tail_to_head()
     present_block, next_block, block_array = @tail, @tail.next_block, []
     
     until present_block == @head
       block_array << present_block
       present_block = next_block
       next_block = present_block.next_block
     end
     
     a_header = ''
     block_array.each {|b| a_header = do_hash(a_header + merkle_tree(b.data_array) + b.time_stamp + b.nonce.to_s)}
     a_header
   end
  
   # fine_grained_corruption_search walks the block-chain from tail to head looking for 1. any incompatibilites
   # between the data array and the stored merkle tree head 2. the merkle tree head, the time stamp, and the nonce,
   # compared to the stored header, and 3. the cumulative hashed header and the stored cumulative hashed header.
   # return -- either an all good or an error message
   def fine_grained_corruption_search()
     present_block, next_block, s = @tail, @tail.next_block, 'No incompatibilities found'
     
     hashed_header = ''
     until present_block == @head
       merkle = merkle_tree(present_block.data_array)
       if merkle != present_block.merkle
         s = 'Merkle -- data incompatility'
         break
       end
       header = merkle + present_block.time_stamp + present_block.nonce.to_s
       if header != present_block.header
         s = 'Header incompability'
         break
       end
       hashed_header = do_hash(hashed_header + header)
       if hashed_header != present_block.cumulative_hash_header
         s = "Cumulative hashed header incompability in block beginning with \"#{present_block.data_array[0]}\""
         break
       end
       
       present_block = next_block
       next_block = present_block.next_block
     end
     s
   end
   
  # publish_master_hash does just that
  # return -- the header hash that insures an uncorrupted chain
  def publish_master_hash()
    @master_hash
  end
  
  # integrity_check compares the master_hash with a newly minted one
  # return -- true if chain is uncorrupted, false if chain is corrupted
  def integrity_check()
    (tail_to_head() == @master_hash) ? 'Chain is intact' : 'Chain is corrupted'
  end
  
  # to_s puts a nicely formatted chain into a string
  def to_s()
    present_block, next_block = @tail, @tail.next_block
    
    until present_block == @head
      printf("%s -- %s -- %d\n", present_block.data_array.join(' '), present_block.time_stamp, present_block.nonce)
      present_block = next_block
      next_block = present_block.next_block
    end
  end
end

End of code

Test input:

a_chain = Chain.new(%w{ Nobody ever went broke underestimating the taste of the American public })
a_chain.add_block(%w{ To apologize is to lay the foundation for a future offense })
a_chain.add_block(%w{ Patience: A minor form of dispair disguised as a virtue })
a_chain.add_block(%w{ War is God's way of teaching Americans geography })
a_chain.add_block(%w{ Happiness: An agreeable sensation arising from contemplating the misery of another })
a_chain.add_block(%w{ Academy: A modern school where football is taught })
a_chain.add_block(%w{ Egotist: A person of low taste, more interested in himself than in me })

puts "The master hash is: #{a_chain.publish_header_hash()}"

File.open('bitcoin_like_chain', 'w+') { |f| Marshal.dump(a_chain, f) }
a_chain = nil
File.open('bitcoin_like_chain') { |f| a_chain = Marshal.load(f) }

puts
puts "#{a_chain.integrity_check()}"
puts
puts "The uncorrupted chain is, in order of insertion:\n\n"
puts a_chain.to_s

puts 'Fine grained error search:'
puts a_chain.fine_grained_corruption_search()

s = %w{ Fidelity: A virtue peculiar to those who are about to be betrayed }
b = a_chain.head.previous_block.previous_block
b.data_array = s
b.merkle = merkle_tree(s)
b.header = b.merkle + b.time_stamp + b.nonce.to_s
b.cumulative_hash_header = do_hash(b.previous_block.cumulative_hash_header + b.header)

puts
puts "#{a_chain.integrity_check()}"
puts "\nThe corrupted chain is, in order of insertion:\n\n"
puts a_chain.to_s

puts 'Fine grained error search:'
puts a_chain.fine_grained_corruption_search()

# Test output:
  
# The master hash is: 5960671347cc1252dbf01229f04a8839dd43ab93

# Chain is intact

# The uncorrupted chain is, in order of insertion:

# Nobody ever went broke underestimating the taste of the American public -- 2015-11-15 16:19:58 UTC -- 42
# To apologize is to lay the foundation for a future offense -- 2015-11-15 16:19:58 UTC -- 42
# Patience: A minor form of dispair disguised as a virtue -- 2015-11-15 16:19:58 UTC -- 42
# War is God's way of teaching Americans geography -- 2015-11-15 16:19:58 UTC -- 42
# Happiness: An agreeable sensation arising from contemplating the misery of another -- 2015-11-15 16:19:58 UTC -- 42
# Academy: A modern school where football is taught -- 2015-11-15 16:19:58 UTC -- 42
# Egotist: A person of low taste, more interested in himself than in me -- 2015-11-15 16:19:58 UTC -- 42

# Fine grained error search:
# No incompatibilities found

# Chain is corrupted

# The corrupted chain is, in order of insertion:

# Nobody ever went broke underestimating the taste of the American public -- 2015-11-15 16:19:58 UTC -- 42
# To apologize is to lay the foundation for a future offense -- 2015-11-15 16:19:58 UTC -- 42
# Patience: A minor form of dispair disguised as a virtue -- 2015-11-15 16:19:58 UTC -- 42
# War is God's way of teaching Americans geography -- 2015-11-15 16:19:58 UTC -- 42
# Happiness: An agreeable sensation arising from contemplating the misery of another -- 2015-11-15 16:19:58 UTC -- 42
# Fidelity: A virtue peculiar to those who are about to be betrayed -- 2015-11-15 16:19:58 UTC -- 42
# Egotist: A person of low taste, more interested in himself than in me -- 2015-11-15 16:19:58 UTC -- 42

# Fine grained error search:
# Cumulative hashed header incompability in block beginning with "Egotist:"