We are currently using the default sp_timestamp::InherentDataProvider::from_system_time() call to get the timestamp that will be passed into the runtime. The problem with that is that we are building blocks as the "relay chain" tells us, this means that we may start some time before the actual slot. This can lead to using the same slot two times, because we just do timestamp / slot_duration. The solution to this, is as we do it while validating the block. We should just use the relay chain slot to calculate the correct timestamp for the parachain (relay_chain_slot * relay_chain_slot_duration).

To implement this, we should create a trait:

trait TimestampInherentDataExt {
    fn from_relay_chain(relay_header: &Header) -> Self;
}

And implement it for the sp_timestamp::InherentDataProvider. Then we can use this in the service to construct the correct timestamp inherent.