I’ve been significantly distracted this week but have had some time to work through some of the problems that Catallax needs to overcome to run on top of ethereum. It has mostly been a series of ideas and discoveries of how those ideas aren’t going to work. I’ll outline them here in case anyone has a readymade solution sitting in a private git repo that they’d like to share.
The Random Draw
The first idea was an outgrowth of a side project I’m working on. The concepts of hypercatallaxy are not intuitive. I’ve written and run a number of computer models and it is still hard for me to do the nth order thinking that one needs to do to ‘think in catallaxy.’ As a solution I’m trying to build a board game to help people get acquainted with the concept. This idea sprang from playing Ticket To Ride with a friend’s teenager and seeing them grok the concept of delayed gratification.
The board game operates on a slightly different principle than hypercatallaxy, but I think it gets the point across. It also happens to be more ‘fun.’ In standard hypercatallaxy, for every dollar you pay out you get a pref in the receiving account’s pref pool. When their cash pool decays the decay fee is paid out to the owners of the pref pool in proportion to their ownership in the pool. Digital currency makes this possible because we have lots of decimal places available due to the concept of divisibility. Lots of decimal places don't translate to a board game well where your smallest unit is probably $1.
To get around this I’ve created a pretty cool game concept where each player has their own ‘blockchain bag’ that is basically like a color coded crown royal bag. Every time you pay another player some cash, you put an equal number of poker chips in their bag that match ‘your’ color. Whenever they have to pay a decay fee, instead of doing a bunch of math, they break down their decaying cash into a few small but equal piles of cash. They then draw a poker chip out of their bag for each stack of cash and give it to the player who’s chip is drawn. It follows that if you have paid more to a player than the other players in the game that you will have a higher chance of claiming a stack of cash. This adds the same line of thinking that one would need in a hypercatallax economy.
Last week I talked about how it was going to be too expensive to distribute out the cash from a catch-up process on chain because one catch up may have to update the balance of 10,000 accounts. It occurred to me that I could use this random draw method to solve this problem. If you are catching up 5 days worth of decay, we could do 5 random draws and send the cash to the winners.
It wouldn’t be pure hypercatallaxy, but it would be enough to do a decent POC on the ethereum chain. All we would need was 1. A quick way to figure out who owned the winning number that was drawn and 2. A way to draw a winning number.
Search Trees
To solve our first problem of who owns a number we need to iterate over every transaction that has come into an account until we find out who has pad the nth dollar where n is the winning number.
Here we run into another problem with ethereum calculation costs. Each lookup of a variable costs gas. We could probably get away with this for accounts that have done a small number of transactions, but once we get into big numbers we are going to blow past the gas limit before we find our winning number(sometimes).
This problem is much less expensive than writing updated balances to the blockchain for all accounts, but it is still not realistic.
One possible solution is to use a form of data structure called a binary search tree. There are all kinds of binary search trees, but I could find very few that were actually available in ethereum. I did find this but had trouble getting it to compile. If you have a self-balancing search tree algo sitting around in solidity that you’d like to share, please point me in the right direction.
The idea would be that upon each transaction we would push a node onto the tree that was something like:
struct Node {
mapping (bool => uint) children;
uint parent;
uint maxValue;
uint minValue;
address winner
}
The magic comes in when trying to keep the top node as much in the center of your possible values. I’m not sure if the fact that our new nodes would always have a maxValue higher than all existing nodes would simplify the code or not.
Solving this problem would get the search down to a much more restricted set operations and make the search for the winner much cheaper. We’d pass the winning number into the top of the tree and it would cascade down the tree until it found a node where it was between min and max value. That is the winner.
Unfortunately, this wouldn’t solve our other problem.
Randomness with Ethereum
Randomness with ethereum is apparently really complicated. One of the best solutions seems to be this proposal called the randao: https://github.com/randao/randao
Reading this pretty much makes my head spin. The big problem is that if a miner doesn’t like the result of your random number generator, they can just not file the block and try again.
This just seems to be a problem with deterministic computing. It is deterministic. Randomness that you can’t cheat is really hard.
Transparent Computing
This leads me back to square one and where I was last week looking at TrueBit[https://truebit.io/] and the possibility of doing a bulk of the calculations and data storage off chain. I spent some time this week reading their white paper and I just kept coming back to the question of ‘does it really need to be this complicated?’
I mean, I get that it does and that crypto isn’t simple. If you want things to really be trustless you have to jump through a ton of hoops. But I got to thinking..
What if you didn’t need to be trustless but just needed to be trusted? Part of what is cool about TrueBit is that anyone can run a calc and if there is some dispute you run some pieces of the code on the main chain for validation. This makes a ton of sense in a trustless environment, but what if I just want to establish trust?
If I publish a beginning state, a set of code, and a result and sign this set as an authority, it should be pretty easy for people to trust me. In effect this a subset of what ethereum itself does. These inputs + this code + this call = this result.
I think I can accomplish this by doing a kind of half-TrueBit. I haven’t gotten very deep down the rabbit hole yet but I think I may spend some more time thinking about this last option this week.
What if the on chain stuff was a pointer to a publicly available start state, a publicly available contract, a function call, and a signed final state. In this scenario we could run all of our calcs against a test rpc ethereum virtual machine and just ignore the gas limit. As long as we can’t overwrite the code and or state used in each transaction anyone with a evm could reverify that we hadn’t lied about our current state(which itself is just a pointer to a publicly available state).
Let me know what holes you see in this and if you have any insight into loading states into evms and persisting the results, let me know too.
Donations always accepted at:
BTC: 1AAfkhg1NEQwGmwW36dwDZjSAvNLtKECas
ETH and Tokens: 0x148311c647ec8a584d896c04f6492b5d9cb3a9b0