Add a transaction origination timestamp and expiration TTL

[gregorycollins]

It would be very useful for chainweb if Pact transactions had the following mandatory fields in PublicMeta:

• origination (or "creation") timestamp

• time-to-live. TTL can be expressed in seconds, and maximum value should be small enough that we can fit it into Word16.

Much of the rest of this note is about how this data will be consumed on the chainweb side.

Validation

For the semantics of the new fields, consider a block B having block timestamp tB and transaction s having origination timestamp tS and TTL dS. The following inequalities must hold for s to validate in block B:

• tS < tB (the transaction cannot be newer than the block)
• tS + dS <= tB (the transaction must make it into a block before expiry)
• tB > t_{parent(B)} (block time must be strictly monotonically increasing)

Clock skew / future timestamps

To avoid having to synchronize on timestamp, nodes need to deal with inputs arriving from the future. Let's talk about clock skew for blocks and clock skew for transactions.

Clock skew for blocks

We will choose a maximum block clock skew k. If a node receives a block B having a timestamp more than k seconds in the future, it should be dropped. If the most recent block had a future timestamp (due to skew), it is important that newBlock account for this to maintain block timestamp monotonicity.

Clock skew for pact txs

We will not allow any skew for transactions relative to blocks, i.e. block time is absolute. This means that transaction clock skew has to be handled at the Chainweb Pact RestAPI/mempool level, since this is the component that receives new pact transactions via the /send endpoint.

Transactions arriving at a node with a timestamp that is not "too far" in the future (here we can make maximum clock skew configurable, but O(10 seconds) is probably ok) will be placed into "purgatory" until after the transaction begin time is past. Once the origination time is no longer in the future, the transaction will be released to the regular pending mempool for candidate inclusion into the next mined block.

[emilypi]

Thanks @gregorycollins. Assigning to myself, and I can have this out today for Chainweb. How does the following sound for PublicMeta?:

data PublicMeta = PublicMeta
  { _pmChainId :: !ChainId
  , _pmSender :: !Text
  , _pmGasLimit :: !GasLimit
  , _pmGasPrice :: !GasPrice
  , _pmTTL :: !Word16
  , _pmCreationTime :: !Int64
  } deriving (Eq, Show, Generic)

Int64 is a representation of time in Micros, which aligns with our representation in Chainweb.

[larskuhtz]

tB > t_{parent(B)} (block time must be strictly monotonically increasing)

This is already enforced during block validation.

[larskuhtz]

Clock skew for blocks

Consensus has following rule: If a node sees a block with tB in the future (with respect to the current clock) it is dropped or ignored until it tB is current. There is no formal assumption about clock synchronization. We think, that above rule provides sufficient incentive for nodes to keep their clocks in sync with respect to universal time (SI seconds since unix epoch).

We will choose a maximum block clock skew k

Consensus makes no assumptions about clock skew. It just ignores events that happened in the future with respect to the local clock. (If the network link of a node doesn't allow the node to sync its local clock with UT to values sufficiently smaller than the block rate, it won't be able to successfully participate in consensus in any case.)

The current behavior is that validation fails, which is equivalent to dropping the node. There is a long standing Github issue for adding a short-term "staging" cache for blocks for which validation fails due to a temporary condition and may pass in the future.

[gregorycollins]

Thanks @gregorycollins. Assigning to myself, and I can have this out today for Chainweb. How does the following sound for PublicMeta?:

data PublicMeta = PublicMeta
  { _pmChainId :: !ChainId
  , _pmSender :: !Text
  , _pmGasLimit :: !GasLimit
  , _pmGasPrice :: !GasPrice
  , _pmTTL :: !Word16
  , _pmCreationTime :: !Int64
  } deriving (Eq, Show, Generic)

Int64 is a representation of time in Micros, which aligns with our representation in Chainweb.

I would make at least a type alias (probably not a newtype) for both, e.g. type TTLSeconds = Word16 -- usually for timestamps you add a comment indicating the format (e.g. "micros since unix epoch")

[larskuhtz]

The current consensus policy with respect to block times are documented here: https://github.com/kadena-io/chainweb-node/blob/2a9c5ab44f30d2faadbd3b3361cb7d6a8f2aad48/src/Chainweb/BlockHeader.hs#L307

[gregorycollins]

The current behavior is that validation fails, which is equivalent to dropping the node. There is a long standing Github issue for adding a short-term "staging" cache for blocks that validation due to a temporary condition and may pass in the future.

We can get away with being absolute about timestamps for now (especially since our validate processing is slow), but some laxity in allowable clock skew is really desirable for distributed systems.

If a node can generate and send blocks to a remote receiver in time t, and we have clock skew s >= t, we can get into a bizarre situation where nodes can only meaningfully participate on the network with other nodes that are sufficiently far away (where round-trip latency delays things long enough for time to catch up to the "future" blocks the skewed node is sending).

[larskuhtz]

time-to-live. TTL can be expressed in seconds, and maximum value should be small enough that we can fit it into Word16.

My understanding is, that this value may have a big impact on the performance of Chainweb. Assuming a target block rate of 2 blocks per chain per minute, actual per chain block time can range roughly between 0.6 and 6 blocks per minute.

Assuming at most 1000 tx per block, a TTL value of 1 day may span over up to 8,640,000 transactions per chain and 172,800,000 tx for 20 chains. (Ethereum has processed less than 550,000,000 tx since its inception and the highest number of tx ever processed on a single day was 1,349,890.)

[gregorycollins]

time-to-live. TTL can be expressed in seconds, and maximum value should be small enough that we can fit it into Word16.

My understanding is, that this value may have a big impact on the performance of Chainweb. Assuming a target block rate of 2 blocks per chain per minute, actual per chain block time can range roughly between 0.6 and 6 blocks per minute.

Assuming at most 1000 tx per block, a TTL value of 1 day may span over up to 8,640,000 transactions per chain and 172,800,000 tx for 20 chains. (Ethereum has processed less than 550,000,000 tx since its inception and the highest number of tx ever processed on a single day was 1,349,890.)

N.B. Word16 in seconds means maximum TTL would be 18 hours. We have to be able to keep an 18 hour window of transaction hash information online, right?

[larskuhtz]

time-to-live. TTL can be expressed in seconds, and maximum value should be small enough that we can fit it into Word16.

My understanding is, that this value may have a big impact on the performance of Chainweb. Assuming a target block rate of 2 blocks per chain per minute, actual per chain block time can range roughly between 0.6 and 6 blocks per minute. Assuming at most 1000 tx per block, a TTL value of 1 day may span over up to 8,640,000 transactions per chain and 172,800,000 tx for 20 chains. (Ethereum has processed less than 550,000,000 tx since its inception and the highest number of tx ever processed on a single day was 1,349,890.)

N.B. Word16 in seconds means maximum TTL would be 18 hours. We have to be able to keep an 18 hour window of transaction hash information online, right?

We could add additional constraints, lowering the allowed window to less than 18h. But it's good to know that it can't be more. That gives us a hard upper bound that we can rely on in algorithms.

[larskuhtz]

The current behavior is that validation fails, which is equivalent to dropping the node. There is a long standing Github issue for adding a short-term "staging" cache for blocks that validation due to a temporary condition and may pass in the future.

We can get away with being absolute about timestamps for now (especially since our validate processing is slow), but some laxity in allowable clock skew is really desirable for distributed systems.

I think, iognoring blocks and considering them when they are recent adds this laxity.

If a node can generate and send blocks to a remote receiver in time t, and we have clock skew s >= t, we can get into a bizarre situation where nodes can only meaningfully participate on the network with other nodes that are sufficiently far away (where round-trip latency delays things long enough for time to catch up to the "future" blocks the skewed node is sending).

The current behavior doesn't ignore skew. It just doesn't include it into the protocol, but instead designs a protocol, that (hopefully) incentivizes the participants to keep their clocks synchronized (by associating an economic disadvantage with clock skew).

For instance, a mining node that produces blocks in the future (from the perspective of other nodes) will see its blocks ignored by other nodes. A validating node that commits on forks with blocks that are in the future (from the respective of other nodes) will find itself producing loosing forks. A miner that post-dates blocks may limit its ability to include recent transactions into their blocks.

The idea is to set the rules that the economically optimal strategy of each node is to minimize clock skew.

[larskuhtz]

The comment on the blockCreationTime field of Chainweb.BlockHeader.BlockHeader, mentions that we still have to check that the assumptions behind the current protocol actually hold under different attack models.

[emilypi]

Added in #610