Recap: Rotterdam Meetup (18.07.2018) Part 2

The inaugural Cardano meetup in the Netherlands was held last week in Rotterdam. From the beautiful event space, the amazing speaker line up and the overwhelming attendance from the Dutch community, it’s an understatement to say this meetup was a success. Special thanks to Blocklab for providing the venue and to our community members @ilhan, @bullish and @Andy_Hendrikx for organizing the meetup!

It includes the summary of Bernardo David’s presentation on Ouroboros and Proof-of-Stake.

Following Bernardo’s talk, the next speaker was Edsko de Vries, a consultant for IOHK from Well-Typed, a Haskell consultancy firm. He presented on the Cardano wallet, and specifically about the mathematics underneath it.

UTxO

• UTxO stands for Unspent Transaction Output
• the Cardano wallet is based on a UTxO model, and this wallet is used for making payments
• Edsko explained transactions from a real-world “cash” setting and compared it to UTxO
• in the example, we have: Alice who wants to pay Bob 70.

• as you can see from the image, this is generally what we see now with our bank accounts and it shows a transaction that takes 70 out of Alice’s account and adds 70 to Bob’s
• and relating this to cash, if Alice has a 100, it would be possible for Bob to give 30 back to Alice and they would complete a transaction of 70

• but in UTxO, bob does not give change
• therefore, for Alice to give Bob 70, she can take her 100 and “destroy” it, giving her 70 and 30

• the act of “destroying” the 100 coin is necessary to avoid any double-spending
• this exact process can also be done by taking two 50’s
• this process is called UTxO

Dust

• now let’s look at a scenario where Alice wants to pay 8
• she has a 50 and 10, and Bob has nothing
• Alice can choose to break the 50 or 10, and you might think the obvious thing to do is to take the 10 and get 8 and 2
• but this creates the problem of dust because that ‘2’ coin has a very small value
• you do not want to have too many small coins
• small coins are bad for performance, they assumingly will be harder to spend
• there are also limitations to how many coins can be used in a transaction meaning you will end up with coins that you cannot spend
• there are also transaction fees in the Cardano protocol with a variable that is dependent on the data size of the transaction, this means the fee can be higher when you use more coins for a transaction
• therefore, in this circumstance, the preference is to choose the 50 and break it so that you pay 8 and keep 42
• if you are not careful, you will end up with lots of small coins, otherwise referred to as dust

Self Organization

• so how do we do this coin selection?
• Edsko explains how complex behaviors can emerge from very simple rules
• in nature and biology, you can examine flocking birds
• there isn’t one bird that is a leader but every bird behaves on their own and their group behavior of flocking emerges

• they have taken inspiration from this and looked to avoid having lots of small coins or dust in a wallet
• to address these issues and to find a solution, they did many simulations

• this chart shows the distribution of coins, the x axis represents the size of coins
• and the y axis shows how many we have
• within the small graph, the blue line is balance and the red line is total number of coins in the wallet
• the total number of coins is what you want to keep down
• so to go back to our last example, the now obvious thing to do is to always take the largest coin (ie. taking the 50)
• but, if you always take the larger, the number of dust will still continue to go up and up and the number of coins grows to 60,000
• watch the ‘Largest First’ simulation:

• which brings us to our first Self Organisation Principle:

Self Organisation Principle #1: If we choose a coin at random, we are likely to pick a small coin precisely when there are many small coins.

• the next simulation shows when they added a new policy “Random” which selects coins at random
• in a situation where there is a lot of dust, it is likely that the Random policy will use them and clean up the dust
• when the Random policy is initiated, you see a sudden drop

• then you think, maybe using the Random function is best since it will use small coins
• but there is also the downfall, that though it may be cleaning them up, it is also generating dust
• watch the simulation and you can observe dust being generated

Self Organisation Principle #2: If for each payment of value x we create a change coin roughly of the same value x, then we will end up with a lot of change coins in our wallet of size x precisely when we have a lot of payments of size x.

• Edsko now explains the Random-Improve coin selection algorithm, one that is proposed with Cardano
• from this algorithm, they found that the generation of dust was much reduced
• it was further tested in a large number of scenarios and proved to be resilient and show good results
• if we go back to the example where Alice wants to pay 70, imagine her selecting coins at random
• say she choose a very large coin, for example, of a value of 300
• one option would be to put this aside and continue her search
• the second option would be to give up at that point and use that coin
• the first option is actually not a good solution because in the worst case scenario, she will continue to look at every coin in her wallet looking for a good one (something as close or equal to 70)
• this process would of course be very slow and is not good for performance
• if we return to the second option and set an upper bound on the size we consider acceptable (in this example, set to twice the payment value) then the algorithm will take advantage of self organisation and create a solution that works
• so in the scenario given, Alice will pick randomly out of her coin, and if she were to go above twice the value of 70 and select coins that add up to 140, then she will give up and use those coins

• this brings us to our third and final principle
• one that is very simple but works well

Self Organisation Principle #3: Searching the wallet for additional coins to improve our change is only useful if the wallet contains coins that are sufficiently small.
But precisely when the wallet contains many small coins, it is less likely that a randomly chosen coin will push the total above the upper bound we set.

Wallet Balance

• after learning about coin selection, Edsko went on to present about wallet balance
• wallet balance pertains to the question: “how much money do I have?”
• this seems like an easy question but in reality, it is quite complicated
• IOHK has a mathematical document with 45 pages of proofs for a cryptocurrency wallet, and a large part of it is about balance
• differences in balance can arise from pending transactions
• say for example, Alice has sent 70 to Bob but it has not yet gone through in the system

• Bob hasn’t gotten the 70, and Alice will see her balance vs. available balance
• current balance shows the last registered balance
• available balance shows how she had to break her 100 to make 70 for bob
• and finally, the total balance which includes the “change” she gets back from the pending transactions
• this final balance is ‘new’ to us because in a bank account, you wouldn’t need to wait for change back from your transactions
• to add to this, there is actually another fourth balance…

• when you use blockchain, a transaction is sent to everybody
• for sake of explanation, say there is only one connection between the US and Europe
• this is depicted in the image above
• where transactions within one system are propogated across to the other continent
• this is important for avoiding double spending as everyone knows which coins have been spent and users can verify if a coin has already been used
• but what if this link between the US and Europe is momentarily broken? Now, only people in each region know about the transactions happening
• having a disconnected system is bad as it leads to a fork
• of course, at some point, the connection will get restored and this is where the chain selection rule comes into play
• the longest chain selection rule makes the longer chain will be picked
• meaning any transaction that was in the shorter chain will disappear and there is no guarantee that they will be entered into the chain

• what does this mean for balance?
• we’ll look at 2 scenarios

• in this first scenario, say you have 1000 to start
• then a fork happens, in the greyed out red chain, you can see that you got 100 and spent 10 from this and keeping 90
• the total balance when you got the change back was 1090
• but at this point the fork is resolved and the other longer chain was selected
• what happens to the balance of people participating in the shorter chain?
• it is possible that they might be included in the new chain but it is possible that neither transaction will be included and then their balance goes back to 1000
• it is also possible that the first transaction is included and the balance is 1100
• note that it is not possible for the second transaction of -10 to go through without the first transaction also being included
• but the only conservative and safe thing to do is that the balance is 1000

• in the second scenario, we start the same way with a balance of 1000 and then there is a fork
• after the fork, you get 100 but now, you spend 200
• this means you spend both
• after the fork is resolved, and now what happens?
• these 2 transactions of +100 and -200 may or may not be included
• if they are included, the balance is 900
• if they are both not included, the balance is 1000
• in this scenario, the assumption is that both are included and the best guess is 900

Watch Edsko’s presentation here:

Self Organisation in Coin Selection
Semi-Formal Development: The Cardano Wallet

If you attended this Cardano meetup, we’d love to hear from you too! Leave your comments below

9 Likes

Great explanation and analysis of UTxO (Unspent Transaction Output)!

1 Like

My favorite lines from Edsko de Vries:

“Not many companies like IOHK. Not many companies who take the mathematics underneath their product so serious. I work in a programing language called Haskell, there are a lot of companies using it and one of the slogans is Haskell is like mathematics people say it but very few actually do it.”

“Not many companies give you that opportunity.”

2 Likes

@Jotunn Edsko was a terrific speaker and you should have seen the people wanting to ask more questions after the talk

1 Like