Tag: Coursera

This lecture brought out a completely new topic of prediction markets. It made the case for why alternative coins may be necessary who had be built to solve different problems and allow for newer solutions.

• Can real world data be brought into Bitcoin?
• What is a prediction market?
• What parts of prediction markets can you build on Bitcoin?
• What about an altcoin?

Real World Data Consequences

Getting real world data opens the door to sow many new applications. The main topic is getting a mechanism to assert real world events. Once you get this into the system, the lecturer mentioned bet and hedge results using smart contracts (programmable pieces of logic) and opens the door to more complex financial products like forwards, futures, and options on Bitcoin. The general formulation is known as prediction markets though.

Prediction Market

A prediction market is pretty straightforward. It’s a market where you can trade shares in a potential future event. Shares are worth some money if the event happens, and zero is not. The current price / x = estimated probability. Before the event, the price may fluctuate based on people’s expectation of the end result. The lecturer spoke about two examples the World Cup 2014 and the 2008 Election between Obama and McCain. Thus as the tournaments progressed the markets changing belief of the winner impacted the probability. The key element that differentiates pure betting, is that one can trade even prior to an event happening. Thus over a hype cycle you can profit and short sell quickly and exit prior to the event even occurring. However, in the long term they will have accurate results.

Thus prediction markets are loved by economists since they reveal all the knowledge about the future. In addition, they allow for profit from accurate predictions and end up beating experts claims. Not sure I believe the bottom quote, but it definitely reveals the confidence placed in prediction markets.

“The most heeded futurists these days are not individuals, but prediction markets, where the informed guesswork of many is consolidated into hard probabilities…The Economist: The Future of Futurology    

Intrade

Intrade was a prediction market company that did all this in a more centralized way. It was founded in 1999 and was a web-based prediction market company. They allowed members to take positions (trade ‘contracts’) on whether future events will or will not occur. The company ran into several regulatory issues in the United States even though it was a Ireland based company. So much so that in 2012, the CFTC filed a civil suit again them for unregulated trading of commodities. In 2013, they had to suspend trading for US investors. Finally, in 2014, they closed shop. Interestingly, their website actually points to a decentralized exchange known as Augur which is built on an Ethereum, an altcoin network. That’s wild in my eyes as really this lecture from 2015 kinda projected the future of this space.

Decentralized Prediction Markets

Bicoin or other public blockchain provide that decentralized service.

• Decentralized payment and enforcement
• Decentralized arbitration
• Decentralized order book

Decentralized payment

This requirement is the easiest according to the lecturer. This can be achieved by Bitcoin and trusted arbiters. Escrow transaction can exist.

Decentralized Arbitration

The alternative would be to use an altcoin that had built in support for arbitration. The lecturer then describes the mechanism for some of the custom transaction types. There should be a BuyPortfolio and SellPortfolio. Lastly, there would be a TradeShares() where you can exchange shares for each other or currency. This means that you essentially buy a share in every possible outcome. Then you would trade the shares to reflect your beliefs on the future outcome. Arbitration has its own mechanism as well. With Bitcoin, you could use trusted arbiters mean that allows anybody to define and open a market and the risk of an incorrect arbitration would be absconding. Users essentially vote which requires incentives. Thus the users are would vote on the outcome thereby tying they a sufficient number of them were honest. This may not be as easy if there was collusion or something. Miners who vote may be disinterested though. Note sure why we’d ask them to take on this role.

There is a company who did this known as Realitykeys, a certificate authority for facts. I think the company is now called Realit.io. Essentially one can sign information on Bitcoin or on Ethereum. Realitio verify real-world events for smart contracts and provide some guarantees. From there website it looks like they’re a decentralized application that can answer questions.

Decentralized Orderbook

An orderbook is a data structure that separates bids and asks while a matching engine actually matches the best bid and ask offers together. it allows the orders to be matched up or split the difference. Usually if there is a space, some party known as a market maker may step in to help facilitate the trades. Centralized order books have issues in that there could be front-running in that someone gets more information about the buys and sells and artificially can profit from this information. Thus they also require regulation, auditing, and monitoring.

Decentralized order books have slightly different issues. You give the orders to miners, and they match any possible trade. The spread is retained as a transaction fee by the miner. The spread is greater than the transaction fee and thus not profitable for the miner. Front running is not considered profitable. Overall, the system may be less efficient as there will be high fees and slower trades.

Wrap-Up

Overall much of this lecture has actually been done in reality. Gnosis and Augur are two examples of prediction markets that live on the Ethereum blockchain. As mentioned this lecture served more as a segue to discuss some of the limitations with Bitcoin and open the door to new possibilities with these alternative chains.

The goal of this lecture was to give examples on how bitcoin could be used as a public randomness protocol. This lecture builds on the previous such that instead of each person generating their own randomness and combing it together, you have more convincing randomness to the public.

• What is public randomness?
• What are examples in the real world of public randomness?
• What is the NIST beacon and Bitcoin beacon?
• How can Bitcoin be used as public randomness?

Public Randomness

Public randomness in cryptography seems to not have been formally introduced until 1992. Randomness is super useful to create simpler, or more efficient algorithms. It’s also useful in the construction of cryptographic primitives. Public randomness seems to mean that the random bits are accessible to all parties enacting the primitive and to any adversary trying to break the primitive.

The proper definition I found from this paper, Public Randomness in Cryptography is “A source of random bits is public for a primitive if it can be read by all the parties enacting the primitive and any adversary trying to break the primitive. The public random string is always chosen uniformly. This line from the paper, i found a bit contradictory, “Although the public random bits are known to an adversary, it turns out that these bits often plays a crucial role in ensuring that the primitive is secure”.

NBA Draft Lottery

The lecturer then transitions to talking about the NBA draft lottery. Honestly this was completely irrelevant segment though highly entertaining. 30 teams come together and randomly choose some weighting based on teams past performance the year prior who has first pick to draft top amateur player in the country. This began in 1985 with the Knicks getting Patrick Ewing. Prior a coin toss was used to get the first pick. Apparently people saw this as a conspiracy and that it wasn’t truly random. I google “conspiracy theory Knicks Patrick Ewing” and have shared some of the results. There was some deliberation over the envelope could have been tampered with. It’s strange that May 14, 2019 many of the news media posted new articles about this, guessing this was due to an anniversary of sorts. It’s interesting that the entire draft lottery was actually full televised as the NBA were trying to get publicity. The lottery is still done every year and people still cal foul but perhaps not to the same degree as 1985.

• Frozen Envelope
• Sports Illustrated Account
• More NBA conspiracies

1969 Vietnam Conscription Lottery

This was a higher stakes lottery though isolated to the United States as before. The lottery was to determine which men would be sent off to ware with Vietnam. Congressional people dropped all dates  in blue plastic capsules into a metal drum and took turns reaching in to remove blue capsules out. Based on the date drawn, it would indicate priority of being conscripted. These numbers wold be broadcast on live TV and radio broadcasts to share with the American public. That to me seems terrifying. This was seen as fair as birthdays were being chosen at random.

Though looking at the results, it was unfortunately botched. Birthdays that were late in the year had lower priority than those found earlier. The cause was explained how they were rotating the drum and even number of times so that the capsules initially put on the top were still more likely to be picked.

Cryptographic Beacons

The two example showed that this problem is actually needed. Getting the public onboard is difficult and people will always come out if they don’t think its fair. This reduces to a more abstract idea.

The idea is cryptographic beacons, which is a service to regularly publish random data As discussed above, it must follow the features of public randomness. Thus the applications could help for lotteries, auditing, ZKP, and cut and choose protocols. The beacons must be cheap, easy, and simple to understand. Though it’s difficult to make this trustless. So the public lottery may not work remotely and distributed, and thus the lecturer provides some modern day solutions

NIST Beacon

NIST does something similar where they have quantum-mechanical randomness that they give to the public. Interoperable Randomness Beacons is what’s on their website and was started in 2011. In 2019 they have a reference for randomness beacons that they’ve published. I’ve provided the diagram reference similar to what the lecturer showed: https://www.nist.gov/image/belltestillo900png. I don’t know what a loophole-free Bell test but that’s what the NIST beacon uses. Full taken from wikipedia, “Bell’s theorem, also referred to as the Bell inequality or Bell test in actual experimentation,^[1] proposes a testable construct for resolving the disparity in causality and locality that exists between quantum mechanics and classical physics models, specifically the concept of quantum entanglement.” Every 60 seconds they publish random data (512 bit) and sign it. Downside to trying to use this, is that one must trust NIST. They could be lying to you… was the one con for this. It’s interesting they have a warning on their website about WARNING: Do NOT use Beacon generated values as cryptographic secret keys! This is line with the the lecturer as you want ot use the public randomness for other mechanisms but not secret key generation.

Natural Phenomena instead

Thus the idea is instead of using one person who needs to be trusted to produce data, one uses natural phenomena instead. Examples of natural phenomena were sun sports, cosmic background radiation, and weather data. Because they can be read all over the world publicly, these are observable but also random data that nature produces. The issues the lecturer brought up was that this data was slow and needed a trusted observer as collecting this data isn’t that easy.

Stock-market beacon

Thus the next idea is to use stock market prices as a beacon. Prices are generated regularly, and the claim is they are costly to manipulate. Though, there could be slow insider attacks though. This was fairly short section and I could only find one academic source about this. The paper covered that these random bits were sound for post-election audits in E2E elections so there was a very specific use case for this data.

Remove central trust: Bitcoin nonces

Nonces are somewhat random. Thus minders finding the random nonce could be that source of randomness. One benefit is these nonces are found every 10 minutes and published pubicly to all miners. At this point, there is no way to predict the next nonce with significant probability as that would give people a mining shortcut. Current there are about 66 bits of randomness which is difficult to predict. Then we discuss how this acually works.

Using the blocks to become a beacon isn’t too difficult. Each time a block is published, the block header data is run through an extractor function that essentially hashes all the data into a unique output. This unique output is a uniform string which anyone could compute. Then we examine the potential security vulnerabilities. The vulnerability would depend on the cost of manipulation which is this case would be the block reward. The attack vector would be manipulating a miner to either throw out a computed block or nonce and not get their block reward. Thus you don’t want to use this randomness beacon on say a NBA lottery where its impact is more expensive then an outputted block reward. The cost of manipulation was pretty simple match.

Bernoulli Trial: forcing a beacon outcome with probability p requires discarding 1/p-1 blocks and discarding a block costs the block reward (12.5 BTC). Thus for an N-party lottery it’s (block_reward) (n-1).

The downsides are those key features to BTC. Timing is slightly imprecise as every 10 minutes isn’t actually true. If you’ve ever looked at block times leading up to or after a fork they tend to fluctuate. Also, this way of randomness is only temporary. As the block reward halves at each section, the randomness mechanism will likely only to be done for cheaper and cheaper lotteries. That said, it could be useful and at least provides a manner of how a public blockchain could be used.

Beacon support using Bitcoin script

New idea is chosen to try to resolve the previous constraints. This one adds an opcode to BTC for a beacon call. The advantage is that it can build multi-party lotteries in only one round without any bonds and no time delays for refunds. So this beacon call would use the previous block’s randomness within its input.

• Real world lottery
• Doing a trust less lottery
• Hash Commitments
• Timed Hash Commitments

Setup offline

As always there are two parties, Alice and Bob who want to take a bet with each other over a fair coin toss. There are two parts. First Alice mentions a price and determines if Bob is interested. Bob accepts and then takes a side usually when the coin is in the air. There are a lot of assumptions to ensure fairness and there is trust that the loser will pay. The goal of this lecture is to describe a way to run an online lottery without trust.

Online lottery without trust

Thus it’s a similar setup in that there are two parties but these parties are connected along a network such as the internet. However, there are several reasons that the offline approach will not work. Because both Alice and Bob are remote, it’s more difficult for each of them to verify the fairness of the coin flip. In addition, final payment requires more setup to ensure that the loser just doesn’t walk away and not pay. Lack of trust hurts these setups.

Alice and Bob want to bet on a coin flip remotely.

The solution that the lecturer brings up is hash commitments. A hash commitment allows one to store a fixed value that is know but hidden and later reveal it without modifying this fixed value. There are specific characteristics for publishing some commitment of x. Thus inputting x essentially reveals the commitment at the end.

1. Can’t find an x’ != x later such that H(x’) = H(x)
2. H(x) reveals no information about x assuming the space of possible is bug.

Hash Commitment lottery – 2 Phase

Thus we now have a new example. There are three parties: Alice, Bob, and Carol and each choose a random number, nonce, respectively x, y, z. Each person must keep this random number to themselves and in round one each will publish some hash using their nonce. By the one-way uniqueness property, publishing the hash of their nonce reveals zero information about their actual nonce. Later the participants will reveal their actual nonce values. Finally, to determine the winner, a function can take in x, y, and z put it into another hash that is known or XOR can be done. This value can then be mod’d by the number of participants, 3 to find the winner. Now we can reason why this solution works.

Everyone can run through the protocol themselves. They guarantee that no one could have lied about their x, y, and z values since in round one, each person had committed the one-way hash result. Thus each person can run the hash function to ensure these values lined up. Furthermore, the final reveal part to get the mod value can also be checked. Because all these functions are known prior to the final run, a participant can choose not to submit their input because they know they’re guaranteed to loser. Thus, this schema is insufficient by itself to create this trustless lottery. Now we are introduced to a slightly better schema, timed hash commitments.

Timed Hash Commitments

As obvious, given this entire lecture are giving uses for bitcoin, use bitcoin blockchain. A timed hash commitment requires that x must be revealed by a certain timestamp. A transaction gets created in a multisig script that will pay the entire bond to one party either if the time expires or the revealed hash indicates a different behavior. Thus if Alice determine she will lose and thus does not participate, Bob can still withdraw funds. Thus the loss to Alice should equal how much she may have won with the lottery. Similarly, the same schema can be used with Alice, Bob, and Carol with each person using a Bond. Unfortunately, ti’s time complexity and bond issue may make it more difficult.

This lecture brought bitcoin into the real world space, or meat space as some call it. In that these unspent UTXOs can represent something else.

Questions answered in this Post:

• What characteristics allow calling it “smart property”?
• What does it mean bitcoin has a trace history?
• What is one example of authenticating bank notes?
• What are colored coins?
• What are some applications using Bitcoin? What is Namecoin?

Transfer of Value

Bitcoin is a transfer of value has definitely stuck. The phrase holds weight to many circles. While the real owners may be anonymous, it is possible to track the transactions of bitcoin throughout time. Even more companies like Chainalysis and Ciphertrace because of their ties to exchanges and crypto trading exchanges know the identities of the bitcoin holders. Likely you can track an unspent UTXO all the way back to when it was minted. It’s public and anyone can view.

Trace History

Thus the lecturer brings up the point, bitcoin is actually unique. While value may be fungible current, each unspent transaction output in unique. Though if there is some reason that one history can separate it from another, perhaps they are no longer fungible. This is a negative for anonymity which isn’t new and allows for bitcoin blacklisting. Though this trace history can open up in opportunities for applications. You could make the argument that same thing holds true for certain fiat currency. A U.S. two dollar bill may be worth more than two dollar due to the rarity of the items. Similar remarks can be made for a silver dollar and certain pennies minted in specific years.

The lecturer brings up the point that without limitation or issuance, it is just a novelty which is true. Having a forged signature by a famous actor may hold the same value as real signature, as it is difficult and requires expertise to tell the difference. Having the claim authenticated is how one would add real value ie authenticated metadata for currency.

Using bank notes for baseball tickets

The idea is pretty simple. Venues can mention a specific serial number could give permission to anyone entering an event. In the slides, Bill #L11180916G stands for given entry to a Yankees game in 2014. To add validity, there can be a signature signed with a message and game number. Thus you’re now assigning more value to something that may have had intrinsic value.

Consequences

The consequences are pretty wide. Currency can now represent some thing else. In addition, anti-counterfeit can build upon the protections that fiat currency already has on it. There is still trust in the system in that their is trust in the issuer. Better question, is it possible the issuer, can revoke that they’ve given additional value to currency? Yes. In addition, echoing the phrase, “You can’t teach an old dog new tricks”. Assigning additional value may not be well understood. Which according to the lecturer may not be a bad thing. It’s fine for their to be a temporal weight and then the dollar bill goes back into circulation.

Assign properties to Bitcoin: Colored Coins

So taking the above example, something similar can be done with bitcoin. Colored coins can track a specific color. The definition in the Bitcoin wiki is it’s an example of methods for tracking real world assets on top of the Bitcoin blockchain. Bitcoin still have their value but you’ve added additional meaning withe metadata for these “colored” coins. How it works, is via a single transaction, one can inject additional metadata thereby injecting meaning to the unspent transaction outputs. This metadata essentially issues new colored coins. There is a protocol for using this known as “Open Assets Protocol“. Coins are issued by passing through P2SH address. A special unspendable marker is outputted. Thus you match colored inputs to outputs.

Pros and Cons Breakdown

Pros

• Compatible with bitcoin
• Flexible to represent any asset
• Can be ignore by community, in that doesn’t require work from miners

Cons

• small cost of un-spendable markets
• must check every previous transaction (because miners aren’t really doing anything)
• harder to use this on smaller memory locations like phone, so think SPV would not be applicable

Applications

Then he mentioned certain applications for this. First up was stock certificates. Thus you wouldn’t need centralized exchanges for stock and could actual have that be peer-to-peer. The second was deed for real estate. The third was cars. He discussed something about real world sharing and driving of cars. Lastly was ownership of domain names. Domain names are interesting and he mentions a project known as Namecoin.

Namecoin is known as the basis for a decentralised domain name system. It’s the same code as Bitcoin just forked. This would fight online censorship. NMC (namecoin) seems to have died Dec 19, 2018 according to this article. The article goes on to mention that Namecoin was actually a though creation of Satoshi via the paper, “BitDNS and Generalizing Bitcoin,”. Moving to 2019, I see IPFS and potential ENS as the way forward for decentralized name servies.

IPFS (Interplanetary Filesystem) along with the other protocols allow for the sharing of information on the internet peer-to-peer. ENS (Ethereum Name Service) allows one to host and launch websites linked to an Ethereum address on the Ethereum main network.

This lecture describes puzzles that may be socially beneficial. Socially beneficial is a pretty loose definition. Questions answered in this Post:

• Can the wasted work from Bitcoin be recycled?
• Protein folding and Alien detection
• What is Primecoin?
• Recovering or repurposing wasted hardware: Permacoin
• Storage Based Puzzle

Recycling Mining Energy

Per the lecture, Bitcoin consumed 150 MW – 900 MW power approximately in mid-2014. A paper from June, 2019 mentioned that the annual carbon emissions is 22.0 to 22.9 MtCO2 in Nov 2018. They also mentioned the annual electricity consumption of Bitcoin to be 45.8 TWh ( terawatt-hour ). The benefits are obvious in that it may reduce energy costs and reduce the negative environment impact. Prof. Miller mentions some natural choices regarding protein folding and search for aliens. The first one is finding a low energy configuration. The second is find an anomalous region of a signal. They have similar characteristics to the current Bitcoin puzzle in that you’re trying to solve a problem that has a large problem space. There is a website called Fold.it that contains crowd-sourced gamified tasks that allow people to participate in scientific research. Proteins are composed of long chains of amino acids and they have a specific stable configuration. The specific shape means that some amino acids are near the center while others are far apart and this shape is the lower energy configuration they can keep. The hypothesis for why the game exists is that humans’ pattern-recognition and puzzle-solving abilities are more efficient than existing computer programs at pattern-folding tasks. Not sure if this is still an open question or if things like deep mind and deep learning change or disprove the hypothesis. The second option is searching for anomalies in space which can help detect extra terrestial life. Both the protein and detecting proteins are classified as crowdsource distributed computing problems. There is an article from Valentine’s day 2018 on how cryptocurrency mining is actually hampering the serach for ET life. SETI (Search for Extraterrestial Intelligence) uses GPU chips for their research. Radio-astronomers use them because they are processing large amounts of data and looking at many frequency channels to find the anomalous signal types. This issue is not unique to them given that video gamers have also mentioned they’ve now had a higher cost of GPUs. From my basic understanding of mining, when there was a market downterm, some miners turned off their mining rigs because it was less profitable. As the price of cryptocurrencies go up, that makes the mining more valuable. Prof. Miller brings up the notion that there is a centralized administrator for these problem sets and define the exploration space for participants. Bitcoin doesn’t have this and thus instances of the problem need to be auto-generated. There was not a clear way to generate these problem systematically to miners and thus while the problems are good, it’s not feasible to do it in a decentralized fashion. So what else is there?

Primecoin

Prof. Miller brings up Primecoin [[http://primecoin.io/]] which addresses these prevoius problems of needing a centralized resource to choose the problems. Primecoin aptly named involves finding large prime numbers. It’s consensus work is having nodes search for chains of prime numbers, specifically prime chains composed of Cunningham chains and bi-twin chains. A Cunningham chain is a chain of numbers where each number has the form 2^i*a + 1. Each is a large (probable) prime such that p is divisible by H (prev || mrkl_root || nonce). Probable prime classificaiton allows for efficient prime testing algorithms to be run as determining primality for very large numbers can be expensive. To date, most of the largest Cunningham chains have come from the Primecoin miners. He briefly mentions that it could be useful but then dismisses saying that the chains found are overkill. Thus, I’m unaware what it’s usecase is beyond helping science and looking at the distribution of primes. The Bitcoinwiki mentions that there may be a connection between the Riemann zeta function and prime distribution and relevant to other modern sciences. Alas, that is beyond what I was able to understand. The paper [http://primecoin.io/bin/primecoin-paper.pdf] similar to Bitcoin was published by a pseudonym Sunny King. It’s short in that it’s only 6 pages.

Permacoin: using storage-based puzzle

He mentions that upwards of 100 million dollars are spent on customized hardware. The hardware is so specialized that the investment is useless for other application. What if that wasn’t the case? Permacoin is mining with storage. You get massively distributed, replicated storage system. Then we get an example. There is a large file F that we’re storing and this F is chosen globally at the beginning by a trusted deal and then each user stores a random subset of the file. Thus this is where he introduces a new type of puzzle, storage-based puzzle.

What are the steps for the puzzle?

A Merkle tree is used where each leaf is a segment of the file F. Then miners will generate a keypair wich determines a random subset of file segments. Then for each mining attempt, a miner wil select a random nonce and then generate a hash h1 which is H(prev || mrkl_root|| PK || nonce). h1 select K segments from the subset. Then a second hash h2 is generated which is H(prev || mrkl_root || PK || nonce || F). Then they get the block if h2 is less than a certain target value. Thus the participants need to keep storing parts of the file. Permacoin adds a benefit for UTXO storage.

Wrap Up

Useful proof of work could be great. Its benefit must be pure public good. Other puzzles have been explored but none have truly captured mainstream adoption so far.

This lectures describes what ASIC resistant puzzles are since this is a widely researched topic in puzzles. I also completely diverted from the lecture notes by bringing up a topic I’ve been following closely which is ProgPOW in Ethereum. This is a proposal for introducing another (potential) ASIC resistant puzzle for Ethereum.

Questions answered in this Post:

• • • What and why do ASIC resistant puzzles matter?
    • Memory Hard Problems
    • Memory Hard Problems: Scrypt
    • Memory Hard Problems: Cuckoo Hash Cycles
    • ProgPOW: Ethereum discussion

Why care about ASIC resistant puzzles?

A bit of a backstory, Bitcoin used to be mined by individuals. Home computers that weren’t fancy could be miners and win the block rewards. Nowadays, that’s pretty much impossible. Companies running giant mining rigs running specialized hardware dominate the network now. ASIC stands for Application-Specific Integrated Circuit and describes the specialized hardware now used to mine Bitcoin and some other cryptocurrencies. Because of this shift, people have proposed alternatives to democratize mining. Is there a way to allow the average consumer the ability to participate once again in mining? ASIC resistant boils down to if allowing specialized hardware to have an intrinsic advantage when participating (mining) for a network.

Based on the above description, it’s clear that one goal of ASIC resistant puzzles is to lower the barrier to entry. This allows potentially any idle hardware could be used to contribute to supporting a blockchain network.

Another goal, in a similar strain, is reducing the monopoly by big manufacturing firms. The creators of the mining hardware have an unfair advantage. If they’ve created the new hardware and then mine Bitcoin with it for a few months, buyers are essentially getting a second-hand piece of hardware. Given that the difficulty level changes over time, it’s thought that when newer hardware is first used, it performs better and then overtimes the reward decreases. The lecturer uses the term “burn-in” advantage to describe the “use before sell” approach. Thus the new approach would be to reduce difference between future hardware and existing custom ASICs which would allow for longevity with the hardware and reduce this “burn-in” advantage.

Tangent on Mining Ecosystem: Work by Siacoin

Ok, not sure if you’re like me, but when I hear Siacoin my first thought was not cryptocurrency. However, they’ve written and done compelling work looking at the ASIC industry. Siacoin is building online network for distributed storage. They created ASICs for their own Sia mining somewhat related to Bitmain’s ASIC release and documented their journey. “The vast majority of ASIC-resistant algorithms were designed by software engineers making assumptions about the limitations of custom hardware. ” This quote alone makes me skeptical whenever people claim that something is ASIC resistant. Further down, I mentioned about ProgPOW for Ethereum and feel comforted that they are seeking a 3rd party audit. The article touches about Monero secret mining which again targets a real world example that this lecture discussed.

Memory Hard Problems

Memory hard problems is a type of puzzle that is ASIC resistant. It uses the idea known since the 80s that cost and performance in memory is more stable than for processors. As time has progressed processing has increased exponentially while memory and storage have increased at a slower rate. Thus if you pick a puzzle based on processing than it’s more likely to change significantly and older versions will have worse performance than a puzzle that was memory or storage intensive. He brings up Moore’s Law briefly when mentioning the exponential improvement.

Scrypt – Colin Percival

One potential memory hard hash function is called Scrypt by Colin Percival (2009). Scrypt is similar to the Bitcoin puzzle but instead of using SHA2, it replaces the function with the scrypt algorithm. It has a trade-off with constant time/memory. It can be computed with a certain amount of fixed memory, any smaller, it will require more time. In addition, it has already been adopted by a known cryptocurrency, Litecoin. Scrypt is used in other application such as for password hashing. Thus the lecturer mentions another benefit to this approach is that if there were issues other people have eyes on this mechanism to look for vulnerabilities.

Scrypt Steps

1. Fill memory with random values
2. Read from the memory in random order

The lecturer then dives into a step-by-step example of how the algorithm works. The algorithm, per the lecturer, was memory hard because if you reduce memory by half, then the number of computational steps increase by 1.5x. One disadvantage is that it requires N steps and N memory to check. In addition, scrypt ASICs unfortunately already exist. There was an interesting thread posted on Bitcointalk which I’ve linked here. It points out that scrypt does use SHA256 but the algorithm happens to be memory intensive. Given that in 2013, the cryptocurrencies using this algorithm were low value and low liquidity, manufacturers were not incentivized to build FPGA and ASIC when GPUs already do much of the needed work. I’ve found newer academic articles proving that scrypt is maximally memory-hard. However, based on what I’ve read, cryptocurrencies may not have achieved the right parameters, specifically the actual memory size, to achieve ASIC resistance which some suggested was due to support GPU miners. Again, I’ve provided my sources, but admittedly I don’t understand the proofs well enough to make a well-substantiated argument.

Cuckoo Hash Cycles – John Tromp + More

Next, we look at Cuckoo hash cycles by John Tromp (2014). It has a clear improvement to Scrypt in that it’s cheap to verify where before verification would require the same amount of memory as solving. For a certain memory size, you still compute the hash function. However, instead of having to look through the entire memory space, you just need to check if there is a cycle of size K where K is less than N.

There are more complex functions that people are researching which Miller mentions. Specifically X11 which as indicated in the name uses 11 different hash functions. The other is called a moving target which builds on changing the puzzle periodically. As with most lectures, Miller also provides a counter argument on why perhaps the current algorithm is sufficient.

ProgPOW: Programmable Proof of Work for Ethereum

Per EIP-1057, “Proof-of-Work algorithm to replace Ethash that utilizes almost all parts of commodity GPUs”. Clear and concise. The goal as mentioned for ASIC Resistance is to allow commodity GPUs to be used for Proof of Work mining. Having a custom ASIC would not be beneficial. The primarily discussion that I’ve read about has little to do with the new algorithm or when it will be implemented. Most conversation has been around getting the algorithm audited. There seems to be consensus around whether people see it as useful. 

Counter Argument: Maybe ASIC Resistant isn’t needed now

The argument simply is that Bitcoin mining ASICs aren’t changing very much anyway. Thus the first argument brought up with Moore’s law, is maybe not as needed. Processing is not increasing at that much of an exponential rate that necessitates the shift to memory intensive algorithms. The difference between the bigger and smaller ASICs is how many copies of the same SHA2 function the hardware holds. 

Similar to where the lecturer mentioned that ASIC resistant wasn’t needed, the most recent BTC forks have also had a similar discussion.

https://news.bitcoin.com/cryptocurrency-projects-aiming-to-be-asic-resistant-have-little-success/

Tangent on Memory Hard Problems

Just a quick note, I wasn’t able to find many resources outside of those related to this course talking about memory hard problems that weren’t cryptography intensive. A. Biryukov from the University of Luxembourg has published two papers relating memory-hard and cryptocurrencies though. If you’re interested, I’ve left links to both papers, Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing and Tradeoff Cryptoanalysis of Memory-Hard Functions

Wrap Up

ASIC resistance

• • • seeks to make it more appealing to mine with regular consumer devices than it is today
    • response to centralization of Bitcoin mining

 

This lecture covers a critical component of certain digital currencies which is mining puzzles. This section covers what are the requirements of these puzzles to be good puzzles. Theoretically you could replace the word “puzzle” for any other word and it would have the same meaning. The use of the word puzzle is not within Satoshi Nakamoto’s seminal paper. He merely writes, “The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash”.

Questions answered in this Post:

• • • What is a puzzle in this case?
    • Why are the important?
    • What are the requirements?
    • What is hash power?

  Why are they important?

  Andrew Miller states that “mining puzzles determine the incentive system in Bitcoin”. Thus whatever puzzle is chosen needs to ensure miner participation. In addition, if shortcuts are found, miners will ultimately choose the most efficient path and thus remove arbitrage situations that may occur. If puzzles are one of the few mechanisms that exist to maintain the protocol, it needs to be at the core and encapsulate the work. Miners are not incentivized to “do good” just to ensure the health of the system if they will not be compensated.

  What are the requirements?

  The first two requirements were discussed in earlier lectures and are straightforward. The puzzle needs to be easy to verify and have an adjustable difficulty setup. Bitcoin’s proof of work puzzle is easy to verify since once a valid value is found, all miners can just use that value with the hashing function and determine whether is it a small enough value (has the sufficient number of zero bits). The puzzles get solved at a known reasonable rate ensuring long term participation. Ten minutes is the current rate for Bitcoin. The puzzle is also adjustable because the value looked up is in a range which can be made smaller or larger. As long as the difficulty is set and shared with all miners, this now gives you the adjustable difficulty setup.

  Another new requirements is that the probability of winning is based on hash power. Simply stated, big fish with more hardware have a higher chance of winning. Small players still have a probability to win but it may be smaller. The lecturer makes a distinction using a sequential proof of work which is marked as a bad puzzle. If the puzzle is more like who can complete N steps faster wins, then likely you’ll have a single party who has the fastest computation and always wins. Instead a good puzzle should have a weighted sample and they also bring up the term “progress-free”. Bitcoin is different in that the small and big miners are all computing and while big miners, those with more hardware, have a higher chance of winning, it’s not 100%.

• I like to think of it more like a dice game where the larger miner has control of faces 1-5 and only 6 is held by the small miner. The small miner still has ~17% chance ie some non-zero chance of winning at every block. In addition, every roll of the die the percentage theoretically stays the same in a perfect world. The die is merely a metaphor but hopefully that point makes sense.

  What is hash power?

  Throughout the lecture, Miller used the term hash power. At some point, he substituted hash power for hardware. Now, I was still unclear on the term so I decided to take a quick trip through Google. I’ve found hash power can be used interchangeably with hash rate. Hash rate is some measurement per second that a miner does work. Examples hash rates are of the order of 16 TH/s (one trillion) hashes per second for mining rigs. This individual hash rate can be compared to the overall network which can be seen in block explorers. The probability creates gives the miner what chance they have of finding the next block as well as some expected value. Here’s a link to one chart at blockchain.com.

  Wrap up

  This lecture was quick. Really excited to find out more alternative mining puzzles that he alluded to.