Found that our key services had no way to agree

The specification, rewritten

This entry covers one afternoon. Everything below was done on 23 September, in the hours after the last entry went up. Nothing further was committed to the platform between 24 and 27 September.

The last entry described the failed review of our key setup document. That document sits inside the specification for the security core, which sets out what each of the five key services does. We rewrote the specification in one pass, in preference to patching it with the 11 amendments already drafted against it.

First, three of our own reviewers went over it, working blind and trying to break it. Adopting the published construction described in the last entry dealt with about a third of what they found. The largest defect was in the rest.

The document now carries 8 citations, where its 1,502 lines had carried none, and it grew to 1,871 lines. Where earlier wording was wrong, the old text is quoted beside the new. Of the 11 amendments, 4 were applied; the other 7 rested on a design that had since been replaced.

Two of the tests we had written to prove claims false could never have failed. Each gave the attacker a starting position in which the attack was already impossible. One of them was the test behind our claim about erasure. Both are now rollback tests, which put a service back to an earlier state.

A gap nobody was looking for

The specification assumes, on every page, that the five services agree with one another: that they hold the same version of a record, the same list of members and the same answer to the same question. It never says how. Of the findings, 32 were that one problem in different forms.

After an interrupted update, two services can hold different versions of the same index. An objection lodged at one service never reaches the three that approve the change. The random sample that decides when old key material may be destroyed is drawn from records which the document itself says differ between services.

Better wording cannot fix that. The rewrite names the gap, marks every claim that depends on it, and states it outright as a limit of the design.

Counting the places that must agree

The plan was to close the gap with one published mechanism, a certified equality check: every service signs its record of a session, and a full set of signatures proves to anyone, later, that all of them saw the same thing. The review stopped it. It would have closed 7 places, left 16 open, and read as though it had closed them all. That is the failure that ended the last two versions of the key setup.

Counted properly, there are 23 places where the services must hold the same value. An estimate the day before had put it at 16. That came from a skim.

• 7 ceremonies, bounded sessions with a record, where the equality check fits

• 16 pieces of running state with no session boundary, where it fits none

• 4 values that cannot agree at all, because each service computes them on its own clock

• Changes to the list of members, which must never be given the check

Four different problems, not one

Two of the four clock values drive hard limits, with no rule for whose answer decides. The last kind is the subtle one. A change to the list of members looks like a ceremony, but the check is a form of broadcast with abort, which tolerates any number of corrupt parties at the price of letting any one of them stop the session. Wrapped in it, a departure could be stalled by one faulty service, and that person's access would not be withdrawn.

All four repairs first proposed were wrong. One amounted to choosing between two competing histories of the same record, and the only sound rule for that is a rollback the design forbids. The review also found three defects worse than any of the four. The worst concerns what the specification calls "the check that bites", which stops someone impersonating an active member. It reads a value each service holds on its own and does not share, so it does not bite at a service the member has not asked recently.

The afternoon produced a requirements document with 12 requirements and no design. Half of it, the part covering ceremonies, waits on one of the five open questions we published on 23 September: whether a single faulty service costs one key or several hundred.

• Secure Computation Without Agreement, Goldwasser and Lindell, 2002

Three fixes that failed review

At 16:54 UTC we committed first fixes for the three worst defects. Every one was wrong, and one was worse than the defect it repaired.

The impersonation check first merged the services' timestamps by taking the highest. With the highest, one liar decides. A single service signing a date 10 years ahead would have blocked a chosen member's only route to recovery for good, silently, with fewer corrupt services than the design tolerates anywhere else. The rule now takes the third highest of the five, which honest values bound from both sides, checked at commit as well as at proposal.

The fix to the log proofs was right but incomplete. A proof that a peer logged an event says nothing about whether the event was allowed. As drafted, one service could stop every peer serving a collection and, for an addition it had invented, have them grant access on its word. The rule now acts only on an event the receiving service checks against its own list of members.

The fix to the erasure record borrowed a threshold from elsewhere in the document. It was safe at five services by coincidence. In a smaller arrangement it equals the number of corrupt services tolerated, so two of them could have certified an erasure that never happened. It now requires more signed entries than that. The sentence a reader would have quoted, "a service missing the entry still refuses", was false for exactly the services it was about.

The first tests for these fixes checked, in one case, the attack the design already blocked rather than the one the fix had opened. Three new tests replace them. The review of the fixes was worth more than the fixes.

A source described from memory

The equality check comes from ChillDKG, a draft from Blockstream Research. Our specification had called it a Bitcoin standard proposal. It is not one, and it has no number. Nor is it proven: the paper behind it proves the surrounding protocol secure given an abstract equality check, and nothing published shows this check meets that. We had also missed that what a participant signs binds its own position in the session, a detail whose absence ChillDKG's own changelog records as a fixed vulnerability. We had written it from memory.

• ChillDKG, distributed key generation for FROST, Blockstream Research, draft
• Practical Schnorr Threshold Signatures Without the Algebraic Group Model, Chu, Gerhart, Ruffing and Schröder, 2023

Where this leaves the key layer

Nothing in this entry is built. No key service code exists, and nothing on the platform is encrypted. The fixes above are specified, and each says in the same sentence that it is not built. The agreement gap has requirements and no design. The five open questions published on 23 September are all still open, and none has been put to, or answered by, a cryptographer outside the team.