The Bitcoin protocol - a highlevel explanation

Bitcoin is a peer to peer financial protocol. There is no central authority that guarantees that the operations are valid, how can this work? How can you trust strangers with your money? Let's say you are selling something for bitcoins - you receive the amount quoted - how can you verify that the transaction was valid? You need to check three things:

1. That it was indeed the owner of the sender account that created the transaction.
   
2. That the acount has the BTCs that are now being sent - i.e. that it previously received them.
   
3. That he has not transfered these BTCs already somewhere else (double spending).
   

The first check is easy - all transactions are signed. For the second you need to know another transaction that transfers the money to the senders account. Of course now you'll need to verify the other transaction as well - and then, in a recursive fashion, all the others leading to the one that generated the bitcoins (more about generating later). The sender could send you this chain of signed transactions - but in fact he does not need to do that because all the transactions are public.

The third check is more tricky - for this you need to always know which transaction was first and which one is second and then possibly reject the second one if it is double spending. This would be easy with a central authority that would timestamp all transactions and log them somehow - but it is very hard to do in a p2p system. In bitcoin there is also a global log of all transactions - it is called block chain (for it's technical representation). The trick is that to add a valid record to that log you need to solve a hard computational problem. You practically have no chances to do that singlehandedly and you need the other nodes in the network to help you. The sender broadcast his will to transfer money to the whole network and then wait until someone from this network solves the problem and correctly saves the transaction to the global log. This is like going to the notary to make sure that all formalities are met. After the transaction is saved to the log it is very hard to undo that - because you'd need to solve this hard problem again - and without a conspiracy between a significant part of the peers this would be impossible.

To be more precise transactions are not logged individually - but rather in batches called blocks. Such a set of transactions is written to the log in one sweep. This is important for efficiency - but not only.

All of this happens in a distributed, asynchronous manner. This means that it is possible that two nodes will write two new blocks to the transaction log in parallel and we'll get two different and valid versions of the log. What would happen then is that when a next block is written down to one version of the log it will take over all of the transactions from the block in the alternative log version, so they are not lost. But it is possible that the alternative logs contain two conflicting transactions (double spending) - then only one of them will be eventually saved. This showcases one important thing - having the transaction written to the log does not yet guarantee that it will stay there, because it can happen that there exists an alternative, valid log version and that eventually this other one will be the one that is continued by the system. But if you wait until another block is written to the log after the one that you are checking - then you are much more safe. This is the most complex part of the protocol - but the general rule is that the more blocks are written to the log after your - the more safe you are, and the safety grows exponentially.

Now - why so many nodes in the network would spend their time trying to save a new transaction block to the log? This is because they are paid if they succeed. In each new block saved to the log there can be one transaction that generates a specific amount of BTCs (now it is 50 - but it will be less in the future). This is they way new bitcoins are generated.

Another question is how the bitcoin project can maintain that the transactions are anonymous when they are all public? The answer is that what is public is the addresses of the sender and the receiver but not who owns these addresses. It is easy to create new addresses. You can use a new one for every incoming transaction and you can also make transfers between your own accounts to hide the tracks. Maybe it is not total privacy - but it is still better then with current money transfers where the banks know everything.

This introduction leaves out lots of technical details - but I hope that it explains the protocol enough to convince readers that it can work :) For more details have a look at the original bitcoin paper and the bitcoin wiki (just remember that what I call transaction log here is called block chain there).

By the way - I've heard bitcoin makes internet tipping in fashion again - so 113uhu2LrJp8gXGDrDLLDqmFGxnC2e3suB is one of my addresses. The interesting twist to that is that the donations are public - you can view the current ballance at blockexplorer. I've already got some tips - thanks :) Consider this an experiment in micropayments for blog financing.

Update: A critical analysis of the decentralization of the bitcoin protocol: http://www.links.org/?p=1164

Synthetic attributes

chromatic writes about synthetic attributes. I wonder why this is not more widely used - it's such a simple technique. I've been using it since I discovered Moose and all the time in the back of my head I had this thought: Why people don't use this more widely? It is so obvious solution to the testing problems. Maybe they know something that I don't? But maybe it is just the matter of some guru (like chromatic :) writing about this technique?

PS. Sorry I'll not explain what synthetic attributes mean - this post is only a comment. I cannot currently comment at chromatic's blog.

git push and other copy commands

The usual pattern of a copy command:

copy source destination

The pattern of git push command

push destination source:destination

the first destination is the destination repository - the second is the branch (and 'source' is the source branch). I must have skimmed the linked manual dozens of times over many years. There was something that just did not make sense and I imagined that I would have to read some book or something to eventually understand the magic 'ref specs'. It never dawned on me that it was that simple.

The additional difficulty is that the destination repository is usually shortened to 'origin' (because it was the origin for the clone command).

Drupal like architecture

The Drupal subject reappears in the Perl blogsphere regularly. In my opinion there are three key architectural choices for 'portable plugin apps'. First, obviously, the plugins needs to be highly independent. Second they need to be controlled by pages - that is the page decide what plugins to use. To meet the independence requirement, in the Plack world, the obvious choice for the plugis is that they are simply PSGI apps that in body return a page fragment. This will make it easy to plugin existing wikis and blogs - you just need to remove the header and footer templates and voila you have a plugin instead of a standalone app. You can also use all the Plack infrastructure, for example the Plack::Client if you ever care about scaling your application.

There is one thing that I forgot in the first version of this post - Javascript and CSS. Applications are rarely pure HTML these days - we'll need also some way to gather all the js and css files that the plugins use and link them in the main page. At the main page side this is nothing special - it is not unusual that applications concatenate many Javascript libraries into one file automatically - so this is already well explored. The complication arises from the requirement to pass something more structured then just a HTML fragment in the Plack response from the plugins.

More interesting is the other key choice - how the plugins are supposed to be plugged in. That is how page handlers will choose what plugin to use and what data pass there. As much as I hate the 'program in XML' approach to language syntax - the obvious established standard here is ESI. Maybe we could even steal the semantics and replace the syntax with something saner? Plack based ESI implementation was submitted as an example GSOC idea - I really hope some student will pick it up.

Update: Added js/css handling consideration (thanks for cezio comment below).

App initialization and web frameworks

Building the application object and its components has nothing to do with serving web pages. The database model setup is exactly the same if you do it for a web application or for your cron utilities and it should also remain the same if you one day decide to make a desktop version of your app. There is no reason that this initialization is a part of web frameworks other then we don't currently have a good standalone application builders. Now every web framework reinvents the wheel and writes one from scratch. Fortunately (in the Perl universe) there are now multiple efforts to create the ultimate configuration engine. There is just one step from a config reader to an application configurator.

As I have already commented elsewhere, I think the ideal for big projects would be a simple config file using simplified syntax that could be changed by the admins plus a Dependency Injection container that would build all the application components from the primitive values provided by this config. This DI container would be a second level configuration - still simple code but touchable only by programmers. For small applications I was quite happy with MooseX::SimpleConfig and Moose type coercions.

Reblessing objects

Yesterday I've read the example from Refactoring transcripted into Perl. Nice work (I am not sure about the legal status of this - but I am sure that it is a great advert for the original book). The last refactoring there starts with:

We have several types of movie that have different ways of answering the same question. This sounds like a job for subclasses. We can have three subclasses of movie, each of which can have its own version of charge (Figure 1.14).

This allows me to replace the switch statement by using polymorphism. Sadly it has one slight flaw - it doesn't work. A movie can change its classification during its lifetime. An object cannot change its class during its lifetime.

It then goes on to show how the State Pattern can solve the problem thus stated. I am not so sure about this argumentation - typically the movie data would be stored in a database and the object would be created just for the one transaction - I think it is reasonable to assume that the movie does not change it's classification during the transaction. But OK - all this is just to show how the State Pattern solves the problem even if in this case the problem itself would not be real - for sure there are cases where it would.

Then it got me thinking - well in Perl you can change the class of an object during it's lifetime. I've even seen it done, I don't quite remember where. In general it is considered to be nasty - but is it always? In real life it is normal that things change - a caterpillar becomes a butterfly, a child becomes an adult.

Spark::Form

I remember when when James was starting his project - his basic ideas were exactly the same as our HTML::FormHandler design. Unfortunately he learned about FormHandler after he had started coding - no way to talk him to change his plans and join FormHandler. Reinventing the wheel - but what I can decipher from his latest presentation - is quite interesting. Model integration - which is a major source of the complexity he criticized in HFH - is still lacking but the validation method is intriguing. Maybe cross-pollination will be possible?

Plack::Middleware::Auth::Form on CPAN

I've got a bit impatient in waiting for feedback and this week I uploaded Plack::Middleware::Auth::Form to CPAN. This does not mean it is entirely finished - but at least it should be easier to install.

Plack::Middleware::Auth::Form has similar functionality as CatalystX::SimpleLogin, but since it is at the Plack level it can be reused by any Plack based framework.

Plack::Middleware::Auth::Form - like CatalystX::SimpleLogin but at Plack level.

I've just published a first version to github: zby / Plack-Middleware-Auth-Form. The authenticator parameter (and it's initialization) is copied from Plack::Middleware::Auth::Basic - this is a much simpler interface then Catalyst::Plugin::Authentication - but I think it can be enough.

The redirects from and to the login page are modeled after CatalystX::SimpleLogin.

t/app.psgi is the only example so far, but I plan to use it in Nblog.

Is Newables/Injectables a fundamental distinction?

In To “new” or not to “new”… Misko Hevery advices us to divide object classes into Injectables and Newables. Newables are objects that cannot be injected with DI frameworks (that is by one type of DI frameworks), Injectables are those that can. The point is to build Injectables only from other Injectables and Newables only from other Newables. To complete this recursive definition the simple Newables are defined as objects that have attributes of only primitive types. It is not so clear what are the atomic Injectables. I guess technically this needs be classes with parameter-less constructors. The examples given suggest things that you get from the OS or external libraries like an audio device or socket, or database connection. Of course sockets are not really parameterless - you need to pass the port number as an argument to the external libraries that create one, neither are audio devices if you have more then one attached to your computer - so this will only work if we assume that the given program works with just one port number or only with '/dev/audio'. What if you wanted to test it on another port? And what if you wanted to have and object containing an array of available sockets - you could not pass the number of the sockets in its constructor, because this would spoil its Injectableness. Parameter-less constructors are only hiding globals.

This distinction between Newables and Injectables proves to be rather constraining - it would be much cleaner if every class (and indeed also primitive types) were Injectable. Fortunately it is only an artefact of the DI framework chosen - there are DI frameworks that can inject any value, because they find them by name not by type. In these frameworks all classes are Injectables - but it might still be useful to keep the name of Newables for objects that can be build internally without calling any external libraries.

Returning to current page after login

This is one of the must have conveniences of a modern web-site: if a logged out user encounters a page that requires a login then - after logging in the user goes directly to that original page (instead of staying on the login page or going to some other predefined page). Here is a quick list of possible high-level solutions - anything missing? What is your choice?

1. No redirect

Either you have the login form on every page (a small one) - or you can display the login form instead of the page text if the login is required. You need more then a small box to fit in all the currently broadly used options like OpenId or logging in via Facebook - so for a universal solution you need a full page. Let's focus on displaying the login form on a page requiring authentication instead of that page content. This is a very simple solution - would it break any of the HTTP protocol rules? But then wouldn't displaying the error message saying 'Login required' break the same rule?

2. Passing the current url in the link to the login form

The minus of this solution is the ugly url of the login page. I also read somewhere that in some implementations there is a security problem - but I cannot find now any reference about it (it was something about crafting the uri param in a way that resulted in two http requests when the redirection was done).

3. Saving the current url in the session

Additionally to all the problems with sessions (and for example multiple tabs open to the site), there is a slight efficiency disadvantage if we do that for each link to the login page, because the session then needs to be saved every time. If the session is save to the database I imagine that this could have a slight impact.

4. Using the Referer HTTP header

This would also be quite simple - but can we rely on it? Additionally it would also require passing that url from that header back to the form for the case when the first login attempt fails. This can be done with hidden field - and since everyone uses POST for the login form method this would not spoil the login page url (or it can also be done with a session - but this time the session would be saved only in the case of a failed login).

This would only work if the user followed a link from the current page to the login page (presumably displayed together with the authentication required error message). But actually it is better to automate that step and:

5. Redirecting both to the login page and from it

This still requires saving the current page in the url (as in 2) or in the session (as in 3) - but without saving current url in the session at every page containing a link to the login page. It can also be combined with 4 if additionally to this mechanism we want to have have links to the login page that would lead the user back to the original page. From the user perspective this is as convenient as 1 but might be a bit more clean from the technology perspective (see Dave's comment below - although is 303 more correct here?). Anyway - this is the solution used by CatalystX::SimpleLogin (and Catalyst::ActionRole::NeedsLogin).

Updates: Added 5.

Is $ responsible for the 'ugliness' of Perl code?

We cannot hide it that Perl code is littered with the $ characters and, compared to the original well rounded Latin letters, that went through the thousands of years of tweaking to please the human eye, compared to them, $ is just an ugly hack. Unfortunately this is what people see when they first look at Perl code - lots of $ signs (by the way @ looks a bit better - maybe we should use more arrays?) - and this is how unconsciously they form the first impression about our language. This is not fair, this is so superficial - but the way the human mind works dictates that this first impression colours every information about Perl that comes later. People don't like to change their minds, and they always will find something to support what they thought initially, even if, or maybe the more so when, that initial thought was just an unconscious impression.

What can we do then? Changing the typeface of $ in the most popular web and editor fonts does not seem like a practical solution, but maybe if we show the sheer shallowness of judging the language by the shape of the typeface of some used character - maybe this would have some impact?

Update: Bear in mind that I don't advocate to get rid of $ in Perl - I find it very useful. The point is that the type face ugliness of $ can project a shadow on the whole language completely independently from it's usefulness as language construct.

Dependency Injection - some updates

I finally found a succinct and clear definition of Dependency Injection:

Dependency injection means giving an object its instance variables instead of letting it create them.

based on answers to What is dependency injection? on Stackoverflow. There are some variations on how you do that - you can pass the instance variables in the call to the object creator (the new method) or you can use a setter to pass it to the object after it is created. This is exactly what I was thinking. Inversion of Control here happens only if you use a framework that takes over the object creation - but this is not required for the practice of DI. The name does not fit too well to its definition - but it is probably too late to change it.

Reasons to do DI:

1. The most immediate reason is that it makes it easy to use mockups (or even undef's or Nulls) for the dependencies in tests. But this is is just a concrete example of the more general reasons that follow.
   
2. To change the coupling between the main class and the dependency from control coupling to data-structured coupling (Types of coupling in wikipedia). Intuitively this also means increasing the encapsulation of the main module.
   
3. To remove more frequently changing code from inside of less frequently changing code. There is an analogy between hardcoded literal constants and hardcoded objects - this is the main subject of my previous post.
   

It is worth noting that Moose by taking over the new method encourages DI, but of course people will always find ways to sidestep this by creating an init or setup method or using BUILD or BUILDARGS from the Moose API.

Dependency Injection or Removing Hardcoded Values?

Ever since I've heard about Dependency Injection (DI) a few years ago, I read and reread all the available documents and I kept having this feeling that I still miss something. Yesterday after some googling - I found that even those whom I always expected to explain things, have similar problems with it (see also this interesting reply to that rant). I am not sure if I now really understand DI, maybe I am still missing something important, but here is my tentative theory about it.

Let us say that somewhere deep in your web app code you have these lines:



Every minimally experienced programmer will notice immediately that for any re-usability the database name, user and his password should be extracted into a place where they can be changed easily, like the first lines of the program or better a config file. This would come very natural - but the reasoning behind it does not come from any theory - it is our experience that tells us that these pieces of data will change more frequently then the surrounding code.

I don't know if anyone would call this Dependency Injection, I think he would rather say that he is removing hardcoded constants.

Now let's take this snippet:



This is better - but the name of the DBI class and the way you construct the $dbh object is still hardcoded here - the point about DI is that this is still wrong because these parts also will change more often then the rest of the MyClass. The most important case for this is tests. In Perl it is possible to change the definition of the whole DBI package (mock it up) for the tests - but a more elegant solution is to move the database connection creation out of the MyClass code:



then, to test the MyClass methods that don't use the dbh field, you could pass an undef there and not bother with setting the database at all. But it is not only tests that require changes to that code - if for example at some point you decide that you want to log all the DBI warnings and add { PrintWarn => 1 } to the DBI->connect call - this would also be easier with this design. Again, just like with the initial example, I haven't seen any theory explaining this, but from my programming practice I am assured that this kind of change happens much more often, and at different phases of development, then changes to the rest of the MyClass code. Maybe the distinction is about what i.e. values (literals or objects) and how i.e. methods and subroutines - what is more expected and easier to change - and to get the advantage of that ease you cannot mix it together with how.

The code removed in the last sample is a bit more complicated then in the initial example - but at the core it has the same nature - it is about computing some values that are later used across a program part (or the whole program). In the initial example these values are literals, here they are objects. Literals can be created independently, objects depend on other objects: we can have a MyUser that depends on MyClass that (as in our example) depends on the database connection. Fortunately solving the dependency graph and finding out what needs to be created to have a MyUser object can be automated - this is what the various DI frameworks (like Bread::Board) do. In more 'strictly' typed languages like Java - this dependency graph is mostly defined by the types used, in Perl the dependency needs to be defined by the programmer explicitly - but the graph solving works in the same way. This is why this object creation code is (or can be made) quite simple and for all objects in the same scope it can fit into one package where you could adjust the various cooperating objects just like you do with the values of the configuration variables.

This is my understanding of Dependency Injection - maybe I am still missing something - but I don't see where, in any non-convoluted way, there is the Injection happening. There are no new dependencies injected into the code. Maybe more appropriate would Dependency Passing - as the dependencies are passed as parameters - but most of the work done when performing this refactorisation is removing parts of code, parameter passing is the trivial part. Additionally Inversion of Control, which is used to explain DI in many places, is just a minor characteristic of it, not very visible one and very different from other more common Inversion of Control occurrences. Mark Fawler coined the term Dependency Injection specifically to differ it from Inversion of Control in general - but I think that even presenting it as an example of IoC is misleading, because it is not very important to understand what is going on and it is so different from the Hollywood Principle that everyone thinks about when reading Inversion of Control. Finally what is frequently blurring explanations of DI is the details of the DI frameworks used and dwelling over constructor injections or setter injections - i.e. going into the how before the why is well explained.

I believe that removing hardcoded values is what Dependency Injection is really about. Most programmers already have good intuitions on why this is needed.

Images inheritance in Plack based apps

My plan for Nblog is to let users customize it by subclassing and overloading, in the screencast I showed how to do that with controllers and templates, in the latest revision of Nblog I added the possibility of overloading images. There are Plack components for all parts of this task - but I had a bit of struggle with getting the settings right. Maybe the following code snippet will spare similar time waste for someone?



Some explanations: psgi_callback is the method in WebNano that constructs the anonymous subroutine required by the PSGI standard and here I use the around Moose method modifier for it to add some additional processing there. static_roots returns a list of directories where to search for the static files - this is our search path - the first file found in these directories is served. In the base class this list contains only 'static' - if you want to overload the static files in a subclass you need to add your directories before this one, in my example subclass config I have:

static_root => [ 'static', '../Nblog/static' ]

(these are relative paths). See also Plack::App::Cascade. All of this would be a bit easier to assemble if the Plack components logged some debug info to STDOUT, like what you can find in the standard Apache logs about files not found, when run in development environment. I am volunteering to write a patch if there is a green light from the core devs.

Unit Testing

With one functional/system test you can test lot's of low level parts that in Unit Testing would require a separate test each. It is also easier to write - because you only need to test how the module/library is used and using it should be easy (and not require mocking etc) - otherwise the library would not be a good library to start with. And what are the reasons to do unit testing? Personally I was never convinced by the arguments until I started reading Misko Hevery - here is for example is the single best explanation of why to do unit testing I've ever seen:

Lets say you would like to test a car, which you are in the process of designing, would you test is by driving it around and making modifications to it, or would you prove your design by testing each component separately? I think that testing all of the corner cases by driving the car around is very difficult, yes if the car drives you know that a lot of things must work (engine, transmission, electronics, etc), but if it does not work you have no idea where to look. However, there are some things which you will have very hard time reproducing in this end-to-end test. For example, it will be very hard for you to see if the car will be able to start in the extreme cold of the north pole, or if the engine will not overheat going full throttle up a sand dune in Sahara. I propose we take the engine out and simulate the load on it in a laboratory.

from It is not about writing tests, its about writing stories

In the rest of his writings you'll also find how to structure your code in a way that makes unit testing easy and does not require crazy mockings. I am also convinced that code structured in that way is well decoupled and easy to understand, modify and talk about.

Experiments in Inheritance - a screencast

This is a short screencast I made to replace the video made at my London Perl Workshop presentation. It did not make the list eventually - but I still think it might be interesting: http://warszawa.pm.org/WebNanoInheritance.mpeg. It is my first screencast ever made - please comment.

The main idea presented there is about solving the "give mi an application like this one but ..." problem, illustrated by making a blog engine that inherits from Nblog, but extends it and overrides some of it's elements.

Namespace Matching

The other day I was reading the Dancer Advent Calendar and I finally found the two words description of what WebNano does. WebNano is the minimal addition to PSGI that provides Namespace Matching. Beside easy deployment, which is currently covered by Plack, Namespace Matching is probably the main feature of Catalyst and now with WebNano you can have that without the heavy baggage of the whole of the Catalyst framework. I think it is important because it seems to produce just the right granularity of the controller classes and provides a path for the application growth (without overloading one file with too much stuff).

WebNano - some incompatible API changes ahead

I tried carefully not to document some things that are likely to change in the closest WebNano releases, but the example code I put in the docs needs to be exact and that means it contains some details I have not yet decided are stable. One of these examples is about overriding the local_dispatch. It used to take the path as a string parameter - now it takes an array - i.e. the path split on the '/' character. The past way was more universal as it let the user programmer to specify how to parse the path - but I think splitting on '/' is such a common usage that it justifies the change. And it is not destructive - so if someone really want's to parse the path in a different way then he can join it back.

This change will be in the next WebNano release.

In the longer perspective I am thinking about being more compliant with the Law of Demeter and building the controllers with the needed model parts in their own attributes, instead of accessing them through app. So for example some code in Nblog would change from

$self->app->schema->resultset( 'Article' )->search
to
$self->article_rs->search

Now this can be done by overriding the handle class method - but maybe it needs something more elegant.

WebNano as Catalyst::Tiny

If you have read The Philosophy of WebNano you might think that WebNano is radically different from Catalyst, the more so if you'd compare the size of these projects (sloccount reports over 5000 lines in lib for Catalyst, versus less then 250 for WebNano). But if you compare the code structure between Nblog and the original RavLog project you'll find it very similar. The DBIC schema and form classes were just copied around, you'll see mostly the same controllers with mostly the same methods.

Look for example at Nblog::Controller::Ajax and RavLog::Controller::Ajax - the changes are minimal, mostly just changing sub check_articles : Local to sub check_articles_action and accessing the model from $c->model('DB::Tag')->search to $self->app->schema->resultset( 'Tag')->search - a bit longer perhaps. Sure there are other controllers like: RavLog::Controller::View that I renamed to Nblog::Controller::Article. This renaming is not important - I just did not like a controller called View but there is also some difference in their methods. The RavLog controller uses the Chained Catalyst dispatcher - while in the Nblog one I overrode local_dispatch, and it uses stash to communicate with the template while in Nblog I passe the data directly as a parameter. Still some similarity remains.

WebNano uses some dependencies - so it does not fit into the original Adam's definition of tiny modules (by the way I cannot fin this definition now - maybe this should go to some semi-official place like the p5p wiki?). But the prerequisites are really minimal - and mostly tiny themselves. Maybe in the subject space of web frameworks this should be allowed?