How much Security is too much Security? Defending against a 99.999% Attack
Speakers: Tadge Dryja
Date: April 3, 2021
Transcript By: Carla Kirk-Cohen
Category: Conference
Media: https://www.youtube.com/watch?v=rSsPViajzQQ
Introduction
Hi everyone, it’s too bad that we can’t be in person but I think by next year we’ll be able to do this in person. It’s been a long year without conferences. And I guess for maybe many people watching the MIT Bitcoin Expo last March, was the last time I saw a bunch of people in person before this whole thing. Thanks to Neha, that was a really good start off for the day. I’m going to talk in some ways about the opposite side of things, saying, well, do we have too much security? And talking about defending against a 99.9% attack.
So what is too much security? Bitcoin is pretty secure. Sure there are all these problems, but generally there haven’t been big reorg attacks. We haven’t seen that kind of thing. If you mined a bunch of Bitcoin in 2010, it’s still there. We haven’t seen these huge kinds of big breaks, which is great. It’s still working. If it stopped working, we probably wouldn’t be talking about it still. And more security is better, right? We need to keep strengthening this? To some extent, but maybe it’s too secure. What does that mean? What does too secure mean?
Too Much Security?
I have some examples of too much security. Some of these are technical, some not so much. For example, 8000 bit RSA keys, you see these sometimes. People say, send me a RSA key so that you can log into this server and it’s a giant 2 page RSA key. It works, it’s slower, but it’s overkill. It doesn’t really meaningfully do anything meaningfully stronger than a 2000 or 4000 bit RSA key. Or maybe it does, but we can’t think of a reason why it would. It seems like any computer that can break a 2000 bit RSA key before the sun burns out could probably break a 8000 bit key before the sun burns out. As far as we can tell, we don’t know of anything, and can’t think of a reason for this to be more secure.
Similarly, 24 word BIP39 seed phrases. Some of you may use these to store your Bitcoin. It’s basically a bunch of words and you write down the words, you hash that all, to turn it into a seed and then you derive your private keys from that. And this is a cool system, you can do it with 12 words and that’s secure. Or you can double that and use 24 words which is more secure in a sense, I guess, but I think it’s less secure because now it’s longer and it’s easier to screw something up or forget parts. And as far as we know it doesn’t give any meaningful security gain over the 12 words. The 12 words gives you 128 bits of entropy, and the 24 gives you twice as much, 256 bits. But what computer can do 2^128 operations but not 2^256. We don’t know about anything that can do that. It doesn’t seem that there’s any theory that can do that. So it sort of seems like, why are you doing that? Another funny example is TSA. Not that I’ve been through an airport in the last year, but if you remember them, you remember thinking is this even secure? It seems like you can get stuff through here. But it’s a huge waste of time and everybody is taking off their shoes.
So there are costs and there are problems with this too much security thing. And sometimes it can paradoxically reduce security. I would say something like a 24 word seed phrase can reduce security, I would use the 12 word one. It’s smaller, there’s just as much cryptographic security and less likelihood that you’re going to lose it.
A Security Specification for Bitcoin
So we want a defined specification of the security level we are targeting. In Bitcoin there is no specification. There is a paper and there is a codebase, which keeps changing, and even the codebase, there are a bunch of different clients. Who knows? But we can look at it and generally it has 128 bit security. That seems to be the design. The meaning of that is that it resists an attacker that can perform up to 2^128 operations. And operations is a little vague, because that’s hashes or elliptic curve operations, and those things are different. Hashes are a lot faster, generally, than elliptic curve operations. There’s a lot of subtleties here, but generally we can say 2^128 operations are required to break this.
Some things have more security than Bitcoin. A big one I keep thinking about are these 20 byte pay to pubkey hashes or pay to witness pubkey hashes. I’m sure people are familiar, if you have used Bitcoin you have used one of these types of addresses. The all lower case bc1 is the new bech32 segwit address, and the older style starts with a 1 and is mixed case, is base58 check addresses. These use 20 byte hashes, so 160 bits of output. And that’s kind of overkill. If you’re targeting 128 bits of security, you’ve not got this 160 bit hash and you don’t really need it. That extra 4 bytes doesn’t really do anything as far as we know. And so you could shorten these things.
This is the length of a Bitcoin address, and you could shorten it to this long and still have the same security properties with no meaningful security loss. Yes it’s easier now to perform a second preimage attack on the key hash, but the second preimage attack on the key hash is already much harder than just figuring out a elliptic curve private key from an elliptic curve public key, so you’re always going to go for the easier attack. So with this shorter address, the second preimage and the private key attacks are both as easy as each other. And you could have shorter addresses. Not a huge difference, but you could. So this is something of an overshoot. But do we really need to switch to 16 byte pubkey hashes? Probably not. This is not a huge gain, it’s already widespread, and we’re switching to Taproot which is even longer, soon. So it’s not a big deal but it’s sort of like, huh, yeah you probably could shave off these 4 bytes with no real problem.
Improving Inefficiencies
And for those kinds of things, are there inefficiencies here that we can use to say, hey, let’s tweak this, this is overshoot, we’re going too far here. And we can get better efficiency and performance in other parts of the system without meaningfully getting rid of security. It’s sort of too much here. On the other hand, there are some things in Bitcoin that have less than 128 bit security. For example pay to script hash. It’s 80 bit security, and it’s the same length as the pay to pubkey hash, they’re 160 bits long. However, the tricky part is that it’s a different threat model. In pay to pubkey hash, you’re just making your own key and somebody sent money to it. In pay to script hash, there are potentially many cases where it’s multisig, maybe most of the cases where it’s multisig. Where there’s multiple keys involved. And that’s interactive. You may be making an multisig with people you don’t trust. And if that’s the case, they may be able to perform collision attacks. And say hey what’s your key, here’s my key but actually they have this other separate key and they can perform a collision attack and take the whole thing and do an attack and do it in 80 bits.
This is a fairly limited case. It’s limited to cases where you’re creating multisig addresses where people are trying to attack you. Maybe you shouldn’t, but the Lightning Network rests on the idea of opening multisig channels with people who might try to rip you off, and you have various defenses against it. So this is fixed with pay to witness script hash, where we’re back up to 128 security. And what I want to say is yes, this is sort of theoretical, but 2^80 operations have happened. Bitcoin has done 2^90, or so, hash operations in all the proof of work ever.
The other thing that really complicates this is that in Bitcoin there’s all these traditional cryptographic security guarantees where we’re like okay, here’s this elliptic curve and here’s these hashes and we know about preimage attacks and collision attacks and all these sort of things, but then there’s also these economic incentives. It doesn’t fit in the standard way, because clearly you don’t have to do 2^128 hashes to rewrite the Bitcoin blockchain, the whole thing is something like 2^90. So it’s way easier to just reorg from genesis, or more than 51% attack. We clearly are not just using 128 bit security, we also have this economic incentive assumption. Initially described as: “The attacker ought to find it more profitable to play by the rules, such rules that favor him with more new coins that everyone else combined, than to undermine the systems and the validity of his own wealth” (Nakamoto, 2008). That was Satoshi back in the day. And that is one of the huge aspects of Bitcoin that makes it possible. It’s not possible to get this kind of consensus with the traditional cryptographic standard guarantees.
Assuming that there isn’t a 51% attack, which could happen, but hasn’t so far. Could we leverage these and combine the 51% attack assumption for better performance by reducing security in other places. Now this seems dangerous, but one of the reasons you don’t want to try this everywhere is that 51% of hash rate changes. What may have been secure against the 51% attack a few years ago would not be secure today, because the Bitcoin mining rate has increased a trillion times, or something like that, compared to 10 years ago. Also 51% attacks don’t really kill Bitcoin. They’re bad, we definitely want to avoid them, but it’s not like oh there’s a 51% attack, it’s all over, let’s all switch to proof of stake or something. It halts the system temporarily. You don’t want to put your coins at more risk by saying okay I’m leveraging this 51%.
But what about 99.99%? Is this secure against really powerful attackers, not 2^128, but so powerful that they could easily destroy Bitcoin. So something like this: an attacker would either need to perform 2^128 operations, or perform operations close to mining a million blocks at the current difficulty. Yeah, Bitcoin only has 600000 blocks and most of those are much easier than the current difficulty. So if you have an attacker who can re-org to genesis in the span of a few days, it might be overkill to defend against that. Current difficulty is the important part here, you can’t target previous difficulty. Saying you’re going to make an address shorter based on the current difficulty isn’t good because your UTXO might stay there for a long time.
Utreexo
So there is an application of this which is something I have been working on for a while. If you have a secure accumulator for Bitcoin, rather than just a merkle tree for transactions in a block. Right now in Bitcoin you have a merkle tree for all the transactions in a block in a merkle tree, you take that merkle root and you put that into the block header and you hash it. We can also use this same technology to keep track of every coin in the system instead of in a regular database, we also put this into a merkle tree accumulator. This is something that’s working now, it’s pretty cool. This is a good application for this sort of reduction of security. Merkle trees rely on collision resistance hash functions. So in general you say okay you add these four aspects, 0,1,2,3 into this set and you hash them together so that you only have this one hash. But then people can prove that 0,1,2,3 were in the original set.
So if you want to attack it, you want to insert something then prove something that you didn’t insert. You need to find two and two prime, where two is not equal to two prime, these two different elements you want to insert where the hashes are the same. You insert one of them then you prove the other one, and the proof for them is the same. And you have broken the system. You’ve inserted two but then you can prove two prime which are different. This is a collision attack, finding two different things that hash to the same thing. This is easier than a hash preimage attack. If you have a 256 bit hash function, it only takes 2^128 to perform this type of attack. In contrast to a preimage attack where it takes the full 2^256.
So we can sort of mix these, the mining proof of work and prevention of the collision attacks. So you can say you’re going to put the block hash confirming a transaction into the UTXO tree. So now you have this commitment to the proof of work. It also commits to its position in the tree so that the attacker can’t collide with an arbitrary element. So for example, the hashes are now the number two (the value), the block hash that confirms it and the UTXO. So this makes collision attacks much harder, because instead of performing a single hash to try and find the collision, you need to mine a block for every attempt. And you can’t reuse this work, every time you try one it changes the block itself. You have two merkle trees, one that has the block hash and one that has the UTXO set. Now you’ve changed the amount of work you have to do. It’s still a collision attack, it’s still 2^128 operations, but the operation has changed from a hash function to mining an entire block, which currently is something like 2^70 hashes. So that is a huge increase. Even though in some sense it’s the same equation.
So if it’s 32 byte hashes, you’d need to mine 2^128 blocks to collide, or to do a preimage attack you’d need to do 2^256 hashes. If you reduced your hash to 16 bytes, you’d need to mine 2^64 blocks to collide, or 2^128 hashes for a preimage attack. And 2^64 blocks is a lot of blocks, 18 quintillion blocks. So it does seem like yeah, it’s a reduction in security, but really are you meaningfully defending against an attacker that can mine 18 quintillion blocks?
So that’s the general idea here. Do we need to reduce hash sizes for these things? No. Is too much security a waste? It can be. It can be very efficient to reduce the size of these things by half. To reduce downloads, and reduce disk storage by half, and speed things up. That’s a meaningful gain. Maybe addresses are a little longer than they need to be, but they’re not twice as long as they need to be. This is an interesting idea, so it’s something I want to put out there. It’s something we should think about. Maybe there are other places that people are working on where there’s proof of work happening. The Bitcoin blockchain keeps going on, doing enormous amounts of work and maybe we’re wasting some of that work. Maybe we can use it to increase efficiency. If you’re been looking at the news in the last 6 months since Bitcoin’s been going up, a lot of people think Bitcoin is really wasteful and it’s pointless. I don’t think they’re right about it. But are we using this proof of work? It’s happening. Are we taking full advantage of this? Can we leverage it for more efficiency and more power in this system?
And then I have this meme about hashes.
Conclusion
Thanks! I’ve put this out as an idea. I’m not like, hey let’s decrease the security of all these things, but I do think it’s an interesting topic. Are there areas here where we’re leaving performance on the table? Or are we paradoxically reducing security by going too far? Questions, comments, disagreements?
I want to reiterate something that Neha said at the end of the last presentation. I work at the DCI, if you’re interested in this kind of stuff get in touch. Get in contact we’re pretty cool. Everything is remote now, so wherever you are in the world it doesn’t make much of a difference. Are there any questions?
Audience Questions
Moderator: One of our questions is, would you suggest saving the state of the blockchain in some way to reduce resource consumption?
Tadge: I didn’t go into this in enough detail here but the idea of the utreexo project is this accumulator I’m working on with a bunch of open source contributors. It’s sort of like pruning the whole UTXO set. In Bitcoin you can store the whole blockchain which is 256 gigs, or you can prune it and say look once I have the block I don’t really need to keep it around. And I can store the UTXO set which is about 4 gigs, and is the current state of who owns what. And this basically prunes that as well. Don’t store the UTXO set, store a little merkle root of it. It’s not quite a merkle root, but it’s very small, it’s less than a kilobyte. And then transactions can prove that the UTXO they’re spending exists with these merkle proofs. That’s one example of where we can potentially leverage smaller proofs. It is a sort of different way of pruning the UTXO set. You don’t need the blockchain, you don’t need the UTXO set, you can run a full node in a very small amount of space.
Moderator: We have time for about two more questions. The next question is: Converse to what you were saying about reducing the hash size, isn’t increasing the hash size supposed to future proof the system instead? Tadge: Well, maybe. But you can’t. You could say, let’s put something new in Bitcoin where we have 512 bit pubkey hashes. Or we use an elliptic curve that is 400 or 500 bits long, so we double the security. Well okay, but we still have almost everyone using the previous parts of the system. If somebody makes a computer that can derive a private key from a public key, which takes 2^128 elliptic curve ops. Maybe you’re safe, but everyone else isn’t, so the whole system isn’t. If you’re going to make your Bitcoins twice as secure, it doesn’t matter, if everybody else’s coins have been stolen it doesn’t matter because the system has collapsed. It’s no use to say “I still have mine”, because everybody just leaves the system. So there may be ways to upgrade, but you kind of need everyone to upgrade, or almost everyone. If there’s 5 million of the 21 million coins are stealable, the system is in trouble.
Moderator: What about quantum computers, is Bitcoin ready for that? Tadge: Right now no, definitely not. If you have a quantum computer, you can grab all of Satoshi’s coins, there’s so many unhashed public keys that are known to have enormous amounts of coins, so you just pick one and perform a quantum operation. You perform that attack and you take all the coins. Right now it’s not, it could be. A system like Bitcoin would be pretty amenable to being quantum safe. There are a bunch of quantum safe signature schemes that we could use, but they’re worse in that they’re bigger and slower and stuff. But you could do it. The question of upgrading is very difficult. You sort of have to change everybody’s keys. Even if it’s just a quarter of the coins that are stealable, is this system going to survive that? There’s also the question of quantum computers and proof of work, how do those interact? So right now no, it’s something people are thinking about but it’s hard to upgrade everyone. Maybe if a quantum computer comes out or it’s imminent, then it’s something that’s scary enough that nearly everyone will move, and we make some kind of soft fork which says all of these old coins are frozen forever. But it would be very disruptive. We’re not really planning for that right now.