Folks:
(This is a copy of
https://tahoe-lafs.org/trac/tahoe-lafs/ticket/795#comment:13 .)
Here's my rendition of our discussion of add-only sets at the Tahoe-LAFS
Summit today. (As usual, I altered and embellished this story significantly
while writing it down, and people who were present to witness the original
discussion are invited to chime in.)
An add-only cap doesn't have to also be a write-only cap. It might be good
for some use cases that you can give someone a cap that lets them read the
whole set, and add elements into the set, without letting them remove
elements or change previously-added elements. It might be good in some
*other* use cases to have an add-onlywrite-only cap, which allows you to
add elements into the set but doesn't let you read elements of the set, nor
remove nor change previously-added elements. We agreed to focus on the
former case for now, because it is easier to design and implement a
solution to it. (See
#796https://tahoe-lafs.org/trac/tahoe-lafs/ticket/796for discussion
of write-only caps.)
We agreed to forget about erasure-coding, which makes an already-confusing
problem (how to implement add-only sets without allowing a few malicious
servers, adders, or set-repairers to perform *rollback attack* or *selection
attack*), into a *very*-confusing problem that exceeded my brain's ability
to grapple with it.
So, for now, assume that add-only sets don't use erasure-coding at all.
Now, the basic design we came up with is like this. I'll explain it in
multiple passes of successive refinement of the design.
FIRST PASS: DESIGN 0
An authorized adder (someone who holds an add-cap) can generate elements,
which are bytestrings that can be added into the set. (I mispronounced
elements as elephants at one point, and from that point forward the
design was expressed in terms of a circus act involving elephants.)
Elephants have an identity as well as a value (bytestring), so:
aos = DistributedSecureAddOnlySet()
aos.add_elephant(b\xFF*100)
aos.add_elephant(b\xFF*100)
results in aos containing *two* elephants, not one, even though each
elephant has the same value (the bytestring with one hundred 0xFF bytes in
it).
aos.add_elephant() generates a random 256-bit nonce to make this elephant
different from any other elephant with the same value. I call this putting
a tag on the elephant's ear — a tagged elephant is a value plus a nonce.
Even if two elephants are identical twins, they can be distinguished by the
unique nonce written on their ear-tags.
aos.add_elephant() then puts a digital signature on the tagged-elephant
(using the add-only-cap, which contains an Ed25519 private key), and sends
a copy of the tagged-elephant to every one of N different servers. Putting
a digital signature on a tagged-elephant is called wrapping a net around
it.
A reader downloads all the tagged-elephants from all the servers, checks
all the signatures, takes the union of the results, and returns the
resulting set of elephants.
Design A relies on *at least one* of the servers that you reach to save
you from rollback or selection attacks. Such a server does this by knowing,
and honestly serving up to you, a fresh and complete set of
tagged-elephants. “Rollback” is serving you a version of the set that
existed at some previous time, so the honest server giving you a copy of
the most recent set protects you from rollback attack. “Selection” is
omitting some elephants from the set, so the honest server giving you a
complete copy of the set protects you from selection attack.
SECOND PASS: DESIGN 1
We can extend Design 0 to make it harder for malicious servers to perform
selection attacks on readers, even when the reader doesn't reach an honest
server who has a complete copy of the most recent set.
The unnecessary vulnerability in Design 0 is that each tagged-elephant is
signed independently of the other tagged-elephants, so malicious servers
can deliver some tagged-elephants to a reader and withhold other
tagged-elephants, and the reader will accept the resulting set, thus
falling for a selection attack. To reduce this vulnerability, adders will
sign all of the *current* tagged-elephants along with their new
tagged-elephant with a single signature. More precisely, let the identity
of a tagged-elephant be the secure hash of the tagged-elephant (i.e. the
secure hash of the nonce concatenated with the value). The signature on a
new tagged-elephant covers the identity of that tagged-elephant,
concatenated with the identities of all extant tagged-elephants, under a
single signature. In circus terms, you add the new tagged-elephant into a
pile of tagged-elephants and throw a net over the entire pile, including
the new tagged-elephant.
Now, malicious servers can't omit any of the older tagged-elephants without
also omitting the new tagged-elephant. Readers will not accept the new
tagged-elephant unless they also have a copy of all of the other
tagged-elephants that were signed with the same
