1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
-*- markdown -*-
Overview
========
This document describes the design of catlfish, an implementation of a
Certificate Transparency (RFC6962) log server.
+------------------------------------------------+
| front end nodes |
+------------------------------------------------+
^ | |
| v v
| +---------------+ +---------------+
| | storage nodes | | signing nodes |
| +---------------+ +---------------+
| ^ ^
| | |
+------------------------------------------------+
| primary merge node |
+------------------------------------------------+
^ |
| v
| +----------------------------------+
| | secondary merge nodes |
| +----------------------------------+
| ^
| |
+-------------------+
| merge-repair node |
+-------------------+
Design assumptions
------------------
* The database grows with 5 GB per year, based on 5,000 3 kB
submissions per day
* Max size is 300 GB, based on 100e6 certificates
* submissions: less than 0.1 qps, based on 5,000 submissions per day
* monitors: 6 qps, based on 100 monitors
* auditors: 8,000 qps, based on 2.5e9 browsers visiting 100 sites
(with a 1y certificate) per month (assuming a single combined
request for doing get-sth + get-sth-consistency + get-proof-by-hash)
Terminology
===========
CC = Certificate Chain
CT log = Certificate Transparency log
Front-end node
==============
* Handles all http requests.
* Has a complete copy of the published data locally.
* Read requests are answered directly by reading local files
and calculating the answers.
* Add requests are validated and then sent to all storage
nodes. At the same time, a signing request is sent to one or
more of the signing nodes. When responses have been received
from a predetermined number of storage nodes and one signing
response has been received, a response is sent to the client.
* Has an inward-facing API with the entry points SendLog(Hashes),
MissingEntries() (returns a list of hashes), SendEntry(Entry),
SendSTH(STH), CurrentPosition().
Storage node
============
* Stores certificate chains and SCTs.
* Has a write API SendEntry(Entry) that stores the certificate chain
in a database, indexed by its hash. Then stores the hash in a list
NewEntries.
* Takes reasonable measures to ensure that data is in permanent
storage before sending a response.
* When seeing a new STH, moves the variable start to the index of the
first unpublished hash.
* Has a read API FetchNewEntries() which returns
NewEntries[start...length(NewEntries)-1].
Signing node
============
* Has the signing key for the log.
Merging node
============
* The primary merge node is determined by configuration.
* The other merging nodes are called "secondaries".
* The primary merge node has two phases, merging and distributing.
Merging (primary)
-----------------
* Fetches CCs by calling FetchNewEntries() on storage node i
where i = 0...(n-1)
* Determines the order of the new entries in the CT log.
* Sends the entries to the secondary merge nodes.
* Calculates the tree head and asks a signing node to sign it.
* When a majority of the secondaries have acknowledged the entries,
compares the calculated tree head to the tree heads of the secondaries.
If they match, considers the additions to the CT log final and
begins the distributing phase.
Merging (secondaries)
---------------------
* Receives entries from the primary merge node. The node must be certain
that the request comes from the current primary, and not
an old one.
* Takes reasonable measures to ensure that data is in
permanent storage.
* Calculates the new tree head and returns it to the primary merge node.
Distributing
------------
* Performs the following steps for all front-end nodes:
* Fetches curpos by calling CurrentPosition().
* Calls SendLog() with the hashes of CCs from curpos to newpos.
* Fetches missing_entries by calling MissingEntries(), a list
of hashes for the CCs that the front-end nodes does not
have.
* For each hash in missing_entries, upload the CC by calling
SendEntry(CC).
* Send the STH with the SendSTH(STH) call.
Merge-repair node
=================
* There is only one of these nodes.
* When this node detects that an STH has not been published
in t seconds, it begins the automatic repair process.
Automatic repair process
------------------------
* Turn off all reachable merge nodes.
* If a majority of the merge nodes cannot be reached,
die and report.
* Fetch the CT log order from the merge nodes.
* Determine the latest version of the log.
* Select a new primary merge node.
* Change the configuration of the merge nodes so that
they know who the new primary merge node is.
* Start all merge nodes.
* If any of these steps fail, die and report.
* If all steps succeed, die and report anyway. The automatic
repair process must not be restarted without manual
intervention.
|
