Libbitcoin: bx seed

Today, I would like to write about a project I’ve been following for some time now, but had simply not the capacity to devote more attention to it: libbitcoin.org, which is a

C++ Bitcoin toolkit library for asynchronous apps.

As far as I’m informed, it was originally conceived by the now (in)famous Amir Taaki with the intention to provide an alternate implementation to Bitcoin Core.

When I’ve checked the source code on GitHub.com/libbitcoin I was simply blown away: An extremely well written piece of software, which splits the various required functionalities – to make Bitcoin work – into cleanly separated commands, adhering to the Unix philosophy of doing a single thing and doing it right!

Upon further investigation, I realized that an huge amount of work has been performed by Eric Voskuil: Based on my own research, it seems like that he took Amir’s ingenious work and turned it into a nice piece of well organized software!

Alright, enough of talking about people. Now, let’s get down to business: The point of this article is to start a series of posts about each individual command which have been implemented using libbitcoin in general and libbitcoin-explorer in particular, where the latter provides the bx binary, which in turn allows to access the various commands. Here is a list of them:

hsk81 ~ $ bx help

Usage: bx COMMAND [--help]

Version: 4.0.0

Info: The bx commands are:

address-decode
address-embed
address-encode
base16-decode
base16-encode
base58-decode
base58-encode
base58check-decode
base58check-encode
base64-decode
base64-encode
bitcoin160
bitcoin256
btc-to-satoshi
cert-new
cert-public
ec-add
ec-add-secrets
ec-multiply
ec-multiply-secrets
ec-new
ec-to-address
ec-to-ek
ec-to-public
ec-to-wif
ek-address
ek-new
ek-public
ek-public-to-address
ek-public-to-ec
ek-to-address
ek-to-ec
fetch-balance
fetch-header
fetch-height
fetch-history
fetch-public-key
fetch-stealth
fetch-tx
fetch-tx-index
fetch-utxo
hd-new
hd-private
hd-public
hd-to-ec
hd-to-public
help
input-set
input-sign
input-validate
message-sign
message-validate
mnemonic-new
mnemonic-to-seed
qrcode
ripemd160
satoshi-to-btc
script-decode
script-encode
script-to-address
seed
send-tx
send-tx-node
send-tx-p2p
settings
sha160
sha256
sha512
stealth-decode
stealth-encode
stealth-public
stealth-secret
stealth-shared
token-new
tx-decode
tx-encode
tx-sign
uri-decode
uri-encode
validate-tx
watch-address
watch-stealth
watch-tx
wif-to-ec
wif-to-public
wrap-decode
wrap-encode

Bitcoin Explorer home page:

https://github.com/libbitcoin/libbitcoin-explorer

As you see there are around 80 commands, hence I’ve some decent amount of work about understanding, dissecting and writing about them. The very first command I’d like to talk about is bx seed:

hsk81 ~ $ bx help seed

Usage: bx seed [-h] [--bit_length value] [--config value]                

Info: Generate a pseudorandom seed.                                      

Options (named):

-b [--bit_length]    The length of the seed in bits. Must be divisible by
                     8 and must not be less than 128, defaults to 192.   
-c [--config]        The path to the configuration settings file.        
-h [--help]          Get a description and instructions for this command.

So, it generates a pseudorandom seed, which means it returns a random looking number of a given bit-length:

hsk81 ~ $ bx seed
a6943c12a9e7fabd8b96ad15f6b1a24a2b7fba2d434cbbba

Each time you run it, you should get something else. Let’s have a deeper look into the code at seed.cpp:

console_result seed::invoke(std::ostream& output, std::ostream& error)
{
    const auto bit_length = get_bit_length_option();

    if (bit_length < minimum_seed_size * byte_bits ||
        bit_length % byte_bits != 0)
    {
        error << BX_SEED_BIT_LENGTH_UNSUPPORTED << std::endl;
        return console_result::failure;
    }

    const auto seed = new_seed(bit_length);

    output << base16(seed) << std::endl;
    return console_result::okay;
}

So, we see that upon doing some checks, the new_seed function with the bit_length argument is invoked delivering our seed, which then in turn is encoded using based16 and send to the output. That was the easy part! Let’s dissect new_seed in utility.cpp:

data_chunk new_seed(size_t bit_length)
{
    size_t fill_seed_size = bit_length / byte_bits;
    data_chunk seed(fill_seed_size);
    random_fill(seed);
    return seed;
}

Alright, so apparently random_fill is our work horse here, which in turn delegates to pseudo_random_fill in random.cpp:

void pseudo_random_fill(data_chunk& chunk)
{
    std::uniform_int_distribution<uint16_t> distribution(0, max_uint8);

    for (auto& byte: chunk)
        byte = static_cast<uint8_t>(distribution(get_twister()));
}

Now, it’s getting interesting: Apparently a uniform distribution over uint8 is used to query the random numbers and to fill the chunk. The get_twister function seems to deliver a seed:

static std::mt19937& get_twister()
{
    const auto deleter = [](std::mt19937* twister)
    {
        delete twister;
    };

    static boost::thread_specific_ptr<std::mt19937> twister(deleter);

    if (twister.get() == nullptr)
    {
        // Seed with high resolution clock.
        twister.reset(new std::mt19937(get_clock_seed()));
    }

    return *twister;
}

Ah, we are getting closer to what’s really going on: Apparently a high resolution clock is used to seed the uniform distribution. The rest around it is just some technical detail w.r.t. pseudo-random number generation. And what does get_clock_seed do?

static uint32_t get_clock_seed()
{
    const auto now = high_resolution_clock::now();
    return static_cast<uint32_t>(now.time_since_epoch().count());
}

Alright, here we have it: The current time in high resolution is the seed! So this means, we take the current time which has elapsed since about 1970 measure it really really well, use that number as a seed for a pseudo-random generator and pick multiple uint8 numbers uniformly at random till we have our final seed of desired length.

What does that mean? Well it means, that you should rather treat your current clock as a secret, since otherwise people could guess the result of bx seed, which might actually be not very difficult, if your system uses the ntp time synchronization protocol.

But before you start jumping around and start screaming security hole, please realize that that’s the nature of pseudo-random generators: If you enter the same seed then you will get the same result.

Hence my suggestion would be to make it really hard for outsiders to determine when exactly your bx seed commands are invoked, which in all practicality should be the case anyway when you disallow unauthorized access to your machine.

You could also run bx seed in batch at some point in time un-guessable by a potential adversary and store the results securely and safely for later retrieval. But you should asses the risk of the seeds being stolen versus the risk of some all observing adversary guessing the exact time of invocation. My gut tells me that pre-calculating the seeds would actually be less secure, than asking for them on demand.

So how does bx seed scale? It should take about 10 times more time, if you run it 10 times in a row, hence a linear dependency:

As you see this is indeed the case. Here is the code I used to produce the corresponding data:

hsk81 ~ $ time for i in $(seq 1) ; do bx seed > /dev/null ; done

real 0m0.013s
user 0m0.010s
sys 0m0.000s

hsk81 ~ $ time for i in $(seq 10) ; do bx seed > /dev/null ; done

real 0m0.142s
user 0m0.107s
sys 0m0.017s

hsk81 ~ $ time for i in $(seq 100) ; do bx seed > /dev/null ; done

real 0m1.225s
user 0m0.927s
sys 0m0.190s

hsk81 ~ $ time for i in $(seq 1000) ; do bx seed > /dev/null ; done

real 0m13.423s
user 0m10.227s
sys 0m1.763s

hsk81 ~ $ time for i in $(seq 10000) ; do bx seed > /dev/null ; done

real 1m53.335s
user 1m23.380s
sys 0m11.900s

So, we’re at then end of our investigation: I hope, that I could give you a rather in depth technical view on bx seed and I’m looking forward to talk about bx ec-new in my next post.

About philosophers and illogical men

Xkcd.com: Philosophy

Just recently, I’ve been reading a beautiful book written by Charles Petzold titled Code: I’m still at chapter eleven “Gates (not Bill)”, but just the chapter before, namely “Logic and Switches” had an intriguing problem described:

$\eqref{eq:dcb6}$ All philosophers are logical; and $\eqref{eq:e6e9}$ an illogical man is always obstinate (stubborn).

Well, these are two premises, but what would the conclusion be? According to Charles it is:

$\eqref{eq:e1c5}$ Some obstinate people are not philosophers.

This is quite counter-intuitive, isn’t it? Well, I wanted see the proof! So I sat down, and translated all statements into predicate logic. Well, the first premise goes like this:

$$\begin{equation}\label{eq:dcb6} \forall{p}\in\mathbb{P}:\textbf{logical}(p) \end{equation} $$

You can read the above statement $\eqref{eq:dcb6}$ like this: “For all $p$ in $\mathbb{P}$ it holds that $p$ is logical”, where $p$ stands for a single philosopher and $\mathbb{P}$ stands for the set of all philosophers. This means we can read the whole thing more naturally like this: “For each philosopher, it holds that he (or she) is logical”, or shorter: “All philosophers are logical.”

Now, let’s have a look at the second premise:

$$\begin{equation}\label{eq:e6e9} \forall{m}\in\mathbb{M}:\neg\textbf{logical}(m) \implies\textbf{obstinate}(m) \end{equation} $$

So, let’s read it again: For all $m$ in $\mathbb{M}$ it holds, that if $m$ is illogical, then $m$ is obstinate, simply meaning that “all illogical men are always obstinate.” Now, let’s translate the conclusion:

$$\begin{equation}\label{eq:e1c5} \neg\forall{m}\in\mathbb{M}:\textbf{obstinate}(m) \land m\not\in\mathbb{P} \end{equation} $$

which means that “not for all $m$ among all men $\mathbb{M}$, it holds that $m$ is obstinate and $m$ does not belong to the set of philosophers $\mathbb{P}$”. This rather very complicated statement can be simplified to: “Some obstinate men are not philosophers!”

Good, now that we have translated perfectly understandable English into completely incomprehensible predicate logic, let’s do some magic to derive from the premises $\eqref{eq:dcb6}$ and $\eqref{eq:e6e9}$ the conclusion $\eqref{eq:e1c5}$. But before that we need to state another rather obvious fact, namely that “all philosophers are men, but not all men are philosophers:”

$$\begin{align}\label{eq:49fe} \mathbb{P}\subset\mathbb{M}\tag{$\star$} \end{align} $$

Above, we say that the set of philosophers $\mathbb{P}$ is a subset of all men $\mathbb{M}$, which is the same as declaring that all philosophers are men (but not necessarily the other way around).

Derivation of the conclusion ¶

Based on the premises $\eqref{eq:49fe}$ that all philosophers are men, and $\eqref{eq:dcb6}$ that they are logical, we can deduce that there are some men who are not philosophers, hence illogical (where we assume based on $\eqref{eq:dcb6}$ that only philosophers can be logical):

$$\begin{equation}\label{eq:95af} \exists{m}\in\mathbb{M}:m\not\in\mathbb{P} \vdash \neg\textbf{logical}(m) \end{equation} $$

Further, since all illogical men tend to be obstinate, we can derive that there exists also an illogical one, who is indeed obstinate:

$$\begin{equation}\label{eq:aa48} \exists{m}\in\mathbb{M}:\neg\textbf{logical}(m) \implies\textbf{obstinate}(m) \end{equation} $$

which we can reformulate by using the fact, that “$\neg{a}$ implying $b$” ($\neg{a}\implies{b}$) is equivalent to “$a$ or $b$” ($a\lor{b}$):

$$\begin{equation}\label{eq:1c8c} \exists{m}\in\mathbb{M}:\textbf{logical}(m) \lor\textbf{obstinate}(m) \end{equation} $$

Hence apparently, there is a man who is logical or obstinate! Now, if we combine $\eqref{eq:95af}$ and $\eqref{eq:1c8c}$ we get:

$$\begin{equation}\label{eq:a4ba} \exists{m}\in\mathbb{M}:\neg\textbf{logical}(m)\land\bigg{(} \textbf{logical}(m)\lor\textbf{obstinate}(m)\bigg{)} \end{equation} $$

which is equal to — derived by pulling the left hand side into the parentheses and then simplifying $\neg\textbf{logical}(m)\land\textbf{logical}(m)$ to $\bot$, namely false:

$$\begin{equation}\label{eq:c038} \exists{m}\in\mathbb{M}:\bot\lor\bigg{(} \neg\textbf{logical}(m)\land\textbf{obstinate}(m)\bigg{)} \end{equation} $$

which is equal to — derived by dropping $\bot$ in the or statement:

$$\begin{equation}\label{eq:8a48} \exists{m}\in\mathbb{M}: \neg\textbf{logical}(m)\land\textbf{obstinate}(m) \end{equation} $$

which is equal to — according to $\eqref{eq:dcb6}$:

$$\begin{equation}\label{eq:b3b1} \exists{m}\in\mathbb{M}: \textbf{obstinate}(m)\land m\not\in\mathbb{P} \end{equation} $$

So $\eqref{eq:b3b1}$ means that “some obstinate man are not philosophers!” Quod erat demonstrandum. $\blacksquare$

Quantum Chance: Non-locality – Part #1

I had recently the privilege to enjoy Nicolas Gisin’s book “Quantum Chance: Non-locality, Teleportation, and Other Quantum Marvels”. It was a tough reading (as promised by the author), but a very eye opening experience!

Here, I’d like to focus on the non-locality aspect, and investigate especially the (in)famous Bell’s Game: It’s rather a mind-boggling thought experiment, which has later on been tested successfully by physicists.

Quite frankly, I don’t want to claim to have fully understood the whole book. I’m merely a computer scientist, who is interested in grasping what these crazy physicists have been up to recently: The whole point of this post is to clarify my own mind by forcing myself to go through the experiment point by point, while not committing blatant mistakes.

Bell’s Game: gorilla or girl? ¶

So, what is this whole game about? Well, it’s not your everyday game; that I can promise you. But to have a more everyday approach to the whole experiment, let’s think of it as a pair of very special gambling devices in a casino:

One day the brothers Ahmed and Mehmed enter the casino, with the strong determination to enjoy a sinful night and get rich in the process. They check Roulette, Black Jack and all the other fancy games, but since they painfully know from experience that somehow the house seems to always win – despite strong claims of fair play – they refuse to play those games.

Then Ahmed discovers a pair of floating spheres - both of them translucent - in the corner of the casino: Neither of them seems to be connected to the ceiling nor to each other, but they simply seem to be suspended in midair! How can this be? Ahmed asks Mehmed: “Yaw, how come that these orbs are floating midair without falling down? Tell me, you’re the physicist here!”

Dr. Mehmed explains to Ahmed with a grin on his face: “Aah, my silly brother: You may have graduated from the number one Computer Science department in the world”, which by the way would be at ETH Zurich in Switzerland, “but when it comes to matters of reality you are utterly lost! Don’t you see that these spheres are made of glass and kept in place thanks to a strong and absolutely steady stream of air from below?”

Ahmed responds: “I see, now I get it! But my cherished brother, I’m not as much of an idiot as you would like to think of myself, alright? Look, there is a scanner embedded into the orbs and when I put my hand onto one it either turns pitch black or marble white. Isn’t that interesting?”

Mehmed is confused: “Indeed very much so! But how do you win or lose this game? Look, independent of which hand I use, the right or the left one, the sphere seems to turn completely randomly black or white. What is the point?”

Ahmed confirms: “You’re right! My orb is acting exactly the same way. But why would they put such a useless game in a casino?” But then he has an idea: “Just wait a minute. What if we touch the orbs at the same time? Maybe then something will happen!”

So, they both touch their respective orbs with their left hands. Ahmed’s orb turns black, while Mehmed’s sphere turns also black. The whole casino starts flashing, and a ravishing girl materializes between the orbs. The brothers cannot believe their eyes and Mehmed asks her: “Amaneen! What’s going on? Who are you?”

The girl responds: “My name is Hooriyeh, and I came to congratulate both of you: You just won one golden ruby. Her you go!” And flip, she’s gone.

Ahmed cheers: “Uy uyyyh, can you believe that? Let’s try it again. Maybe next time she’ll come with a sister of hers and we’ll force them to stay!”

So with greed they touch the spheres again, both of them again with their left hands. But this time one of the orbs turns black, while the other one turns white: Immediately a huge and hairy gorilla materializes and groans: “My name is Hanumaan, and I came to punish you for your sins!” and it starts immediately to whip them without mercy. After some time, which feels like an eternity to the poor brothers, the gorilla vanishes into thin air, but does not take the golden ruby away!

Both brothers get very upset, and complain to the casino manager Zoltaan: “What kind of a violent game is this? We’ll sue you!” But the manager is unmoved, and points out: “When the girl appeared, you were not so upset! I’m going to explain to you now the rules of the game, and then you can decide yourself if you want to continue playing:”

• Rule #1: “If at least one of you two brothers touches the orbs with a left hand, and both orbs turn the same color, Hooriyeh will appear and give you a golden ruby.”

• Rule #2: “If both of you brothers touch the orbs with your right hands, and the orbs color themselves differently, again Hooriyeh will appear with a golden ruby.”

• Rule #3: “In all other cases you will be whipped by Hanumaan. But the gorilla will never take your golden rubies away. If after 400 trials you manage to collect 300 or more rubies, you can marry Hooriyeh and her sister. Otherwise, you’ll be enslaved by Hanumaan for life!”

The brothers are terrified by the possibility of serving a gorilla and potentially be whipped for the rest of their lives. Ahmed speaks: “Come Mehmed, this game is very weird! Let’s switch to roulette.”

However, Mehmed – still a bachelor – cannot silence the masochistic physicist inside himself, and starts unconsciously to calculate the probabilities of winning and losing…

What do you think? Will they stop playing the game, or will they risk everything and potentially get married to two ravishing sisters? It’s a tough choice to make!

TypeScript Decorators: @buffered

There are many circumstances, where a developer desires to ignore subsequent invocations of a function, except the last one. For example, you may want to ignore a crazy user’s high speed clicking, till he stops doing so: Only the very last click should cause an action.

But how do we define last in this context? Well, a simple way to do it, is to buffer all invocations of a function, and then invoke only the very last one, after which (for a certain time window) no such invocation is triggered by the manic user.

For example, I could put the buffer threshold to 200 milli-seconds: This will cause very fast clicks to be interpreted as a single click, but any two subsequent clicks, which are apart by more than 200 milli-seconds, will be interpreted as two separate clicks. Let’s have a look at a toy example:

import {buffered} from "./buffered";

class App {
    public nilHundredMsAgo() {
        console.log('[000-ms-ago]', new Date().toISOString());
    }
    @buffered
    public twoHundredMsAgo() {
        console.log('[200-ms-ago]', new Date().toISOString());
    }
}

let app = new App();
app.nilHundredMsAgo();
app.twoHundredMsAgo();

If we run the example we get:

$ npm start
[000-ms-ago] 2016-08-02T11:20:50.463Z
[200-ms-ago] 2016-08-02T11:20:50.667Z

As you see above their is a time difference of at least 200 milli-seconds, which confirms that the App.twoHundredMsAgo method has been successfully buffered. Let’s extend the above example:

import {buffered, IBufferedFunction} from "./buffered";

class App {
    public nilHundredMsAgo() {
        console.log('[000-ms-ago]', new Date().toISOString());
    }
    @buffered
    public twoHundredMsAgo() {
        console.log('[200-ms-ago]', new Date().toISOString());
    }
    @buffered(600)
    public sixHundredMsAgo() {
        console.log('[600-ms-ago]', new Date().toISOString());
    }
}

let app = new App();
app.nilHundredMsAgo();
app.twoHundredMsAgo();

let fn:Function = app.sixHundredMsAgo;
for (let i = 0; i<256; i++) fn();
let bn = <IBufferedFunction>fn;
bn.cancel();

And this time, if we run the extended example we get:

$ npm start
[000-ms-ago] 2016-08-02T11:23:59.159Z
[200-ms-ago] 2016-08-02T11:23:59.362Z

This looks like the previous output from before! What happened at the 256 different invocations of App.sixHundredMsAgo? Well, they got canceled because of which none of the invocations produced any time stamp.

Accessing the cancel function is a little awkward, since the corresponding method is required first to be converted to a Function and then again to a IBufferedFunction, which has cancel declared. But since it is expected that cancelling a buffered method is not to be used that often, we can live with the way to access cancel.

Further, please also note that above we used @buffered(600), to change the default time window from 200 to 600 milli-seconds. Alright, let’s have a look at a final and more realistic example:

/// <reference path="lib/jquery/index.d.ts" />
import {buffered} from './buffered';

class App {
    public constructor() {
        $('#my-button').on('click', this.onClick.bind(this));
    }

    @buffered
    public onClick(ev:MouseEvent) {
        console.log('[on:click]', ev);
    }
}

let app = new App();

As you see above, by simply decorating the onClick handler with @buffered we can fend off crazy users, who have lost their minds and became click-o-maniacs! Please also note, that we used jQuery to subscribe the buffered handler to click mouse events.

Finally, here is the magic that enables us to use the @buffered decorator:

export interface IBufferedFunction extends Function {
    cancel:Function;
}

export function buffered(
    ms:number):Function;
export function buffered(
    target:any, key:string, descriptor?:PropertyDescriptor):void;
export function buffered(
    arg:number|any, key?:string, descriptor?:PropertyDescriptor
):Function|void {
    if (typeof arg === 'number') {
        return _buffered(arg);
    } else {
        _buffered(200)(<any>arg, key, descriptor);
    }
}

function _buffered(ms:number) {
    return function (
        target:any, key:string, descriptor?:PropertyDescriptor
    ) {
        let fn:Function = descriptor ? descriptor.value : target[key],
            id:number;
        let bn:Function = function (...args:any[]) {
            if (id !== undefined) {
                clearTimeout(id);
                id = undefined;
            }
            if (id === undefined) {
                id = setTimeout(() => {
                    fn.apply(this, args);
                    id = undefined;
                }, ms);
            }
        };
        for (let el in fn) {
            if (fn.hasOwnProperty(el)) {
                (<any>bn)[el] = (<any>fn)[el];
            }
        }
        (<IBufferedFunction>bn).cancel = function () {
            if (id !== undefined) {
                clearTimeout(id);
                id = undefined;
            }
        };
        if (descriptor) {
            descriptor.value = bn;
        } else {
            target[key] = bn;
        }
    };
}

export default buffered;

TypeScript Decorators: @trace

Alright, we want to be able to trace our TypeScript classes using a simple decorator:

@trace
class App {
    public method(n:number, text:string) {
    }
}

let app = new App();
app.method(1, 'text')

This shall produce the following output:

[2016-07-30T12:23:25.520Z]#bc0b >>> @.method
[2016-07-30T12:23:25.520Z]#bc0b { '0': 1, '1': 'text' }
[2016-07-30T12:23:25.546Z]#bc0b <<< @.method
[2016-07-30T12:23:25.546Z]#bc0b undefined

Above, we shall have the time stamp of the invocation followed by some random string (identifying identical invocations). Then, we shall have the method name plus, on the second line, a list of arguments. Further, on the third line, we shall have the time stamp of the return, and finally on the last line the resulting value.

By default, the method name shall not include the corresponding class name. To create fully qualified method names the @named decorator shall be used:

@trace
@named('App')
class App {/*..*/}

Further, we want to be able to provide a boolean flag to @trace to switch tracing on and off:

@trace(false)
class App {/*..*/}

Further, we want the ability to trace a class but omit certain methods, we’re not interested in (since maybe they are called simply too often and tracing the corresponding invocations would quickly become infeasible):

@trace
class App {
    public method1(n:number, text:string) {/*..*/}

    @traceable(false)
    public method2(n:number, text:string) {/*..*/}
}

We also want the opposite, where only certain methods shall be traced, while in general the rest of the class shall be left alone:

class App {
    public method1(n:number, text:string) {/*..*/}

    @traceable
    public method2(n:number, text:string) {/*..*/}
}

How do we implement all this various tracing features? Here it is:

import '../string/random';

export function trace(
    flag:boolean):Function;
export function trace(
    ctor:Function):void;
export function trace(
    arg:boolean|Function):Function|void
{
    if (typeof arg === 'boolean') {
        return _trace(arg);
    } else {
        _trace(true)(<Function>arg);
    }
}

function _trace(flag:boolean):Function {
    return function (ctor:Function) {
        Object.keys(ctor.prototype).forEach((key:string) => {
            let dtor = Object.getOwnPropertyDescriptor(ctor.prototype, key);
            if (dtor && typeof dtor.value === 'function') {
                _traceable(flag)(ctor.prototype, key);
            }
        });
        Object.keys(ctor).forEach((key:string) => {
            let dtor = Object.getOwnPropertyDescriptor(ctor, key);
            if (dtor && typeof dtor.value === 'function') {
                _traceable(flag)(ctor, key);
            }
        });
    };
}

export function traceable(
    flag:boolean):Function;
export function traceable(
    target:any, key:string, dtor?:PropertyDescriptor):void;
export function traceable(
    arg:boolean|any, key?:string, dtor?:PropertyDescriptor
):Function|void {
    if (typeof arg === 'boolean') {
        return _traceable(arg);
    } else {
        _traceable(true)(<any>arg, key, dtor);
    }
}

function _traceable(flag:boolean):Function {
    return function (target:any, key:string, dtor?:PropertyDescriptor) {
        let wrap = (fn:Function, callback:Function) => {
            if (!flag) {
                (<any>fn)['_traced'] = false;
            } else {
                if ((<any>fn)['_traced'] === undefined) {
                    (<any>fn)['_traced'] = true;

                    let tn:Function = function () {
                        let _named = target._named || '@',
                            random = String.random(4, 16),
                            dt_beg = new Date().toISOString();

                        console.log(
                            `[${dt_beg}]#${random} >>> ${_named}.${key}`);
                        console.log(
                            `[${dt_beg}]#${random}`, arguments);

                        let result = fn.apply(this, arguments),
                            dt_end = new Date().toISOString();

                        console.log(
                            `[${dt_end}]#${random} <<< ${_named}.${key}`);
                        console.log(
                            `[${dt_end}]#${random}`, result);

                        return result;
                    };
                    for (let el in fn) {
                        if (fn.hasOwnProperty(el)) {
                            (<any>tn)[el] = (<any>fn)[el];
                        }
                    }
                    callback(tn);
                }
            }
        };
        if (dtor) {
            if (typeof dtor.value === 'function') {
                wrap(dtor.value, (tn:Function) => {
                    dtor.value = tn;
                });
            } else {
                if (typeof dtor.get === 'function') {
                    wrap(dtor.get, (tn:Function) => {
                        dtor.get = <any>tn;
                    });
                }
                if (typeof dtor.set === 'function') {
                    wrap(dtor.set, (tn:Function) => {
                        dtor.set = <any>tn;
                    });
                }
            }
        } else {
            wrap(target[key], (tn:Function) => {
                target[key] = tn;
            });
        }
    };
}

export default trace;

The details are onerous, but the main idea is simple: Wrap a method, which shall be traced, with a function printing the method name and arguments before the invocation, and the result after the invocation.

As hinted above, we shall be able to write @trace or @trace(true|false) (and similarly @traceable or @traceable(true|false)): In the implementation this is achieved using function overloads.

Decorating static methods

Another point, which is worth of mentioning, is the fact that static methods can automatically (or manually via @traceable(true)) be traced as well:

@trace
class App {
    public static method(n:number, text:string) {/*..*/}
}

Decorating get and set accessors

Finally, get and set accessors are by default not traced: This makes sense since in general you do not want to track each and very read and write to a member variable of a class. However there will be situations, where for example you synchronize the state of your class with a persistency layer. In such situations it might very well make sense to closely follow the synchronization process:

@trace
class App {
    @traceable(true)
    public get state():any {
        return this._state;
    }
    public set state(value:any) {
        this._state = value;
    }
    private _state:any;
}

As far as I know, so far Typescript does not allow to apply decorators separately to a getter and setter accessor: You should apply a particular decorator to the first accessor within the class’ declaration. It is then automatically applied to the corresponding partner accessor as well (if such a partner exists).

TypeScript: String.random

Today, I’d like to discuss and analyze a function I’m using quite often during my daily work with TypeScript. It’s about generating random strings, and here is the code:

interface StringConstructor {
    random(length?:number, range?:number):string;
}

String.random = function (length:number, range:number = 36):string {

    length = Math.floor(length);
    range = Math.floor(range);

    let p_0 = Math.pow(range, length),
        p_1 = range * p_0;

    return (length > 0) 
        ? Math.floor(p_1 - p_0 * Math.random()).toString(range).slice(1)
        : '';
};

So, I attach the random function to the String interface: Yes, normative pundits will point out now that I should not overwrite or extend any existing vanilla constructions, but since I use random strings so often, I decided to commit this sin in the name of convenience!

Further, since the result of random is a string, there was no better place for me than to attach the former to the latter. If you cannot follow my logic, so be my guest and put the function where ever you deem it’s best.

Alright, after having addressed the dogmatic computer scientists, it’s time to have a look how we use String.random:

import './random';

let random_1 = String.random(8);
console.log(`random-1 w/{length:8, range:36}: ${random_1}`);
let random_2 = String.random(6, 16);
console.log(`random-2 w/{length:6, range:16}: ${random_2}`);
let random_3 = String.random(4, 2);
console.log(`random-3 w/{length:4, range: 2}: ${random_3}`);

The above code produces on the terminal the following random strings:

random-1 w/{length:8, range:36}: bicgtcoq
random-2 w/{length:6, range:16}: 8cf784
random-3 w/{length:4, range: 2}: 0110

So, apparently the length argument controls the number of characters in the random strings, while the range argument sets the range of characters from which they are chosen from. Do not put a range larger than 36, since otherwise the number.toString(range) function, which is used to convert numbers to strings, will complain very loudly!

Well, so far for the practical side of the code; let’s investigate the theoretical side of randomness: Computers cannot create “true” random numbers, but rely on so called pseudo-random generators (PRNG). In our case, we rely on Math.random() to deliver a reasonably usable (discrete) uniform distribution. The latter reference describes it as:

In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution whereby a finite number of values are equally likely to be observed; every one of $n$ values has equal probability $1/n$.

Or using a simpler language:

Another way of saying “discrete uniform distribution” would be “a known, finite number of outcomes equally likely to happen”.

Actually, getting randomness is in general quite hard and it’s a science: So, do not try to use in security related applications your homegrown PRNGs, but rely on well researched algorithms and correct implementations!

In this context, I’d recommend to even forgo the above code and use for example the Stanford Javascript Crypto Library. However, if you need some quick and good enough implementation then String.random might be your candidate.

Analysis of the Distribution

So what is good enough? Well, the distribution of the random strings should be uniform. Let’s produce the data to analyze, where we’ll generate binary random strings with a length of $16$ characters:

import './random';

class App {
    public logRandom(size:number) {
        for (let i=0; i<size; i++) {
            console.log(String.random(16, 2))
        }
    }
}

let app = new App();
app.logRandom(65536);

This will create a huge list of binary random strings: But how do we determine if it is uniform? Creating directly a histogram might be an approach, but we might not have enough data to gain significant insight.

Why is that? The total number of binary strings of size $16$ — which is $2^{16}=65536$ — happens to be the number of samples we have in our data. So we would expect to see each binary string on average only once: Counting each string once, and creating a corresponding histogram might confirm that we might not have a very skewed distribution, but that’s pretty much it.

However, for uniformly distributed binary strings the following property should hold as well: The number of different characters between any two strings should follow a normal distribution. Let’s check this with a small Python script:

#!/usr/bin/env python

from matplotlib import pyplot as pp
import numpy as np
import sys

def levenstein(source, target):
    if len(source) < len(target):
        return levenstein(target, source)
    if len(target) == 0:
        return len(source)

    source = np.array(tuple(source))
    target = np.array(tuple(target))

    prev_row = np.arange(target.size + 1)
    for s in source:
        curr_row = prev_row + 1
        curr_row[1:] = np.minimum(
                curr_row[1:], np.add(prev_row[:-1], target != s))
        curr_row[1:] = np.minimum(
                curr_row[1:], curr_row[0:-1] + 1)
        prev_row = curr_row

    return prev_row[-1]

with open(sys.argv[1]) as file:
    lines = list(map(lambda l: l[:-1], file.readlines()))

ds, l0 = [], lines[0]
for line in lines[1:]:
    d = levenstein(line, l0)
    if d > 0: ds.append(d)

pp.title('Levenstein Differences')
pp.hist(ds, bins=13)
pp.grid()
pp.show()

And finally let’s have a look at the histogram:

Levenstein Differences

So this pretty much confirms our expectation: The histogram is symmetric around a difference of $7$ characters and fitting a normal distribution to this data should not be a problem.

We conclude that an original uniform distribution might have caused the observed normal distribution, and will stop analyzing further. Of course many more statistical tests should be carried out to determine beyond doubt the quality of the PRNG, but will stop here for the sake of brevity.

TypeScript Decorators: @named

I’ve been playing around recently with this fantastic new language TypeScript in general plus with TypeScript decorators in particular, and would like to share some of my experiences. In this post I’ll keep things to the bare minimum, and will elaborate more in the upcoming posts of mine.

Alright, let’s dive in: I actually wanted to build my own tracing system, where I would see which parts of my code are invoked when, with which arguments and returning with which results.

I was particularly interested in class methods: However, I figured out rather soon that the name of the class is not accessible, unless you would use metadata reflection. But since the latter seems to be rather experimental, I decided to go for my own minimal thing.

So, the easiest approach I imagined was to simply attach any name of my choice to a class of mine using decorators:

import {named} from "./named";

@named('App')
class App {
    public toString():string {
        return this['_named'];
    }

    public static toString():string {
        return this['_named'];
    }
}

var app = new App();
console.log('app.toString:', app.toString());
console.log('App.toString:', App.toString());

Yes, it’s cheap but hey I was looking for a quick and working solution! So, when we run npm start the output should look like:

app.toString: App
App.toString: App

As you see, it works: Both the instance and static toString methods manage to return the expected App string. This little feature will become later important for us to provide tracing using fully qualified function names.

Let’s check the named.ts implementation: It’s rather straight forward, since the supplied named string is attached as the _named instance and static member directly to the object.

export function named(name:string) {
    return function (object:any) {
        if (object.prototype._named === undefined) {
            object.prototype._named = name;
        }
        if (object._named === undefined) {
            object._named = name;
        }
    };
}

export default named;

The source code of this example is available on GitHub.com:

git clone git@github.com:hsk81/calaganne calaganne.git
cd 'calaganne.git/2016-07-26/TypeScript Decorators: @named'/

Further, you have to install the npm dependencies (and compile the project):

npm install

Now, you should be able to start the application as already mentioned above:

npm start