Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

OnionCoin : peer-to-peer anonymous messaging with incentive system Gu, Tianri 2018

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2018_november_gu_tianri.pdf [ 2.02MB ]
JSON: 24-1.0371952.json
JSON-LD: 24-1.0371952-ld.json
RDF/XML (Pretty): 24-1.0371952-rdf.xml
RDF/JSON: 24-1.0371952-rdf.json
Turtle: 24-1.0371952-turtle.txt
N-Triples: 24-1.0371952-rdf-ntriples.txt
Original Record: 24-1.0371952-source.json
Full Text

Full Text

OnionCoin: Peer-to-Peer AnonymousMessaging with Incentive SystembyTianri GuA THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THEREQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2018c Tianri Gu, 2018iThe following individuals certify that they have read, and recommend to the Faculty of Graduate and Postdoctoral Studies for acceptance, a thesis/dissertation entitled:  OnionCoin: Peer-to-Peer Anonymous Messaging with Incentive System  submitted by Tianri Gu  in partial fulfillment of the requirements for the degree of Master of Science in Computer Science  Examining Committee: Mike Feeley Supervisor  Alan Wagner Supervisory Committee Member   Supervisory Committee Member  Additional Examiner     Additional Supervisory Committee Members:  Supervisory Committee Member  Supervisory Committee Member       AbstractThe "free-riders" issue happens in many peer-to-peer system, and this issueseverely damages the liveness of the system especially for the system that heav-ily relies on coordination of multiple peers. Many peer-to-peer system assumesthat the peers are willing to volunteer their resources to support functionality ofthe system, such as content storage and traffic relay. However, the assumptionis hardly true in real Internet world, in which most of the users are trying tomaximize their profit playing to take advantages from the system without pro-viding corresponding services to others in the system. The notable decentralizedanonymous network, TOR[1], also does not have any explicit incentives for thepeer to host Onion Router as infrastructures relaying secure traffics to protectthe other peers’ anonymity. Therefore, eventually the behaving users lose theirfaith in the system due to the unfairness, and the system may cease to properlyrun.OnionCoin(OC) is the first decentralized peer-to-peer anonymous messag-ing system based on Onion Routing with the integration of currency systemattempting to resolve such issues in Onion Routing based systems. A peer inOC will have to "pay" for using the anonymous messaging service, and will"gain" by helping other peers. The purpose of this currency system is to recordthe transactions of "pay" and "gain" in order to provide incentives for peers toparticipate more in the system. Several protocols are designed so that the in-troduction of the currency system does not compromise any existing protectionin Onion Routing on the anonymity of the communicating parties.iiiLay SummaryThis paper presents the design of an peer-to-peer anonymous messaging systemnamed OnionCoin(OC). In OC, for an user to send an anonymous message toanother, the message is going to passed through multiple other users till reachingthe final destination, so that the path of the message is hard to discover by theadversary. OC also provide a solution to resolve the "free-rider" issue in suchsystem by introducing a currency system. A "Coin" represents a token forservices. Any user will have to "pay" a Coin for the service to deliver its ownmessage, and every time a peer helps delivering the message from other peer,it gets "paid" anonymously with one Coin. As a result, every peer trades itscontribution to the community to earn Coins saved for future communicationand be able to communicate with anonymity.ivPrefaceThis dissertation is original, unpublished, independent work by the author,Tianri Gu.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1 Decentralized Identity Provider . . . . . . . . . . . . . . . . . . . 32.2 Roles and Duties . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Global Ledger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.4 Message Encoding Scheme . . . . . . . . . . . . . . . . . . . . . . 62.5 Routing Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.6 Threat Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.7 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Currency System: No Pay No Gain . . . . . . . . . . . . . . . . 93.1 CoSign Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 What Exactly is a Coin? . . . . . . . . . . . . . . . . . . . . . . . 103.3 Blind Signature Review . . . . . . . . . . . . . . . . . . . . . . . 113.4 Coin Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.5 Fail To Exchange Coin . . . . . . . . . . . . . . . . . . . . . . . . 144 Join and Discover . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.1 Register Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.2 Registration Failures . . . . . . . . . . . . . . . . . . . . . . . . . 174.3 Finding Peers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.4 Active Advertisement . . . . . . . . . . . . . . . . . . . . . . . . 184.5 Potential Threat on Peer Discovery . . . . . . . . . . . . . . . . . 185 Anonymous Message Delivery . . . . . . . . . . . . . . . . . . . . 195.1 Preparation Stage . . . . . . . . . . . . . . . . . . . . . . . . . . 205.2 Messaging Model Adjustment . . . . . . . . . . . . . . . . . . . . 205.3 Message Forwarding Protocol . . . . . . . . . . . . . . . . . . . . 245.4 Failure on Delivery . . . . . . . . . . . . . . . . . . . . . . . . . . 25vi6 The Ledger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266.1 Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266.1.1 Registration Record . . . . . . . . . . . . . . . . . . . . . 266.1.2 Coin Exchange Record . . . . . . . . . . . . . . . . . . . . 266.1.3 Coin Reward Record . . . . . . . . . . . . . . . . . . . . . 276.2 Bank Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276.3 Ledger Synchronization Protocol . . . . . . . . . . . . . . . . . . 286.4 Block Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.4.1 Proposing Stage . . . . . . . . . . . . . . . . . . . . . . . 306.4.2 Pushing Stage . . . . . . . . . . . . . . . . . . . . . . . . 316.4.3 Pulling Stage . . . . . . . . . . . . . . . . . . . . . . . . . 317 Threat Case Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 327.1 Passive Threat on Messaging . . . . . . . . . . . . . . . . . . . . 327.2 Single Malicious Node . . . . . . . . . . . . . . . . . . . . . . . . 327.3 Multiple Malicious Intermediate Nodes . . . . . . . . . . . . . . . 338 Cheating on Currency . . . . . . . . . . . . . . . . . . . . . . . . . 368.1 Forging Coins and Records . . . . . . . . . . . . . . . . . . . . . 368.2 Cheating Sender and Intermediate Node . . . . . . . . . . . . . . 389 Analysis of Encryption Steps . . . . . . . . . . . . . . . . . . . . . 399.1 Encryptions in OMSG . . . . . . . . . . . . . . . . . . . . . . . . 399.2 Encryptions in Protocols . . . . . . . . . . . . . . . . . . . . . . . 399.2.1 Signatures In The Records . . . . . . . . . . . . . . . . . 409.2.2 Onioned Messages . . . . . . . . . . . . . . . . . . . . . . 409.2.3 Blind Signature . . . . . . . . . . . . . . . . . . . . . . . . 409.3 Analysis Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 419.3.1 Extra Cost in Coin Exchange . . . . . . . . . . . . . . . . 419.3.2 Extra Cost in Messaging . . . . . . . . . . . . . . . . . . . 4210 Prototype Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 4310.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4310.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4310.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4811 Limitation and Future Work . . . . . . . . . . . . . . . . . . . . . 5111.1 Unidirectional Message . . . . . . . . . . . . . . . . . . . . . . . . 5111.2 Delivery Failure Detection . . . . . . . . . . . . . . . . . . . . . . 5111.3 Performance as of a Messaging System . . . . . . . . . . . . . . . 5211.4 Re-usability of a Coin . . . . . . . . . . . . . . . . . . . . . . . . 5211.5 Features in Future Work . . . . . . . . . . . . . . . . . . . . . . . 5312 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5413 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56viiBibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57viiiList of Tables1 The probabilities that an adversary can forge Coins . . . . . . . 372 Number of Messages and Encryption Steps Summary for CoinExchange in OC compare with NACE . . . . . . . . . . . . . . . 413 Number of Messages and Encryption Steps Summary for a Mes-sage Delivery through L intermediate nodes compared with TOR 42ixList of Figures1 Roles Switches in OC with 5 Nodes and 2 as Bank . . . . . . . . 52 OMSG General Format . . . . . . . . . . . . . . . . . . . . . . . 53 CoSign Protocol with NC = 3 . . . . . . . . . . . . . . . . . . . . 104 Content of a Coin . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Coin Exchange Protocol with NC = 3 . . . . . . . . . . . . . . . 126 Register Protocol with NC = 3 . . . . . . . . . . . . . . . . . . . 167 Message Delivery from S to R through 2 intermediate nodes . . . 198 Message Delivery from S to R through 2 intermediate nodes withCoins "paid-in-advance" . . . . . . . . . . . . . . . . . . . . . . . 219 Message Delivery from S to R through 2 intermediate nodes withCoins "paid-afterward" . . . . . . . . . . . . . . . . . . . . . . . . 2210 Message Delivery from S to R through 2 intermediate nodes withCoins "paid-afterward" and Feedbacks . . . . . . . . . . . . . . . 2311 Ledger Synchronization with d0 = 3 and d1 = 5 . . . . . . . . . . 2912 Number of Messages To Deliver 1000 message as Number ofCoSigners changes . . . . . . . . . . . . . . . . . . . . . . . . . . 4413 Number of Encryptions To Deliver 1000 message as Number ofCoSigners changes . . . . . . . . . . . . . . . . . . . . . . . . . . 4514 Number of Messages To Deliver 1000 message as length of Epochchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4615 Number of Encryptions To Deliver 1000 message as length ofEpoch changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4716 Number of Messages To Deliver 1000 message as Number ofBanks changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4817 Number of Encryptions To Deliver 1000 message as Number ofBanks changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49xAcknowledgementI offer my sincere gratitude to the faulty of Computer Science, staff and mybrilliant peers, who have inspired me to continue my study in Computer Science.Also, thanks to my graduated friends on providing precious suggestions.I owe my particular thanks to Dr. Mike Feeley, whose wisdom and guidancehad greatly helped me on the path of becoming a better researcher and criticalthinker in the field of Distributed Systems design. It was always a wonderfulmemory when discussing the ideas and thoughts in your office on the third floorat ICICS.xiDedicationTo my beloved ones.xii1 IntroductionThe significance of anonymous communication system is getting more attentionfor its capability on protecting the identity of the communication parties underthe pervasive network traffics monitoring. Many researchers have proposed dif-ferent approaches designing application level anonymous communication overlaynetwork to protect user’s anonymity. Majority of these [3, 19, 16] are based onthe centralized server or a group of servers as the proxy to provide covers fortheir users. Although many of these system can provide strong guarantee onanonymity, they are relatively more vulnerable to be attacked on the availabilitysuch as Denial-of-Service(DoS) compared to the systems with more decentral-ized designs such as TOR [1], instead simply shutting down these messagingservers would prevent the anonymous communication from happening. Whenthe servers are distributed across the globe, it makes the attack on availabil-ity much more difficult to perform but are only able to monitor the traffics atbest effort to try to expose the connection among some of the suspecting users.Therefore, for practical use, decentralized anonymous systems are more stablechoice despite they might not provide such strong protection on security due totheir distributed design.TOR[1], as one of the most famous and infamous decentralized anonymousnetworks, has proved its guarantees on anonymity is sufficient for multi-purposediscrete communication at geo-distributed scale. However, in TOR, it requiresmany users to volunteer for hosting Onion Router as traffic relay to help re-directthe other TOR traffic in order to provide cover for the communication ends. Insuch peer-to-peer style system, the incentives for the user to volunteer providingfree help can be questionable. In the original TOR paper, the authors state thathosting an Onion Router would provide better protection on anonymity. As anOnion Router, there will be foreign TOR traffic in and out, which could behaveas the cover traffic when the host is sending secure messages, thus the adversarywould require more resources to capture suspicious behavior of the Onion Routerhost. Nevertheless, this type of incentives may also attract more attention fromthe adversary than the other users that only use TOR as proxies. Also, in theaspect of resource consumption, the user hosting Onion Routing would definitelyconsume some resources on helping other users rather than saving the resourcesfor itself. This encourages the "free-riders" behavior in TOR for there is noregulation on how much resource an user can consume on the public OnionRouter. Is it possible to introduce fairness to anonymous messaging systembased on Onion Routing while still remain its guarantee on anonymity?In this paper, a peer-to-peer anonymous messaging system combined with acurrency system named OnionCoin(OC) is designed to answer this question.In OC, no peer is "free" to use the system for anonymous message delivery, buthave to spend some currency as a proof of providing services for the communityin the past. Each time a user provides help for the other peers would grant itwith a token for messaging service in the future. The currency system is to storesuch transaction records and provides the proof of this help. The records aredesigned so that the communication related to these records will remain anony-1mous. The goal of OC is to add an incentive system on top of Onion Routingbased messaging system without introducing additional security concerns. Thefollowing sections start with the general view of OC, and systematic assump-tions. Then each part of the system is discussed in details stating how variousconsistency and security needs are met to keep the communication anonymous.Afterwards, the paper discusses several cases regarding the attacks on OC andpossible cheating behaviors to the currency, and how these cases are handledwith anonymity protected.22 System OverviewOnionCoin(OC) is an application level P2P overlay network designed to provideanonymous messaging service in decentralized design and no other external ser-vices are required except utility services such as DNS. Each OC node is actingboth as a client using messaging service and a server handing requests fromother OC nodes. The anonymous communication is achieved by encrypting themessage in layers and re-directing multiple times through other OC nodes tillreaching the destination like the ones in TOR[1] and Tarzan[2]. Whenever aforwarding node helps delivered a message to next node, it would get paid witha reward Coin from the sender to honor its help. The information regardingthe currency transactions are recorded in the global Ledger. Every transactionrequires being digitally signed by certain numbers(NC) of authorized nodes tobe considered as a valid transaction record. This section will give a generalpicture of components in OC and how they are connected together to provideincentives for the nodes making contribution to the community.2.1 Decentralized Identity ProviderEvery currency system would require an identity system to link the ownership ofcurrency to users. Many crypto-currency systems [42, 43, 44] use public key asthe identity of the user based on the security guarantee that it is computationallyhard to find the corresponding private key, so that the id of a user is hard tobe imitated. Yet, there is no public records indicating which users are using thesystem nor which public keys are involved. In OC, this kind of identity provideris not enough since the identities of users need to be verifiable by other usersin the system in some operations. Therefore, OC itself is a standalone identityprovider to satisfy the identity authentication requirements among nodes so thatno third-party Certificate Authority is required to authenticate, which makesOC is pruned to the CA-related attacks. In OC, every operational message ispublic-key encrypted and therefore the public key information of all the membersare publicly accessible. Each node Ni in the system must be identified by itsregistered public key PKi recorded on the global Ledger, and each node willsign with the same corresponding secret key SKi. The record also includes theunique ID of the node, which could be the domain name or simply a string. Theidentity authentication can simply be performed by any nodes in the system bychecking the presence of the corresponding public key record in the Ledger. Theverification of the identity of an OC node can be done by validating its digitalsignature in the operational messages exchanged in various situation.2.2 Roles and DutiesIn OC, the publication of every currency-related transaction requires the ap-provals from multiple authorized OC nodes to prevent cheating behaviors suchas forging transactions. The authority however, should not stay as the samegroup of nodes since the corruption may happen. Instead of granting some Su-3per/Leader nodes constantly present privilege over the others all the time, inOC, there are frequent leadership exchanges. A different subsets of nodes areselected as leaders in different time interval, so that no fixed group of nodeswould stay as the authority at the time.There are two Roles that all nodes are expected to play over time with likelyequal possibility, Normal node or Bank node. The time line in OC will bedivided into small equal-length time intervals named epoch, and in each epoch,there are certain number of nodes are selected to be the Bank Nodes, and therest of nodes remain Normal Nodes. The number of Bank Nodes(NB) is asystem parameter configured at boot time of OC. As a Bank node, its primaryduty is to perform the Ledger-related operations such as Coin Exchange andIdentity Registration, which will generate transaction records appended ontothe Ledger indicating the record is published. Each time a record is successfullypublished, the corresponding signing Bank Nodes are rewarded with one Coin asincentives. To perform any such operations, the Bank node must have the lateststable version of the Ledger acquired from the set of Bank nodes in previousepoch. At any point of time, the majority of nodes in OC are playing as NormalNodes who are able to send anonymous messages or help the other Normal Nodesforwarding their messages, but has no authority to modify the Ledger. In thefollowing sections, the Bank nodes will be named as Bank or Bi, and node orNi for the non-bank nodes for simplicity.The Bank Selection Algorithm(Section 6.2) is meant to be randomand dynamic but also globally verifiable by any nodes. In each epoch, thetotal number of Banks selected are expected to be unchanged until there aresignificant changes in total number(NN) of nodes in system. Consider Figure 1,which shows an example OC system with total 5 nodes and 2 of them are selectedas Banks. In this example, the time starts at epoch e0 moving towards e4 anddifferent nodes are picked as Banks in different epoch. For example, in epoche0, B0 and B2 are chosen, and in e2, B2 and B3 are Banks. Notice that thereis no restriction on re-selection in consecutive epochs.2.3 Global LedgerThe currency system in OC relies on the transaction records stored in the globalLedger. Like the other BlockChain-based peer-to-peer systems [42, 43, 44], thepurpose of the global Ledger(BlockChain) is to provide the consistency of thecurrency to prevent and detect the double-spending problem. However, in OC,the way of recording currency transactions are different due to the anonymity re-quirements that the trace of currency should not reveal any identity information.The only unit of currency in OC is Coin. Each Coin has its static ownershipunder one of registered identity in OC and can be only spent(exchanged) by itsowner. A Coin also has an integer coin number to distinguish from other Coinsthat has the same ownership. Each Coin spent(exchanged) will be recorded inthe Ledger with the owner’s ID and the coin number to mark the Coin as usedto prevent the same Coin spent twice.In general, every node, regardless Normal or Bank, is expected to store a4Figure 1: Roles Switches in OC with 5 Nodes and 2 as BankFigure 2: OMSG General Formatlocal version of global ledger in order to perform some Ledger-related operationssuch as Bank Selection, signature verification, and Coin verification. Thereare three possible types of transaction records that could appear in the globalLedger, Registration Record(RR), Coin Exchange Record(CE), andCoin Reward Record(CR). Upon the generation of each transaction record,it requires certain number of Banks to sign the record. These signing Banks arenamed CoSigners. Registration Record will be generated when a new peeris joining the system, including peer’s public key and its unique ID in OC. CoinExchange Record is generated each time a peer exchanges an existing validCoin to a new Coin which can be used to pay for the other peers. For everyCoin Exchange, each recorded CoSigner is rewarded with one unit of Coin andcan be redeemed through a Coin Reward Record. For example, 3 of BankNodes signs a Coin Exchange Record for a Coin, then later each of them canredeem a new Coin from this transaction. Coin Reward Record can be seen asan update operation to the Ledger.52.4 Message Encoding SchemeIn OC, most of operations require identity check on purposes of either verifyingthat the user has right to perform the operation, or simply identifying whichuser is requesting the services. Therefore, all operational messages are secure bydefault for which every message are digitally signed by the sender and encryptedby the receiver. Every operational message is meant to be only readable by itsdesignated receiver and the identity of the sender of the message is verifiableif the sender is registered in the system beforehand. During any messages ex-change, the message will be encrypted and encoding in a designated way andsuch formated messages will be referred as OMSG(Figure 2) in the followingsections.Every OMSG has five sections including OPCODE, SENDERID, TS,HASHSIG, and PAYLOAD. OPCODE indicates the purpose of the mes-sage and its expected operation such as REGISTER for new node registrationand FWD for message forwarding. SENDERID indicates the ID of the sourceof the message, however, which may not be the originator of this message sincethe message could be relayed. HASHSIG is the sender’s digital signature onthe sha-256 sum of the PAYLOAD to detect the possible tamper or corruptionof the message. PAYLOAD includes functional part of data in different oper-ations. After preparing all these information of OMSG, the sender encrypts theentire OMSG with AES first, then encrypts the 256-bit AES key with receiver’spublic key, and attached the encrypted AES key to the front of the messagebefore sending this OMSG.Upon receiving an OMSG, the receiver first decrypts the encrypted AESkey with its private key. If the decrypted OMSG is ill-formated, then discardsthe OMSG. Otherwise it then decrypts the OMSG with decrypted AES key toretrieve the five sections of this OMSG. The integrity of the data can be checkedby comparing the HASHSIG against the PAYLOAD with sender’s publickey, and this also verifies the identity of the sender. Afterwards, the receivercan start perform requested operation indicated by the OPCODE from themessage.2.5 Routing TableThe nodes in OC will all be expected to listen on UDP at OC’s port(1338)for any incoming communication. Due to there will be public key encryptionscheme to verify the identity of communicating nodes, all UDP traffic will beaccepted and then decoded and decrypted if possible. Whenever identity of thesender of an incoming message can be successfully verified as one of the nodesin OC, the IP address associated with this sender will be inserted or updatedin the local Routing Table. Primarily, the entries in Routing Table are <ID,IP> pairs with an approximate Time-to-Live indicating the freshness of thisentry. Since the id of any user is globally unique and can be verified duringeach communication, it can be used solely to map to its IP address. In currentversion of OC, it is assumed that no nodes can concurrently have multiple IPs6for communication, but the IP of any node can frequently be changing in thedynamic network environment. The mechanism regarding peer discover androuting information advertising will be discussed in later sections.2.6 Threat ModelTo achieve anonymity in message delivery, it means that the adversary cannotnot guess which pair of honest nodes are communicating with significantly higherprobability than any other irrelevant node pairs. In order for adversaries toprovide solid proofs regarding their guesses, either the meta-data of the completechain of communication between suspecting ends, or the content that directlyindicating the communication facts with provable digital signatures, are requiredto be used to as the proof of compromising the anonymity. The adversaries havethe capability to inspect, tamper, tag, and drop the datagram in any partof the communication. Moreover, the adversaries may also present as some ofOC nodes pretending as honest users providing re-directing service and/or serveas Bank Node to access and modify the content of the global ledger.For any instance of communication, when all the nodes on the communica-tion path have been compromised or monitored on the same time, a firm linkagecan be made between the sender and receiver. Therefore, we assume that atleast one node on the communication path is not colluding with the other nodeson the path. Due to single path of communication, any tampering or droppingon the datagram probably will stop the message reaching the destination or end-ing up being delivered to the wrong destination. However, this will not exposethe identity of the receiver, therefore also protecting sender’s anonymity. As forother nodes that are not controlled by adversary, it is also assumed that thenodes will act rationally, which means they will not deviate from the protocolif there is no potential earning additional Coins. In other words, all nodes areassumed to be untrusted and greedy, but will not intervene other nodes withoutany benefits.As for the other operations such as currency transactions and user registra-tion, we assume that the adversary cannot compromise more than half of totalnumber of Banks in the same epoch, and no user can register multiple times inOC including the adversary. The registration abuse could cause OC vulnerableto Sybil style attacks [39] since OC’s consensus relies on the number of nodesinvolved. Additionally, it is assumed that when a new user wants to join OC, itcan always find at least one honest Bank node to join.2.7 ChallengesThe one of the greatest challenges to design such a system like OC is to resolvethe conflict between a anonymous messaging system and a currency system.As an anonymous messaging system, the connection between communicatingparties should not be revealed by any other nodes, yet in a currency system,normally, the information regarding the exchange of ownership of currency suchas the previous ownership, new ownership and the amount of currency should7be visible to the public. Therefore, when sender is trying to pay the forwardingnodes, such currency transactions should be carefully designed so that theywould not reflect the path of communication that the sender chooses. In otherwords, this challenge can be split into multiple small guarantees: (1) the validityof Coins can be verified by any node, (2) the Banks can not know the ids ofpayees and (3) the forwarding nodes can not know the id of payer while still beable to get paid. There are also other challenges related to the currency system,such as (4) the Coins cannot be forged, (5) the record cannot be forged, and (6)the Ledger contains same records in every node’s copy. The following sectionsare structured to describe how OC handles these challenges in order.83 Currency System: No Pay No GainIn any kind of p2p system, the "free-rider" issues is always severe, which signif-icantly degrades the performance and liveness of the system and brings psycho-logical damage to the honest peers due to the unfairness. To address such issue,OC adopts the currency system, which will enforce peers to "produce" the helpsbefore "consume" the messaging service. To "produce", in one way it simplymeans a node needs to remain public and open to incoming OC traffic and helpre-directing the message received from other peers with the intention to sendanonymous message. On the other hand, when a node is selected as a BankNode for current epoch, it can "produce" by helping with Normal Nodes whichare planning to perform Coin Exchange or New Peer Registration to finish theCoSign Protocol (Section 3.1). Each signature gathered within any recordswill become a valid unit currency as rewards for the CoSigners. To "consume"the service, it only means the node is planning to send an anonymous messagethrough multiple peers towards the final destination. For each intermediatenodes on the communication path, the sender should include a Coin as rewardsfor the "producing" peers along with the message.All of the records of both "produce" and "consume" of course will be recordedinto the global ledger in order to provide certain level of consistency of overallcurrency volume and to ensure the fairness which is crucial to encourage peers tobehave honestly. However, unlike the other crypto-currency system, OC doesallow some degree of double-spending to occur in trade of performance andefficiency, and the details will be discussed in the later section. Also, unlikeother crypto-currency system, OC is primarily a messaging system and thecurrency is auxiliary, which means the strong consistency in currency controlis not necessary as long as the cheating behaviors are bounded within certaintolerable range to provide sense of fairness. The following sections will describethe definition of the Coin, and the protocols to exchange an old Coin into a newone with related techniques and operations.3.1 CoSign ProtocolFor each record to be added into the ledger, it requires sufficient number ofthe signatures from distinct Banks selected in the same epoch. This protocol isknown as the action of CoSign. The minimum number of signatures requiredis equal to the Number of CoSigners(NC), which is a parameter of OCconfigured at system’s boot time. When performing CoSign Protocol, eachBank will sign the hash of the content in record which varies based on the typeof records, and then appends its ID along with the signature to the back of therecord.For example, considering Figure 3, assume NC=3, and the Banks are pub-lishing a record with CONTENT. B2 is the first Bank receives the CoSignrequest, then it generate its signature on the hash of CONTENT and appendit to the back of the record as sigB2 with the counter incremented to 1. ThenB1 passes this record to B0, and B0 does the same procedure to add sigB0 and9Figure 3: CoSign Protocol with NC = 3increment the counter to 2. Finally, when B1 receives the record, after it addssigB1 to the record, the counter is incremented till it equals to NC. B1 then sortsthe signatures and Bank ids and generate the sha-256 sum of the CONTENTconcatenated with signatures and ids as the identifier of this record, which inthis example the hash is "6D022EB93CFB20C4775923...". At this point,B1 stores this new record locally and waits for the Ledger Synchronization inthe future to make it public.3.2 What Exactly is a Coin?All the currency in OC has single type of unit as Coin, and each time both"produce" and "consume" will also be exactly one Coin. Each Coin is onlyspendable by its owner, yet each Coin’s owner can exchange its Coins with thesame amount of Coins with different IDs in order to pay the helping peers. Coinscan only be published with the approval from multiple Banks. Such operationis known as Coin Exchange. Before the Banks can generate a Coin, a Raw Coinis created by a requesting Normal Node with desired ownership and a randomunused coin number, consider the left part in Fig 4. Then the Raw Coin is splitevenly into multiple pieces with total number of pieces equal to NC. A Coinessentially is a piece of data as a result of concatenation of all pieces of the RawCoin with each piece signed by a distinct Bank. For example, in Figure 4, aCoin CN0 is created by Banks whose IDs are B0, B1 and B2. The content ofCN0 is shown in the right part of the figure, where SKi is the private key of Bi,and "03402991" is random integer generated as the Coin number for CN0 . Also,the ids of CoSigners and the epoch number are included in the Coin for ease ofverification, and this information is not encrypted.10Figure 4: Content of a CoinThe verification of a Coin Cid owned by Nid published by Banks Bi comeswith two steps. First, retrieve the ids of CoSigners and the epoch number ei.Then check if all the CoSigners are registered in the system and if all of themare selected as Banks within epoch ei. If either the condition fails, then Cid cannot be a valid Coin. Second, decrypt each piece of encrypted RCi with SKBito get plain RCi. Then concatenate all RCis and check if it contains the "id"and this "id" matches the presenter of Cid. If the ids are matched, then checkif the Coin Number exists in the Ledger with the same ownership. If the Coinnumber exists, it means this Cid has been redeemed before, so Cid is no longervalid. When both steps succeed, Cid is considered to be a valid Coin owned byNid.3.3 Blind Signature ReviewBlind Signature scheme designed by David Chaum [40], is used to hide contentof the message from the signer, yet still be able to get the signature by the signeron the message. To "blindly" sign a message m by S, m is firstly "blinded" bya blind factor BF recorded by blinder B. With the "blinded" message Blind(m,BF), S is not able to decipher Blind(m, BF) and view the content of m. ThenS normally signs Blind(m, BF) by S’s private key to get privEnc(Blind(m, BF),SKS). Then BF can be removed by B and produce privEnc(m, SKS) which ismessage m signed by S.With the attribute of using Blind Signature scheme, one can provide discreteinformation to the authority to get signed without worry the exposure of thecontent of the information to the authority. Particularly in OC, although thereare no central authorities, the Bank Nodes are responsible to act like temporaryauthorities signing the information provided by the Normal Nodes. One crucialstep in Coin Exchange Protocol is that a Bank needs to sign on the data ofthe new Coin provided by a requester Node, and this information should not be11Figure 5: Coin Exchange Protocol with NC = 3visible to any Banks, since the content of the Coin reflects its ownership. Theusage of a Coin in OC is only to pay the intermediate nodes during messagedelivery, and hence if the identities of the owners of these exchanged Coins areknown by a node Bi, a future communication path which has to be the combi-nation of the owners of these Coins can be easily determined by Bi. Therefore,when a node exchanges a Coin with Bank, the information of the new ownerof the Coin is firstly being "blinded" using Blind Signature, so that the Bankcannot log the id of the new owner of the Coin, but also be able to sign on thenew Coin.3.4 Coin ExchangeThe Coin Exchange operation is the core operation of the currency exchange inOC, which will transform an old Coin into a new Coin with possibly differentownership from the old Coin’s ownership without exposing detailed informationon ownership exchange to the other nodes in the system. In general, by per-forming Coin Exchange, a node N0 is able to exchange a valid Coin Cold_n0into a new Coin Cnew_n0 with the approvals from B0, B1 ... BN , where the id"old" may or may not be the same as the id "new" and N equals (NC - 1), anda new CE record containing Cold_n0 is generated. The overall procedures whenperforming an instance of Coin Exchange can be split into two protocols, CoinExchange Protocol and Coin CoSign Protocol, and they could happenconcurrently. For example, considering Fig 5, N0 wants to exchange Cold==N0into CN1 with NC = 3. N0 initiates with Coin Exchange Protocol, and the stepsare:1. N0 picks a new Coin number CNnew(80903991) that is not appeared on12the Ledger, and generates a Raw Coin RC with expected ownership asN1.2. N0 splits RC into 3 pieces and blinds each RCi with blind factor BFi toget Blind(RC0, BF0), Blind(RC1, BF1), and Blind(RC2, BF2).3. N0 sends a Coin Exchange request to Bi with PAYLOAD as [Blind(RCi,BFi):CN0].4. Bi receives this request, and then verifies Cold. If invalid, abort. OtherwiseBi signs Blind(RCi, BFi) to produce privEnc(Blind(RCi, BFi), SKi).5. Bi replies to N0 with privEnc(Blind(RCi, BFi), SKi), and then Bi canoptionally starts Coin CoSign Protocol.6. N0 unblinds privEnc(Blind(RCi, BFi), SKi) withBFi and retrieve privEnc(RCi,SKi).7. N0 continues from (3)-(6) till all RCi has been signed by distinct Bi, andthen N0 can produce CN1 .During the Coin Exchange, at any point after step (4), when a Bi receives avalid Coin in the Coin Exchange request, Bi can start to perform Coin CoSignProtocol to attempt to generate a new CE. The Coin CoSign Protocol describedbelow is also applied to CoSign Protocol in other occasion(Fig 3 with the dif-ferent content only.1. B0 signs the hash of Coin Cold to produce privEnc(Cold, SK0).2. B0 sends [counter:Cold:B0:privEnc(Cold, SK0)] to another Bank B1, wherecounter indicates how many signatures have acquired.3. B1 repeats (1) and (2) till counter reaches NC, and a new CE record isproduced.Since any node can start CoSign Protocol whenever receiving valid Coins,the Banks are actually competing with each other to get their signatures on thenew records. Even though, more than enough number of Banks may involveand there could be multiple versions of the same record, this competitive envi-ronment encourages the Banks to generate the new records as soon as possibleto try to get the rewards from the new records. Moreover, this intended compe-tition helps prevent the cheating groups of Bank Nodes from getting unlimitedrewards from collusion, because now the other honest Banks are also tryingto produce the records and when the number of honest Banks are greater, thepossibility of forging records is lowered.133.5 Fail To Exchange CoinThe Coin Exchange operation of changing Cold to Cnew can be considered astwo separate parts, one from N0’s aspect and the other from the Banks. ForN0, the success of a Coin Exchange is to get a valid Cnew from any of Banks,and yet whether Cold is marked as used should not be concerned. When N0fails to get Cnew, the following incidents could be happening. First, there is notenough number of Banks currently available in the current epoch. Second, thesignatures gathered from one or more Banks are not correct. Third, one or moresignatures gathered are not from current set of Banks. To address the secondand third occasion, N0 can resend the incorrectly signed RCi to different Banksto get correct signatures, which however may also fail due to insufficient numberof other Banks. The first occasion seems to be solvable by simply waiting foranother epoch to re-try the same exchange, but there could be the case that Coldhas already been marked as used when the first time proposed. This problemis also the one of limitations in OC, which will be described in Section 11.As from Banks’ point of view, the failure would be unable to generate anew RR containing Cold to get rewards from. This failure is also applied tothe other CoSign scenarios when new valid records cannot be generated. Thecases could be insufficient number of available Banks, one or more ill-behavingBanks, or the information loss during the Ledger synchronization. For thefirst occasion, there is no feasible solution, the operation will have to abort.Waiting for another epoch to re-try may not solve the problem since differentset of Banks are selected. To address the second problem, one can re-try gettingthe signatures from other available Banks till correct and enough signatures arecollected. The solution to the third problem is categorized as the failure inLedger synchronization and will be discussed in later section.144 Join and DiscoverTo be able to use the services in OC, the first step would be finding the peers toperform corresponding operations, and being visible to the public is importantas well. To become a member of OC, a registration is always required. Theonly indication for a node N0 becoming a legitimate member is the presence ofa valid RR contains N0 and PKN0 in the Ledger. PKN0 is the only identifierto distinguish N0 from other nodes in OC, and the string id N0 is only thepurpose of human-readability. Also, no user can have more than one id in OCas stated in the Threat Model. The IP address cannot be used to identify auser in OC due to two reasons. First, in the dynamic network environment,a static IP address is not practical and OC will not make such assumption byusing end-to-end verification using public key. Second, like the suggestion inTOR, it is always a good idea to use additional VPN for better protection.With VPN, the IP address is certainly not the original one. Therefore, OC usesgossip style protocols to spreads the routing information of different nodes tothe entire network.Before a user can use OC’s service, a registration is always required since theidentity verification of a user is crucial in currency related operations. When auser is trying to find some peers in OC, the ids of the targets are required in thequery to peers. In this section, the procedures of joining OC and finding peers inOC are described. OC is designed to only provide service for registered members,and the identities of all members are publicly available to all of the peers. Inorder to join OC, a new peer will have to generate a new public/private keypair, and pick an unused ID in OC. Then the new peer can forward the requestto any one of the Banks in the current epoch, and then wait for the Banks topublish a corresponding RR with new peer’s public key and ID chosen. Thenumber of Banks required to help new peer finishing the Register Protocol is atleast NC. For the following sections, we will assume that the new peer will joinon one of the honest Bank Nodes and the first round of new peer’s informationwill not be intentionally tampered by the adversary, and also the new peer canpick a new unique ID locally without contacting any nodes in OC.4.1 Register ProtocolThe Register Protocol is mandatory for any user who wants to use OC’s service,the success of a registration is marked by having a corresponding RR in theLedger. When joining the system, we assume in this paper that the new peerwill always be able to find an honest Bank to finish the Join Protocol. However,this will not be true in the real untrusted network environment, and the solutionregarding how to find the trusted node at the first place will not be addressedin this paper. Even though in OC every OMSG is encrypted with public key,some messages in the Register Protocol can not be encrypted since there is notyet registered public key for the new user Nnew. For Nnew to join the systemwith NC = 3, Nnew requires 3 Banks to help publishing RR through CoSignProtocol. To begin the Register Protocol, considering Fig 6, the steps are as15Figure 6: Register Protocol with NC = 3following:1. Nnew first generates public/private key pair PKnew. Then along with theidnew, Nnew sends a REGISTER request to the one of the Banks, in thisexample, B0.2. UponB0 receives PKnew and idnew fromNnew with opcodeREGISTER,B0 retrieves PKN and check if there is same public key entry registeredin the system by verify the existence of it in the Ledger. If idnew is notregistered, then B0 signs on the hash of PKnew and idnew.3. B0 forwards Nnew’s information appended with B0’s signature to one ofthe other Banks, B2.4. When B2 receives such message, it first verifies the signature of B0, andif the signature is valid, B2 also signs on the hash of Nnew’s informationand append the signatures to the back of message, then pass along to oneof the other Banks.5. As soon as enough signatures have been gathered, the last Bank, in thisexample, B1, generates a RR and stores it locally. Then B1 can alsonotify the completion of the Register Protocol to Nnew.Nnew, at the point receiving the notification from B1, is however not con-sidered as fully registered since the RR with id Nnew may not be published yetand no other nodes can see the fact that Nnew has joined the system. Nnew inthis case, will have to wait until current epoch passes and all the records fromB1 are made publicly visible(appended to the Ledger). Then Nnew’s public16key and ID are verifiable by any other nodes in OC for future communication.Therefore, the notification sent by B1 is optional and only for the purpose toshow Nnew that the REGISTER request has been processed. After Nnew’s RRis generated, B1 will send some of its routing information to Nnew to help Nnewfinding more peers in the system.4.2 Registration FailuresThe failure situation could be happening when there is not enough Banks helpingto sign theRR with Nnew’s information orNnew’s public key and ID values havebeen already registered previously. To handle the first failure case, Nnew willhave to either retry the Register Protocol from beginning in a different epoch.To deal with the latter, Nnew will have to generate a new public/private key pairand/or picks a different ID, then restart the Register Protocol. The other failurecases could be when one or more signing Banks tampered the information aboutNnew. Therefore, the information although can be published successfully, maynot be originated from Nnew. In this case, if only the idnew is modified, the newpeer can choose to use this ID, since the public/private key pair information isstill unregistered. However, if the public key has been tampered, the privatekey that Nnew has is no longer useful in any sense. As a result, Nnew will haveto generate a new key pair and restart the Register Protocol in latter case.4.3 Finding PeersThe overlays network in OC is considered as unstructured due to the churn ofpeers is expected to be high, in which structured routing techniques are rela-tively not efficient and scalable such as DHTs [45, 46, 47]. Also, in such struc-tured overlays network, if no proper modification to keep routing informationprivate, the anonymity of communication may be revealed by checking whichrouting information are queried in the history. In OC, the method to aggregateand maintain routing information of other peers is gossip based, in which theinformation may not be very accurate at runtime, but can be spread efficiently.Also, a node can send query for specific node by its id or public key.In general, there are two ways getting more routing information of otherpeers in the system. First, send a LOOKUP query to one or more nodes in theRouting Table asking for recent updates of the entries in their Routing Table.This kind of lookup however should be used with caution if the node is suspectedby the adversary. Second, every node is expected to broadcast a subset of allrouting information including its own information it has to multiple nodes inthe system. The subset should be chosen randomly to ensure every one hasequal probability to be reached for operations. In both methods, the routinginformation should always include the recent updates to Time-to-Live values formore accurate planning for communication. However, the incentive for a nodeto provide routing information to other peers is not directly related to currencyearnings, but to make its presence and approximate duration of up-time knownto the other parts of system.174.4 Active AdvertisementWhen a registered peer whose information has been recorded as RR in theLedger, it no long needs to go through Register Protocol. However, especiallyfor a peer gone off-line for a long period, its information regarding the routingis probably outdated. Each time when a registered node is coming back on-line to OC, this node can optionally choose to "advertise" its presence with thepurpose of providing the possible updated IP address. The procedure is simplyproviding the current IP address and the expected Time-to-Live to the nodes inits Routing Table. This procedure is typically recommended for the nodes whichplan to present as a forwarding node to earn Coins, since actively "advertising"would provide accurate IP information more quickly comparing to waiting tobe queried directly or indirectly.Moreover, this procedure can also be used for probing. As described inthe previous section, after Nnew receives the notification from B1 indicatingthe success of generating the new RR, Nnew is still not fully registered. Nnewhowever cannot checking its status by viewing the Ledger since query for Blocksis also an operation using OMSG which requires public key encryption. Withthis "advertisement", Nnew can periodically probe with any known nodes inthe system to check whether the id Nnew has been added to the Ledger sinceif it has not, Nnew would receive negative responses since the signature in themessage Nnew sent cannot verified. This action is also used when a heartbeat isrequired to ensure the target node is current on-line. However, this heartbeatshould be used with caution, since this action may expose the communicationplan when probing the forwarding nodes.4.5 Potential Threat on Peer DiscoveryIt is a general concern regarding the potential attacks on the peer discovery inpeer-to-peer network, in which the adversary is able to compromise some of thenodes to pollute the Routing Table of its targets. Similar problem happens toTOR’s directory server attack [1], and also in Bitcoin’s underlying peer-to-peernetwork [48]. In OC, since the routing information can only come from otherpeers in the system, yet some of them can be malicious. The malicious nodescan pro-actively advertise its target frequently with only the routing informationof the other malicious nodes, and as a result, the target node is more likelychoosing malicious nodes as forwarding nodes and the anonymity of the receiveris compromised. Although, it is assumed that a node will start with routinginformation of honest nodes in the system, by doing progressively advertising,the adversary is at least be able to make its target nodes choose some of maliciousnodes, which increases the probability for the adversary to know the identity ofthe receiver. In this paper, no solution is proposed to fully prevent this kind ofattacks, but will definitely consider is in the future version of OC.18Figure 7: Message Delivery from S to R through 2 intermediate nodes5 Anonymous Message DeliveryThe primary functionality of OC is to provide a decentralized platform for regis-tered peers in the system to be able to deliver message to other peers in systemwith anonymity. Such decentralized anonymous messaging systems have beenproposed in many different paradigms, and famous ones like TOR [1] are beingactively deployed globally. In OC, the scheme to achieve anonymity is inspiredby the Onion Routing [1] based system, in which the message is being encryptedmultiple times in layers with different keys. Then this encrypted message will gothrough multiple intermediate node and each node can decrypt it with its ownprivate key to peel one layer off the message. So that, only when the messagereaches the destination node, the content of the original message can be viewed.In contrast to TOR [1], instead of using symmetric keys to wrap and unwrapthe original message, OC only uses public key for encryption.The reason that OC chooses not to use sole symmetric encryption is thatOC tries to leverage the use of public key for both identification and encryptionpurpose, for which if using symmetric key scheme cannot achieve both purposesat meantime directly. In TOR, multiple of symmetric keys for each pair of hopsare negotiated when the virtual circuit is built, and those keys can only be usedwithin the same circuit for encryption and identification. When the old circuitis destroyed, these symmetric keys are no longer useful for identification.With the integration of the currency system, besides the extra content addedin OMSG, there are also extra steps added when delivering messages. These ex-tra steps are mainly for the purpose to utilize the currency to provide incentivesfor peers to be more likely participate in OC while still remain anonymous. Tobe specific, the intermediate nodes will get Coins from the source at the proper19moment when it provides the help re-directing the message. Besides, some ofthe optional steps are designed to serve as the cover traffics to aid hiding theintention of the communication. The full procedure of send an anonymous mes-sage can be separated into two parts, the Preparation Stage and the deliveryof the message by Message Forward Protocol.5.1 Preparation StageIn Preparation Stage, the sender is responsible for getting enough informationto make the message delivered with high probability such as routing informationof the selected forwarding nodes, and the Coins for every forwarding node. Forthe sender node S to deliver a message m to the receiver node R, S first needsto prepare several necessities before actually send off the m. (1) S needs to planthe communication path consists of multiple intermediate nodes with ids N0,N1, ...Nk, with public keys PK0, PK1, ...PKk which are registered in OC. (2)If any routing information of intermediate nodes or R is missing or suspected toexpired in S’sRouting Table, S needs to gather such routing information fromother nodes . (3) If S does not have at least one Coin for each Ni, S needs toperform one or more Coin Exchange operations to acquire enough Coins C0, C1,... Ck for rewarding, (4) Optionally, S could wait for the time when there areintense incoming traffic while sending m for better anonymity. (5) S preparesthe layered payload M in form ofpkEnc(N1 : CS : ... : pkEnc(R : Ck1 : pkEnc(m : Ck, PKR), PKk)...., PK0)as the PAYLOAD part in OMSG with OPCODE to be FWD. For instance,if S chooses N0 and N1 as intermediate nodes, the payload M should be:pkEnc(N1 : CS : pkEnc(R : C0 : pkEnc(m : C1, PKR), PK1), PK0)The order of steps are crucial, especially steps (2) needs to be done before(3)-(5), otherwise, once the Coins are exchanged and if some of intermediatenodes are not currently on-line, the deliver would fail with high probability.The broken point on the communication path is undetectable, therefore theCoins that have been spent before reaching the broken point are paid to theother peers, however, the Coins that are supposed to pay for the peers after thebroken point are still valid and can be used in future for the same subset ofpeers.5.2 Messaging Model AdjustmentContinue with the same context from previous sections, where the communica-tion lies among S, R, and N0, N1 ... Nk. To reason about the necessity of theextra steps for message delivery added in OC, start considering the base ver-sion of Onion Routing message delivery protocol(Figure 7). The steps (1)-(4) inPreparation Stage remain the same, and perhaps with different mechanism20Figure 8: Message Delivery from S to R through 2 intermediate nodes withCoins "paid-in-advance"according to the system designs. In the last step, the content of M can be sim-pler as there is no need for Coins. The form of message M with a path consistsof N0 and N1 should in the format like:pkEnc(N1 : pkEnc(R : pkEnc(m,PKR), PKn1), PKn0)Then S forwards M to N0. As N0 receives M , it can decrypt M0 with itsprivate(secret) key SK0 and get next hop id N1 and the inner message M1.After that, N0 forwards M1 to N1. N1 can also decrypt it to retrieve id R andM2. Finally, R receives M2, and decrypts it with SKR to read the message mwhich was originated by S. This base version of Onion Routing provides theanonymity for S by hiding its action deliveringm to R via multiple intermediatenodes in which none of these nodes are able to read the content of m due tothe encryption. Also, none of these intermediate nodes are able to determinethe source of m since the fact that m could be going through multiple hopson purpose and therefore the neighbor nodes are not certainly the origin nordestination of m.The base version of Onion Routing has no assumption about the odds thatthe intermediate nodes will or will not deliver m continuously till reaching Rsince no incentives are provides. Now considering adding Coins toM0 for payingthe intermediate nodes, based on the Onion Routing communication model,Coins are added for rewarding the intermediate nodes for helping deliver mfrom S to R. Assume S has already gained two Coins Cn0, Cn1 for N0 and N1.The simplest way for S is to "pay-in-advance". For example, S prepares thepayload M aspkEnc(N1 : Cn0 : pkEnc(R : Cn1 : pkEnc(m,PKR), PKn1), PKn0)21Figure 9: Message Delivery from S to R through 2 intermediate nodes withCoins "paid-afterward"In this way, considering Figure 8, when N0 receives M0, it can decrypt M0 andretrieve its rewarding Coin Cn0 and so does N1. Base on the validity of theCoins, the intermediate nodes can then determine whether or not to continueforwarding the M1 to next hop. However, this model has to be based on theassumption that every node is willing to behave according to protocol if thenode is rewarded properly, which can be too excessive to ask for in the real-world network environment. Any intermediate nodes in this communicationmodel actually have no incentives to keep providing aids since the rewards havebeen "paid-in-advance".In order to prevent intermediate nodes from taking the rewards withoutproviding the service, a better design would be that the rewards can be "paid-afterward". Now consider a better version of this model(Figure 9), in which theCoins are no longer directly accessible by its owner at the first place. Considerthe following procedure, S prepares M0 in the form of:pkEnc(N1 : CS : pkEnc(R : Cn0 : pkEnc(m : Cn1, PKR), PKn1), PKn0)Now after N0 decrypts M0, N0 will not get Cn0 for reward. Instead, N0 will getCn0 for the node from its next hop which is N1 in this case, and N0 should replyCS to S for rewarding S and then N0 delivers M1 to N1. In this version, therewards will always coming from the peer on next hop, and by designing it thisway, it guarantees that only after an intermediate node has helped delivering amessage, this node may get the rewarding Coin. With this fact in the protocol,the intermediate nodes should be more willing to deliver the message furthercompared to the first model(Figure 8).However, this model introduces one extra message for each hop on the com-22Figure 10: Message Delivery from S to R through 2 intermediate nodes withCoins "paid-afterward" and Feedbacksmunication path, which in general doubles the total number of messages re-quired to deliver m, and it is not enough to provide the sense of incentive tothe intermediate nodes especially when S plans to cheat. In this model, everyintermediate node expects to get rewards from its next hop, yet these interme-diate nodes can not really do anything to guarantee receiving a valid Coin afterproviding the help. The sender S can simply wraps some of invalid Coins orjust trivial data along with the m, and the m will probably still be able to reachthe destination with the same probability compared to that S uses valid Coinsto pay the intermediate nodes.To resolve the problem with the cheating sender, one extra step can is nec-essary to add to constrain S from cheating with invalid Coins. The format ofmessage M0 remains the same as in previous model, and an intermediate nodeNi can only get reward from its next hop Ni+1. The extra step would be, af-ter Ni decrypts M0, instead of forwarding the inner message M1 to Ni+1 andreplying Ni1 with Ci1 at meantime, Ni replies Ci1 to Ni1 with the Coinfirst, and then wait for a feedback from Ni1. The feedback from the Ni1varies by the result of Ni1 verifying the validity of the Ci1. After Ni receivesthe positive feedback from Ni1 indicating Ci1 received is valid, Ni based onthis positive feedback, can decide whether to forward M1 to Ni+1. ConsiderFigure 10 for how this new model works.With the feedback step added, the intermediates nodes now are able to tellwhether S has included invalid rewards for their previous hops. An intermediatenode although cannot directly determine the validity of its upcoming Coin forits next hop, the fact that if S has provided the invalid Coin at its previous hop23indicates S’s intention to cheat. Therefore, with this step added, the sendershould be more willing to provide only the valid rewards to increase the proba-bility of a successful message deliver, since once any cheating by S is detected,the intermediate nodes probably would not want to continue helping to forwardthe message.This model however still allows S to partially cheat and yet get the messagedelivered with the same probability. Now consider S preparesM0 with all Coinsto be valid except the one for the last intermediate node Nk. By doing this way,even though Nk is able to detect cheating behavior of S, the message itselfhas already be received by the receiver R, which allows S to pay one less Cointo deliver the message with same success rate compared to that all Coins arevalid. Nevertheless, when S cheats in this way, Nk has a higher chance to detectthat its next hop R is the final destination of m, which could aid compromisingthe anonymity of this communication especially if Nk is part of the adversary.Therefore, for S’s best interest, S would still want to use only the valid Coinsto deliver m.5.3 Message Forwarding ProtocolThis version of protocol is adopted in OC as the Message Forwarding Pro-tocol(Figure 10). The steps for S to deliver a message m to R can be concludedas following:1. S finishes the steps described in Preparation Stage, with M0 ready.2. S forwards M0 to N0.3. N0 receives M0 and decrypts it with SK0 to retrieve id N1, CS , and innermessage M1.4. N0 forwards CS to S.5. S receives CS , and verifies CS , then forwards the feedback fS to N0.6. N0 receives the fS . If fS is negative, abort the operation. Otherwise, N0forwards M1 to N1.7. N1 receives M1 and repeat steps 3 to 6 till Nk receives the fk1 fromNk1.8. Nk forwards Mk to R based on fk1.9. R decrypts Mk with SKR to retrieve message m and Ck.10. R forwards Ck to Nk, and reads message m.Notice that there is a Coin CS sending from N0 to S. The purpose of havingthis CS is to prevent N0 from suspecting that S is the originator of M0, whichwill provide more information regarding this communication. The same reason24goes for the presence of Ck. Since Ck is the last intermediate node, and R willbe able to retrieve m anyway without sends Ck back to Nk. However, if R doesnot give Ck to Nk, Nk can suspect that R can possibly be the destination ofthis communication.Compared to base version of Onion Routing communication model, OC’smodel introduces 2 more messages for each hop on the path, one for the Coin,and one for the feedback, which eventually triples the total number of messagesrequired to deliver m compared to the base version of Onion Routing. However,with these extra steps added to OC’sMessage Forwarding Protocol, besidesthe incentives are provided for the helping peers, the anonymity of the commu-nication is also enhanced. The extra messages exchanged in every hop can alsobe considered as the cover traffics to introduce extra difficulty for adversariesto inspect the traffic and determine useful patterns to correlate the identities ofthe communicating nodes.5.4 Failure on DeliveryIn OC, there is no protocols to detect the failure status or locate the exactposition of broken point on the delivery path when there a message failed toreach its destination. It is not because that the communication model in OC isdatagram(UDP) based, which by default there is no indicator on delivery statussuch as acknowledgement(ACK) expected by the message sender. The primaryreason is that the message will be re-directed multiple times to hide the identityof the original sender S, and any kind of indicator directly reporting back to Swill compromise S’s cover of action. Also, due to the design of message encodingand encryption scheme, as well there is no easy design to decide where the failurereport should go back to.Although, it is always possible to including extra information in the mes-sage for the purpose of failure detection or correction, this way will increasethe chance for adversary to identify the communicating parties. For example,consider adding the steps in the protocol in which each intermediate node isable to maintain the status of the message delivered mapped to some ids. Oncethe failure case is suspected, such as no Coin has come from the next hop fora long time, the node can send the special message Fid indicating the failureto its previous hops with the identifier(id) of this communication, and then theprevious hop can do the same until Fid finally back to the S. Based on theinformation included in Fid, S is able to detect the broken point of the path,and also knows which Coins are still valid to use. However, this protocol bringsus back to the problem with incentives. In order for the peers to helping deliverFid, providing the rewards are also necessary, which could potentially lead todouble the number of Coins required from S.256 The LedgerThe Ledger in OC represents the globally distributed database of all the trans-action records with three different types: Registration Record(RR), CoinExchange Record(CE), and Coin Reward Record(CR). The Ledgeradopts the BlockChain-like approaches, in which a block consists of multipletransaction records, and blocks are append-only to the Ledger. Each node isexpected to have local copy of the Ledger, and the "longest branch" principle isapplied when conflicts happen. The major difference between OC’s blockchainand the ones from other crypto-currencies [42, 34, 43, 44] is that the "mining"in OC can only be done by the Banks in current epoch. At the end of theepoch, the Banks will cooperate to generate a single new block containing allthe transactions happened in current epoch. This approach is inspired by theidea of "leader" in BlockChain-NG [34], where only the leader nodes are ableto mine the new blocks.6.1 RecordsAlthough there are different types of transactions, the general format of themare the same. Each record consists of four segments: CONTENT, TIMES-TAMP(TS), SINGERS, and SIGNATURES(SIGS). TS is general UNIXtime-stamp of 8 bytes in size. SINGERS are the list of strings representing theids of CoSigners of this record, and the SIGS are the corresponding digital sig-natures on the hash of the CONTENT by these CoSigners. CONTENT is theonly varying part in different type of records, and the details will be describedin the following sections. When a record is added to a block, this record canbe identified by the sha-256 sum of its CONTENT since all CONTENT couldnever be duplicated.6.1.1 Registration RecordThe Registration Record(RR) is generated each time the Banks have ap-proved of registration of a new peer into the system. The CONTENT of RR isid of the new peer Nnew and the public key PKnew generated by Nnew. Themembership in OC is only being verified by checking the existence of corre-sponding RR in the Ledger. Also, the positions of RRs in the Ledger are usedwhen selecting the Banks.6.1.2 Coin Exchange RecordThe Coin Exchange Record(CE) represents the action of marking the oldCoin as invalid from the point this CE is added to Ledger, since the old Coinhas been considered to be exchanged for a new Coin. However, the informationof the new Coin is not recorded to protect the identity of the owner of the newCoin. The CONTENT in a CE is the data of a valid Coin as defined in earliersection. The generation of CE may not necessarily indicate the fact that a new26Coin has been generated due to the failure cases described in earlier section.Therefore, the purpose of having CE on the Ledger is only to record the usageof those old Coins to detect "double-spending" behavior.6.1.3 Coin Reward RecordA node can "redeem" its previous service to the community when serving as aBank into new Coins. Every time a transaction is published, the ids of CoSignersare recorded in the record as well. Any of these CoSigners can later require a newCoin from one of these old records by requesting Banks for publishing a CoinReward Record(CR). The CONTENT of CR includes the block depth(indexof block on chain) in the Ledger, transaction hash, and node id. This informationshould only mark one of the CoSigners in one previous transaction record inone of the previous Blocks. The generation of CRs is crucial for the liveness ofcurrency system since it is the only mechanism in OC to publishing new Coins.6.2 Bank SelectionIn OC, the term epoch refers to a short time-interval whose length is determinedat the boot time of the system. In each epoch, a subset of nodes will be selectedto play the role as Banks(Figure 1). The Banks are not considered elected butinstead selected automatically by the consistent hash function F . The definitionof F is fixed at the boot time of OC, which will output certain number of ids. Theparameters of F are epoch number ei, number of transaction records generatedin last epoch ei1, and registered ids and their positions relative to the beginningof the Ledger. Since the Ledger is consistent globally, the registered ids andtheir order of registration are also consistent to any nodes that has the mainversion of the Ledger.At the end of each epoch, with proper synchronization of the Ledger, everynode is able to determine which nodes are going to be Banks in next epoch,therefore, no protocol for consensus or notification is required. Base on the factthat, majority of nodes will maintain the same version of the Ledger, then themajority of the nodes would have the same view of the choice of Banks for nextepoch. However, the Ledger is so distributed that the synchronization maynot always successfully happen, and as a result, less than majority of the nodescould have the same version.With static definition of F , some forms of attacks could be performed by theadversaries to try to acquire the majority of the Banks in some epochs in orderto collude and cheat on currency system. Although the definition of F is static,the parameters are changing dynamically overtime and therefore unpredictableunless the adversary is able to control the number of transactions happened incertain epochs.276.3 Ledger Synchronization ProtocolLike other BlockChain-based system, keeping the Ledger up to date is crucialto the operations involving accesses to the Ledger such as Bank Selection andCoin Verification. The synchronization among all the nodes is also the costliestpart compared to other messages exchanged in OC. In OC, in order to improvethe efficiency, the Block generation is limited only to the Banks in current epochand the Normal Nodes are not required to have the new block until next epochto fully operate since the information on the newest block is never accounted inany operation such as Bank Selection, and Coin Verification.The principle of performing synchronization of the Ledger is similar to theother BlockChain-based system, which is to try to locally store the chain ofblocks with the longest branch. The branching could happen due to either thenetwork failures, limited view in system, or simply a node is not operating duringrecent time intervals. In OC, even though the Block generation is epoch-based,in which only one block will be generated for each epoch, the branching couldstill occur due to similar reasons.For a node N0 with local Ledger L0 of depth d0 to synchronize L0 withanother node N1 with Ledger L1 of depth d1. The general protocol goes asfollowing. N0 sends SYNC request to N1 with payload including d0 and khashes of the blocks in L0, hd0k, hd0k+1, hd0k+2 ..., hd0 . When N1 receivesthe SYNC request, five cases could happen:1. d0 is same as d1 and all hashes on the same positions are same.2. d0 is same as d1 but some hashes on the same positions are different.3. d0 is greater than d1.4. d0 is smaller than d1 and all hashes on L0 are same as the ones on L1 insame positions.5. d0 is smaller than d1 but some blocks on L0 are different from the oneson L1 at same positions.When N1 receives the request, it first compares d0 and d1. If d0 is thesame as d1, then N1 checks if all hd0i are the same as hd1i, if yes(case 1),N1 ignores the request. Otherwise(case 2), N1 also ignores the request sincethere is no way to tell which Ledger the main version is. If d0 is greater(case3), N1 ignores the request. Otherwise N1 checks if all hd1i are the same ashd0i. If true(case 4), N1 replies with blocks bd1d0 , bd1d0+1, bd1d0+2, ... bd1 .Otherwise(case 5), N1 finds the first position p such that hd1p is not equal tohd0p and replies with blocks bd1p, bd1p+1, bd1p+2, ... bd1 .For example(Figure 11) as of case 5, consider N0 has a shorter Ledger with3 Blocks with hashes h00, h01, and h02, and N1 has a longer one 5 Blocks withhashes h10, h11, h12, h13, and h14, assuming k = 2. Then the synchronizationprotocol goes as follow:1. N0 sends the d0 = 3 and hashes h01, and h02 as SYNC request.28Figure 11: Ledger Synchronization with d0 = 3 and d1 = 5292. N1 receives the SYNC request, and finds out d0 is smaller than d1.3. N1 then checks h01(B89B32), and h02(7C290E) against h11(B89B32),and h12(B9811E), and finds out that h12 is different from h02.4. N1 replies with blocks b12, b13 and b14.5. N0 receives the new blocks, and based on the depth of these blocks, N0trims its chain by discarding b02 and append b12, b13 and b14 to L0 thenupdate d0 to 5.During the procedure that N0 sends the SYNC request to N1, N0 yet hasno way to verify that the blocks from N1 are from the longest branch, andN1 also not guarantee to have the longest version of it. Therefore, N0 shouldrequest the blocks from multiple sources and possibly only append the mostcommonly occurred blocks. This problem yet will not affect the correctness ofthe other part of the protocols since the most recently generated blocks will notbe expected to involve in the protocol and information from these new blocksshould never be used for verification.6.4 Block GenerationAt the end of every epoch, a new block containing of all the transactions pro-cessed in the current epoch is expected to be generated by the Banks of thecurrent epoch. All the Banks are expected to cooperate to attempt to generatea new Block approved by majority. The generation of the new block can besplit into three stages: (1)Proposing, (2)Pushing, and optionally (3)Pulling.After finishing all three stages, every participated Bank is expected to hold thesame version of the Ledger with new Block added.6.4.1 Proposing StageIn Proposing Stage, each Bank gathers the data of all the records storedlocally and sends them to all the other Banks with best effort. After receivingthe transaction records from the other Banks, a Bank validates each of therecords received by checking several things. First, whether all the CoSignerswere selected as Banks in the epoch recorded. Second, whether the signatureson the hash of the CONTENT is correct. Finally, whether the CONTENT isplausibly correct, for example, if the Coin is valid and has not been used in a CE.Then every Bank adds all non-duplicate records received to its local transactionbuffer. Two records are duplicated if the hashes of the CONTENT are the same,but the signatures and signers can be different. By the end of Proposing Stage,each Bank participated should have a same set of records. Although there couldbe failure cases in which some of the Banks may not have the full set of records,these Bank will not be considered having useful Block during Pushing Stageand they are able to detect this situation.306.4.2 Pushing StageEach Bank generates a new Block containing all the records from its local trans-action buffer, and sends the meta-data of this new Block to all of the otherBanks. Upon receiving the information of the new Block from other Banks,each Bank keeps recording the frequency of distinct Blocks. At the end of thisstage, each Bank should be able to determine which Block is being proposedby the majority of Banks which would be the Block that has the highest fre-quency. However, there could be the case that the majority cannot be formed,where multiple Blocks may all be considered as the major ones. In such case, theBlock that has the highest hash sum value is considered as the one to keep. Thismethod can be however replaced with other standard to resolve the conflict.6.4.3 Pulling StageAt the end of the Pulling Stage, each Bank should have a Block generate locally,and the Bank also knows whether this Block is the major Block. If the localBlock is not the same as the major one, the node will broadcast the request forLedger SYNC, and the new Block will be pulled from whichever Bank that hasthis Block generated. This is the end of Pulling Stage, and also the end of theBlock Generation Protocol. The other nodes in the system can expect to get aversion of the newest block from any of these participated Banks, yet there is noguarantee that the block will be the major one. Therefore, it is recommendedto attempt to retrieve the blocks from multiple Banks and the major block canbe easily determined. Since the the Bank Selection Protocol is known globally,it is always feasible to request the blocks from the nodes that were playing asBanks from the last epoch.317 Threat Case AnalysisOC’s primary feature is to provide anonymity to all the users regardless the rolesthe users are currently playing, yet the other security aspects such as messageintegrity, identity authenticity and privacy are also being covered. In order tostate to compromise the anonymity of the communicating parties, the proofdoes not have to be perfectly gathered, for example, the adversary can provethat there is a message originated by sender S and it is eventually delivered toR and no further hops after R. As long as there is evidence indicating thereis a message coming from S to R, the connection between S and R then canbe concluded and hence the anonymity is considered broken. In this section,multiple instances of different possible attacks on OC’s protection on anonymityof the users are analyzed.7.1 Passive Threat on MessagingIn the passive attacks, the adversary only means to inspect traffic and try toretrieve useful information to make connection regarding the message flows. Thepotential passive attacks in OC are very similar to the other Onion Routingbased message passing [37, 35, 36, 38]. Although in OC, there may be twomore message exchanges between a pair of hops, the overall behavior can stillbe reduced to fit the Onion Routing based model since the number of messageexchanged between hops are considered consistent. However, there are extradangerous cases in OC due to the addition of the currency system. In thefollowing section, multiple cases of an instance of communication from S to Rvia k intermediate nodes N0, N1, N2 ... Nk1 where 0 < k are discussed.7.2 Single Malicious NodeIn this section, assume that one of the nodes is controlled by the adversary. Theadversary can use any information received from the other nodes to expose theconnection of S and R, yet the adversary is assumed having no ability to inspectthe traffics flow at the other points of communication. However, accordingto the design, an intermediate node only has knowledge about its neighbornodes, and the messages exchanged are all encrypted, and the Coins exchangedcannot identify their originator. Therefore, with single node as the adversary,the anonymity of the communication with more than one intermediate nodeis not going to be broken in any cases since this node cannot capture enoughinformation of the identities of both communicating ends.The first category of scenario is that one of the end node is compromised,sender or receiver. Since S is the source of m, the case that S is compromisedtherefore is trivial. If R is controlled or hijacked by the adversary, this com-munication will firmly be revealed if S has provided its signature or any solididentity proof along with m. However, if S did not include any identity infor-mation in the payload of m, S will not be connected to R. But in such case32where S does not prove its identity authenticity, R cannot verify the originatorof m and therefore the communication is considered failed.Now consider the scenario that the adversary has compromised one of Niwhere 0  i < k on the communication path with Mi received on each hoprespectively. There are possibly three cases: (1) N0 who is the directly next hopof the sender is compromised, (2) Nk1 who is the previous hop of the receiver iscompromised, and (3) Ni (0 < i < k 1) which is not directly contacting eithersender or receiver. In every case, the compromised node Ni is able to retrieve theprivate key information of Ni and use it for encryption, and also able to activelyrecord incoming traffics from any points. The case that k = 1 is considered thecase in next section where all intermediate nodes are compromised.In case (1), N0 acquires the message M0 from S and N0 is able to retrievethe Coin CS and the id of next hop which is N1. So far, N0 can conclude thatS is communicating with N1 based on the next hop id received, yet N1 is notrelated to R. Besides, the content of CS may cause N0 to suspect that S isthe originator or M0 if S decided to use an invalid Coin to pay itself, or thatS is trying to cheat the system. If the CS is a genuine one and S also repliesto N0 with the feedback after receiving CS from N0, N0 would have nothingto distinguish S from being an intermediate node dutifully relaying M0 fromunknown source, where PS is the sender ⇡ PS is a relay node.In case (2), Nk1 is aware that Mk1 comes from Nk2 and the next hopis R. From the content of Mk2, Nk2 is not able to tell any connectiondated back to S. After Nk1 delivers Mk to R, at this point R could haveitself exposed as the final receiver if R does not reply CNk1 to Nk1. Aslong as R gives CNk1 to Nk1, Nk1 then has no information to distinguishR from being another intermediate node on the communication path, wherePR is the receiver ⇡ PR is a relay node.In case (3), Ni is able to know that Mi is coming from Ni1 and the nexthop is Ni+1, therefore the connection between Ni1 and Ni+1 can be made, yetneither nodes are S or R. Based on the Coin information, Ni may suspect thatthe Ni1 is the originator if CNi1 is not valid, or suspect that Ni+1 is the finalreceiver if Ni does not receive CNi from Ni+1. However, in either case, S andR are not directly involved.7.3 Multiple Malicious Intermediate NodesIn this section, the cases when there are multiple compromised intermediatenodes are discussed. The strength of protection on the anonymity relies onnumber of intermediate nodes, hence it is obvious that the more nodes that theadversary controls, the higher probability that the communication ends can beidentified. However, the positions of compromised nodes on the path is also adominating factor based on two interesting facts. First, a pair of non-adjacentnodes may correlate the traffic between them based on some factors such aspacket size, timing, and frequency, and the chance of making correct conclusionincreases as the length of the gap decreases. Second, only when both N0 andNk1 are controlled, the adversary has the opportunity to link S and R because33they are the only nodes directly contacting the sender or receiver. The best playfor the adversary therefore is to control N0 and Nk1 first and try to pick Nj ’s(0 < j < k  1) such that no node is adjacent to other nodes. In the followingparagraphs, several cases are selected for demonstration.The best case for the adversary would be controlling all of the intermediatenodes, in which the adversary can firmly state that there is a message from Sto R going through the path consist of Ni’s. Although whether S is the origi-nator of the message nor whether the R is the final receiver is not known withsolid evidence, the adversary has had enough information to make conclusionregarding S is communicating to R. This case is also the most severe case thatbreaks the anonymity in other Onion Routing based approach, yet as stated inthe Threat Model Section, OC is not resilient to such situation.Now consider the cases that the adversary controls k1 Ni’s on the path, todemonstrate the importance of controlling N0 and Nk1. There are three cases(1) i starts at 0 and goes up to k 2, (2) i starts at 1 and goes up to k 1, and(3) i starts at 0 and goes up to j1 (0 < j < k1), and then from j+1 to k1.In case (1), the adversary can firmly state that there is a message delivered fromS to Nk2 yet the connection to R is unclear. The same rationale goes in (2),in which the adversary can only state that R receives a message from N1. Incase (3), the adversary can confirm that there is a message m from S sendingthrough N0 to Nj and afterwards there is also a message m0 sending from Njto R. There is no direct evidence to proof that m0 is derived from m, yet thecorrelation in timing that m goes to Nj happens before m0 comes out of Nj isalways true. The adversary therefore would more likely making conclusion thatS is trying to send a message to R. This attack that is similar to the end-pointattack happened in TOR, in which if the exit nodes are controlled, the flow ofthe traffic can be correlated with less difficulty.To demonstrate how the positions of the compromised nodes on the path mayaffect the strength, consider the cases that the adversary is able to control N0,Nk1 and exactly other p = bk22 c intermediate nodes. Consider the followingthree cases when p nodes are picked with different positioning. (4) p nodesinclude Nj to Nj+p1 (0 < j < k1p), in which these p nodes are consecutiveon the path, (5) p nodes include N2, N4 ... Nk3, in which there is one-hop gapbetween any two nodes on the path, and (6) the other combinations.In case (4), the adversary firstly has full knowledge about the traffic fromNj1 to Nj+p. Base on the position of Nj , the adversary may also be ableto conclude that S is sending message through N0 to Nj+p if Nj is close toN0. However, the connection between Nj+p and Nk1 is unlikely to be foundsince they are far away from each other, and hence the connection from S to Rcannot be found. The same rationale goes for the case that Nj+p1 is close toNk1, in which the connection between Nj1 to R may be concluded but S isnot involved. In these cases, the chance of breaking anonymity increases as thelength of the gap between N0 and Nj , and the gap between Nj+p1 and Nk1decreases.In case (5), the adversary has better chance finding evidence about S istalking to R compared to (4). The traffic in the gaps between these p nodes can34be guessed with the help of correlation in timing especially when there is littletraffic coming from S. For example, with N0 and N2 controlled, the adversaryhas better chance conclude that there is message from N0 to N2 via N1 usingtraffic correlation. As for case (6), it lies between (4) and (5), in which theadversary would have higher chance finding the link between S and R if thepositioning is more like the one in (5), and less chance it is like one in (4). Inconclusion, to fully utilize the help from correlation, the adversary should try tocreate as many gaps on the path as possible yet also try to minimize the lengthof each gap.358 Cheating on CurrencyIn OC, the requirement on consistency regarding the currency is not necessarilyas strong as those crypto-currency systems since the currencies in OC are notdirectly related to real world currencies. As a result, it is possible to cheat oncurrency system in OC with low probability if the adversary is able to con-trol large number of nodes. In this section, some cases regarding the potentialcheating behaviors on the currency system are discussed. Like many other dig-ital currency systems, there are always attempts by the members to exploit thebugs in the system to make undeserved profits. The collusion is mostly an ef-fective way to acquire super power over the peers to go against the consistencyof the system especially in decentralized environment, where the consistency isrelied on some forms of consensus. In OC, such collusion is also possible sincethere are always multiple Banks behaving as the temporary authorities to co-ordinate the transactions on the Ledger. However, in such cases, the protectionof the anonymity of the peers are not affected. Beside the collusion, the senderwho pays to every helping peer may also cheat on the system to save someCoins.8.1 Forging Coins and RecordsSince each record requires NC Banks to sign on it to make it valid and thoseBanks who signs will get rewards for signing this record, Banks can then playto sign as many records as they could to increase their profits. Yet, there isanother method for Banks to get even more profits with less efforts, which isconsidering forging records or Coins. One Bank however cannot possibly forgeanything since each record requires NC signatures, and NC should always begreater than one in practice. However, with at least NC colluding Banks, recordscan be forged. In the following paragraphs, the discussions about how Banksmay collude to forge records and Coins, and how likely this collusion can happenare made.RR itself cannot be simply forged due to the assumption that no node canhave multiple ids registered in OC, and CR cannot be forged as well due to thateach CR claims a reward from previous records and the reward can only be usedby its actual owner which is the Bank that signed this record. Therefore, onlyCE may be forged if enough Banks are colluding. However, each CE requires avalid Coin to be marked as spent, therefore, the essential question becomes isit possible to forge a valid Coin? A valid Coin also requires NC Banks in thesame epoch to sign on it, therefore, if the adversary can control at least NCBanks in the same epoch, it is able to forge as many Coins as possible duringthis epoch. These Coins can be spent in the later epochs, and the forging cannot be detected due to the feature that a Coin’s old owner is not linked to thenew one.Now lets consider the probability that an adversary can control NC nodesthat happen to be Banks in the same epoch. Since the Bank is assumed tobe selected randomly and cannot be predicted, the probability that any node36#Nodes(n) #Banks(b) #CoSigners(c) p10 5 3 0.0833333310 5 5 0.0039682510 7 3 0.2916666720 5 3 0.0087719320 5 4 0.00103199100 5 3 0.00006184100 5 4 0.00000128100 10 3 0.00074212100 20 3 0.0070500910000 10 5 3.027 x 101610000 20 5 1.862 x 10141000000 10 5 3.024 x 1026Table 1: The probabilities that an adversary can forge Coinsis selected as Bank is equal. Also, assumes that an adversary can compromiseany node with equal probability. Let n be the total number of nodes in thesystem, b as the number of Banks selected in each epoch, and c as the numberof CoSigner that the adversary can compromise, where b is always greater orequal to c, and b and c are smaller or equal to n. The question can then bereduce to a probability quiz question that what is the probability p that all cnodes selected from n nodes happen to be Banks given that there are b out ofn as Banks? The solution is:p =bCcnCc=b!(n c)!n!(b c)!The value of p may not be very clear to tell given such formula in terms ofmultiple variables. Let consider some values of p in different examples withvarious n, b, and c selected, shown in Table 1.Although it is possible for the adversary to have multiple of nodes compro-mised and be able to forge many Coins, the probability that it could happen canbe very small when either there are large number of total nodes or the numberof CoSigners is large. Increasing the number of Banks selected in each epochwould increase this probability but the ratio of number of Banks to number oftotal nodes should be small in practice. On the other hand, this cheating be-havior once happens, would not harm the anonymity guarantees regarding anycommunications since no useful information is leaked from these forged Coins.As for the other honest peers, they also would not lose any deserved Coins sincethe forged Coins would not cost any Coins from these honest node. Therefore, amechanism to full prevent this cheating behavior from happening is not designedin this paper but may be considered in the future works.378.2 Cheating Sender and Intermediate NodeAs discussed in the Section 5.2 when developing the communication model frombase version Onion Routing, sender is totally capable of cheating to save someCoins. However, the saving may cause the failure of message delivery or theexposure of anonymity. For sender S to deliver m to R through N0, N1 and N2,S should pay three Coins in total. With the Feedback step in the protocol, if Sever includes invalid Coins for any of N0 and N1, m will be failed to deliver withhigh probability. When the Coin for N2 is invalid, the success of delivery of mwill not be affected, however N2 can suspect R as being the final destination ofm, which lowers the difficulty for adversary find the links between S and R sinceone end of the communication is found. Another concern for sender to cheatis that whether S is able to use the Coin before any of Ni receives them. Dueto the design that every Coin can only be exchanged by its owner, S once hasprepared the Coins for Ni, S cannot re-exchanged them. Therefore, under anycircumstance, the best play for S is to pay enough valid Coins for intermediatenodes.As for the intermediate nodes, the cheating behavior is also feasible but willnot damage the system. One possible case is that when Ni receives Mi, it canget Ci1 by decrypting Mi, but Ni can choose not to send Ci1 back to Ni1and instead sending an invalid Coin to Ni1 and ignore the feedback from Ni1.Then Ni can continue deliver Mi+1 to Ni+1 and wait for Ci. By doing this way,Ni1 does not get a deserved reward but the message delivery is not affected.As for Ni, since Ci1 can only be used by Ni1, Ni does not get an additionalCoin, and therefore this cheating behavior is not beneficial to Ni. The samerationale goes for the case that Ni gives falsified feedback to Ni+1, in whichNi is not getting additional reward but may cause the overall message deliveryfailed.389 Analysis of Encryption StepsIn OC, the public key encryption and symmetric key encryption are used almostevery time a message is sent to from one node to another. In the operationsrelated to the currency system, there are even more encryption steps to suitdifferent security requirement. However, the encryption itself is computationallyexpensive due to massive arithmetic operations. In this section, each encryptionstep will be discussed regarding its necessity and possible alternatives.9.1 Encryptions in OMSGEvery OMSG is designed so that only its designated receiver can decrypt itand has the accessibility to PAYLOAD. A common approach is that use thereceiver’s public key to encrypt the message and then send to the receiver andno other peer is able to read it. The other approach is that performing Diffie-Hellman key exchange [41] between the sender and the receiver to negotiate asecret session key for encryption. The former approach is adopted in OC dueto that identities of senders of any messages need to be verifiable as membersin OC, and symmetric key encryption scheme cannot give such informationregarding the identities of the key holders. However, the size of OMSG can bevery large in some cases and the public key encryption is not efficient in suchcase, therefore the hybrid approach is applied to improve this encryption step.The OMSG will be encrypted using a one-time AES key first, and then the AESkey is encrypted by the public key.For a registered node Ni to deliver an OMSG, the HASHSIG section isgenerated by signing the sha-256 sum of the payload with the private key SKi.The purpose of this signature is twofold. First, the receiver is able to verifythat the sender is registered, and sender is who it claims to be. Since OC isdesigned to only provide services for members, the ability to verify the identityof the OMSG sender is a must. When N0 receives an OMSG from N1, despitethe SENDERID is claimed to be as N0 in this message, N1 cannot confirm thatit is actually sent by N0 rather than a spoofing node. Therefore, the proof ofidentity of N0 is required to be included in this OMSG, and like many othersystem, digital signatures are used here to provide such proof. Secondly, thissignature also provides the evidence that the data in PAYLOAD is not corruptedor tampered. N1 should be able to compare the hash of the PAYLOAD againstthe value gained by decrypting HASHSIG with SKN0 to check if the PAYLOADis not altered.9.2 Encryptions in ProtocolsThe encryption steps also happen in the process of some of the operations invarious protocols. In the Message Forwarding Protocol, the message is to bewrapped multiple time as an onioned message, and then later this onionedmessage will be peeled multiple time as well. Also, during the Coin Exchangeand CoSign Protocol, some public key encryption steps are there to protect39either the anonymity of the sender or to proof the authenticity and validityof the information being published. In the following sections, each of theseencryption steps will be discussed.9.2.1 Signatures In The RecordsFor a record to be valid, it needs to contain multiple signatures from the Banksin the same epoch. In OC, the Banks act like the authorities to approve thetransactions that Normal Nodes proposed. The Bank signs the CONTENT of arecord to show their approval to this record, and the signatures are included inthe record for other nodes to verify their validity. The signature is one step ofpublic key encryption, and for every record there are then NC times encryptionsteps required. These signatures are necessary to validate a record, as well toprotect the CONTENT of this record from being tampered.9.2.2 Onioned MessagesThe layered public key encryption used in formatting the message being deliv-ered is mainly to guarantee that the intermediate nodes are not able to view thecontent of the original message so that the intermediate nodes cannot acquireuseful information from the content to reveal the link between the sender andreceiver.In OC, however, when such message is delivered in OMSG format, the en-cryption seems to be redundant due to that OMSG also encrypts the message,which means the message is encrypted twice to protect from being viewed. Whenan intermediate node receives the layered message, it needs to first decrypt theOMSG to see the PAYLOAD and then again it needs to decrypt the PAYLOADto get the inner content which is also encrypted. Then the receiver needs to makeanother OMSG with the inner content and pass it to the next intermediate node.However, the steps regarding wrapping and peeling the onioned message cannotbe removed even though the onioned message is within the OMSG.9.2.3 Blind SignatureAs describe in Section 3.3 when a node N0 is doing Coin Exchange and withplain Raw Coin RCi, Bi can log RCi received from N0 to make guess aboutN0’s planned communication path. Therefore, N0 should always "blind" RCibefore it goes to Bi. The Blind Signature is also using the public key encryptionto apply the blind factor the message and when removing the blind factor is alsoanother step of public key encryption. The "blinding" is important for hidingthe information regarding the new Coin which also indicates the N0’s possiblefuture contacts. This step however cannot be replaced with other encryptionscheme such as normal public key encryption or symmetric encryption sincethese scheme does not forbid the Bi to know the content of the message andalso be able to have the signature from Bi.40#Messages : #Encryption StepsNACE OnionCoin1. Split RC into NC pieces and blindeach piece0 : 0 0 : NC2. Send RC pieces to Banks NC : 0 NC : 03. Cost at Each Bank NC* NC*3.1 Verify old Coin 0 : NC 0 : NC3.2 Sign on RC or blinded RC piece 0 : 1 0 : 13.3 Reply to the requester 1 : 0 1 : 04. Unblind signed blinded RC pieces 0 : 0 0 : NCTotal Message Encoding 0 : 12NC 0 : 12NCTotal without Encoding 2NC:NC2+NC 2NC:NC2+3NCTotal 2NC:NC2+13NC 2NC:NC2+15NCTable 2: Number of Messages and Encryption Steps Summary for Coin Ex-change in OC compare with NACE9.3 Analysis SummaryIn this section, the extra encryption steps and extra messages in some part ofOC’s protocol are computed and summarized to demonstrate the extra costusing OC as a peer-to-peer anonymous messaging system with anonymous cur-rency exchange. Two protocols are mainly analyzed, Message ForwardingProtocol and Coin Exchange, which are the primary functionalities in OC.Each part of these protocol is compared with either an existing system or thesimulated system for benchmarking purpose, so that the extra cost of using OCcan be computed directly in terms of number of messages exchanged and en-cryption steps, which are the major contribution to degrade performance of thesystem. The following variables are used in the following sections for compu-tation, NC as number of CoSigners, NB as number of Banks, NN as numberof total nodes, L as the number of nodes on the communication path (numberof intermediate nodes plus one receiver and one sender). The OMSG encodingcost is fixed for each message, which is 6 encryption steps in total with 3 forencryption and 3 for decryption.9.3.1 Extra Cost in Coin ExchangeThe Coin Exchange Protocol in OC is novel, and no other existing system hassimilar approach for anonymous currency exchange. Therefore, a simulatedprotocol named Non-Anon Coin Exchange(NACE) is proposed for bench-marking purpose. In NACE, an old Coin is also being exchanged for a new Coinwith possibly different owner, and the content of Coin remains the same. Themain difference in NACE is that the ownership exchange is no longer oblivi-ous, in which Banks can record these transactions in order to make assumptionabout a future message delivery by a specific node. The OMSG encapsulationis still required for confirming the former ownership of the old Coin is the same41#Messages : #Encryption StepsTOR OnionCoin0. Initial Setup (circuitbuilding in TOR, andCoin Exchanges in OC)L2-3L+3:2*(L-2)2 (L-2) * CE1. Prepare Onion 0 : (L-2) 0 : 2L-22. Cost at Each Hop (L-2)* (L-1)*2.1 Peel Layer 0 : 1 0 : 12.2 Verify Coin 0 : 0 0 : NC2.3 Reply Coin backward 0 : 0 1 : 02.4 Send Feedback 0 : 0 1 : 02.5 Forward to Next Hop 1 : 0 1 : 0Total Message Encoding 0 : 0 0 : 18L-18Total without encoding L-2:2L-4 3L-3:(L-1)(NC+3)Total without Ini Setup L-2:2L-4 3L-3:(L-1)(NC+21)Total (L-1)2:2L2-6L+4 [3L-3:(L-1)(NC+21)]+(L-2)*CETable 3: Number of Messages and Encryption Steps Summary for a MessageDelivery through L intermediate nodes compared with TORas the Coin Exchange requester. In NACE, when a node N0 wants to exchangeCold for Cnew, N0 first generate a Raw Coin RCnew and send it to at least NCBanks along with Cold. When Bi receives RCnew, Bi verifies Cold and signs onthe hash of RCnew, then replies the signature to N0. The difference in cost ineach different step is shown in Table 2 in measures of number of operationalmessages and number of encryption steps.9.3.2 Extra Cost in MessagingSince the Message Forwarding Protocol is very similar to the communicationmodel in Onion Routing, TOR is used as the benchmarking model to computethe extra cost in OC to delivery anonymous message from one end to anotherwith the extra features such as Coin rewards, and Feedbacks. As shown inTable 3, the extra cost in term of number of messages and number of encryptionsincluding both symmetric and public key at each separate step are listed. Inboth model, there are initial setups before the sending the messages. In TOR,a virtual circuit consisting of L  1 node is built and the L  1 symmetrickeys are negotiated using Diffie-Hellman key exchange [41] iteratively. In OC,the sender may need to perform L  1 Coin Exchange to get enough Coins.The extra steps in OC include OMSG encapsulation, Coin rewarding, Coinverification, and Feedback. The cost in OC also needs to consider the value ofNC which is set as a parameter when the system boots. The cost of a singleCoin Exchange can be found in Table 2 which is considered the minimal cost inthe best case of a Coin Exchange.4210 Prototype EvaluationTo evaluate OC’s performance, some scenarios are run with different systemparameters. The primary goal of the following experiments is to show the per-formance variation of the message delivery in different scenarios with variablesystem parameters. The metrics of performance is not the end-to-end latency,but instead number of operational messages sent, and number of encryptionsteps are used to measure the performance. The system parameters of OC in-clude (1)Number of CoSigners(NC), (2)Number of Banks(NB) in each epochand (3)Epoch Length(EL). In all of the following experiments, the total numberof nodes(NN) in system is fixed at 20 and every node has full knowledge of ad-dressing the other nodes, which means the peer discovery cost is not consideredas part of the performance cost in this paper. Also, every node is actively follow-ing the designed procedure, and no lazy nodes are present. The issues regardingthe consistence of the Ledger is not covered during the following experiments,but the cost related are measured along with the other cost.10.1 ImplementationThe prototype of OnionCoin system is implemented using Go in 2800 line ofcode. The implementation only uses Go’s standard libraries for all the function-alities. The source code is available on Github public encryption, digital signature and Blind Signature are all using RSAscheme. The RSA key length is variable but should be at least 1024-bit. Thesymmetric encryption uses AES with 256-bit key. The hashing all uses SHA-256, and UDP sockets for all communication. All of the following experimentsare all running on one Ubuntu 17 desktop with quad-core Intel i7 3.7GHz CPUsand 12 GB of RAM.10.2 ExperimentsThe scenarios of the experiments go as below. Each node will start with the sameinitial Ledger including RRs of all 20 nodes, and the Routing Table containingfull addressing information. Starting from an initial epoch, each node exceptthe Banks will send a message to a random destination through a path of severalnodes with random length(L) between 2 to 5 at random frequency less than halfof the EL. Each node initially will hold several valid Coins owned by itself, andmay need to perform Coin Exchange before sending a message.The experiments are mainly divided into three set based on the controlvariables, (1)with fixed EL and NB, varying NC, (2)with fixed NC and NB,varying EL and (3) with NC and EL fixed, changing NB. In the first set, differentinstances with NC varies from 1-5 are tested with EL as 20s and NB equal to5, shown in Figure 12 and Figure 13. In the second set, 10s, 15s, 20s, 25s, 30s,40s and 60s are used for EL where NC = 3 and NB = 5. In the third set, NC431 1.5 2 2.5 3 3.5 4 4.5 522.533.544.555.566.5·104Number of CoSigners(NC)NumberofMessages#messagesFigure 12: Number of Messages To Deliver 1000 message as Number of CoSign-ers changes441 1.5 2 2.5 3 3.5 4 4.5·105Number of CoSigners(NC)NumberofEncryptionSteps#encryptionFigure 13: Number of Encryptions To Deliver 1000 message as Number ofCoSigners changes4510 20 30 40 50 60111111.011.011.01·105Length of Epoch(EL)NumberofMessages#messagesFigure 14: Number of Messages To Deliver 1000 message as length of Epochchanges4610 20 30 40 50 603.·104Length of Epoch(EL)NumberofEncryptionSteps#encryptionFigure 15: Number of Encryptions To Deliver 1000 message as length of Epochchanges473 4 5 6 7 8 9 100.950.960.970.980.9911.·105Number of Banks(NB)NumberofMessages#messagesFigure 16: Number of Messages To Deliver 1000 message as Number of Bankschangesis set to 3 and EL as 20s, with NB varies from 3 to 10. For each instance ofexperiments, the system is kept running until a total 1000 messages have beensuccessfully exchanged, and then the statistics are collected from 20 nodes. Thestats including number of messages exchanged related to the message deliverybut not one with the Ledger synchronization or record CoSigning. Also, thestats do not include the encryptions in formating OMSG, since every messagewill have such cost and eventually they will be canceled out.10.3 EvaluationAs shown in Figure 12 and Figure 13, the number of messages is growing linearlyas NC increases from 1 to 5, which is as expected since the total number ofmessages is related to NC due to the cost of Coin Exchange is proportional toNC. As for the number of encryption steps, this number grows super-linearly asNC increases. This growth is also within the expectation range since this costis also related to NC due to Coin Exchange and Coin Verification. In Figure 16,483 4 5 6 7 8 9·104Number of Banks(NB)NumberofEncryptionSteps#encryptionFigure 17: Number of Encryptions To Deliver 1000 message as Number of Bankschanges49Figure 17, Figure 14 and Figure 15, as NB and EL vary, there are no significantchanges in both number of messages and number of encryptions. This behavioris also the same as expected since, the cost of delivery is not directly related toeither NB or EL.The value of NC is the dominating parameter in OC in almost every part,although in some operations, the Banks are not involved in the messaging, butthe operations such as Coin Verification or record validation also requires NCtimes encryptions. The experiment does not cover the performance related tothe record CoSigning or Ledger synchronization, but it is obvious that NC isalso the key factor that affects the performance significantly. Therefore, in thefuture work, reducing the cost of the operations related to NC is the primaryalternatives to consider to improving the performance and the scalability.5011 Limitation and Future WorkOC’s communication model lacks some functionality that provide features forreliable, fast, and lightweight messaging delivery. Although the anonymousmessaging system always brings in more overhead to protect user’s privacy orsecurity, message delivery in OC introduce even more steps in order to integratethe currency system to provide just incentives for its users. While maintainingthe ability for the currency system to provide useful information such as currencystatus and authorized identities, there are overhead in different part of OC’sprotocol which either would introduce additional latency, or use extraneousspace such as keep the Ledger. In this section, these limitations are discussed andsome more features are proposed for future improvement consideration. Besidesthe limitations regarding communication, there are also limitations related tothe currency system, such as low utilization of Coins.11.1 Unidirectional MessageOC is considered as a messaging system that can only deliver a message tothe destination, and if the receiver node needs to reply to the sender, it willbe considered as another message delivery originated by the receiver node. InTOR, the communication tunnel is designed to be bi-directional based on TCPfor multi-purpose message delivery. For example, an HTTP request may besent by the sender through the circuit and its replies may come back using thesame circuit, which comparing to OC, makes TOR is convenient for differentforms of communication. This limitation in OC however is not related to thenetwork protocols chosen for delivering data, but due to the principle in OCthat every peer needs to "pay" for the service. Therefore, an instance typicalrequest-response communication has to be considered as two separate messagesdeliveries in OC to properly handle the Coin rewards.11.2 Delivery Failure DetectionOC should not be considered as a reliable messaging system since there is nofailure detection or correction protocols to try to ensure the success delivery ofa message. In OC, the sender of a message has no ability to detect the failureduring the delivery or the ability to confirm that the receiver has received thismessage. As proposed in the previous section, the intermediate nodes are ableto keep recording the status of delivered messages, and once the failure is foundby any of intermediate nodes, this failure status including the position of thebroken point can be reported back to the previous hops recursively till thesender node. This mechanism however is not adopted by OC also for that thisfailure detection can also be considered as a service which should require thepayment. Therefore, the future design regarding the failure detection will haveto consider embedding rewarding Coins in such status reporting messages inorder to provide incentives.5111.3 Performance as of a Messaging SystemIn terms of being a messaging system, the major functionality is to deliverand receive the message, and preferably secure and fast. In terms of security,OC has covered almost every aspect, such as data integrity, authenticity, andanonymity. However, the performance of OC is not as acceptable as the otherlow-latency anonymous messaging systems such as TOR. The performance is-sue also happens in TOR’s case for the same reasons, multiple hops, multipleencryption, and more network failing points. While due to the addition of cur-rency system in OC, the steps that cause longer latency are mostly expensivepublic key encryption/decryption to provide security protection. As describein Section 9.3, the additional cost for each hop on the communication path isstill constant but is greater than the ones in TOR. However, the cost for sendercan be significantly increased as NC goes up since each rewarding Coin has theoverhead of doing a Coin Exchange by the sender.11.4 Re-usability of a CoinAs defined in Coin Exchange protocol, a Coin CN0 can only be exchanged by itsowner N0 to another Coin with different ownership such as N1. However, afterthe Coin’s owner becomes N1, N0 cannot exchange it again although this N0deserves this Coin. This may cause the new Coin to be invalid if the new owneris no longer using the system, in which N0 loses a Coin and cannot get it back.Also, similar problem also happens during the Coin Exchange. By the designof protocol, N0 should present a valid Coin CN0 along with Raw Coin pieces toBanks, and whenever a Bank can verify that CN0 is valid, it may start CoSignprotocol to generate according CE record. This becomes a problem when thereare not enough Banks available in current epoch to help N0 to get a new Coin,the CN0 may also used by the Banks for generating CE to get rewards. As aresult, N0 loses CN0 since it has been marked as used and does not get a newCoin as return.However, this problem does not have an easy fix since this feature is also theone that ensures there is no linkage between a Coin’s previous owner and itsnew owner, and also ensures when the sender cannot cheat on forwarding nodes.For example, assume a Coin can be exchanged by any node holding it. In suchcase, after a sender S prepares the message M with valid Coins and send M tothe first intermediate node, S then can start to exchange those Coins wrappedinM . As a result, these intermediate nodes may still believe the Coins are validand provide help for the message delivery. In another case, assume that whenBanks receive CN0 from N0 requesting for an exchange, Banks have to waitfor a proof or notification from N0 indicating that N0 successfully gets enoughsignature from Banks and a new Coin is made. Nevertheless, N0, for its bestinterest, may not want to give such proof, so that N0 can still use CN0 and alsogets a new Coin. Such behavior would waste the effort of these Banks.5211.5 Features in Future WorkThe cost of maintaining the Ledger can be significantly high for that the contentof obsolete information on the Ledger is unlikely to be useful but still have tooccupy space to provide global consistency. This problem also occurs for otherBlock-Chain based system for verifiable source of transaction, yet in OC this maybe easier to solve since the full history of transactions is not always required.Another reason is that the number of Blocks is known based on the currentepoch number. The only type of record should remain on the Ledger is the RR,since RRs will always be used for Bank Selection and id authentication. As forCE and CR, as long as the rewards have all been collected by the CoSigners, thefull information of these records are not required in the future. Therefore, oneapproach can be applied to save the disk space when storing the Ledger. buildtwo separate Chains, one for RR only and the other for CE and CR. The RRChain remains using same way to maintain. CE and CR now can be expired sothat the old Blocks in the earliest epochs can be either compressed or trimmedto save space.In current version of OC, there is only one currency unit as Coin, and anypayments or earnings take exactly one Coin. The amount of work done thereforeis not proportional to its payment amount, which would cause unfairness insome situation. For example, the size of message varies significantly from one toanother, and sending these messages will consume different amount of resource.The "pay" and "gain" therefore are not proportional which cannot fully utilizethe incentives provided by the currency system. An obvious solution would beto introduce more currency units for finer payment amount arrangement. Thepayment and earning then can be varying according to the type of service andthe amount of resource required to finish the operations, such as size of bytesdelivered, encrypted, or stored. Two possible challenges when dealing withmultiple possible currency are (1) publishing the payment plan anonymouslyand (2) preventing the adversary correlating the amounts of payments to thecorresponding operations.5312 Related WorksThere are numerous proposed designs of system regarding anonymous communi-cation, and based on the primary technology used for security concerns, they canbe divided into following categories: Private Information Retrieval(PIR) based,Mixnet-based, Dinning Cryptographer(DC-nets), and protection on Network-level, in which some of these systems use a combination of multiple techniques.However, it is hard to compare OC with any of those systems since OC is pri-marily adjusted for the purpose to support currency system for incentives, andtechniques for ensuring anonymous communication has no difference from OnionRouting. Therefore, in the following sections, the features of these systems arediscussed to see whether they can be used to improve OC or whether the ideaof incentive can be applied in these systems, instead of comparing OC to thosesystem in aspects of performance and security.PIR-based systems [29, 30, 28, 27, 14] are primarily used to pull informationfrom untrusted database without exposing user’s identity and content retrievedwith high probability. In OC, the routing information of the other nodes arenot always publicly available or accurate in real time, hence sometime the peerdiscover is required. However, this procedure may also introduce potential leaksto adversary learning about one node’s intention by analyzing its recent queriesfor peers similar to the directory attacks in TOR. Therefore, PIR is a candidatetechnique to replace OC’s routing information retrieval protocol since the goalof PIR is to protect the content of the query from untrusted queried peers.DC-nets systems [19, 20, 21, 22, 31, 27] allow a group of users to exchangeanonymous message within the group using broadcast. Although DC-net wouldprovide stronger anonymity for its members yet in peer-to-peer environment,the cost to maintain all the group member for participation is expensive andthis assumption does not seem reasonable for improvising communication. How-ever, considering using incentive system to encourage peer to be more willingto participate could be the solution resolving such issue. Assuming a memberwould require spending coins for communication and for the other idle nodes,the presence of them would reward them with some coins. Some group membersin DC-net can simply participate to provide the covers to the other memberswho are actually communicating in order to earn the currency for future use,and the number of members in the group therefore may remain large enough toprovide strong security.In Mixnet-based systems [5, 6, 8, 9, 10, 11, 14, 15, 13, 3], a group ofmix nodes play as the relays to collect messages from users and then shufflethese messages and forward through other mix nodes till delivering to the finaldestination. The system topology and type of roles of nodes in Onion Routingsystem and Mixnet are very similar. The messages in both systems are beingre-directed multiple time to hide its real path from source to destination, andthere are nodes as intermediate mix to handle the re-direction of the messages.However, the Mixnet would provide stronger anonymity against traffic analysisattacks compared to TOR and OC, with the drawbacks that for Mixnet as amessaging system, each mix node will have to collect enough number messages54before sending towards next nodes, which could introduce much unnecessarylatency due to lack of activities in some periods of time. Therefore, Mixnet isbetter for the system that would wait for enough messages collected, such asanonymous voting system.5513 ConclusionIn order to address the "free-riders" issues in peer-to-peer anonymous messag-ing system, in this paper, a peer-to-peer anonymous messaging system namedOnionCoin is designed to support anonymous digital currency for incentiveswithout introducing extra potential security leaks regarding Onion Routing dur-ing the communication. The currency system is built upon Block-Chain basedglobal database called the Ledger to store currency transactions and the mem-bership information, and there are Bank Nodes acting at temporary authoritiesto perform currency-related operations. In the Ledger, a record requires to besigned by multiple CoSigners to prevent forging records.Several protocols are proposed for different security purposes in OC. OCadopts Onion Routing-like style for layered message encryption and communi-cation model using public keys from different selected users. A derived versionof this communication model is designed to provide rewards for the forwardingnodes while delivering the message without adding additional threats to theanonymity of communication ends. Also, a Coin Exchange protocol using Blindsignature to ensure the new ownership of the Coin is not known to any otherusers in OC. There is additional cost in performance of message delivery, inwhich there are about two more messages exchanged for each forwarding nodesand number of encryption steps added is quadratic to number of CoSigners.56References[1] Roger Dingledine, Nick Mathewson, and Paul Syverson. 2004. Tor: thesecond-generation onion router. In Proceedings of the 13th conference onUSENIX Security Symposium - Volume 13 (SSYM’04), Vol. 13. USENIXAssociation, Berkeley, CA, USA, 21-21.[2] Michael J. Freedman and Robert Morris. 2002. Tarzan: a peer-to-peeranonymizing network layer. In Proceedings of the 9th ACM conferenceon Computer and communications security (CCS ’02), Vijay Atluri (Ed.).ACM, New York, NY, USA, 193-206.[3] Jelle van den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich.2015. Vuvuzela: scalable private messaging resistant to traffic analysis.In Proceedings of the 25th Symposium on Operating Systems Principles(SOSP ’15). ACM, New York, NY, USA, 137-152.[4] Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zel-dovich. 2017. Stadium: A Distributed Metadata-Private Messaging System.In Proceedings of the 26th Symposium on Operating Systems Principles(SOSP ’17). ACM, New York, NY, USA, 423-440.[5] Chaum, D., Javani, F., Kate, A., Krasnova, A., de Ruiter, J., Sherman,A.T. and Das, D., 2016. cMix: Anonymization by high-performance scal-able mixing. 25th USENIX Security Sym-posium.[6] Chaum, D.L., 1981. Untraceable electronic mail, return addresses, and dig-ital pseudonyms. Communications of the ACM, 24(2), pp.84-90.[7] Jerichow, A., Muller, J., Pfitzmann, A., Pfitzmann, B. and Waidner, M.,1998. Real-time mixes: A bandwidth-efficient anonymity protocol. IEEEJournal on Selected Areas in Communications, 16(4), pp.495-509.[8] Danezis, G. and Laurie, B., 2004, October. Minx: A simple and efficientanonymous packet format. In Proceedings of the 2004 ACM workshop onPrivacy in the electronic society (pp. 59-65). ACM.[9] Wikström, D., 2004, February. A universally composable mix-net. In The-ory of Cryptography Conference (pp. 317-335). Springer, Berlin, Heidel-berg.[10] Danezis, G., Dingledine, R. and Mathewson, N., 2003, May. Mixminion:Design of a type III anonymous remailer protocol. In Security and Privacy,2003. Proceedings. 2003 Symposium on (pp. 2-15). IEEE.[11] Rennhard, M. and Plattner, B., 2002, November. Introducing MorphMix:peer-to-peer based anonymous Internet usage with collusion detection. InProceedings of the 2002 ACMworkshop on Privacy in the Electronic Society(pp. 91-102). ACM.57[12] Clarke, I., Sandberg, O., Wiley, B. and Hong, T.W., 2001. Freenet: A dis-tributed anonymous information storage and retrieval system. In Designingprivacy enhancing technologies (pp. 46-66). Springer, Berlin, Heidelberg.[13] Le Blond, S., Choffnes, D., Zhou, W., Druschel, P., Ballani, H. and Fran-cis, P., 2013, August. Towards efficient traffic-analysis resistant anonymitynetworks. In ACM SIGCOMM Computer Communication Review (Vol. 43,No. 4, pp. 303-314). ACM.[14] Sassaman, L., Cohen, B. and Mathewson, N., 2005, November. The pyn-chon gate: A secure method of pseudonymous mail retrieval. In Proceedingsof the 2005 ACM workshop on Privacy in the electronic society (pp. 1-9).ACM.[15] Danezis, G. and Goldberg, I., 2009, May. Sphinx: A compact and provablysecure mix format. In Security and Privacy, 2009 30th IEEE Symposiumon (pp. 269-282). IEEE.[16] Angel, S. and Setty, S.T., 2016, November. Unobservable Communicationover Fully Untrusted Infrastructure. In OSDI (pp. 551-569).[17] Gelernter, N., Herzberg, A. and Leibowitz, H., 2016. Two cents for stronganonymity: The anonymous post-office protocol. Proceedings on PrivacyEnhancing Technologies, 2, pp.1-20.[18] Chen, C., Asoni, D.E., Barrera, D., Danezis, G. and Perrig, A., 2015, Oc-tober. HORNET: High-speed onion routing at the network layer. In Pro-ceedings of the 22nd ACM SIGSAC Conference on Computer and Commu-nications Security (pp. 1441-1454). ACM.[19] Chaum, D., 1988. The dining cryptographers problem: Unconditionalsender and recipient untraceability. Journal of cryptology, 1(1), pp.65-75.[20] Golle, P. and Juels, A., 2004, May. Dining cryptographers revisited. InInternational Conference on the Theory and Applications of CryptographicTechniques (pp. 456-473). Springer, Berlin, Heidelberg.[21] Corrigan-Gibbs, H. and Ford, B., 2010, October. Dissent: accountableanonymous group messaging. In Proceedings of the 17th ACM conferenceon Computer and communications security (pp. 340-350). ACM.[22] Wolinsky, D.I., Corrigan-Gibbs, H., Ford, B. and Johnson, A., 2012, Octo-ber. Dissent in Numbers: Making Strong Anonymity Scale. In OSDI (pp.179-182).[23] Goel, S., Robson, M., Polte, M. and Sirer, E., 2003. Herbivore: A scalableand efficient protocol for anonymous communication. Cornell University.[24] Sirer, E.G., Goel, S., Robson, M. and Engin, D., 2004, September. Eludingcarnivores: File sharing with strong anonymity. In Proceedings of the 11thworkshop on ACM SIGOPS European workshop (p. 19). ACM.58[25] Soska, K., Kwon, A., Christin, N. and Devadas, S., 2016. Beaver: A De-centralized Anonymous Marketplace with Secure Reputation. IACR Cryp-tology ePrint Archive, 2016, p.464.[26] Kwon, A., Corrigan-Gibbs, H., Devadas, S. and Ford, B., 2017, October.Atom: Horizontally scaling strong anonymity. In Proceedings of the 26thSymposium on Operating Systems Principles (pp. 406-422). ACM.[27] Corrigan-Gibbs, H., Boneh, D. and Mazières, D., 2015. Riposte: An Anony-mous Messaging System Handling Millions of Users. IEEE Security andPrivacy.[28] Cheng, R., Scott, W., Parno, B., Krishnamurthy, A. and Anderson, T.,2016. Talek: a private publish-subscribe protocol. Technical Report. Uni-versity of Washington.[29] Kwon, A., Lazar, D., Devadas, S. and Ford, B., 2016. Riffle. Proceedingson Privacy Enhancing Technologies, 2016(2), pp.115-134.[30] Borisov, N., Danezis, G. and Goldberg, I., 2015. DP5: A private presenceservice. Proceedings on Privacy Enhancing Technologies, 2015(2), pp.4-24.[31] Corrigan-Gibbs, H., Wolinsky, D.I. and Ford, B., 2013, August. Proac-tively Accountable Anonymous Messaging in Verdict. In USENIX SecuritySymposium (pp. 147-162).[32] Castro, M. and Liskov, B., 1999, February. Practical Byzantine fault toler-ance. In OSDI (Vol. 99, pp. 173-186).[33] Kogias, E.K., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L. and Ford,B., 2016, August. Enhancing bitcoin security and performance with strongconsistency via collective signing. In 25th USENIX Security Symposium(USENIX Security 16) (pp. 279-296).[34] Eyal, I., Gencer, A.E., Sirer, E.G. and Van Renesse, R., 2016, March.Bitcoin-NG: A Scalable Blockchain Protocol. In NSDI (pp. 45-59).[35] Evans, N.S., Dingledine, R. and Grothoff, C., 2009, August. A PracticalCongestion Attack on Tor Using Long Paths. In USENIX Security Sympo-sium (pp. 33-50).[36] Jansen, R., Tschorsch, F., Johnson, A. and Scheuermann, B., 2014. Thesniper attack: Anonymously deanonymizing and disabling the Tor network.OFFICE OF NAVAL RESEARCH ARLINGTON VA.[37] Murdoch, S.J. and Danezis, G., 2005, May. Low-cost traffic analysis of Tor.In Security and Privacy, 2005 IEEE Symposium on (pp. 183-195). IEEE.[38] Sun, Y., Edmundson, A., Vanbever, L., Li, O., Rexford, J., Chiang, M. andMittal, P., 2015, August. RAPTOR: Routing Attacks on Privacy in Tor.In USENIX Security Symposium (pp. 271-286).59[39] Douceur, J.R., 2002, March. The sybil attack. In International workshopon peer-to-peer systems (pp. 251-260). Springer, Berlin, Heidelberg.[40] Chaum, D., 1983. Blind signatures for untraceable payments. In Advancesin cryptology (pp. 199-203). Springer, Boston, MA.[41] Diffie, W. and Hellman, M., 1976. New directions in cryptography. IEEEtransactions on Information Theory, 22(6), pp.644-654.[42] Nakamoto, S., 2008. Bitcoin: A peer-to-peer electronic cash system.[43] Wood, G., 2014. Ethereum: A secure decentralised generalised transactionledger. Ethereum project yellow paper, 151, pp.1-32.[44] Miers, I., Garman, C., Green, M. and Rubin, A.D., 2013, May. Zerocoin:Anonymous distributed e-cash from bitcoin. In Security and Privacy (SP),2013 IEEE Symposium on (pp. 397-411). IEEE.[45] Stoica, I., Morris, R., Karger, D., Kaashoek, M.F. and Balakrishnan, H.,2001. Chord: A scalable peer-to-peer lookup service for internet applica-tions. ACM SIGCOMM Computer Communication Review, 31(4), pp.149-160.[46] Zhao, B.Y., Kubiatowicz, J. and Joseph, A.D., 2001. Tapestry: An infras-tructure for fault-tolerant wide-area location and routing.[47] Maymounkov, P. and Mazieres, D., 2002, March. Kademlia: A peer-to-peerinformation system based on the xor metric. In International Workshop onPeer-to-Peer Systems (pp. 53-65). Springer, Berlin, Heidelberg.[48] Heilman, E., Kendler, A., Zohar, A. and Goldberg, S., 2015, August.Eclipse Attacks on Bitcoin’s Peer-to-Peer Network. In USENIX SecuritySymposium (pp. 129-144).60


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items