{"action":"created","comment":{"url":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/comments/33870614","id":33870614,"diff_hunk":"@@ -1396,6 +1402,94 @@ the STH changes.\n         <t>\n           A <xref target=\"tls_clients\">TLS client</xref> can audit by verifying an SCT against any STH dated after the SCT timestamp + the Maximum Merge Delay by requesting a Merkle inclusion proof (<xref target=\"fetch_proof\"/>). It can also verify that the SCT corresponds to the certificate it arrived with (i.e. the log entry is that certificate, is a precertificate for that certificate or is an appropriate name-constrained intermediate [see <xref target=\"name_constrained\"/>]).\n         </t>\n+        <t>\n+          The following algorithm outlines may be useful for clients that wish to perform various audit operations.\n+        </t>\n+        <section title=\"Verifying an inclusion proof\" anchor=\"verify_inclusion\">\n+          <t>\n+            When a client has received an <spanx style=\"verb\">audit_path</spanx> and <spanx style=\"verb\">leaf_index</spanx> and wishes to verify inclusion of an input <spanx style=\"verb\">hash</spanx> for an STH with a given <spanx style=\"verb\">tree_size</spanx> and <spanx style=\"verb\">sha256_root_hash</spanx>, the following algorithm may be used to prove the <spanx style=\"verb\">hash</spanx> was included in the <spanx style=\"verb\">sha256_root_hash</spanx>:\n+            <list style=\"numbers\">\n+              <t>Set <spanx style=\"verb\">r</spanx> to <spanx style=\"verb\">hash</spanx>.</t>\n+              <t>\n+                For each <spanx style=\"verb\">i</spanx> from <spanx style=\"verb\">0</spanx> up to <spanx style=\"verb\">LENGTH(audit_path) - 1</spanx>:\n+                <vspace blankLines=\"1\" />\n+                If the <spanx style=\"verb\">LSB(leaf_index >> i)</spanx> is set, then:\n+                <list style=\"empty\">\n+                  <t>Set <spanx style=\"verb\">r</spanx> to <spanx style=\"verb\">HASH(0x01 || audit_path[i] || r)</spanx></t>\n+                </list>\n+                Otherwise:\n+                <list style=\"empty\">\n+                  <t>Set <spanx style=\"verb\">r</spanx> to <spanx style=\"verb\">HASH(0x01 || r || audit_path[i])</spanx></t>\n+                </list>\n+              </t>\n+              <t>Compare <spanx style=\"verb\">r</spanx> against the <spanx style=\"verb\">sha256_root_hash</spanx>. If they are equal, then the log has proven the inclusion of <spanx style=\"verb\">hash</spanx>.</t>\n+            </list>\n+          </t>\n+        </section>\n+        <section title=\"Verifying consistency between two STHs\" anchor=\"verify_consistency\">\n+          <t>\n+            When a client has an STH <spanx style=\"verb\">first_hash</spanx> for tree size <spanx style=\"verb\">first</spanx>, an STH <spanx style=\"verb\">second_hash</spanx> for tree size <spanx style=\"verb\">second</spanx> where <spanx style=\"verb\">0 &lt; first &lt; second</spanx>, and has received a <spanx style=\"verb\">consistency</spanx> array that they wish to use to verify both hashes, the following algorithm may be used:\n+            <list style=\"numbers\">\n+              <t>If <spanx style=\"verb\">first</spanx> is an exact power of 2, then prepend <spanx style=\"verb\">first_hash</spanx> to the <spanx style=\"verb\">consistency</spanx> array.</t>\n+              <t>Set <spanx style=\"verb\">fn</spanx> to <spanx style=\"verb\">first - 1</spanx> and <spanx style=\"verb\">sn</spanx> to <spanx style=\"verb\">second - 1</spanx>.</t>\n+              <t>If <spanx style=\"verb\">LSB(fn)</spanx> is set, then right-shift both <spanx style=\"verb\">fn</spanx> and <spanx style=\"verb\">sn</spanx> equally until <spanx style=\"verb\">LSB(fn)</spanx> is not set.</t>\n+              <t>Set both <spanx style=\"verb\">fr</spanx> and <spanx style=\"verb\">sr</spanx> to the first value in the <spanx style=\"verb\">consistency</spanx> array.</t>\n+              <t>\n+                For each subsequent value <spanx style=\"verb\">c</spanx> in the <spanx style=\"verb\">consistency</spanx> array:\n+                <vspace blankLines=\"1\" />\n+                If <spanx style=\"verb\">LSB(fn)</spanx> is set, or if <spanx style=\"verb\">fn</spanx> is equal to <spanx style=\"verb\">sn</spanx>, then:\n+                <list style=\"numbers\">\n+                  <t>\n+                    Set <spanx style=\"verb\">fr</spanx> to <spanx style=\"verb\">HASH(0x01 || c || fr)</spanx>\n+                    <vspace blankLines=\"0\" />\n+                    Set <spanx style=\"verb\">sr</spanx> to <spanx style=\"verb\">HASH(0x01 || c || sr)</spanx>\n+                  </t>\n+                  <t>If <spanx style=\"verb\">LSB(fn)</spanx> is not set, then right-shift both <spanx style=\"verb\">fn</spanx> and <spanx style=\"verb\">fn</spanx> equally until <spanx style=\"verb\">LSB(fn)</spanx> is set.</t>","path":"rfc6962-bis.xml","position":206,"original_position":206,"commit_id":"dba78bd47daaee64d9ca32236ea1f6c95898933e","original_commit_id":"dba78bd47daaee64d9ca32236ea1f6c95898933e","user":{"login":"aeijdenberg","id":5984070,"avatar_url":"https://avatars.githubusercontent.com/u/5984070?v=3","gravatar_id":"","url":"https://api.github.com/users/aeijdenberg","html_url":"https://github.com/aeijdenberg","followers_url":"https://api.github.com/users/aeijdenberg/followers","following_url":"https://api.github.com/users/aeijdenberg/following{/other_user}","gists_url":"https://api.github.com/users/aeijdenberg/gists{/gist_id}","starred_url":"https://api.github.com/users/aeijdenberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeijdenberg/subscriptions","organizations_url":"https://api.github.com/users/aeijdenberg/orgs","repos_url":"https://api.github.com/users/aeijdenberg/repos","events_url":"https://api.github.com/users/aeijdenberg/events{/privacy}","received_events_url":"https://api.github.com/users/aeijdenberg/received_events","type":"User","site_admin":false},"body":"Corrected 2nd fn to sn.  Let me think about the other statement.","created_at":"2015-07-03T15:24:32Z","updated_at":"2015-07-03T15:24:32Z","html_url":"https://github.com/google/certificate-transparency-rfcs/pull/57#discussion_r33870614","pull_request_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57","_links":{"self":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/comments/33870614"},"html":{"href":"https://github.com/google/certificate-transparency-rfcs/pull/57#discussion_r33870614"},"pull_request":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57"}}},"pull_request":{"url":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57","id":39144482,"html_url":"https://github.com/google/certificate-transparency-rfcs/pull/57","diff_url":"https://github.com/google/certificate-transparency-rfcs/pull/57.diff","patch_url":"https://github.com/google/certificate-transparency-rfcs/pull/57.patch","issue_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/issues/57","number":57,"state":"open","locked":false,"title":"Add algorithms for verifying inclusion proofs, consistency checks","user":{"login":"aeijdenberg","id":5984070,"avatar_url":"https://avatars.githubusercontent.com/u/5984070?v=3","gravatar_id":"","url":"https://api.github.com/users/aeijdenberg","html_url":"https://github.com/aeijdenberg","followers_url":"https://api.github.com/users/aeijdenberg/followers","following_url":"https://api.github.com/users/aeijdenberg/following{/other_user}","gists_url":"https://api.github.com/users/aeijdenberg/gists{/gist_id}","starred_url":"https://api.github.com/users/aeijdenberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeijdenberg/subscriptions","organizations_url":"https://api.github.com/users/aeijdenberg/orgs","repos_url":"https://api.github.com/users/aeijdenberg/repos","events_url":"https://api.github.com/users/aeijdenberg/events{/privacy}","received_events_url":"https://api.github.com/users/aeijdenberg/received_events","type":"User","site_admin":false},"body":"Some other misc spacing changes to remove warnings from xml2rfc tool.","created_at":"2015-07-03T04:00:17Z","updated_at":"2015-07-03T15:24:32Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6056ed22fe7d9fa479345e2f16ffaab45330e772","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57/commits","review_comments_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57/comments","review_comment_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/comments{/number}","comments_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/issues/57/comments","statuses_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/statuses/dba78bd47daaee64d9ca32236ea1f6c95898933e","head":{"label":"aeijdenberg:add_step_by_step_audit_help","ref":"add_step_by_step_audit_help","sha":"dba78bd47daaee64d9ca32236ea1f6c95898933e","user":{"login":"aeijdenberg","id":5984070,"avatar_url":"https://avatars.githubusercontent.com/u/5984070?v=3","gravatar_id":"","url":"https://api.github.com/users/aeijdenberg","html_url":"https://github.com/aeijdenberg","followers_url":"https://api.github.com/users/aeijdenberg/followers","following_url":"https://api.github.com/users/aeijdenberg/following{/other_user}","gists_url":"https://api.github.com/users/aeijdenberg/gists{/gist_id}","starred_url":"https://api.github.com/users/aeijdenberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeijdenberg/subscriptions","organizations_url":"https://api.github.com/users/aeijdenberg/orgs","repos_url":"https://api.github.com/users/aeijdenberg/repos","events_url":"https://api.github.com/users/aeijdenberg/events{/privacy}","received_events_url":"https://api.github.com/users/aeijdenberg/received_events","type":"User","site_admin":false},"repo":{"id":38460669,"name":"certificate-transparency-rfcs","full_name":"aeijdenberg/certificate-transparency-rfcs","owner":{"login":"aeijdenberg","id":5984070,"avatar_url":"https://avatars.githubusercontent.com/u/5984070?v=3","gravatar_id":"","url":"https://api.github.com/users/aeijdenberg","html_url":"https://github.com/aeijdenberg","followers_url":"https://api.github.com/users/aeijdenberg/followers","following_url":"https://api.github.com/users/aeijdenberg/following{/other_user}","gists_url":"https://api.github.com/users/aeijdenberg/gists{/gist_id}","starred_url":"https://api.github.com/users/aeijdenberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeijdenberg/subscriptions","organizations_url":"https://api.github.com/users/aeijdenberg/orgs","repos_url":"https://api.github.com/users/aeijdenberg/repos","events_url":"https://api.github.com/users/aeijdenberg/events{/privacy}","received_events_url":"https://api.github.com/users/aeijdenberg/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/aeijdenberg/certificate-transparency-rfcs","description":"Certificate Transparency RFC","fork":true,"url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs","forks_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/forks","keys_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/teams","hooks_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/hooks","issue_events_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/issues/events{/number}","events_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/events","assignees_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/assignees{/user}","branches_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/branches{/branch}","tags_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/tags","blobs_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/git/refs{/sha}","trees_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/statuses/{sha}","languages_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/languages","stargazers_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/stargazers","contributors_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/contributors","subscribers_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/subscribers","subscription_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/subscription","commits_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/commits{/sha}","git_commits_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/git/commits{/sha}","comments_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/comments{/number}","issue_comment_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/issues/comments{/number}","contents_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/contents/{+path}","compare_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/merges","archive_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/downloads","issues_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/issues{/number}","pulls_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/pulls{/number}","milestones_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/milestones{/number}","notifications_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/labels{/name}","releases_url":"https://api.github.com/repos/aeijdenberg/certificate-transparency-rfcs/releases{/id}","created_at":"2015-07-02T22:53:02Z","updated_at":"2015-07-02T22:53:02Z","pushed_at":"2015-07-03T04:09:35Z","git_url":"git://github.com/aeijdenberg/certificate-transparency-rfcs.git","ssh_url":"git@github.com:aeijdenberg/certificate-transparency-rfcs.git","clone_url":"https://github.com/aeijdenberg/certificate-transparency-rfcs.git","svn_url":"https://github.com/aeijdenberg/certificate-transparency-rfcs","homepage":"http://www.certificate-transparency.org/","size":1617,"stargazers_count":0,"watchers_count":0,"language":"Makefile","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"google:master","ref":"master","sha":"7793e62f8f7ec7d95fac308fbe800539b1749b4a","user":{"login":"google","id":1342004,"avatar_url":"https://avatars.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"repo":{"id":20069953,"name":"certificate-transparency-rfcs","full_name":"google/certificate-transparency-rfcs","owner":{"login":"google","id":1342004,"avatar_url":"https://avatars.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/google/certificate-transparency-rfcs","description":"Certificate Transparency RFC","fork":false,"url":"https://api.github.com/repos/google/certificate-transparency-rfcs","forks_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/forks","keys_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/keys{/key_id}","collaborators_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/teams","hooks_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/hooks","issue_events_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/issues/events{/number}","events_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/events","assignees_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/assignees{/user}","branches_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/branches{/branch}","tags_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/tags","blobs_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/git/refs{/sha}","trees_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/git/trees{/sha}","statuses_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/statuses/{sha}","languages_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/languages","stargazers_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/stargazers","contributors_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/contributors","subscribers_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/subscribers","subscription_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/subscription","commits_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/commits{/sha}","git_commits_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/git/commits{/sha}","comments_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/comments{/number}","issue_comment_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/issues/comments{/number}","contents_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/contents/{+path}","compare_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/compare/{base}...{head}","merges_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/merges","archive_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/downloads","issues_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/issues{/number}","pulls_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls{/number}","milestones_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/milestones{/number}","notifications_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/labels{/name}","releases_url":"https://api.github.com/repos/google/certificate-transparency-rfcs/releases{/id}","created_at":"2014-05-22T17:15:59Z","updated_at":"2015-07-03T07:00:10Z","pushed_at":"2015-07-03T14:43:17Z","git_url":"git://github.com/google/certificate-transparency-rfcs.git","ssh_url":"git@github.com:google/certificate-transparency-rfcs.git","clone_url":"https://github.com/google/certificate-transparency-rfcs.git","svn_url":"https://github.com/google/certificate-transparency-rfcs","homepage":"http://www.certificate-transparency.org/","size":1617,"stargazers_count":23,"watchers_count":23,"language":"Makefile","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":8,"mirror_url":null,"open_issues_count":5,"forks":8,"open_issues":5,"watchers":23,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57"},"html":{"href":"https://github.com/google/certificate-transparency-rfcs/pull/57"},"issue":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/issues/57"},"comments":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/issues/57/comments"},"review_comments":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57/comments"},"review_comment":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/pulls/57/commits"},"statuses":{"href":"https://api.github.com/repos/google/certificate-transparency-rfcs/statuses/dba78bd47daaee64d9ca32236ea1f6c95898933e"}}}}