Is the system actually secure?
rkfg opened this issue · 7 comments
I'd like to discuss the incentives and flaws of the blockchain in this system. I have a deep understanding of Bitcoin, its incentives and technical details so we can compare these projects and see how ALFIS can be attacked.
First of all, it's important to understand who the attacker is. It's probably not a script kiddie or some random hacker, but rather the State with a lot of resources at hand. Since ALFIS tries to compete with the traditional DNS system which is ultimately controlled by the USA (IANA and root servers), our attacker would probably be the US government. If the system isn't designed to withstand state-level attacks, it should be explicitly mentioned so that people have reasonable expectations regarding the system reliability and stability. With that in mind, let's see how system consensus works.
I'll be referring to the about_ru.md file. A huge issue that I instantly see is the PoS requirement. Any PoS system is subjective, it's essentially an opinion of people regarding the ledger state. PoW is objective, either you did the work or you didn't, you can measure that work, you can compare two forks in terms of energy (work) spent on each and pick the one with the most work. That's how Bitcoin establishes consensus. PoS relies on circular reasoning: the validators are determined by the ledger state (whoever has the most tokens/blocks/any other internal ledger data, is allowed to create a block), but the ledger state itself is determined by the validators, and it's done with no external cost, essentially for free. So this raises a question:
- what happens if the ALFIS validator refuses to sign the block?
Indeed, they have no incentive to do that. There's no token, no monetary benefit. However, if they have the majority among the prior blocks with their signatures, they now control the future ledger state by allowing or disallowing people to add their blocks. I think for a reasonable bounty the attacker can easily buy the keys of those validators (they only need the 7 most popular keys) and capture the entire system. Remember, unlike PoW, you can't "unseat" the attacker by adding more hardware or energy. If the attacker notices that you try to dominate the key share, they can refuse to sign your blocks and mine more blocks themselves in the meantime, and sign them of course.
Well, maybe the developer can manually blacklist the compromised keys. If that's true, then the system is even less decentralized and depends on the developer's personal opinion. The State can coerce him into changing the rules arbitrarily as they see fit. It's the least desirable outcome.
Next goes the time correctness requirement. In a decentralized system time can be very weird. In Bitcoin time can even go backwards between blocks, but the overall rules are pretty lax (read this article, it's quite interesting). In general, block propagation can take arbitrary amount of time (the Internet is not reliable by design) and you can never be sure that nodes don't lie about time. What happens if you mined a block but your clock was slightly off? Say, by 5 minutes? Your PoW would be valid but nodes wouldn't accept it, and your hard work was all in vain. Hopefully, with clock sync and automatic adjustments (if syncing isn't possible) this can be worked around.
Now, the biggest issue is conflict resolution, which is exactly why Bitcoin was created. What happens if your node gets two different but valid histories? Which one should be chosen? In Bitcoin it's trivial, whichever fork has most work (not just the number of blocks!), wins. For this algorithm to work the chain should always move forward no matter what, otherwise the attacker can create a longer chain and overcome the old one, just because it's not growing. The author for some reason thinks that in ALFIS that'd be a severe flaw. However, the opposite is true: if the chain isn't constantly growing, there's no competition between the participants for the scarce block space. Which means the block space isn't scarce and as such can be created in any amount at any time. If there's no constant growth, there's no difficulty adjustment (the central invention of Satoshi Nakamoto that binds computation work with time). And in that case an attacker with a lot of resources can outgrow the current chain secretly and cheaply (since the difficulty is constant). The system isn't future-proof, as the computing power becomes cheaper (inevitably) it becomes easier to pool resources, and eventually new domains would require just a few minutes of PoW calculations. Creating competing forks would become trivial for everyone (it might even become accidental if the block doesn't propagate fast enough or doesn't get enough signatures), but the ultimate authority over the fork validity decision belongs to those 4-of-7 keys. And if they don't like your domain, they will not sign your block and rather pick some other block. Note, that Bitcoin still works great despite growing from CPU mining to GPU, to FPGA, to ASIC, and nobody manually corrected the difficulty. The algorithm scaled flawlessly from the first version, and despite the computation power became million times higher, we don't see millions of blocks created every day.
Let's imagine a situation:
- ALFIS becomes very popular, there are some high-profile domains created that the State doesn't like
- the 7 key owners from the early times collude (or are coerced/threatened/bought by the State) and decide to rewrite the chain
- the current majority of keys doesn't even matter! In PoS systems there's no time because advancing the chain doesn't require resource consumption (see the argument about difficulty adjustment).
- nobody can force you to create the next block at the tip since there's no center; you can mine any block with any parent block.
- the attacker creates thousands of blocks that fork at some early block (say, block number 100) using whatever resources they have, they also have the key owners to sign those blocks and keep their majority intact.
Now whoever connects to the network and downloads the block history is presented with two radically different branches that diverge at the 100th block. Both have valid PoW, both have valid PoS signatures. Which one should the new node choose? It's trivial to run more nodes distributing the alternative chain, cheap Amazon instances would do the trick, so the new nodes are guaranteed to connect to at least one of them. I don't see how ALFIS can resolve this without manual intervention or other centralized decision.
This is another example of PoS not increasing, but decreasing security, because it relies on politics, or personal decisions of individuals, to decide on the history for everyone. It's enough to bribe the early participants who were disenchanted and left the system, to completely rewrite the entire history or wreak havoc. How much would a key cost if you can't do anything with it now as you've lost your majority according to the "current" state of the ledger? Probably not much. What if someone pays you $1000 for such a useless thing? I bet you'd gladly accept. With PoW it's simply not possible because the early work can't cancel the later work. You need to redo the entire accumulated amount of work to cancel the current chain. Basically, outcompete the entire world...
...which brings us to the last topic: finality. In Bitcoin finality is always probabilistic. There's always a very small (but not zero) chance of a competing chain with more work than on "your" chain (that you think is the true one). This is why you need to wait for at least 1-2 more blocks, to ensure there's no other chain after the block you're interested in. Usually, it's the block you got paid in, so that your money doesn't disappear after a fork switch where this tx never happened. Every block requires enormous amount of energy to mine, so the same amount and even more required to orphan it. This amount secures your transaction against the State and other attackers. In ALFIS the chain only grows if someone else decides to create/update a domain. Which means your security yet again depends on someone else's needs, and if no one needs a domain right now you're not protected by PoW. Not that you were in the first place, because PoW without difficulty adjustment is pretty useless. However, I don't see any mention of cumulative PoW amount as a consensus factor, so I suppose finality doesn't even conceptually exist in ALFIS.
So, the nodes who are aware of the "current" tip will reject a competing fork. What about those who were offline for a year? Or the new nodes with zero knowledge of the situation? How do they all reach the same consensus if there are very possible attacks like those I described above? What if the current majority-key-holders decide to sign two competing blocks (that have the same parent block)? Just for fun because why not. Can they stall or diverge the chain for everyone?
In the end, I want to note that systems such as ALFIS can indeed work. As long as they're not popular and don't threaten the status quo, and the issues such as conflicting forks can be resolved on a case-by-case basis by the developers/community. But that explicitly shows they're not decentralized and depend on the developers to function, hence having a central single point of failure (the developer's authority over the consensus). I'm not talking about bugs even, but if your consensus rules require manual intervention, it's not a consensus. It's a dictated decision. People deserve to know the shortcomings of the system and only rely on this if they're ready to see it fail one day like in one of the above scenarios (or in another, more complex scenario), and don't overinvest into it. So far there's only one truly decentralized consensus model that works, which is Bitcoin, because it uses the most energy, greatly aligned incentives and it can not be corrupted by swaying some influential person's opinion.
Useful articles:
- https://blog.bitmex.com/bitcoins-block-timestamp-protection-rules/ Bitcoin block timestamp protection rules
- https://yanmaani.github.io/proof-of-stake-is-a-scam-and-the-people-promoting-it-are-scammers/ Proof of stake is a scam and the people promoting it are scammers
First of all, thanks for such a thorough explanation!
But the blockchain in ALFIS differs from mainstream blockchains greatly. I'll try to explain what challenges were faced and how did I circumvent those.
Main problem of current blockchains with DNS functionality is that their blockchain is very big, and it grows fast. It is not possible to host them on a router, or even on your laptop. But we needed to shift that "point of trust" as near to the user as possible.
So, main points are:
- Very small blockchain
- Not growing when not needed
- Is very simple - no coin, no transactions, only DNS data
How do we circumvent forks? What do we do with forks? How do we reach finality? - We prevent the forks totally.
Blockchain grows in these simple steps:
- Someone mined some domain or remined domain records - new block is propagated through the network of connected nodes.
- From the data in the block all nodes calculate the 7 signing keys, needed to sign that block.
- Some of them sign that block by mining empty blocks on top of that block. Yes, signatures are in separate blocks.
- When some node that is mining signature encounters new signature block it rebases its block on top of that and restarts mining.
- If some nodes mined signatures in the same time - all nodes that encounter those two blocks select one, that is "better" by some formula.
- Eventually, signers produce and distribute 4 needed (empty) signing blocks.
- If some slow node produces "better" block lower than tip, i.e. first or second, when there are 3-4 signatures already - nodes can replace that block and the tip, and remine those signatures. But they can rewind only 4 blocks back. So, the block with DNS data will not be replaced if there are 4 signatures.
There is no way for someone to mine their own fork for say 10 blocks back - nodes will not accept them, and will ban such nodes.
So, any new node will not discover such "faulty" nodes. They connect to initial bootstrap nodes, and get other nodes by peer exchange. Faulty nodes are not exchanged this way.
The main and only vulnerability of ALFIS is that some number of the signers can drop the network or die, and stop signing blocks.
I didn't find the solution to this.
There is no way for someone to mine their own fork for say 10 blocks back - nodes will not accept them, and will ban such nodes.
I think there certainly is a way. You mine such a fork but only return the alternative blocks to the new nodes that ask for them. How would you detect a node that deliberately distributes another fork? Would you request all the blocks since the genesis to make sure it doesn't try to switch newcomers to its own fork? Imagine we have 100 blocks currently. The attacker creates a fork at block 50 and mines 100 blocks from there (so the attacker now has 150 blocks). There's no difficulty adjustment so whoever has enough compute can create a chain of any length, and compute can be rented on Amazon, probably cheaply since CPU costs much, much less than GPU, and even GPUs can be rented by individuals these days. You don't need to sustain this work, just do it once to have a very long chain. In the meanwhile you keep accepting and distributing the main chain blocks such as 101, 102 etc. to evade any bans and don't raise suspicion. No one's gonna ask you for block 50 because it's in the past. Except the new nodes.
So, a new node spins up somewhere by some unsuspecting victim. They connect to the seed nodes, get some random addresses from there to connect and ask for blocks. Unfortunately, our attacker spun up many cheap attacking nodes that distribute their 150 block long chain with alternative history (but only if the early blocks are requested explicitly). These nodes don't need to do any work so they're dirt cheap: only need networking and a little storage. There are thousands of them to make sure the victim connects to a few of them.
Now, the victim starts asking for blocks. They download the block 1, 2, 3 etc. and arrive to block 50 eventually. But they get two different versions of them from different nodes (the attacker's and some other ones). Which one is the real one? They both have valid PoW and signatures (because the keys were bought/stolen/acquired in any other way). Eventually they get two forks, one is 100-something blocks (the main chain) and the other is 150 blocks. What now?
The main and only vulnerability of ALFIS is that some number of the signers can drop the network or die, and stop signing blocks.
Which isn't mentioned anywhere and it's quite a real threat for a small-scale project. You also haven't addressed concerns about those signers being corrupted and starting censoring blocks or creating forks deliberately to break the system.
The attacker creates a fork at block 50 and mines 100 blocks from there
How does he do that without signing all his blocks by legitimate signers? He definitely must get their keys.
I think there certainly is a way.
No, there isn't without getting signers keys. But signers are distributed - some of them are in EU, some in the US, and some in Russia. Can you imagine collaboration of all those governments on this topic? :)
How does he do that without signing all his blocks by legitimate signers? He definitely must get their keys.
Like I said, money talks. The problem in this system is that it's not tracking time. Creating a chain of any length isn't exponentially expensive (the complexity is totally linear). So you can recreate the history from very early at any future point in time. I suppose after a couple of years it might not be hard to find a few people who still have the keys but aren't interested in it, and buy them cheaply. I highlighted the possible scenarios in the OP. The issue is that your security model relies on specific people with subjective opinions, not physical objective energy. And people can be corrupted, bought, intimidated. Then after those keys are obtained, the whole system is captured. Would you bet the safety of the entire chain history (past, present and future) on the human honesty? I sure wouldn't, not a single chance.
Next, what happens if just one validator out of those 4 selected refuses to sign? Maybe he's offline or his storage died. Shit happens after all. Do we need to wait until someone mines a different block with a different signature so that a different set of 4 validators is selected? What stops us from cheaply mining these blocks in such a way that only the 4 validators we control are always selected (the algorithm of selection is known, so brute forcing singatures until you get 4 items out of 7 is beyond trivial)?
Next, should validators also mine a block using PoW or just a signature is enough? If it's the former, I don't know who'd to that without any compensation. Wasting electricity on someone else's transaction and getting nothing in return? Quite weird.
Like I said, money talks.
But they need to bribe many different people, including me. I don't want my system to become vulnerable or tinkered that way.
Then after those keys are obtained, the whole system is captured.
No, current nodes, dozens of them, will not change their blocks that they already have. And any attempt of such an attack will be visible to many users.
Next, what happens if just one validator out of those 4 selected refuses to sign? Maybe he's offline or his storage died.
If four signers are offline, then the system is frozen and waits for them. This is a mitigation of having forks. ALFIS is not designed for network split or something like that.
Do we need to wait until someone mines a different block with a different signature so that a different set of 4 validators is selected?
Theoretically, yes. Some modified node can remine that last block with transaction and change the signers. But we didn't try that.
What stops us from cheaply mining these blocks in such a way that only the 4 validators we control are always selected?
It will not be cheap. It's a lot of PoW.
Next, should validators also mine a block using PoW or just a signature is enough?
They mine blocks, but with lower difficulty. Just 3-10 seconds on decent desktop.
Wasting electricity on someone else's transaction and getting nothing in return? Quite weird.
This is a payout for stable system :)
But they need to bribe many different people, including me. I don't want my system to become vulnerable or tinkered that way.
So your system can't work without you? Doesn't sound decentralized at all. And you don't need many people, just 7 is enough.
No, current nodes, dozens of them, will not change their blocks that they already have. And any attempt of such an attack will be visible to many users.
But new nodes will. What do you do in this case? Tell every new node they're wrong and they should accept a different fork? Again, it's not decentralized and the consensus is based on your personal knowledge. Or what if you're lying and instead trying to push a malicious fork? A new node can't tell from the chain alone.
If four signers are offline, then the system is frozen and waits for them. This is a mitigation of having forks. ALFIS is not designed for network split or something like that.
So the whole chain stops because four unlucky users are offline?.. I guess it's more likely than it might sound. And in the meanwhile no one can create a domain or update it... a perfect scenario for the state, just target 4 users to stop the system. Even worse if you need to update your domain ASAP for unrelated reasons (the server it points to was hacked for example).
It will not be cheap. It's a lot of PoW.
No difficulty adjustment = known and predictable price. Either it's too expensive for regular users or it's too cheap for a motivated resourceful attacker that can run a cluster of CPUs at Amazon for a week (without distributing these blocks of course).
They mine blocks, but with lower difficulty. Just 3-10 seconds on decent desktop.
What's the incentive of doing it at all? If it's so cheap and fast, why mine? Isn't just a signature enough?
This is a payout for stable system :)
Doesn't look stable to me with all these implications.
Okay, another simple scenario. We don't steal or buy keys. We just create a bunch of key pairs, 23 bits of zeroes is a trivial PoW and it only needs to be done once. So the limitation of 1 domain per day isn't really enforceable, if we create 1000 of such keys we can register 1000 domains every day. But that's not the point. The point is, we start mining blocks with these domains (they can be anything really), and we quickly get the majority of public keys in the recent blocks. Even if mining a block requires a few hours of work, we can rent 100 VPS and create hundreds of blocks in one day, they will use different keys as we pretend to be many people. But some keys will be used more often than the others. So, we now control 7-10 keys that were used in the majority of the blocks. All the future blocks will be signed by us (or rejected). Then we stop using the system and walk away. The system is left in an unusable and unrecoverable state, unless you intervene and somehow ban our keys. Which is, yet again, isn't decentralized at all.
I just wrote a simple program in Go to generate and hash ECDSA keys and check if the first 3 bytes are 0 (that's 24 bits of zeroes if my math is correct). On my i9-12900kf it took me 38 seconds to generate a key that satisfies this PoW using all 24 cores (and I didn't even try to optimize it). So I can create about 100 keys in one hour and generate 100 domains every day. Looks like a very low effort for a motivated squatter. The problem here is that this key generation PoW doesn't compound, it's enough to do it once to increase the number of domains to register every day, the only limiting factor that still applies is the fixed PoW to actually mine the block. So why does this key generation PoW exist?
PS: note, that I hashed the key with SHA-256 and not your algorithm which is expected to be slower on purpose. It doesn't change much because mining can be easily parallelized and you only need to mine the keys once. Even if it takes one hour (which is already too much for a casual user), you can mine 10 attacking keys in 10 hours, and anyone with spare cash can create thousands in the same time.
PPS: I implemented blakeout in Go (the test vectors matched so I believe the implementation is correct) and retried key generation, it took 1 hour and 9 minutes (I only managed to load all the cores at 80%, the bottleneck is probably RAM). As I said before, it doesn't prevent squatting at all. And it could be implemented in CUDA to accelerate this a lot. I estimate memory consumption at about 2 Mb for one hash, my GPU has 24 Gb so I can run 10 000 such hashes at the same time ideally, and VRAM itself is much faster. But that's way beyond my current skill and knowledge, and as I stated before I'm not interested in attacking this system, just wanted to see the actual numbers to estimate the attack cost.