[EP -2 ] The Magic Behind Blockchain: ⇛ Partial Exploit ⇚
Previously on Episode 1 of “The Magic Behind Blockchain”…
we established a common understanding of the following:
- Blockchain, Distributed Decision Technologies and their importance
- Consensus and the Scalability of Trust problem and why it is a problem worth solving
- The consensus layer is the very heart of every blockchain solution
Today, we will analyse a homegrown blockchain solution to get a quick feel for some important aspects to come in this series. In order for anyone to assess whether any blockchain solution is trustworthy for any investment, they must first ask themselves:
How do the computers in this network agree on the next decision to take?
This question is a crucial one because, the problem of creating agreement amongst a large group of people (in this case computers in a network a.k.a — nodes) is a truly hard and wicked problem! It is not trivial, however, anyone who correctly solves it stands to gain immense value.
VOTING IS NOT THE ONLY WAY
Most agreement problems are solved through voting, however, voting is not the only way to achieve consensus. In fact, any set of steps a group can take to arrive at an agreement despite their varying interests is a form of agreement protocol. Technically, this is called a consensus algorithm. Again a good example:
The world did not vote to elect toilet paper as the most expensive / sort-after item during the COVID pandemic but somehow the majority of people in some countries came to that conclusion.
This is an interesting protocol to think about.
If you are trying to create agreement, one critical ground rule is that, in every large crowd (of people or computers) making a joint decision, there are 3 groups of people:
- Honest — this group will follow whatever protocol set forth religiously to the letter
- Semi-honest — this group will follow most of the protocol honestly. However, they are curious! And if they found a way to cheat others without getting caught, they might just take it.
- Dishonest — this group is here to destroy. They will do anything in their power to ensure that the protocol fails especially if it is to their benefit.
You need to factor this ground rule into your process. And yes Honest, Semi-honest and Dishonest are actual technical cryptographic terms.
MY FIRST CONSENSUS ALGORITHM (Bread & Cake Blockchain)
I came across my first consensus algorithm very early in life. I was about 7 years old. However, I would only realise this was a consensus Algorithm in my first Advanced Cryptography class.
The setting is West Africa, Ghana. My dad used to bring special bread and cake home from work every other day. My two siblings and I always had a major disagreement (sometimes fights) on who should share the cake, and most importantly who should have the largest part.
We just didn’t trust one another. You see.. we knew that whoever shared the cake that day would be sure to punish the sibling that wronged them the most. And whoever shared would, of course, also choose the biggest part. Everyone wanted to have the this power, hence the fights. So one day, my dad called us and gave us a protocol for all future cake / bread sharing.
He said “use these 3 steps”:
- You should all flip a coin / roll a dice to choose one person amongst the three of you (siblings) to share the cake. To set the tone for more formal mathematics, I propose we call this person S meaning “Sharer of cake”. So S divides the cake into 3 parts.
2. Each sibling picks a piece / share. However most importantly: Whoever shares the cake will pick up shared pieces last. So S picks last.
3. The other two siblings can pick up pieces first and second in alphabetical order of their first names. So assuming the siblings are Alice, John and Peter, and John is the “Sharer of Cake”, they pick the cake in the following order.
- Alice first (name comes first alphabetically),
- Peter goes second (again alphabetically) and
- John goes last since he is S(Sharer of cake).
For the sake of our mathematician friends, let’s present this formally and in general terms.
All I’m trying to say, without ambiguity, here is that, there can be only one Sharer and the Sharer must be one of the siblings. Also this doesn’t really work for less than 3 siblings.
So back to my story, in more concrete terms:
n = 3, because there are 3 siblings so the set of picker = {p1, p2, p3} .
If the coin toss chooses sibling p2 as picker, the p2 = S (Sharer of cake)
WHY MY FATHER’S PROTOCOL WORKED
After this date (when my father told us to share cake with this algorithm), all the fights were over! Because we always knew who would share / divide the cake after we tossed the coin. Or at least, we accepted our fate at the coin toss.
The person sharing (S) also always had the incentive to share the cake as equally as possible because if the cake is ever cut unevenly, they are sure to get the smallest part when they pick last.
SECURITY ASSUMPTIONS
An important cryptographic question to ask here is: What are the security assumptions? Because the truth is, ALL cryptography and cryptographic protocols are based on assumptions (specifically the one-way function and random oracle assumptions) that are usually unproven and this is what I love to exploit in cryptanalysis.
In typical blockchain consensus exploits, there are two main attack vectors worth considering: participant selection and value correctness
1. Participant Selection: If there are any participants chosen randomly, how is that done? Proof of Stake, BFT, even Proof of Work and many other consensus protocols rely partially on some “random” way of choosing participants to create consensus. In our Bread and Cake Blockchain it is how we select Sharer of Cake and picker.
2. Value Correctness: If any values are transmitted via network to achieve consensus, how do you guarantee that the values are correct / legitimate? Manipulation of this value may result in manipulation of consensus.
In our Bread and Cake Blockchain, all participants are in close proximity to share the cake so no need for transmitting values (Imagine if I were communicating with each sibling via a walkie-talkie. In later episode we will tackle this attack vector further.
In our Bread and Cake blockchain, we unconsciously made the following security assumptions:
- The dice / coin thrown or tossed to choose the “sharer of cake” is fair dice (or fair coin).
- All parties are at least semi-honest. In other words, they at least follow the protocol to the end. So we don’t have a “sharer of cake” who decides not to share the cake but rather eat it all themselves. The economic incentive here is if one sibling tried to abandon the protocol, the others would gang up on him / her and they would be outnumbered.
- There are no collisions in first names, otherwise, two people have to pick at the same time.
- There is no collusion between participants.
BREAKING THE BREAD & CAKE BLOCKCHAIN CONSENSUS PROTOCOL
As noted earlier, we forgot one key assumption! And that is collusion. The ability of 2 out of 3 siblings to form a gang against the other. My father clearly underestimated our love for cake! Cake could make unlikely friends out of arch enemies. The Bitcoin analogy for collusion is mining pools.
You see.. This protocol does not completely resist collusion. So there is only partial collusion resistance. Now let’s exploit this assumption.
If my other two siblings decide to collude against me, the only way they can cheat me is if:
- The fair dice chooses one of them as the “Sharer of cake”
- The first person to pick is also a member of the gang.
So they break the algorithm like this:
- Sibling A gets luckily elected as “Sharer of cake”.
- He / She cuts the cake into 3 portions: one extremely big part and 2 very small parts.
3. Sibling B who is A’s accomplice is lucky to be first to pick (so he is p1) because his name comes first alphabetically.
4. Sibling B picks the largest piece of the cake.
5. I, as the other sibling, would then have to pick only between two small pieces
6. The “Sharer of cake” also picks a small piece
7. Finally, Sibling B shares his large chunk of cake with his accomplice (sibling A).
And voila! They hacked the protocol and managed to cheat me. Note that, they only needed Sharer S and p1 (the first picker).
LESSONS LEARNT
It is very important to model these security assumptions and where they fail mathematically; and provide the necessary mathematical and cryptographic proofs to prevent the consensus protocol from being exploited when it scales up. This also provides confidence to investors who want to utilise the system.
Please note that, in real life blockchains, there are several viable targets to exploit apart from the consensus mechanism.
Each of the blockchain layers presented in Episode 1 has its own traps such as:
- insecure Peer-to-peer networking at the P2P layer,
- insecure smart contract at the Content layer or even
- bad cryptography at the Primitives layer.
I am intentionally targeting the consensus layer here because that is the heart of the blockchain — so the most viable target. We look at more targets as we progress in later episodes.
If we had done this properly for the protocol above, we would know that this protocol is only secure if:
- Dice is truly random → so in practice, use the right entropy / randomness generator here
- There is no collusion with someone whose name comes first alphabetically. Because even if we run this protocol for 1000 people, it only takes one Sharer who colludes with the person named “Aaron” (I assume this would be the first name alphabetically) to cheat everyone else.
- There are no collisions in first names; otherwise two people have to pick at the same time. And now you have more consensus problems to solve. How do the 3 people named John agree on who to pick next? This would be a recurring consensus problem.
Of course we would have to present this in formal mathematics, which is trivial, and then realise that the weakest point to improve here is: how to choose the first person who picks the cake share after the S shares the cake.
Perhaps choosing alphabetically is not random enough!
Maybe we need another dice (apart from the one that chooses the sharer). But not just for the first person to pick but also the subsequent pickers until the last picker (Sharer of cake) picks. Otherwise we just shift the problem forward. If you have 1000 people and use a dice to choose randomly only for the first 500, the 501th person chosen alphabetically could cheat! This is like kicking the can down the road. Eventually you would have to solve this problem.
WHAT COULD GO WRONG? CAN WE MAKE IT MORE EFFICIENT?
So with n people participating in the protocol, you probably need 1 coin / dice to choose Sharer and n -1 dice throws to choose subsequent pickers.
Here comes the most important step:
The entire protocol can be mathematically reduced into an entropy problem! This means the entire security of this specific consensus algorithm fully depends on how secure your randomness is, for choosing all participants (whether sharers or pickers)
And then you can make the security assumption that once you choose a universally good CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) for “Sharer of cake” selection and the next n-1 picker selections, the system would have the same security as breaking the chosen CSPRNG. Hence Proven!
In terms of time-complexity (efficiency) of algorithm,
- if each random selection is trivial, then the runtime is O(n).
- However, if it takes O(n) for one selection, then the runtime becomes O(n²).
- You can improve upon this by just randomly pre-sorting the participants before protocol begins. However, as we already established our cryptographic reduction, this sorting (picking order entropy) is the heart of the entire protocol so you would have to treat this as secret material. Your O(logn) sorting algorithms will really come in handy here!
In terms of space complexity, You would need at least n bits of entropy to sort n people. If you decide to use fresh entropy after every selection then you would need n-1 entropy bits afterwards. That brings you to O(nⁿ) in terms of space in the ideal case.
As you can see, you don’t even need to start coding if you properly model and understand the problem from a mathematical and cryptographic point of view. You can already foresee the problems in implementation before the first line of code touches Github!
CONCLUSION
I would like to conclude objectively with some pros and cons of the cake-and-bread blockchain consensus algorithm:
If you understood my little bread and cake consensus algorithm till this point, you already have a great foundation to fundamentally understand and analyse most blockchain solutions. Most consensus protocols aren’t even this complicated.
In fact, in the next episode, we will focus on a classical consensus problem known as the Byzantine Generals’ problem, establish a classical foundation and then dissect a classical consensus protocol solution called Byzantine Fault Tolerance (BFT) the same way.
What to remember in this episode:
- Mathematical and cryptographic reduction is the most crucial tool in the cryptanalysis toolbox. First understand the algorithm, enumerate the assumptions, reduce the assumptions to simple equations and then break the equation!
- Cryptography alone is not enough. It can only take you so far. Hashing, signatures, encryption, etc will not last forever. What lasts a lifetime is people’s need to act in their own self-interest. Therefore introducing economic incentives is one of the most important ingredients in designing blockchain. There is a whole discipline coined after this called crypto-economics.
Alright this entire article somehow made me hungry for cake. Catch you later!
About Naoris Protocol
Naoris Protocol is a Decentralized CyberSecurity Mesh for the hyper-connected world. Our disruptive design pattern makes networks safer as they grow, not weaker, by turning each connected device into a trusted validator node. A robust Blockchain protocol that every company can use to protect against the escalating levels of cyber threat.
Devices are rewarded for trusted behavior fostering a secure environment. Participants earn $NAORIS staking rewards for securing the network.
The more users, businesses, and governance structures that use the Decentralized Cyberecure Mesh, creating networks of networks, the stronger and more secure it becomes.
Want to learn more about it?
Visit our Website or check out our Whitepaper
