Monday, March 2, 2015

Non-bitcoin assets on the block chain are not interesting

I frequently hear people in the Bitcoin community say that money is just the first application of the Bitcoin block chain, and that they want to use it for tracking other assets like land and securities. That thinking is misguided and I would like to explain why.

First of all, let's talk about the data in the block chain. The payload data for the block chain is mainly just a bunch of blobs of structured binary data called transactions. Each transaction has a list of inputs and a list of outputs, and it specifies how much value is stored inside each output. The value inside each output is just a positive integer which represents how many bitcoins are in that output. Each transaction output also has a script which determines who can unlock the output, and the typical script will contain something called a Bitcoin address. The rest of the data in the block chain, and all the software that runs on the nodes in the Bitcoin network, is designed to fulfill one purpose: it establishes a decentralized consensus on the set of unspent transaction outputs. It does this in a way that anyone can use the network, but nearly no one can modify its data maliciously.

The block chain, and the servers that maintain it, know nothing about real estate or stocks. So when someone tells you they have developed a way to represent non-bitcoin assets on the block chain, what they are saying is that they have invented a set of rules for how to interpret the data in the block chain in order to add extra information to it about asset ownership.

These rules that they invented are not enforced in the block chain. Therefore, if you are an owner of a non-bitcoin block chain asset, then you have to trust some third party to actually give value to your asset. That third party could arbitrarily change the rules of the game some day and declare that your assets are not valid, in a very similar manner to how PayPal or Coinbase can arbitrarily freeze your account. The block chain doesn't care, so the only recourse you would have is to complain loudly in public and/or file a lawsuit. There is nothing you can actually do by yourself in order to maintain control of that asset. Therefore, that kind of asset is inferior to an actual, real bitcoin, and it is not a particularly interesting thing to talk about.

The only benefit I can see to these kind of schemes is that there would be more transparency in the ownership and transfer of these assets. But you don't need the block chain to achieve that. Imagine this alternative system instead: the central authority that everyone is trusting could simply maintain a centralized ledger themselves. They could publish a new version of the ledger on their website every hour, signed with their company's PGP key. The asset holders could use ECDSA cryptography, or any kind of authentication mechanism that the company implements, in order to authenticate themselves and issue orders for transferring the asset. This kind of system is totally possible with today's technology, and it would be cheaper to implement than a block chain-based system because you wouldn't have to download tens of gigabytes of data or pay fees to Bitcoin miners.

So why does everyone keep talking about non-bitcoin assets on the block chain and writing software and protocols for it? There are people who have spent a lot more time thinking about this than I have, so maybe I am missing something. Please enlighten me in the comments.

TLDR: The bitcoin network establishes a decentralized consensus on the set of unspent transaction outputs. It doesn't know anything about non-bitcoin assets, so you'd have to trust a third party in order to actually hold such an asset. If you are trusting a third party, there is no real reason to use the block chain.

Sunday, February 15, 2015

Ruby blocks with brackets are parsed differently

In Ruby, you can write blocks using either brackets or with the do/end keywords. Check out this code that gives surprising results:


a = []
 
a.concat a.map { |b| }  # => []
 
a.concat a.map do |b|
end
# => no implicit conversion of Enumerator into Array (TypeError)

It turns out that the Ruby parser actually cares which notation you use for your blocks, and that affects which method will receive the block. In the code above, a block written with brackets gets passed to the last method in the statement. A block written with do/end gets passed to the first method, which causes the code example above to break.

You can even use both types of blocks in the same statement, and they go to different methods:


def f(x)
  puts 'f got block' if block_given?
end
 
def g(x)
  puts 'g got block' if block_given?
end
 
def h
  puts 'h got block' if block_given?
end
 
f g h { } do
end
# f got block
# h got block

I used to think that the different notations for blocks were just equivalent ways of writing the same thing, and I said that do/end should be used if and only if the block is multi-line. Now it seems like there might be legitimate reasons to break that rule, or to come up with a different rule.

Monday, September 22, 2014

Introducing RPicSim

Check out the post I recently wrote on the Pololu blog: Introducing RPicSim. It talks about a tool we made for using Ruby, RSpec, and test-driven development to aid the development of PIC microcontroller firmware.

Friday, July 11, 2014

Version 2.0.0 of minimu9-ahrs released

This week I released version 2.0.0 of minimu9-ahrs, which adds support for the MinIMU-9 v3. You can see more information on the Pololu blog.

Sunday, April 6, 2014

Introducing the Ruby ECDSA gem

I am happy to announce that I released version 1.0.0 of the Ruby ecdsa gem today. ECDSA stands for Elliptic Curve Digital Signature Algorithm. This algorithm, defined in a document called SEC1, allows you to make secure, cryptographic digital signatures of messages. The ecdsa gem is an implementation of ECDSA written almost entirely in pure Ruby.

To install the gem, run:

gem install ecdsa

One of the main purposes of the ecdsa gem is education; it is a good resource for people who want to learn about ECDSA. The ecdsa gem seems to be a lot slower than OpenSSL, but that is okay. Verifying a single secp256k1 signature with the gem takes about 280 ms on my machine.

The main reason that I made the ecdsa gem is because I wanted to do some experiments related to Bitcoin. My language of choice for experimentation is Ruby. Ruby has built-in support for ECDSA through its OpenSSL binding, but I found it frustrating to use.

Comparison to OpenSSL

Ruby's built-in OpenSSL ECDSA support is frustrating mainly because the documentation is very sparse. For example, it says on this page that you can create a new OpenSSL::PKey::EC::Point object from a "group" and a "bn". The group part is easy to figure out, but the "bn" part is not obvious at all. The "bn" stands for "big number". In general, a point can be created from a private key, which is a big number, so I would think that the "bn" argument might be the private key. Instead, the "bn" turns out to actually be a binary representation of the two coordinates of the public key, as defined in section 2.3.4 of SEC1. There was no way to figure this out from the Ruby documentation or the OpenSSL documentation; I had to do an experiment to verify it after someone on StackOverflow explained it to me.

In contrast, the Ruby ecdsa gem documentation explains the types of all its parameters and cites official documents when appropriate. Also, the classes and routines for doing cryptography are very clearly separated from the routines for encoding and decoding data from strings. All the binary formatting routines live in the ECDSA::Format module, and the parts of the gem that do actual cryptographic calculations do not depend on them.

Here is a bit of Ruby code showing how you would verify an ECDSA signature using OpenSSL and then again using the ECDSA gem:


digest =
  "\xbf\x91\xfb\x0b\x4f\x63\x33\x77\x4a\x02\x2b\xd3\x07\x8e\xd6\xcc" \
  "\xd1\x76\xee\x31\xed\x4f\xb3\xf9\xaf\xce\xb7\x2a\x37\xe7\x87\x86"

signature_der_string =
  "\x30\x45" \
  "\x02\x21\x00" \
  "\x83\x89\xdf\x45\xf0\x70\x3f\x39\xec\x8c\x1c\xc4\x2c\x13\x81\x0f" \
  "\xfc\xae\x14\x99\x5b\xb6\x48\x34\x02\x19\xe3\x53\xb6\x3b\x53\xeb" \
  "\x02\x20" \
  "\x09\xec\x65\xe1\xc1\xaa\xee\xc1\xfd\x33\x4c\x6b\x68\x4b\xde\x2b" \
  "\x3f\x57\x30\x60\xd5\xb7\x0c\x3a\x46\x72\x33\x26\xe4\xe8\xa4\xf1"

public_key_octet_string =
  "\x04" \
  "\xfc\x97\x02\x84\x78\x40\xaa\xf1\x95\xde\x84\x42\xeb\xec\xed\xf5" \
  "\xb0\x95\xcd\xbb\x9b\xc7\x16\xbd\xa9\x11\x09\x71\xb2\x8a\x49\xe0" \
  "\xea\xd8\x56\x4f\xf0\xdb\x22\x20\x9e\x03\x74\x78\x2c\x09\x3b\xb8" \
  "\x99\x69\x2d\x52\x4e\x9d\x6a\x69\x56\xe7\xc5\xec\xbc\xd6\x82\x84"

# Verifying with openssl.
require 'openssl'
ec = OpenSSL::PKey::EC.new('secp256k1')
key_bn = OpenSSL::BN.new(public_key_octet_string, 2)  # 2 means binary
ec.public_key = OpenSSL::PKey::EC::Point.new(ec.group, key_bn)
result = ec.dsa_verify_asn1(digest, signature_der_string)
puts result  # => true

# Verifying with the new ecdsa gem, version 1.0.0.
require 'ecdsa'
group = ECDSA::Group::Secp256k1
point = ECDSA::Format::PointOctetString.decode(public_key_octet_string, group)
signature = ECDSA::Format::SignatureDerString.decode(signature_der_string)
result = ECDSA.valid_signature?(point, digest, signature)
puts result  # => true

As you can see above, OpenSSL requires you to make this weird OpenSSL::PKey::EC object which represents an elliptic curve but it also holds a reference to a public key, which is a point on the curve. The object is weird because you cannot say concisely what it really is using the vocabulary of the problem domain, which is ECDSA. In contrast, the ecdsa gem uses the ECDSA::Group class to represent elliptic curves and the ECDSA::Point class to represent points on those curves.

You will also see that OpenSSL's verification method takes an ASN1 string directly, instead of taking a more abstract object that represents a signature. As a result, it is not easy for the user to inspect the internal structure of that signature, which actually consists of two big numbers. In contrast, the ecdsa gem takes a ECDSA::Signature object, so you are not forced to use any particular binary format to represent the signature and it is easier to see what is going on.

Thursday, January 30, 2014

What Ruby does at parse time

Yesterday at the Las Vegas Ruby Group, someone was surprised that Kernel#global_variables will list global variables that have not been used yet. The same thing is actually true for symbols and methods, as shown here:


p Symbol.all_symbols.map(&:to_s).grep(/neve/)
    # => ["never", "never_runs", "$never_global", "never_sym"]

p global_variables.grep(/neve/)  # => ["$never_global"]

def never_runs
  $never_global
  :never_sym
end

The first line of this program tells us that Ruby has already found four things. It found a symbol :never which apparently comes from the Ruby interpreter since we never defined it. It has found the name of the method in our program even though we haven't defined that method yet. It found a symbol we used in that method even though we are never going to call the method. Similarly, it found a the name of a global variable we were never going to use.

The second line just reproduces the original thing that happened at the Ruby group, and shows that Ruby is aware of "$never_global" as an actual global variable and not just a symbol.

To understand this, you need to know that Ruby does not simply run a source file one line at a time:

  • First, Ruby parses the syntax of all the code in the file.

  • Later, Ruby runs the code in the file.

We already intuitively know this because whenever we make a syntax error in a file, we can see that Ruby just reports a syntax error and does not run any of the other code in the file. This means it is parsing the entire file before running any of it.

So it shouldn't be surprising that the Ruby interpreter is aware of symbols and global variables before they are used; it just tells us that those things are probably recorded at parse time instead of run time. Some more evidence for this conclusion can be found in the fact that the Ruby interpreter has lots of symbol table code in parse.y.

Most of the time you can just pretend that Ruby processes your file one line at a time, but this is a case where the details of its behavior reveal a little bit about how it actually works.

The code in this blog post was executed with Ruby 2.0.0. Ruby 1.8.7 had the same results except the symbol "never" was not present.

Saturday, November 30, 2013

Running JRuby under JDB in Windows

I am working on some JRuby code that calls third-party Java libraries. The Java libraries were behaving oddly so I wanted to run them under JDB, the Java Debugger, so I can step through them line by line and inspect important values.

In Linux and Mac OS X, I think you should be able to do this by passing the --jdb option to JRuby when you run it. In Windows, JRuby does not support that option, but I was able to figure out how to do it anyway. Here is the command I used:

"C:/Program Files/Java/jdk1.7.0_45/bin/jdb.exe" -classpath "C:/jruby-1.7.4/lib/jruby.jar" -Djruby.home="C:/jruby-1.7.4" org.jruby.Main

The -classpath argument to JDB allows it to find the jruby.jar file, which defines jruby's org.jruby.Main class, which is the class to start if you want to use JRuby. The -Djruby.home option is recognized by JRuby and allows it to find its libraries and gems. If you want to pass any arguments to JRuby, then you can add them on to the end of this command, after org.jruby.Main. For my situation, I wanted to run RSpec so I added -S rspec:

"C:/Program Files/Java/jdk1.7.0_45/bin/jdb.exe" -classpath "C:/jruby-1.7.4/lib/jruby.jar" -Djruby.home="C:/jruby-1.7.4" org.jruby.Main -S rspec

Once you have started JDB successfully, you should see a message like "Initializing jdb ..." and a command prompt on the next line. My basic workflow is that I would figure out what class and method I want to inspect, and then I would add a breakpoint for it by running a command like this:

stop in com.example.namespace.ExampleClass.exampleMethod

Then run the run command. The JRuby and Java code will run until the specified breakpoint is hit, at which point the debugger will stop and let you interact with it again. Here are some more common commands I use:

  • where prints a full stack trace. These tend to be very long because of the internals of JRuby but if you scroll to the top you can see what part of the Java code you are in.
  • step advances to the next line of code, stepping into method calls if they are present.
  • next advances to the next line of code, skipping any method calls that might be present.
  • print EXPR evaluates the Java expression EXPR and prints the result. For example, if there is a local variable named "foo" you can type print foo to see its value.
This works in both the normal Command Prompt that comes with Windows and also the Git Bash shell that comes with Git. There are a couple more things that would be nice to have:
  • It would be nice to have a JDB command that prints out the current filename, method name, and line number. You get this info whenever you run next or step, but sometimes that output ends up really far up in my buffer and I would like a way to quickly see that information again.
  • It would be nice to do this inside some kind of an graphical interface or IDE. Has anyone gotten that working?
By the way, I think JDB is only for debugging Java code. If you want to debug JRuby code there are other tools for that. One that worked for me is the ruby-debug gem, even though people claim it is not maintained.