Fungibility and Privacy
Speakers: Adam Back
Date: February 9, 2014
Transcript By: Bryan Bishop
Tags: Privacy problems, Privacy enhancements
Media: https://www.youtube.com/watch?v=3dAdI3Gzodo
First of all I was going to explain what we mean by fungibility before bitcoin and ecash. It’s an old legal concept in fact, about paper currency. It’s the idea that a one ten dollar note is the same as any other ten dollar note. If you receive a note that was involved in a theft, 10 transactions ago, and the police investigate the theft, they have no right to remove the ten dollar note from your pocket. It’s not your fault that it was involved in a previous crime. And so bank notes actually have serial numbers, so it would be possible for a stolen note to be traced back to you.
This first arose, there was a 17th century court case where a wealthy merchant sent a couple of high-value bank notes to a colleague in the post and they never arrived. Before he sent them, he was quite paranoid that they would get stolen. He wrote down the serial numbers and made a mark on them. Sure enough they didn’t arrive, so he put in a complaint with the bank, and evenutally the notes turned up at the bank. He tried to get the bank to return the notes to his ownership. The courts sided with the bank. Their reason was that if notes could be returned to their original owner after a theft, it would damage confidence in currency and it would be bad for business, the currency would become unusable because every time you received the paper note you would have to look in the newspaper whether it was reported stolen, or you would have the risk of it being taken, or you would have to rush to the bank to deposit it so that it was the bank’s problem.
That became a legal concept and it applies to most countries now. In electronic cash systems, before bitcoin, there were a number of cryptographic electronic cash system.s They introduced the concept of cryptographically-enforced fungibility. You make it so that you can’t tell one note from another. Because there’s, you don’t have to rely on law. It’s mathematically impossible to tell which note came from the previous transaction because they are randomized or anonymized in some way. This is another example of a bitcoin-adopted mantra of trust math over law. Because you can’t tell one coin or note from another, there’s no need for a legal mandate to treat all of the mequal, because they are all treated that way by default because you can’t tell the difference between them.
The first person to think of this concept to cryptographically enforce this was a guy named David Chaum. He invented blind signatures in 1982. If you’re familiar with RSA signatures, this is how it looks. You can kind of switch off if you’re not interested in math. Basically, if m is the coin, then there’s a trick that you can multiply it by b which is a random value, the blinding factor, if you raise it to the power of e before multiplying it, if the server signs it, which is the normal way, the d and the e cancel. So you get left b the blinding factor. So to the server that looks like a random number because it never learns b. So the user can divide it by b, and the user has ended up with a signature on a message that the server never saw. And it can be verified in the normal RSA way, too. It’s quite an interesting, mathematically it’s relatively simple, it’s an interesting property because you can have a server sign something that it doesn’t see. You might write a letter, and there’s an envelope in the letter, someone can sign it but they can’t see what they are signing.
There are some technical problems with that. If the bank signs anything, there’s an attack on signatures called an existential forgery, you make up a random number and raise it to the power of e, and you can claim that it’s a signature. It passes a signature test on the random number. To prevent that, the message that is signed has to have some structure so that you have to find a random message with that structure. The structure inside the coin is only seen by the user at the beginning. They get it signed and the value inside the structure is the serial number, it’s analogous to a bank note serial number. The bank just signs it and says it’s a valid note, without seeing the serial number. When you go to spend it, you give it to someone else, and they deposit it on the bank. Chaum ecash is not p2p. You take money from the bank, you hold it in your wallet, and once you give it to someone else they have to deposit immediately, because otherwise you could spend it again. The arbiter of what a valid coin is the bank, because they have a double-spend prevention database.
The whole security of the system relies on the double-spend database at the bank. We’ll see how this makes for trouble. Unlike bitcoin it’s vulnerable to the server being shut down or subjected to political pressure. This form of ecash is actually quite anonymous.
Chaum’s ecash has some other properties. It’s unlinkable. When the user takes the coin from the bank and turns around and it igves it to the merchant who gives it to the bank, even the merchant and the bank colluding can’t determine which user deposited the coin. It’s much more anonymous than bitcoin, it has zerocoin or zerocash properties, and it’s very efficient and compact, but it has the central server attacks. It’s optionally payee-anonymous as well. The merchant can optionally be anonymous, although it didn’t tend to get deployed that way, to avoid criticism from black-mail scenarios or something. As it stands, the user and the bank can collude to identify the merchant, so someone could blackmail you to prove that.
It’s online, so the payee has to deposit immediately. You would typically link it to a bank account, a conventional bank account, you would withdraw electronic cash coins that you could use, but it wouldn’t have to be linked to a bank account. At a protocol level you could deposit a coin and get back a fresh coin without using a bank account.
One limitation is that it only supports a single denomination. If your base denomination is 1 cent, and you pay someone 50 dollars, it’s 5000 coins and the size of the transaction becomes big. You could create multiple denominations of coins, but that reduces anonymity because the change tends to leak things about what’s going on.
It does have perfect cryptographic privacy and perfect fungibility as I mentioned. There’s no question of a coin being tainted by a previous transaction because nobody could tell one coin from another basically. It’s completely randomized after each deposit. But it’s vulnerable to a server shutdown.
Around 1995, this company is now long bankrupt at this point. David Chaum put some of his own money and investor money to start an electronic cash company. There was a lot of excitement around this technology. There was not as much as bitcoin excitement, but people were still excited. They appeared to be on the verge of doing deals with banks and so on. As part of this, they put together a demonstration ecash server with no related bank accounts, it was just a demo server. They promised that they would never issue more than $1 million dollars of betabuck coins. You could get coins by just asking for them, like if you went to a website or sent them an email they would give you some coins to play with.
People saw this and started to do something similar to what happened with bitcoin; there’s no exchange and nobody sitting there as a market maker, and since it seemed to have scarcity by the company’s promise, people started selling things for them. Just t-shirts and things in the post, low-value things, choosing their own exchange rate I guess some exchange rate would arise. I think people thought that if they kept this up amongst their community, their coins might arrive at a value, and they could be exchanged. But the company went bankrupt.
The double spend database being on the server… people still had the coins in their own possession, but nobody could tell from their own coins whether it was valid or not because you can’t, you have to deposit to the bank to tell that it is spent and the bank wasn’t there anymore. So that demonstrated to people the vulnerability, first-hand, of central servers.
There was another ecash project that came later from Stefan Brands, one of David Chaum’s PhD students. It had many more features based on the representation problem, and an extension of the Schnorr signature scheme. It had blind signatures, which are necessary for privacy, and it supported multiple denominations, and it did not have the single denomination efficiency problem. And it actually has attribute certificates. So you could go to a certificate authority and present identity information to the certificate authority and it was possible to put your age, your citizenships, your credit rating, any kind of attributes you wanted, and the CA would issue a certificate with all these attributes encoded it. You would be able to selectively disclose those attributes afterwards, so you could prove that you were eligible to buy some good or service. You could also prove boolean formula regarding the attributes, in zero-knowledge. So you could prove this example like that you’re over 18 or that you’re a Dutch citizen. But someone overseeing the proof doesn’t know which of those is true, which specific values are or in the boolean formula are true. That’s all done in zero-knowledge, so it’s perfectly private apart from that. So you don’t need identity associated with this.
This same system could be used to make an electronic cash system, and it was licensed by DigiCash for a while, later by Zero Knowledge Systems. This is just some more details about how Brands’ credentials work. You encode some attributes into a public key, x is a private key, you blind this public key, you send it to the CA, and you also prove in zero knowledge what the attributes are in this blinded public key, the CA verifies it and signs it and then sends it back to you, then you unblind it, and you’re left with a certificate proving these attributes and you could prove these to other people.
Later I came up with hashcash thing, which as many mentioned, has to do with anti-dos for email. It’s decentralized, so there’s no CA or issuer of these things. You just issue them yourself with your computer. You just mine. They are generally going to be small because it’s just the cost of sending email, it might take 30 seconds or 1 minute. They are anonymous and fungible, because they are not resependable. Each link is a fresh coin. It’s not linkable. To prevent the same coin being spent to different people, the coin acts like a check. So when you send an email you put into a coin the email address of the person you’re paying, so when they receive it they will see that the coin is specific to them. So if you create one coin and spend it a million times, that wouldn’t help spam. But because the coin is specific to the recipient, the recipient can be sure in isolation without reference to any issuer or central server, that the work that went into this coin was specific to the email they are receiving at their email address. These are one use and they are not reusable. It’s like a postage stamp, it’s used up, and you use another one when you want to send the next email. So in this case the string that you are hashing is the email address, and in bitcoin it’s the coinbase transaction and the merkle tree of the transactions and all that stuff. And then you repeat a counter until you get a leading number of zeros in the hash, which is the difficulty. The counter should have a random offset or ther eshould be some other random offset to it, otherwise different users might have the same coins by accident and they would be invalid. So you see an aspect of this in, there was a bug in early bitcoin, maybe it’s still there, where Satoshi Nakamoto had forgot to reset the low precision counter that wrapped around. So all of his coins were linked together, and someone has a blog where they analyzed this and there was a graph where the coins were going up in value, and that kind of pegged Satoshi Nakamoto’s approximate number of coins. So that was a mistake regarding not starting the counter at a random offset. It’s important to do this in bitcoin because otherwise you could distinguish between someone with not much compute power who was lucky, from someone who had a lot of compute power who was unlucky, just by the size of the counter.
Then there were a couple of other things building on hashcash in reaction to the DigiCash shutdown. People saw that a central server wouldn’t work very well. People were interested in electronic cash of some kind being available. People were interested in privacy-enhancing technology, such as anonymous remailers, anonymous file servers, things which required network resources to operate but were privacy-related. So you wanted some kind of payment that wasn’t a credit card, and it would be a lower-barrier-to-entry than obtaining a merchant account to receive credit cards. If you’re providing a privacy service, charging a credit card attaches identity to it.
Two people made similar proposals around this time. There was B-money by Wei Dai and bit-gold by Nick Szabo (1998). They were using hashcash to mine coins, but then they make the coins respendable on the server. There will be a set of server that keeps track of account balances, whe nyou make a transaction you broadcast it to the network, and the servers between them keeps track of each person’s balance. There was no attempt to deal with the byzantine’s general problem, the problem of which transaction came first, or double spending. That was ignored by the design; and inflation was not directly dealt with. In B-money, the people operating the servers would vote amongst themselves for how many coins to make and then how much work it should take, and it was kind of a currency control board to define it. Bit-gold had some ohter market concept, where some traders would basically collect stamps of different rare scarcity and put them together into batches that would have the same value. Both of these would have; they are not fully specified, but they would have been pseudonym based, there’s no unlinkability to payments.
You could see bitcoin as a way to realize B-money and bit-gold but with the very hard problems that were glossed over except figured out and implemented.
There was a loss of functionality going from Chaum’s ecash which has perfect anonymity and perfect fungibility, and the B-money or bit-gold systems that were pseudonym based and thus linkable just like bitcoin. There was a paper by Sandra T. that provided something like blinding but for a distributed system in 1999. They had a paper about auditable electronic cash. Instead of using blinding, they used a zero-knowledge proof of set membership, so it’s somewhat inefficient but you can prove in zero-knowledge whether a particular value is a member of a set, without revealing what the value is. To deposit a new coin, you just add a number at the end, and to spend it you just prove that you have a coin in the set, and then there’s a double spend database to stop you from doing it twice. There was a merkle tree and a log n sized proof, so it was quite expensive. The interesting thing is that there was no bank private key, because the users were doing the proofs, so it’s actually compatible with B-money or bit-gold or bitcoin. It’s somewhat inefficient, but this paper was referenced by the zerocoin paper.
Then we have bitcoin, and it’s using hashcash mining like b-money and bit-gold proposed about 10 years prior. All of the other problems are solved. It introduced dynamic difficulty with a fixed supply curve. It was a distributed solution to inflation, which solves a number of problems. It’s, with reference to the system internally only, so there’s no central party that has to make decisions about the supply of currency. When people were looking at inflation before, they were thinking about no inflation, like no dollar-adjusted inflation or something, but bitcoin intentionally adds inflation so that it has initially quite high inflation tapering off, but the demand side has been higher so it feels like deflation in fact, so it acts as an adoption driver. And also, obviously, the solution to the byzantines general problem is that bitcoin can more efficiently solve the problem of which transaction came first. It’s based on pseudonyms, so it’s quite linkable. People say that bitcoin is anonymous, but there’s a number of papers showing this isn’t the case. When you spend, you pay change back to yourself, so now you have to spend the change later. When you get left over with change that is too small, you have to combine dust change and that further links transactions together. If you actually put it together with business records, with anoyne that has the ability to ship goods to you, it is clear that you would quite quickly become identified and there are a number of nice papers with lots of graphs showing network flow graphs that it’s extremely not private.
Then we arrive at this problem of taint tracing. Because it’s not very private, some people took an interest in tracing coins and I think the motivation was that there’s a number of high-profile thefts of coins from exchanges and other businesses, and that’s a problem for those businesses and they went out of businss because of it. Some people would like to put distance between themselves and coins that were used in illicit use. There is a law that says that currency is fungible, but because you can somewhat tell where a coin was used before, people started to care. Coin validation proposed to offer as a service to trace coins and try to give you a rating about how the history of the coin from your point of view and to offer that as a service to businesses. I think this could be quite dangerous because it goes back to that 17th century court case where now you could receive a coin that is perfectly valid at the time that you receive it, but a few weeks later a crime is uncovered and now your coin is tainted. So if this coin validation service is advicing many of the merchants where you would want to spend your coin at, it’s tainted and now the merchant would refuse to accept your coin. That’s a strange experience for you; you’re holding a coin that you might have to sell at a discount to get rid of it. The aggregate effect of this might create a run on the bitcoin price. So it reopens this long-set legal principle that currency or currency units are all equal.
The reason this whole problem arises is because bitcoin has weak fungibility. Unlike David Chaum’s digicash, which is perfectly cryptographically fungible, so you can’t tell one currency from another, in bitcoin that’s not the case. It’s being used for two different and conflicting purposes. The users are being assured, like people hear this transaction ledger is public, don’t worry it’s somewhat private because your name isn’t on it, but at the same time the banks and governments are being assured that it’s not very private. So these things don’t fit together. This creates conflict because users want more privacy once they realize how weak the privacy is, it’s like putting your bank statements online with your name blanked out. Governments and law enforcement often want the privacy features to stay as they are or to become less private. Then you have the other aspect from everybody that understands, they should want the fungibility to be good because otherwise the currency could lose its utility. The problem is that fungibility tends to provide privacy as a side-effect, so you can’t generally provide fungibility without getting some privacy. It sounds like it’s conflicting, and I think this is the source of difficulty for people maintaining bitcoin-related bank accounts. The banks are worried about volatility, which is unrelated, but also their ability to comply with regulations regarding who was behind a payment and those kinds of things.
So I want to say some things about identity. Just because the coin itself is relatively anonymous doesn’t mean that you’re anonymous when you use it in practice, and most people aren’t. Bitcoin’s privacy is quite fragile. But even if you had a strongly anonymous coin like David Chaum’s coin, or zerocash/zerocoin, the internet is not very anonymous. So you will often be giving your identity when you are paying for something. You have an account with an online merchant, you have your IP address, your delivery address, and you can have regulated businesses ask for your photo or a copy of your passport and all this kind of thing.
Then you might ask the question, “what properties do we want the system to have?”. There’s kind of this societal contract up around money and eavesdropping, taping people, a requirement for reasonable suspicion before you spy on people. You could see that if businesses are keeping business records for criminal investigations even if the coins are replaced, 99% of all users are not taking any efforts to protect their privacy, then law enforcement will be able to follow business records and work their way back and probably identify people anyway. So they could just present subpoenas anyway and follow it back to the business transactions unrelated to the crime.
Another aspect here is national intelligence agencies. As we have seen, they have from the Snowden releases that they have lots of network compromises, device compromises and network tapping; it seems unlikely that we will have a solution for that in the short-term. Host security is hard.
It’s quite hard for people to get privacy even with anonymous coins.
Zerocoin was another development. It’s a proposed, best system for improving priavcy in bitcoin with cryptographic fungibility and privacy. Zerocoin was published in 2013, it had an optimized set membersihp proof in zero-knowlege, it was more efficient though with another form of an accumulator. It provides good fungibility and privacy, but it has a number of problems. It’s quite expensive to create a coin, it’s quite expensive on a desktop CPU. It’s about 20-40 kB per coin. Only supports 1 denomination, because if you create more than one denomination then you reduce the anonymity or privacy of the system. Another problem is that, a big problem, is that the accumulator has a trapdoor so when the system is setup, somebody has to generate a parameter, and the parameter has a private key, and for the system to be secure everyone has to trust that person to delete that key. It’s hard to find a single person that everyone would trust to delete that private key. You could video tape someone taking a laptop and installing an OS, clean media on camera, generating the thing, printing it out and then destroying the laptop in an amusing fashion, and it wouldn’t be convincing because the whole thing could be faked. That’s a protocol problem. But also it’s inefficient.
Then came zerocash (2014), they presented on it and gave some information. It’s using some more advanced cryptography, some kind of zero-knowledge proof that some small C program is being executed on some private and some public inputs, and you get a small proof that can be verified efficiently afterwards, which is compatible with bitcoin in the 300 bytes kind of range. It actually works with a sha256 merkle tree, but the zero knowledge proof involving in that, if you just use the merkle tree it wouldn’t be private, but since it’s a zero-knowledge proof you can make that cryptographically private. It’s much better than zerocoin. Supports multiple denominations. There’s a globally shared parameter, about a gigabyte, that’s not so ideal for a smartphone but if tha twas the only problem then perhaps we could work with that. It’s quite expensive to create small compact proofs. It still has a trapdoor, a different one, but the same problem that the zerocoin trapdoor presents. And also in this case, it’s quite new cryptography, so sometimes cryptosystems fail, despite best efforts, even after a decade, and some of the things in here have been around for 15 years, but they haven’t seen practical use. If you rest 10 billion dollars on top of this cryptography, you might find that it’s not secure and the currency will crash. But it’s clearly a step forward.
Apparently, Matthew Green and Miers are planning to do an altcoin using zerocash. They are going to do some kind of setup ceremony to convince people that they deleted the private key. Whether it’s an altcoin or something else, there’s other ways to do it, at least they are going to try it out I guess. That’s potentially a politically sensitive thing to do since it’s very very anonymous.
Philosophically, if we could do this, should we? Would society tolerate it? If we say there’s a new electronic cash system, like zerocoin or zerocash without the trapdoor, perhaps someone would do it with cryptography that’s not too advanced; perhaps if someone cracks that, that would provide fungibility which is good, but is society ready for full anonymous electronic cash where you can transfer a billion dollars or 1 cent and it’s completely anonymous? You can see that transactions are happening, but you wouldn’t be able to see how much or who or when, and nobody could undo them or unblock them or freeze them.
I just want to say that it’s still very interesting to have extremely anonymous forms of ecash because you can think of it as a building block. Just because the base component has those properties, the resulting system doesn’t need that. You can use it as a building block in a larger system. You could have a transaction layer with anonymous coins, and perhaps less anonymity at the payment layer or something. You already get this to some extent with bitcoin because it has a transaction system and it also has a payment protocol where you can optionally, the merchant can certify themselves with x509 certificate and there’s an optional certificate for the user. There’s an analogy for that, there’s some transactions where you have to be non-anonymous, but you can still pay with cash. It’s like going into a gun shop and having to show your drivers license, but you are still capable of paying in cash in other cases. So society would be able to function with this I think.
So if we have this hypothetical, electronic anonymous cash at the transaction level, we could have optional certified identity for regulated business so that when you go to a bitcoin exchange or the equivalent, you could either provide your identity information to the exchange, or to a certificate authority and use that to more quickly be able to setup brokerage accounts or exchange accounts. The other factor that makes this reasonable in practice is that most users are not bad actors. And if the users and the buisnesses are keeping records of transactions, and users are having some basic self-certified identity, then if someone needs to investigate something they can just go do old-fashion police work to issue subpoenas and try to figure out what happened. You could argue that this replicates the status quo, and it avoids the kind of global, the completely public transaction database that bitcoin has, and also potentially avoids pre-emptive global surveillance that Snowden did a good job of uncovering.
There are some other interesting things you could do with this. You could say that, just because you’re having to provide proof of identity to get service, doesn’t mean that you want that merchant to know a whole lot about you. It’s not really important that they know your name or address if you are just buying an ebook or something. If they could have an encrypted version of your identity, then they could be assured that if there was an investigation they could give the police some information and then they could take that information and take it to the certificate authority, without your actual identity having to be broadcast to all of the merchants. You can just put some encrypted value into this. The hard part is the efficient distributed ecash system for fungibility; once you got that, it’s quite easy with existing simple encryption systems to encrypt identity and make it selectively revealable. For the non-regulated scenario, the users can just assert email addresses or whatever they find convenient. Defaults go a long way in systems, most users don’t bother to change defaults. So if the system was keeping a record just for your own information about what this payment was for, with bitcoin you’ll often find yourself confused about what this transaction was for, if there was a note of who sent it and what it was for, most users would probably keep that and find it useful. And that information could be useful in an investigation, so if most users are just doing their normal activity, then it means that there’s a similar kind of societal contract which is that you could have quite fungible coins, you could have privacy as a user, but investigation is still possible. The other argument which is to say, we need full identity everywhere, which is difficult to achieve with a p2p system, is that identity doesn’t fix problems. We have identity now, and there’s still thefts, and HSBC just laundered a billion dollars. Obviously they had identity for all of the Mexican cartel drug accounts, and identity isn’t the answer and thieves can steal identity. You should assume that most users are not bad actors, and you should keep records as a default for user convenience. If someone tried really hard they could put in false self-asserted identities, but they could already do that today with some simple identity theft.
Those are long-term things. While we have zerocoin and zerocash there are a number of problems. In the short-term people have been looking at various work-arounds that work with bitcoin as it is today.
CoinJoin is where bitcoin transactions have multiple inputs and multiple outputs, and it turns out that the inputs don’t have to be owned by the same person. Two people can get together and it can have four outputs. If the amounts are appropriate and not unique, you can get some kind of privacy out of this within the bitcoin protocol.
Another one is merge avoidance which is just that in the payment protocol you can pay for a transaction in multiple parts. If you need to pay $15, if you pay you know $5 three times and there’s lots of $5 transactions floating around and spaced out in time, it’s not obvious that you paid $5. You know and the merchant knows it, but the merchant doesn’t know it.
There’s one-use addresses, to avoid directly linking.
There’s a coinswap where it’s a trustless mix, where you can pay one person and they can pay someone else on their behalf but the network can’t see that they are related transactions and you don’t have to trust them to not run off. Smart contracts allow that.
Another one is coin control, most wallets don’t have good intelligence about which coins to use. This could be done in ways to reduce the linking.
Even apart from bitcoin’s single-use addresses not being anonymous, there are other factors which means it’s far less anonymous. There are donation addresses and vanity addresses; users find it inconvenient to understand and use one-use addresses. Many of the smart phone wallets are not using HD addresses, users simply don’t understand one-use addresses. It’s confusing. So there have been people working on reusable addresses, like a “stealth address” and a number of similar proposals. It only works with full-nodes. You encrypt the transaction for using a key derived from the recipients key, and the only way to find it is to try to decrypt every transaction on the network and is obviously expensive and wont work for smartphones.
Another proposal was to add a prefix so that a smartphone could find a transaction for that, but it reduces the anonymity set and makes things work. So a normal smartphone works with a bloom filter to add some ambiguity about which transactions you’re looking for, but it’s quite bandwidth-intensive so the bloom filter tends to be quite small, and so there’s not much ambiguity unfortunately.
The last one is an identity-based encryption address, which has not been implemented. But using some identity-based encryption based on a weil pairing, the user acts as an identity server so when the sender wants to send a payment, you have a one-use address which is your master identity key, they can derive from it a public key that is unique to an epoch in time and they can encrypt the transaction for that, and because of the way that identity-based encryption works, a smartphone wallet can derive the private key corresponding to a given block or epoch and given it to a random full node, which could decrypt the transactions in that block with that key, and give you the transactions if any that are waiting for you. That key is only valid for the public key related to that block, so it provides much more privacy and they can’t look at all of your transactions forwards and bookwards. The query is more compact than a bloom filter, but it’s more work for the node that has to decrypt the transactions so it could turn into a denial of service, if you could send to the node with no fee queries that require moderate cpu usage, so you might require a query fee for which there is no facility at the moment.
Another form of payment privacy is to do with the value of a transaction. If you’re somebody who is paid in bitcoin, if you’re working for a related company being paid in bitcoin, that might reveal your salary which is not nice. If you are running a bitcoin business, they might be able to reverse engineer your business model, see what your profitability is, or if you were somebody who was involved in early bitcoin then you have some large bitcoin wallets perhaps if you make a small bitcoin payment in person, they could see the size of the change address. This could be dangerous to your safety. Bitcoin payments are often made by default without any network privacy, like not using tor. They might be looking at the IP address of transaction origination and geolocate the street address and figure out when to burgle or steal your USB keys with large amounts of bitcoin.
So then there’s the idea that you could do something to cryptographically hide the value in a way that would be compatible with bitcoin. There’s a homomorphic encryption method. There’s also single-homomorphic encryption, which means you could have encrypted values such that you have an encrypted value A, and add to the ciphertext the encrypted value of B, and the result is the decryption of A + B. So decryption can work through encryption for some schemes like ElGamal which works with a variant elliptic curve (51m 39sec). This addition is not normal addition, it’s addition modulo n the order of the curve. Knowing that, if you were using these coins, you could add n to your balance, so it oculd become an easy way to print unlimited amounts of bitcoin basically, so you have to use a zero-knowledge range proof to prevent the wrapping, and it’s an expensive larger kind of proof.
This zero-knowledge range proof from Schoenmakers 2000 ish, I tried to optimize it. The normal bitcoin value is 8 bytes, 64 bits, and the optimized range proof in homomorphic value is about 1 kilobyte per encrypted value. That’s quite a bit of bloat, but it could be interesting for high-value transactions where you don’t want to reveal the contract amount or something. Basically it just works because the exponent or the scalar multiplies in elliptic curve notation add up. So there’s a random value x, which is just to hide the values which cannot be bruteforced, and then a second base h and the value is v, and it also works with unencrypted values, you can mix both encrypted and unencrypted values. You need the fee to be in the clear so that the miner can accept it. It’s a different privacy feature than cryptographically anonymous coins. The transactions are linkable, but people can’t tell how much money is changing hands.
So things you could do with that: you can preserve commercial confidentiality, you could provide open books for businesses because they have less reasons to close their books. You could perhaps be able to audit their insurance coverage. You could look to see that their smart contract for covering their business liabilities is adequate for the other metrics of the business. You could even have like audit in the sense that if you have an insurance company issuing policies, if the policy they are about to issue you pushes you over their insurance abilities, then each person receiving these smart contracts could immediately and fully audit that the business is following whatever rules in place. You might be able to get a bitcoin audited company, where its shares are issued on some kind of colored coin, and all dividends, salaries and so on sent on the blockchain, this could all be publicly auditable without any off-sheet risks. You could potentially also audit leverage ratios.
A curiosity related to homomorphic encrypted values is ringcoin. It turns out that because of this thing you can recombine it with zero-knowledge “OR” proof. How this works is that you, let me backup a second. There’s a form of signature, there’s a multi-party signature where two people can sign a transaction. Bitcoin has multisig which is not multi-party exactly. There’s another kind of multi-party signature called a ring signature where I can sign a transaction, and I can choose to implicate a random person of my choice as a cosigner. They know that either I signed it or that person signed it, but the person I implicated didn’t cooperate, I can just choose them. We can do this with homomorphic values. If I want to make a transaction, I can give it two inputs, one of them is mine and one of them is someone else’s, and the reason it’s okay for me to do that even though I don’t have the cooperation of the other preson is that in zero-knowledge I am either using that other key or the value I am taking up is zero, so that’s safe to do so you could potentially add privacy from this, and it’s potentially more private than coinjoin, and with coinjoin you are joining transactions with random people, and if there are people that are hostile to privacy in the network then they might flood the mixset for coinjoin with small transactions. You have no additional privacy in that context. With ringcoin you can at least choose randomly or pick plausible people with same kinds of similar interests and spending habits.
There’s one more type of system. There’s a committed-transaction concept. This is related to centralization risk and privacy aspects. It’s an idea related to the risks of mining power being concentrated in large mining pools. The idea is that the risk that you’re worried about with concentration of mining power is that the miners might start to enforce policy, or governments might demand they do so, and the policies might be stuff like “the recipient of the transaction or the origination of the transaction”. I found a mechanism to send an encrypted transaction to the network. In the initial stage, you encrypt the transaction in a certain way, the miners in the network validate the transaction. They are only partly validating it, because they can’t see who it’s from or to or the value, but because of the way it’s encrypted they could see that it’s not double spent. That’s all that the initial validation does. After some time, after like six blocks or something, the person who sends the transaction can reveal the key to the network or to the recipient of the transaction. It means that the miner cannot enforce any policy because they cannot see any information about the transaction until it’s done. After it’s done, a miner cannot undo the transaction without undoing its own work. And if the miner did undo work, they would be losing miner revenue, and the user could just go ahead and reveal more transactions, so it makes it uneconomic for miners to enforce policy basically.
The other interesting thing is that it seems as though there’s some dispute about who controls the protocol in bitcoin. You might say it’s the miners because they are doing the calculations, but in another way of thinking, it’s actually the users and their wallets because if a miner changes the protocol and all of the users ignore the coins coming out of it, then the miner hasn’t changed the protocol, they hvae just formed an altcoin with no users on it and the hashrate has fallen. There’s a limit to how far you can go. If the hashrate is 90% of something, and those miners start chasing the protocol, the hashrate could fall dangerously low and be vulnerable to double spends.
And this is how these transactions relate to privacy. You could respend an encrypted transaction in its committed form. You do this by sending the key to the recipient, and the recipient can see that the transaction hasn’t been double spent, and because you’ve got the key, they can decrypt it and see the unencrypted transaction that it comes from. It provides privacy initially, but as coins circulate, you receive the key and can see the transaction history all the way back to the unencrypted transactions. Over time it loses privacy when there’s 100 transactions in the history everyone can see everything as the coins get mixed together in the history. So that’s it.
Q: In zerocoin, these are built on top of existing bitcoin chain or is it an altcoin?
A: Zerocoin was proposed as a modification to bitcoin. It could have been integrated into bitcoin with changes, but it was viewed as quite, the transactions are quite large and the changes are evasive and complicated and it has a number of problems. Zerocash, learning from that experience of bitcoin not being willing to take the changes, they proposed to make an altcoin. Either protocol can be used in bitcoin or outside, but in zerocash the academic authors are thinking of making an altcoin with strong anonymity.
Q: Some of the protocols that you have described were invented 15 or 20 years ago. What can be used today? How far are we from actually using these?
A: Some of these are implementable. I think the problem for bitcoin is that it’s difficult to make changes because they have to be careful about damaging the values. So if you introduce a bug, potentially $10 billion can go up in smoke. There’s many incremental changes or known-defect,s there’s a big laundry list of known defects and they tend to not be implemented because of the caution.
Q: Why not the altcoins?
A: Yes, they have more scope to implement in altcoins for now.
Q: Can you refer to how reliable or how trustworthy sha256 is given the history of sha128?
A: So, actually, the sha1 problems are not relevant for bitcoin in the sense that the defect in sha1 was a birthday collision and bitcoin is using preimages, so even sha1 would still be good for bitcoin. And also, bitcoin can survive a graceful degradation in hash function security. Let’s say that sha256 turns out to be like 10x easier than we thought to create collisions or something, right? It doesn’t really matter, all that happens is that the difficulty jumps by 10x and then people update their mining software and we carry on. I think it’s quite secure.
Q: Something that was missing from your presentation was, you described what about ripple? Anything about ripple?
A: The question was could I say something about ripple. I think bitcoin has many different properties. Superficially it may sound similar, but ripple is more of a transaction network and it’s based on consensus rather than, it has no mining. It ends up being either subject to sybil attacks or ends up being centralized. At the moment I think it is centralized in the sense that all of the ripple gateways are companies with business contracts with ripple the company. And because it has no mining and it’s based on consensus, it’s not revocable in principle. One of the things that makes bitcoin transactions cheap is that they are irrevocable, it’s cryptographically irrevocable even the miners that just mined it; in ripple to undo a transaction, you just present a court order to 2 or 3 businesses in the US and the transaction gets undone. So the protocol stops and then they have to go and disambiguate what’s happening. I think they have some ambition or a plan to make it more decentralized but they haven’t worked out how to do that yet, so you could say that unless bitcoin is missing a trick, there only solution is to do what bitcoin does. I don’t know. They have aspiration to do something but it’s not clear if a protocol to do that exists without mining.
Q: So is ripple based on trust or friend-of-a-friend?
A: Yes, there’s some trust stuff going on. Think primarily that the gateways; they do some transaction cancelation to save transaction fees. They cancel out some debits and credits, so that at the time of cash out, they pay out banking transaction fees on $10 instead of $30 so they can save some on that, they are technically issuing IOUs between users and you have to setup a trust relationship to do that. I’m not sure how good it is for users to manage trust relationships. Maybe you just want a payment system to pay stuff, but managing trust relationships is something that Paypal has to do and there’s a mental cost to that, and I guess people will end up in disputes over small amounts of money eventually.
Q: (Something) coin claims to have some of the privacy implications.
A: I heard about it. I think several people, when zerocoin came out, were interested in putting it into an altcoin. I don’t know beyond that.
Q: So zerocash, what’s the attack model if someone knows the private key?
A: That’s a good question. I’m not 100% sure with zerocash. But with zerocoin, you still remain perfectly private, but the person with the private key can print unlimited coins. I think it would be the same with zerocash.
Q: So forging coins is possible but does not compromise privacy?
A: Does not compromise privacy, but someone has a bottomless wallet.
Q: Could you describe your confidence levels in bitcoin, given the problems and solution? Do you think bitcoin can overcome these things?
A: I’ve been interested lately in pegging. I didn’t talk about it, but the idea is that you can create an altcoin with no mining, kind of a merge mined coin and peg it into bitcoin in a way that you could move a bitcoin into a sidechain and you could move a bitcoin out of it. So if we could get those features implemented, a one-way peg could be done today, but a two-way peg requires changes to bitcoin. People could experiment with different features that interoperate with bitcoin. Someone could implement zerocash on a sidechain, move bitcoin into there, and then move out. It’s a way to experiment with colored coin features and zerocash features. If you have some experimental sidechain with bugs, you lose your bitcoins, but if it’s an altcoin it might be more like a penny stock that you don’t care about losing. But they have testnets as well, so you would probably wait to put real bitcoin into it.
Q: I am interested in identity verification. Is anyone trying this right now? Using cryptography like this?
A: I don’t know. I suppose you could say that, I don’t know about people issuing identity certificates; you can certainly get email certs I think there are some providers like CAs giving free x509 certificates for email addresses. You could see that the way the internet works is that there’s a lot of identity attached to connections and email addresses, and it tends to get logged either explicitly or by accident. So that’s sort of the status quo in a way.
Q: Someone was telling me that there was an architecture decision to not include turing-complete calculations in bitcoin for security reason? And now there’s something else like…
A: Ethereum? Yeah. Yeah, so the question was about ethereum and more complex scripting languages. I think bitcoin has an intentionally simplified scripting language for security reasons. People have explored adding features to bitcoin’s scrpting langugae. There could be the ability of a coin to look at the script of the coin that is being transferred to; even with that one simple change, you could make a viral contract that says if you’re going to make this change then this code has to be; it could have all kinds of amusing or bad side effects. If something has turing complete language, then it probably has that problem or possibly many others that we haven’t thought about. It’s potentially interesting in that it could be lots of fun to play with. It’s probably self-extensible and popular, but there are other concerns about the security of the interpreter. We’ve, there’s a long history of VM sandbox escape from java bytecode interpreters. If that were to happen with the ethereum interpreter, that could destroy it in one day.
Q: You mentioned that there were, difficult to make changes to bitcoin because of the need for consensus, and if there were bugs and defects still in the protocol, what do you think the chances are a future attack would severely compromise the security of bitcoin?
A: I mean, it seems to have held up so far. There was also the berkeleydb fork bug from 2013. There were also things wrong like things that are more complex than it needs to be, like the offline wallets like trezor and the armory wallets, the value of the transaction is not included in the signature, so the only way for an offline wallet to verify how much it is sending is to pull with it a bunch of transaction history. It’s a very simple and elegant change to put the value in the thing, and this has been known for years I guess. It’s just an example of small useful things that tend to not get done. There’s another one with signature malleability, when you have smart contracts involving more than one transaction, the second one depends on the first or previous one, and the transaction identifier is a hash of the transaction, the serializer for the signature is ambiguous, you can invalidate a multi-transaction smart contract by changing part of the contract, and you can walk away with half the contract. That’s a signature malleability bug, it’s fixable in the sense that if everyone stopped accepting those transactions..they could all potentially generate a valid transaction, but many clients are too forgiving in what they accept, and some are generating bad encodings. It does not require a hard fork, but it takes a while for everyone to get upgraded. I think that’s slowly happening but it might take a few years.
Q: Is this like escrowing?
A: Some of the smart contract things rely on multiple transactions, like fair coin tosses, atomic swaps, and all sorts of things like that.
Q: Does this make escrowing more risky?
A: Some of the escrowing doesn’t require multiple contracts or transactions, so that can be alright. Some more sophisticated transactions or contracts, you need more than one contract and one depends on the other. The second transaction if you send it to the network first, it will sit there and wait for the first transaction to see; if someone changes the first transaction, then the second part might never complete.
Q: You mentioned previously that bitcoin security doesn’t depend on sha256. However, if one finds an algorithm that solves it 10 times more efficient, and publishes the algorithm, then the network is really vulnerable against a 50% attack, you could double spend and you know override the main chain. Ignoring the orphan blocks, so the network doesn’t know how many blocks is discarded you just count the successful blocks and… It depends heavily on security of sha256.
A: Yeah, I mean, in the sense that there is some large disparity between the effective ease with which different people are mining. Some people have older generation mining equipment, graphics cards are no longer profitable, and then there’s multiple generations of asics. If someone was to find a faster way to do it and keep it to themselves, that could be very profitable to themselves. Maybe they would profit from it until it is discovered. My guess is that most things will be independently discovered, if it’s just a mathematical problem with the algorithm or something. If they are abusing it in terms of double-spending, that would be observable to the network. You can see double-spend attacks, if that happened in a large way people would realize something’s going on. About that, the other thing that I was mentioning was the committed transactions, which is a way to avoid at least policy attacks, it doesn’t prevent double-spend attacks, but it could be done to prevent miners attacking the network in that way.
Q: Once you establish decentralization, mastercoin or colored coins or these other projects? Would it be possible to solve the anonymity problem where you use these contracts and various inflows of payments to one address, and these contracts just scramble it to large outputs, but wouldn’t that solve the anonymity problem?
A: I think you could think of coinjoin and coinswap as things lik that. Coinswap involves four transactions to make that happen, it’s a smart contract to allow two people to exchange value without having to trust each other, it’s a trustless way with smart contracts to hide things.
Q: Couldn’t you use this to decentralize with either built on top of bitcoin for a new and solid as-is, or just counterparty…
A: It tends to not be very effective. There was some large theft, and the guy who stole the coins just traced them through lots of mixes and watched them with some large success ratio. I suppose if there’s nobody mixing the same amount of money, this was like 1000s of bitcoin stolen from some online service.
Q: One certain address and everyone uses the same address and the same … it would be .. just going through that address, and then that would solve it?
A: Maybe. There has been some move to use coinjoin, I think blockchain.info has implemented this. But apparently it’s somewhat slow because you have to wait for transactions, perhaps that’s because not many people are using it.
https://www.reddit.com/r/Bitcoin/comments/1qomqt/what_a_landmark_legal_case_from_mid1700s_scotland/