SegWit and technologies built on it are grossly oversold

Like all good lies, there is a kernel of truth behind them. However, like all good lie, they omit or distort some specific information which are key. Like all good lie, they get repeated so often that they may end up looking like truth. Let’s go over some of them.

SegWit solves malleability

SegWit only solve malleability for transaction which spend ONLY SegWit UTXO. All other transactions remains malleable. This fix is enough to enable technologies like Lightning network. This comes at the cost of reduced fungibility, because only some coins can be locked in the lighting network.

SegWit solves quadratic hashing

SegWit solves quadratic hashing for some specific transactions just like it solves malleability for some specific transactions. However, quadratic hashing is an attack vector and solving it in some specific case is about as useful as being partially on birth control: none at all. SegWit absolutely fails to solve anything related to quadratic hashing.

SegWit allows blocks up to 4MB

That is technically true. However, while block can be up to 4MB, this is not really what people require bigger block were asking for. To illustrate, let’s imagine your friend got a kid and tells you he needs a bigger car than his 2 seaters. How do you think he will react when you propose him a car that is twice as big, but still only has 2 seats? Well that’s what some are trying to sell to you.

Considering current usages, we can estimate that SegWit will increase the amount of transaction which can be processed by a factor of 1.7x to 2x. The fact that SegWit allows blocks up to 4MB while delivering only a 2X capacity increase is not something to be proud of. It adds a new attack vector, as one could start producing bloated blocks and ultimately reduce the long term scaling capability because the adversarial case just got twice as bad.

People do not want bigger blocks for the sake of bigger blocks, but for the value they bring to users just like people do not want bigger car for the sake of bigger car but because they can transport more people or stuff in it.

Lightning network can go world scale

Lightning network, or in short LN, is a technology which allow users to lock funds into a channel, then do transactions offchain and only settle the end result in the blockchain. This is all great until you look at the fine prints, which are for some reason always omitted.

The first one is that is changes the security model. With LN, the person you are transacting with can steal your funds at any time and it is up to you to publish a proof that you are being stolen from, within a given time frame. This is a drawback in itself, but something one could work with considering the benefit brought by LN. However, in the case where the chain is running at capacity, it may be very expensive, or even not possible at all for you to publish the proof within the required timeframe. In the world of LN, full blocks equals stealing.

The second problem is that it require an ungodly amount of capital to operate. If you want to be able to pay up to $100 using LN, you need to have $100 or more locked into a channel. If you want to be able to receive $100 , this amount or more needs to be locked on the opposite side of the channel. If we imagine an extremely centralized network with only one hub in the middle, processing payments for 10 millions users (which is the order of magnitude of the number of Bitcoin users today) and allow these users to send payments up to $100 , the users collectively would have to lock up at least $1B in channels, and the hub itself would have to also lock $1B in all the channels with its users, and yet, be less useful because of the $100 limit. Yes, that’s $1B, to create a LN the size of the current Bitcoin network. Growing to a billion users and up to $1000 in payments require a trillion dollars from the hub.

But we imagine we won’t have one giant hub, instead we will have several hubs interconnected with each others. Let’s imagine we can find routes for Alice to send a payment to Bob in an average of 3 hops, then we need to have the amount Alice’s send to Bob or more locked up in each channel along the way. The inevitable conclusion is that LN strongly incentivize centralization as longer routes require operators to lock up even more fund that in the centralized scenario.

Schnorr signatures will provide addition capacity

Schnorr signatures are very cool and are indeed both cheaper to validate than currently used ECDSA, and are also more compact, so you can fit more of them in a block. However, signatures go into the witness section of the block, and, with current use cases, and if we keep the same block size limit, the expected witness usage is of about 1MB when it is possible to have up to 3MB of witness data in a SegWit block. As a result, Schnorr cannot deliver any extra capacity because it is optimizing the wrong thing.

Conclusion

When someone is lying continuously to you to sell their tech, rely on censorship, be sure they have ulterior motives. Do not buy or you’ll get scammed.

Schnorr signatures for (not so) dummies

This article is a follow up Schnorr signatures for dummies, make sure you understand its content before reading this one. This article is a bit more technical and complex than the first one

Schnorr signatures are very interesting beasts. If you were interested in the first article and want to learn more about them you are at the right place. However, please be reminded that these blog posts won’t make you a cryptography expert, but simply to convey you a general intuition about how Schnorr works and what you can do with them.

Using (R, s) instead of (e, s)

In the previous article, we explained how the signature can be produced the pair of number (e, s). However, over the years a variation of this scheme has become popular. Instead of sharing (e, s) Alice will share a pair (R, s) with R = k * G. This may not be obvious at first, but this is completely equivalent. R can be computed from (e, s) via R = s * G + e * P and e can be computed from (R, s) via e = H(m || R). As a result, sharing (R, s) provides the same information as providing (e, s).

While computing e from R can be used to verify the signature, using (R, s) validation is usually done in a different manner, by checking that R = s * G + H(m || R) * P.

The important difference is that we run the hash function first, and then do elliptic curve operations, rather than starting with elliptic curves operations and then running the hash function like it is done with (e, s). This seemingly small difference in the way we compute things allows to do various interesting tricks.

Public key recovery

Schnorr signatures allow to recover a public key from a message and a signature via the procedure

1
2
R = s * G + H(m || R) * P
P = (R - s * G) * H(m || R) ^ (-1)

Hardened security

Let’s imagine Alice signed a message m with her public key P = x * G. It is possible for Bob to use Alice’s signature to forge another signature for another public key Q = P + y * G as (R, s – H(m || R) * y) on the same message.

1
2
3
4
5
e = H(m || R)
R = s * G + e * P
R + e * y * G = s * G + e * P + e * y * G
R + e * y * G = s * G + e * Q
R = (s - e * y) * G + e * Q

Depending on the situation, this may or may not be a problem. Because Bob doesn’t know x, Bob cannot create a signature with the public key of his choice. However, in some cases such as key derived using BIP32, it is possible if Bob knows Alice’s master public key to transform Alice’s signature using one public key into another for any public key derived for the same master public key. The details of how this works are a bit off topic here, so I won’t spend too much time on it. Long story short: this is something that could reduce Schnorr signature security in some specific scenarii, and so it is worth fixing.

To do so, we will hash the public key in addition of the m and R when signing and verifying the transaction, such as e = H(m || P || R). Because any change in the public key would produce unpredictable changes in e, Bob cannot use an existing signature to do anything but verify it. This also makes recovering the public key impossible.

Compact and private n-out-of-n multisig

Let’s assume Alice and Bob want to sign the same message. They could produce one signature each, but it would take twice as much space as one signature (!) and would require run the verify procedures twice (!!). Ideally, we’d like them to produce only one signature for both Alice and Bob, and this can be done using Schnorr.

Alice has a private key x0 and a public key P0 = x0 * G. Bob has a private key x1 and a public key P1 = x1 * G. They can add their public key to produce a multisig public key P = P0 + P1 that is common to both of them. We know that P = (x0 + x1) * G, but only Alice knows x0 and only Bob knows x1, so they will need to cooperate to produce a signature. Alice and Bob know that the public key is a multisig, but interestingly enough, it looks like a regular public key to everybody else, and the signature will look like any signature.

To do this, they’ll proceed in 2 rounds. First, Alice and Bob will chose a value for k: k0 and k1. Alice will compute R0 = k0 * G and give it to Bob. Bob compute R1 = k1 * G and give it Alice. Alice do not know k1 and Bob do not know k0, but both can compute R = R0 + R1 and e = H(m || P || R).

Alice will compute s0 = k0 – e * x0 and Bob s1 = k1 – e * x1. From s0 and s1, the value s = s0 + s1 is computed, forming the signature (R, s). This process can be extended to include an arbitrary number of participants.

The verification is done as explained before, by checking that R = s * G + H(m || P || R) * P.

By expanding this into Alice’s and Bob’s value, it is clear why. If we use e = H(m || P || R), we get R = s * G + e * P and further expansion gives:

1
2
3
R0 + R1 = (s0 + s1) * G + e * (P0 + P1)
(k0 + k1) * G = (s0 + s1) * G + e * (x0 + x1) * G
k0 + k1 = (s0 - e * x0) + (s1 - e * x1)

Which works if

1
2
k0 = s0 - e * x0
k1 = s1 - e * x1

Sadly, while this scheme is attractive, it is actually not secure if either Alice or Bob is trying to cheat. Let’s assume Alice wants to cheat. She will ask Bob’s public key P1, and then pretend her public key is Q = P0 – P1. This way, when Bob thinks he is committing to a public key P = P0 + P1, he is in fact committing to the public key P0 = Q + P1. Now Alice has full control and Bob doesn’t know it.

To work around this problem, we use a method to compute the multisig public key which is a bit more involved. First we compute C = H(P0 || P1), second we compute Q0 = H(C || P0) * P0 and Q1 = H(C || P1) * P1. The public key is P = Q0 + Q1. The same scheme as described above work if Alice uses y0 = x0 * H(C || P0) as private key and Bob y1 = x1 * H(C || P1). By using a different factor for Alice and Bob, and making this factor depends on the choice of Alice and Bob’s public keys, it becomes impossible for Alice to chose a key depending on Q1, Bob’s public key. Doing so would affect C, which in turn would affect Q1 in a non linear manner, making this task impossible.

Batch validation

It is common that a system needs to verify a large number of signatures instead of a single one. When validating a signature, the most expensive operations are the 2 elliptic curve multiplications involved. Using the (R, s) representation, we can verify the signature doing the hash operation first, and then perform elliptic curve operations. This means we can use various accounting tricks to validate a group of signature at once.

We established that a signature (R, s) is valid if R = s * G + H(m || P || R) * P. That means that a group of valid signature will verify

1
2
R0 + R1 = s0 * G + H(m0 || P0 || R0) * P0 + s1 * G + H(m1 || P1 || R1) * P1
R0 + R1 = H(m0 || P0 || R0) * P0 + H(m1 || P1 || R1) * P1 + (s0 + s1) * G

Because the multiplication by G can be factorized, by summing all the values of s before doing the multiplication, only one multiplication per signature is required, plus one for the sum of all s * G.

Sadly, this isn’t secure. This is because an attacker can produce a set of signatures that cancel each others. To work around this, we will introduce a random factor z per signature. Not knowing the factor z for each of his signatures, the attacker is now unable to have them cancel each others.

1
z0 * R0 + z1 * R1 = z0 * H(m0 || P0 || R0) * P0 + z1 * H(m1 || P1 || R1) * P1 + (z0 * s0 + z1 * s1) * G

While we defeated the attacker, we also defeated out nice batch optimization by adding one extra elliptic curve multiplication per signature: zn * Rn. Hopefully not, we have one more trick to pull using the fact that

1
z0 * Q0 + z1 * Q1 = (z0 - z1) * Q0 + z1 * (Q0 + Q1)

By keeping a sorted list of point and factors, we can recursively pick the 2 largest values of z and associated point, do the above mentioned transformation, and reinsert the 2 new z and associated points int he list. Every time z0 – z1 is 0, a point can be removed from the list. Doing so properly will see all values of z but one converge toward 0 and leave us with only one elliptic curve multiplication at the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
auto sumOfS = 0;
Heap!(Scalar, Point) heap;

// Ideally, we'd like to build the whole collection and then heapify
// because it is faster that way, but to keep things short
// we won't in this example.
foreach (sig; signatures) {
    auto z = getNewRandom();
    sumOfS += z * sig.s;
    heap.push(z * H(sig.m || sig.P || sig.R), sig.P);
    heap.push(-z, sig.R);
}

heap.push(sumOfS, G);

while (heap.size > 1) {
    (z0, Q0) = heap.pop();
    (z1, Q1) = heap.pop();
    heap.push(z1, Q0 + Q1);

    // We know that z0 >= z1, so z values will get smaller
    if (z0 != z1) heap.push(z0 - z1, Q0);
}

(z, Q) = heap.pop();
assert(z * Q == 0);

Obviously, reducing the number of multiplications come at the cost of having way more additions to do, but the more z values you have, the easier it becomes to find 2 that cancel each others, and the more multiplications you save. This quickly becomes profitable as the number of signatures to check grows.

Conclusion

We have seen variations of the Schnorr signature scheme that allow both more efficient signature verification using (R, s) instead of (e, s) and improve its security by using H(m || P || R), at the cost of being unable to recover the public key from the signature.

Alice signs with R = k * G and s = k – H(m || P || R) * x.
Bob verify with R = s * G + H(m || P || R) * P.

We also explained how we can create n-out-of-n multisig with a single Schnorr signature, and finally, how we can verify many signatures at once efficiently.

There are a few more fancy things you can do with these signatures, but with what was presented here you have enough to understand the main use cases and how they can be made secure and fast, which is where we wanted to go.

Variable size integer encoding

It is a known fact of nature that most integers are small. When transferring data over the network, or to/from disk, or pretty much anywhere the IO is slow, keeping data compact is a plus. Obviously, compression is an option, but it is fairly CPU heavy. Taking advantage of the fact that, in practice, most integer values are small is an option to effectively reduce the amount of data for a modest cost in term of CPU.

Continue reading

Using Merklix tree to shard block validation

When scaling a system, there always comes a time when all of the processing cannot be done on one machine. This problem is solved by spreading the workload across several machines. This presents some challenges however, solutions are well known in the industry.

In a trustless system such as Bitcoin, peers generally do not trust each other. Currently this is solved by having all peers doing all of the validation, which obviously doesn’t scale, at all. If we are to shard the blockchain, how can a node trust that other shards are validating properly ?

Continue reading

Efficient mempool synchronization using bloom filters and entropy coding

One of the major challenge to scale bitcoin is that a lot of the work done by nodes is reactive. Nodes receive a block and start validating. This takes time and resources and is right in the hot path. The problem gets worse the bigger the block are, to the point were consensus takes more and more time to be reached. At some point, consensus cannot be reached.

In order to improve scaling capabilities of the network, it is key that nodes do as much work as possible ahead of time. When a block is received, node just have to assert that the node effectively contains what they expected, which speeds up validation significantly.

Continue reading

Using Merklix tree to checkpoint an UTXO set

In a previous article, I introduced Merklix trees as a way to cryptographically describe an unordered set or map. It is possible to produce proof that an element is contained or absent of the datastructure in o(ln(n)), and use these proof to mutate the structure, even without knowing its full content.

I will now explain how this can be used to help handling the UTXO set in blockchain technologies like Bitcoin.

Continue reading

Introducing Merklix tree as an unordered Merkle tree on steroid

Merkle tree are awesome. They allow to hash an ordered set of elements and provide a way, known as a Merkle proof, to prove that a given element is at some position in the set without having to provide the whole set. While this is a very useful tool, the fact that it is ordered can be somewhat troublesome. Inserting or removing an element in the middle of the set will require significant work and, more generally, 2 sets containing the same elements, but in a different order will yield 2 radically different trees.

Today, I’d like to introduce a new tool to the software engineer toolbox, which, as far as I know – and that probably tells more about my searching-foo than anything else, hasn’t been proposed before. The goal is to hash an unordered set in such a way that:

  • The end result is the same, no matter in what way the tree is created
  • Insertion and deletion are ln(n)
  • It is possible to produce a proof that an element is contained in the set without producing the set

Continue reading

On code review

Code review has become a standard programming practice, for open source projects, but also for many companies that practice it in house. While this practice has proven to be very valuable, many developers struggle with it. So here are some tips and tricks that will help you work more efficiently when code review is involved.

There are (at least) 2 persons involved in code review. Someone that I’ll call a contributor, who want a piece of code to be merged, and a reviewer, who try to confirm that this piece of code meets quality standards and won’t introduce too much complexity compared to the value it provides. Making the whole exercise efficient requires each party to understand and empathize with the other and act accordingly.

Continue reading