Building a STARK

This post will step through how to build a simple zk-STARK. Whereas I have outlined the ideas already in a couple of posts (STARKS I and II), these took a very general approach and consequently were rather abstract. This post will be more concrete by detailing how one can be built for a specific calculation. For this, I pick a ‘toy’ example for ease of exposition, but which is still very interesting. The calculation will be based on the rule 30 elementary cellular automaton. There are many ways of actually building a STARK, some of which will perform better than others. I make the choices aiming for simplicity and to avoid complex constructions.

First, let’s recap what a zk-STARK is. It is an acronym for zero knowledge Scalable Transparent Argument of Knowledge. While they are often phrased as proofs of existence of some quantity (e.g., existence of 3-colorings of a graph), more properly, they are a proof that the person constructing the STARK has knowledge of this quantity. We can be a bit more precise. The setup must include some algorithm or computable function F and a value b which it may or may not return. This information will be publicly known, so that anyone can verify what F(a) does evaluate to on given input a. Anyone can also make a statement such as:

I know of a value a such that F(a) evaluates to b.

However, such a statement does not itself prove that they do really know of such a value. An argument of knowledge is a method of proving the truth of this statement. As an example, consider digital signatures. In this scenario, the value a is a private key and F is the calculation deriving the associated public key b. A digital signature is an argument of knowledge of a private key. For elliptic curve based schemes as used in ECDSA and Schnorr signatures, it can be shown mathematically that for any public key there does exist an associated private key, although it can be practically impossible to actually find it. Hence, a digital signature is not a proof that a private key exists, which we know already. Instead, it is a proof that it was known to the person constructing the signature.

One method of proving a statement like the one given above is to simply display the value of a, so that anyone can evaluate F(a) and verify that it does indeed equal b. There are two reasons why this may not be a desired or viable approach, corresponding to the other words making up the acronym zk-STARK. Firstly, the value of a may be a secret, such as with the digital signature example. It should be zero knowledge. Ideally, the proof does not reveal any information beyond the fact that the prover knows of a valid value for a. Secondly, it should be scalable.

By scalable, we mean that the size of a zk-STARK should remain small and reasonably quick to validate, even if F is very computationally expensive to compute. For example, we could take the value a and hash it billions of times to get the result b. If we want to convince others of the result, then expecting them to go through the whole tedious calculation might not be realistic. Instead, a STARK can be constructed, which anyone can check proves that the result is b as claimed without having to redo the entire calculation. This is especially useful for blockchains where the use of STARKS can greatly reduce the work required by validators and avoid using up a lot of the limited block space. A long list of transactions with their associated digital signatures could be replaced by a much shorter proof of the combined effect of these transactions.

The scalability property is really the magic part of STARKs and the closely related SNARKs. A very long calculation will take a long time to perform. However, once one person has done this, they are able to prove the result to others without requiring them to also go through the long calculation. We really do not have any right to expect that this is even possible, but luckily it is!

Next, STARKs are transparent, which means that there is no trusted setup. This is in contrast to the closely related SNARKs (scalable non-interactive argument of knowledge), where a procedure is required to initialize the contruction of the SNARKs, and involves data which must be kept secret by those involved. Revealing this data would allow ‘proofs’ to be constructed even though the prover does not have the knowledge being claimed. STARKs do not have this issue.

Finally, I mention that STARKs are non-interactive. Any argument of knowledge involves two parties, the prover and the verifier, with the former trying to convince the latter of the truth of a statement. Interactive proofs involve messages being passed back-and-forth between the two. Essentially, the verifier asks questions of the prover, and checks his responses, until she is convinced of the proof of the original statement. A non-interactive proof just consists of a single message sent from the prover to the verifier. This is what is needed in many blockchain applications, since the proof can simply be constructed and added to the chain. Anyone can be the verifier by reading the data from the blockchain, such as done by validators.

As with any argument of knowledge, STARKs are sound, meaning that it is practically impossible for someone without the claimed knowledge to construct a valid proof. However, I should point out that, in theory, it is always possible to just guess at a valid argument by blind luck. For this reason, any such construction will come with a soundness parameter. This is an upper bound on the probability that, without the claimed knowledge, any parameter choices made in its construction leads to a valid proof by chance. The idea is that this should be tiny to avoid such false positives. It is true that an untrustworthy prover could try over and over, choosing different parameters each time, to try and brute-force a solution. As long as the soundness parameter is small enough — say, about 2-100 or lower — then it becomes practically impossible to even brute-force a solution.

Automaton Rule 30

The toy calculation used in this post is the elementary cellular automaton Rule 30. The idea is that we have a one dimensional array of cells, indexed by the integers. Each cell can be in one of two states, either set or unset, which I will label by the numbers 0 and 1. We then iteratively update this array, one step at a time. At every step of the calculation, each cell is updated according to the value of it and its immediate neighbours.

Using si(t) to represent the state of cell i at time t, I will also denote this by just si, suppressing the time variable for brevity. Its value si(t + 1) at time t + 1, which I denote by s′i, is some function of si - 1, si, si + 1.

s′i = S(si - 1, si, si + 1).

The rule is defined by the function S and, given any initial state, this can be applied to compute the state at every future time. There are many different choices for S giving different cellular automata with different properties. I choose rule 30, for which the state s′i is determined from si - 1sisi + 1 by looking up its value in the following table:

current pattern 111 110 101 100 011 010 001 000
new state for center cell 0 0 0 1 1 1 1 0

Figure 1: Rule 30.

As there are 8 possible values which si - 1sisi + 1 can take, and each of these can lead to two possible states for s′i, there are 28 = 256 distinct elementary cellular automata. This particular one is called ‘rule 30’ since the second row of figure 1 is the binary expansion of the number 30.

To avoid dealing with infinite arrays, I will use a fixed window width of 200. That is, rather than an infinite array of cells, we just have 200 of them labelled as si for 0 ≤ i < 200. At the edges of the window, we allow the rule to wrap around, so that, on the left, s-1 is defined to equal s199 and, on the right, s200 is defined to be s0.

Then, if we start with the single cell number 50 set, and the others unset, repeated applications of the rule give figure 2 below. Here, the time starts from the top of the figure and increases towards the bottom. Each row of pixels represents the state at the corresponding time, with black pixels representing cells which are set and white those which are unset.

rule 30
Figure 2: Rule 30 with a single initial cell set

Continue reading “Building a STARK” →

Mimblewimble

No, I haven’t gone crazy. Named after a Harry Potter spell rendering the target incapable of speaking coherently, mimblewimble is a blockchain protocol which scrambles up the transaction quantities and addresses, giving both a high degree of privacy and an efficient representation allowing massive savings on block space. According to its anonymous inventor, “I call my creation Mimblewimble because it is used to prevent the blockchain from talking about all user’s information”. Remarkable properties include not just hiding transaction quantities, but also allowing all transactions to be merged into a single big transaction, and spent outputs combined with their corresponding inputs and stripped from the blockchain. This last point has potential huge savings on blockchain space and validation time.

The protocol was implemented by the Grin and Beam cryptocurrencies, launched in January 2019. More recently, it was introduced into Litecoin in the MWEB upgrade (Mimblewimble extension block). This formally locked in on 3 May 2022 and went live a couple of weeks later.

Mimblewimble Continue reading “Mimblewimble” →

Merge Mining and Auxiliary Proof of Work

merge mining
Figure 1: Mining on two blockchains at once

Merge mining or merged mining is the process of mining more than one blockchain simultaneously. This is possible for some proof-of-work (POW) chains, where a miner puts the same hash power to work creating blocks on multiple chains and earns the associated rewards on each of them, without having to pay separate energy costs for each. Here, I explain the ideas behind merge mining.

For a blockchain incorporating the proof-of-work protocol, miners use hash power in order to win the chance of appending their block. For leading chains such as Bitcoin, this is an energy intensive process where each individual hash has a minuscule chance of winning. They need to perform a huge number of hashes to be in with any chance. Where there are multiple proof-of-work chains available, the miner needs to choose which one to contribute his hash rate towards. So long as his hardware is compatible with the specific hashing algorithms used (such as SHA256), he is free to mine on either chain, and switch between them as desired. Usually, it is not possible employ the same hash power simultaneously on both chains. This is because each hash is applied to the block header for the chain in question, so can only be used for solving the POW problem for that specific blockchain. However, if the protocol for all (or, all but one) of the blockchains in question have been designed to specifically to allow for it, then it can be possible for each hash function application to contribute to the proof of work on each chain simultaneously. This is known as auxiliary proof-of-work (AuxPOW).

There are several blockchains that can be merge mined along with Bitcoin. The first such case was Namecoin (NMC), which was created in April 2011 and upgraded in October 2011 to support merge mining. Another example is Rootstock (RSK), which was created in January 2018 and is a sidechain of Bitcoin supporting smart contracts. According to the article The Growth of Bitcoin Merge Mining from October 2020, over 90% of the Bitcoin hashrate is involved in merge mining. This is shown in figure 2 below, borrowed from the same article and showing the proportion of Bitcoin blocks which contain an auxiliary proof-of-work in the coinbase transaction, indicating that it was merge mined along with another blockchain. One notable example not involving Bitcoin is Dogecoin, which is merge mined along with Litecoin, using the scrypt hash function.

merge proportion
Figure 2: Proportion of Bitcoin blocks with auxiliary POW (source: BitMEX Research).

Continue reading “Merge Mining and Auxiliary Proof of Work” →

Atomic Swaps and HTLCs

Atomic swaps are a method of exchanging one asset for another, such as two cryptocurrencies, even if they exist on distinct blockchains. The idea is to do this in a trustless way, avoiding counterparty risk, so that the swap either goes ahead and both parties receive what was agreed, or the whole thing is cancelled. It should not be possible for one ‘leg’ of the exchange to go through on its own without the corresponding payment. So, we can treat the entire exchange as a single trade which either goes through or not. As separate blockchains exist in isolation, and cannot directly communicate, atomic swaps are a useful cross-chain solution. They help to build a more interoperable ecosystem of interacting blockchains. Furthermore, atomic swaps can also be used with off-chain payments such as on the lightning network, connecting these with on-chain transactions.

atomic
If Alice hands over her bitcoin first, can she trust Bob to give her the ether?

Consider the scenario: Alice owns bitcoin, which she wants to use to purchase ether from Bob. The exchange rate (BTCETH) at the time is about 13. So, they agree to a swap where she sends one bitcoin to Bob and, in return, he sends 13 ether to Alice’s Ethereum account address.

This is fine in theory but, before sending her payment transaction to the Bitcoin blockchain, she has second thoughts. What happens if Bob does not submit his corresponding transaction? In that case, she will have sent him the bitcoin with nothing in return. Can he really be trusted? So, she asks Bob to submit his transaction first. However, Bob is also not really sure that he can trust Alice. If he submits his Ethereum transaction before Alice’s payment is confirmed, how can he be sure that he will be paid? To be safe, both parties in this transaction want the other to confirm their payment first. Consequently, they do not go ahead with the exchange.

What can be done to resolve the issue of trust and counterparty risk? This is not something specific to cryptocurrencies. Whenever two parties want to exchange any items of value, there is the possibility that one of them will not follow through with their side of the agreement. Here are three possible solutions. Continue reading “Atomic Swaps and HTLCs” →

Non-Interactive Proofs

This post discusses non-interactive zero knowledge proofs, which can also be considered as digital signature algorithms. These can be used in blockchains to verify that the creator of a transaction has access to some secret data satisfying specific defined properties.

I previously discussed zero knowledge proofs, where a party Bob has some secret data satisfying certain properties. For example, this could be the private key associated with a publicly known Bitcoin address, or it could be a file whose SHA256 hash is equal to a given value, or maybe he knows a 3-colouring for a specified graph. In fact, it could be any data satisfying a clearly defined computable property. Bob wants to prove that he has such information to Alice but, as it is secret, he does not want to send her the data itself. Ideally, he wants to prove this without revealing any knowledge besides the simple fact that he knows of something satisfying the claimed properties. As was discussed, this can be achieved by an interactive proof where he exchanges messages with Alice until she is able to conclude with a high degree of confidence that he does indeed have the claimed secret. This as in figure 1 below, where Bob is acting as the prover and Alice is the verifier. As I will build on such zero-knowledge proofs here, if you are not already familiar with them it is suggested to first read the earlier post.

interactive
Figure 1: An interactive proof.

Alice verifies that Bob’s messages satisfy some required properties and, if they do, she accepts his proof. Otherwise, she rejects it. Recall the important properties:

  • Completeness: If Bob has the claimed information, he is able to send messages to convince Alice of this fact.
  • Soundness: If Bob does not have the claimed information, he is not able to fool Alice that he does, other than with a very small probability.
  • Zero-knowledge: The verifier learns no information beyond the fact that Bob has the knowledge.

To ensure soundness, Alice should select her messages at random according to a specific procedure. Essentially, she is challenging Bob with unpredictable questions, which he is very unlikely to be able to answer all correctly unless he has the claimed knowledge. If Alice sticks to this method, she is an honest verifier. Similarly, if Bob has the claimed information then, to ensure completeness and zero-information, he should also construct his messages according to a specific procedure which, again, are randomized to ensure that he does not leak any secret information. If he does this, then he is an honest prover.

In many situations, the setup described above is not desirable or is not possible at all. It may be preferable for Bob to send a single proof to Alice for her to verify without having to respond with further questions. Maybe there is no communication channel from Alice to Bob, or maybe she will check the proof at a later date when she no longer has contact with Bob. This is the case, for example, where Bob is submits a transaction containing the proof to be included in a blockchain, and Alice is a network validator who later verifies this transaction. These are non-interactive proofs, so figure 1 should be updated to only include a single message sent from the prover to the verifier.

non-interactive
Figure 2: A non-interactive proof.

Technically, it is not possible for valid non-interactive proofs to be zero-knowledge, at least by the standards described in the previous post. For one thing, Alice could take the message sent from Bob, and pass it off as her own to try and prove that she has access to the secret data, which is incorrect. In fact, Bob may have already done this, and simply passed off a proof originally from someone else as his own. So, the best that we can expect, is for the message to prove that someone had access to the secret and constructed the message. Continue reading “Non-Interactive Proofs” →

Zero Knowledge Proofs

Where's Waldo
Where's Waldo?

Alice is busy trying to find Waldo in the picture above (or, Wally, for those outside of North America). After some time without success, she is doubtful that he is even in the image at all. Bob assures her that Waldo is there, since he already found him. However, this is not enough to satisfy Alice. She needs proof before spending any more time on the task. How is it possible for Bob to prove this to her, without giving the game away by pointing out his location?

Assuming that the picture is printed out on a sheet of paper, Bob could take a large piece of cardboard and cut out a small Waldo-shaped hole. Then, while keeping the hole covered, he slides the paper underneath and, after correctly positioning it, he uncovers the hole to reveal Waldo! Alice can look with her own eyes and see his face, which looks like this: Waldo. She agrees that Waldo is in the image but, since all of the rest of the picture is covered by the cardboard, Bob has not revealed the location. So, she continues with her task in the knowledge that, at least, it is possible.

What Bob has done here, is provided a zero-knowledge proof that Waldo is in the picture. That is, he did this while providing no information to Alice other than the fact that he is there. You could argue that he did provide some information. Specifically, he showed Alice the exact size and appearance of Waldo’s face. However, if we assume that this information is no secret and is already publicly known, then it is true that Bob did manage to prove Waldo’s existence in the image without revealing any other previously unknown information. Continue reading “Zero Knowledge Proofs” →

A Smart Contract Platform on Bitcoin?

Consider the following question. Is it possible to use the Bitcoin blockchain for smart contracts? By this, I am not asking how far we can push the rather limited functionality of the native Bitcoin Script. Rather, can we write code for something like the Ethereum Virtual Machine (EVM), which is a Turing complete computation engine used by the Ethereum blockchain, and run on Bitcoin? This would enable a great variety of different uses for Bitcoin, such as ERC20 tokens, decentralized exchanges (DEX), NFTs, zk-STARKS, and any of the many different types of contract used by Ethereum.

While your first answer to the question above is probably “no, this is not possible”, there is one way in which it can be done with, albeit, a rather large caveat. Bitcoin transaction outputs incorporate a script, which is a simple stack-based programming language used to restrict how the coins can be spent. Output scripts starting with the OP_RETURN opcode cannot be spent in any way. More than this, they are provably unspendable, so are ignored by Bitcoin nodes which do not even record such outputs in the UTXO set. The output quantity would likely to be set to zero, so as to avoid irretrievably destroying any bitcoin associated with the output. This means that we can include any arbitrary data following the OP_RETURN to be recorded on the blockchain, which is simply ignored by all validating nodes. This is one of the uses of Bitcoin, as an immutable and decentralized store of data.

smart contracts
Figure 1: Smart contract transactions in OP_RETURN statements.

So, all we have to do, is to include smart contract code in OP_RETURN outputs using whatever language, such as EVM, that we want. Ok, this does not form part of the protocol, so is ignored by Bitcoin nodes. Blockchain explorers would show the code as raw data, but would not interpret the contract language. This is a rather large caveat, and you may well reply that it is not really ‘running’ on Bitcoin and, really, all that we are doing is using the blockchain as data storage. However, it is interesting to consider and, even if due to reasons to be discussed below, it is not very efficient, these methods are implemented by the Omni Layer and also lead on to ideas such as Proof of Transfer. Continue reading “A Smart Contract Platform on Bitcoin?” →

STARKS II: Is that a polynomial?

The previous post outlined how a potentially long and complicated calculation can be represented by polynomials. Correctness of the calculation result can then be verified by checking that their values satisfy some simple identities. One issue that was avoided was how to identify if the values are indeed given by polynomials.

Bob (the prover) has performed a long and intensive calculation, and sent the result to Alice (the verifier). To be sure, Alice wants to verify the result, so requests that Bob also sends a proof of its correctness. The problem is that Alice does not have the time or computational resources to replicate the entire calculation, so it is necessary for Bob’s proof to be significantly shorter than this. So, Bob computes polynomial interpolants of the execution trace, and Alice requests their values of at a small number of random points. She checks that these values satisfy some simple algebraic identities which encode the calculation steps. If they are satisfied, then she agrees that Bob sent the correct result. However, this is assuming that Bob can be trusted. He could be sending any values selected to satisfy the identities. If we are not willing to simply trust that he has performed the original calculation correctly, why would we trust that he is really evaluating the polynomials? Alice needs a way of checking that the received values are consistent with polynomial evaluation. We will discuss how this can be done, and the solution to this problem forms a major component of STARK implementations for blockchain scaling.

poly values
Figure 1: Bob chooses a polynomial, which he evaluates at points chosen by Alice. How can Alice be sure that the received values are really from a polynomial?

Continue reading “STARKS II: Is that a polynomial?” →

STARKS I: Polynomials, everywhere!

Terms such as zk-SNARKs, zk-STARKs and zk-Rollups are becoming increasingly common when discussing scalability solutions for blockchains. The idea is that, we do not send long and complex calculations to be computed on-chain, since it is expensive and inefficient, and there is limited capacity for such contracts. Instead, the calculation is performed off-chain, and only the result together with a proof that it is the result of the calculation is sent for inclusion in the blockchain. It turns out that it is possible to create a proof that a calculation leads to a particular result, such that the proof is much shorter than the calculation itself. Of course, the process of constructing these proofs is rather complicated, but that is done off-chain. In-depth descriptions of zk-SNARKS and zk-STARKS are usually rather long, and consist of several different and complex ideas all brought together. Here, I look at one of these ideas, which is replacing the original computation by expressions involving polynomials.

Alice and Bob

Suppose that Alice and Bob each have a data file of length N bits, and they want to check that they are identical. Of course, Bob could just transmit his information to Alice, and she can confirm if they are indeed the same. However, these are large files, and communication is slow. Instead, Bob could send only the bits from a randomly chosen set of places in his file. Alice can check that, at least, their data agrees in these locations. If a significant proportion of their data bits are different, then this has a high probability catching the discrepancy. However, it is possible that they differ at only one place, in which case Bob would need to send all or almost all of the data to have a good chance of catching this.

How can they do this is an efficient manner? How many bits does Bob have to send to Alice in order for her to have a high probability of telling whether or not their data agrees for every bit. At first thought, you may think that he needs to send all or almost all of it, so about N bits. On the other hand, if you are familiar with hash functions, then you would probably answer that he could compute something like the SHA256 hash and send this instead, so only 256 bits need to be transmitted. While that is true, there is also an efficient approach using polynomials, where we can prove its efficacy with some simple maths and without assuming any of the properties of hash functions. Also, as we will see, polynomials allow us to do so much more than just comparing bits. Continue reading “STARKS I: Polynomials, everywhere!” →

Proof of Transfer

PoX chain

I will discuss an interesting blockchain protocol — or consensus mechanism — in which blocks are constructed on one blockchain by transferring assets on an entirely separate one. This is used by Stacks, where bitcoin needs to be spent in order to add blocks to the Stacks chain. Benefits include recycling the considerable proof-of-work of Bitcoin to secure additional chains, and can extend its functionality by introducing features such as smart contracts closely linked with Bitcoin.

As described in previous posts, decentralized cryptocurrencies such as Bitcoin require a protocol in order to regulate construction of the blockchain and to ensure immutability. Blocks of transactions are appended, one by one, to the end of the chain. The protocol helps decide who gets to assemble each block and receive the associated reward, as well as ensure immutability so that confirmed blocks remain unchanged in the chain for perpetuity. The focus of this post will be on the consensus mechanism itself, rather than any additional features of the blockchain in question such as support of smart contracts.

Most well-known is the proof-of-work (PoW) protocol used by Bitcoin as well as by many other leading cryptocurrencies. This requires miners to compete by expending computational power in order to gain the chance to create a block. Currently, the main competitor to proof-of-work is proof-of-stake (PoS), which requires validators to lock up units of the underlying chain asset in order to be selected to create blocks. Examples include Cardano and Solana. Both kinds of consensus mechanism function by requiring the prospective block-builders to spend some resource in order to win the chance of building a block, and receiving a block reward paid on-chain. These approaches gain their security from the idea that an attacker would need to gain control of more than half of the global resource in order to be able to control the network, known as a 51% attack.

For proof-of-work, the resource in question is hash rate or computational work, which boils down to using sufficient energy. This is external to the blockchain since the energy exists independently of the blockchain. For proof-of-stake, the resource is the blockchain asset itself or, more precisely, its opportunity cost because it is only required to lock up the asset for a period of time. This is internal to the blockchain. Since the resource used for security itself depends on the security of the network, it can introduce some circularities or difficulties when trying to analyse properties of the blockchain such as immutability and possible attack vectors.

There is a third kind of protocol, which is the focus of this post. Specifically, a blockchain can be secured by requiring validators to spend a resource existing on a separate blockchain. Since this approach gains its security from a ‘base’ blockchain to which it refers, it makes sense to use what is considered the most secure and decentralized chain. Namely, Bitcoin. The idea is quite general, and other chains such as Ethereum could be used be used in exactly the same way. As of writing this article, there is one blockchain using such a consensus mechansim. This is Stacks, which gains its security by validators spending bitcoin in order to build Stacks blocks. As such, I will use this as the canonical example demonstrating the approach. The name ‘proof-of-transfer’ (PoX) is used by the Stacks team. This makes sense, since validators are effectively transferring bitcoin in exchange for native Stacks coins when constructing blocks. The important point, though, is that they are spending a resource on the Bitcoin blockchain in order to build blocks on the Stacks one.

stacks blockchain
Figure 1: Stacks chain secured on the Bitcoin blockchain.

Continue reading “Proof of Transfer” →