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.
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.
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”→
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.
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.
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”→
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: . 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”→
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.
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?
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.
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!”→
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.
Figure 1: Stacks chain secured on the Bitcoin blockchain.
I previously described how Bitcoin is secured by a Proof of Work (PoW) protocol. Now, I describe an alternative method of achieving the same goal — Proof of Stake (PoS). This is currently being used for some blockchains, such as Cardano, and there are also plans for Ethereum to move from its current PoW incarnation to a PoS system. Both methods have their benefits and drawbacks, with PoS requiring much less energy but, on the other hand, is more complex with more possible attack vectors. Opinion is divided on which is the better,with defenders of either system having very strong convictions. In this post, I concentrate on describing how proof of stake works and only briefly touch on the possible benefits of one method over another. There are many different implementations of proof of stake so, here, I give an overview of the methods used without concentrating on any one particular utilization.
As explained in an earlier post, whichever method is used to secure a blockchain, it should require miners to spend some resource in order to build blocks. For PoW chains like Bitcoin, this resource is computing power or hashrate. For PoS chains, the resource is the underlying tokens or cryptocurrency represented by the blockchain itself. More precisely, as it just requires miners to lock up coins for a period, it is the opportunity cost of these coins that they spend. This is an internal resource of the blockchain rather than an external one as with PoW. Before going any further, there is a slight matter of terminology. The people who build blocks for a proof of work chain are called miners whereas, in proof of stake, they are called validators. Other terms, such as forgers, are also in use. Personally, I think it would have been simpler to use the same word regardless of the protocol but, to be consistent with the common usage, I will refer to block builders as validators.
Let’s just refresh our understanding of what a protocol needs to do. It should;
allow anyone with the necessary resources to participate in building the blockchain.
allow the network to reach agreement on a single global blockchain state at each time.
(immutability) ensure that, once a block is added and considered to be confirmed, then it will remain in the chain indefinitely.
Furthermore, these properties should continue to hold even in the event that a minority of validators are acting dishonestly or, even, are collaborating to attack the network.
In proof of stake, individuals register to become a validator by locking up a quantity of the blockchain asset. The protocol then divides up time into a sequence of successive slots, one for each block. It needs to assign one validator per slot, and do this in a way such that, on average, the number of slots assigned to each validator is in proportion to their stake size. Then, when their time slot is reached, it is the job of the validator to collect together transactions from the mempool, and construct a valid block to append to the chain. In return, they receive a reward which can be one of, or a combination of, the transaction fees in the block and the block reward.
Figure 1: Validators building a blockchain.
Each block is appended to the one constructed in the previous time slot so that, as time progresses, the validators continually add blocks on top of blocks, building the chain. Figure 1 shows this procedure with the cryptopunks acting as validators. Unlike with PoW where anyone who is able to create a valid block can submit it for inclusion, here the protocol needs to verify that the block used in each time slot has indeed been created by the validator assigned to it. This can be achieved with public key cryptography where, when they purchase a stake, each validator has to supply a public key. They then sign their blocks using the associated private key, proving that they were created by or, at least, approved by the assigned validator. Continue reading “Proof of Stake”→
What is a blockchain? For Bitcoin, it is a distributed ledger recording all transactions, and updated in real-time as new blocks of transactions are added. It has the important properties that anyone with the necessary private keys is able to create valid transactions to be added and, conversely, uses cryptography to ensure that only those with the necessary private keys are able to create such transactions. Other important properties include that there is a single valid blockchain state, and this state is accessible to anyone connected to the network. Furthermore, immutability requires that once a transaction has been added to the chain and is considered ‘confirmed’, then it should exist unchanged in all future blockchain states. More generally, a blockchain can be thought of as a kind of distributed database with a single shared state, which can be updated via the addition of blocks of transactions.
Let us look at the process of building a blockchain, whether it be Bitcoin, Ethereum, or something else. Users submit transactions to the network for inclusion on the blockchain. Then, miners (or similar) collect these transactions together into blocks, and add any additional required information such as the previous block hash, timestamp, hash root of the transaction data, or nonce required by the proof of work protocol. As long as the block is valid according to the protocol, this is then transmitted to the network for inclusion in the chain. This procedure is graphically displayed in figure 1 below.
Figure 1: Constructing a blockchain as a sequence of transaction blocks.
Some blockchains, such as Ethereum, use an account model to represent the quantities of an asset held by each party, and transactions between them. This is an alternative to the UTXO model described in an earlier post. The idea is straightforward. At any time, we have a set of accounts, each with a unique identifier and an associated quantity of the asset. A transaction consists of, at least, the following:
From: The account to be debited.
To: The account to be credited.
Value: The size of the transfer.
Fee: A fee for processing the transaction.
Figure 1 gives an example where Alice is paying Bob 30 units, with a transaction fee of 2 units.
Figure 1: Applying a transaction in the account model.
Processing the transaction consists of adding the transaction value to the ‘To’ account and subtracting the transaction value and the fee from the ‘From’ account, to obtain the new state. Since the value of an account cannot drop below zero, we must have,
Transaction Value + Transaction Fee ≤ From Account Value.
There are some additional fields that are required in order to be able to validate a transaction, although they do not have any effect on the state of the accounts.
Signature: Only Alice should be able to spend the contents of her account which, as with the UTXO model, is done using public key cryptography. Each account should have an associated public key. Alice can sign the transactions from her account using the private key and, then, validation requires using the public key to verify that the signature is valid. In Ethereum, the account name is just a hash of the public key.
Nonce: Figure 1 above shows a transaction from Alice to Bob of 30 units, with a fee of 2 units. What happens if she wants to repeat this payment? She could try submitting the exact same transaction again. However, this cannot be accepted by the network. If it was possible for the same transaction to be applied more than once, then anyone could just take Alice’s original transaction and re-submit it as many times as they like, until her account has been drained. This can be avoided by including a nonce field (‘number used only once’) in the transaction. Then, Alice can submit a new transaction with the same value and fee, but with a different nonce. In Ethereum, the nonce is required to start at 0 for the first transaction from an account, and increase by 1 for each subsequent one, so is always equal to the total number of previous transactions from that account.
. 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.
Zero Knowledge 