# 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:"