Hi again

I opened this PR, which recommends that implementations output, or be able
to output, their messages in TLS format:
https://github.com/ietf-wg-keytrans/draft-protocol/pull/52 -- The "or be
able to output" clause here is somewhat load-bearing. While I don't think
that TLS is going to be the right wire format for most applications, I
think it's a small ask that implementations include serializers for TLS
format if it allows more thorough interop testing.

Also, I rewatched the meeting recording and I think I misunderstood your
comments on the CombinedTreeProof. You said at the time that the wire
format of the CombinedTreeProof is fine, but that the text in the draft is
lacking. There's a series of subsections of section 13.2 that explain what
exactly goes into the CombinedTreeProof for each algorithm. Does this text
address your concern / is it in the right direction but needs further
development?

On Fri, Jul 31, 2026 at 2:31 PM Brendan McMillion <
brendanmcmillion@gmail.com> wrote:

> Hi Felix
>
> We should make one wire format mandatory. Currently, the draft allows
>> implementers to freely choose the wire format. I would make TLS mandatory.
>> If people want to use a different wire format, they of course still can,
>> but fixing TLS allows us to at least hope that different implementations
>> interoperate.
>
>
> To give my own thoughts and to recap the discussion on the list a bit, the
> pros of not having a fixed wire format are:
>
> - Given the nature of this protocol, we can expect that most applications
> are going to want to customize their use / implementation of it to some
> degree. As an easy example, an application might be very prescriptive about
> what labels can be searched for / updated / monitored, to the point where
> allowing these fields to even be set in a request would be pointless. A
> flexible wire format makes these customizations easier to accomplish.
> - Inspecting the contents of requests is necessary for access control.
> Allowing flexibility, at least in the encoding of requests, also makes this
> easier to accomplish.
> - TLS cedes a lot of ground as far as extensibility, compressibility, and
> human intelligibility.
>
> The only con that I've seen discussed of not having a fixed wire format is
> that it makes interop testing harder. But the counterpoint here is that,
> since the wire format isn't fixed, we shouldn't be interop testing it. We
> should be interop testing un-encoded structures. So I wouldn't give you a
> byte string corresponding to an encoded SearchRequest, I'd give you
> SearchRequest{last: 1234, label: "brendan", ...} and see how your
> implementation processes it.
>
> I suggest simplifying the PrefixProof structure as follows: Represent
>> prefix trees as a list of leafs with their depth. Either store the node's
>> hash value (can be omitted for an empty leaf) or store the VRF output and
>> the commitment. The reconstruction algorithm can then simply do a DFS
>> search over the prefix tree and initialize it along the way. With the
>> current wire format, one must merge prefix trees first with the binary
>> ladder, then initiate leafs from the prefix search results, then fill in
>> node values.
>
>
> I don't understand how this is a simplification. You say that currently,
> you have to write code to compute each leaf's hash from the VRF output and
> commitment before you can evaluate the proof. And your claim is that you
> can simplify your implementation if each leaf's hash is directly in the
> proof. The issue with putting the leaf hashes directly into the proof,
> though, is that now you have to verify they're correct. So your proposal
> swaps code that does "compute each leaf's hash from the VRF output and
> commitment and insert it into the PrefixProof calculations" for "compute
> each leaf's hash from the VRF output and commitment and check that it
> matches what's in the PrefixProof." This doesn't seem any simpler to
> implement and requires more bytes on the wire. Am I missing something here?
>
> Such language makes the draft hard to implement because one now needs to
>> consider the entire document to understand how to parse the data structure.
>> I think this one will be quite hard to address. I cannot come up with the
>> right language right now, because I'm not sure what actually holds about,
>> e.g., the combined tree proof in all cases. But maybe that's a sign that
>> such text is needed.
>
>
> It's extremely simple to parse this data structure though, it's 4 arrays
> of simple data types. That's all that should be done at the parsing phase. Evaluating
> the proofs is also meant to be fairly easy: you implement the algorithms as
> they're specified, and when one of the algorithms needs a timestamp or a
> prefix proof, you pop the next one off of the `timestamps` or
> `prefix_proofs` field, respectively. So you essentially have two queues.
> This implementation strategy is discussed somewhat briefly in Appendix C.
>
> But note what this means: explicitly associating each timestamp or prefix
> proof with its log entry doesn't actually simplify implementation. Each
> algorithm already wants a specific set of timestamps in a specific order
> (which timestamps? evaluate the algorithm!). But now you need to parse this
> more complex wire format and do extra verification, such as: ensuring that
> the same position isn't listed multiple times, enforcing an order on the
> encoded map entries, and so on. Let me know if I'm missing something about
> this proposal, or if maybe adding more text to Appendix C would be helpful
>
> On Tue, Jul 28, 2026 at 4:31 AM Felix Linker <linkerfelix@gmail.com>
> wrote:
>
>> Hi everyone,
>>
>> As there was little time for discussion at the end of the meeting, I
>> wanted to raise my three suggestions for the protocol document on list and
>> here what other people say. Here they are:
>>
>>    - We should make one wire format mandatory. Currently, the draft
>>    allows implementers to freely choose the wire format. I would make TLS
>>    mandatory. If people want to use a different wire format, they of course
>>    still can, but fixing TLS allows us to at least hope that different
>>    implementations interoperate.
>>    - I suggest simplifying the PrefixProof structure as follows:
>>    Represent prefix trees as a list of leafs with their depth. Either store
>>    the node's hash value (can be omitted for an empty leaf) or store the VRF
>>    output and the commitment. The reconstruction algorithm can then simply do
>>    a DFS search over the prefix tree and initialize it along the way. With the
>>    current wire format, one must merge prefix trees first with the binary
>>    ladder, then initiate leafs from the prefix search results, then fill in
>>    node values.
>>       - I implemented this new wire format for testing purposes, and my
>>       code for constructing prefix trees indeed becomes much simpler:
>>       https://github.com/felixlinker/keytrans-verification/blob/ca4157ae8aaaae0b0e5b4b4e0e9d6d08524786a1/pkg/trees/prefix/prefix.go#L471
>>       - Previously, this was the code to first merge binary ladder
>>       results into the prefix tree:
>>       https://github.com/felixlinker/keytrans-verification/blob/3c4bb83d7dbcf47a4091d54653a5b6a2dcc84a8f/pkg/proofs/proofs.go#L102
>>       and this is the code to construct the prefix tree:
>>       https://github.com/felixlinker/keytrans-verification/blob/3c4bb83d7dbcf47a4091d54653a5b6a2dcc84a8f/pkg/trees/prefix/prefix.go#L536
>>    - I suggest describing the wire format more explicitly. For example,
>>    Section 12.3, specifying the combined tree proof, only says: "The
>>    timestamps field contains the timestamps of specific log entries [...].
>>    There is no explicit indication as to which log entry the elements
>>    correspond to, as they are provided in the order that the algorithm the
>>    user is executing would request them." Such language makes the draft hard
>>    to implement because one now needs to consider the entire document to
>>    understand how to parse the data structure. I think this one will be quite
>>    hard to address. I cannot come up with the right language right now,
>>    because I'm not sure what actually holds about, e.g., the combined tree
>>    proof in all cases. But maybe that's a sign that such text is needed.
>>
>>
>> Curious to hear what the rest thinks!
>>
>> Best,
>> Felix
>>
>> Am Do., 16. Juli 2026 um 10:14 Uhr schrieb Felix Linker <
>> linkerfelix@gmail.com>:
>>
>>> Hi Prachi and fellow keytrans enthusiasts,
>>>
>>> We made progress implementing a client. The client is still very much
>>> WIP, but I believe (with an asterisk) that it should be able to verify
>>> greatest version queries.
>>>
>>> The code for that can be found here:
>>> https://github.com/felixlinker/keytrans-verification/blob/felixlinker/client-state/pkg/client/client.go#L98
>>> Development currently happens on that branch.
>>>
>>> I could not test whether the client works yet because I'm not aware of a
>>> server implementation that generates search responses for search requests.
>>> Maybe my understanding here is wrong, I asked both Guy and Brendan for
>>> this. Would be great to have test vectors. My implementation of a prefix
>>> and log tree is tested, but only "against itself," i.e., I check that my
>>> implementation satisfies certain invariants.
>>>
>>> We also prove that our go implementation is memory safe. We haven't gone
>>> much further than that in our mechanized proofs because I would first like
>>> to test whether the client implementation actually works. It is much
>>> cheaper to test than to prove, so I want to do that first.
>>>
>>> The asterisk that I mentioned above is that I took the liberty to change
>>> the server response format slightly so that proofs are easier to parse. I
>>> could, at the meeting, present my experience implementing the client. My
>>> life would be much simpler if the change in wire format were part of the
>>> draft, and I find there are certain parts of the draft which are hard to
>>> implement and get right.
>>>
>>> Best,
>>> Felix
>>>
>>>
>>> Am Di., 14. Juli 2026 um 16:50 Uhr schrieb Prachi Jain <
>>> prachi.jain1288@gmail.com>:
>>>
>>>> Hello KEYTRANS enthusiasts,
>>>>
>>>> Please share any topics, discussion items, or anything else you'd like
>>>> to cover during our time at IETF 126. We have an hour allocated to us.
>>>>
>>>>
>>>> -Chairs
>>>> --
>>>> Keytrans mailing list -- keytrans@ietf.org
>>>> To unsubscribe send an email to keytrans-leave@ietf.org
>>>>
>>> --
>> Keytrans mailing list -- keytrans@ietf.org
>> To unsubscribe send an email to keytrans-leave@ietf.org
>>
>