Research / 2026

Auditing a signed log that not everyone may read

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

A signed, hash-chained log whose rules also limit who may read each event. Validity is a fold over a permission state, a fraud proof about one step convicts the signer and cannot frame an honest one, the parties who can check a step are characterised exactly for those who know the state, and two machine-checked counterexamples show that readers and auditors differ. A zero-knowledge fraud proof discloses only its claim. Everything is proved in an idealised symbolic model and checked in Lean.

Hash chainsFraud proofsAccess controlZero knowledge
1 step
one fraud proof about the first invalid step convicts the signer of an invalid log
2 ways
in which "the auditors of an event are its readers" fails; both counterexamples are machine-checked
(head, i, r)
all that the public statement of a fraud proof reveals

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 reads(p,h)\mathrm{reads}(p, h) says whether party pp may read the body of an event with header hh.

The combination should achieve five things.

  1. Local validity. A log is valid exactly when every step is valid in the state folded from the steps before it.
  2. 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.
  3. No framing. Under the stated assumptions, if the signer only ever signs heads of valid logs, then no fraud proof against it is accepted.
  4. Auditability. For a step ii and a rule rr, say which parties can decide from their own view whether rr accepts step ii.
  5. 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 H(…H(H(g,e0),e1)…,en−1)H(\dots H(H(g, e_0), e_1)\dots, e_{n-1}) for a fixed genesis value gg. 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 pp can decide XX” means XX has the same value in every world that pp 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 rr at step ii”. The verifier checks the proof and the signature on the head. If both pass, the signer is convicted.

  1. append
    event e
    state s := apply s e
  2. sign
    head h
    h := H(h, e)
  3. dispute
    find step i
    check r s_i e_i = false
  4. prove
    claim (h, i, r)
    zero knowledge
  5. verdict
    signer convicted
    signed h ∧ proof ok
Fig. 1The combined protocol. Only the dispute path produces a proof, and the proof is about one step. Its public statement is the triple (head, i, r).

Definitions

Rule system. A rule system is a tuple (s0,apply,R,check)(s_0, \mathrm{apply}, \mathcal R, \mathrm{check}) with an initial state s0s_0, a transition apply:S×E→S\mathrm{apply} : S \times E \to S, a finite list of rules R\mathcal R, and check:R×S×E→B\mathrm{check} : \mathcal R \times S \times E \to \mathbb B. A step ee is valid in state ss when check(r,s,e)\mathrm{check}(r, s, e) holds for every r∈Rr \in \mathcal R. For a log ℓ=e0…en−1\ell = e_0 \dots e_{n-1}, the state before step ii is the fold of the first ii events,

si(ℓ)=apply(…apply(s0,e0)…,ei−1),s_i(\ell) = \mathrm{apply}(\dots \mathrm{apply}(s_0, e_0)\dots, e_{i-1}),

and the log is valid when each eie_i is valid in si(ℓ)s_i(\ell), 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 ss and log ℓ\ell, the log is valid from ss if and only if, for every index ii with ℓ[i]=e\ell[i] = e, the step ee is valid in the state si(ℓ)s_i(\ell).

Proof. Induction on ℓ\ell. The empty log is valid, and it has no indices. For e::ℓ′e :: \ell', validity is ”ee valid in ss, and ℓ′\ell' valid from apply(s,e)\mathrm{apply}(s, e)”. Index 00 gives the first conjunct. Index j+1j+1 of e::ℓ′e :: \ell' is index jj of ℓ′\ell', and sj+1(e::ℓ′)=sj(ℓ′)s_{j+1}(e :: \ell') = s_j(\ell') computed from apply(s,e)\mathrm{apply}(s, e). The induction hypothesis then gives the second conjunct. ∎

Theorem 2a (first invalid step). If ℓ\ell is not valid from ss, there are an index ii, the event e=ℓ[i]e = \ell[i] and a rule r∈Rr \in \mathcal R with check(r,si(ℓ),e)=false\mathrm{check}(r, s_i(\ell), e) = \mathrm{false}, and every step before ii is valid in its own state.

Proof. Induction on ℓ\ell. If the first step is invalid, some rule in the list rejects it, and i=0i = 0 with nothing before it. Otherwise the rest of the log is invalid from apply(s,e)\mathrm{apply}(s, e). The induction hypothesis gives an index ii there, and i+1i + 1 works for the whole log, since step 00 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 gg and a function H:D×E→DH : D \times E \to D. The head of a log is head(ε)=g\mathrm{head}(\varepsilon) = g and head(ℓ⋅e)=H(head(ℓ),e)\mathrm{head}(\ell \cdot e) = H(\mathrm{head}(\ell), e). In Lean this is a chain over the reversed list. The lemma head_snoc states the append equation.

Assumption A1 (collision-free hash, idealised). HH is injective on pairs, and H(d,e)≠gH(d, e) \ne g for all d,ed, e. 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, head(ℓ1)=head(ℓ2)\mathrm{head}(\ell_1) = \mathrm{head}(\ell_2) implies ℓ1=ℓ2\ell_1 = \ell_2.

Proof. Compare the reversed lists by induction. If one is empty and the other is not, one side is gg and the other is a value of HH, 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 c=(h,i,r)c = (h, i, r). A log ℓ\ell witnesses cc when head(ℓ)=h\mathrm{head}(\ell) = h, ℓ[i]=e\ell[i] = e for some ee, r∈Rr \in \mathcal R and check(r,si(ℓ),e)=false\mathrm{check}(r, s_i(\ell), e) = \mathrm{false}. This relation is the statement that the proof system proves.

Assumption A2 (unforgeable signatures, idealised). A predicate signed(h)\mathrm{signed}(h) 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 cc exactly when signed(c.h)\mathrm{signed}(c.h) holds and some log witnesses cc.

-- 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 signed(head(ℓ))\mathrm{signed}(\mathrm{head}(\ell)) and ℓ\ell is invalid, then there are ii and rr such that the claim (head(ℓ),i,r)(\mathrm{head}(\ell), i, r) is accepted, and every step before ii is valid.

Proof. Theorem 2a gives the first invalid step ii and a rejecting rule rr, and ℓ\ell itself witnesses the claim. ∎

Theorem 2c (conviction). If a claim cc is accepted, then there is a log ℓ\ell with signed(head(ℓ))\mathrm{signed}(\mathrm{head}(\ell)), head(ℓ)=c.h\mathrm{head}(\ell) = c.h and ℓ\ell invalid. Under A1, ℓ\ell is the only log whose head is c.hc.h.

Proof. A3 gives a witness ℓ\ell. If ℓ\ell were valid, Theorem 1 would make step c.ic.i valid, so every rule, c.rc.r 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 cc is accepted. Theorem 2c gives an invalid log ℓ\ell with signed head c.hc.h. Honesty gives a valid log ℓ0\ell_0 with head c.hc.h. By the binding lemma ℓ0=ℓ\ell_0 = \ell, so ℓ\ell is both valid and invalid. ∎

Collision-freedom is needed. Let H(d,_)=d+1H(d, \_) = d + 1 with g=0g = 0. This HH never returns gg, but it is not injective. Take one rule, “the event is not 13”. The signer signs only head 11, which is the head of the valid log [0][0], so it is honest. The log [13][13] also has head 11 and violates the rule at step 00, so the claim (1,0,rule)(1, 0, \text{rule}) 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 pp sees every header, and it sees a body only if reads(p,header)\mathrm{reads}(p, \text{header}) holds.

View. viewp(ℓ)\mathrm{view}_p(\ell) is the list of pairs (header, body if pp reads it, otherwise nothing).

Decides. Party pp decides rule rr at step ii of ℓ\ell when every log ℓ′\ell' with viewp(ℓ′)=viewp(ℓ)\mathrm{view}_p(\ell') = \mathrm{view}_p(\ell) gives the same verdict as ℓ\ell for rule rr at step ii. Here the verdict is check(r,si,ℓ[i])\mathrm{check}(r, s_i, \ell[i]), or “no step” if the log is shorter.

Knows the state. Party pp knows the state at ii when every log with the same view has the same folded state sis_i.

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 pp reads step ii and knows the state at ii, then pp decides every rule at step ii.

Theorem 4b (reading the prefix gives the state). If pp reads every event before step ii, then pp knows the state at ii.

Proof. For 4a, a log with the same view has a step ii with the same header. Because pp 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 ii, 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 ii there is an exact criterion.

Theorem 4c (non-readers, exact). Suppose ℓ[i]=e\ell[i] = e and pp does not read ee. If pp decides rr at ii, then the verdict does not depend on the body: check(r,si,(e.hdr,b))=check(r,si,e)\mathrm{check}(r, s_i, (e.\mathrm{hdr}, b)) = \mathrm{check}(r, s_i, e) for every body bb. If pp also knows the state at ii, the converse holds as well, so the two conditions are equivalent.

Proof. Forward: replace the body of step ii by bb. The view of pp does not change, and the prefix before ii does not change, so neither does sis_i. Since pp decides rr, the two verdicts agree. Converse: a log with the same view has a step ii with the same header and some body b′b', and, because pp knows the state, the same sis_i. 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 [0,1][0, 1]. A header is (author, kind), where kind 00 is a grant whose body names the new writer and kind 11 is a post. Rule 00 says the author is a current writer. Rule 11 says a post body is below 100100. A party reads an event if it is the author or party 00.

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 ii but knows the state there can audit rule rr exactly when rr 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 ℓ\ell witnesses cc, the transcript is (c,true)(c, \mathrm{true}). So two witnesses for the same claim give the same transcript, and the transcript depends only on (h,i,r)(h, i, r).

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 ii breaks rule rr, and together with the public header of step ii 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 ii. 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).