Author

I am Joannes Vermorel, founder at Lokad. I am also an engineer from the Corps des Mines who initially graduated from the ENS.

I have been passionate about computer science, software matters and data mining for almost two decades. (RSS - ATOM)

Meta
Wednesday
Jan112012

MathJax, at last a decent way to post maths on the web

For a long time, posting something as simple as a square root on the web has been a major pain. Despite MathML having been around for years, Firefox is still the only browser (that I know of) to render MathML correctly.

$$p=\Phi\left(\sqrt{2\ln\left(\frac{1}{\sqrt{2\pi}}\frac{M}{H}\right)}\right)$$

Recently, I did stumble upon MathJax, an outstanding JavaScript rendering engine for mathematics that works for all major recent browsers. The syntax is derived from the one of LaTeX, and the output is either MathML (if you have Firefox) or plain HTML/CSS otherwise.

Thanks to MathJax, I have been able to post a long delayed analysis about optimal service levels (that the illustrating formula here above) and economic order quantity. Kudos to the MathJax team!

Tuesday
Dec202011

Instant transfer with Bitcoin but without 3rd parties

Update 2012-05-17: Double spending can be made extremely difficult through quasi-instant double spending attempt detection. See TransactionRadar.com as an illustration. I now believe that the ideas posted below are moot, because early double spending detection is just the way to go.

Bitcoin is a crypto-currency (check out my previous post for some more introductory thoughts) that provides many desirable properties such as decentralization, very low transaction fee, digital-native, ... However enabling instant payment has not been a forte of Bitcoin so far. It's very noticeable that people did even raise funds to address this problem with a trusted 3rd party setup.

In this post, I will try to describe a convention that would offer instant (1) secure (2) decentralized (3) transactions with Bitcoin (4).

Let's start by clarifying the scope of this claim:

1. Instant. There is no such thing as real-time on the Internet, if only because of speed of light. Here, I am considering as instant anything below 10 seconds, which would be sufficient for the vast majority of the mundane use of a currency such as shopping.
2. Secure. With Bitcoin, a transaction can be propagated in the network within seconds, yet, the transaction only becomes secured - aka with no further possibility of double spending - once the transaction has been included into the blockchain (6 blocks inclusion being the default of the Bitcoin client). Obviously, this requirement somewhat conflicts with the previous one, because 6 blocks represents about 1h on average (10min per block being the target speed of Bitcoin).
3. Decentralized. The solution to reconciliate 1 and 2 should not rely on a trusted 3rd party. I hold no grudge against BitInstant, but if a solution exists to do the same thing without middlemen, then I believe it will only make Bitcoin stronger.
4. Bitcoin. The solution should preserve the Bitcoin protocol as it exists today, requiring no upgrade of the community, except for those who would like to leverage instant payments. It's a convention in the usage of Bitcoin that I am referring to: it fits into the existing protocol spec. Those who don't want to follow this convention can safely ignore the whole thing.

Disclaimer: I am neither a cryptograph nor a security expert, merely an enthusiast Bitcoin user.

The core idea of my proposal is to introduce a twist in the notion of security: instead of a strict prevention of double spending, let's make double-spending more expensive that the expected benefit. Indeed, if double-spending becomes possible but only a steep cost (cost being expressed in Bitcoin too) then there is no incentive to actually make any widespread use of the double-spending trick for instant payments. With this twist, we accept the possibility of double spending, but only because it's highly innefficient for the attacker. It will not prevent a crazy attacker to do some damage, but from a global perspective, the overal damage through this twist should stay insignificant (because there are so many better ways to wreak havoc anyway if you're willing to spend money on the case).

For the convention that reconcilitate 1, 2, 3 and 4, I use two ingredients:

• A Bitcoin address that is provably expensive: the setup cost of the address is X BTC.
• A mechanism to check that garantees that no double-spending attack to place for the address in the past (blockchain-wise).

Usual Bitcoin addresses are quasi-free (the CPU cost to generate a new address is negligible), but it's not difficult to produce a Bitcoin address that comes with a provable cost. The easiest way is go for monetary destruction with a transaction that targets /null. Yet, destroying coins is not entirely satisfying.

Thus, in order to prove the value of the address AX, I propose to have a transaction, originating from a single address 1A only (only 1 input) that by convention redistribute its value to the coinbase address (*) of 10 consecutive blocks that are less than 1 month old (at the time of the proof).

(*) It's the address of the first transaction of the block used by the miner himself to capture its reward.

Indeed, we cannot rely on transaction fee alone to prove the cost of address, because a miner could decide to create a ficticious high-fee transaction in a block - fictictious in the sense that the fee would cost nothing to the miner, who would immediately recover the fee through the ownership of the block.

Yet, by targeting 10 consecutive blocks, we prevent any miner to fully self-reward itself with the transaction. Indeed, blocks are assigned based on a lottery where the odds are proportional to the processing power injected in the process. A "smart" miner would be able to target one (**) of his block, lower the cost by 10% which does not compromise the pattern (the cost remains very real).

(**) Some super-heavy mining pool, like deepbit, could push the leverage further; but having a single mining operator representing more than 1/2 of the total hashing power of Bitcoin is a big problem for Bitcoin anyway; so I am assuming here that no operator has more than a fraction of the total computing power available.

Then, the 1 month old restriction is just there to increase the odds that the coins do not get lost. Indeed, since the owner of the targeted addresses do not expect further funds to be pushed on those addresses they may not even monitor them once they have been emptied. Yet, with the 1 month delay, the lucky reward will not stay unnoticed.

Another argument in favor of rewarding the coinbase addresses is that it increases the incentive on mining efforts, hence strenghtening Bitcoin as a whole.

Based on the convention established here above, we have now a way to prove that a Bitcoin address did cost at least X BTC to her owner. Yet, we still need a way to be sure that no double-spending attack has already been done.

Here, the intuition is the following: you cannot prevent double-spending with instant payment (aka without block validation), but you can expose afterward the double-spending attack which will destroy the trust invested in the provably expensive address.

Let Alice be the honest merchant who offer instant Bitcoin payment; let Bob be the bad guy who trying a double-spending attack on Alice.

At the moment of the transaction, Bob gives to Alice the content of the transaction Tx1 that has 1B as input (the address of Bob, proved being expensive) and 1A as output (the address of Alice). Yet, at the very same time, Bob is issuing another transaction Tx2 that empties the address 1B. As a result, after a while, Alice realizes that Tx1 has been rejected.

It's now time for Alice to retaliate by exposing Bob. In order to do that, Alice produces a small dummy transaction to herself where the transaction Tx1 in recursively embedded as data though a convention based on OP_DROP. (***) Once the transaction Tx1 is exposed, the community of merchants, who like Alice, accept instant transaction withness that 1B cannot be trusted any more because the cumulative effect of the transaction Tx2 going out of 1B and of the exposed transaction Tx1 (which never made its way to the block chain) leads to a negative coin amount on 1B.

(***) For the sake of concision I am leaving out the tiny specifics of how exactly should this recursive transaction embedding be implemented. Anyway, based on my understanding of Script, it's perfectly possible to recursively embark a transaction (treated as data) into another transaction.

At this point, we have a system where Bob, the bad guy cannot hurt Alice the merchant (recipient) without getting some retaliation. Yet, what if Alice is a bad merchant and Bob the honest client? Could Alice hurt Bob just for the sake of breaking the community trust into his provably expensive address 1B?

We need one final touch to the convention to protect Bob the sender from a false accusation of Alice. In order to achieve that Bob should make sure each emitted transaction Tx1 from 1B, his provably expensive address, is broadcasted to the network, and not just given to Alice. By doing this, Bob ensures that Tx1 will make its way to the blockchain and prevents Alice to report 1B as dishonest (to be safe Bob is better off putting some transaction fee in Tx1 that guarantees a speedy chain inclusion).

Implementating the convention

As far I can tell, the proposal does not involve any breaking change. Ideally, the convention would make its way to the Bitcoin client (or a dedicated fork) to support 3 extra features:

• Spending BTC to increase the trust level on a particular Bitcoin address.
• Performing instant transactions channelled through the "expensive" Bitcoin address.
• Reporting the "cost" of the address for the incoming transactions.

Then, there is many small details that would need to be polished such as the delay for the community to decide whether trust is lost on an address after being reported. Also, the convention as a whole can also probably be polished further.

Anonymous payments

This convention would be one step further is making Bitcoin less anonymous that it is today. Considering the scope of application of instant payments, it does not seem (to me) too much of a problem. If you really want to stay anonymous, then, entering a retail store isn't top notch anyway. Alternatively, for eCommerce, the 1h payment delay is mostly a non-issue (except maybe for pizza delivery).

In real life

Instant payments are needed for small purchases: you typically don't need to transfer both a big amount AND to do it instantly, it's either or. To accept (or not) whether an instant payment of X BTC made from a proved Y BTC address should go through instantly should be left to the merchant itself.

With a 10 BTC proof, it would reasonable to accept instant payment up to 10 BTC (maybe a bit less assuming a self-serving miner scenario). Coordinating triple-spending (or more) in real life seems complicated (but not impossible) but I seriously doubt people would actually bother for such a complex scheme except to demonstrate its feasability. Indeed, the stakes would be very limited anyway, as anything large would go the usual route of non-instant payments.

Then, looking at recurring customers payment with the same address would be also a way to gradually increase the confidence cap (from the merchant viewpoint) for instant payments even without asking the client to increase its proof.

Compared to a rough 2% middleman fee (based on pricing of BitInstant), I feel that the provably expensive address would be amortized in less than 1 year considering weekly purchase. Not a deal breaker, but still an option probably worth having a look at considering the positive side-effect on the mining side.

Wednesday
Nov232011

Among the (small) community interested by the software practices of Lokad to develop entreprise software over Windows Azure, Lokad.Cloud vs Lokad.CQRS comes as a recurring question.

It's a good question, and to be entirely honest, the case is not 100% solved even at Lokad

• from different backgrounds:
• Lokad.Cloud orginates from the hard-core data analytics back-end.
• Lokad.CQRS originates from our behavioral apps.
• with different intents:
• Lokad.Cloud wants to simplify hard-core distributed algorithmics.
• Lokad.CQRS wants to provide flexibililty, auditability, extensibility (*).
• and different philosophies:
• Lokad.Cloud is a sticky framework, it defines pretty much how your app is architected.
• Lokad.CQRS is more a NoFramework, precisely designed to minimally impact the app.

(*) without compromising scalability, however scalability is not the primary purpose.

Then, historically, Lokad.Cloud has been developed first (which is a mixed blessing), and, as we have been moving forward, we have started to partition into standalone sub-projects:

• Lokad.Cloud.Storage, the O/C mapper (object to cloud), dedicated to the interactions with the Azure Storage.
• Lokad.Cloud.AppHost, an AppDomain isolation layer to enable dynamic assembly loading within Azure Worker roles (aka reboot a VM with new assemblies in 5s instead of 5min). (**)
• Lokad.Cloud.Provisioning, a toolkit for the Windows Azure Management API.

(**) Lokad.Cloud does not leverage Lokad.Cloud.AppHost yet, it still relyies on a very similar component (which was developed first, and, as such, is not as properly decoupled than AppHost)

The case of Lokad.Cloud.Storage is a bit more complicated because Lokad.CQRS because Lokad.CQRS already has its own Azure Storage layer which focuses on CQRS-style storage abstractions. In particular, Lokad.CQRS emphasizes interoperable storage abstractions where the local file storage can be used in place of the cloud storage.

The Future

As far I can speak for Lokad.CQRS (see the projet boss), the project will keep evolving focusing on enterprise software practices, aka not so much what the framework delivers, but rather how it's intended to structure the app. Then, Lokad.CQRS might be completed by:

• tools at some point such as a maintenance console.
• refined storage abstractions (probably event-centric ones).

In constrast, Lokad.Cloud will continue its partitioning process to become decoupled and more flexible. In particular,

• the cloud runtime
• the service execution strategy

are still very heavily coupled to other concepts within the execution framework, and likely candidates for sub-projects of their own.

I would not advise to combine Lokad.Cloud (execution framework) with Lokad.CQRS within the same app. At Lokad, we don't have any project that adopts this pattern, and the resulting architcture seems fuzzy.

Then, it's possible to adopt a SOA architecture where some heavy-duty functional logic gets isolated, behind an API, into the Lokad.Cloud execution framework, while the bulk of the app adopt CQRS patterns through Lokad.CQRS. This pattern has been adopted to some extent at Lokad.

Friday
Oct142011

Oddities of machine learning software code

Developping machine learning software is special. I did already describe a bit how it feels to be in a machine learning company, but let's be a bit more specific concerning the code itself.

One of most shocking aspect of machine learning code is that it tends to be full of super-short cryptic 1-letter or 2-letter variable names. This goes completely against the general naming conventions which emphasis readability over brievity. Yet, over the years, I have found that those compact names where best for mathematical / statistical / numerical algorithms.

Indeed,

• Logic is typically overly intricate, with tons of nested loops and seemingly random stopping conditions. Hence, even if the variables were perfectly readable, the logic would remain show-stopper for any fast-reading attempt.
• Variables typically hold intermediate computational results, which cannot be associated with 2 or 3 English words without being extremely ambiguous at best. It's not a = OnButtonClick but rather a = InterpolatedDetrendedDeseasonalizedQuantile90PercentsOfPromotionEffects.

As a result, extreme variable name brievity makes the code much more compact which in turns makes it easier to understand the logic. It forces the coder digging into the code to learn by heart the semantic of the variables (because names are cryptic), but this effort is only marginal compared to the amount of effort to grasp the logic itself anyway.

Then, magic numbers are all over the place, frequently inlined with the rest of the code. Again, for non-machine-learning, magic numbers are a big NO-NO, and a cardinal rule of sane software design consist of clear speration between data and logic. Yet, in statistical algorithms, those seemingly random numerical values are the result of the incremental tuning that is necessary to obtain the desired performance and accuracy.

• There is no benefit in isolating the magic number, because it is used only once.
• The actual numerical value is typically more insightful than the variable name. It helps the developer to get a sense of the behavior of the algorithm.

Then, it remains a good practice to add a lot of inline comments to justify the purpose of the magic numbers, and how they have been optimized.

If your code is super fast, you're probably getting it wrong. For most machine learning problems, it's better to try to take advantage of the outrageously large amount of processing power available nowadays to improve results. I am not saying that super fast code is bad in itself, but if your code is super fast, then it means that you've got room to go for more complex methods that would consume more resources in exchange for better, more accurate, results.

Unit tests are both very handy to validate small block pure-mathematical operations, and yet, quasi-useless for the bulk of the machine learning logic. Indeed, when it comes to statistical accuracy, there is no black & white, but only in shades of gray. As long performance is acceptable, the overall accuracy is the only metric that matter. In particular, it happens, from time to time, that a bug - aka a piece of code that does not reflect the original intent of the developer - turns out to behave well over the data. On average, bugs tend to degrade accuracy, but sometime, it just stumbles upon an interesting (and counter-intuitive) behavior.

Finally, Object-Oriented Programming is still around, but seldom usedFunctional Programming is king. This pattern reflects the fact that the machine learning problem itself, either classification or regression is nothing but trying to build a big complex function to tackle real-world data.

Wednesday
Aug032011

Bitcoin, thoughts on a nascent currency system

Bitcoin is a fascinating concept, in short, it's a crypto-currency backed by nothing other than raw processing power and geeky enthusiasm. For those who've never heard of it, you can have a look at the introduction provided by the Bitcoin community itself or by The Economist.

This currency seems to trigger a much positive reactions than skeptical ones. My personal stance is very inclined in favor of Bitcoin, and I have invested a conservative amount of Euros in exchange of Bitcoins. Granted, nothing that would too troublesome even considering a 100% loss of value for those Bitcoins.

A lot have been said already about Bitcoin, so I will not go through the routine discussion of pros and cons, but merely make some observations.

Bitcoin vs Credit Cards and Classical Banking, the long term value

A good deal of interest in Bitcoin is strictly speculative: people go for Bitcoin thinking they have a good chance of cashing out. Yet, when it comes to evaluate the value of venture of any kind, I am a strong believer of the Guy Kawasaki credo: does it make sense? Is the world a better place with Bitcoin than without? Indeed, making a speculative profit is not enough, Bitcoin has to improve the world in some tangible ways.

Here I believe that Bitcoin addresses a very deep problem: how to pay or receive money without involving either an expensive physical process (meeting and exchanging gold, goods, ...) or an expensive middleman (your bank, your credit card operator, PayPal, ...).

To a web entrepreneur, the current banking system looks like a 19th century legacy setup:

• About 4% (1) of my money gets consumed through system friction.
• It takes days (2) to complete anything that does not go through credit cards.

(1) Indeed, there are many costs that pills up (rough estimates):

• 0.5%, fees of the consumer bank account (explicit or not),
• 1%, fees of the credit card owned by the consumer,
• 2%, merchant fees for any online payment,
• 0.5%, fees of the merchant for its own bank account.

(2) International wire transfers with a bank routing in the middle where a 7 to 10 days delay is pretty much the standard.

And yet, in my experience there is not so much to be done about this friction, at least not if you're just Joe the Plumber or a small business. Marginally lowering those costs through negotiations with the bank is possible if you have leverage (that is to say money) and a lot of patience; but there is so much one side can do because both sides (payer and receiver) are paying fees anyway.

The long-term promise of Bitcoin is to bring down this 4% friction to 0.1% or less, and to reduce payment latency from days to minutes, possibly seconds with a healthy competitive ecosystem of trusted 3rd parties. Indeed, Bitcoin is not natively designed for low latency transactions, but Bitcoin can be complemented by low latency services (backed by Bitcoin) if the need arises.

Anecdotal evidence: When I purchased Bitcoins on MtGox a few days ago, the sole wire transfer from France to UK cost me about 4% (EUR to GPB conversion included), plus the transfer took 8 days, because the receiving bank in the UK had a multi-day downtime of one of their system.

Weaknesses of Bitcoin

When it comes to assessing the weaknesses of Bitcoin, most people discuss the possibility of breaking the underlying cryptography, or swarming the network with some overwhelming computing power. Yet, Bitcoin has been designed to be natively resilient against this sort of attacks, and very capable people are working hard to make Bitcoin even more resilient. Hence, I am not too worried here: the Bitcoin community is now big enough to make those sort of attacks really complicated.

Anecdotal evidence: I have tried to mine about 0.01 BTC through Deepbit.net and on my GPU enabled laptop it was taking about 30h. Naturally, I gave up before the end of the experiment, as it was pointless to waste further electricity. Bitcoin mining has reached the state of being vastly unprofitable for everyone but the experts, which is good. It means Bitcoin had reached the point of diminishing returns where printing money (aka mining) is only very marginally profitable.

The most critical threat for Bitcoin is something simpler and stronger: a potential fade of interest, which may vastly hinder the tooling ecosystem to mature. Fade of interest would not annihilate Bitcoin, but it would make it stagnant. Then, in the innovation trade, being stagnant is the closest thing to being dead.

For the short term (next few months), my No1 concern is that a tiny few individuals such as the enigmatic Satoshi Nakamoto may possess +100k BTC (or this guy with 370k BTC). And no, the problem is not that the system is unfair - being unfair does not hinder economical success, quite the opposite actually. The problem is that each one of those individuals has the power to disrupt the emerging usage of Bitcoin. As a matter of fact, the first Bitcoin market crash was not the result of a weakness within the protocol, but the result of a not-fully-secured wallet within a trading system. A lot of early adopters are moving around with thousands of BTC, and each one of those, willingly or not, may disrupt the Bitcoin trading by simply getting their wallet stolen. A similar analysis goes for all the emerging companies supporting the Bitcoin economy that are really lacking the expertise needed to operate properly (ex: the now infamous MyBitcoin.com downtime fiasco). Those bumps are not for the faint hearted, and are likely to slow down the Bitcoin adoption. As time goes, this sort of problem will fade through survival of the fittest, but a couple of Bitcoin crashes should be expected.

For the mid-term (6 months ahead to 2 years), the most difficult operation will be to transition the Bitcoin community from mining stage to trading stage, then repeat the process again from trading stage to end-user stage (see below, for the detail of the phases) - and do those transitions without loosing commitment and enthusiasm of the people who contribute the most to the Bitcoin community. Basically, as long there are smart people enthusiastic about Bitcoin, Bitcoin will keep growing; but the attention sharing economy is a harsh mistress, and the community interest might jump to the next revolutionary idea just as well. See the law of conservation of hype as a practical illustration. Bitcoin has successfully attracted a horde of miners. Now this horde needs to involve into the next stage, as mining earnings are marginalized.

For the long term (2 years), assuming Bitcoin interest has not faded already, direct Government interventions - for whatever reasons (*) - may kill the community. Outlawing Bitcoin would be hard to enforce to its fullest extent, at least if Internet still exists, but flagship companies supporting Bitcoin are easy targets. It would also be easy to spot any company publicly accepting Bitcoin as payment method. Again, the problem is not Bitcoin annihilation - which seems a remote possibility - but rather Bitcoin undergoing a fade of interest if its community has to go underground.

(*) Until 1996, all encryption methods were banned in France, classified a warfare materials. As a result, encryption usage was close to inexistent despite obvious benefits.

Assessing a global value for Bitcoin

Many people looking at Bitcoin make the naïve assumption that BTC mined X USD per BTC gives any reasonable assumption of the overall market value of Bitcoin. This approach is misleading. First, we don't know for sure how many BTC have been lost already. Super early users were not really treating BTC as a real currency, and it took more than 2 years for Bitcoin to take off. I suspect that many early casual miners have not properly preserved their wallet. This could account for 1M or 2M BTC being lost already (warning: this number is vastly unverifiable).

Second, those who've read Making Money  - which I strongly recommend - know that the real long-term backing of any currency is the people behind it, possibly as unwilling taxpayers (but I am digressing). Granted, Bitcoin has no magical Golems backing the protocol, but they have about the next best thing: a enthusiastic, dispersed and growing community of geeks working hard to make of Bitcoin a success.

Bitcoin v3.0 - Merchant tools

If Bitcoin gets adopted by a sufficiently large amount of people, then it will start getting the interest of retail folks. There are already a few eCommerce out there supporting Bitcoin, but it's still very niche. The design of Bitcoin offers unprecedented opportunities to support micropayments that were simply not tractable with classical systems. Indeed, anything below $20 is considered as a micropayment by Visa, and there is no widespread electronic solution out there for payments below$1. In comparison, Bitcoin would easily scale down to \$0.01 payments (or rather the equivalent amount in BTC) with only a marginal friction. Yet, in order to grab those opportunities, it will take some serious Bitcoin-powered merchant systems, as complete automation is required. Offering to any (non-geek) merchant all the tools he/she needs to receive and process Bitcoin payments is the v3.0 milestone.

Bitcoin v4.0 - Enterprise tools

No matter the success of Bitcoin, large companies will probably be among the latest entrants in the Bitcoin economy. In order to make Bitcoin useable in corporate environments, it will require a lot of support from the software industry. For example, there is nothing yet in the Bitcoin software ecosystem that would enable an enterprise to grant rights to people to operate within spending quota, possibly requesting multiple approvals if a spending goes over a certain threshold. Naturally, the same Bitcoin system would also need to be seamlessly integrated into the primary accounting system in order not to drive nut both accountants and auditors. Getting Bitcoin corporate-proof is the v4.0 milestone.

So what next?

Bitcoin is still in the middle of trading stage but, for those who are inclined in giving Bitcoin a chance to establish a very low-friction currency system, the most simple contribution is not to purchase Bitcoins, but simply to start accepting Bitcoin, which is exactly what my company, Lokad.com, started doing.

Page 1 ... 3 4 5 6 7 ... 31