How large does the largest turnNum need to be?

We’re currently looking into a couple of improvements to force-move to counteract some front-running attacks. As part of this, we’re proposing to store a couple of different quantities inside a single bytes32.

In order to do this we’re proposing making the following changes:

  • turnNum changes from uint256 to uint48
  • finalizesAt changes from uint256 to uint40
  • channelStorageHash changes from uint256 to uint160

Here are some rough size calculations to put these into context:

  1. There are roughly 2^25 seconds in a year.
  2. A max turnNum of 2^48 = 2^10 * 2^25 * 2^13 would allow for a channel where ~1000 states were exchanged every second for the next 8000 yrs. Which seems like plenty.
  3. A timestamp of 2^34 gets us to Wednesday, May 30, 2514 1:53:04 AM, so even if finalizesAt stays in seconds, 2^40 should be sufficient.
  4. A hash difficulty level of 2^160 is the same as used for ethereum addresses. (Although I don’t know the extent to which having to find a pre-image that is also a valid public key strengthens this.)
  5. Alternatively, the max hash rate of the Ethereum network to date was 300kGH/s ~= 2^39, so it seems like 2^160 is going to be plenty.

Does this seem reasonable? Can anyone think of reasons why any of these quantities needs to be bigger?

Also keen to hear opinions on the smallest values we could get away with. (If we could fit in a couple of turnNumbers into the bytes32, along with finalizesAt and the channelStorageHash, it opens up more options.)

1 Like
  1. A max turnNum of 2^48 = 2^10 * 2^25 * 2^13 would allow for a channel where ~1000 states were exchanged every second for the next 8000 yrs. Which seems like plenty.

Just a note on this throughput: If you were 300km apart (how far light goes in 1ms in a perfect vacuum), and exchanging 1000 states per second, the application and wallet would need to work with zero computation time.

  1. A timestamp of 2^34 gets us to Wednesday, May 30, 2514 1:53:04 AM, so even if finalizesAt stays in seconds, 2^40 should be sufficient.

A potential issue with this is if the block timestamp gets changed to milliseconds. However, that scenario would probably require a migration to a new adjudicator anyway, since any challenges that begin just before the fork would not behave as intended.

Also keen to hear opinions on the smallest values we could get away with. (If we could fit in a couple of turnNumbers into the bytes32, along with finalizesAt and the channelStorageHash, it opens up more options.)

If Alice and Bob have a high-throughput virtual channel, they can reset the turnNum to zero by starting a new virtual channel with an agreed-upon outcome, and then switch the funding from the old channel to the new channel. With this technique, even 16 bits might be enough.

It seems like your application+wallet needs to either
A1) gracefully handle a turnNum reset using this technique; or
A2) rely on never running out of turns in a given channel

For A2, I feel like you might need at least 32 bits, while for A1, it doesn’t seem like there’s any practical difference between 16 and 24 bits.

Just wanted to note: @tom, you have 8 bits currently unused in your proposal, so we may as well use those to increase the length of one or more of the fields. That is, unless these bits are reserved for some other purpose?

finalizesAt:

I think a uint40 is the minimum we should consider. Reasons being:

  • Solidity only supports uints that are a multiple of 8 bits.

  • 32 bits only allow for 136 years from the epoch (the year 2106) and this doesn’t seem enough. There’s a chance some of us will still be around then…

  • 40 bits gets us to the year 3682

  • 48 bits gets us to the year 8921556

Without getting bogged down in futurology, 56 bits would put enable our state channels to safely run until after the sun swallows the earth; which seems like a reasonable upper bound on what we should consider(!)

turnNum:

I like the idea of letting the speed of light inform the discussion about how large turnNum needs to be. However, the 300km distance that @AndrewStewart mentions does not represent all possible applications of state channels.

It’s not infeasible that you might want to run a state channel between participants who are very close, for example. For example, using Bluetooth (10m) or NFC (4cm). In those scenarios the speed of light is unlikely to be the limiting factor on how fast states are exchanged (in practice).

Other factors include the computational time taken to sign a state (as @AndrewStewart suggests), as well as the bandwidth of the connection. 2^48 = ~ 300 trillion states could be churned through in about 5 years if the updates weren’t much bigger than a signature and participants communicated over a GBit local network. However, such limits may change with time, whereas the speed of light will not. Although practical considerations are probably sufficient for our purposes, It’s interesting to see if the laws of physics set a useful limit on the turn number: if we can comfortably exceed that limit in storage, then the practical considerations become irrelevant.

Incidentally, High Frequency Trading operates at intervals down to microseconds, and could go lower: If it hits the limits set by the speed of light, this would be nanoseconds. This means a state update frequency of 1Mhz (or 1GHz). That could churn through 300 trillion states in about 10 years (or 3 days).

To me all this means is that 48 bits is not enough to ensure

A2) rely on never running out of states

simply by appeal to the finite speed of light c. For that we would use something like

max turnNum = max duration * c / minimum distance

One might argue that the max duration should be the same as finalizesAt, since channels may be opened near the start of the epoch. This seems to imply that turnNum should be about a factor 10^9 larger than finalizesAt (if we take minimum distance to be 30cm or so).

Note that this is, in most use cases, an inaccurate estimate, since both the distance and throughput can vary as a function of time. To accurately calculate the maximum turn number, you would therefore need to integrate over time, and in that case, uint48 seems like it would be enough.

This argument doesn’t apply to a use case like HFT, where two servers might sit next to each other forever, communicating constantly with near-zero latency. However, I don’t see any drawbacks aim for [A1] for now, since:

  1. We can deal with running out of turns with one of the strategies below;
  2. It’s incredibly hard to imagine a use-case for a long-running unidirectional state channel operating at 1GHz, or a bi-directional state channel where the behaviour is not random enough to run out of funds before running out of turn-numbers; and
  3. Unlike the “Year 2038 bug”, it’s feasible to increase turn numbers from, say, uint32 to uint64, if needed: We deploy a new adjudicator, and migrate to using it*

Of course, this attitude might very well be short-sighted!

*It’s hard to imagine that, once deployed to production, there will never be a need to migrate to a new adjudicator. Therefore, we will need to know how to pull off such a migration.


Restarting a virtually funded channel:

GIVEN: a virtual channel C1 between [Alice, Bob], funded by guarantor channels G1 & G2
IF: state.turnNum is “close” to maxTurnNum
THEN WHILE C2 is not covered by G1 & G2,

  • in each response, include two states with identical application data: one for the ongoing channel, and one for a new “cloned” channel C2
  • simultaneously redirect the guarantees in G1 & G2 to cover C2, rather than C1

FINALLY: discard C1 and continue in C2

This would slow down throughput while updating G1 & G2, by forcing each participant to sign two effectively identical states. Operating non-stop at 1GHz, which seems to be the absolute limit, this would need to happen

  • once every ~5 seconds using uint32 turn numbers, requiring any hub to be 100% responsive
  • once every ~20 minutes using uint40 turn numbers

Restarting an indirectly funded channel:

GIVEN:

  • an application channel C1 between [Alice, Bob],
  • a ledger channel L between [Alice, Bob], which allocates to C1
    IF: state.turnNum is “close” to maxTurnNum
    THEN for one step, send
  • the updated state s for C1
  • a state s equivalent to s' except with turnNum == 0, and with a different channel id for a channel C2
  • a state update s'' in L voting to change the allocation from s.channelId to s'.channelId
    FINALLY: discard C1
  • In this strategy, L could even be a virtual channel!
  • Practically, this would not reduce throughput. Perhaps there would be something like a GC pause once every 20 minutes, but the pause would be negligible compared to a GC pause.

If we’re ok with limiting channels to 2^8 participants, then we could use a uint8 bit map to store who has challenged so far at the current turn number. This can be used to prevent a participant from challenging multiple times at a given turn number.

Wouldn’t that limit it to 8 participants?

… yes, that’s right :flushed:

I’ve seen something similar crop up before when it was suggested that you stored one turnNum per participant?

as I currently understand it, the protocol only really cares that it’s seen a valid state (or series of states) with a final turnNum of #n. Only one challenge is permitted at a time, and it must strictly increase the turnNum when it is resolved. I don’t see the benefit of allowing multiple challenges at the same turnNum - as they can all be resolved by anyone with any later state? Nor do I understand why this turnNum should be different per-particpant?

The problem here is that the refute action results in a challenge being cancelled without the turn number being increased. The idea behind refute was to allow a cheap way of responding to provably bad behaviour - by just providing one later state signed by the challenger. Unfortunately, if you just provide one state, that doesn’t mean that everyone’s seen a valid series of states up to that point, so you can’t increase the turnNum. So you need a different way of preventing multiple challenges at the same turn number.

We’re currently thinking that we’re going to move the refute action from the protocol entirely. That way a challenge being cancelled always involves an increase to the max turnNum, which prevents multiple challenges at the same state.

@zakalwe, the idea behind the “per-participant turnNum” would be that it is updated per participant according to turnNumRecord[p] = max(turnNumReccord[p], supportedState.turnNumber)

  • increases for everybody when the adjudicator sees a supported state (in forceMove, respond, and checkpoint)
  • increases just for for p when someone calls refute to cancel an ongoing challenge from p.

This prevents multiple challenges by p at a given turn number: If Eve calls forceMove(s10), and Alice calls refute(s1000), Eve can now call forceMove only with states a turn at least 1000. Nothing would stop eve from calling refute(s9001) with a made up state s9001. This sets turnNumRecord[Eve] but that would stop her from calling any forceMove until the rest of the channel catches up to turn number 9001.

OK - I think I get that, thanks!

1 Like