Key generation in AES-based Proof-of-Time (PoT)

Iterative AES computation is used as Proof-of-Time (PoT) as described in the spec. To generate the AES key for the PoT at a certain slot X, a hash of the seed of the last proof is used. Specifically, key is derived as hash(last_proof.seed). A potential problem with this approach is that the key for slot X can be derived at the beginning of slot X-1 itself. However, since the seed is computed as hash(injected_block_hash||last_proof.get_output()), one would have to first derive the output of the last proof to be able to apply the key for X to the right seed value. So while the ability to derive the key for a certain slot a little bit ahead of time seems problematic, it may not be an immediate cause for concern. Nonetheless, one could still consider other methods of deriving keys that don’t have this potential issue at all.

4 Likes

Interesting indeed. What would you propose as a solution here?

Next slot seed is simply the output of previous( last_proof.get_output()) so to address your concern we could derive the key as hash(last_proof.get_output()), which was something I considered, but didn’t want to have seed and key be “related”. I do not have proof that my concern has any foundation under it. WDYT?

I don’t have a great alternative yet. Still thinking :slight_smile:

@dariolina For your proposal, we could look into the KDM (key-dependent message) security of AES as a block cipher.

The key seems to be just an artifact of AES. It is not clear that it has to be modified with each invocation, instead of using a fixed value.

Wouldn’t it be possible to design a hardware that has this one key hardcoded that operates more efficiently than general-purpose AES hardware if we make the key fixed?

Sounds reasonable, but really not my field of expertise. I was trying to say that deriving the key one invocation in advance does not seem to be an issue in practice.

We can pick the AES key once and for all in the beginning, but would we have enough entropy at the start to make sure that the key is sufficiently random for everyone? I guess picking a fresh key at every slot helps us leverage the unpredictable growth of the blockchain to bring in more randomness.

@Barak Yes, deriving the key one slot in advance does not seem to be an issue at the moment. I was just wondering if we could come up with an alternative design.

Why can’t we do something as simple as hashing output of the last PoT and using first 128 bits and key and last 128 bits as seed or something like that? It’d reduce number of external input parameters from two to one and we’ll not have to deal with potentially insecure key reuse (always sounds dangerous to me).

I haven’t thought about that before, but sounds alright.

@nazar-pc Are you suggesting that we hash only the output of last PoT or do something like hash(injected_block_hash||last_proof.get_output()), which is currently used to derive just the seed but now we can use it for both seed and key?

Yes, that is exactly what I’m suggesting

@shashank right now we use that hash(last_proof.get_output()) (sometimes hash(injected_block_hash||last_proof.get_output())) truncated to 16 bytes from 32 bytes for seed, Nazar is suggesting we keep the rest 16 bytes for the key

@nazar-pc @dariolina makes sense