At PETshop on Monday before CCS, Cédric Fournet gave a talk on how extend Bitcoin to be provably anonymous.
Recent papers show that Bitcoin only offers limited anonymity because transactions are linked by the so-called addresses in the public ledger. This allows to run graph algorithms to find clusters and thus link addresses together and possibly to people if an address was to used to buy or sell anything. There are numerous anonymizer services, some of which simply steal the coins. However, even services with better intentions cannot completely guarantee anonymity.
Zerocoin addresses the issue by having transaction only linked through secret information. More concretely, every transaction features a commitment to a random serial number, the serial number of a previous transaction, and a zero-knowledge proof that the serial number is actually hidden in one of the previous transactions. The authenticity of a transaction is given by the proof, the uniqueness of the serial number prevents double spending, and the zero-knowledge property breaks the public link between transactions. However, every proof depends on the whole history, which implies that the verification complexity grows with the ledger, whereas in Bitcoin this only depends of the last usage of the coin.
It remains to choose a commitment scheme. Zerocoin uses Pedersen commitments and double-discrete logarithm proofs, to prove knowledge of an opening of an undisclosed commitment in a given list. It uses about one minute to both generate and verify a proof. To speed this up, Cédric proposed a system called Pinocchio, which is a pairing-based non-interactive zero-knowledge proof system. This allows information-theoretic succinct proofs with eight group elements in an extension field of a 254-bit prime order field. Another possibility would be to use SHA1-based commitments, but this would make verifying inefficient.
Cédric also highlighted that verifiable computation could become the norm with such a practical system that implements succinct non-interactive zero-knowledge proofs for an NP-complete language.
Recent papers show that Bitcoin only offers limited anonymity because transactions are linked by the so-called addresses in the public ledger. This allows to run graph algorithms to find clusters and thus link addresses together and possibly to people if an address was to used to buy or sell anything. There are numerous anonymizer services, some of which simply steal the coins. However, even services with better intentions cannot completely guarantee anonymity.
Zerocoin addresses the issue by having transaction only linked through secret information. More concretely, every transaction features a commitment to a random serial number, the serial number of a previous transaction, and a zero-knowledge proof that the serial number is actually hidden in one of the previous transactions. The authenticity of a transaction is given by the proof, the uniqueness of the serial number prevents double spending, and the zero-knowledge property breaks the public link between transactions. However, every proof depends on the whole history, which implies that the verification complexity grows with the ledger, whereas in Bitcoin this only depends of the last usage of the coin.
It remains to choose a commitment scheme. Zerocoin uses Pedersen commitments and double-discrete logarithm proofs, to prove knowledge of an opening of an undisclosed commitment in a given list. It uses about one minute to both generate and verify a proof. To speed this up, Cédric proposed a system called Pinocchio, which is a pairing-based non-interactive zero-knowledge proof system. This allows information-theoretic succinct proofs with eight group elements in an extension field of a 254-bit prime order field. Another possibility would be to use SHA1-based commitments, but this would make verifying inefficient.
Cédric also highlighted that verifiable computation could become the norm with such a practical system that implements succinct non-interactive zero-knowledge proofs for an NP-complete language.
No comments:
Post a Comment