PacketCrypt

PacketCrypt Caleb James DeLisle (​[email protected]​) Vishnu Seesahai (​[email protected]​, ​[email protected]​) Abstract Since proof of work was popularized by the Bitcoin project, there has been active research into ways to make Proof of Work (PoW) useful. Unfortunately it has proven remarkably difficult to make PoW serve humans without allowing miners to influence the nature of the work problem to their own advantage, destroying the fairness of the algorithm. PacketCrypt takes a different approach, while the work done by PacketCrypt itself is not useful, PacketCrypt attempts to make the PoW very similar to useful work so that research and development into technologies for efficiently mining PacketCrypt will be reusable for other purposes. PacketCrypt encourages the development of technologies for high speed encryption of internet traffic, it also contains a component using randomly generated code in order to encourage CPU mining and research on highly parallel CPUs. Most importantly, PacketCrypt is parallelizable with n-to-n communication, making it a bandwidth hard proof of work. 1. PacketCrypt Protocol Overview steady supply of fresh announcements, thus creating The PacketCrypt protocol consists of two distinct the demand for bandwidth. stages, in the first stage (“announcement mining”), the miner executes a CPU-hard algorithm which 2. PacketCrypt Algorithm creates 1KB proof (called an ​announcement​), then in PacketCrypt is an algorithm which takes input data the second stage (“block mining”) the miner (for example of a block header) and a list of data pre-commits a merkle root of collected items (in the block mining stage, the data items are announcements and then executes a memory-hard the announcements) where the merkle root of that list proof of work algorithm which accesses random has been committed in the input data. It accesses 4 announcements from that set. Upon finding a items from the list (determinant random based on the “winning hash”, the miner presents the items and input data) and then outputs a hash of the announcements which were accessed in that cycle as input data and the 4 items. It also outputs a proof well as merkle branches linking them to the containing the 4 data items from the list and a partial pre-commitment, and statistically proving that they merkle tree allowing the verifier to prove that those had as many announcements as they claimed to have. items existed at the given positions in that list. This presentation is referred to as the PacketCryptProof and is needed to prove that the Verification of the resulting proof consists of using work was done. the partial merkle tree to build a sparse list with only those 4 data items and then repeating the process of The amount of work which the block miner needs to hashing. If the PacketCrypt algorithm requires a data perform is reduced based on the amount of item which is not present, the verification fails. On announcement work in the pre-committed set of success it results in the same hash which was announcements. But effective announcement work produced by the original mining algorithm. decays as time goes on so block miners require a When searching for a partial preimage, as is done in This is a total of 31 encryption attempts, which cryptocurrency mining, the PacketCrypt algorithm compared to 1*5, the case where all memory is must be run millions of times over, each time it is available, requires 6.2x the CPU usage. run, it must access data items from the list, making the result an effective proof that the data set was There is also another type of TMTO which we’ll call present in the miner’s memory at the time that they a ​regenerative TMTO because it is based on were mining. regenerating the data which was discarded. Scrypt, one of the earliest works on memory hard functions, A. What is a time memory tradeoff ? has a ​regenerative TMTO which requires only 17% A time memory tradeoff (TMTO) describes the increase in processor time to halve the memory. This “price” in CPU processing time of reducing memory issue has since been formalized1 and is the main consumed in computing the solution to a particular reason why ASIC Litecoin miners are able to problem. While TMTOs can take a number of dominate. different forms, we will concentrate on two in particular. While the properties of the ​probabilistic TMTO are clearly understood for PacketCrypt, the ​regenerative An obvious attack against the block mining stage of TMTO is, for PacketCrypt, dependent on the the PacketCrypt protocol is to throw away difficulty of generating the data items themselves. announcements or lie about the number of Therefore, as long as it takes CPU power to create a announcements which you have. Suppose you wanted data item, we can form a unified definition of to pretend you had twice as many announcements as time/memory effort used for PacketCrypt. If we you really had: Every time you perform a hash conjecture that we have identified all of the operation which seeks an announcement that is degenerate cases, we can informally prove that there missing, you simply try again. This is what we will exists no method of mining PacketCrypt hashes call a ​probabilistic TMTO​, because it is based on which is more advantageous than the best one which faking data in the hopes that it will not be needed. we identify. PacketCrypt requires 4 dependent memory accesses B. Hash Algorithms Used so the chance that you can mine with half of the data The PacketCrypt algorithm uses chacha20/poly1305 missing is 1 in 16. The choice of the number 4 is encryption algorithm to encrypt a 2048 byte buffer intended to avoid excessively bloating the size of the multiple times over, while copying each data item PacketCryptProof while still significantly penalizing over the first 1024 bytes of that buffer in each cycle. the exercise of the TMTO. It’s tempting to think that At the end of each cycle, the poly1305 authenticator needing to make 16 hash operations means one needs and part of the encrypted data as the key for the next to perform 16x the CPU effort, but because encryption cycle as well as for the index of the next PacketCrypt performs the memory lookups data item to access. While this choice of algorithm is sequentially, one is able to bail out part way through clearly unorthodox, the objective is to encourage the the hash operation. As a hash operation consists of 5 development of technology which works for steps with 4 memory lookups in between, the steps encrypting and sending messages of about the same which must be performed to test 16 possibilities with size as an internet packet. 50% of the memory missing are: 8*1 (fail in the first cycle) + C. PacketCrypt as a Broadcast Network 4*2 (fail in the second cycle) + PacketCrypt can be used to form a gossip-based 2*3 (fail in the third cycle) + broadcast network, where anyone can broadcast a 1*4 (fail in the forth cycle) + message as long as it contains a minimum amount of 1*5 (success) proof-of-work. In fact, any type of announcement can 1 ​https://eprint.iacr.org/2015/430.pdf be sent on this broadcast network. An announcement is created by a participant in the network who wants Parties who want to broadcast a message across the to get their message heard by a large number of other network will be able to do so by crafting an participants. Miners collect announcements into what announcement and mining it themselves before we will call an AnnouncementSet which is then used releasing it with some work done on it. The layout of for memory hard mining. By collecting an announcement message is as follows: announcements from network participants, a miner is able to get a discount on the proof of work which they must perform, effectively outsourcing some of the mining effort to those making announcements. Version uint8 Version number, currently 2 SoftNonce [3]byte Nonce used for mining, can be changed without regenerating the mining dataset. HardNonce [4]byte Nonce used for mining, any change requires regenerating the mining dataset. WorkBits uint32 Bitcoin format compact representation of the max hash for this announcement ParentBlockHeight uint32 Number of the most recent block at the time this announcement was made UserDefined [40]byte Data which can be decided by the announcement miner SigningKey [32]byte If this is non-zero, the announcement must be signed with this ed25519 key when it is included in a block. MerkleBranch [14][64]byte A branch proving one of the elements in the announcement dataset. LastItemPrefix [40]byte First 40 bytes of the last item in the dataset. Table 1: This table shows the layout of an announcement. The colors show the point in the announcement hashcash mining cycle when the parts of the announcement are committed. MerkleBranch and LastItemPrefix are not committed at all and are only attached to the announcement as proof, SoftNonce is used in the hashing process but is not committed when building the dataset, the rest of the elements are committed (along with the hash of the block at ParentBlockHeight) when constructing the dataset. is hashed again with the Merkle root (again with a. Announcement Hashcash SoftNonce zeroed and MerkleBranch and The instance of PacketCrypt used for hashing the LastItemPrefix omitted). Fourth, the announcement individual announcements is somewhat special. First mining begins, with SoftNonce advanced to try each a hash ​h0 is created by hashing the announcement new hash. When a hash is found which meets the along with the block header hash of the most recent requirement in WorkBits, the Merkle branch of the block, when performing this hash, the SoftNonce, is forth data item is placed in MerkleBranch and the zeroed and HashBranch and LastItemPrefix are first 40 bytes of this item are used to pad out the end omitted. Then ​h0 is expanded into an array of 2​13 of the announcement, filling LastItemPrefix. 1KiB items (8MB) by generating a RandomHash program (explained further below) and executing it Verification is similar but with less memory needed, 2​13 times. Third, a Merkle tree is built from that array the announcement is hashed as before but instead of of items using 512 bit blake2b and the announcement creating an array of 2​13 items up-front, the items are created as needed during the PacketCrypt cycle. The way the batch limit is applied is by constraining When the 4th item is reached, its hash and index is the range of SoftNonce, but since the difficulty of validated against the HashBranch entry and the result winning an announcement is variable, the range of of the PacketCrypt cycle is compared to WorkBits. SoftNonce must also be variable. The range of SoftNonce is 0-1024 if the hash target is at the i) GPU and ASIC frustration minimum (every second hash is a winner), but for While the PacketCrypt block mining algorithm is every halving of the hash target, the maximum largely intended to work on any hardware which can SoftNonce doubles, keeping the expected number of encrypt and move data quickly, the announcement valid announcements stable at 512. hashcash is designed to prefer the unused CPU cycles of existing hardware which is geographically b. Announcement rules distributed. While we acknowledge that In order to be valid, an announcement needs to CPU-preferring algorithms carry a higher risk of contain two commitments: ASIC implementation, we prefer CPU for the announcement hashcash because bandwidth is only 1. The hash of the most recent block at the interesting if it actually goes somewhere and it would time the announcement was created be largely self-defeating if announcement miners and 2. The amount of proof of work which the block miners all placed their equipment in announcer intends to perform (target hash), datacenters, or worse, colocated it in the same this is specified in WorkBits. datacenter to eliminate transit costs. An announcement will only be valid for inclusion in For the announcement mining, the addition of the a block at height ParentBlockHeight + 3. The choice RandomHash is intended to maximally frustrate of 3 is to allow one block period for network GPUs and ASIC implementations. RandomHash participants to mine an announcement, one block constructs a random “program” made of a set of period for them to broadcast it across the network, instructions that do a sequence of math, logic and and the third block period when miners stop branching operations. This favors the flexibility of accepting new announcements because they’re general purpose processors over GPUs or ASICs. mining. After block number ParentBlockHeight + 3, the value of the work done on an announcement ii) Announcement batch limits halves each block following, this is done to ensure If an announcement miner is allowed to create too that block miners must continuously mine or many announcements with the same dataset, the download fresh announcements. This decayed announcement miner is able to avoid expanding valuation of announcements is referred to as ​effective bandwidth sending them all to the block miner work.​ After the amount of ​effective work decays because instead they can simply send the entire below the minimum allowable work, the dataset plus a compressed representation of the announcement is no longer usable in any capacity. winning SoftNonces. c. Compact proof To prevent this, we limit the number of winning Since the AnnouncementSet can be many gigabytes announcements to around 512 per batch. The reason in size, it is unacceptable to include the entire set for the choice of 512 is because the merkle tree of all with each block. Because the PacketCryptProof 2​13 items in the dataset is 1MB which is twice that of provides a random sample of the AnnouncementSet, 512 announcements, providing a reasonably we can verify any property which we expect all comfortable margin given the recipient needs merkle announcements to have, with the same confidence as branches and also a 40 byte prefix of one of the our belief the miner is not using ​probabilistic TMTO.​ actual data items to reconstruct the announcements. For example, if we insist that all announcements must begin with the letter “A”, it does a miner no more good to mine an Announcement set where one announcement starts with a “B” than he does to omit ● block_miner_work is the amount of that announcement entirely. memory-hard work done by the block miner ● min_ann_work ​is the lowest amount of We can therefore require announcements to contain a effective work that is done for any of the minimum amount of CPU work by requiring the announcements in the AnnouncementSet block miner to specify the minimum work of any ● global_work is the product of announcement in his AnnouncementSet, in his block_miner_work times coinbase commitment. The verifier checking that the ann_min_work times the ​ann_count 4 announcements provided with the squared PacketCryptProof will also verify that he adhered to And the work is valid if the global work is greater this commitment. than or equal to the cube of the difficulty as specified in the block header. The announcement count is d. AnnouncementSet rules squared because first it is multiplied by the For a miner’s block to be valid, all of the ann_min_work to compute the effective value of announcements which they provide in their announcement mining effort and then it is multiplied PacketCryptProof must also be valid, furthermore the again to add a secondary equal weight to bandwidth Merkle tree of the announcements in the usage. PacketCryptProof must match a merkle root which is committed in the coinbase. Also in the coinbase, 3. Participant behavior modelling there must be a commitment of the minimum We will now attempt to reason about the behavior of announcement ​effective work (henceforth participants in the network. We will start with the min_ann_work​) and all announcements in the incentives facing network participants and then finish PacketCryptProof must have at least this as their by discussing the miner’s incentives and the minimum required hash work. Finally of course, the incentives which affect both roles. work done by the block miner must be valid according to the target as defined by the blockchain A. Announcement miner incentives consensus rules. However, the amount of work Looking at existing cryptocurrencies and the expected of the block miner is based on the amount emergent ecosystems around them, we can enumerate of announcements that they have, so the computation a number of different activities which network is not straight forward. This global difficulty is participants will want to engage in. defined as follows: ● Transfer of cryptocurrency Work(hash) = (2**255 / hash + 1) ● Making and responding to OTC market block_miner_work = Work(packet_crypt_hash) offers min_ann_work = MIN( ● Communicating the quality of their network for_each ann in ann_set: links in order to be able to sell bandwidth Decay(ann.target_work) leases. ) ● Participating in mining (e.g. in a mining global_work = block_miner_work * pool) min_ann_work * ● Broadcast novelty messages (ann_count ** 2) The transfer of cryptocurrency is perhaps the most work_is_valid = simple case because it is fulfilled by the blockchain global_work >= Work(block_header.nBits) ** 3 and lightning network operating in their normal capacity. All other objectives can be achieved In words: through the use of announcements. a. Types of announcements potentially to be positive, as they create incentive for There is no technical limitation against an miners to use more bandwidth than they would have announcement containing any type of data, but we otherwise. We can imagine such applications as chat can will attempt to predict the general types of or microblogging to be built on top of novelty announcements which will be in common use. We announcements. predict that announcements will take 4 general forms: iv) Mined announcements ● Network state updates Mined announcements are announcements which are ● Market offers created for the sole purpose of assisting miners in ● Novelty announcements winning a block. Unlike any other type of ● Mined (empty) announcements announcement discussed, the announcer does ​not want the announcement to be received by as many i) Network state updates network participants as possible, he rather wants it to These are announcements which communicate be received by a miner who will pay him for it. changes in the quality and amount of available network bandwidth on a particular link. Participants A mined announcement will normally tend to have no in the network may send them to maintain a good user defined data order to save bandwidth by reputation by maintaining clear communication with compression. those who have leased access to their bandwidth as well as those who might lease access in the future. b. Announcement cost and demand The amount of cost which a network participant is ii) Market offers willing to incur in order to send an announcement is While the Lightning Network provides a convenient defined by what is effectively a market for bandwidth way for network participants to make OTC on congested links. As long as there is no network exchanges, there remains a need for discoverability of congestion, the cost to an announcer converges on the available offers. The announcement system provides minimum that is valid for an announcement to be a fully decentralized way for market offers to be forwarded. When some links in the network begin to exchanged without any kind of “exchange” to become congested and nodes begin to prioritize coordinate them. The most obvious type of offer which announcements they forward, the cost to the which will be exchanged is the offer of a network announcer grows to the market rate for reaching the bandwidth lease but we foresee the emergence of subset of nodes who are behind congested links. many different types of assets being exchanged in Because participants have different priorities, we emergent OTC markets. expect announcements to bear a wide range of different amounts of work. iii) Novelty announcements From the history of arbitrary data in the Bitcoin B. Block miner incentives blockchain to applications like Cryptokitties, it With ​block_miner_work​, ​min_ann_work and should be clear by now that anything which ​can be the square of ​ann_count all multiplied together, we used to broadcast arbitrary messages to the world, expect miners expend effort on whichever number will be. Participants who send novelty data act for can be raised by a given percentage most cheaply. their own amusement and thus do not act in ways considered economically rational. At times they are The cost associated with ​min_ann_work rises prepared to spend many times what a rational actor linearly with a rise in ​ann_count because each would spend for the same service for its intended use. announcement in the set of size ​ann_count must bear at least ​min_ann_work​ proof of work. Because announcements are not stored in the blockchain, we consider novelty announcements The cost of increasing ​block_miner_work rises unlikely to have any negative consequence and with ​ann_count as well, but as a function of memory bandwidth and capacity. For example, if the size of the announcement set is less than half the size of the memory used to store it, ​ann_count can be doubled with a relatively low impact on the cost of mining the announcement set. However, if the announcement set is near to the limit of a cache or memory size, the cost of expanding ​ann_count even slightly could be more than an order of magnitude. A miner who is collecting announcements from the network will be incentivised to choose from all announcements which he knows of, subset for which min_ann_work * ann_count ** 2 is the greatest, henceforth known as the ​best subset.​ a. Mining announcements When increasing ​min_ann_work * ann_count ** 2 is cheaper than increasing block_miner_work​, a miner will tend to begin mining the announcements or paying someone else to do it. This will tend to happen when the value of the block reward is more than double the work value of the ​best subset​. i. Changing the best subset When the savings in memory and bandwidth cost difference exceeds the value of the lowest value announcements in the ​best subset,​ miners are incentivized to mine announcements with more than the least possible work, in order to increase the min_ann_work​ of the best subset. 4. Conclusion Here we documented the PacketCrypt proof of work algorithm which is designed to be bound by both memory latency and network bandwidth between participants. We reasoned about a number of potential failure modes and we considered different use cases of announcements and how users might affect the network in different ways. The code for this algorithm can be found at: https://github.com/cjdelisle/PacketCrypt/ and is currently implemented in the PKT cryptocurrency (​https://pkt.cash​).  PacketCrypt2 Announcement Hash Data flow Legend Message HardNonce LastBlkHash SigningKey Input Data Computation State MerkleHash Ann Header Data flow 2-way (table lookup) Data flow only if hash found RandHash + 8MiB Pre-Dataset CryptoCycle Announcement Item0 Item1 Encrypt Item2 MerkleTree Root Item3 GetMerkleProof ... Item8191 softNonce RandHash + CryptoCycle 2 KiB state 8MiB Dataset Lookup CryptoCycle Item0 Item1 Lookup CryptoCycle Item2 Lookup CryptoCycle Item3 ... Lookup CryptoCycle Item8191 ResultHash CryptoCycle