Just a little bit more Bitcoin trouble

There has been so much tumult in bitcoin and cryptocurrency over the past few days! Interest and concern extends beyond online communities. Motives vary.

Bitcoin miner GUI running Windows 7

Anonymous and decentralized

There are two conceptual pillars of trust that uphold bitcoin as being superior to fiat currency. (The fiat currency of reference is primarily the US dollar. Why? Because the US dollar is the world’s reserve currency, for now.)

The first is anonymity. US dollars held as cash are bearer instruments. Ownership and use is anonymous, but only until one wants to use them for commercial transactions of significant size as defined by anti-money laundering rules. Bitcoin does have some anonymity shortcomings, as transactions on the blockchain are actually pseudonymous, but there may be tractable remedies. Further details have been widely covered elsewhere.

The second conceptual pillar of bitcoin is decentralization. The US dollar is highly centralized. As ideological (but not market) confidence in the dollar diminishes, the appeal of an apolitical, alternative currency increases, especially one that is a fungible store of value.

All markets are game theoretic. Bitcoin is too.  I really wish we could ask Professor John Nash what he thinks of bitcoin! Nash wrote a pleasant, accessible article that described bitcoin-like currency, titled “Ideal Money” a few years ago.

Did Mathematician John Nash Help Invent Bitcoin? http://t.co/AVNLfSW5bZ

— Egan J Chernoff (@MatthewMaddux) June 13, 2015

I mention game theory because monopolists and cartels can assert control over bitcoin production. This is playing out right now.

Centralization of bitcoin

Currently, Bitcoin’s most acute concern is loss of decentralization. This is due to the documented, persistent existence of a 51% majority mining pool controlled by gHash.io. gHash is owned and operated by private entity cex.io. gHash’s market dominant behavior was noted in March 2014, however the situation was transient. That has since changed.

PDF history and something special from Adobe

Part One: PDF history 

PDF is a formal open standard, ISO 32000. It was invented by Adobe Systems 17 years ago.

PDF = Portable Document Format

History of the PDF by Adobe Systems

The image links to a pleasant interactive timeline of Adobe Systems and its role in the development of the PDF. The chronology is in Flash, and thankfully free of any video or audio. Read more about Adobe Systems role in the history of PDF file development.

PDF files are more versatile than I realized, and

• are viewable and printable on Windows®, Mac OS, and mobile platforms e.g. Android™
• can be digitally signed
• preserve source file information — text, drawings, video, 3D, maps, full-color graphics, photos — regardless of the application used to create them

Additional PDF file types exist, including PDF/A, PDF/E and U3D. All are supported by Adobe software. 

Economic Models for Turbulent Times Part I

Crust is an algorithm for reconstructing surfaces of any topology. In other words, it is a computational method for digitally rendering any 2-D shape, using data in three-dimensional space as input.

Strange topology at MIT

Such methods garner a lot of attention these days. Here are a few reasons why: Graphical simulation models are increasingly needed for visualization and testing purposes in the field of particle physics. World of Warcraft and Second Life rely heavily on computationally intensive computer graphics, and scalable distributed systems. The U.S. economy is a highly complex system, partly guided by the results of mathematical models.

Crust was developed as a collaborative effort between two staff scientists at Xerox PARC and a researcher at MIT.

None of this happened recently. In fact, Crust hasn’t been semantically linked with the word “new” since its debut at the 1998 ACM SIGGRAPH Conference.

What is so special about Crust?

The Crust algorithm is special because it has certain features uncommon in most quantitative models, yet highly sought after.

First, Crust offers results with “provable” guarantees. Given a good sample from a smooth surface, Crust’s results are guaranteed. That is, Crust guarantees that its output is topologically correct, converging to the original surface with increasing faithfulness depending on the input data density.

Graphical computation with Crust: Voronoi Piggy

The third member of the Crust project team was Manolis Kamvysellis, a Ph.D. student at MIT. Manolis did much of the implementation and testing work—he wrote a short-form version, A New Voronoi Based Reconstruction Algorithm [PDF], of the original ACM journal publication. Happily, he had the good sense to demonstrate Crust with this fine pink pig! Let’s do the same.

Highly efficient porcine reconstruction in three dimensions

Recall that Crust’s criteria for acceptable sample size is determined dynamically . A single topological surface, such as Piggy, may have very detailed surfaces, with high data density. Observe this near Piggy’s ears and snout. Other areas like the hindquarters are quite featureless.

Crust dynamically adjusts its smallest acceptable sample size accordingly. Even minimally detailed surfaces such as Piggy’s lower hind quarters above the hooves can be reconstructed accurately.

To be continued…

Random Numbers in Java

This post is about alternatives to the java.util.Random class, the most commonly used method to generate random numbers in Java.

Random: Playing the odds in Ancient Rome Osteria della Via de Mercurio

 java.util.Random

This class generates “random enough” values, which are described as having an informal level of randomness. Such numbers have a superficial appearance of randomness to an observer, usually a human observer, not a machine. These are considered low-quality random numbers. They should never be used in any security application.

True randomly-generated numbers must have the following characteristics:

• Any number is equally likely to be generated on every iteration. This is also known as a uniformly distributed series of numbers.
• The second criterion follows directly: No dependency exists between successive numbers as they are generated.

Alternatives to better match your random needs

Neil Coffey of Javamex describes three alternative random number generation methods. Each approach continues to use class java.util.Random, while replacing the underlying algorithm. The first, called the XORShift generator, produces medium-quality random numbers very quickly, with only a single state variable and very simple code. This method is very well suited to J2ME games.

The next algorithm generates much higher-quality random numbers. It is a combined generator, using two XORShift generators of the sort described above. Mr. Coffey provides the code and explanation for the algorithm. This combined XORShift yields good-quality random numbers. It is suitable for non-gambling games and simulations, although it runs slightly slower than java.util.Random.

A cryptographic quality random number generator should have the following properties:

1. It should be impossible to predict prior and future numbers from any number generated;
2. The numbers should have no discernible biases;
3. The generator has a large period;
4. The generator can seed itself at any position within that period with equal probability.

A cryptographically secure random number generator is appropriate for security applications such as producing a web-server session id or picking encryption keys. Very high-quality random numbers are generated using java.security.SecureRandom as the replacement for java.util.Random. The trade-off in quality versus CPU cycle consumption is hardly surprising.  java.security.SecureRandom runs 20 to 30 times slower than any of the other algorithms.

Relative comparison between the methods

Here is a very simplified way of understanding the difference between each algorithm.

Let’s say that we need to generate a 128-bit encryption key. java.security.SecureRandom actually picks from a pool of 2 raised to the 127th power number of possible keys. Of course java.util.Random can also be used to generate a 128-bit key. However, the values will be selected from a smaller pool of numbers, on the order of 2 raised to the 47th power number of possible keys. This is because java.util.Random has a much shorter period, equal to 2 raised to the 48th power.

The single XORShift generator method falls between the two, as it has a slightly longer period, of 2 raised to the 64th power. The combined XORShift generator approach extends the period a bit further.

Note than neither java.util.Random nor either of the XORShift generators are seeded randomly. This is why java.security.SecureRandom, with a machine-generated and much more truly random random seed, is superior.

* The machine-generated random seed is what is called entropy in random number generators.