A group keeps one shared log. One party, the signer, appends events and signs the running head of the log. The log has rules: only current writers may post, only an administrator may grant a role, a post must satisfy some bound. The rules also say who may read each event. A grant might be visible only to its author and an administrator, and a post only to its author and an administrator.
This creates a tension. Checking that the signer followed the rules seems to need the whole log, but most parties may not read most of it. The question for this article is what can be guaranteed anyway, and by whom. None of the parts used here is new. Hash-chained heads, signatures, a state folded from the log, fraud proofs that are produced only on dispute, and zero-knowledge proofs are all standard, and each is credited below. The contribution is the combination, together with proofs that the combination does what it is meant to do, and two small counterexamples that show where the obvious guess about auditors goes wrong.
Every result below is machine-checked in core Lean 4. The Lean blocks, read in order, form one file with no unfinished proofs and no added axioms. The cryptography is not proved. Signatures, the hash, the proof system and zero knowledge enter as explicit assumptions in an idealised symbolic model, and each one is marked where it appears.
The goal
Fix a set of parties, a type of events, a type of states with an initial state and a transition function, and a finite list of rules. Each rule looks at the current state and the next event and returns accept or reject. A log is a list of events, and its head is a short value computed from the whole log by a hash chain. The signer publishes signed heads. Each event has a public header and a body, and a relation says whether party may read the body of an event with header .
The combination should achieve five things.
- Local validity. A log is valid exactly when every step is valid in the state folded from the steps before it.
- One step suffices. If the signer signs the head of an invalid log, then a single fraud proof about the first invalid step, together with the signed head, convicts the signer.
- No framing. Under the stated assumptions, if the signer only ever signs heads of valid logs, then no fraud proof against it is accepted.
- Auditability. For a step and a rule , say which parties can decide from their own view whether accepts step .
- Disclosure. What a verifier learns from an accepted fraud proof is its public statement, the triple (head, step, rule), and nothing about the events beyond what that statement itself says.
The components
Each component is standard. The source given for each is where I take the idea from, not a claim about who first had it.
- Hash-chained heads. The head of a log is for a fixed genesis value . Chaining hashes so that one value commits to an ordered history goes back to How to Time-Stamp a Digital Document (Journal of Cryptology, 1991). Signed heads of append-only logs are studied in Efficient Data Structures for Tamper-Evident Logging (USENIX Security Symposium, 2009).
- Signatures. The signer signs heads. The security notion assumed is existential unforgeability under adaptive chosen-message attack, from A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks (SIAM Journal on Computing, 1988).
- A permission state folded from the log. Roles and permissions are the state of a state machine, and each event moves that state. Roles as the unit of permission follow Role-Based Access Control Models (IEEE Computer, 1996).
- Single-step dispute resolution. A challenger who sees a violation proves one specific step wrong. Reducing a dispute to one step follows the refereed games in Practical Delegation of Computation Using Multiple Servers (ACM CCS, 2011). Running checks only when someone disputes, so that nobody re-executes the log by default, is a design choice of this combination and is not taken from that paper.
- Zero-knowledge proofs. The fraud proof shows that a violation exists without showing the events, from The Knowledge Complexity of Interactive Proof Systems (SIAM Journal on Computing, 1989). Zero knowledge is used here as an ideal functionality, in the sense of Universally Composable Security: A New Paradigm for Cryptographic Protocols (FOCS, 2001). A real instantiation would also need knowledge soundness, from On Defining Proofs of Knowledge (CRYPTO, 1992).
- The symbolic model. Cryptographic primitives are treated as perfect, as in On the Security of Public Key Protocols (IEEE Transactions on Information Theory, 1983).
- Knowledge as indistinguishable views. “Party can decide ” means has the same value in every world that cannot tell apart from the real one, as in Knowledge and Common Knowledge in a Distributed Environment (Journal of the ACM, 1990). Asking what a party’s view does and does not determine is the idea behind Security Policies and Security Models (IEEE Symposium on Security and Privacy, 1982).
- Accountability. Misbehaviour can be blamed on the party responsible, and no honest party is blamed, as in Accountability: Definition and Relationship to Verifiability (ACM CCS, 2010).
The combination
The signer keeps the log and the folded permission state. It appends events, and after each append it signs the new head. Parties receive every header and the bodies they may read. In the normal case nobody proves anything. A party that holds a log consistent with a signed head and finds a step that breaks a rule produces a zero-knowledge proof of the claim “the log with this head violates rule at step ”. The verifier checks the proof and the signature on the head. If both pass, the signer is convicted.
- appendevent e
state s := apply s e - disputefind step i
check r s_i e_i = false - proveclaim (h, i, r)
zero knowledge - verdictsigner convicted
signed h ∧ proof ok
Definitions
Rule system. A rule system is a tuple with an initial state , a transition , a finite list of rules , and . A step is valid in state when holds for every . For a log , the state before step is the fold of the first events,
and the log is valid when each is valid in , checked from left to right.
/-
Rule-following of an append-only signed log whose events have restricted readers.
Idealised symbolic model, core Lean 4 only.
Assumptions are modelled, never proved:
* collision resistance of the chain hash -> the hypothesis `CollisionFree`
* unforgeability of the head signature -> `signed : D → Prop` is exactly the set of
heads the signer actually signed
* soundness/completeness of the proof system -> `Accepted` holds iff a witness exists
* zero knowledge -> the ideal transcript is `(claim, bit)`
-/
namespace PrivateLogAudit
/-! ## 1. Rule systems, folded state, per-step validity -/
structure Sys (S E R : Type) where
init : S
apply : S → E → S
rules : List R
check : R → S → E → Bool
variable {S E R D : Type}
/-- A step is valid when every rule accepts it in the current state. -/
def stepOK (sys : Sys S E R) (s : S) (e : E) : Bool :=
sys.rules.all (fun r => sys.check r s e)
/-- Whole-log validity, checked step by step while folding the state. -/
def validFrom (sys : Sys S E R) : S → List E → Bool
| _, [] => true
| s, e :: es => stepOK sys s e && validFrom sys (sys.apply s e) es
/-- The state in force just before step `i`: the fold of the first `i` events. -/
def stateFrom (sys : Sys S E R) (s : S) (l : List E) (i : Nat) : S :=
(l.take i).foldl sys.apply s
theorem stateFrom_zero (sys : Sys S E R) (s : S) (l : List E) :
stateFrom sys s l 0 = s := by
simp [stateFrom]
theorem stateFrom_cons_succ (sys : Sys S E R) (s : S) (e : E) (es : List E) (i : Nat) :
stateFrom sys s (e :: es) (i + 1) = stateFrom sys (sys.apply s e) es i := by
simp [stateFrom]
theorem all_false {α : Type} (p : α → Bool) :
∀ l : List α, l.all p = false → ∃ x ∈ l, p x = false
| [], h => by simp at h
| x :: xs, h => by
cases hx : p x with
| false => exact ⟨x, by simp, hx⟩
| true =>
simp [List.all_cons, hx] at h
obtain ⟨y, hy, hpy⟩ := all_false p xs (by simpa using h)
exact ⟨y, by simp [hy], hpy⟩
Theorems 1 and 2a: validity is local, and the first invalid step
Theorem 1 (fold). For every state and log , the log is valid from if and only if, for every index with , the step is valid in the state .
Proof. Induction on . The empty log is valid, and it has no indices. For , validity is ” valid in , and valid from ”. Index gives the first conjunct. Index of is index of , and computed from . The induction hypothesis then gives the second conjunct. ∎
Theorem 2a (first invalid step). If is not valid from , there are an index , the event and a rule with , and every step before is valid in its own state.
Proof. Induction on . If the first step is invalid, some rule in the list rejects it, and with nothing before it. Otherwise the rest of the log is invalid from . The induction hypothesis gives an index there, and works for the whole log, since step is valid. ∎
-- continues the file above
/-- Theorem 1 (fold): the log is valid iff every step is valid in its folded state. -/
theorem valid_iff_steps (sys : Sys S E R) (s : S) (l : List E) :
validFrom sys s l = true ↔
∀ i e, l[i]? = some e → stepOK sys (stateFrom sys s l i) e = true := by
induction l generalizing s with
| nil => simp [validFrom]
| cons e es ih =>
simp only [validFrom, Bool.and_eq_true, ih]
constructor
· intro ⟨h0, hrest⟩ i e' hi
cases i with
| zero =>
simp at hi
subst hi
simpa [stateFrom_zero] using h0
| succ j =>
rw [stateFrom_cons_succ]
exact hrest j e' (by simpa using hi)
· intro h
refine ⟨?_, ?_⟩
· simpa [stateFrom_zero] using h 0 e (by simp)
· intro j e' hj
have := h (j + 1) e' (by simpa using hj)
rwa [stateFrom_cons_succ] at this
/-- Theorem 2a (first invalid step): an invalid log has a least step `i` and a rule `r`
that rejects it, with all earlier steps valid. -/
theorem first_invalid (sys : Sys S E R) (s : S) (l : List E)
(h : validFrom sys s l = false) :
∃ i e r, l[i]? = some e ∧ r ∈ sys.rules ∧
sys.check r (stateFrom sys s l i) e = false ∧
∀ j e', j < i → l[j]? = some e' → stepOK sys (stateFrom sys s l j) e' = true := by
induction l generalizing s with
| nil => simp [validFrom] at h
| cons e es ih =>
cases hs : stepOK sys s e with
| false =>
obtain ⟨r, hr, hc⟩ := all_false _ _ hs
refine ⟨0, e, r, by simp, hr, ?_, ?_⟩
· simpa [stateFrom_zero] using hc
· intro j e' hj; omega
| true =>
have hrest : validFrom sys (sys.apply s e) es = false := by
simpa [validFrom, hs] using h
obtain ⟨i, e', r, hi, hr, hc, hprev⟩ := ih (sys.apply s e) hrest
refine ⟨i + 1, e', r, by simpa using hi, hr, ?_, ?_⟩
· rw [stateFrom_cons_succ]; exact hc
· intro j e'' hj hj'
cases j with
| zero =>
simp at hj'
subst hj'
simpa [stateFrom_zero] using hs
| succ k =>
rw [stateFrom_cons_succ]
exact hprev k e'' (by omega) (by simpa using hj')
Hash-chained heads
Head. Fix a genesis value and a function . The head of a log is and . In Lean this is a chain over the reversed list. The lemma head_snoc states the append equation.
Assumption A1 (collision-free hash, idealised). is injective on pairs, and for all . A real hash function only makes collisions hard to find. A1 replaces that computational property by the symbolic one.
Lemma (a head binds the log). Under A1, implies .
Proof. Compare the reversed lists by induction. If one is empty and the other is not, one side is and the other is a value of , which A1 rules out. If both are non-empty, injectivity gives equal last events and equal heads of the remaining lists. ∎
-- continues the file above
/-! ## 2. Hash-chained heads (idealised collision-free hash) -/
structure HashModel (D E : Type) where
genesis : D
H : D → E → D
/-- Chain over a newest-first list. -/
def chain (hm : HashModel D E) : List E → D
| [] => hm.genesis
| e :: r => hm.H (chain hm r) e
/-- The head of an append-only log (oldest first). -/
def head (hm : HashModel D E) (l : List E) : D := chain hm l.reverse
theorem head_snoc (hm : HashModel D E) (l : List E) (e : E) :
head hm (l ++ [e]) = hm.H (head hm l) e := by
simp [head, chain]
/-- ASSUMPTION (idealised): the hash is injective on pairs and never returns `genesis`. -/
def CollisionFree (hm : HashModel D E) : Prop :=
(∀ d e d' e', hm.H d e = hm.H d' e' → d = d' ∧ e = e') ∧
(∀ d e, hm.H d e ≠ hm.genesis)
theorem chain_inj {hm : HashModel D E} (hcf : CollisionFree hm) :
∀ r1 r2 : List E, chain hm r1 = chain hm r2 → r1 = r2
| [], [], _ => rfl
| [], e :: r, h => absurd h.symm (hcf.2 _ _)
| e :: r, [], h => absurd h (hcf.2 _ _)
| e :: r, e' :: r', h => by
obtain ⟨h1, h2⟩ := hcf.1 _ _ _ _ h
rw [chain_inj hcf r r' h1, h2]
/-- A head binds the whole log. -/
theorem head_inj {hm : HashModel D E} (hcf : CollisionFree hm) {l1 l2 : List E}
(h : head hm l1 = head hm l2) : l1 = l2 := by
have := congrArg List.reverse (chain_inj hcf _ _ h)
simpa using this
Fraud proofs
Claim and witness. A claim is a triple . A log witnesses when , for some , and . This relation is the statement that the proof system proves.
Assumption A2 (unforgeable signatures, idealised). A predicate holds exactly for the heads the signer actually signed. Nobody else can make it true.
Assumption A3 (sound and complete proofs, idealised). The verifier accepts a fraud proof for exactly when holds and some log witnesses .
-- continues the file above
/-! ## 3. Fraud proofs: accountability and no framing -/
/-- Public statement of a fraud proof: "the log with head `head` violates rule `rule`
at step `idx`". -/
structure Claim (D R : Type) where
head : D
idx : Nat
rule : R
/-- The NP relation behind the fraud proof; the witness is the log. -/
def Witnesses (sys : Sys S E R) (hm : HashModel D E) (c : Claim D R) (l : List E) : Prop :=
head hm l = c.head ∧ ∃ e, l[c.idx]? = some e ∧ c.rule ∈ sys.rules ∧
sys.check c.rule (stateFrom sys sys.init l c.idx) e = false
/-- ASSUMPTIONS (idealised): `signed h` holds exactly for heads the signer signed
(unforgeability), and the verifier accepts iff a witness exists (soundness and
completeness of the proof system). -/
def Accepted (sys : Sys S E R) (hm : HashModel D E) (signed : D → Prop)
(c : Claim D R) : Prop :=
signed c.head ∧ ∃ l, Witnesses sys hm c l
Theorems 2 and 3: conviction and no framing
Theorem 2b (one step suffices). If and is invalid, then there are and such that the claim is accepted, and every step before is valid.
Proof. Theorem 2a gives the first invalid step and a rejecting rule , and itself witnesses the claim. ∎
Theorem 2c (conviction). If a claim is accepted, then there is a log with , and invalid. Under A1, is the only log whose head is .
Proof. A3 gives a witness . If were valid, Theorem 1 would make step valid, so every rule, included, would accept it. That contradicts the witness (witness_invalid). Uniqueness is the binding lemma. ∎
So an accepted fraud proof shows that the signer put its signature on the head of a log that breaks the rules. Under A1 there is exactly one log behind that head, so the signer cannot claim it meant a different one.
-- continues the file above
/-- A witnessed violation makes the log invalid. -/
theorem witness_invalid (sys : Sys S E R) (hm : HashModel D E) (c : Claim D R)
(l : List E) (hw : Witnesses sys hm c l) : validFrom sys sys.init l = false := by
obtain ⟨_, e, he, hr, hc⟩ := hw
cases hv : validFrom sys sys.init l with
| false => rfl
| true =>
have hstep := (valid_iff_steps sys sys.init l).1 hv c.idx e he
have := List.all_eq_true.1 hstep c.rule hr
rw [hc] at this
exact absurd this (by decide)
/-- Theorem 2b (one step suffices): a signed head of an invalid log
yields an accepted fraud proof about its first invalid step. -/
theorem fraud_proof_exists (sys : Sys S E R) (hm : HashModel D E) (signed : D → Prop)
(l : List E) (hs : signed (head hm l)) (hinv : validFrom sys sys.init l = false) :
∃ i r, Accepted sys hm signed ⟨head hm l, i, r⟩ ∧
∀ j e', j < i → l[j]? = some e' →
stepOK sys (stateFrom sys sys.init l j) e' = true := by
obtain ⟨i, e, r, he, hr, hc, hprev⟩ := first_invalid sys sys.init l hinv
exact ⟨i, r, ⟨hs, l, rfl, e, he, hr, hc⟩, hprev⟩
/-- Theorem 2c (conviction): an accepted fraud proof exhibits a signed head of an
invalid log; under collision-freedom that log is the only log with this head. -/
theorem conviction (sys : Sys S E R) (hm : HashModel D E) (signed : D → Prop)
(c : Claim D R) (hacc : Accepted sys hm signed c) :
∃ l, signed (head hm l) ∧ head hm l = c.head ∧ validFrom sys sys.init l = false ∧
(CollisionFree hm → ∀ l', head hm l' = c.head → l' = l) := by
obtain ⟨hs, l, hw⟩ := hacc
refine ⟨l, hw.1 ▸ hs, hw.1, witness_invalid sys hm c l hw, ?_⟩
intro hcf l' hl'
exact head_inj hcf (hl'.trans hw.1.symm)
Honest signer. The signer is honest when every head it signs is the head of some valid log.
Theorem 3 (no framing). Under A1, A2 and A3, no claim is accepted against an honest signer.
Proof. Suppose is accepted. Theorem 2c gives an invalid log with signed head . Honesty gives a valid log with head . By the binding lemma , so is both valid and invalid. ∎
Collision-freedom is needed. Let with . This never returns , but it is not injective. Take one rule, “the event is not 13”. The signer signs only head , which is the head of the valid log , so it is honest. The log also has head and violates the rule at step , so the claim is accepted.
-- continues the file above
/-- An honest signer signs only heads of valid logs. -/
def Honest (sys : Sys S E R) (hm : HashModel D E) (signed : D → Prop) : Prop :=
∀ h, signed h → ∃ l, head hm l = h ∧ validFrom sys sys.init l = true
/-- Theorem 3 (no framing): under collision-freedom, no fraud proof against an honest
signer is accepted. -/
theorem no_framing (sys : Sys S E R) (hm : HashModel D E) (signed : D → Prop)
(hcf : CollisionFree hm) (hon : Honest sys hm signed) (c : Claim D R) :
¬ Accepted sys hm signed c := by
intro hacc
obtain ⟨l, hs, hh, hinv, huniq⟩ := conviction sys hm signed c hacc
obtain ⟨l0, hl0, hval⟩ := hon _ hs
have : l0 = l := huniq hcf l0 (hl0.trans hh)
subst this
rw [hval] at hinv
exact absurd hinv (by decide)
/-! Collision-freedom is needed: with a colliding hash an honest signer is framed. -/
def toySys : Sys Unit Nat Unit where
init := ()
apply := fun s _ => s
rules := [()]
check := fun _ _ e => e != 13
def collidingHash : HashModel Nat Nat where
genesis := 0
H := fun d _ => d + 1
theorem framing_without_collision_freedom :
Honest toySys collidingHash (fun h => h = 1) ∧
Accepted toySys collidingHash (fun h => h = 1) ⟨1, 0, ()⟩ := by
refine ⟨?_, ?_⟩
· intro h hh
subst hh
exact ⟨[0], rfl, rfl⟩
· exact ⟨rfl, [13], rfl, 13, rfl, by decide, rfl⟩
Who can audit a step
Now give events a public header and a body. Party sees every header, and it sees a body only if holds.
View. is the list of pairs (header, body if reads it, otherwise nothing).
Decides. Party decides rule at step of when every log with gives the same verdict as for rule at step . Here the verdict is , or “no step” if the log is shorter.
Knows the state. Party knows the state at when every log with the same view has the same folded state .
This is the indistinguishability notion of knowledge. A party can check a step exactly when no log it cannot tell apart from the real one gives a different verdict.
-- continues the file above
/-! ## 4. Auditability under restricted reading -/
/-- Events have a public header (author, kind, ...) and a body visible only to readers. -/
structure Ev (Hd B : Type) where
hdr : Hd
body : B
deriving DecidableEq
variable {Hd B P : Type}
/-- What party `p` sees of the log: every header, and the bodies it may read. -/
def view (reads : P → Hd → Bool) (p : P) (l : List (Ev Hd B)) : List (Hd × Option B) :=
l.map (fun e => (e.hdr, if reads p e.hdr then some e.body else none))
/-- Verdict of rule `r` on step `i` (`none` if the log is shorter). -/
def checkAt (sys : Sys S (Ev Hd B) R) (l : List (Ev Hd B)) (i : Nat) (r : R) : Option Bool :=
(l[i]?).map (sys.check r (stateFrom sys sys.init l i))
/-- `p` can decide rule `r` at step `i`: the verdict is a function of `p`'s view. -/
def Decides (sys : Sys S (Ev Hd B) R) (reads : P → Hd → Bool) (p : P)
(l : List (Ev Hd B)) (i : Nat) (r : R) : Prop :=
∀ l', view reads p l' = view reads p l → checkAt sys l' i r = checkAt sys l i r
/-- `p` holds the role state at step `i`: that state is a function of `p`'s view. -/
def KnowsState (sys : Sys S (Ev Hd B) R) (reads : P → Hd → Bool) (p : P)
(l : List (Ev Hd B)) (i : Nat) : Prop :=
∀ l', view reads p l' = view reads p l →
stateFrom sys sys.init l' i = stateFrom sys sys.init l i
Theorem 4a (readers who know the state). If reads step and knows the state at , then decides every rule at step .
Theorem 4b (reading the prefix gives the state). If reads every event before step , then knows the state at .
Proof. For 4a, a log with the same view has a step with the same header. Because reads it, the body is the same too, so the event is the same, and the state is the same by assumption. For 4b, equal views with every body visible force equal prefixes of length , and the state is a fold of that prefix. ∎
-- continues the file above
theorem view_at {reads : P → Hd → Bool} {p : P} {l l' : List (Ev Hd B)}
(hv : view reads p l' = view reads p l) {i : Nat} {e : Ev Hd B}
(he : l[i]? = some e) :
∃ e', l'[i]? = some e' ∧ e'.hdr = e.hdr ∧ (reads p e.hdr = true → e' = e) := by
have := congrArg (fun v => v[i]?) hv
simp only [view, List.getElem?_map, he] at this
cases h' : l'[i]? with
| none => rw [h'] at this; simp at this
| some e' =>
rw [h'] at this
simp only [Option.map_some', Option.some.injEq, Prod.mk.injEq] at this
obtain ⟨hh, hb⟩ := this
refine ⟨e', rfl, hh, ?_⟩
intro hr
rw [hh, hr] at hb
simp at hb
cases e; cases e'
simp_all
/-- Theorem 4a: a reader of event `i` who holds the state at `i` decides every rule there. -/
theorem reader_with_state_decides (sys : Sys S (Ev Hd B) R) (reads : P → Hd → Bool)
(p : P) (l : List (Ev Hd B)) (i : Nat) (e : Ev Hd B) (he : l[i]? = some e)
(hr : reads p e.hdr = true) (hk : KnowsState sys reads p l i) (r : R) :
Decides sys reads p l i r := by
intro l' hv
obtain ⟨e', he', _, heq⟩ := view_at hv he
have : e' = e := heq hr
subst this
simp [checkAt, he, he', hk l' hv]
theorem view_nil {reads : P → Hd → Bool} {p : P} {l' : List (Ev Hd B)}
(h : view reads p l' = view reads p []) : l' = [] := by
cases l' with
| nil => rfl
| cons _ _ => simp [view] at h
theorem prefix_eq {reads : P → Hd → Bool} {p : P} :
∀ (l l' : List (Ev Hd B)) (i : Nat), view reads p l' = view reads p l →
(∀ e ∈ l.take i, reads p e.hdr = true) → l'.take i = l.take i
| [], l', i, hv, _ => by rw [view_nil hv]
| e :: es, [], i, hv, _ => by simp [view] at hv
| e :: es, e' :: es', 0, _, _ => by simp
| e :: es, e' :: es', i + 1, hv, hr => by
simp only [view, List.map_cons, List.cons.injEq, Prod.mk.injEq] at hv
obtain ⟨⟨hh, hb⟩, htl⟩ := hv
have hre : reads p e.hdr = true := hr e (by simp)
have heq : e' = e := by
rw [hh, hre] at hb
simp at hb
cases e; cases e'
simp_all
have := prefix_eq es es' i htl (fun x hx => hr x (by simp [hx]))
simp [heq, this]
/-- Theorem 4b: a party that reads every event before step `i` holds the state at `i`. -/
theorem prefix_reader_knows_state (sys : Sys S (Ev Hd B) R) (reads : P → Hd → Bool)
(p : P) (l : List (Ev Hd B)) (i : Nat)
(hr : ∀ e ∈ l.take i, reads p e.hdr = true) : KnowsState sys reads p l i := by
intro l' hv
simp only [stateFrom, prefix_eq l l' i hv hr]
For a party that does not read step there is an exact criterion.
Theorem 4c (non-readers, exact). Suppose and does not read . If decides at , then the verdict does not depend on the body: for every body . If also knows the state at , the converse holds as well, so the two conditions are equivalent.
Proof. Forward: replace the body of step by . The view of does not change, and the prefix before does not change, so neither does . Since decides , the two verdicts agree. Converse: a log with the same view has a step with the same header and some body , and, because knows the state, the same . Body-insensitivity then gives the same verdict. ∎
-- continues the file above
/-- Replace position `i` of a list. -/
def replaceAt {α : Type} : List α → Nat → α → List α
| [], _, _ => []
| _ :: xs, 0, y => y :: xs
| x :: xs, n + 1, y => x :: replaceAt xs n y
theorem replaceAt_take {α : Type} :
∀ (l : List α) (i : Nat) (y : α), (replaceAt l i y).take i = l.take i
| [], _, _ => rfl
| _ :: _, 0, _ => rfl
| x :: xs, n + 1, y => by simp [replaceAt, replaceAt_take xs n y]
theorem replaceAt_get {α : Type} :
∀ (l : List α) (i : Nat) (x y : α), l[i]? = some x → (replaceAt l i y)[i]? = some y
| [], _, _, _, h => by simp at h
| _ :: _, 0, _, _, _ => by simp [replaceAt]
| _ :: xs, n + 1, x, y, h => by
simp only [replaceAt, List.getElem?_cons_succ] at h ⊢
exact replaceAt_get xs n x y h
theorem view_replaceAt {reads : P → Hd → Bool} {p : P} :
∀ (l : List (Ev Hd B)) (i : Nat) (e : Ev Hd B) (b : B), l[i]? = some e →
reads p e.hdr = false →
view reads p (replaceAt l i ⟨e.hdr, b⟩) = view reads p l
| [], _, _, _, h, _ => by simp at h
| x :: xs, 0, e, b, h, hr => by
simp at h
subst h
simp [replaceAt, view, hr]
| x :: xs, n + 1, e, b, h, hr => by
simp only [List.getElem?_cons_succ] at h
have := view_replaceAt xs n e b h hr
simp only [view] at this ⊢
simp [replaceAt, this]
/-- Theorem 4c (non-readers, exact): a party that does not read event `i` decides rule `r`
there iff the verdict does not depend on the body (given the header and state);
the forward direction needs no state assumption, the converse needs `KnowsState`. -/
theorem nonreader_decides_needs_body_insensitive (sys : Sys S (Ev Hd B) R)
(reads : P → Hd → Bool) (p : P) (l : List (Ev Hd B)) (i : Nat) (e : Ev Hd B)
(he : l[i]? = some e) (hnr : reads p e.hdr = false) (r : R)
(hd : Decides sys reads p l i r) :
∀ b, sys.check r (stateFrom sys sys.init l i) ⟨e.hdr, b⟩ =
sys.check r (stateFrom sys sys.init l i) e := by
intro b
have hv := view_replaceAt l i e b he hnr
have := hd _ hv
simp only [checkAt, replaceAt_get l i e ⟨e.hdr, b⟩ he, he, Option.map_some',
Option.some.injEq] at this
rw [stateFrom, replaceAt_take] at this
exact this
theorem body_insensitive_decides (sys : Sys S (Ev Hd B) R) (reads : P → Hd → Bool)
(p : P) (l : List (Ev Hd B)) (i : Nat) (e : Ev Hd B) (he : l[i]? = some e)
(hk : KnowsState sys reads p l i) (r : R)
(hins : ∀ b, sys.check r (stateFrom sys sys.init l i) ⟨e.hdr, b⟩ =
sys.check r (stateFrom sys sys.init l i) e) :
Decides sys reads p l i r := by
intro l' hv
obtain ⟨e', he', hh, _⟩ := view_at hv he
have h1 := hins e'.body
rw [← hh] at h1
simp [checkAt, he, he', hk l' hv, h1]
theorem nonreader_decides_iff (sys : Sys S (Ev Hd B) R) (reads : P → Hd → Bool)
(p : P) (l : List (Ev Hd B)) (i : Nat) (e : Ev Hd B) (he : l[i]? = some e)
(hnr : reads p e.hdr = false) (hk : KnowsState sys reads p l i) (r : R) :
Decides sys reads p l i r ↔
∀ b, sys.check r (stateFrom sys sys.init l i) ⟨e.hdr, b⟩ =
sys.check r (stateFrom sys sys.init l i) e :=
⟨nonreader_decides_needs_body_insensitive sys reads p l i e he hnr r,
body_insensitive_decides sys reads p l i e he hk r⟩
The naive guess is that the parties who can audit an event are exactly the parties who may read it. It fails in both directions. The example system has as its state the list of current writers, initially . A header is (author, kind), where kind is a grant whose body names the new writer and kind is a post. Rule says the author is a current writer. Rule says a post body is below . A party reads an event if it is the author or party .
Theorem 4d (reading is not enough). In the log “party 1 grants writing to party 2, then party 2 posts 5”, party 2 reads step 1 but does not decide rule 0 there. The log in which party 1 grants writing to party 3 instead looks the same to party 2, because the grant body is hidden from it. In that log the author of step 1 is not a writer.
Theorem 4e (reading is not needed). In the log “party 0 grants writing to party 7”, party 3 does not read step 0, but it decides both rules there. The state at step 0 is the initial state, the author 0 is in it whatever the body says, and rule 1 only constrains posts.
-- continues the file above
/-! ### Counterexamples to "auditors = readers"
Headers are `(author, kind)`; kind `0` is a grant whose body names the grantee, kind `1`
is a post. Rule `0`: the author holds write permission. Rule `1`: a post body is `< 100`.
A party reads an event iff it is the author or party `0`. -/
def roleSys : Sys (List Nat) (Ev (Nat × Nat) Nat) Nat where
init := [0, 1]
apply := fun s e => if e.hdr.2 = 0 then e.body :: s else s
rules := [0, 1]
check := fun r s e =>
if r = 0 then s.contains e.hdr.1 else (e.hdr.2 != 1 || decide (e.body < 100))
def roleReads (p : Nat) (h : Nat × Nat) : Bool := p == h.1 || p == 0
def logA : List (Ev (Nat × Nat) Nat) := [⟨(1, 0), 2⟩, ⟨(2, 1), 5⟩]
def logB : List (Ev (Nat × Nat) Nat) := [⟨(1, 0), 3⟩, ⟨(2, 1), 5⟩]
def logC : List (Ev (Nat × Nat) Nat) := [⟨(0, 0), 7⟩]
/-- Theorem 4d: a reader is not enough. Party 2 reads step 1 but cannot decide rule 0
there, because the grant at step 0 is hidden from it. -/
theorem reader_cannot_decide :
roleReads 2 (2, 1) = true ∧ ¬ Decides roleSys roleReads 2 logA 1 0 := by
refine ⟨by decide, ?_⟩
intro h
have := h logB (by decide)
revert this
decide
/-- Theorem 4e: reading is not necessary. Party 3 does not read step 0 of `logC`,
yet decides both rules there. -/
theorem nonreader_can_decide :
roleReads 3 (0, 0) = false ∧
Decides roleSys roleReads 3 logC 0 0 ∧ Decides roleSys roleReads 3 logC 0 1 := by
have hk : KnowsState roleSys roleReads 3 logC 0 := by
intro l' _; simp [stateFrom_zero]
refine ⟨by decide, ?_, ?_⟩ <;>
· apply body_insensitive_decides roleSys roleReads 3 logC 0 ⟨(0, 0), 7⟩ rfl hk
intro b
simp [roleSys, stateFrom_zero]
Together, 4a to 4e answer the auditability question as far as it is answered here. A party that does not read step but knows the state there can audit rule exactly when ignores the body at that step. A reader that knows the state can audit every rule, and reading the whole prefix is one way to know it. Reading alone is not enough, because the permission state can depend on events the reader may not see.
Disclosure
Assumption A4 (zero knowledge, idealised). What the verifier sees of a fraud proof is the pair (claim, accept bit). Nothing about the witness log appears in it.
Theorem 5 (disclosure). If witnesses , the transcript is . So two witnesses for the same claim give the same transcript, and the transcript depends only on .
Proof. The decidable form of the relation is true exactly on witnesses (relB_iff), and the transcript is defined as the claim paired with that bit. ∎
This theorem holds by definition once A4 is assumed. Its content is the choice of public statement. The claim names the head, the step and the rule, but no event body and no state. It still discloses something. It tells everyone that step breaks rule , and together with the public header of step it also says who authored the faulty step.
-- continues the file above
/-! ## 5. Disclosure (ideal zero-knowledge functionality) -/
/-- Decidable form of the fraud-proof relation. -/
def relB [DecidableEq D] [DecidableEq R] (sys : Sys S E R) (hm : HashModel D E)
(c : Claim D R) (l : List E) : Bool :=
decide (head hm l = c.head) && decide (c.rule ∈ sys.rules) &&
match l[c.idx]? with
| some e => !sys.check c.rule (stateFrom sys sys.init l c.idx) e
| none => false
theorem relB_iff [DecidableEq D] [DecidableEq R] (sys : Sys S E R) (hm : HashModel D E)
(c : Claim D R) (l : List E) : relB sys hm c l = true ↔ Witnesses sys hm c l := by
unfold relB Witnesses
cases h : l[c.idx]? with
| none => simp
| some e =>
simp only [Bool.and_eq_true, decide_eq_true_eq, Bool.not_eq_true',
Option.some.injEq]
constructor
· intro ⟨⟨h1, h2⟩, h3⟩; exact ⟨h1, e, rfl, h2, h3⟩
· intro ⟨h1, e', he', h2, h3⟩; subst he'; exact ⟨⟨h1, h2⟩, h3⟩
/-- ASSUMPTION (zero knowledge, idealised): the verifier's view of a proof is the public
claim together with the accept bit. -/
def idealTranscript [DecidableEq D] [DecidableEq R] (sys : Sys S E R) (hm : HashModel D E)
(c : Claim D R) (l : List E) : Claim D R × Bool :=
(c, relB sys hm c l)
/-- Theorem 5 (disclosure): the transcript of an accepted proof is `(claim, true)`;
it depends only on `(head, idx, rule)`, not on which valid witness was used. -/
theorem transcript_only_claim [DecidableEq D] [DecidableEq R] (sys : Sys S E R)
(hm : HashModel D E) (c : Claim D R) (l : List E) (hw : Witnesses sys hm c l) :
idealTranscript sys hm c l = (c, true) := by
simp [idealTranscript, (relB_iff sys hm c l).2 hw]
theorem transcript_indep [DecidableEq D] [DecidableEq R] (sys : Sys S E R)
(hm : HashModel D E) (c : Claim D R) (l1 l2 : List E)
(h1 : Witnesses sys hm c l1) (h2 : Witnesses sys hm c l2) :
idealTranscript sys hm c l1 = idealTranscript sys hm c l2 := by
rw [transcript_only_claim sys hm c l1 h1, transcript_only_claim sys hm c l2 h2]
end PrivateLogAudit
Limits and assumptions
What is proved is proved about the idealised model. The following are outside it.
- No computational proofs. A1 to A4 stand in for collision resistance, unforgeability under chosen-message attack, soundness of the proof system and zero knowledge. Nothing here proves a bound on an adversary’s advantage.
- Knowledge soundness in a real instantiation. In the model, an accepted proof only shows that a witness exists. That is enough because A1 makes the head injective. A real hash has collisions, so the head of a valid log may also be the head of some invalid log, and a proof that only shows such a log exists would then convict an honest signer. A real instantiation therefore needs an argument of knowledge, so that an extracted witness together with the honest log yields a collision that was actually found. This is assumed, not shown.
- The head is left out of the view. Theorem 4 measures what a party can infer from headers and readable bodies. The head is deliberately not in the view, because in the symbolic model an injective hash determines the whole log. A deployment should chain hiding commitments to the bodies, not the bodies themselves. Otherwise a body drawn from a small set can be recovered by hashing every candidate. The model does not cover this.
- Who can build a fraud proof. The witness is the whole log, so the prover must know every event up to step . Nothing here shows how a party with a partial view could build a witness, for example from openings of committed state.
- Auditability is exact only for parties who know the state. Readers who know the state decide every rule (4a), and non-readers who know it decide exactly the body-insensitive rules (4c). For parties that do not know the state there is only the counterexample 4d. There is no general characterisation of which parties know the state beyond reading the prefix.
- One log, no forks. “Honest” means every signed head is the head of some valid log. Signing the heads of two different valid logs is not a rule violation here. Detecting such forks needs proofs that one head extends another and a way for parties to compare the heads they saw, and neither is modelled.
- Disclosure of the claim itself. Theorem 5 is definitional under A4, and the claim is public by design.
- No cost model. Being optimistic means proofs are produced only on dispute, but no time, size or round bound is proved.
Prior work
The parts are standard, and the sources below are the ones the components above are drawn from.
- How to Time-Stamp a Digital Document, Journal of Cryptology, 1991: chaining hashes to commit to an ordered history.
- Efficient Data Structures for Tamper-Evident Logging, USENIX Security Symposium, 2009: signed commitments to append-only logs and proofs between them.
- A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM Journal on Computing, 1988: the unforgeability notion idealised as A2.
- On the Security of Public Key Protocols, IEEE Transactions on Information Theory, 1983: the symbolic treatment of cryptographic primitives.
- Role-Based Access Control Models, IEEE Computer, 1996: roles and permissions as the state the rules consult.
- Practical Delegation of Computation Using Multiple Servers, ACM CCS, 2011: proving a computation wrong by pinning down one disputed step.
- The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Computing, 1989: zero-knowledge proofs.
- On Defining Proofs of Knowledge, CRYPTO, 1992: the knowledge-soundness property needed in a real instantiation.
- Universally Composable Security: A New Paradigm for Cryptographic Protocols, FOCS, 2001: security as an ideal functionality, the shape of A4.
- Knowledge and Common Knowledge in a Distributed Environment, Journal of the ACM, 1990: knowledge as truth in every indistinguishable view, the shape of “decides”.
- Security Policies and Security Models, IEEE Symposium on Security and Privacy, 1982: the requirement that one party’s actions leave another’s view unchanged, the idea behind asking what a party’s view does and does not determine.
- Accountability: Definition and Relationship to Verifiability, ACM CCS, 2010: accountability as the property that misbehaviour can be blamed on a party, with no honest party blamed. Theorems 2c and 3 are in the spirit of this notion: misbehaviour is blamed (2c) and an honest signer is never blamed (3).