idnits 2.17.1 draft-keytrans-mcmillion-protocol-02.txt: -(1448): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There is 1 instance of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There is 1 instance of too long lines in the document, the longest one being 5 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (18 November 2024) is 713 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'X' is mentioned on line 314, but not defined == Unused Reference: 'CONIKS' is defined on line 1455, but no explicit reference was found in the text == Unused Reference: 'OPTIKS' is defined on line 1464, but no explicit reference was found in the text == Unused Reference: 'SEEMLess' is defined on line 1468, but no explicit reference was found in the text == Outdated reference: A later version (-11) exists of draft-ietf-keytrans-architecture-02 ** Downref: Normative reference to an Informational draft: draft-ietf-keytrans-architecture (ref. 'I-D.ietf-keytrans-architecture') ** Downref: Normative reference to an Informational RFC: RFC 2104 ** Obsolete normative reference: RFC 6962 (Obsoleted by RFC 9162) ** Obsolete normative reference: RFC 8446 (Obsoleted by RFC 9846) ** Downref: Normative reference to an Informational RFC: RFC 9381 Summary: 6 errors (**), 0 flaws (~~), 7 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 KEYTRANS Working Group B. McMillion 3 Internet-Draft 4 Intended status: Standards Track F. Linker 5 Expires: 22 May 2025 18 November 2024 7 Key Transparency Protocol 8 draft-keytrans-mcmillion-protocol-02 10 Abstract 12 While there are several established protocols for end-to-end 13 encryption, relatively little attention has been given to securely 14 distributing the end-user public keys for such encryption. As a 15 result, these protocols are often still vulnerable to eavesdropping 16 by active attackers. Key Transparency is a protocol for distributing 17 sensitive cryptographic information, such as public keys, in a way 18 that reliably either prevents interference or detects that it 19 occurred in a timely manner. 21 About This Document 23 This note is to be removed before publishing as an RFC. 25 The latest revision of this draft can be found at 26 https://Bren2010.github.io/draft-keytrans/draft-keytrans-mcmillion- 27 protocol.html. Status information for this document may be found at 28 https://datatracker.ietf.org/doc/draft-keytrans-mcmillion-protocol/. 30 Source for this draft and an issue tracker can be found at 31 https://github.com/Bren2010/draft-keytrans. 33 Status of This Memo 35 This Internet-Draft is submitted in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at https://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on 22 May 2025. 50 Copyright Notice 52 Copyright (c) 2024 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 57 license-info) in effect on the date of publication of this document. 58 Please review these documents carefully, as they describe your rights 59 and restrictions with respect to this document. Code Components 60 extracted from this document must include Revised BSD License text as 61 described in Section 4.e of the Trust Legal Provisions and are 62 provided without warranty as described in the Revised BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 67 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 68 3. Tree Construction . . . . . . . . . . . . . . . . . . . . . . 4 69 3.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 70 3.2. Log Tree . . . . . . . . . . . . . . . . . . . . . . . . 5 71 3.3. Prefix Tree . . . . . . . . . . . . . . . . . . . . . . . 7 72 3.4. Combined Tree . . . . . . . . . . . . . . . . . . . . . . 9 73 4. Searching the Tree . . . . . . . . . . . . . . . . . . . . . 10 74 4.1. Implicit Binary Search Tree . . . . . . . . . . . . . . . 11 75 4.2. Binary Ladder . . . . . . . . . . . . . . . . . . . . . . 14 76 4.3. Most Recent Version . . . . . . . . . . . . . . . . . . . 15 77 4.4. Putting it Together . . . . . . . . . . . . . . . . . . . 16 78 5. Monitoring the Tree . . . . . . . . . . . . . . . . . . . . . 16 79 6. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 18 80 7. Cryptographic Computations . . . . . . . . . . . . . . . . . 18 81 7.1. Verifiable Random Function . . . . . . . . . . . . . . . 18 82 7.2. Commitment . . . . . . . . . . . . . . . . . . . . . . . 18 83 7.3. Prefix Tree . . . . . . . . . . . . . . . . . . . . . . . 19 84 7.4. Log Tree . . . . . . . . . . . . . . . . . . . . . . . . 20 85 7.5. Tree Head Signature . . . . . . . . . . . . . . . . . . . 21 86 8. Tree Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 22 87 8.1. Log Tree . . . . . . . . . . . . . . . . . . . . . . . . 22 88 8.2. Prefix Tree . . . . . . . . . . . . . . . . . . . . . . . 23 89 8.3. Combined Tree . . . . . . . . . . . . . . . . . . . . . . 24 90 8.3.1. Proofs for Contact Monitoring . . . . . . . . . . . . 24 91 8.3.2. Proofs for Third-Party Auditing . . . . . . . . . . . 26 92 9. Update Format . . . . . . . . . . . . . . . . . . . . . . . . 26 93 10. User Operations . . . . . . . . . . . . . . . . . . . . . . . 27 94 10.1. Search . . . . . . . . . . . . . . . . . . . . . . . . . 28 95 10.2. Update . . . . . . . . . . . . . . . . . . . . . . . . . 29 96 10.3. Monitor . . . . . . . . . . . . . . . . . . . . . . . . 29 97 11. Security Considerations . . . . . . . . . . . . . . . . . . . 32 98 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 32 99 12.1. KT Ciphersuites . . . . . . . . . . . . . . . . . . . . 33 100 12.2. KT Designated Expert Pool . . . . . . . . . . . . . . . 33 101 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 33 102 13.1. Normative References . . . . . . . . . . . . . . . . . . 33 103 13.2. Informative References . . . . . . . . . . . . . . . . . 34 104 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 34 105 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 34 107 1. Introduction 109 End-to-end encrypted communication services rely on the secure 110 exchange of public keys to ensure that messages remain confidential. 111 It is typically assumed that service providers correctly manage the 112 public keys associated with each user's account. However, this is 113 not always true. A service provider that is compromised or malicious 114 can change the public keys associated with a user's account without 115 their knowledge, thereby allowing the provider to eavesdrop on and 116 impersonate that user. 118 This document describes a protocol that enables a group of users to 119 ensure that they all have the same view of the public keys associated 120 with each other's accounts. Ensuring a consistent view allows users 121 to detect when unauthorized public keys have been associated with 122 their account, indicating a potential compromise. 124 More detailed information about the protocol participants and the 125 ways the protocol can be deployed can be found in 126 [I-D.ietf-keytrans-architecture]. 128 2. Conventions and Definitions 130 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 131 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 132 "OPTIONAL" in this document are to be interpreted as described in 133 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 134 capitals, as shown here. 136 This document uses the TLS presentation language [RFC8446] to 137 describe the structure of protocol messages, but does not require the 138 use of a specific transport protocol. As such, implementations do 139 not necessarily need to transmit messages according to the TLS format 140 and can chose whichever encoding method best suits their application. 141 However, cryptographic computations MUST be done with the TLS 142 presentation language format to ensure the protocol's security 143 properties are maintained. 145 3. Tree Construction 147 A Transparency Log is a verifiable data structure that maps _label- 148 version pairs_ to cryptographic keys or other structured data. 149 Labels correspond to user identifiers, and a new version of a label 150 is created each time the label's associated value changes. 151 Transparency Logs have an _epoch_ counter which is incremented every 152 time a new set of label-version pairs are added. 154 Epoch Update Set of logged Label-Version Pairs 155 * n X:0 -> k { ..., X:0 } 156 * n+1 Y:3 -> l { ..., X:0, Y:3 } 157 * n+2 Z:2 -> m { ..., X:0, Y:3, Z:2 } 158 * n+3 X:1 -> n { ..., X:0, Y:3, Z:2, X:1 } 160 Figure 1: An example log history. At epoch n the user with label 161 X submits their first key k. As it is their first key, it is 162 associated with version 0. At epoch n+1, user Y updates their 163 key to l. 165 KT uses a _prefix tree_ to commit to a mapping between each label- 166 version pair and a commitment to the label's value at that version. 167 Every time the prefix tree changes, its new root hash is stored in a 168 _log tree_. The benefit of the prefix tree is that it is easily 169 searchable, and the benefit of the log tree is that it can easily be 170 verified to be append-only. The data structure powering KT combines 171 a log tree and a prefix tree, and is called the _combined tree 172 structure_. 174 This section describes the operation of both prefix and log trees at 175 a high level and the way that they're combined. More precise 176 algorithms for computing the intermediate and root values of the 177 trees are given in Section 7. 179 3.1. Terminology 181 Trees consist of _nodes_ which have a byte string as their _hash 182 value_. A node is either a _leaf_ if it has no children, or a 183 _parent_ if it has either a _left child_ or a _right child_. A node 184 is the _root_ of a tree if it has no parents, and an _intermediate_ 185 if it has both children and parents. Nodes are _siblings_ if they 186 share the same parent. 188 The _descendants_ of a node are that node, its children, and the 189 descendants of its children. A _subtree_ of a tree is the tree given 190 by the descendants of a particular node, called the _head_ of the 191 subtree. 193 The _direct path_ of a root node is the empty list, and of any other 194 node is the concatenation of that node's parent along with the 195 parent's direct path. The _copath_ of a node is the node's sibling 196 concatenated with the list of siblings of all the nodes in its direct 197 path, excluding the root. 199 3.2. Log Tree 201 Log trees are used for storing information in the chronological order 202 that it was added and are constructed as _left-balanced_ binary 203 trees. 205 A binary tree is _balanced_ if its size is a power of two and for any 206 parent node in the tree, its left and right subtrees have the same 207 size. A binary tree is _left-balanced_ if for every parent, either 208 the parent is balanced, or the left subtree of that parent is the 209 largest balanced subtree that could be constructed from the leaves 210 present in the parent's own subtree. Given a list of n items, there 211 is a unique left-balanced binary tree structure with these elements 212 as leaves. Note also that every parent always has both a left and 213 right child. 215 X 216 | 217 .---------+. 218 / \ 219 X | 220 | | 221 .---+---. | 222 / \ | 223 X X | 224 / \ / \ | 225 / \ / \ | 226 X X X X X 228 Index: 0 1 2 3 4 230 Figure 2: A log tree containing five leaves. 232 Log trees initially consist of a single leaf node. New leaves are 233 added to the right-most edge of the tree along with a single parent 234 node, to construct the left-balanced binary tree with n+1 leaves. 236 X 237 | 238 .---------+---. 239 / \ 240 X | 241 | | 242 .---+---. | 243 / \ | 244 X X X 245 / \ / \ / \ 246 / \ / \ / \ 247 X X X X X X 249 Index: 0 1 2 3 4 5 251 Figure 3: Example of inserting a new leaf with index 5 into the 252 previously depicted log tree. Observe that only the nodes on the 253 path from the new root to the new leaf change. 255 While leaves contain arbitrary data, the value of a parent node is 256 always the hash of the combined values of its left and right 257 children. 259 Log trees are powerful in that they can provide both _inclusion 260 proofs_, which demonstrate that a leaf is included in a log, and 261 _consistency proofs_, which demonstrate that a new version of a log 262 is an extension of a past version of the log. 264 An inclusion proof is given by providing the copath values of a leaf. 265 The proof is verified by hashing together the leaf with the copath 266 values and checking that the result equals the root hash value of the 267 log. Consistency proofs are a more general version of the same idea. 268 With a consistency proof, the prover provides the minimum set of 269 intermediate node values from the current tree that allows the 270 verifier to compute both the old root value and the current root 271 value. An algorithm for this is given in section 2.1.2 of [RFC6962]. 273 X 274 | 275 .---------+---. 276 / \ 277 X | 278 | | 279 .---+---. | 280 / \ | 281 (X) X (X) 282 / \ / \ / \ 283 / \ / \ / \ 284 X X X (X) X X 286 Index: 0 1 2 3 4 5 288 Figure 4: Illustration of a proof of inclusion. To verify that 289 leaf 2 is included in the tree, the server provides the client 290 with the hashes of the nodes on its copath, i.e., all hashes that 291 are required for the client to compute the root hash itself. In 292 the figure, the copath consists of the nodes marked by (X). 294 X 295 | 296 .---------+----. 297 / \ 298 (X) | 299 | | 300 .---+---. | 301 / \ | 302 X X X 303 / \ / \ / \ 304 / \ / \ / \ 305 X X X X (X) [X] 307 Index: 0 1 2 3 4 5 309 Figure 5: Illustration of a consistency proof. The server proves 310 to the client that it correctly extended the tree by giving it 311 the hashes of marked nodes ([X] / (X)). The client can verify 312 that it can construct the old root hash from the hashes of nodes 313 marked by (X), and that it can construct the new root hash when 314 also considering the hash of the node [X]. 316 3.3. Prefix Tree 318 Prefix trees are used for storing key-value pairs, in a way that 319 provides the ability to efficiently prove that a search key's value 320 was looked up correctly. 322 Each leaf node in a prefix tree represents a specific key-value pair, 323 while each parent node represents some prefix which all search keys 324 in the subtree headed by that node have in common. The subtree 325 headed by a parent's left child contains all search keys that share 326 its prefix followed by an additional 0 bit, while the subtree headed 327 by a parent's right child contains all search keys that share its 328 prefix followed by an additional 1 bit. 330 The root node, in particular, represents the empty string as a 331 prefix. The root's left child contains all search keys that begin 332 with a 0 bit, while the right child contains all search keys that 333 begin with a 1 bit. 335 A prefix tree can be searched by starting at the root node, and 336 moving to the left child if the first bit of a search key is 0, or 337 the right child if the first bit is 1. This is then repeated for the 338 second bit, third bit, and so on until the search either terminates 339 at a leaf node (which may or may not be for the desired value), or a 340 parent node that lacks the desired child. 342 X 343 | 344 .-------+-----. 345 / \ 346 0 1 347 | | 348 | .--+-. 349 | / \ 350 0 0 | 351 / \ / \ | 352 / \ / \ | 353 Key: 00010 00101 10001 10111 11011 354 Value: A B C D E 356 Figure 6: A prefix tree containing five entries. 358 New key-value pairs are added to the tree by searching it according 359 to the same process. If the search terminates at a parent without a 360 left or right child, a new leaf is simply added as the parent's 361 missing child. If the search terminates at a leaf for the wrong 362 search key, one or more intermediate nodes are added until the new 363 leaf and the existing leaf would no longer reside in the same place. 364 That is, until we reach the first bit that differs between the new 365 search key and the existing search key. 367 X 368 | 369 .------+------. 370 / \ 371 0 1 372 | | 373 .--+-. .--+-. 374 / \ / \ 375 0 | 0 | 376 / \ | / \ | 377 / \ | / \ | 378 Index: 00010 00101 01101 10001 10111 11011 379 Value: A B F C D E 381 Figure 7: The previous prefix tree after adding the key-value 382 pair: 01101 -> F. 384 The value of a leaf node is the encoded key-value pair, while the 385 value of a parent node is the hash of the combined values of its left 386 and right children (or a stand-in value when one of the children 387 doesn't exist). 389 A proof of membership is given by providing the leaf hash value, 390 along with the hash value of each copath entry along the search path. 391 A proof of non-membership is given by providing an abridged proof of 392 membership that follows the path for the intended search key, but 393 ends either at a stand-in node or a leaf for a different search key. 394 In either case, the proof is verified by hashing together the leaf 395 with the copath hash values and checking that the result equals the 396 root hash value of the tree. 398 3.4. Combined Tree 400 Log trees are desirable because they can provide efficient 401 consistency proofs to assure verifiers that nothing has been removed 402 from a log that was present in a previous version. However, log 403 trees can't be efficiently searched without downloading the entire 404 log. Prefix trees are efficient to search and can provide inclusion 405 proofs to convince verifiers that the returned search results are 406 correct. However, it's not possible to efficiently prove that a new 407 version of a prefix tree contains the same data as a previous version 408 with only new values added. 410 In the combined tree structure, which is based on [Merkle2], a prefix 411 tree contains a mapping where each label-version pair is a search 412 key, and its associated value is a cryptographic commitment to the 413 label's new contents. A log tree contains a record of each version 414 of the prefix tree that's created. With some caveats, this combined 415 structure supports both efficient consistency proofs and can be 416 efficiently searched. 418 Note that, although the Transparency Log maintains a single logical 419 prefix tree, each modification of this tree results in a new root 420 hash, which is then stored in the log tree. Therefore, when 421 instructions refer to "looking up a label-version pair in the prefix 422 tree at a given log entry," this actually means searching in the 423 specific version of the prefix tree that corresponds to the root hash 424 stored at that log entry (where a "log entry" refers to a leaf of the 425 log tree). 427 Epoch n-1 n n+1 429 Root hash o -------- o ---------------------- o 430 / \ | | 431 /___\ .--+--. .------+------. 432 / \ | / \ | 433 /___\ | /___\ .-------+-------. 434 | / \ 435 [X:0->k; h(PT_n)] [X:0->k; h(PT_n)] [Y:3->l; h(PT_n+1)] 437 Figure 8: An example evolution of the combined tree structure, 438 following the example from the beginning of the section. At 439 every epoch, a new leaf is added to a log tree, containing a 440 change to a label's value and the updated prefix tree (PT). 442 4. Searching the Tree 444 When searching the combined tree structure described in Section 3.4, 445 the proof provided by the Transparency Log may either be *full* or 446 *abridged*. A full proof must be provided if the deployment mode of 447 the Transparency Log is Contact Monitoring, or if the user has 448 specifically requested it. Otherwise, proofs are provided abridged. 450 A full proof follows the path of a binary search for the first log 451 entry where the prefix tree contains the desired label-version pair. 452 This ensures that all users will check the same or similar entries 453 when searching for the same label, allowing for efficient client-side 454 auditing of the Transparency Log. The binary search uses an _implicit 455 binary search tree_ constructed over the leaves of the log tree 456 (distinct from the structure of the log tree itself), which allows 457 the search to have a complexity logarithmic in the number of the 458 log's leaves. 460 An abridged proof skips this binary search, and simply looks at the 461 most recent version of the prefix tree to determine the commitment to 462 the update that the user is looking for. Abridged proofs rely on a 463 third-party auditor or manager that can be trusted not to collude 464 with the Transparency Log, and who checks that every version of the 465 prefix tree is constructed correctly. This is described in more 466 detail in Section 4.4. 468 4.1. Implicit Binary Search Tree 470 Intuitively, the leaves of the log tree can be considered a flat 471 array representation of a binary tree. This structure is similar to 472 the log tree, but distinguished by the fact that not all parent nodes 473 have two children. In this representation, "leaf" nodes are stored 474 in even-numbered indices, while "intermediate" nodes are stored in 475 odd-numbered indices: 477 X 478 | 479 .---------+---------. 480 / \ 481 X X 482 | | 483 .---+---. .---+---. 484 / \ / \ 485 X X X X 486 / \ / \ / \ / 487 / \ / \ / \ / 488 X X X X X X X 490 Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 492 Figure 9: A binary tree constructed from 14 entries in a log 494 Following the structure of this binary tree when executing searches 495 makes auditing the Transparency Log much more efficient because users 496 can easily reason about which nodes will be accessed when conducting 497 a search. As such, only nodes along a specific search path need to 498 be checked for correctness. 500 The following Python code demonstrates the computations used for 501 following this tree structure: 503 # The exponent of the largest power of 2 less than x. Equivalent to: 504 # int(math.floor(math.log(x, 2))) 505 def log2(x): 506 if x == 0: 507 return 0 508 k = 0 509 while (x >> k) > 0: 510 k += 1 511 return k-1 513 # The level of a node in the tree. Leaves are level 0, their parents 514 # are level 1, etc. If a node's children are at different levels, 515 # then its level is the max level of its children plus one. 516 def level(x): 517 if x & 0x01 == 0: 518 return 0 519 k = 0 520 while ((x >> k) & 0x01) == 1: 521 k += 1 522 return k 524 # The root index of a search if the log has `n` entries. 525 def root(n): 526 return (1 << log2(n)) - 1 528 # The left child of an intermediate node. 529 def left(x): 530 k = level(x) 531 if k == 0: 532 raise Exception('leaf node has no children') 533 return x ^ (0x01 << (k - 1)) 535 # The right child of an intermediate node. 536 def right(x, n): 537 k = level(x) 538 if k == 0: 539 raise Exception('leaf node has no children') 540 x = x ^ (0x03 << (k - 1)) 541 while x >= n: 542 x = left(x) 543 return x 545 The root function returns the index in the log at which a search 546 should start. The left and right functions determine the subsequent 547 index to be accessed, depending on whether the search moves left or 548 right. 550 For example, in a search where the log has 50 entries, instead of 551 starting the search at the typical "middle" entry of 50/2 = 25, users 552 would start at entry root(50) = 31. If the next step in the search 553 is to move right, the next index to access would be right(31, 50) = 554 47. As more entries are added to the log, users will consistently 555 revisit entries 31 and 47, while they may never revisit entry 25 556 after even a single new entry is added to the log. 558 4.2. Binary Ladder 560 When executing searches on a Transparency Log, the implicit tree 561 described in Section 4.1 is navigated according to a binary search. 562 At each individual log entry, the binary search needs to determine 563 whether it should move left or right. That is, it needs to 564 determine, out of the set of label-version pairs stored in the prefix 565 tree, whether the highest version of a label that's present at a 566 given log entry is greater than, equal to, or less than a target 567 version. 569 A *binary ladder* is a series of lookups in a single log entry's 570 prefix tree, which is used to establish whether the target version of 571 a label is present or not. It consists of the following lookups, 572 stopping after the first lookup that produces a proof of non- 573 inclusion: 575 1. First, version x of the label is looked up, where x is 576 consecutively higher powers of two minus one (0, 1, 3, 7, ...). 577 This is repeated until x is the largest such value less than or 578 equal to the target version. 580 2. Second, the largest x that was looked up is retained, and 581 consecutively smaller powers of two are added to it until it 582 equals the target version. Each time a power of two is added, 583 this version of the label is looked up. 585 As an example, if the target version of a label to lookup is 20, a 586 binary ladder would consist of the following versions: 0, 1, 3, 7, 587 15, 19, 20. If all of the lookups succeed (i.e., result in proofs of 588 inclusion), this indicates that the target version of the label 589 exists in the log. If the ladder stops early because a proof of non- 590 inclusion was produced, this indicates that the target version of the 591 label did not exist, as of the given log entry. 593 When executing a search in a Transparency Log for a specific version 594 of a label, a binary ladder is provided for each node on the search 595 path, verifiably guiding the search toward the log entry where the 596 desired label-version pair was first inserted (and therefore, the log 597 entry with the desired update). 599 Requiring proof that this series of versions are present in the 600 prefix tree, instead of requesting proof of just version 20, ensures 601 that all users are able to agree on which version of the label is 602 _most recent_, which is discussed further in the next section. 604 4.3. Most Recent Version 606 Often, users wish to search for the "most recent" version of a label. 607 That is, the label with the highest version possible. 609 To determine this, users request a *full binary ladder* for each node 610 on the *frontier* of the log. The frontier consists of the root node 611 of a search, followed by the entries produced by repeatedly calling 612 right until reaching the last entry of the log. Using the same 613 example of a search where the log has 50 entries, the frontier would 614 be entries: 31, 47, 49. 616 A full binary ladder is similar to the binary ladder discussed in the 617 previous section, except that it identifies the exact highest version 618 of a label that exists, as of a particular log entry, rather than 619 stopping at a target version. It consists of the following lookups: 621 1. First, version x of the label is looked up, where x is a 622 consecutively higher power of two minus one (0, 1, 3, 7, ...). 623 This is repeated until the first proof of non-inclusion is 624 produced. 626 2. Once the first proof of non-inclusion is produced, a binary 627 search is conducted between the highest version that was proved 628 to be included, and the version that was proved to not be 629 included. Each step of the binary search produces either a proof 630 of inclusion or non-inclusion, which guides the search left or 631 right, until it terminates. 633 For the purpose of finding the highest version possible, requesting a 634 full binary ladder for each entry along the frontier is functionally 635 the same as doing so for only the last log entry. However, 636 inspecting the entire frontier allows the user to verify that the 637 search path leading to the last log entry represents a monotonic 638 series of version increases, which minimizes opportunities for log 639 misbehavior. 641 Once the user has verified that the frontier lookups are monotonic 642 and determined the highest version, the user then continues a binary 643 search for this specific version. 645 4.4. Putting it Together 647 As noted at the beginning of the section, a search in the tree will 648 either require producing a full proof, or an abridged proof may be 649 accepted if the user can trust a third-party to audit and not collude 650 with the Transparency Log. 652 The steps for producing a full or abridged search proof are 653 summarized as follows: 655 * Full proof: 657 - If searching for the most recent version of a label, a full 658 binary ladder is obtained for each node on the frontier of the 659 log. This determines the highest version of the label 660 available, which allows the search to proceed for this specific 661 version. 663 - If searching for a specific version, the proof follows a binary 664 search for the first entry in the log where this version of the 665 label exists. For each step in the binary search, the proof 666 contains a (non-full) binary ladder for the targeted version, 667 which proves whether the targeted version of the label existed 668 yet or not by this point in the log. This indicates whether 669 the binary search should move forwards or backwards in the log. 671 * Abridged proof: 673 - If searching for the most recent version of a label, a full 674 binary ladder is obtained only from the last (most recent) 675 entry of the log. The prefix tree entry for the most recent 676 version of the label will contain the commitment to the update, 677 ending the search. 679 - If searching for a specific version, a (non-full) binary ladder 680 for this version is obtained only from the last entry of the 681 log. Similar to the previous case, the prefix tree entry for 682 the targeted version will contain the commitment to the update. 684 5. Monitoring the Tree 686 As new entries are added to the log tree, the search path that's 687 traversed to find a specific version of a label may change. New 688 intermediate nodes may become established in between the search root 689 and the leaf, or a new search root may be created. The goal of 690 monitoring a label is to efficiently ensure that, when these new 691 parent nodes are created, they're created correctly so that searches 692 for the same versions continue converging to the same entries in the 693 log. 695 To monitor a given label, users maintain a small amount of state: a 696 map from a position in the log to a version counter. The version 697 counter is the highest version of the label that's been proven to 698 exist at that log position. Users initially populate this map by 699 setting the position of an entry they've looked up, to map to the 700 version of the label stored in that entry. A map may track several 701 different versions of a label simultaneously, if a user has been 702 shown different versions of the same label. 704 To update this map, users receive the most recent tree head from the 705 server and follow these steps, for each entry in the map: 707 1. Compute the entry's direct path (in terms of the Implicit Binary 708 Search Tree) based on the current tree size. 710 2. If there are no entries in the direct path that are to the right 711 of the current entry, then skip updating this entry (there's no 712 new information to update it with). 714 3. For each entry in the direct path that's to the right of the 715 current entry, from low to high: 717 1. Receive and verify a binary ladder from that log entry, for 718 the version currently in the map. This proves that, at the 719 indicated log entry, the highest version present is greater 720 than or equal to the previously-observed version. 722 2. If the above check was successful, remove the current 723 position-version pair from the map and replace it with a 724 position-version pair corresponding to the entry in the log 725 that was just checked. 727 This algorithm progressively moves up the tree as new intermediate/ 728 root nodes are established and verifies that they're constructed 729 correctly. Note that users can often execute this process with the 730 output of Search or Update operations for a label, without waiting to 731 make explicit Monitor queries. 733 It is also worth noting that the work required to monitor several 734 versions of the same label scales sublinearly, due to the fact that 735 the direct paths of the different versions will often intersect. 736 Intersections reduce the total number of entries in the map and 737 therefore the amount of work that will be needed to monitor the label 738 from then on. 740 Finally, unlike searching, there is no abridged version of 741 monitoring. 743 6. Ciphersuites 745 Each Transparency Log uses a single fixed ciphersuite, chosen when 746 the log is initially created, that specifies the following primitives 747 to be used for cryptographic computations: 749 * A hash algorithm 751 * A signature algorithm 753 * A Verifiable Random Function (VRF) algorithm 755 The hash algorithm is used for computing the intermediate and root 756 values of hash trees. The signature algorithm is used for signatures 757 from both the service operator and the third party, if one is 758 present. The VRF is used for preserving the privacy of labels. One 759 of the VRF algorithms from [RFC9381] must be used. 761 Ciphersuites are represented with the CipherSuite type. The 762 ciphersuites are defined in Section 12.1. 764 7. Cryptographic Computations 766 7.1. Verifiable Random Function 768 Each label-version pair created in a log will have a unique 769 representation in the prefix tree. This is computed by providing the 770 combined label and version as inputs to the VRF: 772 struct { 773 opaque label<0..2^8-1>; 774 uint32 version; 775 } VrfInput; 777 The VRF's output evaluated on VrfInput is the concrete value inserted 778 into the prefix tree. 780 7.2. Commitment 782 As discussed in Section 3.4, commitments are stored in the leaves of 783 the log tree and correspond to updates. Commitments are computed 784 with HMAC [RFC2104], using the hash function specified by the 785 ciphersuite. To produce a new commitment, the application generates 786 a random 16 byte value called opening and computes: 788 commitment = HMAC(fixedKey, CommitmentValue) 790 where fixedKey is the 16 byte hex-decoded value: 792 d821f8790d97709796b4d7903357c3f5 794 and CommitmentValue is specified as: 796 struct { 797 opaque opening<16>; 798 opaque label<0..2^8-1>; 799 UpdateValue update; 800 } CommitmentValue; 802 This fixed key allows the HMAC function, and thereby the commitment 803 scheme, to be modeled as a random oracle. The label field of 804 CommitmentValue contains the label being updated and the update field 805 contains the new value for the label. 807 The output value commitment may be published, while opening should be 808 kept private until the commitment is meant to be revealed. 810 7.3. Prefix Tree 812 The leaf nodes of a prefix tree are serialized as: 814 struct { 815 opaque vrf_output; 816 uint64 update_index; 817 } PrefixLeaf; 819 where vrf_output is the VRF output for the label-version pair, VRF.Nh 820 is the output size of the ciphersuite VRF in bytes, and update_index 821 is the index of the log tree's leaf committing to the respective 822 value, i.e., the log tree's tree_size just after the respective 823 label-version pair was inserted minus one. 825 The parent nodes of a prefix tree are serialized as: 827 struct { 828 opaque value; 829 } PrefixParent; 831 where Hash.Nh is the output length of the ciphersuite hash function. 832 The value of a parent node is computed by hashing together the values 833 of its left and right children: 835 parent.value = Hash(0x01 || 836 nodeValue(parent.leftChild) || 837 nodeValue(parent.rightChild)) 839 nodeValue(node): 840 if node.type == emptyNode: 841 return 0 // all-zero vector of length Hash.Nh 842 else if node.type == leafNode: 843 return Hash(0x00 || node.vrf_output || node.update_index) 844 else if node.type == parentNode: 845 return node.value 847 where Hash denotes the ciphersuite hash function. 849 7.4. Log Tree 851 The leaf and parent nodes of a log tree are serialized as: 853 struct { 854 opaque commitment; 855 opaque prefix_tree; 856 } LogLeaf; 858 struct { 859 opaque value; 860 } LogParent; 862 The commitment field contains the output of evaluating HMAC on 863 CommitmentValue, as described in Section 7.2. The prefix_tree field 864 contains the root hash of the prefix tree, after inserting a new 865 label-version pair for the label in CommitmentValue. 867 The value of a parent node is computed by hashing together the values 868 of its left and right children: 870 parent.value = Hash(hashContent(parent.leftChild) || 871 hashContent(parent.rightChild)) 873 hashContent(node): 874 if node.type == leafNode: 875 return 0x00 || nodeValue(node) 876 else if node.type == parentNode: 877 return 0x01 || nodeValue(node) 879 nodeValue(node): 880 if node.type == leafNode: 881 return Hash(node.commitment || node.prefix_tree) 882 else if node.type == parentNode: 883 return node.value 885 7.5. Tree Head Signature 887 The head of a Transparency Log, which represents the log's most 888 recent state, is represented as: 890 struct { 891 uint64 tree_size; 892 opaque signature<0..2^16-1>; 893 } TreeHead; 895 where tree_size counts the number of entries in the log tree. If the 896 Transparency Log is deployed with Third-party Management then the 897 public key used to verify the signature belongs to the third-party 898 manager; otherwise the public key used belongs to the service 899 operator. 901 The signature itself is computed over a TreeHeadTBS structure, which 902 incorporates the log's current state as well as long-term log 903 configuration: 905 enum { 906 reserved(0), 907 contactMonitoring(1), 908 thirdPartyManagement(2), 909 thirdPartyAuditing(3), 910 (255) 911 } DeploymentMode; 913 struct { 914 CipherSuite ciphersuite; 915 DeploymentMode mode; 916 opaque signature_public_key<0..2^16-1>; 917 opaque vrf_public_key<0..2^16-1>; 919 select (Configuration.mode) { 920 case contactMonitoring: 921 case thirdPartyManagement: 922 opaque leaf_public_key<0..2^16-1>; 923 case thirdPartyAuditing: 924 opaque auditor_public_key<0..2^16-1>; 925 }; 926 } Configuration; 928 struct { 929 Configuration config; 930 uint64 tree_size; 931 opaque root; 932 } TreeHeadTBS; 934 8. Tree Proofs 936 8.1. Log Tree 938 An inclusion proof for a single leaf in a log tree is given by 939 providing the copath values of a leaf. Similarly, a bulk inclusion 940 proof for any number of leaves is given by providing the fewest node 941 values that can be hashed together with the specified leaves to 942 produce the root value. Such a proof is encoded as: 944 opaque NodeValue; 946 struct { 947 NodeValue elements<0..2^16-1>; 948 } InclusionProof; 950 Each NodeValue is a uniform size, computed by passing the relevant 951 LogLeaf or LogParent structures through the nodeValue function in 952 Section 7.4. The contents of the elements array is kept in left-to- 953 right order: if a node is present in the root's left subtree, its 954 value must be listed before any values provided from nodes that are 955 in the root's right subtree, and so on recursively. 957 Consistency proofs are encoded similarly: 959 struct { 960 NodeValue elements<0..2^8-1>; 961 } ConsistencyProof; 963 Again, each NodeValue is computed by passing the relevant LogLeaf or 964 LogParent structure through the nodeValue function. The nodes chosen 965 correspond to those output by the algorithm in Section 2.1.2 of 966 [RFC6962]. 968 8.2. Prefix Tree 970 A proof from a prefix tree authenticates that a set of values are 971 either members of, or are not members of, the total set of values 972 represented by the prefix tree. Such a proof is encoded as: 974 enum { 975 reserved(0), 976 inclusion(1), 977 nonInclusionLeaf(2), 978 nonInclusionParent(3), 979 } PrefixSearchResultType; 981 struct { 982 PrefixSearchResultType result_type; 983 select (PrefixSearchResult.result_type) { 984 case inclusion: 985 uint64 update_index; 986 case nonInclusionLeaf: 987 PrefixLeaf leaf; 988 }; 989 uint8 depth; 990 } PrefixSearchResult; 992 struct { 993 PrefixSearchResult results<0..2^8-1>; 994 NodeValue elements<0..2^16-1>; 995 } PrefixProof; 997 The results field contains the search result for each individual 998 value. It is sorted lexicographically by corresponding value. The 999 result_type field of each PrefixSearchResult struct indicates what 1000 the terminal node of the search for that value was: 1002 * inclusion for a leaf node matching the requested value. 1004 * nonInclusionLeaf for a leaf node not matching the requested value. 1005 In this case, the terminal node's value is provided given that it 1006 can not be inferred. 1008 * nonInclusionParent for a parent node that lacks the desired child. 1010 The depth field indicates the depth of the terminal node of the 1011 search, and is provided to assist proof verification. 1013 The elements array consists of the fewest node values that can be 1014 hashed together with the provided leaves to produce the root. The 1015 contents of the elements array is kept in left-to-right order: if a 1016 node is present in the root's left subtree, its value must be listed 1017 before any values provided from nodes that are in the root's right 1018 subtree, and so on recursively. In the event that a node is not 1019 present, an all-zero byte string of length Hash.Nh is listed instead. 1021 The proof is verified by hashing together the provided elements, in 1022 the left/right arrangement dictated by the tree structure, and 1023 checking that the result equals the root value of the prefix tree. 1025 8.3. Combined Tree 1027 8.3.1. Proofs for Contact Monitoring 1029 A proof from a combined log and prefix tree follows the execution of 1030 a binary search through the leaves of the log tree, as described in 1031 Section 3.4. It is serialized as follows: 1033 struct { 1034 opaque proof; 1035 } VRFProof; 1037 struct { 1038 PrefixProof prefix_proof; 1039 opaque commitment; 1040 } ProofStep; 1042 struct { 1043 optional version; 1044 VRFProof vrf_proofs<0..2^8-1>; 1045 ProofStep steps<0..2^8-1>; 1046 InclusionProof inclusion; 1047 } SearchProof; 1048 If searching for the most recent version of a label, the most recent 1049 version is provided in version. If searching for a specific version, 1050 this field is omitted. 1052 Each element of vrf_proofs contains the output of evaluating the VRF 1053 on a different version of the label. The versions chosen correspond 1054 either to the binary ladder described in Section 4.2 (when searching 1055 for a specific version of a label), or to the full binary ladder 1056 described in Section 4.3 (when searching for the most recent version 1057 of a label). The proofs are sorted from lowest version to highest 1058 version. 1060 Each ProofStep structure in steps is one log entry that was inspected 1061 as part of the binary search. The first step corresponds to the 1062 "middle" leaf of the log tree (calculated with the root function in 1063 Section 4.1). From there, each subsequent step moves left or right 1064 in the tree, according to the procedure discussed in Section 4.2 and 1065 Section 4.3. 1067 The prefix_proof field of a ProofStep is the output of executing a 1068 binary ladder, excluding any ladder steps for which a proof of 1069 inclusion is expected, and a proof of inclusion was already provided 1070 in a previous ProofStep for a log entry to the left of the current 1071 one. 1073 The commitment field of a ProofStep contains the commitment to the 1074 update at that leaf. The inclusion field of SearchProof contains a 1075 batch inclusion proof for all of the leaves accessed by the binary 1076 search. 1078 The proof can be verified by checking that: 1080 1. The elements of steps represent a monotonic series over the 1081 leaves of the log, and 1083 2. The steps array has the expected number of entries (no more or 1084 less than are necessary to execute the binary search). 1086 Once the validity of the search steps has been established, the 1087 verifier can compute the root of each prefix tree represented by a 1088 prefix_proof and combine it with the corresponding commitment to 1089 obtain the value of each leaf. These leaf values can then be 1090 combined with the proof in inclusion to check that the output matches 1091 the root of the log tree. 1093 8.3.2. Proofs for Third-Party Auditing 1095 In third-party auditing, clients can rely on the assumption that the 1096 prefix tree is monitored to be append-only. Therefore, they need not 1097 execute the binary ladder but the proof can directly jump to the 1098 index identified by the prefix tree leaf. 1100 struct { 1101 optional version; 1102 VRFProof vrf_proofs<0..2^8-1>; 1103 PrefixProof prefix_proof; 1104 InclusionProof inclusion; 1105 } SearchProofCompact; 1107 The semantics of the version field do not change. 1109 Similarly to SearchProof, vrf_proofs contains the output of 1110 evaluating the VRF on a different version of the label. Either one 1111 version will be included (when requesting a specific version) or the 1112 versions to verify the full binary ladder (when requesting the latest 1113 version). 1115 prefix_proof contains the proof to either verify the inclusion of the 1116 label-version pair (when requesting a specific version) or to verify 1117 the full binary ladder (when requesting the latest version). Both 1118 types of proofs are for the most recent prefix tree. 1120 inclusion contains a batch inclusion of the most recent leaf and the 1121 leaf that commits to respective value for the request label-version 1122 pair. The most recent leaf is needed to obtain the prefix tree's 1123 root hash, and the leaf committing to the requested value will be at 1124 the index identified in the most recent prefix tree. 1126 9. Update Format 1128 The updates committed to by a combined tree structure contain the new 1129 value of a label, along with additional information depending on the 1130 deployment mode of the Transparency Log. They are serialized as 1131 follows: 1133 struct { 1134 select (Configuration.mode) { 1135 case thirdPartyManagement: 1136 opaque signature<0..2^16-1>; 1137 }; 1138 } UpdatePrefix; 1140 struct { 1141 UpdatePrefix prefix; 1142 opaque value<0..2^32-1>; 1143 } UpdateValue; 1145 The value field contains the new value associated with the label. 1147 In the event that third-party management is used, the prefix field 1148 contains a signature from the service operator, using the public key 1149 from Configuration.leaf_public_key, over the following structure: 1151 struct { 1152 opaque label<0..2^8-1>; 1153 uint32 version; 1154 opaque value<0..2^32-1>; 1155 } UpdateTBS; 1157 The label field contains the label being updated, version contains 1158 the new version, and value contains the same contents as 1159 UpdateValue.value. Clients MUST successfully verify this signature 1160 before consuming UpdateValue.value. 1162 10. User Operations 1164 The basic user operations are organized as a request-response 1165 protocol between a user and the Transparency Log operator. 1167 Users MUST retain the most recent TreeHead they've successfully 1168 verified as part of any query response, and populate the last field 1169 of any query request with the tree_size from this TreeHead. This 1170 ensures that all operations performed by the user return consistent 1171 results. 1173 struct { 1174 TreeHead tree_head; 1175 optional consistency; 1176 select (Configuration.mode) { 1177 case thirdPartyAuditing: 1178 AuditorTreeHead auditor_tree_head; 1179 }; 1180 } FullTreeHead; 1181 If last is present, then the Transparency Log MUST provide a 1182 consistency proof between the current tree and the tree when it was 1183 this size, in the consistency field of FullTreeHead. 1185 10.1. Search 1187 Users initiate a Search operation by submitting a SearchRequest to 1188 the Transparency Log containing the label that they're interested in. 1189 Users can optionally specify a version of the label that they'd like 1190 to receive, if not the most recent one. 1192 struct { 1193 optional last; 1195 opaque label<0..2^8-1>; 1196 optional version; 1197 } SearchRequest; 1199 In turn, the Transparency Log responds with a SearchResponse 1200 structure: 1202 struct { 1203 FullTreeHead full_tree_head; 1205 SearchProof search; 1206 opaque opening<16>; 1207 UpdateValue value; 1208 } SearchResponse; 1210 Users verify a search response by following these steps: 1212 1. Evaluate the search proof in search according to the steps in 1213 Section 8.3. This will produce a verdict as to whether the 1214 search was executed correctly and also a candidate root value for 1215 the tree. If it's determined that the search was executed 1216 incorrectly, abort with an error. 1218 2. With the candidate root value for the tree, verify the given 1219 FullTreeHead. 1221 3. Verify that the commitment in the terminal search step opens to 1222 SearchResponse.value with opening SearchResponse.opening. 1224 Depending on the deployment mode of the Transparency Log, the value 1225 field may or may not require additional verification, specified in 1226 Section 9, before its contents may be consumed. 1228 10.2. Update 1230 Users initiate an Update operation by submitting an UpdateRequest to 1231 the Transparency Log containing the new label and value to store. 1233 struct { 1234 optional last; 1236 opaque label<0..2^8-1>; 1237 opaque value<0..2^32-1>; 1238 } UpdateRequest; 1240 If the request passes application-layer policy checks, the 1241 Transparency Log adds a new label-version pair to the prefix tree, 1242 followed by adding a new entry to the log tree with the associated 1243 value and updated prefix tree root. It returns an UpdateResponse 1244 structure: 1246 struct { 1247 FullTreeHead full_tree_head; 1249 SearchProof search; 1250 opaque opening<16>; 1251 UpdatePrefix prefix; 1252 } UpdateResponse; 1254 Users verify the UpdateResponse as if it were a SearchResponse for 1255 the most recent version of label. To aid verification, the update 1256 response provides the UpdatePrefix structure necessary to reconstruct 1257 the UpdateValue. 1259 10.3. Monitor 1261 Users initiate a Monitor operation by submitting a MonitorRequest to 1262 the Transparency Log containing information about the labels they 1263 wish to monitor. 1265 struct { 1266 opaque label<0..2^8-1>; 1267 uint32 highest_version; 1268 uint64 entries<0..2^8-1>; 1269 } MonitorLabel; 1271 struct { 1272 optional last; 1274 MonitorLabel owned_labels<0..2^8-1>; 1275 MonitorLabel contact_labels<0..2^8-1>; 1276 } MonitorRequest; 1278 Users include each of the labels that they own in owned_labels. If 1279 the Transparency Log is deployed with Contact Monitoring (or simply 1280 if the user wants a higher degree of confidence in the log), they 1281 also include any labels they've looked up in contact_labels. 1283 Each MonitorLabel structure contains the label being monitored in 1284 label, the highest version of the label that the user has observed in 1285 highest_version, and a list of entries in the log tree corresponding 1286 to the keys of the map described in Section 5. 1288 The Transparency Log verifies the MonitorRequest by following these 1289 steps, for each MonitorLabel structure: 1291 1. Verify that the requested labels in owned_labels and 1292 contact_labels are all distinct. 1294 2. Verify that the user owns every label in owned_labels, and is 1295 allowed (or was previously allowed) to lookup every label in 1296 contact_labels, based on the application's policy. 1298 3. Verify that the highest_version for each label is less than or 1299 equal to the most recent version of each label. 1301 4. Verify that each entries array is sorted in ascending order, and 1302 that all entries are within the bounds of the log. 1304 5. Verify each entry lies on the direct path of different versions 1305 of the label. 1307 If the request is valid, the Transparency Log responds with a 1308 MonitorResponse structure: 1310 struct { 1311 uint32 version; 1312 VRFProof vrf_proofs<0..2^8-1>; 1313 ProofStep steps<0..2^8-1>; 1314 } MonitorProof; 1316 struct { 1317 FullTreeHead full_tree_head; 1318 MonitorProof owned_proofs<0..2^8-1>; 1319 MonitorProof contact_proofs<0..2^8-1>; 1320 InclusionProof inclusion; 1321 } MonitorResponse; 1323 The elements of owned_proofs and contact_proofs correspond one-to-one 1324 with the elements of owned_labels and contact_labels. Each 1325 MonitorProof in contact_proofs is meant to convince the user that the 1326 label they looked up is still properly included in the log and has 1327 not been surreptitiously concealed. Each MonitorProof in 1328 owned_proofs conveys the same guarantee that no past lookups have 1329 been concealed, and also proves that MonitorProof.version is the most 1330 recent version of the label. 1332 The version field of a MonitorProof contains the version that was 1333 used for computing the binary ladder, and therefore the highest 1334 version of the label that will be proven to exist. The vrf_proofs 1335 field contains VRF proofs for different versions of the label, 1336 starting at the first version that's different between the binary 1337 ladders for MonitorLabel.highest_version and MonitorProof.version. 1339 The steps field of a MonitorProof contains the proofs required to 1340 update the user's monitoring data following the algorithm in 1341 Section 5. That is, each ProofStep of a MonitorProof contains a 1342 binary ladder for the version MonitorProof.version. The steps are 1343 provided in the order that they're consumed by the monitoring 1344 algorithm. If same proof is consumed by the monitoring algorithm 1345 multiple times, it is provided in the MonitorProof structure only the 1346 first time. 1348 For MonitorProof structures in owned_labels, it is also important to 1349 prove that MonitorProof.version is the highest version of the label 1350 available. This means that such a MonitorProof must contains full 1351 binary ladders for MonitorProof.version along the frontier of the 1352 log. As such, any ProofStep under the owned_labels field that's 1353 along the frontier of the log includes a full binary ladder for 1354 MonitorProof.version instead of a regular binary ladder. For 1355 additional entries on the frontier of the log that are to the right 1356 of the leftmost frontier entry already provided, an additional 1357 ProofStep is added to MonitorProof. This additional ProofStep 1358 contains only the proofs of non-inclusion from a full binary ladder. 1360 Users verify a MonitorResponse by following these steps: 1362 1. Verify that the lengths of owned_proofs and contact_proofs are 1363 the same as the lengths of owned_labels and contact_labels. 1365 2. For each MonitorProof structure, verify that MonitorProof.version 1366 is greater than or equal to the highest version of the label 1367 that's been previously observed. 1369 3. For each MonitorProof structure, evalute the monitoring algorithm 1370 in Section 5. Abort with an error if the monitoring algorithm 1371 detects that the tree is constructed incorrectly, or if there are 1372 fewer or more steps provided than would be expected (keeping in 1373 mind that extra steps may be provided along the frontier of the 1374 log, if a MonitorProof is a member of owned_labels). 1376 4. Construct a candidate root value for the tree by combining the 1377 PrefixProof and commitment of ProofStep, with the provided 1378 inclusion proof. 1380 5. With the candidate root value, verify the provided FullTreeHead. 1382 Some information is omitted from MonitorResponse in the interest of 1383 efficiency, due to the fact that the user would have already seen and 1384 verified it as part of conducting other queries. In particular, VRF 1385 proofs for different versions of each label are not provided, given 1386 that these can be cached from the original Search or Update query. 1388 11. Security Considerations 1390 12. IANA Considerations 1392 This document requests the creation of the following new IANA 1393 registries: 1395 * KT Ciphersuites (Section 12.1) 1396 All of these registries should be under a heading of "Key 1397 Transparency", and assignments are made via the Specification 1398 Required policy [RFC8126]. See Section 12.2 for additional 1399 information about the KT Designated Experts (DEs). 1401 RFC EDITOR: Please replace XXXX throughout with the RFC number 1402 assigned to this document 1404 12.1. KT Ciphersuites 1406 uint16 CipherSuite; 1408 12.2. KT Designated Expert Pool 1410 13. References 1412 13.1. Normative References 1414 [I-D.ietf-keytrans-architecture] 1415 McMillion, B., "Key Transparency Architecture", Work in 1416 Progress, Internet-Draft, draft-ietf-keytrans- 1417 architecture-02, 26 August 2024, 1418 . 1421 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 1422 Hashing for Message Authentication", RFC 2104, 1423 DOI 10.17487/RFC2104, February 1997, 1424 . 1426 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1427 Requirement Levels", BCP 14, RFC 2119, 1428 DOI 10.17487/RFC2119, March 1997, 1429 . 1431 [RFC6962] Laurie, B., Langley, A., and E. Kasper, "Certificate 1432 Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013, 1433 . 1435 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 1436 Writing an IANA Considerations Section in RFCs", BCP 26, 1437 RFC 8126, DOI 10.17487/RFC8126, June 2017, 1438 . 1440 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 1441 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 1442 May 2017, . 1444 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 1445 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 1446 . 1448 [RFC9381] Goldberg, S., Reyzin, L., Papadopoulos, D., and J. Včelák, 1449 "Verifiable Random Functions (VRFs)", RFC 9381, 1450 DOI 10.17487/RFC9381, August 2023, 1451 . 1453 13.2. Informative References 1455 [CONIKS] Melara, M. S., Blankstein, A., Bonneau, J., Felten, E. W., 1456 and M. J. Freedman, "CONIKS: Bringing Key Transparency to 1457 End Users", 27 April 2014, 1458 . 1460 [Merkle2] Hu, Y., Hooshmand, K., Kalidhindi, H., Yang, S. J., and R. 1461 A. Popa, "Merkle^2: A Low-Latency Transparency Log 1462 System", 8 April 2021, . 1464 [OPTIKS] Len, J., Chase, M., Ghosh, E., Laine, K., and R. C. 1465 Moreno, "OPTIKS: An Optimized Key Transparency System", 4 1466 October 2023, . 1468 [SEEMLess] Chase, M., Deshpande, A., Ghosh, E., and H. Malvai, 1469 "SEEMless: Secure End-to-End Encrypted Messaging with less 1470 trust", 18 June 2018, . 1472 Acknowledgments 1474 Authors' Addresses 1476 Brendan McMillion 1477 Email: brendanmcmillion@gmail.com 1479 Felix Linker 1480 Email: linkerfelix@gmail.com