We trust some people may be exeptical about this: "A potentially infinite collaborative canvas? There is no way that scales! It would be cost prohibitive! How can you handle concurrent users drawing!? Its insane!". The more you think about it, the less sense it makes, but bear with us! We had those concerns ourselves, but we really liked this idea, and wanted to do it, there is nothing like it at the time! We identified many obstacles and technical limitations, but they did not turn us down. On the contrary, and we got obsessed with making it work, and we got creative. REALLY creative.
There is no need to trust our word blindly on this (that would go agains all Web3 stands for!). We will walk you though the thought process we used and every line of code we wrote. It will be long, and it may get a little technical at times, but it will be worth it. Once you have seen all the dark magic under the hood, you will understand that this not only is possible: its unique.
Lets first state what we aimed for:
- Each user, in time, may ask for a CANVAS and DRAW in it.
- All canvases together constitute the BOARD.
- We set a preexisting "seed" so that all user drawings have at least a NEIGHBOR.
- When a user is drawing, he will be able to see neighboring canvases that were drawn before.
- We need canvases to not change once they are drawn, so that they can be used as neighbors for future canvases.
- We need not to leave blank drawings in the canvas, so that the board is coherent.
- We need to maximize concurrent users.
- The board must be stored on chain.
- It needs to be cheap!
These are the two fundamental operations: reserve and draw. Reserving asks the smart contract for a canvas, a place in the board. Drawing uploads your art to the canvasyou reserved. We need this to be a 2 step process because when you start creating your art, you need to see the adyacencies in order to complete the canvas in a way that is coherent for the board. In order, it works like this:
- you RESERVE a place on the board
- you get the adyacent drawings to your canvas. This algorithm is complex, but it is readonly, so it is cost free ;)
- you create art on your assigned canvas on the browser
- you finish your drawing and upload it to the chain. Technically speaking, you DRAW
Lets start where we started. What is the most straight forward way to expand a board that may grow indefinitely? Something like this may come to mind:
What you are seeing is a sample board, each numbered square represents a canvas. You should be able to intuitively grasp how this would grow to infinity and beyond.
Great, right!? Well... not quite. This would work great if you only had one user adding one drawing at a time, but if you add another user, everything breaks down!
Lets say you are drawing on "1" and someone wants to draw on "2". With this layout, you would have to wait for 1 to be drawn before you can draw 2, since 1 is a previously drawn neighbor of 2. Same happens from 2 to 3, from 3 to 4... Each increment we are locked to one concurrent user, because you cant start drawing the next slot until you have drawn the last. Lets illustrate how inneficient this is with two examples, blue are the canvases we already drawn, green are the ones we can reserve at the moment.
This is sad, no matter the size of the canvas, we can just draw 1 at a time.
We tried multiple seeds but its complexity made it really expensive. We tried optimistic allocation but that meant leaving empty canvases or filling them up much later, both unacceptable. We thought about racing for drawing canvases, but that would encourage speed over quality and scripting over taking the time to create something beautiful. We've tried a number of approaches, but most of them broke one of our commandments. Our main problem was simple: if possible, we wanted the algorythm to be incremental in order to make for cost efficient simple contracts, but incremental seemed like it would inevitably lead to the issues discussed before. If you increment one by one, you MUST need 6 in order to get 7, right? Well, we soon discovered that was not exactly the case.
The coiling looking incremental canvas seemed nice and intuitive. Lets see if we can modify it slightly.
Well, it is kind of coily. It is incremental too, no coordinates or adhoc relationship needed to store the canvases, but what does this solve exactly? Lets see how concurrency works here. Remember that blue are already drawn canvases and green are the ones you can reserve.
Wow! That is a lot more available canvases! We start with 4, which may not seem like much, but it quickly grows to 8. The bigger the board, the higher the amount of users we can handle drawing at the same time, which will make the canvas bigger, which will allow for more users...
This works on a rings system: Each drawing slot unlocks a whole ring, asuming all previus drawings were drawn, and each ring is 4 drawings bigger than the last.
This approach seems great, but the board is kinda diamond shaped. Not really an issue, but we have to be pragmatic here: phones, notebooks, screens of all sizes, or even if you wanted to paint the board on a mural or have it printed on a portrait hanging on the wall, they are all... rectangles, for lack of a better word.
Then we thought: the board is diamond shaped but the canvases are square shaped. What would happen if we made the canvases diamond shaped?
Perfection.
Being the astute reader I am sure you are, you must have noticed that our aproach left an issue unresolved. Since reserving and drawing are two separate steps, what happens if you reserve but you do not draw? Well, that is expected, and even necesary up to some point: after all, concurreny counts on it. Lets imagine the following scenario, where we add orange to our color scheme, orange meaning "reserved". Here we can see Alistair reserved 2.
Alistair has not yet finished drawing, but Babbage came along and decided to reserve too. Since 2 is reserved already, we give Babbage 3.
Babbage is a really good at drawing! He even finishes before Alistair!
This is fine, there is no need to rush Alistair. There are still some canvas for users to reserve. There is one issue tho. You may have noticed that we did not add any assignable (green) canvas. That is because Alistair is holding what we call the "first assignable". 5 is at this moment the "last assignable", and it is stuck at 5 until the first assignable canvas is drawn. The canvas that we can reserve are those between the first assignable and the last assignable that we haven't drawn or reserved yet.
The problem is Alistair went to buy some cigarretes. He never came back...
What should we do? Advancing the last assignable would cause either blank canvases (2) which goes against our rules. Even if after advancing the last assignable Alistair came back and drew on 2, there is a chance someone would have drawn in its adyacencies, going against our other rule.
But if we do not advance the last assignable and Alistair never came back, we would be stuck, so... is that the end?
Of course not! What we need is to set a time limit to draw. Something sensible that lets you explore your creativity, but at the time pushes you forward to not leave it blank and hinder this gorgeous colaborative effort. If the time limit is exceeded, we give your canvas to the next artist that reserves one. It will even be given before the rest of the assignable canvases, we need to move forward with the first assignable after all! So, assuming Alistair for some reason did not draw on its given time frame, 2 becomes reservable again.
Carolina comes along and wants to contribute. She reserves a canvas:
She is exited to be a part of this! She takes her time, but he confirms her drawing within the time window.
Notice that now that 2 is drawn, not only do we have a new first assignable (4), the last assignable (8) is higher too, which is what we want. With just 1 drawing, we unlocked 3 available canvases.