Ethernaut – Part 1

I recently came across Ethernaut, a game about finding issues with Ethereum smart contracts and breaking them. I do enjoy a capture the flag and I know practically nothing about smart contracts, so it seems like a fun thing to attempt to chip away at.

I’ve currently managed to do the first two challenges, the second which took me a very long time to do, as the challenges assume a small bit of experience in web3.js and the general tool chain.

Anyway, I’ll put my solutions below. Obviously spoilers.

Prerequisites

  1. A Metamask wallet. Metamask is a browser plugin that lets you join an Ethereum network and also exposes a wallet you can use in browser land.
  2. Etherum in a wallet associated with the Ropsten Test Network. You can get this from the Ropsten Faucet. The Ropsten Test Network, you guessed it, is for testing dApps (Distributed Apps) before they go to production land.

Once you have the above, you can start the challenges.

Level 0 – Hello Ethernaut

This is really more of a tutorial with interacting with their game environment. Once you have a metamask wallet set up and connect it to the Ropsten Test Network, you can get a new instance and load up your javascript console (F12 in most browsers).

The following is how I solved the level:

await contract.info()
await contract.info1()
await contract.info2("hello")
await contract.infoNum()
await contract.info42()
await contract.theMethodName()
await contract.method7123949()
await contract.password()
await contract.authenticate("ethernaut0")
await contract.getCleared()

Hit submit and get some great console art.

Level 1 – Fallback

This was the real first level. It gave a contract to scrutinise and some rough hints. The contract is below:

pragma solidity ^0.4.18;

import 'zeppelin-solidity/contracts/ownership/Ownable.sol';

contract Fallback is Ownable {

    mapping(address => uint) public contributions;

    function Fallback() public {
        contributions[msg.sender] = 1000 * (1 ether);
    }

    function contribute() public payable {
        require(msg.value < 0.001 ether); 
        contributions[msg.sender] += msg.value; 
        if(contributions[msg.sender] > contributions[owner]) {
            owner = msg.sender;
        }
    }

    function getContribution() public view returns (uint) {
         return contributions[msg.sender];
    }

    function withdraw() public onlyOwner {
        owner.transfer(this.balance);
    }

    function() payable public {
        require(msg.value > 0 && contributions[msg.sender] > 0);
        owner = msg.sender;
    }
}

The functions of interest are contribute and the final function, which has no name and is known as the fallback function.  There is also a contract level mapping variable (contributions) which tracks addresses to money in the contract.

contributions is initialised as empty except for the owner with 1 Eth.

contribute() records any contributions from other addresses, rejects any that have a value over 0.001 Eth, and will swap ownership of the contract if some contributes more than 1 Eth. Which is possible, but would require at least 1000 calls of this function to trigger the ownership change.

The fallback function is a bit more interesting. If it is called with a value, and the address calling it has already contributed to the contract already, it will transfer ownership. This is our route to own this contract.

So the action plan is:

  1. Contribute to the contract legitimately
  2. Trigger the fallback and claim ownership
  3. Drain the contract

Seems simple, but at the time I had no knowledge of web3.js so it turned out being much more difficult than I had anticipated!

So, first off, how to pay a function?!
await contract.contribute({from: player, value:toWei(0.0009)})

This calls the contribute function on the contract with a value of 0.0009 which, crucially, gets past the requirement of < 0.001 Eth. All values need to be in Wei for web3 transactions which can be achieved with the web3 function toWei().

This creates a transaction to be mined, and once it has finished, sure enough, the contract shows that we have contributed when we check the contribution mapping with await contract.contributions(player).

Great, Step 1 complete. Also, we have successfully managed to call a payable function through the ABI (Application Binary Interface).

This conveniently create an object-like interface in javascript to call contract functions. The ABI provides syntactic sugar so that

await contract.contribute({from: player, value:toWei(0.0009)})

is actually calling

sendTransaction({from: player, value: toWei(0.0009), to: instance, data: "0xd7bb99ba"})

To complete Step 2, we need to trigger the fallback function. The way to do that is to pay the contract via a function that doesn’t exist. Functions are normally encoded in the ABI, so by setting the data field to junk we should trigger the fallback.

sendTransaction({from: player, value: toWei(0.0009), to: instance, data: "0x99999999"})

A quick check of the contract owner with await contract.owner() shows that the address is equal to player. Step 2 complete!

Step 3 is an easy await contract.withdraw() and once that is done, the instance can be submitted.


I’ve done 2 levels so far (although, honestly its only one that wasn’t a tutorial) and I’m really enjoying playing with smart contracts. Hopefully I will solve the next level and will be able to post my solution.

35 under 35 – One to Watch

(This is also posted on the company blog here)

I was delighted to find out that have been declared “one to watch” by BusinessCloud as part of their 35 under 35 piece. Please see here and here for more information.

I will try and make sure that I am an interesting and entertaining person throughout the rest of the year and not waste your valuable attention.

I’ve wanted to do a post about the journey for sometime, and this seems like a great opportunity to actually write something. It’s been a rollercoaster the last few years and hopefully I can capture the highlights with some sharp quotes and headings.

I’m an ex-academic (but do you really leave?) who worked as a Data Scientist before starting a company. I’m very mechanically minded and can say with a straight face that at the start I honestly believed such platitudes as “build it and they will come”, “the product will sell itself”, and “meritocracies exist!”. If your brow is furrowing now, hopefully this post will be useful to you.

A lot of what I’m going to say you’ll probably have read from other people doing “what I learned posts”, but I think it is really valuable to repeat some of the same insights. Repetition of results is sometimes the only way to highlight their importance to the more mechanically minded.

We commercialised some real research

Our biggest success story for HE Inventions has been getting a project that started as a projector tied to a bit of 2×4 as part of John Hardy’s PhD and turning it into a real piece of factory machinery: the Digital Inspection Table.

It look a lot longer than we thought (about 3 years) and has been an incredible learning experience. If I could extract 3 things out of it which may be of use to another trying this route, they would be:

  1. Change management is the single biggest hurdle to distributing and disseminating disruptive products. You could have the most productive and efficient technology in the world, but if your users are not your customers (think larger corperate customers vs. their employees) you are going to have to communicate the benefits of the product in two very different ways: financial vs. how much easier this is going to make your job while not putting your job at risk.
  2. There is a sweet spot between a modest and ostentatius communication plan. Coming from an academic and engineering background, its very easy to purposely downplay your products and achievements. The product should speak for itself right? However, if you don’t show that little flash of excitement to your prospective customers then they also won’t be excited to hear what you have to say. Additionally shouting from the rooftops and having a street parade about how wonderful
    your products are will just lead to very defensive customers.
  3. The market decides what is “product-market fit”. It’s really tempting as an inventor and engineer to ignore feature requests that seem boring or tangential. Use every ounce of self control you have to squash those feeling and listen! Especially if you are entering a market you are unfamiliar with, if prospective customers are telling you what they’d like to see, they’re really saying “If it had this, I’d buy it”. Of course, it’s your judgement whether to implement those changes, but if you’ve yet to sell anything it’s probably wise to.

You’ve probably noticed that all the above wasn’t technical, and that’s because…

The tech bit was actually the easiest bit

As a company, we are really really good at building useful technology that will, and does, save our customers money and gives them an edge in the market. Our prototype product was first built in 3 months, and the final interaction of that prototype was finished by the first year and is still being used by our first customer.

So why did it take 3 years to launch with our partner, Bobst? To be able to make the product in a repeatable way? To be able to integrate with the IT of our customers?

Operations.

Legal, supply chain, and process documentation were, by several orders of magnitude, the lionshare of the work in getting this product to market. To break that down:

  1. We have partnered with another company to sell the product world wide that requires a lot of legal formalisation of process in terms of payment, customs, and internationalisation.
  2. We have a hardware product with different suppliers and subcontractors which all need to know what they are making and what our expectations are.
  3. We need to actually write down everything that happens from when we receive an order to maintenance 5 years down the line. We could get hit by a bus, but life continues on.

Sure, we still do technical work on the product – parts enter end of life so replacements much be added, bugs get found, features and improvements are added – but that is really just maintainance.

Self-funding is hard

While the last insights have been in the business, the next few are really *on* the business. You hear that a lot from director networking events. If you’re running the business but spend all of your time doing product work, there will definitely be large important areas of your venture you need to look at.

We have been self-funding since 2015. What do I mean by self funding? We raise our money by selling products and services to our customers, instead of using other financial instruments like cash-for-equity or loans.

I can honestly say it has been a terrifying and wild ride, and given the choice I would not do repeat the decision. As a consequence of it we have an agency wing in the business, and when we need to build up the war chest the company moves completely into it.

A product mindset and a project mindset are very different things and I believe when switching we pay the price in terms of productivity, scope creep, and burnout.

At the time when we made the decision, we had a technology without a real product, which is why we assumed we could never raise. If I was to do it again I would spend a month actually thinking about how much time we needed to get to where we are now, and approach investors. My mistake was assuming that unless we had a product ready to go, no one would talk to us.

Remote working with hardware is also hard

I love working from home – good coffee, great commute, food readily available. I can schedule when I’m going to engage in meetings, emails, slack and I’m incredibly productive because of it. The only reason I’ve gotten around to writing this is because I’m in my kitchen writing it. I try and encourage the rest of the team to work from home when they can.

However, we have a hardware product, and there’s only so much you can do with taking key sub components home to work with. Additionally, having an augmented reality product means that even if you can remote into a system in the office, unless you have a series of elaborate cameras set up, its nearly impossible to test your work.

We have a reference hardware build set up in the office. It’s small compared to our actual product, but its still some IKEA shelves and Rexroth beams – not exactly portable. As a consequence, the ability to work from home gets completely curtailed when we are doing a big engineering cycle – which realistically is where we would see the largest benefit of remote working.

I’m hoping as we grow and the product gets more mature as a team we can work from home more – but this won’t be the case for a young hardware startup. I think for hardware startups, which are hard anyway, they lose one of the great advantages of a pure software startup.

Starcraft classic is free

Finally, I’d like to point out that Blizzard have made the original Starcraft (and the expansion) completely free]. This has been an incredibly effective tool for relieving stress, burnout, and discovering that the quiet designer is actually a cold, calculating strategist and it would be incredibly useful to bring them into more planning meetings.

The PhD and Industry

Back in April I was invited to give a talk at the  Lancaster University Postgraduate Research Conference held at the university. The room would be full of PhD candidates and other postgraduates, so I wanted to give a talk that would have been helpful to me when I was at this stage.

I know the main thing worrying me at the time was about my options and if academia was right for me. I didn’t really consider that industry would be interested in my skills or if they even applied.

I was wrong about that, so I wanted to make sure the students in the room knew it was an option for them.

Here’s the video of the talk

Top 3 things to take away:

  1. Time and project management skills learned during the PhD are incredibly transferable to any other role you choose to pursue.
  2. A PhD is all about communicating complex concepts into understandable language. This puts you at an advantage within industry as you can quickly and efficiently spread your message.
  3. The skills you’ve picked up by finishing a PhD are valuable, rare, and sought after outside of academia.

If you’re interested in transitioning from your PhD into industry, I’m happy to advise. Please email me at carl at heinventions dot com or DM on twitter @carlc75

Projected DnD

So I wanted to build some interactive play maps for when running DnD games, so that I could hide rooms automatically and create a more involved experience. I already had the hardware to build this system, and combined with some JavaScript it was not long until the players were running the DnD starter set adventure on it.

Hardware

As part of my fledgling company, I have a lot of projectors and associated rigging equipment lying about.

So for when I’ve been DM’ing, I’ve used a Dell M110 projector mounted onto monitor desk mount that has been extended with a custom lathed plastic tube. With the extension, the projector ends up being about 1.5m above the table.

The projector isn’t the brightest in the world, especially against wood coloured tables, but sticking some white paper on the table surface and dimming the room lights worked great.

Software

I wrote a very simple html template to display the interactive maps. The interaction, in this case, was the DM being able to control which areas of the map (e.g. rooms) are currently visible.

This was done by making a number of “layers” which only covered the areas they were responsible for, and then toggling their visibility with JavaScript. The layers were made using Inkscape.

The layers which could be toggled had an img#id the same as the key that would toggle them (e.g. img#1, img#2, etc) and the following snippet was used to actually change the visibility.

 

function toggle_visibility(e) {
    // Toggle an elements visiblity
    if(e.style.display == 'block' || e.style.display == '')
        e.style.display = 'none';
    else
        e.style.display = 'block';
}

function khandle(e) {
    // Find the key that was pressed, and then toggle 
    // KEY.png's visibility
    e = e || event;
    var evt = e.type;
    var c = String.fromCharCode(e.keyCode || e.charCode);
    var handle = document.getElementById(c);
    toggle_visibility(handle);
}

function init() {
    // Make sure the first room is visible
    toggle_visibility(document.getElementById("1"));
}

document.body.onkeydown = khandle;
document.body.onload = init;

Future

So far, this system has worked quite well for me. It does require some preparation work (creating the area masks) and forgetting which area of the map is bound to which key can be a bit of a pain.

However, I think without too much effort I could create a “DM screen” that would be shown on my laptop where I could more easily control which areas are visible, play sound effects, or show more visual effects (e.g. lightning strikes, fire).

The code and non copyrighted resources for the first chapter of the starter set is up on my Github if anyone wants to try this themselves. It would work just as well for those builds which are using an LCD screen for a table too.

DnD: First Encounter at Lyst

It was everyone’s first time playing DnD, including mine so there will likely be rookie DM and player mistakes. We were all work colleagues from Lyst (@MakingLyst) and spent 3-4 hours in our canteen playing.

The whole night has fantastic fun and we will be continuing the quest to find the Mine of Phandelver in the future.

Characters

@StevieBuckley as ‘Iron’ Mike Baggins – Fighter, Folk Hero
@Maciej_Kula as Blane Kinglyquartz – Cleric
@ejlbell as Artemis von Spiegelhorn the Chaoshadow – Wizard
@trepca as Ljubomir ljivkovic Sljucica – Rogue
@wolffan as Kosef Longsummer – Figher, Noble

@carlc75 as The Dungeon Master

Setup

Projected maps,  Fog of War, Sound effects.

I used map resources from Mike Schley who has kindly put up the digital assets for a pittance. I made custom fog of war masks for the cragmaw cave map and used javascript to hide/show the different areas. The code and resources (minus Mike Schley’s maps) are up at GitHub.

Encounter 1, Goblin Arrows

In the city of Neverwinter, a dwarf named Gundren Rockseeker has asked the party to escort a wagon of supplies to the rough and tumble settlement of Phandalin, which lies a couple of days travel southeast. Gundren was excited, and claimed he had found “something big”, so promised to pay the party 10gp each to get the supplies to Barthen’s Provisions in Phandalin. He then rode on ahead with a warrior escort named Sildar Hallwinter as he needed to “take care of business”.

The party has spent the last couple of days with the an ox wagon on the road. ‘Iron’ Mike is riding an ox, guiding the cart with his animal handling skills. Arty and Kosef are in the back of the cart with the supplies: Arty trying to forcefully converse about foreign tax law unsuccessfully. Blane walks beside the wagon with Ljubomir bringing up the rear.

As the turn a bend, they notice 2 dead horses peppered with arrows in front of them. ‘Iron’ Mike stops the cart, and an irritated ‘Driver, driver, why are you stopping?!’ floats over from Arty. Annoyed, ‘Iron’ Mike drags Arty along to the horses to investigate. As they draw closer, they recognise the horses as those that their friends rode on ahead.

Before they can investigate further, 2 goblins rush from the under brush and attack ‘Iron’ Mike. The first goblin misses his swing, but the other manages to get in a hit. He attempts to retaliate with his mighty sword, but fumbles the swing. Instead a surprise arrow from Ljubomir takes the goblin through the chest. Arty, suitable annoyed at the goblin in front of it, sends 3 Magic Missiles to ‘explode’ it. Suddenly, a goblin arrow streaks from the southern under brush, flies past Kosef’s head, and lands in the cart with a thunk. Kosef spots the offending goblin shooter, grabs his axe, and charges into the under brush. His battleaxe swings down with such power it splits the goblin (and some small trees) in two. Across the trail, another previously hidden goblin is heard panicking and running away through the undergrowth to the north.

The battle over, and with Blane mostly oblivious to what just happened, the survivors check the goblin bodies for loot. Kosef grabs some arrows for ‘Iron’ Mike and is disappointed at the lack of loot from the malnourished goblins. Arty pokes at the residue of his slain goblin and laments that he could not learn more about it. ‘Iron’ Mike, however, finds that the goblin with the arrow in its chest is still alive and, with the help of Blane, manages to stabilise it.

Arty is brought over to translate, and finds that the goblin is named Stinkblade. Arty attempts to persuade Stinkblade that they will not harm him if he talks, but the goblin does not believe him, even when donning a godlike illusion. ‘Iron’ Mike attempts to intimidate the goblin into submission by sitting on him, but this only aggravates it. Finally, Blane casts Command and forces the goblin to speak.

They learn that their friends were captured by Stinkblade’s goblin troupe and were taken to their hideout in a northward cave. Their troupe leader had received orders to capture the duo via courier from Cragmaw Castle. At the mention of this place, Arty flies in to a rage and stabs the goblin, ending the interrogation.

Worried about Gundren and Sildar, the party decide to investigate this cave to the north. However, first they take a short rest and engage in a heated argument about taking the cart with them. ‘Iron’ Mike ends up winning, taking the cart with them, but at the cost of making the journey time much longer.

With wounds healed and spell slots replenished, the party head out slowly with the cart along a difficult woodland trail. ‘Iron’ Mike is sitting upon the ox, guiding them with twitches of his hands. Arty and Blane are in the cart discussing religions affect on crop yields in winter, Kosef is taking the rear guard and Ljubomir is out in front — on the lookout for traps and things to snag the cart.

After an hour on the trail, Ljubomir fails to notice a snare trap that is draped in front of him but just manages to jump out before he is snapped up. Kosef decides to take the front, and another hour later fails to notice a pit trap in front of him.
He noticed, however, that he was falling 10ft to the bottom of it. Climbing out, with minor injuries to body, major injuries to pride, he helped the cart navigate around the pit. After a further hour travelling, the party sees a large cliff coming into view, so decide to tie up the cart and oxen, then investigate on foot.

The party reach the cliff, trying to stay as quiet as possible. They exit the trail and come upon a clearing, which edges up to a stream. On the other side of the stream lies thick brambles and trees, and the stream is bursting forth from a cave in the cliff. There is room on the other side to walk into the cave.

Ljubomir stealthily creeps up to the stream and spots two goblins in the under brush, not paying attention to him or anything else that isn’t their simple stones game. He slowly creeps back to inform the others of the enemy.

With a surprise attack, Blane channels Sacred Flames to burn the goblins, but miss and burn everything else around them. As the under brush turns to ash, Ljubomir and ‘Iron’ Mike unleash arrows, which both miss. Kosef charges with his great axe brandished and cleaves a goblin in twain. Arty sends a ray of frost at the second goblin, who freezes, shatters, and scatters into the wind.

Blane scouts ahead into the cave, using his Dwarfen sight to see in the dark. He stealthily notices the wolf kennel and assesses than they are very hungry, more so than caring about guard duty. Sneaking back, Blane informs the party and they get to work dragging the 2 pieces of goblin into the cave. ‘Iron’ Mike gains acceptance, but not leadership, of the pack, in order to drag the goblin meals inside. The wolves begin eating, but will not let anyone near them.

Blane scouts further into the cave and notices a wooden bridge, 20ft above the main passage – along with a goblin sentry. The goblin does not notice him. Blane sneaks back, and the party come up with a plan. Creeping forward, Ljubomir and ‘Iron’ Mike ready their bows as Arty creates a ball of light in front of the goblin. Blinded, it did not see the two arrows that sunk into its heart. The goblin toppled forward into the stream and floated out of the cave.

Noticing a small, fragile, trail to the left Blane and Arty scouted ahead. At the top of the trail they successfully find rooms at either end of the passage they find themselves in. At the western end: a barracks of sorts with 6 goblins; to the east: a room with 2 dammed pools of water and 3 goblins. The party decide a sneak attack on the larger group of goblins in the western room. Everyone climbs up the fragile trail in pairs until the party is in the upper corridor.

From the shadows, Arty casts sleep on 4 of the goblins, with ‘Iron’ Mike taking out a fifth with an arrow. Ljubomir creeps in to the room, and attacks a much larger goblin, scoring a critical hit with an arrow that perfectly hits the part of the goblin’s brain that makes it explode. Entering the room the party find Sildar who is badly beaten. They help him up and pass him a goblin short sword for protection. Sildar says he will help where he can and will answer questions once they deal with the goblins.

Seeing the sleeping goblins as a threat, ‘Iron’ Mike brings out his secret weapons. Ham fists, from his encounter with a greedy boat captain in Neverwinter, and punches a sleeping goblin as hard as he can. The goblin takes massive damage, but survives. The ham, now quite old, explodes sending rancid meat into the eyes and mouths of the sleeping dwarfs, instantly waking them.

Ham Fists: When working in the galley of a ship in Neverwinter, ‘Iron’ Mike led a workers revolt against a captain who was unlawfully exploiting his workers. Finding two large hams in the kitchen, he plunged his hands through the flesh to grab the sturdy ham bones within, creating his Ham Fists. Using his weapons, he beat the corrupt captain into submission, before taking him to the guards.

The party, thoroughly annoyed at having to engage the 4 groggy goblins send arrows, Rays of Frosts, and the business end of an axe into the goblins. 3 are killed but 1 managed to escape and run towards the other goblins at the pools in the eastern cave.

Giving chase, ‘Iron’ Mike, Ljubomir, and Kosef all send ranged attacks, but due to the darkness miss. Arty catches the fleeing goblin with a ray of frost, not killing it but slowing it. They could only watch in apprehension as the very cold goblin rounds a corner into the welcoming arms of reinforcements.

Blane chants a prayer to bless the party in preparation of their next fight. ‘Iron’ Mike, Ljubomir, and Kosef ready ranges attacks on the next goblin they see across the bridge. The other goblins across the bridge move to confront the party. Arty casts light onto the ceiling of  the pool room, flooding it with light. This fortunately illuminates a goblin on the other side of the bridge. Arrows and javelins pummel the goblin, instantly killing it. The other goblins move up to the bridge, one hiding behind a stalagmite. Meanwhile the ham fist survivor manages to run into a deeper cave on the southern wall, no doubt alerting those inside.

An arrow from Ljubomir takes out the goblin on the bridge, allowing ‘Iron’ Mike to charge at the stalagmite with his great sword drawn. As he stabs the goblin and lifts it above his head on the tip of his sword, Arty finishes him off with a quick Ray of Frost.

Regrouping outside of the next cave, the party try to perceive what is inside. Kosef peers in and sees a near empty room with crates and sacks piled up near the far wall. There is more of the cave to the right, but it hidden from the entrance. Just as Kosef is about to turn to the others, he notices a goblin foot stick out from behind a sack. The ambush is ruined as he notices 2 more limbs behind various items. Telling Arty the goblin positions, 3 Magic Missiles zip into the room to injure the goblins. The most injured goblin flies at Kosef in a rage, to only be split in two by his great axe.

Smelling the rancid ham that is emanating from the original goblin survivor, ‘Iron’ Mike bursts into the room and sets his sites on the poor bloodied beast — but not before being bitten by a wolf which was lying in wait in the shadows. ‘Iron’ Mike shrugs it off to finish the goblin who broke his Ham Fist. Only then does he notice how badly he is bleeding. Ljubomir enters the room and hides behind ‘Iron’ Mike, while trying to send an arrow into one of the remaining goblins — but he misses. Kosef enters the room to levy his axe upon the wolf, heavily wounding it. Arty attempts to freeze a goblin with Ray of Frost, but misses. The two remaining goblins move up to attack the intruders, one focusing on ‘Iron’ Mike, landing a crippling hit, and the other focusing on Kosef, but he misses.

Out from behind one of the stalagmites of the cave, a large bugbear appears, screaming ‘KLAARG WILL KILL THE INTRUDERS‘. Klaarg then throws a javelin at Kosef, heavily wounding him before moving closer. Blane enters the cave and lays his hand on Kosef to cure his wounds. ‘Iron’ Mike, fed up of goblins, brings his great sword down in a tight arc to finish off the goblin attacking him, then uses his Second Wind to make a slight recovery. Ljubomir sends an arrow to finish off the final goblin.

Kosef levels his axe on Klaarg, attempting to cleave him from the crotch up, but the axe bounces off his armour. Arty steps fully into the cave and tries to grab the wolf to use his Shocking Grasp, but the wolf sidesteps away. Retaliating, the wolf tries to get a bite out of Arty, but misses. Klaarg swings his morning star at Kosef, but the brute of a weapon swings above his head.

Blane attempts to finish the wolf off with his hammer, but looses his footing and fumbles the blow. ‘Iron’ Mike sheaths his great sword and brings out his longbow, firing an arrow into Klaarg. The arrow lodges into his shoulder, sending him into a rage. Ljubomir performs a ranged sneak attack and sends an arrow deep into Klaargs gut. Kosef swings with his axe, taking a chunk of Klaarg with it. Arty tries to send a Ray of Frost at Klaarg, but just succeeds in freezing a nearby wall. The wolf tries a second bite, but misses again, and Klaarg swings again at Kosef with his morning star, but his rage has effected his accuracy, and he misses by a clear foot. Finally regaining his composure, Blane smashes his hammer onto the wolfs skull, ending it there. ‘Iron’ Mike and Ljubomir send two arrows into Klaargs face, sending him reeling backwards onto the ground and into the afterlife.

The battle over, the party surveys their surroundings. Gundren is not here, but there are many branded crates in the cavern which look recoverable, and a chest in the corner of the room. Inside the chest they find 1200cp, 110sp, a small statue, and 2 potions. The party splits the cash, ‘Iron’ Mike pockets the statue, and after Arty identifies the potions as healing potions, they are given to the fighters.

Interrogating Sildar does not provide much more information than they got from Stinkblade, other than he will pay the party 50gp to escort him to Phandalin, payable there. The party agree and start hauling out the stolen crates to their parked wagon, intent on returning them to their owners, feeling more experienced from the whole encounter. ‘Iron’ Mike tries one last time to tame one of the tied up wolfs, and manages to gain the trust of the smaller wolf, which the party allow him to keep so long as it is chained up and doesn’t bite anyone.

They decide to camp for the night outside the cave, away from the stench of dead goblins and under the stars.

Stripe CTF 3.0

Sadly, level 3 would not run for me, even with Stripe’s patch, so I could not continue with the competition. It was fun while it lasted though – C

Wednesday saw the beginning of another Stripe CTF! This time I was in London when it started so I went to the launch meeting with some old uni friends.

The theme this time was distributed computation, so with a tiny netbook, I dove in to the levels.

Level 0

Level 0 was essentially an exercise in optimisation. A given text input was checked against a list of words. If an input word was in the preset dictionary, it had to be tagged. The preset dictionary was an ordered list, and as such was O(n) to search. By applying the following:

index 1558f2d..d07273f 100644
--- orig.rb
+++ mod.rb
@@ -1,4 +1,5 @@
#!/usr/bin/env ruby
+require 'set'

# Our test cases will always use the same dictionary file (with SHA1
# 6b898d7c48630be05b72b3ae07c5be6617f90d8e). Running `test/harness`
@@ -7,6 +8,7 @@

path = ARGV.length > 0 ? ARGV[0] : '/usr/share/dict/words'
entries = File.read(path).split("n")
+entries = Set.new(entries)

contents = $stdin.read
output = contents.gsub(/[^ n]+/) do |word|

 


The list is turned into a set with a  O(1) lookup time. Significantly speeding up the operation.

Level 1

This level was about cryptocurrencies, and to pass this level you had to mine a … ‘GitCoin’. Essentially, you were given a repo with an initial catalog of transactions. You had to successfully submit a transaction with gave your given use a gitcoin.

Proof of work for a gitcoin was determined by ensuring that the git commit message had a SHA1 signature that was lexigraphically smaller than the difficulty. So add a nonce to your commit message and keep cycling though random numbers until the commit message had a valid signature.

Stripe provided a very slow bash reference implementation, which I still used to pass the level. Instead of increasing the nonce in bash though, I wrote a python script to find a correct hash for me faster.

import sys
from hashlib import sha1
import random
import string
import Queue as queue
import threading

def work(diff, tree,  parent, timestamp, q):
    diffl = len(diff)
    diff = ''.join('0' for x in range(diffl))
    body = "tree %snparent %snauthor CTF user <me@example.com> %s +0000ncommitter CTF user <me@example.com> %s +0000nnGive me a Gitcoinnnnonce: " % (tree, parent, timestamp, timestamp)
    while True:
        body_b = '%s%s' % (body, ''.join(random.choice(string.hexdigits) for x in range(8)))
        s = sha1('commit ' + str(len(body_b)) + '' + body_b)
        hex = s.hexdigest()[:diffl]
        if hex.startswith(diff):
            body = body_b
            break
    q.put(body)

def main():
    diff, tree, parent, timestamp = sys.argv[1:]
    q = queue.Queue()
    threads = [threading.Thread(target=work, args=(diff, tree, parent, timestamp, q)) for i in range(1)]
    for th in threads:
        th.daemon = True
        th.start()

    body = bytes(q.get())
    with open('/home/carl/level1/test.txt', 'w') as f:
        f.write(body)

    for th in threads:
        th.join(0)

if __name__ == '__main__':
    main()

There were some hurdles I came across while solving this, which show in the code.  The git hashing command git hash-object -t commit didn’t just take the SHA1 hash of its input, it would first prepend commit len(data) before hashing. This was easy enough to find with a bit of searching, but a major issue I was having that I couldn’t replicate the SHA1 hash unless I first wrote the commit to a file, rather than streaming via stdout. So I just wrote to a file and modified the miner bash script to change:

@@ -56,12 +56,12 @@ $counter"

        # See http://git-scm.com/book/en/Git-Internals-Git-Objects for
        # details on Git objects.
-       sha1=$(git hash-object -t commit --stdin <<< "$body")
+       sha1=$(git hash-object -t commit /home/carl/level1/test.txt)

        if [ "$sha1" "<" "$difficulty" ]; then
            echo
            echo "Mined a Gitcoin with commit: $sha1"
-           git hash-object -t commit --stdin -w <<< "$body"  > /dev/null
+           git hash-object -t commit --stdin -w /home/carl/level1/test.txt  > /dev/null
            git reset --hard "$sha1" > /dev/null
            break
        fi

Which let me get the correct hashes and mine the coin.

Level 2

Level 2 was all about DDOS attacks. The idea was that there were a number of back end servers, a reverse proxy (which you modified), and a number of clients, some malicious and others not. You had to modify the reverse proxy (called shield) to not let malicious traffic through, and to attempt to minimise back end idleness. Scores were determined by a test harness and also on the git push hook.

Stripe provided the attack code for reference, which made the level really easy. Malicious attackers basically spawned more connections more often, and the numbers that they spawned was defined in the file, as:

simulationParameters = {
'clientLifetime': 2, // In rounds
'roundLength': 500, // In ms
'roundCount': 40,
'clientsPerRound': 5,
'pElephant': 0.4,
'mouseRequestsPerRound': 2,
'elephantRequestsPerRound': 50,
'backendCount': 2,
'backendInFlight': 2,
'backendProcessingTime': 75
};

So from this you can see that malicious clients send 50 requests per round, and normal clients send 2.  So my first solution was just to limit the number of connections from each client with a simple counter. My implementation looks like:

diff --git a/shield b/shield
index c67bd68..8ba87f2 100755
--- a/shield
+++ b/shield
@@ -7,6 +7,7 @@ var httpProxy = require('./network_simulation/lib/proxy');
var checkServer = require('./network_simulation/lib/check_server');
var nopt = require('nopt');
var url = require('url');
+var rcount = {};

var RequestData = function (request, response, buffer) {
this.request = request;
@@ -14,6 +15,16 @@ var RequestData = function (request, response, buffer) {
this.buffer = buffer;
};

+
+function checkRequest(ip){
+ if (rcount[ip] === undefined) {
+ rcount[ip] = 1;
+ } else {
+ rcount[ip]++;
+ }
+ return rcount[ip] <= 4;
+}
+
function ipFromRequest(reqData) {
return reqData.request.headers['x-forwarded-for'];
}
@@ -29,10 +40,10 @@ var Queue = function (proxies, parameters) {
};
Queue.prototype.takeRequest = function (reqData) {
// Reject traffic as necessary:
- // if (currently_blacklisted(ipFromRequest(reqData))) {
- // rejectRequest(reqData);
- // return;
- // }
+ if (!checkRequest(ipFromRequest(reqData))) {
+ rejectRequest(reqData);
+ return;
+ }
// Otherwise proxy it through:
this.proxies[0].proxyRequest(reqData.request, reqData.response, reqData.buffer);
};

I committed and pushed, and surprisingly, this gave me a passing score!

Level 3

This is where the story gets sad. I checked out the code, and I could not get the ./test/harness to work correctly. The tak was a file indexing service, and it had to be optimised. It was written in Scala, which I have never used – so I could not work out how to debug it.  Stripe released a fix, but it still did not fix my issues. At which point I had to move on to other things and could not complete the CTF.

Sad times.

Fashion Hackathon – London Startup Weekend

The weekend of the 14th December I attended the London Startup Weekend Fashion Hackathon. This was a much larger event than the previous hackathon I attended and was more geared towards creating a viable business as well as the tech to support it.

The format was fun, on the first day a number of people would pitch ideas, we would all vote for them, then form teams to begin on the Saturday morning. I attended in order to build something new and fun, so just stood back and listened for some interesting pitches.

There were two super interesting pitches: A smart bag which worked out what was in your bag and alerted you if things were missing; and an automatic garment detector which would allow you to take a picture, and then buy the clothes from the picture.

I ended up picking the image recognition project as it sounded the most fun and I didn’t think we would be able to source an RFID reader (or similar) over the weekend. (it turned out that this team didn’t pitch,  so maybe they pivoted or disbanded?)

The mini-startup we made was called LookSnap, and it was fun and quite gratifying to see that my business instincts were reinforced by the actions of the rest of the group. Over the day and a half that it was worked on,  I think the business model ended up fairly solid.

My main job for the weekend was getting the image recognition working. In terms of the technology and with the very short time-scale in mind I decided to limit the acceptable inputs as much as possible. As such, I designed an algorithm that would be able to extract the clothing (top, bottoms, shoes) from a picture of someone who was facing forward and had their arms down.

The algorithm works as follows:

  1. Use OpenCV to detect a face
  2. With the face position, composite a “clothing mask” (see images) onto the original photo using graphicsmagick
  3. This than gives you a fairly decent cut out of just that persons clothes. Apply different masks for top, bottom, and shoes.

Once I had these images, the idea was to use reverse image search on the lyst.com domain to always return something relevant.

However, there was a slight hitch with this plan. Google reverse image search, which worked well manually, had no API in which to pass an image…

So the stopgap method was to extract the average colour from the garment by averaging all the pixel colours that were in the appropriate garment masks, and then mapping these colour to their more broader hue. This turned out to be incredibly hard and would have been impossible if not for reverse engineering a very good hue detector at http://www.color-blindness.com/color-name-hue/

Once this was working I packaged it all up in a FLASK api where an image file was posted to the endpoint, the above magic happened, and a json file was returned giving the X,Y of the garment in the photo, and information on the product name, description, image, and a buy link.

Unfortunately there was not enough time to integrate the service into our POC app, which would have made persuading the judges that we have actually done basic image detection much easier!

Overall, the team did an excellent job, and even though we didn’t win I feel the weekend was very well spent.

Data Science London Hackathon

On the weekend of October 5th, I participated in the Data Science London Hackathon for Smart Cities. This involved having access to a number of datasets of city based data from London. These datasets included things such as:

  • Car Parking Counts
  • Oyster Journeys
  • Incidents of Antisocial Behaviour

A couple of guys from work and myself made a team (TeamLYST) and decided to have a closer look at the antisocial behaviour dataset to see if we could make something interesting.

The data gave events that happen on a given day, for a given street for about a month. The events were lovingly given as:

  • Dog Fouling
  • Graffiti
  • AntiSocials (public urination, vomit, etc)

So from this we decided to make a predictive application that would generate a number of likely events to happen for a Monday, Tuesday, etc.

The application was split into 3 parts:

  1. Pre-processing the data into a format which was useful, adding in default values etc,
  2. Creating a generative predictive model from this data
  3. Visualising the data

There were three on our team, so I picked the visualisation. I did this using Python and PyGame to draw a PNG of London, which was generated by open streetmap. Event locations were translated to map locations, and the map could be translated and zoomed with the events staying where they were supposed to be. The visualiser allowed you to flip through different days and to access new generated events.

The generative model was trained by looking at each Monday, Tuesday, etc to work out a count of each event type per street, which was then normalised against the total events of that day. This gave a likelihood for each event in each street for each day in the week. Assuming that all events are equally likely to occur (a big assumption) we can sample a normal distribution and apply this to our likelihood map to generate an event. We do this the same amount as the average number of events for that day and we get a pseudo -typical event set.

The final product worked as intended, and with more accurate data could be extended into a nice predictive application to help with local law enforcement responses and distributions.

We didn’t win the hackathon, but it was a fun experience. We put up a video of our work too.

Migrated fully to WordPress

I’ve moved my main domain to WordPress now, so carlellis.co.uk, www.carlellis.co.uk, and blog.carlellis.co.uk all point to here now!

The move has been slow and forthcoming with my originally semi-static site needing more dynamic content and then becoming stagnant as I focused on adding things to the WordPress. The only thing which was given attention on the old site was the literature review pages.

I didn’t want to lose the site completely, so currently it is parked at old.carlellis.co.uk .

I consider this a pre-emptive strike against my growing NIH syndrome.

A Fractal Height Map Generator in Ruby

[I’m migrating my old articles to the blog in order to switch to it entirely]

Date: 25th March 2010

Introduction

This article describes the theory behind, and how to implement, a basic fractal height map generator. It is based upon the algorithm defined at http://gameprogrammer.com/fractal.html. Height maps are used in many things: positioning software, graphical rendering, and procedural map generation. Given the right conditions, height maps can be used to create visually stunning images, and are frequently used with an alpha channel to simulate clouds.

All source code used in this article shall be made freely available, under a Creative Commons GPL Licence

The implementation which will be defined here outputs an array of numbers, which on the surface seems fairly mundane. However, with a bit of tweaking with VT100 colour codes, or passing to an image generation program, the algorithm can produce outputs such as this:

The ASCII renderer assigns a colour code to a range of numbers and then depending on your ranges, you can create rainbow-like maps like the one above. The grey scale and transparent images had their number arrays passed to an image generation program called RMagick.

 

The Theory

I will go through the basic idea again as it was defined in the gameprogrammer link, to keep a consistency with terms used further in the article. So before we get on to the DiamondSquare algorithm, I shall implement the simpler 1 dimensional algorithm, which will describe the height of a line, similar to a horizon. The patterns created show some fractal behaviour, in that it is said to be self-similar. An object is said to be self-similar when magnified subsets of the object look like, or are identical to, the whole and to each other[1].

In context of this algorithm, it means that as we add more detail, the more rougher and major features will still hold true, but more detail will become apparent as we look closer. This makes the algorithm ideal for recursion or iterative methods. This implementation uses an iterative method.

Midpoint Displacement in One Dimension

For the creation of the 1 dimensional height map, similar to a horizon, a very simple algorithm is used:

    def generateLine(length)

      # Due to this algorithm being simple for
      # the articles sake, length should be 
      # constrained to the powers of 2. 
      #
      # As we need a midpoint, however, length
      # should be defined as (2^n)+1.

      # Create an array which describes a line.
      # Set the default values to 0American Standard Code for Information Interchange 
      line = Array.new(length, 0)

      # Define the range of the terrain values.
      # For this example we shall take the range
      # of values to be -63 to 63, with the midpoint
      # at 0, out default value. 
      # Range is then 128.
      range = 128;

      # Work out the number of line segments
      # levels there are in the line. As each line 
      # segment level is defined by deviding by two 
      # until length is 1, the number of segments
      # is the log_2 of the length.
      noSegments = Math.log(length-1, 2)

      #Iterate through the levels
      (1 .. noSegments).each{ |level|

        # Work out the line segment length so you
        # can properly address the offset.
        segLength = (length/2**level)

        # Work out the number of line segments
        # within this level
        noSegL = (2**level)-1

        # Iterate through the line segments and 
        # apply your random function.
        (1 .. noSegL).each{ |segOffset|

          # If value is not zero, skip over it, done on a previous
          # level
          if( line[segLength*segOffset] == 0 )

            # Make sure the current value of the line
            # is directly midway between its two parents.
            line[segLength*segOffset] = (line[segLength*(segOffset-1)] + line[segLength*(segOffset+1)])/2

            # Apply random function to value
            line[segLength*segOffset] = randomFunction(line[segLength*segOffset], level, range)

          end
        }
      } 

      return line
    end

Now as you can see the most important part of that algorithm is that which I have purposely missed, randomFunction. This is where you, quite obviously, define how you want your heights defined. A good way is to simply use a bounded random function, where the bounds are defined by the line segment level you are currently within. For example, a function like:

    def randomFunction(value, level, range)

      # Roughness constant 0 < h < 1
      # As h approachs 0, the level dependent
      # bounds grow and tend to 1 for all values
      # of level
      h = 0.8

      # Define bounds in terms of level and a roughness
      # function
      multiplier = 2 ** (-h * level-1)

      # Perform random function, bound it, and then apply 
      # multiplier
      value += (rand() * (range) - (range / 2)) * multiplier

      # Return
      return value
    end

Would offset the value of the line a random amount which is bounded by a function dependent on the line segment level and a roughness coefficient. As this function is the heart of this algorithm and the 2 dimensional algorithm, I will go into some detail on the use of the roughness coefficient. If the roughness coefficient is set to 1, then the multiplier acts the same as : 2^{(-l-1)}; 0 < l < infty ; l in mathbb{Z}^+[/latex]. Decreasing the value of h flattens out the function meaning the bounds are less constrictive and allowing for much rougher terrain. Here is a plot of the multiplier when h=0.8 and h=0.2, and a plot of the generated lines when those constraints are used. X axis is equal to line segment level.  [gallery columns="2" ids="434,433"]  As you can see, the roughness coefficient makes a massive difference to the outputted numbers. For those interested in recreating the plot, I piped the output of the above code into a text file, and then used <a href="http://www.gnuplot.info/">GNUPlot</a> to make the images.</p> </div> <div id="2d"> <h3>Extending into 2 dimensions - The diamond square algorithm</h3> <p>To extend this algorithm into the second dimension, we have to imagine the terrain data as a two dimensional array of numbers. Each number represents a height in this two dimensional field, and so each column and row can be treated similarly to above.</p> <p>To split up a two dimensional array in a self-similar way we must use squares, or diamonds, which are analogous to the line segments of the 1 dimensional algorithm. Then, rather than using the ends of a line segment to work out a base height the corners of the square, or diamond, are used. For example:</p> [gallery columns="2" ids="436,435"] <p>Like the line segment algorithm, the mathematical 'meat' is the same random function as before. The complexity comes in managing which indexes are part of a diamond or a square. So, for example, here is a code segment which works out indexes of a square, depending on level and location, and applies the random function:</p> <pre>    # Get the corners of an arbitrary square and perform operation     # on center.     #     # @param  array           Array to use     # @param  topleftIndexX   X index of top left of square     # @param  topleftIndexY   Y index of top left of square     # @param  length          Length of the square      # @param  level           Level into the calculation     def processSquare(array, topleftIndexX, topleftIndexY, length, level, range, h)        # Get coordinates of the corners of the square       toprightIndexX    = topleftIndexX       toprightIndexY    = topleftIndexY + length + ((level == 0) ? -1 : 0)        bottomleftIndexX  = topleftIndexX + length + ((level == 0) ? -1 : 0)       bottomleftIndexY  = topleftIndexY        bottomrightIndexX = topleftIndexX + length + ((level == 0) ? -1 : 0)       bottomrightIndexY = topleftIndexY + length + ((level == 0) ? -1 : 0)        middleX           = topleftIndexX + (length)/2       middleY           = topleftIndexY + (length)/2        # Get values       topleftValue      = array[topleftIndexX][topleftIndexY]       toprightValue     = array[toprightIndexX][toprightIndexY]       bottomleftValue   = array[bottomleftIndexX][bottomleftIndexY]       bottomrightValue  = array[bottomrightIndexX][bottomrightIndexY]        # Get average       average = (topleftValue + toprightValue + bottomleftValue + bottomrightValue)/4        # Set new value       array[middleX][middleY] = average + calculateOffset(level, range, h)     end</pre> <p>Where <em>calculateOffset</em> is the random function in this application. The diamond calculation algorithm is very similar and looks like this:</p> <pre>    # Get the edges of an arbitrary diamond and perform operation     # on center     #     # @param  array           Array to use     # @param  topIndexX       X index of top of diamond     # @param  topIndexY       Y index of top of diamond     # @param  length          Length of diamond     # @param  level           Level into the calculation     def processDiamond(array, topIndexX, topIndexY, arraylength, level, range, h)        # Adjust       arraylength -= 1       length = arraylength/(2 ** level)        #Get coordinates of the diamond       rightIndexX   = topIndexX + length/2       rightIndexY   = (topIndexY == length) ? length/2 : topIndexY + length/2         leftIndexX    = topIndexX + length/2       leftIndexY    = (topIndexY == 0) ? arraylength - length/2 : topIndexY - length/2        bottomIndexX  = (topIndexX + length/2 == arraylength) ? length/2 : topIndexX + length       bottomIndexY  = topIndexY        middleX       = topIndexX + length/2       middleY       = topIndexY        # Get values       topValue      = array[topIndexX][topIndexY]       rightValue    = array[rightIndexX][rightIndexY]       bottomValue   = array[bottomIndexX][bottomIndexY]       leftValue     = array[leftIndexX][leftIndexY]        # Get average       average = (topValue + rightValue + bottomValue + leftValue)/4        # Set new value       array[middleX][middleY] = average + calculateOffset(level, range, h)        # Wraps       if(middleX == arraylength)         array[0][middleY] = array[middleX][middleY]       end       if(middleY == 0)         array[middleX][arraylength] = array[middleX][middleY]       end     end</pre> <p>The only difference with the above snippet is the different indices it retrieves, and that it must handle wrap around for some of the edges.</p> <p>So currently, we can create arbitrary diamonds and squares within a 2-dimensional array and assign a fuzzy average of the edges according the <em>h</em> value. Now all we need is some code to manage traversing through the levels of iterations and through the diamonds and squares themselves. Here is my solution:</p> <pre>    # The main control loop for the algorithm.     #     # @param  lengthExp       Length exponent     # @param  range           Value range     # @param  h               Roughness constant     def generateTerrain(lengthExp, range, h)        length = (2 ** lengthExp) + 1        array = Array.new       array = createArray(array, length)        #Go through Levels (irerative recursion)       (0 .. lengthExp - 1).each{ |level|          # Iterator for the Square part of the algorithm         # Will go through the x-axis coords         (0 .. (2 ** level) -1 ).each { |sqx|            # Y axis coords           (0 .. (2 ** level) -1).each { |sqy|              gap = length/2 ** level             x = (0 + (gap*sqx))             y = (0 + (gap*sqy))              processSquare(array, x, y, gap, level, range, h)           }         }          # Iterator for the diamond part of the algorithm         (0 ... (2 ** (level+1))).each { |dix|            # Offset in the number of points on the y-axis. Dependant           # on if x iteration is even or odd.           offset = (dix.even?) ? 1 : 2           (0 ... (2 ** (level+1)/2)).each { |diy|              gap = (length/2 ** (level+1))             ygap = 2 * gap              x = (0 + (gap*dix))             if (dix.even?)                y = 0 + (ygap*diy)             else                y = gap + (ygap*diy)             end             processDiamond(array, x, y, length, level, range, h)           }         }       }       return array     end</pre> <p>And this gives us our array with its height map hidden inside. Using a library like <a href="http://rmagick.rubyforge.org/">RMagick</a> we can output images like the ones shown above. To create the gray scale image, the following code was used:</p> <pre>  image = Image.new(array.length, array.length)    (0 ... array.length).each { |x|     (0 ... array[x].length).each { |y|       val = array[x][y] * (2**9)       # Create greyscale image       image.pixel_color(x, y, Pixel.new(val, val, val, val))     }   }   image.display</pre> <p>Which just takes the value in the array, and multiplies it by 512 which gives the values a range of [latex]0 ge v ge 2^{15}, ; frac{v}{512} in mathbb{Z} . This gives us the gaseous image that has been generated above.

Code Listings

A library version of the ruby code found in this tutorial can be found at GitHub.

References

  1. Voss, Richard D., FRACTALS in NATURE: characterization, measurement, and simulation. SIGGRAPH 1987

Creative Commons License
Ruby Diamond Square Height Map Generator by Mr Carl Ellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
Based on a work at gameprogrammer.com.