Saturday, November 12, 2016

OpenBazaar: Truly Free Trade Through Crypto


All of the privacy tools in the world won't help one if all of one's commerce is centralized through a few corporate websites that eagerly mine one's information to sell to advertisers and governments either directly or indirectly. With time, a person can be profiled and targeted. The classic example of the pressure-cooker-backpack police raid shows that United States online purchases have become watched as if we lived in a totalitarian nation. 

While most agree that customs and standardized import restrictions in the real world are useful, many dislike it online. One country may impose political views upon the entire rest of the world because of the location that a business incorporates. The ability to censor what is sold, to fix prices, and to impose localized trade restrictions degrades free trade. Ebay, Amazon, and Etsy refuse to allow for resale of many items. This pushes users into the murky waters of sites without a verified trust system. Trust is the bedrock of online commerce. 

OpenBazaar seeks to create a fully distributed marketplace protocol which optimizes for anonymity, freedom, trustworthiness, and convenience. The restriction of full distribution without any central arbitrators or global buyer enumeration forces a creative architecture that promises high scalability. 


Threat Model


OpenBazaar has two classes of enemies worth considering. The first wants to abuse the system much as users abuse existing commerce sites on a daily basis. The latter wants to perform an expensive, widespread attack to deanonymize users or degrade the entire system.

Bad vendors and buyers are addressed very well through the power of multisig Bitcoin transactions and through OpenBazaar's web of trust model. 

The web of trust (which we explain better later) allows a buyer who trusts a small number of peers to iteratively predict the trust they should place in another peer. This network is created through using external services, interaction, or personal history.

When a sale occurs, the buyer and vendor pick a peer that both trust create a Bitcoin transaction which requires that 2 of the 3 parties agree to the transaction for it to move forward. This allows for arbitration without relying on a centralized support team. If one fears that a bad node may be picked, this type of contract can scale indefinitely. One could construct a system where 8 of 15 nodes must agree to the transaction, or it does not go through. Shipping tracking information and terms of the sale are placed into a cryptographically-traceable ledger that acts as a log for arbitration. 

Globally malicious attackers require a different type of strategy. Transactions occur over the blockchain, meaning that an impersonation (Sybil) attack would require an attacker to spend an unfeasible amount of money to overload vendors. In essence, they would simply be buying out the market and aiding business! 

To impersonate a vendor, an attacker would need to gain trust by becoming a vendor. Once they begin acting badly and tying up arbitrator time, their reputation will suffer. In this way, a Sybil attack degrades into a failed attempt to game the system.

Deanonymization attacks are the only justified fear. OpenBazaar does a good job of tackling the problem better than previous solutions. By preventing one from seeing the entire web of trust, OpenBazaar prevents an adversary who can observe some mail and who know a few users' identities from inductively tracing down every purchaser and vendor. 

A malicious vendor will be able to see one's IP address if Tor isn't used. Currently, Tor and OpenBazaar do not interoperate together perfectly. This is coming quite soon though, and current usage seems to be good enough for certain network operations. Oddly enough, OpenBazaar suggested one day rolling out an onion routing mail protocol. By encrypting subsequent addresses and sending the package to intermediate peers, one can mimic Tor and avoid exposing the sender address to the purchaser. This would carry a stamp cost, but may be able to keep people safe from persecution. 


Technical Difficulties


Attackers are not the only challenge faced by OpenBazaar. OpenBazaar is prevented from making certain naive design choices due to their commitment to convenience and scalability. 

While using a blockchain technology like Ethereum to host traffic would have been easy, it would have added an unacceptable latency and mining fee to each transaction. Furthermore, it's an expensive model for needless consistency. The network view is quite localized; a buyer only needs to talk to the vendor most of the time. 

Reputation change is included in the Bitcoin blockchain, but this information is included in a Bitcoin transaction that would have to happen anyways. 

Lastly, the commitment to full distribution forced OpenBazaar to make choices about what types of products they can create. OpenBazaar is primarily a protocol, not an application. There can be multiple frontends. This forced OpenBazaar to make a "machine readable" trade format that sends the required information over JSON. At the same time, "human readable" names must be used to allow users to familiarize themselves with vendors. 


Sale Architecture


The secret behind OpenBazaar's indefinite scalability is the use of their Kademlia-style distributed hash table. This DHT associates a globally unique identifier with a peer's hostname and port. This identifier is a self-signed public key that has been hashed twice. This GUID cannot be reused by another peer without access to the private key in the keypair.

As such a GUID would be unacceptably difficult to remember for most people, OpenBazaar can use the Blockstack system to associate identities with GUIDs. OpenBazaar initially used Namecoin, but switched to the alternative Blockstack. Blockstack embeds identities into any suitable blockchain, rather than requiring the separate Namecoin blockchain. This has the advantage of not requiring explicit support from mining pools, which increases the number of nodes mining the block. This, argues many, makes Blockstack more secure. Other information in the Blockstack entry can be used for external validation. It's worth noting that this could compromise anonymity entirely for some vendors.

In order to allow for people to quickly find a peer's listed items, the DHT also contains the hashes and keywords for items that are listed for sale. After finding the hash of an item listing, a peer can then request this listing from the vendor in a direct P2P manner. If this architecture feels like BitTorrent, that is because it is remarkably similar.

These listings are known as Ricardian Contracts and are digitally signed documents with the necessary server information and public keys for a peer to resume the contract's back-and-forth. Contracts describe everything related to the listing, in a JSON-encoded document. The format is flexible enough that the merchant can describe the structure of payment and business that they expect from a buyer.

This means that OpenBazaar suits both digital and physical goods, and could potentially be used for labor and "sharing economy" tasks. Without a centralized authority taking a steep cut, OpenBazaar would be quite attractive. The web of trust that we will cover next can be used to establish a validated reputation to keep people safe.


Web of Trust and Ratings



There are two cases that we trust a person in our daily lives. We typically either have had extensive interaction with a person, or we have had it with someone who trusts them very well. In OpenBazaar, this is also the case. 

"Direct" trust can be established between people who validate each other's identity through other channels. If one doesn't have direct trust rating for a peer one wishes to query the evaluation of, one asks one's peers what their trust rating for the peer is. They perform a similar recursive check and query. Eventually, this bottoms out with a series of trust estimation chains. 

A trust value ranges between 0 and 1 for positive trust, and 0 and -1 for distrust. The peers one will query from must be trusted, and must therefore have a trust between 0 and 1. This can therefore be used as a scale factor. By taking the product of the trusts along the chain, and summing up all such products, the query finds an aggregate trust for the peer for a node's corner of the web. 

This system is entirely decentralized. The partial observability built into it also prevents deanonymization through passive observation by a nation-state adversary. To avoid enumeration, nodes must only allow queries from trusted nodes. 

There is one worrying attack that OpenBazaar is vulnerable to. A peer which copies the listings of another vendor could simply forward buyer requests to another peer. This would lead to an accumulation of trustworthy interactions with an untrustworthy individual. Furthermore, this attack is cheap. It could be done by almost anybody. The definitive way to check for one such abuse is for the vendor to include a copy of their GUID and key material inside the shipment. A buyer can therefore find out if something is wrong, and can spread news of distrust throughout the network. An adversary who is willing to receive and repackage shipments is essentially acting as a legitimate reseller. 

This system can be insufficient though. The web of trust should be a single web; this system is not difficult to partition. In order to provide a global trust score for some users, an external resource must be burned to prevent someone from creating many globally-trusted accounts and bootstrapping evil peers of these accounts to be recommended indirectly. The current best solution to that is simply to buy your good graces. By using Bitcoin's scripting language to make coins unspendable while recording the user's hash, a user can provide global evidence that their account cost them money to keep. The economic disincentive for that peer to behave badly has been proven to the network. 

The rating system is different. It's much more fine-grained for starters, enabling a review of shipment time and item quality as well as other attributes. Secondly, the goal is not to tell whether a peer is abusive but whether they offer a high-quality service. Ratings and reviews are documents in the DHT which have their hash embedded in the payment Bitcoin transaction. Ratings require transactions, which require a purchase with the vendor. Impersonation and sybil attacks are mitigated in this way.

Vendors do not review buyers, as all opportunities for buyer abuse are mitigated or arbitrated away by the protocol.

Success of Protocol


There are currently between 5,000 and 5,500 listings posted to OpenBazaar DHT. One can find everything from Alibaba purchases to expensive teas to physical and digital artwork. The network is slowly but steadily growing, and appears to have a lot of users who remain lightly active. 

The myriad of implementations are likely the reason. The official desktop application is a Javascript desktop application written using the Electron shell. For mobile, there is BazaarHound. Both of these allow for interactive exploration and make it easy to instantaneously purchase an order. 

Search on the applications could be better though. For this, there are two popular search engines: DuoSear.ch and BazaarBay. The former appears much more polished, competing with many small-time centralized interfaces for quality.

The official desktop application can be made to work through Tor, to add and another layer of anonymity. Information about one's host may be leaked by the information in the protocol itself though, and it's not clear right now how much the software will expose. In OpenBazaar 2.0, CoinDesk promised Tor integration from the ground up. The reliance on the IPFS (inter-planetary filesystem, a BitTorrent-like file network) means that IPFS must work perfectly with Tor for OpenBazaar to. 

This protocol has multiple implementations and is growing to carry many novelties and staples steadily. The flexibility and trustworthiness of the service means that OpenBazaar makes an amazing platform for new applications of the sharing economy which protect the users' privacy.


References


docs.openbazaar.org

Saturday, November 5, 2016

Ethereum, or the Blockchain of Code


Software is incredibly powerful. Like most things in mathematics, the more powerful the thing being studied is, the harder it is to state useful things about it. In fact, the definition of programming as we know it came from Turing's seminal paper on the Halting Problem which told us what we couldn't do with a computer. It is from this that we draw the name "Turing-complete" to describe any system which is computationally powerful enough to run into the same limitations.

The Halting problem prevents us from knowing for sure how a computation will turn out without running. A slightly different problem that haunts many domains is that software is inherently disappearing. In calling a function, we trade the arguments for the end result. In the name of space efficiency, we later discard our arguments most of the time. At some point a variable is "useless" and the data it contained is erased.

Anybody who has gotten a bug report with an application state that seems borderline nonsense can understand the pain of this. Trying to reverse-engineer what one's own code did is what makes debugging so time consuming.

A slightly different problem caused by this is that it becomes important where code is run. When two systems cooperatively interact to compute something, something can go wrong at every single step of the way. Frequently, something does. It becomes the duty of an ultimately trusted entity to pick up the pieces and decide what the correct view of the world should be. In many situations, this is unacceptable.

The Solution

Ethereum tries to solve this problem by having everybody run the code, and by keeping around the arguments used to generate the result indefinitely. If this sounds expensive, it is. Someone using Ethereum to do numerical computation over a large amount of data is going to have to pay the network a lot for it.

Most applications aren't like this though. Most applications are thin, pretty wrappers around a data store that allow for simplistic manipulation. Messaging applications, commerce, social networks, and asset management applications are all examples of this.

The interesting thing is that when everybody is running the code, it is almost as if nobody is running the code. There's no need to keep servers online constantly to receive messages that might come with unknown frequency. The network as a whole provides uptime on behalf of the application writer. In this way, Ethereum applications are frequently called "serverless."

Ethereum promises a lot, and they do a pretty good job of delivering on it.

Architecture 

Ethereum is a blockchain technology, like many of the architectures that we've covered thus far. Human input into the network is done by sending transactions to the mining pool, which validates the transaction and adds it to a block to mine. After a miner manages to find the integer necessary to make the block's hash smaller than a determined difficulty, the block is considered part of the chain and the mining pool starts on the next block.

In financial blockchains, a transaction is always an exchange of value. Validating a transaction is thus validating that the person sending the money actually has the money. Bitcoin also has a scripting language which allows for very rudimentary computation. In Ethereum, use of the scripting language is the primary reason to use the network. Ethereum also contains a currency, which is used primarily to pay the transaction fee to the miners but can be sent between people as well. Validating an Ethereum transaction involves executing scripts held by the recipient of a transaction, which is paid for with the sender's transaction currency.

Contracts

A contract is born by making a transaction which contains the compiled code of a contract in the data field. After mining, this contract becomes an entity that can receive transactions.

A contract is really thought of as a self-contained piece of code that responds to payment messages by executing the script. This script execution can essentially do anything that a person interacting with Ethereum can do. Scripts can create new contracts, send transactions to other contracts, and save the results of computation to a permanent storage. Anything that requires computation or storage has a computational fee that is measured in "gas" and is what determines the mining fee.

What's interesting is that these Turing complete virtual machines live on the blockchain to serve their defined goals without any further need for the code author to interact with the network. As long as the people who need to run the code can afford the execution, the network will take care of everything.


Managing Turing Completeness with Gas Money

Now anybody familiar with the Halting problem will flinch at the thought of putting an open server out there which will run any code submitted to it. An infinite loop can be crafted to lock up a system. A malicious agent would be able to derail every node that tries to validate that transaction.

Ethereum handles this through fine-grained accounting. A transaction contains two figures that determine the cost to the sender. The STARTGAS counts the computational load of operations that the sender expects the contract to run. Operations which store data or are more computationally expensive have a higher price in gas. The GASPRICE is the rate that the sender is willing to pay per "gas" unit in terms of Ethereum's underlying currency.

A transaction verifier will run a contract until the gas runs out, or until the script finishes. If the script finishes then the remaining gas is refunded to the recipient and the miner keeps the product of the consumed gas and GASPRICE. If the gas runs out, all state changes are reverted and the miner just keeps the money. 


Scalability

Ethereum, like Bitcoin, faces the issue of storage. If Bitcoin were to handle the load of a modern credit card processing company, it would grow by about 1GB per hour. If Ethereum were to become mainstream, a naive implementation of it might face the same issues. As the blockchain grows, fewer and fewer nodes can afford to hold onto the entire chain. These "full nodes" have all of the power; if they were to form a malicious alliance then the history of the blockchain would be at risk.

Ethereum will likely scale a bit easier by the fact that the blockchain is not quite necessary to get a full view of the state of the network. Each Ethereum full node needs only to hold onto the global storage and the holdings of accounts, and can fold each incoming block into this.

Ethereum uses a modification of a Merkle tree optimized for addition and removal called a Patricia tree. This tree refers to subtrees of previous blocks by hash and tries to reduce hash invalidation. This is used to create a hash of the global application state that can be inserted into each block.

Ethereum has a formal method for finding the bad link in a poisoned chain. If a chain has a defect, it must occur between two blocks such that state N is correct and state N+1 is not. By walking through the blockchain from an expected good state, maybe even the initial block, a node can find the exact wrong state transition and can offer it to the network as proof that another miner had mined a bad block.

There is another kind of scalability worth considering, and that's the ability to do things cheaply. Ethereum's costs are relatively high currently, making it inappropriate for certain classes of high-throughput systems. Ethereum is moving to proof-of-stake in order to make it less computationally costly to mine, and therefore less expensive for the end user to run contracts.

The DAO

One cannot talk about Ethereum without talking about the problem that was the DAO. The DAO, or distributed autonomous organization, was an entity that would hold the users' funds in a joint account that would be utilized as the holders saw fit. The DAO was widely successful, raising $150 Million. 

Unfortunately, the contract behind the DAO had a few bugs. Furthermore, the creators of the project didn't expect such a success, and put all of the money into a single account. This enabled an attacker to leave the DAO in a state that threatened to have the funds made useless or able to be stolen outright. 

The solution that the Ethereum project saw was to provide miners with an option to choose to continue mining the version of the blockchain that contained the result of the DAO and the attacker's actions, or to mine a new version that relocated the funds so that caretakers of the DAO could refund those who bought in to the best of their ability.

The miners favored the refund, and the attacker had their funds taken from them by the network. This "hard fork" was met with both relief and unease. This showed that unpopular actors in a blockchain network can have the network decide to do whatever it wants with their funds. While this is no surprise, given the nature of the 51% attack vulnerability in blockchains, it burst the bubble of some of the most crypto-anarchist-libertarian supporters of cryptocurrency. 

Cryptocurrency assets are able to be seized. The global consensus of ownership is a democracy due to the nature of the underlying blockchain.
 
Ethereum Ecosystem

A language or virtual machine succeeds or fails based on the flexibility of implementations and the availability of existing libraries. Ethereum is no different. There are many programmatic implementations of the clients currently, but the exciting stuff is still on the horizon.

At this point in time, much effort is being put into Ethereum's Mist browser. Mist offers a user-friendly interface for the intricacies of distributed serverless applications. It functions as a client for the Ethereum network and prioritizes privacy and the user experience.

I look forward to seeing the distributed applications that people will build for this exciting new platform.



References

https://github.com/ethereum/wiki/wiki/White-Paper
https://github.com/ethereum/wiki/wiki/Mining
http://ethdocs.org/en/latest
https://blog.ethereum.org/2016/07/12/build-server-less-applications-mist/
https://github.com/ethereum/mist 
http://www.coindesk.com/understanding-dao-hack-journalists/

Saturday, October 29, 2016

ZeroCash: Trustless Bitcoin Tumbling

Use Case:

ZeroCash is to bitcoin like Tor is to traffic. ZeroCash wants to mix everybody's traffic up between users in order to get privacy. Bitcoin's dirty little secret is that it has very little privacy; anybody who reads the chain can figure out what accounts are doing. By following the flow of money, an adversary can spy on a person's monetary activities. 

Increasingly worrying is the lack of forward secrecy on the blockchain. There's nothing to stop a heavy-handed agency from subpoenaing everybody who sent someone bitcoin. Someone can be found guilty through association. 

Forget a court of law, bitcoin transactions can make someone guilty or vulnerable in the eyes of another party. Hacktivists and simple hackers will know who has a bitcoin nest egg and might be motivated to attack your computer to get access to the keys for the bitcoin.

Many people turn to sites called tumblers. Tumblers are centralized sites that take in bitcoin and allow users to "cash out" bitcoin. This works to split a bitcoin wallet up into hundreds of pieces and to give a different hundred pieces to a different bitcoin account. This policy is currently the standard way to get privacy with bitcoin. This way is not perfect though.

This centralized tumbler might act in bad faith. They might act good for 99 days and on the 100th day run off with thousands of dollars in bitcoin. They might be working with an attacker to profile transactions. They may take your hundred bitcoins and give them all to somebody who uses them to break the law in a way that traces back to you. They may do all of these at the same time.

ZeroCash is a protocol underlying the newer tumbler pool called ZCash that hopes to provide a trustless solution to tumbling.

Implementation:

The basic idea behind ZeroCash is to create a pool of funds that anybody can use to mix their holdings in. After adding one's bitcoins to the pool, one can take out an equal amount of other bitcoins in order to hide a paper trail. The problem with this is that the process of identifying which deposit the withdrawing user had used is enough information to identify the withdrawing user. This could defeat the purpose. ZeroCash thus uses zero-knowledge proofs to check and manipulate what people's balances are without exposing which users are being manipulated.

ZeroCash has a construction which uses some tools that we haven't seen before. ZeroCash falls back upon non-interactive zero-knowledge proofs (zk-SNARKs). These are slower than some of the other cryptography that we've seen before. These zk-SNARKs are quite complex things. They enable someone to validate certain characteristics about a piece of encrypted data without seeing the decrypted data. The crazy thing is that in ZeroCash, this zero-knowledge proof will provide evidence that someone has been owed enough

ZeroCash has two operations, Mix and Pour. Both of them build up the cryptographic state to create a new "now." When someone adds new coins to the pool, they perform a Mix. When someone removes coins from their pool, they perform a Pour.

Since it's relatively expensive to use the zk-SNARC, most of ZeroCash's design is based around minimizing the amount of reliance on the mechanism. Mix and Pour both create states to validate, but only Pour transactions really require a full validation as Pour transactions are the only ones that require action from the pool. These transactions are a few microseconds, so they're not incredibly slow. They would definitely pose a problem to scaling to a proof on every bitcoin transaction.

One of the secrets to scaling ZeroCash is that the zk-SNARC is not forced to handle a structure tracking every account in the pool. ZeroCash maintains a Merkle tree. The depth of the tree is logarithmic in the number of transactions, making it much more computationally tractable to carry out the slower zk-SNARC operations.

Effectiveness:

ZeroCash is just fast enough to do what it promises but too slow to do much more. The algorithm underlying the system is quite powerful and complex, using cryptographically-verified manipulation of ledgers that nobody can read the entirety of. People interact with the ledger to carry out their ZeroCash activities, creating a state that can be queried and verified later. 

Nowhere in this state is there a decrypted copy of whom has inserted and removed the coins in question. When someone wishes to remove a unit of currency from the system, they cause the state to change in a way that does this without exposing their role in the operation. This offers near perfect anonymity to the user. 

The problem is that this system is both very powerful and fairly slow. While only taking milliseconds to verify a number of proofs, these add up. This means that most people won't use ZeroCash between every transaction, only as a way to "clean" a quantity of coins of a paper trail.

This nature is reinforced more by the fact that ZeroCash is unsuitable for transactions. Transactions require a long chain of money changing hands; which may become arbitrarily difficult to process. Because of this, and because of the lack of ZeroCash proof checking by bitcoin miners, ZeroCash cannot work as a sidechain and transfer money between peers. ZeroCash is only a money tumbling service. 

How good of a money tumbling service is it? So no longer can a tumbler operator collect traffic analysis or steal from a user. No longer does bitcoin laundering require communication with multiple active parties. 

On the other hand, someone who analyzes the ZeroCash network may be able to perform attacks which are quite similar to the attacks on any mixnet. If an attacker observed someone pay 0.083 btc to ZeroCash and then 0.083 btc in transactions leaving the network and all eventually going to the same address, then the attacker can correlate the message. Likewise, if someone uses the network for a quick Mix and Pour in the middle of the night when the network has few other people, then the timing of the transaction is enough to betray who was doing the mixing. Lastly, you have no control what the coins that you put into the pool are doing. You may be unintentionally implicating your bitcoins in felonies. 

ZeroNet thus needs enough users for "privacy in numbers" in order to get real privacy. 



Extensions of Idea:

The really interesting thing is to consider the mechanics of this system. By anonymously allowing users to "check in" and "check out" resources from a global pool, ZCash contributes a novel cryptographic technique. In many systems, embedded devices will take and return resources such as shared locks. These systems must work hard to prevent reverse engineering and obfuscation.

ZCash seems like a reliable model for cooperative resource sharing among agents with strong ownership. After it becomes more mainstream, it will be interesting to see how it may be applied to the embedded blockchain domain. 


Resources:

https://github.com/scipr-lab/libsnark
http://zerocash-project.org/media/pdf/zerocash-oakland2014.pdf
http://eprint.iacr.org/2013/879
https://z.cash/

Saturday, October 22, 2016

How BitTorrent Really Works



BitTorrent is both ambitious and simple. BitTorrent is a P2P protocol in which peers coordinate to distribute requested files. In order to resist downtime due to real-world seizure of computers, BitTorrent has had to progress to a fully distributed architecture, without any single point of failure. This is an impressive technical feat.

Even more impressive is that BitTorrent gets faster with additional content-fetchers, rather than slower. The classic economics of content distribution is suddenly inverted, rewarding high-desirability content.

It's no surprise then that BitTorrent is used nowadays for everything from sharing Linux ISO files to live broadcast streaming of sports and politics. BitTorrent's name is still controversial in many places because of its role as a subversive software. BitTorrent's power made it the first choice for piracy, which lead to many concluding that BitTorrent is only useful for piracy. While many ISPs and externally-administered networks attempt to block and trace BitTorrent, the fight has largely been lost.

By not placing restrictions on peers, BitTorrent opens itself up to a universe of attacks. Like other architectures, a combination of limited observability and sound mathematics is the solution. As we will see, the architecture prevents an evil actor from serving a corrupted file or causing undue load on the BitTorrent network.

Lastly, BitTorrent is forward-thinking. It contains an extension protocol that allows clients to design protocols that alter the behavior of peers, and enables peers to intelligently fall back upon the extensions supported by each. At the bottom of this is the basic peer protocol; ensuring that clients can agree on enough to simply serve the file if they share no extensions.

The Peer Protocol

When a peer wants to start sharing a file, they construct a metadata file that describes the attributes of the file as well as a number of options. BitTorrent uses bencoding for most data sent, which prefixes a data literal with a character describing its type and its length (if a string). The metadata will describe the files in the torrent, but also includes a SHA1 hash of each of the "pieces" or file fragments in the torrent. These fragments can be downloaded individually, allowing for streaming or for selective downloading.

The file's attributes are known as the "info" block and is what uniquely defines the torrent. The info block's hash is the torrent's unique identifier in the BitTorrent swarm of peers. This metadata file also announces a tracker that the torrent will be associated with. This is outside of the info block, to enable multiple tracker to track the same torrent and to have the same infohash.

This metadata file is half of what a downloader needs to know to download the file. The other half is the list of peers serving the torrent. Conventionally, a peer will query the torrent tracker for a list of peers serving the file. The distributed hash table, peer exchange, and local service discovery are all other methods. We will discuss the first later. The latter two can be thought of as "gossip" protocol extensions that allow peers to become known by the swarm. 

Now once a peer has a list of peers, and has connected to each of them over TCP (or the uTorrent transport protocol, not covered here), it now uses the peer protocol to fetch all of the files. These peer connections are bidirectional and have attributes set on them by either side. Peers will announce when they have finished downloading a piece, so that peers connected to them know whether they want anything from a certain peer.

A side may be interested, which means that they want "pieces" that the other peer has. A side may also be choking, which means that they're busy sharing with another peer. When a connection is both interested and unchoked, then data transmission happens. Peers will use "optimistic unchoking," or rotation of the choke list, to ensure that there is enough choke variability for the swarm to have a fair chance of progressing. Choking is done in order to limit the number of outbound TCP connections, to ensure that the communication switching overhead is low enough for a peer to be useful to those it is connected to.

Transmission only occurs when one side is interested and the other side is not choking. This enables peers to have a tit-for-tat where the peers which share the most freely are the ones which are able to access pieces the most rapidly. This localized enforcement of good behavior enables the network to scale upwards without collapsing. The hashing of all pieces sent ensure that no peers can "poison" the network by sending bad file fragments. This pervasive integrity checking was one of the things that allowed BitTorrent to succeed where its early competitors failed. 


DHT and Magnet Links

BitTorrent uses a DHT protocol to enable peer discovery without requiring communication with the centralized tracker. DHT "nodes" are not the same thing as torrent "peers," although a computer can be both. Nodes listen for DHT requests over UDP, while peers listen for the BitTorrent peer protocol over TCP. BitTorrent clients include a DHT node, which operates mostly as a querying "client" node.

The Kademlia-like DHT works by giving each DHT node an ID. IDs have a "closeness" metric that is computed by XORing two IDs together and interpreting the result as an unsigned integer. Nodes will know about other nodes which have a low XOR distance and will know about few nodes that have a high XOR distance.

A client makes a query for a torrent by using the hash of the metadata's info as an ID, and finding the node that it knows that is closest to the key. This node is then sent the request. If the node doesn't have the torrent, the node forwards the request to the node that is the closest to the ID that it knows. This process iteratively finds the node in the network that is the closest to the query's key. If the peer can't find a peer tracking the metadata's info hash, it will have to insert itself as the node responsible for the key into the DHT by introducing itself to the nodes closest to the key. 

In order to prevent a bad actor from registering other peers for torrents, the DHT includes a paper trail. The query will return a token. If the query fails, this token must be presented by the peer trying to register itself as responsible for the key. Tokens are only valid for approximately ten minutes.

A node constructs a list of peers by searching the DHT for nodes closest to its own node ID. Most of the peers the node knows will have nearly keys. A few exceptions will exist because of other observed nodes through other network operations. In this way, nodes tend to construct a very "localized" view of the network that makes it faster to narrow in on a single key quickly. 

Now this DHT is quite simple, it associates peers with a torrent. In order to get the querying node enough information to begin downloading the torrent, the network must serve the torrent's metadata file as well. This newer feature is referred to as a "magnet" link, and enables a peer to complete an entire download using only the node ID. Trackers using magnet links need only provide links with hashes, rather than indexing and serving a collection of torrent metadata files.

Private Torrents

BitTorrent is a very inclusive network in its default state. The Distributed Hash Table, peer exchange, and local service discovery can all help a peer find other peers without having to rely on the tracker. While this is typically a good thing, it can be undesirable to remove the ability to control file distribution centrally.

One frequent use case for centralized control is to enforce a share ratio. When a community shares many files, it becomes important to enforce that peers upload an acceptable ratio of data to what they download.

This fine-grained access control is done by restricting peer information querying to those peers that the private tracker decides should be able to download the file. This is really security through obscurity.
Once an intruder peer has obtained the IP address and port of a peer, regardless of the source, the intruder can initiate a connection to that peer and trade pieces with the peer. Once in the swarm, the intruder is granted equal treatment as all other peers. 
Source: http://www.bittorrent.org/beps/bep_0027.html

What happens is that the torrent's metadata file includes a "private" flag that tells peers to only use the tracker to exchange peers. Furthermore, a client may only use the peers from a single private tracker at a given time for a given torrent. This prevents a peer from uploading a private metadata file to a public tracker and having the existing swarm serve the file.


Future

We're seeing a lot of new innovation in the BitTorrent sphere recently.

BitTorrent's power is proportional to its convenience. The associations with piracy have led to BitTorrent software that requires that one jump through a lot of hoops in order to use the software sometimes. You can only download from BitTorrent what peers are seeding through BitTorrent. Convenience is largely the reason that many consumers have abandoned piracy torrents in exchange for services like Netflix and Spotify.

PopcornTime (https://popcorntime.sh/) is an example of the power of BitTorrent with good content indexing and a nice UI. While it is plagued by the fact that it is a piracy-focused tool, PopcornTime represents a fairly flexible CDN system for popular media. One can imagine clones for open-access media and for news. What's worth noting is that the cost of running PopcornTime is absolutely minuscule for the software creators, especially compared to the behemoth infrastructure of Netflix. With good copy protection on media, BitTorrent may one day be seen as the powerful content-agnostic technology that it is.

BitTorrent is useful for a lot more than shuffling around large files though. WebTorrent uses the newer webrtc browser features which enable P2P data channels. Browsers are now able to act as peers, making the ecosystem much more flexible. It's worth noting that WebTorrent peers are not compatible with BitTorrent peers due to the use of webrtc for transport, rather than naked tcp sockets. As well as serving large media files, torrents can now serve static websites. Peers can send messages and media between each other in realtime chats without relying on a centralized server. With enough adopters, webTorrent may invert the economics of web hosting. Popular sites will be cheaper to host than less popular sites, without having to fall back on advertisement networks.

The web2web (https://github.com/elendirx/web2web) project uses bitcoin and BitTorrent together to replace the entire web stack. The blockchain is searched for the last outgoing transaction from a given address. This transaction uses the OP_RETURN bitcoin opcode to define the transaction as invalid, and stashes the torrent infohash in the transaction's body. This hash is enough to fetch the website being served through WebTorrent.

CacheP2P (http://www.cachep2p.com/) uses WebTorrent to offer a website cache. The reasoning is that popular content is likely to have a nearby peer which is closer than the nearest CDN server. CacheP2P, it's worth noting, costs the website maintainer nothing and costs each of the site's visitors a very small amount of traffic. This stands in contrast to the expensive caching infrastructure necessary to blanket a country or the globe. If a site becomes more popular in a certain area, CacheP2P will bring more cache servers to the region automatically. This latter point is a good enough argument alone.


Resources

http://www.bittorrent.org/beps/bep_0003.html
http://www.bittorrent.org/beps/bep_0004.html
http://www.bittorrent.org/beps/bep_0005.html
http://www.bittorrent.org/beps/bep_0006.html
http://www.bittorrent.org/beps/bep_0009.html
http://www.bittorrent.org/beps/bep_0023.html
http://www.bittorrent.org/beps/bep_0027.html
https://github.com/elendirx/web2web
https://webtorrent.io/
https://popcorntime.sh/en

Friday, October 14, 2016

How the Textsecure Protocol (Signal, WhatsApp, Facebook, Allo) Works




Goals


The goal of TextSecure is to offer "end-to-end security, deniability, forward secrecy, and future secrecy". What this means in practice is that TextSecure wants to construct a stream of messages between two people which keeps key material around for as short a time as possible. Key compromise in the future should not make it possible to decrypt traffic observed today. 

I've covered a critical analysis of the Signal Protocol below. It studies the implemented architecture, notes discovered flaws, and evaluates how well the stated goals are met. A deeper analysis of the goals follows the system description.


Terminology


TextSecure is one name given to the application now called Signal. The codebase and the documentation throughout it use the name TextSecure. In order to maintain consistency with the System, I will refer to the entire system as TextSecure. 

In reality, there are a number of different things here:

The TextSecure Server, referred to as TS in the linked whitepapers (bottom) is the centralized server which coordinates state for the rest of the system. 

The Signal Protocol refers to the more general protocol in use by messaging apps from Facebook Messenger to Google Allo. It implements the functionality described below, but leaves these implementations free to do message routing and metadata tracking however they like.

The Signal application is a mobile application which implements the Signal Protocol using the described TextSecure Server policies analyzed below. This is the original implementation of the protocol. 


Architecture



TextSecure is a modification of the Off-The-Record chat protocol with a focus on asynchronous coordination. Whereas OTR requires an interactive handshake, TextSecure considers the indeterminate latency unacceptable. Having to bring an app into the foreground and carry out a handshake before being able to send a message would offer a terrible user experience.

Instead, copies of the server's role in the key negotiation are stored by a centralized server for potential clients to fetch and use. This server acts as a channel not trusted with key information able to decrypt anything; all encryption is end to end. 


Cryptography




TextSecure uses a small set of cryptographic primitives. Public key cryptography is carried out through elliptic-curve Diffie-Hellman using Curve25519. AES is used for symmetric encryption, for both counter mode without padding and cipher block chaining mode. HMAC-SHA256 is used for message authentication. These are the trusted base.

Double Ratchet:


The core of TextSecure's encryption engine is the Axolotl double ratchet algorithm. The big-picture idea is that there are two ratchets that can move forward: a receive ratchet and a send ratchet. The structure allows for the first half of the key negotiation to be saved and replayed asynchronously later to yield a full handshake. 

The receive ratchet is used when a message is received, which must include new material for the next key negotiation. This material is used to generate new symmetric keys for encryption and message authentication later. 

The sending hash ratchet generates a new set of keys using the keystream generated from the previous set of coordinated shared secrets. This ratchet is reset when the receive ratchet is activated and the shared secrets change.

What is important here to observe is that a sender never has to wait in order to send a message. They can always take a step to send a message which terminates in a bounded amount of time. These messages will all be encrypted with different symmetric keys. This means that the current keys on either person's devices cannot be used to decrypt a message sent in the past. (We see later that this has one caveat.)


Protocol



- Phase 1: Textsecure Registration



Registration starts by having a client tell the server the phone number with which it can be contacted, as well as whether it would prefer to receive a token via phone call or via SMS. This token acts as the proof of ownership which enables the user to store registration information with textsecure. 

The client sends message authentication and encryption symmetric keys ('signaling' keys), and their long-term public key.

It also posts a collection of prekeys, which are one-time copies of the client's half of key negotiation when the client is a recipient. These stored prekeys allow a sender to carry out key negotiation without requiring the client be able to respond, reducing negotiation latency significantly. The client also uploads a "prekey of last resort" which is used last and is shared between all sessions until the recipient pushes new prekeys.

That signal doesn't warn the user about relying on a prekey that's been used by other clients is less than ideal, in my opinion. 

The client then registers with Google Cloud Messaging to get a registration ID to give textsecure. This registration with textsecure includes whether the client wants to receive SMS or only data.


- Phase 2: Key comparison


Textsecure allows for clients to compare the fingerprint of each other's long-term keys to verify each other's identity. It also includes support for displaying keys as QR codes to enable convenient comparison. 


- Phase 3.1: Sending an initial message


The sender starts by requesting a prekey for the recipient. They're given the prekey index, the prekey, the registration ID, and the long-term public key of the recipient. These are used to negotiate a shared secret through the HDKF key derivation algorithm. This is referred to as the root key.

An ephemeral keypair is generated for this message. The root key is used with HDKF to derive a new root key and a chaining key. This chaining key is what is used to generate encryption and MAC keys. 

Lastly, AES counters are initialized. There are two counters: ctr and pctr. The ctr counter is incremented with every sent message while the pctr counter holds the counter of the last message seen. This allows a recipient to enforce an ordering between messages received out of order.

These are used to encrypt the message for the recipient, which is send to the signal server. This message contains the information necessary for the recipient to complete the key negotiation handshake. 

The signal server will check that the Google Cloud Messenger registration ID is right for the phone number in question, and will encrypt the message with the 'signaling' keys before sending the message to the cloud server. This indirection ensures that Google Cloud Messenger does not see the message sender. 


- Phase 3.2: Receiving a message


The sender receives the prekey index and uses it to find the prekey used by the sender. It then uses the information sent to complete the handshake and to find the same root keys as the sender. These generate the keys used to decrypt the sent message.



- Phase 4: Sending a Follow-up Message



If the original sender wants to send a second message before the recipient replies, they generate a new chaining key and use this to find new encryption and message authentication keys.
- Phase 5: Sending a Reply


When the recipient wishes to reply they first choose a new ephemeral keypair. Using the sender's ephemeral public key, and their ephemeral private key, they generate a new shared secret. This is used to find a new chaining key to find new keys for encryption and authorization. This is used to encrypt the message, which is sent along with the new ephemeral public key.


Known Issues



Key Submission



TextSecure uses a shared secret between the TextSecure server and client, the machine-generated "pw", to authenticate upload of new prekeys. This is also used for authenticating sent messages. Leaking the password is then enough to allow someone to both send messages and upload keys on behalf of a user. The encrypted export function allowed a TextSecure client to move accounts between phones, but was removed because the export included the machine-generated password in it. This unencrypted backup was placed on the device's SD card, which meant that other apps on the phone could read it. 

This feature has since been removed. If you noticed it missing, it's not a usability bug. It's a conservative approach to a real problem. 


Unknown Key-Share Attack



This attack is one of forged delivery. If an attacker carries out a UKS attack, they trick someone into crafting a message for another person (the target) when they believe they are communicating with the attacker. 

This is easily done by a powerful attacker by replacing their own public key on the TextSecure server with the target's public key. They can do this by re-registering their number with TextSecure. They then can use QR codes to validate that their fingerprint matches what the sender has. This is the fingerprint of the target's key. 

Then, they must re-register the sender's account and intercept the validation SMS or phone call from reaching the sender. This is trivial to anybody with a permissive-enough warrant. They now can authenticate as the sender and pass along the signed message. 

This attack has not been fixed by TextSecure. They added signing of prekeys, but they are still not cryptographically associated with an identity. They may be passed-off and replayed due to this lack of association.  

A feasible fix would be to have the sender and recipient both mentioned in the encrypted body of the message. 

Goal Evaluation


TextSecure achieves forward security due to it's construction. Forward secrecy states that if long-lived public keys remain secure, that leakage of current symmetric keys forms a security breach which is active for a bounded amount of time. Since the public keys are required in each new ratchet, this is met.

Perfect forward secrecy is defined as the property that seizing the current keys had by a client won't allow an adversary from decrypting messages sent previously. This is enforced by the TextSecure wire protocol but it turns into a bit of a semantics game. Since keys are only stored on the devices, it is unlikely for a key to be disclosed without having access to other keys currently on the app. The long-term key isn't enough to decrypt a message without the short-term keys associated with the ratchet state, but these can be pulled from the phone and used to decrypt messages sent and not yet replied to (messages using the previous ratchet). This is disclosure of a "previous" message technically.

Deniability is much shaker. While it's possible to say that anybody could have created a given message, since the prekeys are published, the centralization of TextSecure poses a threat to that. The TextSecure server authenticates and forwards messages, and may log them. While the content is encrypted end-to-end, the metadata is not.

Sources


Analysis Whitepaper:
http://ieeexplore.ieee.org/document/7467371/


Marlinspike, Moxie (30 March 2016). "Signal on the outside, Signal on the inside". Open Whisper Systems. Retrieved 31 March 2016.

Sunday, October 9, 2016

Golem: Generic Trustless, Stateful P2P Application Backends



There is a saying that is often used as justification for the madness of kings. “Absolute power corrupts absolutely.” The costs of maintaining control pushes one to reason that one has a duty to extract every last bit of profitability or utility off of it. Rather than growing the kingdom and profiting from the established means of reward, a king may choose the local minima of exploiting those whom give him power in order to have a secure reward. Modern systems put absolute power in the hands of the person who owns a website. This is partially because it becomes necessary for the author of the website to provide computer hosting for the website. This is both a blessing and a curse.

With power comes the ability to find novel ways to profit from the system in ways outside of the site’s social contract. Even if the system only needs to save a few bits of information about each user to provide service, the system may need to see much more about the user in order to create the inserted data or to create an interface for the user. The user has no idea how much of their data is saved. If they consent to tracking, it tends to be a single opt-in which gives a blanket pardon for collecting all of this data.

On the negative side, power comes with the ability to harm without retribution. Through misrepresentation or denial of service, the server can decide which users should be ostracized. Major social networks are accused of selectively displaying certain kinds of information in order to engineer a worldview in their users. Users point at the identity representation that the application has and says “this is me,” while having no final say on what that representation holds. This is much like a King’s authority to edit the society’s stories to be more flattering.

All of this power comes at a cost. On the internet you may be a king, but someone with a warrant can compel you to use this power in their interests. The more popular your service becomes, the more likely it is that attackers will find any vulnerability you have. The legacy of kings is one of anxiety and bloodshed for a reason: nature abhors a power vacuum.

Golem: Trustless, Stateful P2P Application Backends


The problem of power centralization is caused by placing the duty of data storage and manipulation in the hands of the maintainer-owned server. The Internet at large has been trying to fix this through peer-to-peer systems since the days of Napster. We’ve never quite gotten it right though.

The core issue is one of abuse and data integrity. If anybody can control your database, it becomes impossible to ensure that a bad actor doesn’t remove all of your records and destroy your system. An easy answer is to use encryption to make sure that an updater “owns” the data to be inserted. This works for messaging and file-sharing systems. This is not sufficient in most systems because the data will typically hold semantics that constrain the values. It is the application code’s sequencing of updates that constrains data transitions.  

If the data-manipulating application code is allowed to run on the client machines, it becomes increasingly difficult to ensure that the requests made by the client are requests that are formed by the application. Furthermore, clients have a copy of the code to reverse-engineer and copy. This is the real motivation behind client-server web apps. If data-manipulating application code is run by the maintainer of the website, then they are in a position to be forced to eavesdrop or manipulate it.

What if somebody else ran the code responsible for validating and altering the database? It’s not intuitive why this would improve anything. This person would see the client’s intermediate sensitive data, could use it to generate an invalid data alteration, can reverse-engineer the code, and has less investment in correctness than a good user and a good maintainer.

The Golem project arose from a desire to counteract each of these problems through knowledge limitation, intimate accounting of state changes, pervasive rate-limiting, and cryptographically-validated identities.  

Saturday, October 1, 2016

Peercoin: Bitcoin without the Energy Bill




This week, we examine Peercoin. I'm not going to go into the threat model, because it has the same threat model as Bitcoin. It has a slightly different idea of what an "enemy" might be though.


In Bitcoin, we say that if an adversary has 51% of the mining power, then they win. The idea of one CPU giving you one vote is nice, but it ignores the fact that 51% of the mining power costs much less than 51% of the bitcoins would. Investing in mining gear suddenly looks profitable for a wealthy adversary. Peercoin wants to avoid this incentive by making the age of held coins determine the power of a vote.


Peercoin also intends to be more environmentally friendly than Bitcoin. Bitcoin mining has come to draw significant power. If Bitcoin had to mine the blocks to push the transaction volume of a large payment card processor, it would require immense banks of ASICs hashing guessing every day. We'd see centralization in mining power as it became more and more expensive to mine. These few actors would be playing the game of crypto lottery to coordinate together without trusting each other. Some would say this is at best a waste of electricity, and at worse that it undermines the goals of bitcoin.


Peercoin hopes to remove power and hardware as the consumed resource by making the external resource consumed into time itself. By relying on the stake of those holding coins in the network, Peercoin makes it expensive to act quickly and makes it difficult for any single identity to play too large a role in the system.


Coin Age


The idea of coin age has been known since the early days of Bitcoin. Coin age is a measurement of the amount of currency held, multiplied by the time since it was attained. Since a transaction consumes all of the input, sending the remainder back to the spender, this is akin to a measurement of the time since the coin was last changed.


An attacker who wants to acquire coins rapidly will likely have a problem with steadily acquiring coin age. To keep $1,000 in spendable coin age every day, you would need to acquire $1,000 in coin every day. You could only recycle the coin after it had aged 30 days, upon which the coin age is destroyed when it's used.


Coin age is truly the vote of the old money then. Those with the longest holdings of a coin are those who have the most investment in it's success, one reasons.


Proof of Stake via Coin Age


How does this coin age measurement allow one to implement a voting system for extending the blockchain?


Coin ages start being counted after the transaction making the coin amount is more than 30 days old. This has to do with checkpointing, as mentioned below. It allows nodes to deterministically agree on coin age through the checkpointing mechanism.


Peercoin has proof-of-work blocks, but most blocks won't be mined by proof-of-work. Proof-of-stake blocks will include a transaction in which the minter sends themselves their coins. These must have a coin age signifying they're greater than 30 days old.


Now this age goes into voting by acting as a "difficulty setting" for the hash target for a typical SHA-256, HashCash-style proof-of-work. This system allows someone spending more coin age to have the output of their hash-guess-lottery fall within a broader range and consider it success. This is probabilistically the same as giving the old money more lottery tickets for the same amount of money. After the work has been done, the worker needs to sign the block. This prevents the minter from using their same lowered difficulty to mine another block with the same parent. Nodes see the duplication and drop both, and the blockchain continues due to the signatures of honest nodes.


Peercoin further diverges from Bitcoin by creating a system which automatically scales the difficulty multiplier as the chain is built. In order to ensure that blocks are mined at an agreed-upon rate, the blocks contain a difficulty multiplier that can be adjusted. This continual changes allows the network to scale to sharp changes, in contrast with Bitcoin's periodic reassessments that can shock the mining economy.


Lastly, each transaction has a transaction fee which is destroyed. Furthermore, there are costs associated with everything that modifies the blockchain. This protects against attacks to fill the blockchain by making it expensive.


Minting Economics


Minting is perhaps much less lucrative in Peercoin. There is a 1% return annually on the amount of coin that someone puts toward minting. It's not even guaranteed to be a profit. If two people mint the same block in a given timeframe, the one with the most coin age will win. When a transaction stakes it's coins, they are locked for 520 block confirmations over 3-4 days. These minting coins can't be used for day-to-day transactions, they have to be set aside. Merging transactions, spending them, or doing anything really will cause coin age to reset to zero. Minting more frequently doesn't even get you more. If you mint every 30 days, you'll be expected to make the same amount as if you minted annually.


Minting, unlike Bitcoin mining, is not like striking gold. Minting is akin to taking in your cash every now and then and asking to have it "upgraded" to account for inflation. This keeps people invested in the system, and keeps the power out of the hands of any one group of people. Lastly, it makes it unprofitable for someone to make a run on the system by making it expensive to mine multiple blocks. This makes attacks more expensive than the Bitcoin network, as long as it remains expensive to buy most Peercoin.