Elastic Scaling (fka Parachain Scaling by Parablock splitting)

[pepyakin]

This post assumes familiarity with the parachains. Refer to the glossary and this article for the detailed description of the parachain consensus.

A parachain reaches the limits of throughput of a single slot. What options does it have?

There are incoming scaling improvements, such as async backing, which should allow more time for PVF execution. It does not change the problem fundamentally. At some point, even that higher ceiling will be reached. There are other scaling ideas, such as squaring polkadot, which essentially increases the available number of slots.

One may say that the parachain should deploy the second parachain instance. That is, the parachain will acquire another parachain slot, deploy the almost same code there, and subjugate it governance-wise. That might work. In the end, it’s similar to the now classical scaling solution — sharding.

Sharding, however, has downsides. Communication between the shards is limited and suffers from increased latency. The complexity caused by requiring intershard communication can be hidden by introducing complex mechanisms or that complexity could be dumped on the developers’ shoulders.

Here I want to propose an alternative: parablock splitting. The crux of it is to decouple the notion of one parachain one core. Right now, each parachain with a parachain slot can submit only one parachain block candidate for every relay chain block. With the parablock splitting, a parachain would be allowed to submit 2 candidates for a single parablock.

Here’s what it will look like:

A parablock is logically split into two parts. E.g., the first 50 transactions end up in the first part and another 50 in the second. The parablock will have two state roots. The intermediate state root is obtained after executing the first 50 transactions and the post-state root.

During authoring, the collator packs the first 50 transactions in the first candidate. The PoV for that candidate will contain the witnesses required for executing that batch of transactions. Essentially, the candidate will prove that the state transition from the pre-state to the intermediate state is correct.

The very same thing happens with the last 50 transactions. The collator packs the last 50 transactions with the witness required to prove the correctness of state transition from the intermediate state root to the post-state root.

There is nothing special about the number 2. Potentially it can be more than that.

I am not entirely sure it is possible to implement the parablock splitting with the current structure of the parachains host and cumulus (Although lmk if you have an idea), and if it is, then it will be clunky. One example, it’s not clear what to do wrt messaging. XCMP enables channels between a pair of para ids and the parablock splitting will either mess it up or require some workarounds (e.g. sending messages are allowed only in the first candidate).

A better way is to treat a core independently from a parachain slot and allow one parachain to claim two cores within one relay block. Those candidates would be verified in parallel. If any of those candidates fail (e.g., not achieving availability or if PVF fails), then the whole chain of candidates is rolled back. All candidates are executed with the same PVF, the PVF of the parachain. The output of the last’s candidate PVF should write into the new head data. The messaging context is the same for all candidates, i.e., their PVFs can send and receive the messages (ordered by order of execution).

It’s not entirely clear how to reconcile this with the current market of parachain slots and parathread bids. This is also related to the discussion of the exotic para cores scheduling. I can see that reserving the second slot might be too big of a commitment. On the other hand, IIUC, the parathread bidding might not be quick enough to accommodate the changes in demand.

[burdges]

It’s doable I think… We’re basically incurring a pre-finality debt for the relay chain to check the state root updates align across cores, which may add complexity if we want more complex storage schemes, like KZG commitments, but really does not sound too problematic.

Yes, XCMP needs some special handling, due to having a special presence in the block header and/or candidate receipt. I’ve not thought about the details but it could likely be adapted with pre-finality debts and special relay chain handling, vaguely like how state roots are adapted. At worse doing XCMP only from the first block works.

It sounds like you want parachains to do this for bursts of activity, not just own a second slot? That’d be cool, but yeah we never properly designed doing bidding fast, etc.

---

We should afaik be able to process many thousands of transactions in the two seconds allocated to running a parachain block. As such, we should likely be optimizing the parachain code itself more. We also have the multi-threading models discussed long ago by gav and me.

We can make the crypto 40% cheaper &smaller by doing pre-batching aka half-aggregation of signatures, or doing snarkpack on a groth16 chain like a zcash sappling clone. We can make dense parts of merkle proofs cheaper using techniques I’ve explained many times. We cannot necessarily make sparse parts of merkle proofs too much cheaper directly, although I’ve some crazy pants ideas. I’d assume crypto and merkle proofs gets checked by separate threads already, but if not that’s another optimization, and Gav’s suggestion of using GPUs for the merkle proorfs clearly requires this anyways.

We can surely better optimize how we work with state. I’d expect various whole block optimizations help somewhat too. As an example, my zk uniswap proposal requires fixing the uniswap bid & ask prices for the whole block, but this could be done for a non-zk uniswap too, and doing so avoids much MEV and intermediate state writes. I’d think those intermediate state writes should not incur hashing costs anyways, and if they do then this should be fixed separately, but it’s still more complex logic than a couple inequalities. Afaik whole block optimizations are not really smart contract friendly, but smart contracts are crap anyways so who cares.

[rphmeier]

This reminds me of Back and include multiple blocks at once for a single availability core · Issue #4951 · paritytech/polkadot · GitHub .

The category of approach that makes the most sense to me is to just give parachains the option to have more than one core at a time and to express dependencies between blocks occupying those cores, so if one block fails to be included it takes down all the dependents as well.

Parachains could acquire extra cores by long-term lease, or collators could acquire them temporarily by participating in parathread auctions. That is, parachain slots are used to guarantee capacity whereas parathread auctions are used for burstiness.

If we implement parathread auctions in the right way, we should have a conceptual alignment between parachains and parathreads, in that parathreads would just be parachains with 0 cores.

[pepyakin]

I agree that the throughput that can be achieved with only one slot could and must be optimized. However, that’s out of the scope of this post. I want to focus this post on what a parachain should do after it squeezes everything it can from a single slot. Please consider creating a new topic(s) for discussing those various techniques in detail.

It sounds like you want parachains to do this for bursts of activity, not just own a second slot? That’d be cool, but yeah we never properly designed doing bidding fast, etc.

Not necessarily. I think the second slot could also be used to accommodate a persistent increase in activity.

[rphmeier]

related somewhat: Parathreads: Take II · Issue #5492 · paritytech/polkadot · GitHub

[burdges]

I like the parathread scheduling proposal but it reveals incompatibilities between parathread scheduling and parablock splitting: A fast moving parathread cannot typically buy extra block space 30s in advance.

Instead, we should discuss short-term whole slot leases too, which buy parachains an extra whole core for fixed time periods, like hours, epochs, or days.

What do traffic bursts look like in web2 services? Are they regional due to ad campaigns, language, etc. and thus do not last 24 hours? If so, then we need 1 hour leases or less.

Can we do short-term parachain slot leases not too far in advance? I think so… I suspect they’re simpler than parathreads actually.

[rphmeier]

We discussed this in-person and are interested in pursuing a pricing model for parathreads/boost cores which isn’t based on auctions but instead based on control theory using supply/demand of cores - when cores aren’t being purchased by parathreads/boost the price goes down. When they are, the price goes up.

We also discussed strategies for parallelizing block backing by having each of the multiple cores for a parachain assigned to a different group, but this is maybe unnecessary.

There will be lessons to learn from AWS / cloud pricing I suspect.

[burdges]

We various parameters here like: How early should sales be done? Is some floor established by parachain auctions? How long are these short-term leases? We tied parathreads to specific collators, but bulk purchases should be parachain wide, so maybe the parachain rewards logic must handle this?

---

I omitted an important side issue in my derail above: There exist parachain “swarm” designs with natural state sharding, like the zcash scaling proposal by Daria Hopwood, and some simple state channel chains, including game chains with locality. We should encourage this over sequenced multi-core usage as it controls state size better, but it’s complicates the parachain of course, and doing this dynamically sound horrific.

[SamuelHaefner]

Out of curiosity: How is excess demand for cores handled technically if we use a pricing model for cores? Is there going to be a queuing mechanism, and if so, what would it look like? With auctions, the solution is simple: just serve the parachains according to their bids. But if everyone is forced to pay the same price, then on what dimension do you order the requests? I think that this could have an impact on the parathreads’/parachains’ willingness to pay.

[burdges]

We’ve so far discussed some target unused core level, decrease prices when we’ve more unused cores, and increase prices when we’ve too few unused cores, which brings questions like if the prices respond fast enough with so little information. In this, we’re still thinking parathreads I guess, but actually our short-terms leases do run long enough for auctions.

Any non-auction models should be first-come-first-served probably because anything else surely requires better randomness, no? We’ll provide a cumulative VRF randomness source in sassafras, which while biasable, but maybe suffices if one analyzes how bias impacts say the random auction close scheme.

We’ve discussed deploying GitHub - kobigurk/aggregatable-dkg: Aggregatable Distributed Key Generation for better randomness, after first optimizing it properly, but it brings considerable complexity.

Interesting, if short-term leases became our most desired product, which sounds plausible, then we could maybe price real parathreads off those auctions plus some price increment.

[SamuelHaefner]

@burdges

We’ve so far discussed some target unused core level, decrease prices when we’ve more unused cores, and increase prices when we’ve too few unused cores, which brings questions like if the prices respond fast enough with so little information. In this, we’re still thinking parathreads I guess, but actually our short-terms leases do run long enough for auctions.

What is the main reason not to run auctions? Too many actions required from the parathreads if lease periods are very short?

@burdges

Any non-auction models should be first-come-first-served probably because anything else surely requires better randomness, no?

I guess I am just asking because I don’t fully understand the underlying tech: I presume that asking for a core works through submitting a transaction. But if everyone is doing this all at once, who decides which transactions were before others? Or does this happen off-chain? Sorry for the stupid question.

[rphmeier]

Thanks for weighing in, @SamuelHaefner

In all cases, we need to give at least K (~=1) relay-chain blocks of lead time to know which parathreads are going to be assigned to which cores. This is crucial for collators to discover validators, validators to anticipate their assignments, etc.

Likewise, both in the case of parathreads and for boosting parachains by assigning extra cores, we’d like the lead time between putting in a bid and being scheduled onto a core to be minimal. I’m not opposed to auctions, but they may need to run for 5-10 minutes and this is not ideal from a product perspective, especially for parathreads. For that reason I suggested to use tools from optimal control theory to set ‘spot’ prices and sell short-term core occupancy rights.

We have a fixed amount of the underlying resource in question we wish for the relay-chain to sell: availability cores at specific times. We cannot oversell this resource because there is no capacity to meet surplus demand (maybe a discussion to have here), and we also know exactly how much of this resource we have in the near future (i.e. for this session and the next). Some types of claims will be for fixed periods (e.g. 100 blocks starting at block N) and some will be flexible (e.g. a claim for a single block).

If demand is less than supply, then there is in principle no issue.

One design issue for short-term claims is that even if the availability core is scheduled for a particular parachain, there is no guarantee that the claim will be utilized. This can be due to the fault of the collator (not authoring or transmitting a candidate), the backers (not backing the candidate), or the block author at that relay-chain block height (not including the backed candidate). We need some flexibility in retrying parathread claims for that reason.

[rphmeier]

@SamuelHaefner

I presume that asking for a core works through submitting a transaction. But if everyone is doing this all at once, who decides which transactions were before others

No, it doesn’t work like this. Cores and core assignments are determined by the relay-chain runtime and can be computed based on a relay-chain state. A relay-chain block is authored and the author may place any (or 0) of the backed parachain candidates into the new block, as long as they obey the core assignments as-of the parent relay-chain block. Most of the coordination happens off-chain at the p2p layer, but the relay-chain block author ultimately can filter and limit what they want to post on-chain.

[burdges]

As a summary…

We think parablock splitting need not support actual parathreads because actual parachain projects need short-term core leases more than individual parathreads blocks.

These short-term leases would run for 1hour or 10min or similar, whatever we determine by talking with cloud providers and maybe advertising companies.

We could award short-term leases either by first price auction, either simple or candle, or else by price adjustments like Rob suggests. if doing candle auctions then our randomness should be the new progressive block VRF collection in sassafras, not the individual block VRF outputs.

We’ll likely choose price adjustments because we doubt auctions bring too much benefit really, aside from handling wild price swings better. Assuming we do price adjustments instead of auctions, then we must sequence parachain priority in buying leases by public on-chain randomness, not first-come-first-served.

If doing auctions then we’d deterministically price parathread blocks as some small multiple of the short-lease auction block price, depending upon usage, so no auctions for parathread blocks, and we hope first-come-first served does not become problematic.

Assuming we do price adjustments then we could similarly set parathread prices based upon short-term lease prices, under the assumption that information from parathread prices should not control short-term lease price. Anyone think prathread prices should influence short-term lease prices?

[SamuelHaefner]

Thanks for your explanations, @rphmeier. That was very helpful.

Since we are only selling very short-term leases, I thought we might sacrifice some of the candle auction’s security and run something simpler instead. A first-price auction, for example, like Jeff suggests. I’d be curious what @AlistairStewart thinks about that.

I think Jeff’s idea of using the resulting prices in the short-term lease auctions for parathread block prices is very interesting. The question of whether the prices of the two will be linked is important.

One consideration is substitutability: Does it make sense for parachains to buy parathread blocks if they wouldn’t secure a short-term lease in the auction? If so, then the demand for the two things will be linked. If not, then maybe not.

Another consideration is: Do we assume that parathreads and parachains are hit by common demand shocks for cores, or are their business models sufficiently differentiated so that their demand is uncorrelated?

[rphmeier]

@SamuelHaefner

I think Jeff’s idea of using the resulting prices in the short-term lease auctions for parathread block prices is very interesting. The question of whether the prices of the two will be linked is important.

In practice we cannot rely on linking them because we should expect that parathreads will live in isolation for a while as these more complex scheduling topics are worked out. I believe that the best route would be to design a controller for the prices of parathread slots in isolation and then expand from there.

@SamuelHaefner

Does it make sense for parachains to buy parathread blocks if they wouldn’t secure a short-term lease in the auction? If so, then the demand for the two things will be linked. If not, then maybe not.

Yes, I think this is quite likely. For instance, it could be possibly be used for MEV. Let’s say there’s an incoming queue of messages which is too long to process in a single block but long enough to process in 2 blocks. Then let’s say there’s a message in the latter part of that queue which exposes an arbitrage opportunity. Then a parachain collator might ‘boost’ the parachain for a single block in order to harvest the arbitrage by authoring two blocks at the same time.

This is a hypothetical; in general I’d assume that demand is linked not just because of this use-case but also because we cannot predict all use-cases of both services.

Do we assume that parathreads and parachains are hit by common demand shocks for cores, or are their business models sufficiently differentiated so that their demand is uncorrelated?

I think it’s best to assume that out of the broader universe of parathreads which are registered and could purchase a claim, some wil overlap will any demand shock that a parachain experiences.

Also, conceptually, there should be no difference between parathreads and parachains. The only difference is the number of long-term reserved cores that they have. I believe that it should be possible for parathreads to also participate in any kind of short-term core auctions we’d come up with.

[SamuelHaefner]

@rphmeier

In practice we cannot rely on linking them because we should expect that parathreads will live in isolation for a while as these more complex scheduling topics are worked out. I believe that the best route would be to design a controller for the prices of parathread slots in isolation and then expand from there.

Fair enough. I agree. So, basically, that means finding a function that takes current demand for parathread blocks and outputs a price in a reasonable manner? I guess we could also define some parameters of the function that can be adapted through governance. (I would think it is a very hard problem to get the parameters right in the first place, without knowing how the demand dynamics actually pan out.)

[rphmeier]

Yes, that seems reasonable. I think it’s a good idea to leave as many parameters up to governance as possible, and to expect that any initial solution without real-world data will only be directionally correct, which is acceptable.

[rphmeier]

This is getting off-topic, but one possible application of ‘Parachain Boost’ short-term slots would be for Ephemeral Chains - parathreads which are spun up with a runtime, perhaps comprising a single pallet, and which reserve 1 or more cores for a short period (an hour, a day, a week). This chain can handle some large computation or operation and then terminate. Other chains would be able to read the result from the final header produced by the ephemeral chain.

[taqtiqa-mark]

Possibly controversial, definitely left-field…

@pepyakin

A parachain reaches the limits of throughput of a single slot. What options does it have?

Reading this thread, and assuming no background knowledge, one can imagine a reader concluding that the Dotsama/Substrate tech-stack doesn’t scale. Weird (and wrong) because that is what it was designed to do - scale.

The contradiction is resolved, at the expense of exposing another contradiction, by observing that this scalability issue is resolved (today) if your unit of development is a Relaychain and not a Parachain. You start off with your Relaychain having a single Parathread/Parachain and then you can scale up/out to all the Parathreads/Parachains that Relaychain can support.

The second contradiction this exposes is: Why are people trying to develop a decentralized ecosystem via a centralized “choke-point” - Polkadot? But that is another topic I’ll link to when I’ve gathered my thoughts appropriately.