ビットコインの仕組み

#
# DO NOT SET THIS VALUE "false".
#
IS_TESTNET = true

class Key
public
  def self.hash256(plain)
    return OpenSSL::Digest::SHA256.digest(OpenSSL::Digest::SHA256.digest(plain))
  end

  def self.hash160(plain)
    return OpenSSL::Digest::RIPEMD160.digest(OpenSSL::Digest::SHA256.digest(plain))
  end

  BASE58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
  def self.encode_base58(plain)
    # plain is big endian

    num = plain.unpack("H*").first.hex

    res = ''

    while num > 0
      res += BASE58[num % 58]
      num /= 58
    end

    # restore leading zeroes
    plain.each_byte do |c|
      break if c != 0
      res += BASE58[0]
    end

    return res.reverse
  end

  def self.decode_base58(encoded)
    num = 0
    encoded.each_char do |c|
      num *= 58
      num += BASE58.index(c)
    end

    res = num.to_s(16)

    if res % 2 == 1 then
      res = '0' + res
    end

    # restore leading zeroes
    encoded.each_char do |c|
      break if c != BASE58[0]
      res += '00'
    end

    return [res].pack('H*')
  end

  def self.encode_base58check(type, plain)
    leading_bytes = {
      :main    => { :public_key => 0,   :private_key => 128 },
      :testnet => { :public_key => 111, :private_key => 239 }
    }

    leading_byte = [leading_bytes[IS_TESTNET ? :testnet : :main][type]].pack('C')

    data = leading_byte + plain
    checksum = Key.hash256(data)[0, 4]

    return Key.encode_base58(data + checksum)
  end

  def self.decode_base58check(encoded)
    decoded = Key.decode_base58(encoded)

    raise "invalid base58 checksum" if Key.hash256(decoded[0, decoded.length - 4])[0, 4] != decoded[-4, 4]

    types = {
      :main    => { 0   => :public_key, 128 => :private_key },
      :testnet => { 111 => :public_key, 239 => :private_key }
    }

    type = types[IS_TESTNET ? :testnet : :main][decoded[0].unpack('C').first]

    return {:type => type, :data => decoded[1, decoded.length - 5]}
  end

  def to_address_s
    return Key.encode_base58check(:public_key, Key.hash160(@key.public_key.to_bn.to_s(2)))
  end

class BloomFilter

  def hash(seed, data)

  def insert(data)
    @hash_funcs.times do |i|
      set_bit(hash(i * 0xfba4c795 + @tweak, data) % (@filter.length * 8))
    end
  end

class Network
private
  PROTOCOL_VERSION = 70001

  def write_message(message)
    # Create payload
    serialize_message(message)

    # 4bytes: magic
    raw_message = [IS_TESTNET ? '0b110907' : 'f9beb4d9'].pack('H*')

    # 12bytes: command (padded with zeroes)
    raw_message += [message[:command].to_s].pack('a12')

    # 4bytes: length of payload
    raw_message += [@payload.length].pack('V')

    # 4bytes: checksum
    raw_message += Key.hash256(@payload)[0, 4]

    # payload
    raw_message += @payload

    @socket.write raw_message
    @socket.flush
  end

  def message_defs
    # 中略
    return @message_defs = {
      :version => [
        [:version,   uint32],
        [:services,  uint64],
        [:timestamp, uint64],
        [:your_addr, net_addr],
        [:my_addr,   net_addr],
        [:nonce,     uint64],
        [:agent,     string],
        [:height,    uint32],
        [:relay,     relay_flag]
      ],
      :verack => [],
      :mempool => [],
      :addr => [[:addr, array.curry[net_addr]]],
      :inv  => [[:inventory,  array.curry[inv_vect]]],
      :merkleblock => [
        [:hash,        block_hash],
        [:version,     uint32],
        [:prev_block,  hash256],
        [:merkle_root, hash256],
        [:timestamp,   uint32],
        [:bits,        uint32],
        [:nonce,       uint32],
        [:total_txs,   uint32],
        [:hashes,      array.curry[hash256]],
        [:flags,       string]
      ],
      :tx => [
        [:hash,      tx_hash],
        [:version,   uint32],
        [:tx_in,     array.curry[tx_in]],
        [:tx_out,    array.curry[tx_out]],
        [:lock_time, uint32]
      ],
      :filterload => [
        [:filter,     string],
        [:hash_funcs, uint32],
        [:tweak,      uint32],
        [:flag,       uint8]
      ],
      :getblocks => [
        [:version,       uint32],
        [:block_locator, array.curry[hash256]],
        [:hash_stop,     hash256]
      ],
      :getdata => [[:inventory, array.curry[inv_vect]]]
    }
  end

    integer = lambda do |rw, val = nil|
      case rw
      when :read
        top = uint8.call(:read)

        if top < 0xfd then
          return top
        elsif top == 0xfd then
          return uint16.call(:read)
        elsif top == 0xfe then
          return uint32.call(:read)
        elsif top == 0xff then
          return uint64.call(:read)
        end

      when :write
        if val < 0xfd then
          uint8.call(:write, val)
        elsif val <= 0xffff then
          uint8.call(:write, 0xfd)
          uint16.call(:write, val)
        elsif val <= 0xffffffff then
          uint8.call(:write, 0xfe)
          uint32.call(:write, val)
        else
          uint8.call(:write, 0xff)
          uint64.call(:write, val)
        end

      end
    end

Usage: ruby bcwallet.rb <command> [<args>]
commands:
    generate <name>             generate a new Bitcoin address
    list                        show list for all Bitcoin addresses
    export <name>               show private key for the Bitcoin address
    balance                     show balances for all Bitcoin addresses
    send <name> <to> <amount>   transfer coins to the Bitcoin address

# BCWallet#run
    when 'balance'
      STDERR.print "loading data ...\r"
      @network = Network.new(@keys, @data_file_name)

      @network.sync()

      wait_for_sync()

      puts 'Balances for available Bitcoin addresses: '

      balance = @network.get_balance()
      balance.each do |addr, satoshi|
        puts "    #{ addr }: #{ sprintf('%.8f', Rational(satoshi, 10**8)) } BTC"
      end

  def sync
    Thread.abort_on_exception = true
    @is_sync_finished = false
    t = Thread.new do

      unless @socket then
        @status = 'connection establishing ... '

        @socket = TCPSocket.open(HOST, IS_TESTNET ? 18333 : 8333)

        send_version()
      end

      if @created_transaction then
        @status = 'announcing transaction ... '

        send_transaction_inv()
      end

      loop do
        break if dispatch_message()
      end

      @is_sync_finished = true
    end
    t.run
  end

  def dispatch_message
    message = read_message()

    case message[:command]
    when :version
      # 最後のブロックの高さ
      @data[:last_height] = message[:height]
      save_data

      write_message({:command => :verack})

    when :verack
      # ハンドシェイク完了

  # message_defs()
      :version => [
        [:version,   uint32],
        [:services,  uint64],
        [:timestamp, uint64],
        [:your_addr, net_addr],
        [:my_addr,   net_addr],
        [:nonce,     uint64],
        [:agent,     string],
        [:height,    uint32],
        [:relay,     relay_flag]
      ],
      :verack => [],

  # 中略

  def send_version
    write_message({
      :command => :version,

      :version   => PROTOCOL_VERSION,

      # 完全なブロックを相手に送れないので0
      :services  => 0,

      :timestamp => Time.now.to_i,

      :your_addr => nil, # 本当はちゃんと書かないといけないけどテキトーでも
      :my_addr   => nil, # 相手クライアントから怒られないから省略

      :nonce     => (rand(1 << 64) - 1), # A random number.

      :agent     => '/bcwallet.rb:1.00/', # エージェントの名前
      :height    => (@data[:blocks].length - 1), # 所持しているブロックの高さ

      # filterloadするまでいかなるinvも送信しない
      :relay     => false
    })

    return
  end

    when :verack
      # ハンドシェイク完了

      # ブルームフィルターをセット
      send_filterload()

      # メモリープール内のトランザクションを勝手にinvするように
      write_message({:command => :mempool})

      # 必要ならばgetblocksを送って、もう終わりならtrueを返す。
      return true if send_getblocks()

          # message_defs
          :filterload => [
            [:filter,     string],
            [:hash_funcs, uint32],
            [:tweak,      uint32],
            [:flag,       uint8]
          ],

   # 中略

   def send_filterload
    hash_funcs = 10
    tweak = rand(1 << 32) - 1

    bf = BloomFilter.new(512, hash_funcs, tweak) 

    @keys.each do |_, key|
      bf.insert(key.to_public_key)
      bf.insert(key.to_public_key_hash)
    end

    write_message({
      :command => :filterload,

      :filter     => bf.to_s,
      :hash_funcs => hash_funcs,
      :tweak      => tweak,

      # BLOOM_UPDATE_ALL, updates Bloom filter automatically when the client has found matching transactions.
      :flag       => 1
    })
  end

      # message_defs
      :getblocks => [
        [:version,       uint32],
        [:block_locator, array.curry[hash256]],
        [:hash_stop,     hash256]
      ],

  # 中略

  def send_getblocks
    weight = 50
    perc = (weight * @data[:blocks].length / @data[:last_height]).to_i
    @status = '|' + '=' * perc + '_' * (weight - perc) +
      "| #{(@data[:blocks].length - 1)} / #{@data[:last_height]} "

    # @data[:blocks].length includes block #0 while @data[:last_height] does not.
    if @data[:blocks].length > @data[:last_height] then
      save_data()
      return true
    end

    if @data[:blocks].empty? then
      send_getdata([{:type => MSG_FILTERED_BLOCK, :hash => @last_hash[:hash]}])
    end

    write_message({
      :command => :getblocks,

      :version => PROTOCOL_VERSION,
      :block_locator => [@last_hash[:hash]],
      :hash_stop => ['00' * 32].pack('H*')
    })

    return false
  end

def generate_block_locator_indices(height)
  res = []

  step = 1
  while height > 0
    step *= 2 if res.length >= 10
    res.push height
    height -= step
  end

  res.push 0

  return res
end

> generate_block_locator_indices(500)
=> [500, 499, 498, 497, 496, 495, 494, 493, 492, 491, 490, 488, 484, 476, 460, 428, 364, 236, 0]

    inv_vect = lambda do |rw, val = nil|
      case rw
      when :read
        type = uint32.call(:read)
        hash = hash256.call(:read)
        return {:type => type, :hash => hash}
      when :write
        uint32.call(:write, val[:type])
        hash256.call(:write, val[:hash])
      end
    end

  # 中略

      :inv  => [[:inventory,  array.curry[inv_vect]]],
      :getdata => [[:inventory, array.curry[inv_vect]]]

  # 中略

  MSG_TX = 1
  MSG_BLOCK = 2
  MSG_FILTERED_BLOCK = 3

  # 中略
    when :inv
      send_getdata message[:inventory]

  # 全部のデータを受け取ったか判定できるように、送ったgetdataの数を覚えておく
      @requested_data += message[:inventory].length

  # 中略

  def send_getdata(inventory)
    write_message({
      :command => :getdata,

      :inventory => inventory.collect do |elm|
        # receive merkleblock instead of usual block
        {:type => (elm[:type] == MSG_BLOCK ? MSG_FILTERED_BLOCK : elm[:type]),
         :hash => elm[:hash]}
      end
    })

    return
  end

      :merkleblock => [
        [:hash,        block_hash],
        [:version,     uint32],
        [:prev_block,  hash256],
        [:merkle_root, hash256],
        [:timestamp,   uint32],
        [:bits,        uint32],
        [:nonce,       uint32],
        [:total_txs,   uint32],
        [:hashes,      array.curry[hash256]],
        [:flags,       string]
      ],
      :tx => [
        [:hash,      tx_hash],
        [:version,   uint32],
        [:tx_in,     array.curry[tx_in]],
        [:tx_out,    array.curry[tx_out]],
        [:lock_time, uint32]
      ],

    block_hash = lambda do |rw, val = nil|
      case rw
      when :read
        return Key.hash256(@r_payload[0, 80])
      end
    end

    tx_hash = lambda do |rw, val = nil|
      case rw
      when :read
        return Key.hash256(@r_payload)
      end
    end

    outpoint = lambda do |rw, val = nil|
      case rw
      when :read
        hash = hash256.call(:read)
        index = uint32.call(:read)
        return { :hash => hash, :index => index }
      when :write
        hash256.call(:write, val[:hash])
        uint32.call(:write, val[:index])
      end
    end

    tx_in = lambda do |rw, val = nil|
      case rw
      when :read
        previous_output = outpoint.call(:read)
        signature_script = string.call(:read)
        sequence = uint32.call(:read)
        return { :previous_output => previous_output,
                 :signature_script => signature_script, :sequence => sequence }
      when :write
        outpoint.call(:write, val[:previous_output])
        string.call(:write, val[:signature_script])
        uint32.call(:write, val[:sequence])
      end
    end

    tx_out = lambda do |rw, val = nil|
      case rw
      when :read
        value = uint64.call(:read)
        pk_script = string.call(:read)
        return { :value => value, :pk_script => pk_script }
      when :write
        uint64.call(:write, val[:value])
        string.call(:write, val[:pk_script])
      end
    end

  def extract_public_key_hash_from_script(script)
    # OP_DUP OP_HASH160 (public key hash) OP_EQUALVERIFY OP_CHECKSIG
    unless script[0, 3]  == ['76a914'].pack('H*') &&
           script[23, 2] == ['88ac'].pack('H*') &&
           script.length == 25 then
      raise 'unsupported script format' 
    end

    return script[3, 20]
  end

  def get_balance
    balance = {}
    @keys.each do |addr, _|
      balance[addr] = 0
    end

    set_spent_for_tx_outs()

    @data[:txs].each do |tx_hash, tx|
      @keys.each do |addr, key|
        public_key_hash = key.to_public_key_hash

        tx[:tx_out].each do |tx_out|
          # The tx_out was already spent
          next if tx_out[:spent]

          if extract_public_key_hash_from_script(tx_out[:pk_script]) == public_key_hash then
            balance[addr] += tx_out[:value]
          end
        end
      end
    end

    return balance
  end

  # 
  # コインを指定したアドレスに送る
  # from_key = コインの送信元のキーのオブジェクト（Keyクラスのインスタンス）
  # to_addr  = 受信するアドレスの文字列
  # transaction_fee = 取引手数料
  #
  def send(from_key, to_addr, amount, transaction_fee = 0)
    to_addr_decoded = Key.decode_base58check(to_addr)

    raise "invalid address" if to_addr_decoded[:type] != :public_key

    public_key_hash = from_key.to_public_key_hash

    set_spent_for_tx_outs()

    total_satoshis = 0
    tx_in = []
    @data[:txs].each do |tx_hash, tx|
      break if total_satoshis >= amount

      matched = nil
      pk_script = nil

      tx[:tx_out].each_with_index do |tx_out, index|
        next if tx_out[:spent]

        if extract_public_key_hash_from_script(tx_out[:pk_script]) == public_key_hash then
          total_satoshis += tx_out[:value]
          matched = index
          pk_script = tx_out[:pk_script]
          break
        end
      end

      if matched then
        tx_in.push({ :previous_output => { :hash => tx[:hash], :index => matched },
                     :signature_script => '',
                     :sequence => ((1 << 32) - 1),

                     # 送信データには含まれないが、電子署名の作成に使う
                     :pk_script => pk_script })
      end
    end

    payback = total_satoshis - amount - transaction_fee

    raise "you don't have enough balance to pay" unless payback >= 0

    prefix = ['76a914'].pack('H*') # OP_DUP OP_HASH160 [length of the address]
    postfix = ['88ac'].pack('H*')  # OP_EQUALVERIFY OP_CHECKSIG

    tx_out = [{ :value => amount,  :pk_script => (prefix + to_addr_decoded[:data] + postfix) },
              { :value => payback, :pk_script => (prefix + public_key_hash + postfix) }]

    @created_transaction = {
      :command => :tx,

      :version => 1,
      :tx_in => tx_in,
      :tx_out => tx_out,
      :lock_time => 0
    }

# ここまでで、電子署名抜きのデータを作成したので電子署名を以下で生成する。

    signatures = []

    tx_in.each_with_index do |tx_in_elm, i|
  # 元のデータが壊れないように必要最小限の深さだけコピー
      duplicated = @created_transaction.dup
      duplicated[:tx_in] = duplicated[:tx_in].dup
      duplicated[:tx_in][i] = duplicated[:tx_in][i].dup

  # 対応するtx_outの:pk_scriptで埋める（他のtx_inのsignature_scriptは空欄）
      duplicated[:tx_in][i][:signature_script] = tx_in_elm[:pk_script]

      serialize_message(duplicated)

  # @payloadにシリアライズされたデータが入る

      # hash256 includes type code field (see the figure in the URL above)
      verified_str = Key.hash256(@payload + [1].pack('V'))

      signatures.push from_key.sign(verified_str)
    end

    signatures.each_with_index do |signature, i|
      @created_transaction[:tx_in][i][:signature_script] =
        [signature.length + 1].pack('C') + signature + [1].pack('C') +
        [from_key.to_public_key.length].pack('C') + from_key.to_public_key
    end

    @status = ''

    return
  end