An introduction to Bitcoin

I held a little intro talk about Bitcoin last night at a local Linux meetup kinda thing. It was a light technical description of what the system is and how it works.

Here are the slides and their LaTeX sources. That is all.

Blind signature basics

I'm starting work on my diploma thesis this month. The exact topic isn't set in stone yet, but it will be something crypto. If everything goes dreamy-awesome, I'll find something nice to write about lattice-based blind signatures or somesuch. Background:

• Blind signatures are used for e-cash. I'm fascinated with e-cash.
• Lattice-based methods are candidates for quantum-resistant systems. Appearently there's lots of current research going on.
• I've done some lattice theory at Charles University in Prague. Never thought I'd see it again, so wouldn't that be something.
• There's zero knowledge in there somewhere. Another fascination.

So, time to sum up the basics. As far as my history serves, David Chaum invented blind signatures in the 80s for electronic voting but nobody wanted to buy that, so he also invented electronic cash. Then he got really paranoid and didn't sell it either. Real quick summary. ;)

Anyway…

The principle is to mix whatever you want signed (electronic voting ballot, 100 EUR banknote) with a random blinding factor and divide that out only after Trent (your government, bank) has signed. Thus Trent cannot recognize and connect the note to you when it comes back to him later.

The classic algorithm is based on RSA and is painted up fast. Unfortunately, my awesome markup language still has no fancy math support so you have to live with ASCII art:

m = message to be signed
e = public "encryption" (i.e. verification) exponent
n = public modulus
d = secret "decryption" (i.e. signing) exponent
k = blinding factor (just a random number)

x^(de) = x^(ed) = x (mod n)         -- RSA property

Alice prepares:  mk^e               -- blinded message
Trent signs:     (mk^e)^d = m^d k
Alice unblinds:  m^d k / k = m^d    -- signed message
Bob can check:   (m^d)^e = m

One might think that signing something completely blindly might be a bad idea. After all, a bank needs to know the value of the note it is signing. To ensure any desired property of the signed document, Trent can require a cut-and-choose step. In this case Alice must give him n different but equivalent messages. He chooses one of them and asks Alice to unblind all the others. Trent signs the remaining blinded one if the others satisfy the desired property. Alice's chance to cheat of 1:n can be made unattractive by attaching a suitable penalty.

Making a stupid little time waster with Javascript

Awesome!

I used the weekend to code a little memory game in Javascript. Apart from being pointless and annoying (especially if your visual memory sucks as much as mine), I think it turned out lovely!

I was hoping to gain some experience with user-facing Javascript from it, as previous excursions into the misunderstood programming language have been minimal in one way or another. So, this time I got to use some actual objects. Structured data, woo!

I poked around the design space a little to see what was up with Crockford's take on prototypal inheritance vs. others' assertions that his dislike of the new-operator was ill-founded. You can look at the code to see what I settled on in this instance, but maybe I'll leave that discussion for another post. Suffice it to say, it's a bit of a mish-mash but I'm sure it will crystallize nicely.

Oh yeah, and this is going onto my side project (I desperately needed one!) site kompilierfreizeit.de. I'm going to collect some nice other time wasters there, but won't say it out too loud, yet. That would just make me feel obligated…

Have fun!

Tron (1982) awesomenesses

I just (re)watched the original Tron. Highlights:

• Adam, Tron's user, has the phrase gort klaatu barada niktu posted up in large letters on his cubicle wall. This is not a reference to Army of Darkness (1992, duh) but to The Day the Earth Stood Still. I should watch that.
• The screen in the control room of bad guy's ship shows pac-man in one scene (see image above).
• The image of Moses in Southpark episode Jewbilee (s03e09) is modeled after the Master Control Program (see image below).
• Spotted Kenneth Perlin in the credits.

carpalx keyboard layouts for X11

carpalx is a program for the algorithmic evaluation and optimization of keyboard layouts. The site is a wealth of information and adds a nice scientific angle to the endless discussion of alternatives to the QWERTY layout. First of all it provides evaluations and comparisons of several popular layouts, including Dvorak and Colemak. In addition it describes a number of layouts generated by the program, optimized to certain parameters and side conditions. Within the given effort metric, they improve significantly over all alternatives.

carpalx' fully optimized layout with Colemak lettermask, QGMLWB.

I've created an XKB definition file that allows the five featured layouts to be used with X11. In fact, it also includes the worst layout TNWMLC which maximizes the effort metric. Don't use that, though.

To install, copy carpalx.xkb to your XKB symbols directory (path my differ slightly)

$ cp carpalx.xkb /usr/share/X11/xkb/symbols/carpalx

and add the following lines to /usr/share/X11/xkb/symbols.dir:

-dp----- a------- carpalx(qgmlwb)
--p----- a------- carpalx(qgmlwy)
--p----- a------- carpalx(qfmlwy)
--p----- a------- carpalx(qwkrfy)
--p----- a------- carpalx(qwyrfm)
--p----- a------- carpalx(tnwmlc)

Now it should be possible to load the layouts with, e.g.

$ setxkbmap carpalx                            # defaults to QGMLWB
$ setxkbmap -layout carpalx -variant qwkrfy    # to select other variants

Technically, the following files should also be updated:

/usr/share/X11/xkb/rules/xorg.lst
/usr/share/X11/xkb/rules/xorg.xml

For the time being I couldn't be bothered, but I think that's necessary if the layouts are to show up in Gnome and KDE control panels.

PS: Dear search engines, X11 means X Window System, means this lets you use carpalx layouts on Linux (desktops). Or FreeBSD for that matter.