arXiv CSopen access

VCT: A Verifiable Transcript System for LLM Conversations

VCT: A Verifiable Transcript System for LLM Conversations Ruilin Xing∗, Feihong Li, Jiayue Liu, Jiali Zheng†, Wei Liu‡, Wanzhi Xie School of Computer Science and Electronic Information, Guangxi University

arXiv:2606.23003v1 [cs.CR] 22 Jun 2026

Abstract Large language model (LLM) interaction records are increasingly vital in digital forensics and compliance auditing. However, traditional linear tamper-evident logs fail to capture the inherent non-linear evolution of LLM conversations, such as re-prompting based on historical queries, response regeneration, session deletion, multi-device concurrency, and selective sharing. To address this issue, this paper proposes Verifiable Conversation Transcript (VCT), which abstracts complex non-linear LLM semantic operations into account-level authenticated state transitions. VCT constructs a three-tier cryptographic data structure: atomic Q&A pairs form branch-level hash chains, branch tails aggregate into session-level Merkle roots, and all session roots are further aggregated into an account-level Merkle root anchored by joint signatures from both the user and the server. VCT introduces a serialized state transition protocol with deletion barriers to eliminate conflicts between deletion and modification, complemented by a deterministic state-merge protocol to preserve concurrent non-deletion incremental operations. Furthermore, incremental denial checks and a gossip protocol enable asynchronous user devices to autonomously detect view forks caused by malicious servers and generate non-repudiable forensic evidence. Security analysis demonstrates that, under standard cryptographic assumptions, VCT guarantees the integrity, consistency, verifiable shareability, and non-repudiation of account-level conversation records. Evaluation of a Python prototype shows that the cryptographic latency of core operations is within sub-millisecond to low-millisecond ranges. Under a realistic configuration with 21 KB of text, security metadata introduces a negligible storage overhead of only 0.9%, validating the deployment feasibility of VCT for high-stakes forensic review on production-grade LLM platforms.

Keywords: large language models; verifiable conversation transcript; hash chain; Merkle tree; digital forensics; integrity; non-repudiation

1

Introduction

Large language models (LLMs) have become widely used tools in high-expertise workflows, including legal consultation, scientific writing, software engineering, and business analysis [1, 2]. In these settings, human–AI conversations are no longer merely transient interaction traces. They increasingly serve as records of reasoning, sources of advice [3], and, in certain jurisdictions, potential legal evidence. Courts, auditors, and regulators have begun to rely on such records to assess intent, attribute responsibility, and review decision-making processes [4, 5, 6]. This shift raises a fundamental question that current AI infrastructure has not adequately addressed: can the integrity and authenticity of LLM interaction records be independently verified? Recent legal disputes make this question practically urgent. Conversation records between users and AI systems have already entered judicial proceedings and have been treated as evidentiary materials. In criminal investigations, the affidavit in United States v. Rinderknecht [7] ∗

Email: [email protected] Corresponding author ‡ Co-corresponding author †

1

cited the defendant’s queries to ChatGPT to infer subjective intent and post-event awareness. In civil lawsuits against AI service providers, the plaintiffs in Garcia v. Character Technologies [8] and Raine v. OpenAI [9] argued that model outputs themselves constituted central factual elements contributing to the alleged harm, and submitted complete conversation records as evidence of product defects and failures to warn. Yet in these cases, the authenticity and integrity of the conversation records ultimately depend on traditional evidentiary mechanisms, such as device seizure, assumptions that platform logs have not been tampered with, or post hoc admissions, rather than any cryptographic guarantee. This fragility stems from a more basic limitation: existing LLM platforms do not provide a reliable mechanism for verifying what content a model actually generated, under which conversational context it was generated, and at what time it was produced.This temporal-anchoring problem has long been studied in the cryptographic timestamping literature [10]. Unlike conventional digital evidence, LLM interaction records lack foundational authenticity guarantees. Screenshots can be easily forged, exported text can be silently edited, and platform-hosted sharing links often refer to mutable server-side state. More fundamentally, modern LLM interfaces allow users to regenerate responses, edit previous prompts, delete historical messages, and explore alternative conversation branches, making the notion of a “true” interaction history itself ambiguous. Even if these representation-level issues were resolved, a deeper systemic limitation would remain. In legal settings, the admissibility of electronic evidence depends on authenticity, integrity, and traceability [5, 11, 12]. Existing LLM systems, however, operate on opaque centralized infrastructure, where service providers unilaterally control how interaction histories are stored and presented. This creates an evidentiary asymmetry: one party may present AI-generated records, while the other lacks a reliable means to determine whether those records are genuine, complete, or selectively constructed. This tension shows that traditional evidentiary mechanisms alone are insufficient for the verification challenges introduced by LLM interaction records. Existing research does not fully address this problem. Tamper-evident secure logs [13, 14, 15, 16] typically provide integrity guarantees for a single linear append-only sequence through chained or aggregated authentication values, but they cannot express legitimate branching, historical edits, deletion operations, or the hierarchical state composed of branches, conversations, and accounts in LLM systems. Merkle trees and authenticated data structures [17, 18, 19] provide compact assertions and inclusion proofs; however, as general-purpose authentication mechanisms, they do not define the state objects or transition semantics specific to LLM conversations. Transparency logs [20, 21] rely on a public auditing model that does not match the privacy boundary of LLM conversations. Their append-only consistency model cannot express leaf updates or replacement by deletion-state roots, and their fork semantics cannot distinguish legitimate user-created conversation branches from malicious server-induced forks. Secure messaging protocols [22, 23] target communication confidentiality, participant authentication, and key-update security. They do not provide account-level transcript proofs for third parties, non-repudiable sharing, or hierarchical conversation-state assertions over Q&A atomic nodes. Verifiable reasoning systems [24, 25, 26] assume that the underlying interaction records are authentic and complete, an assumption that does not hold in practice. Thus, the missing piece is not merely a lack of verification, but the lack of a verifiable assertion over evolving LLM conversation state itself. The core issue is therefore one of problem formulation. The goal is not to build a better logging mechanism, but to construct cryptographic assertions over evolving conversational state, so that any disclosed interaction record can be independently verified against a tamper-evident, account-level global view. To address this challenge,Verifiable Conversation Transcript (VCT) is introduced as a system designed to provide integrity, consistency, verifiable sharing, and non-repudiation for LLM interaction records. Unlike traditional linear logs or symmetric message streams, LLM conversation records ex-

2

hibit multi-level and dynamically evolving structure. At the interaction level, each record is naturally organized as a Q&A pair consisting of a user input, a model response, and associated metadata, requiring a clear atomicity boundary. Within a conversation, users may re-prompt based on historical questions or request regenerated responses, causing the conversation to branch; an integrity mechanism must therefore provide compact assertions over branch states without rewriting the entire history. At the account level, the verification target is no longer a single conversation but the cumulative state of multiple independent conversations, requiring conversation roots to be further aggregated into an account-level assertion. Multi-device concurrency further complicates account-state evolution. Devices may hold different local views before synchronization, and the protocol must distinguish benign concurrent divergence from server-induced account-level view forks while enabling consistency checking and accountability without assuming an honest server. Meanwhile, deletion operations in concurrent settings may conflict with non-deletion updates issued from other devices; the protocol must therefore define serialization rules between deletion and concurrent updates, and maintain a consistent user signing identity across devices. In addition, partial sharing introduces an independent verification requirement. Users often intend to selectively disclose only certain conversation fragments, but server-generated sharing links or exported artifacts may replace, remove, reorder, or omit the content that the user intended to share. Recipients therefore need a verification mechanism independent of the server-rendered view. These characteristics show that making LLM conversation records trustworthy is not merely a problem of single-message or single-conversation integrity, but an account-level state-authentication problem across branches, multiple conversations, concurrency, deletion, and sharing. VCT addresses this account-level state-authentication problem by combining a layered authenticated structure with protocol-defined state transitions. To capture Q&A atomicity, conversation branching, and multi-session aggregation, VCT models each Q&A pair as a hash-chain node, using parent hash to preserve the sequential dependency along the same branch. The tail hashes of all branches within a conversation are aggregated into a conversation-level Merkle root, denoted MTR con. The roots of all conversations under an account are further aggregated into an account-level Merkle root, denoted MTR acc, which is jointly signed by the user and the server to produce a verifiable assertion over the complete account state. To handle multi-device concurrency and deletion semantics, VCT introduces a deterministic state-merge protocol that preserves non-deletion concurrent increments, models conversation deletion as an account-level serialized operation to avoid delete–modify conflicts, and uses a gossip protocol for synchronized devices to exchange signed account roots and detect server-induced account-level view forks. VCT also employs deterministic key derivation to maintain a consistent user signing identity across devices, without depending on the server to synchronize user private keys. For partial sharing, VCT reorganizes the shared nodes into an independent hash chain and requires both the user and the server to sign the chain tail, enabling the recipient to verify the shared content independently of the server. In this way, VCT binds branching, multi-session aggregation, concurrency, deletion, and sharing operations in LLM conversations to a unified account-level verifiable state assertion. Contributions. This paper makes the following contributions. • Verifiable Data Structure for Branching and Multi-Device Conversations. A three-layer authenticated structure—comprising branch hash chains, conversation-level Merkle trees, and an account-level Merkle tree—is introduced to provide a unified representation of state transitions, including Q&A atomic nodes, conversation branches, message appends, new conversation creation, and conversation deletion. This structure progressively binds branch-level interaction histories, conversation-level branch sets, and accountlevel multi-conversation states into a single account root, thereby enabling any disclosed node, branch, or conversation state to be traced back to an account-level verifiable state jointly confirmed by the user and the server. 3

• Multi-Device Concurrent Consistency Protocol with Accountability. An accountlevel state-synchronization protocol is proposed to orchestrate concurrent multi-device interactions. The protocol preserves non-deletion concurrent updates within the same deletion epoch through deterministic state merging, and models conversation deletion as an account-level serialized operation to mitigate delete–modify conflicts. It further incorporates a device-side rejection mechanism for stale incremental replay, preventing a malicious server from returning an outdated state and later replaying omitted increments to evade detection. Finally, a gossip mechanism enables devices to exchange signed account roots over end-to-end encrypted channels, facilitating the detection of forked account views and producing accountable evidence backed by dual signatures. • Verifiable Conversation Sharing Protocol. A sharing mechanism is presented that couples an independent hash chain with dual signatures. A recipient only needs to verify the chain-tail hash and the corresponding signatures to confirm that the shared fragment remains untampered and jointly confirmed by the server and the data owner. Once generated, the sharing snapshot maintains its cryptographic verifiability independently of any subsequent appends, branches, or deletions within the original conversation.

2

Related Work and Insights

The core objective of Verifiable Conversation Transcript (VCT) is to provide account-level integrity, consistency, share verifiability, and non-repudiation for interaction records from human– LLM conversations. Unlike traditional system logs or ordinary message records, an LLM conversation is an evolving account state composed of Q&A nodes, branching relations, deletion states, multi-session aggregation, and multi-device synchronization. VCT must therefore verify not only whether an individual record has been tampered with, but also whether the account state remains consistent across concurrent updates, deletion, and synchronization, and whether fragments derived from that account state have not been replaced, reordered, deleted, or selectively constructed during sharing. This section compares VCT with six lines of related work: tamper-evident secure logs, Merkle trees and authenticated data structures, transparency logs, secure messaging protocols, fork consistency in untrusted storage, and verifiable reasoning.The key question is not whether these techniques can provide local integrity, but whether they can support the system-level semantics required by VCT, including branching LLM conversation structure, account-level cumulative assertions, consistency checking within account privacy boundaries, verifiable sharing, and non-repudiation in forensic settings. VCT draws on hash chains from secure logging, compact assertions and inclusion proofs from Merkle trees and authenticated data structures, signed roots and fork-detection ideas from transparency logs, transcript hashes from secure messaging protocols, and the broader concern for LLM output trustworthiness from verifiable reasoning. However, VCT does not aim to construct a public linear log, nor does it verify the correctness of model reasoning. Instead, it provides an account-level, branching, privacy-bounded verifiable state assertion for LLM interaction histories.

2.1

Tamper-Evident Secure Logs

Tamper-evident secure logs study how to maintain log records for post hoc auditing and forensics on partially untrusted hosts. Schneier and Kelsey [13] proposed a secure audit-log scheme based on hash chains and key evolution, so that even if an attacker compromises the logging host at some point, previously generated log entries cannot be modified or deleted without detection. The central goal of this line of work is to make tampering detectable during later audits, rather than to prevent all attacks. Bellare and Yee [14] further introduced the notion of forward integrity, formalizing the requirement that compromise of the current key should not invalidate 4

the integrity of past log entries, and presented constructions satisfying this property. Holt’s Logcrypt [15] combines forward security with public verification, reducing the dependence of log integrity checking on a private verifier and improving usability in third-party audit scenarios. Ma and Tsudik [16] improved the space efficiency and verifiability of secure logs through techniques such as forward-secure sequential aggregate authentication, focusing on authentication overhead and verification efficiency. Secure logs provide a basic building block for the interaction layer of VCT. In an LLM conversation, a user request and the corresponding model response can be treated as a Q&A atomic node. Each node cryptographically binds the user input, the model output, associated metadata, and the hash of its parent node, so that adjacent nodes along the same branch form a chained dependency. If an attacker modifies the input, output, or metadata of any round, the recomputed node hash will no longer match the parent hash recorded by its successor or the tail hash committed for that branch. Hash chains are therefore well suited to the interaction layer of VCT, where they provide sequential integrity within a single branch. The difference between secure logs and VCT is twofold. At the data-model level, traditional secure logs assume a single linear append-only event sequence. LLM conversations, by contrast, allow users to edit historical prompts or regenerate responses, thereby creating legitimate branches; conversation deletion is also not an ordinary append operation, but a state transition that changes the account state. VCT therefore cannot simply place all interaction records into one linear log. It must instead represent parent–child and derivation relations among different conversation paths at the branch level. At the authentication-granularity level, traditional secure logs typically establish integrity over individual log entries, linear chain states, or aggregated authentication values, using mechanisms such as MACs, hash chains, forward-secure signatures, or sequential aggregate authentication. The authenticated object in VCT is not a single linear log, but a hierarchical state composed of branches, conversations, and accounts. VCT progressively accumulates these states into an account-level Merkle root and requires both the user and the server to sign that root, thereby covering all conversation states under the account with a single account root rather than signing each Q&A node individually. Thus, secure logs offer a useful primitive for local sequential integrity, but they do not capture legitimate branching, deletion states, or account-level assertion semantics in LLM conversations.

2.2

Merkle Trees and Authenticated Data Structures

Merkle trees recursively aggregate hashes of data blocks into a root hash, thereby providing compact commitments and efficient inclusion proofs for large data sets. Merkle’s classic work [17] shows that conventional cryptographic functions can be used to construct digital signature schemes and authentication structures, allowing a verifier to check the relationship between an element and a root commitment without reading the entire data set. Building on this idea, authenticated data structures (ADS) study how data can be stored and queried on untrusted servers, while requiring the server to provide efficiently verifiable proofs for query results. Papamanthou et al. [18] focus on correctness and integrity verification for outsourced databases, while Miller et al. [19] propose general-purpose ADS from the perspective of programming languages and type systems, enabling a broader class of data structures to support authenticated operations and compact proofs. Merkle trees and authenticated data structures (ADS) provide two core capabilities for VCT. First, a Merkle authentication structure can aggregate multiple objects into a single root hash and use a Merkle proof to show that a given object is committed by that root. Crosby and Wallach [27] demonstrate the practical significance of this property for tamper-evident logging: replacing a flat hash-chain traversal with a tree-based aggregation structure reduces inclusionproof size from linear to logarithmic in the number of log entries. For VCT, this means that a verifier can check whether a Q&A node, a branch tail hash, or a conversation root is included in a signed account state with only logarithmic overhead, without reading all conversations under 5

an account. Second, Merkle structures support local recomputation: when a leaf changes, only the authentication path from that leaf to the root needs to be recomputed. VCT uses this structural property to localize the effect of a state transition within the authenticated structure to the affected Q&A node, the branch tail hash, the conversation-level Merkle path, and the account-level Merkle path. However, ADS is a general authentication abstraction. It specifies how to authenticate data-structure states, query results, and update procedures, but it does not define how LLMspecific operations should modify the authenticated state. VCT must prove not only that “a leaf belongs to a root,” but also that a state transition conforms to the legal operation semantics of an LLM conversation system. Concretely, when a user appends a Q&A pair to an existing branch, the branch tail hash is replaced by the new node hash. Since the conversation-level Merkle tree uses branch tail hashes as leaves, this operation updates an existing leaf in the conversation-level Merkle tree and further propagates to the account-level Merkle root. When the user regenerates a response or re-prompts from a historical node, the system does not overwrite the original history; instead, it creates a new branch at the historical node and inserts the new branch tail hash into the conversation-level Merkle tree. When a user creates a new conversation, the new conversation root is inserted into the account-level Merkle tree. When a user deletes a conversation, the system does not simply remove a leaf, but replaces the original conversation root with a deletion-state conversation root, thereby preserving a cryptographic assertion of the pre-deletion state. Thus, Merkle trees and ADS provide the authentication mechanisms required by VCT, but not the complete state semantics of LLM conversations. VCT defines a three-layer state structure on top of these mechanisms: the interaction layer records Q&A nodes and their parent–child relations, the conversation layer aggregates multiple branch tails within a single conversation, and the account layer aggregates all conversation states of a user. This structure represents branch extension, historical editing, response regeneration, new conversation creation, and conversation deletion in LLM conversations as verifiable account-state transitions.

2.3

Transparency Logs

Transparency-log systems combine Merkle trees, signed tree heads, inclusion proofs, and consistency proofs to detect unauthorized modifications to historical records by centralized services. Certificate Transparency (CT) [20] requires TLS certificates to be recorded in a public, auditable, append-only log, allowing clients, monitors, and auditors to verify both certificate inclusion and append-only consistency between log roots observed at different points in time. CONIKS [21] applies similar transparency principles to user-key bindings in end-to-end encrypted communication, enabling end users to efficiently detect whether their key bindings are presented inconsistently by a provider, without relying on global third parties to monitor all entries. Transparency logs provide two main insights for VCT. First, a server-signed root assertion makes it difficult for the server to later deny having published a particular state. Second, root comparison and consistency checking across different clients or devices can reveal equivocation or forked views. The gossip-based detection protocol in VCT adopts this idea in a multidevice setting for a single user. Devices exchange their locally stored account-level Merkle roots together with the corresponding dual signatures from the server and the user. If different devices receive incompatible account states, verifiable fork evidence can be produced based on the signed account roots. However, transparency logs cannot be directly applied to VCT for three reasons. First, their auditing model does not match the privacy boundary of LLM conversations. Certificate entries in CT and key bindings in CONIKS are public or semi-public objects that can be observed and audited by external monitors. In contrast, LLM conversation records contain private information, including user inputs, model outputs, conversational context, and auxiliary file in6

formation. It is therefore impractical to require all users to collectively audit a public log. Consequently, VCT neither exposes complete conversation histories nor places all user records into a single global log. Instead, it constructs account-level Merkle roots within each user’s account boundary and performs consistency checking primarily across devices belonging to the same user. Second, the consistency proofs used in transparency logs differ from the consistency semantics required by VCT. Append-only consistency proofs characterize a prefix-preserving relation in which existing leaves remain unchanged and only new leaves are appended[28]. VCT, however, does not operate on a purely append-only log. To represent branching conversation states, VCT uses the current cumulative tail hash of each branch as a leaf in the conversationlevel Merkle tree. As a result, legitimate interactions in an LLM conversation may not only append new records but also modify authenticated state leaves. For example, when a user appends a new Q&A pair to an existing branch, the current branch-tail hash is replaced by the hash of the newly created node, causing both the conversation-level and account-level Merkle roots to change. Similarly, response regeneration or re-prompting from a historical question introduces new branch leaves, creating a new conversation introduces a new account-level leaf, and deleting a conversation replaces the original conversation root with a deletion-state root. VCT therefore must verify a set of legitimate state transitions defined by LLM conversation semantics, rather than a single notion of append-only consistency. Third, the fork semantics of transparency logs do not directly carry over to LLM conversations. In a linear transparency log, presenting incompatible histories to different observers typically indicates equivocation or a malicious fork. In contrast, a “branch” in an LLM conversation may be the result of legitimate user actions, such as editing a historical prompt or regenerating a response. VCT must therefore distinguish between two fundamentally different phenomena: legitimate branches created by user operations within a conversation and malicious forks caused by a server presenting incompatible account views to different devices of the same user. The former is explicitly represented as a normal state within the three-layer authenticated structure, whereas the latter is detected and attributed through account-level roots, dual signatures, and inter-device gossip verification. Therefore, VCT borrows the notions of signed roots and fork detection from transparency logs, but does not inherit their globally visible, linear append-only logging model.

2.4

Secure Messaging Protocols

Secure messaging protocols primarily focus on authentication, confidentiality, forward secrecy, and key update between communicating parties. The Signal protocol provides end-to-end encryption, message authentication, forward secrecy, and post-compromise security for instant messaging through X3DH key agreement and the Double Ratchet mechanism. Cohn-Gordon et al. [22] conducted a formal security analysis of Signal’s core key agreement and ratcheting construction. Messaging Layer Security (MLS) [23] targets asynchronous group communication, managing member updates using tree-based group state and maintaining a transcript hash within the protocol. It is worth noting that the transcript hash in MLS does not establish a complete log over all application-layer chat messages; rather, it computes a running hash over Proposal and Commit messages that affect group state, thereby binding the group key state to the history of prior protocol updates. The insight these protocols offer for VCT is that system state can be bound to its historical trajectory through running hashes and key-state evolution. In particular, the transcript hash in MLS demonstrates that in dynamic, multi-party, and asynchronous update settings, a protocol can do more than protect individual messages—it can incorporate state transitions themselves into a verifiable history. What VCT borrows from this line of work is precisely this idea of “binding state evolution to a historical assertion.” Nevertheless, the goals and data models of secure messaging protocols differ fundamentally from those of VCT. Signal and MLS are primarily designed for communication confidential7

ity, participant authentication, and key-update security; they do not provide publicly verifiable transcript proofs for courts, auditors, or sharing recipients. Some protocols also emphasize deniability, whereas VCT requires non-repudiation in sharing and forensic settings. Even the MLS transcript hash, which comes closest to binding state to history, binds the evolutionary history of group protocol state rather than long-term verifiable LLM conversation content. Furthermore, in secure messaging protocols, messages are typically sent directly by communicating parties; the basic record unit in VCT, by contrast, is a Q&A atomic node jointly constituted by user input and model output—only after the server generates model output A in response to user input Q does the tuple (Q, A, model config, file aux info, timestamp) enter the record as a complete node. This distinction makes it difficult for secure messaging protocols to directly express the state-transition semantics in LLM platforms that arise from response regeneration, historical editing, conversation deletion, account-level aggregation, and share export. Accordingly, VCT does not compress the entire interaction history into a single running digest analogous to a transcript hash. Instead, it models LLM conversations as a hierarchical account state, with both the user and the server jointly signing the account root. For sharing scenarios, VCT further constructs an independent share chain and signs the share-chain tail. In this way, VCT extends the history-binding ideas of secure messaging protocols into a verifiable integrity, share verifiability, and multi-device accountability mechanism tailored to cloud-based LLM conversations.

2.5

Fork Consistency in Untrusted Storage

The notion of detecting inconsistent views served by an untrusted storage provider has been studied extensively in the distributed systems security literature under the name of fork consistency [29]. SUNDR [30] shows that a network file system can guarantee fork consistency—clients can detect any integrity or consistency violation as long as they eventually exchange their locally observed, signed version structures—whether or not the server is honest. Depot [31] generalizes this guarantee to a Byzantine cloud-storage setting via Fork-Join-Causal consistency, tolerating faulty clients in addition to a faulty server. VCT’s gossip-based fork detection follows the same high-level principle as SUNDR/Depot— divergent views are made detectable through the cross-exchange of signed, comparable digests. However, VCT differs in object granularity and trust topology: SUNDR/Depot authenticate a single shared file-system or key-value namespace across multiple mutually distrusting users, whereas VCT authenticates a hierarchical, branching account state across multiple devices of the same user, and must additionally distinguish legitimate conversation branching from serverinduced forks, a distinction that has no counterpart in the file-system fork-consistency model.

2.6

Verifiable Reasoning vs. Verifiable Interaction

An important line of recent research on LLM trustworthiness focuses on verifying the model’s reasoning process. Lightman et al. [24] compare outcome supervision with process supervision, training process-reward models using step-level human feedback to improve the reliability of complex mathematical reasoning. Ling et al. [25] propose a framework for deductive verification of chain-of-thought reasoning, improving the rigor and inspectability of intermediate steps through a more structured natural-language reasoning format. Jacovi et al. [26] introduce the REVEAL benchmark for evaluating the fine-grained judgment capabilities of automatic verifiers on relevance, evidence attribution, and logical correctness within reasoning chains, and observe that existing verifiers still face substantial difficulties in detecting errors in such chains. This body of work addresses the question of whether the reasoning produced by a model is correct, or whether intermediate reasoning steps are verifiable. While these contributions are important for improving the reliability of LLM outputs, they rest on an implicit assumption: that the prompts, responses, and reasoning traces being verified are authentic, complete, 8

and untampered. In the context of legal forensics, auditing, and accountability tracing, this assumption does not always hold. Users may edit exported text, selectively excerpt favorable fragments, modify context, or forge screenshots; servers may return stale states, omit certain branches, present different account views to different devices, or replace, reorder, or delete content in sharing links and exported files. Even if a reasoning chain is logically verified, reasoning verification alone cannot support evidentiary authenticity and completeness if the underlying interaction record does not faithfully reflect what actually occurred. Put differently, the validity of reasoning verification depends on the authenticity of the interaction record—a precondition that existing work on verifiable reasoning does not guarantee. A distinction is therefore drawn between verifiable reasoning and verifiable interaction, one that echoes broader work in the field of verifiable computation [32], where execution correctness and input authenticity are treated as two independent concerns. Specifically, verifiable reasoning is concerned with whether a model reaches sound conclusions given a specified input and reasoning trace—that is, it verifies the content of reasoning. Verifiable interaction is concerned with whether a given input, model output, context, and conversational state have indeed been incorporated into a signed, untampered historical assertion—that is, it verifies the interaction trace itself. VCT operates at the level of verifiable interaction: it does not directly assess whether model answers are correct, nor does it certify the faithfulness of the model’s internal reasoning. Instead, it provides a more foundational evidentiary basis, enabling third parties to verify that a disclosed LLM conversation originates from a confirmed account state and has not been tampered with, reordered, omitted, or substituted in the course of disclosure. Verifiable interaction can serve as a prerequisite for verifiable reasoning. If prompts, responses, or contextual records can be arbitrarily edited or selectively disclosed, then even a reasoning verifier that judges a given chain to be formally correct cannot confirm that the chain corresponds to a human–AI interaction that genuinely took place. Through node-level hashing, conversation-level branch assertions, account-level dual signatures, and a verifiable sharing mechanism, VCT binds the objects subject to reasoning verification to an inspectable interaction history. The two are not alternatives but operate at different layers: VCT guarantees the authenticity and completeness of interaction records, while verifiable reasoning builds upon this foundation to further evaluate the correctness of model outputs and reasoning processes. Related Work Summary Existing work collectively provides several technical building blocks required by VCT. Tamperevident secure logs contribute ideas of sequential integrity, forward integrity, and post hoc auditing, but their linear append-only model and linear chain-based authentication objects cannot express the legitimate branching, historical editing, deletion-state operations, and account-level hierarchical state found in LLM conversations. Merkle trees and authenticated data structures provide compact assertions, inclusion proofs, and local update capabilities; however, as generalpurpose authentication mechanisms, they do not define the state objects or state-transition semantics specific to LLM conversations. Transparency logs contribute ideas of signed roots, consistency proofs, and fork detection, but their public, linear, append-only log model is incompatible with the privacy boundaries of LLM conversations and cannot directly express the state consistency required by VCT, which encompasses leaf updates, new-leaf appends, and deletionstate replacements; moreover, their fork semantics cannot distinguish user-created legitimate branches from server-induced malicious forks. Secure messaging protocols contribute transcript hash techniques and experience with asynchronous state evolution, but their primary goals are communication confidentiality, participant authentication, and key-update security, rather than account-level transcript proofs, non-repudiable sharing, or hierarchical conversational-state assertions over Q&A atomic nodes.Fork-consistency protocols for untrusted storage [29, 30, 31] contribute the technique of detecting divergent views through the cross-exchange of signed, comparable digests, but they authenticate a flat file-system or key-value namespace shared by mutually distrusting clients, rather than a hierarchical, branching account state belonging to a

9

single user, and therefore do not need to distinguish legitimate intra-account branching from server-induced forks, a distinction central to VCT’s gossip protocol. Research on verifiable reasoning addresses whether model reasoning steps are correct, but does not certify whether the underlying interaction records are authentic, complete, and untampered. VCT systematically reconstructs these technical foundations for the LLM conversation setting. At the data-structure level, VCT employs branch hash chains, a conversation-level Merkle tree, and an account-level Merkle tree, rather than a single linear log or a flat global log. At the signing granularity level, VCT applies dual signatures to the account-level Merkle root and the share-chain tail, rather than signing each Q&A node individually. At the audit-model level, VCT does not rely on all users jointly auditing a public log; instead, it performs multi-device consistency checking within account privacy boundaries. At the forensic-semantics level, VCT explicitly distinguishes user-operation-induced legitimate branches from server-induced malicious forks—where the server presents incompatible states to different devices—and supports independent third-party verification of the authenticity, completeness, and non-repudiation of disclosed fragments through its verifiable sharing mechanism. Table 1: Related Techniques and Their Limitations for VCT Related tion

Direc-

Primary Problem Addressed

Applicable Mechanism

Why Cannot Be Directly Applied to VCT

Secure Logs [13, 14, 15, 16]

Tamper-evidence, forward integrity, post-hoc auditing for linear logs

Hash chains, public verification, aggregate authentication

Assumes a single linear append-only event sequence; cannot express legitimate branching, historical editing, or deletion in LLM conversations. The authenticated object is typically a single log entry, linear chain state, or aggregated authentication value, rather than the hierarchical state of branches, conversations, and accounts.

Merkle / ADS [17, 18, 19]

Compact assertions, inclusion proofs, query authenticity for untrusted storage

Merkle root, Merkle proof

Provides a general-purpose authentication abstraction, but its interface does not include LLM-specific state semantics, such as when a branch tail hash is updated, how a new branch is added, how a conversation root propagates to the account root, or how a pre-deletion conversation root is replaced by a deletion-state root.

Transparency Logs [20, 21]

Append-only records, inclusion/consistency proofs, fork detection for public objects

Signed tree head, consistency proof, root gossip

Public or semi-public auditing does not match the privacy boundary of LLM conversations. Append-only consistency proofs cannot express leaf updates or deletion-state replacements. Fork semantics cannot distinguish user-created legitimate branches from server-induced malicious forks. Continued on next page

10

Table 1: Related Techniques and Their Limitations for VCT (continued) Related tion

Primary Problem Addressed

Applicable Mechanism

Why Cannot Be Directly Applied to VCT

Secure Messaging Protocols [22, 23]

End-to-end communication security, key updates, group state consistency

Transcript hash

Does not provide third-party-verifiable account-level transcript proofs or non-repudiable sharing. The transcript hash primarily binds the evolution of protocol state rather than the hierarchical account state of LLM conversation content. Does not define LLM-specific state-transition semantics such as regeneration, historical editing, conversation deletion, multi-session aggregation, or share snapshots.

Fork Consistency [29, 30, 31]

Detecting divergent views and equivocation served by an untrusted storage provider to mutually distrusting clients

Signed version structures, cross-client digest exchange, fork-consistency guarantee

Authenticates a flat, shared file-system or key-value namespace across multiple distinct users, rather than a hierarchical, branching conversation state belonging to a single user across devices. Defines no notion of legitimate intra-account branching (e.g., response regeneration, historical editing) that must be distinguished from server-induced forks, and provides no deletion-state semantics or account-level aggregation across multiple independent conversations.

Verifiable Reasoning [24, 25, 26]

Verifying reasoning steps, process supervision, CoT verifier evaluation

—

Assumes that underlying interaction records are authentic and complete, an assumption that does not hold in practice.

3

Direc-

Preliminaries and Problem Definition

This section establishes the formal foundations of VCT. Notation and participants are first defined, followed by the core storage abstraction model underlying the protocol. The underlying cryptographic primitives and security assumptions are then detailed, and the threat model and security objectives are subsequently formalized. Collectively, these elements provide a unified formal basis and a precise problem boundary for the subsequent protocol design and security analysis.

3.1

Notation and Tools

The following notation is adopted throughout the remainder of this paper.

11

Table 2: Notation and Description Notation

Description

Hash(X) hashtail

Cryptographic hash value of X. Final cumulative hash value of each branch hash chain within the same conversation. Hash value of the parent node in a hash chain. Conversation-level Merkle root; constructed from the hashtail of all branches in the same conversation as leaves. Deletion-state conversation root, defined as old MTRdel con = Hash("DEL SESSION"∥MTRcon ∥timestampdel ). Account-level Merkle root; constructed from MTRcon or MTRdel con of all conversations belonging to the same user as leaves. Digital signature generated on message Z using the private key skx of entity x. User’s signature on the account-level state root, typically STRuacc ← SIGNsku ("ACCOUNT STATE"∥MTRacc ∥timestamp). Server’s signature on the account-level state root, typically STRsacc ← SIGNsks ("ACCOUNT STATE"∥MTRacc ∥timestamp). LLM model configuration parameters, including at least modelid , nonce, temperature, and may include other parameters that ensure deterministic output. Composite data object containing uploaded files and their auxiliary information. User input prompt. Response generated by the LLM model based on the user prompt. User root key, used to derive user signing private key and multi-device communication keys. Asymmetric signing private keys of user u and server s, respectively. Asymmetric signing public keys corresponding to sku and sks , respectively. Ordinary timestamp used for temporal anchoring of node creation, state signing, and protocol events. Timestamp of conversation deletion operation. Signature timestamp bound to STRuacc returned by the server during ”update conversation record”. Timestamp when a device initiates an ”update conversation record” operation. Timestamp of an incremental node, used for incremental freshness checking. Timestamp bound to the account state signature, used to verify the account state anchored by STRsacc and STRuacc . Timestamp of share snapshot generation, used to generate and verify sharessig and shareusig . Tail of the independent hash chain used for sharing. Signature generated by entity x on sharetail during sharing, where x ∈ {u, s}. A deterministic key-derivation algorithm that maps a high-entropy seed seed u to a user public/private signing key pair (sku , pku ). User login password. User key seed, derived from Ku and pwdu via KDF, used to deterministically generate the user signing key pair. Gossip communication key derived from Ku and pwdu using a KDF with domain separation label "gossip encryption". Set of Merkle authentication paths used in the protocol to prove that a relevant node, branch tail, or conversation root is anchored to the corresponding signed Merkle root during conversation update or sharing verification. The locally persisted account-level Merkle root that the user’s device submits to the server as the state-transition baseline for an update or sync request.

hashparent MTRcon MTRdel con MTRacc SIGNskx (Z) STRuacc STRsacc modelconfig

file aux info Q A Ku sku , sks pku , pks timestamp timestampdel timestampsig timestampupdate timestampnode timestampacc timestampshare sharetail sharexsig DeriveKeyPair(·) pwdu seedu Kgossip MerkleProofs

MTRbase acc

Continued on next page

12

Table 2: Notation and Description (continued) Notation

Description

MTRcurrent acc MTRold con

Server’s current account-level Merkle root at the time of request processing. Conversation-level Merkle root before conversation deletion.

The following participants are involved in this paper. Table 3: Participants and Description Participant

Description

User

The same user, who may own multiple devices and concurrently initiate conversations with the LLM. Generates responses to user prompts and participates in conversation state storage, signing, and synchronization. Logically, it can be separated into a model inference service and a conversation storage service. Third-party entity used to verify the integrity of LLM conversation records and associated proofs. Recipient, i.e., the party who views the shared conversation records.

LLM Model Server

TP R

Based on the above notation and participant definitions, the system state and storage model of VCT is further described below.

3.2

System State and Storage Model

VCT targets LLM conversation systems built on a typical client-server (B/S) architecture, placing the persistent maintenance of complete conversation state on the server side while requiring user devices to retain only the minimal local state necessary for state verification and signature confirmation. The server maintains the committed state for each account, comprising Q&A nodes, branch structures, the conversation-level Merkle root MTRcon , deletion-state records del (MTRold con , MTRcon , timestampdel ), and the current account anchor (MTRacc , timestampacc , s u STRacc , STRacc ). To support device synchronization, deterministic merging, and state traceability, the server additionally maintains a complete MTRacc state-transition chain or an equivalent incremental log, and records the last confirmed account anchor and synchronization boundary (timestampsig , timestampupdate ) for each device. Merkle intermediate nodes do not constitute semantic state that the protocol requires to be persistently stored; they may be retained as a server-side performance cache to support incremental Merkle updates and authentication path generation. In the absence of such a cache, the server can still reconstruct the relevant paths or root values from the underlying conversation state. User devices are not required to retain complete conversation records, branch trees, or Merkle intermediate nodes over the long term. Instead, each device retains only the most recently verified account anchor, namely (MTRacc , timestampacc , STRsacc , STRuacc ), together with the server public key pks , the synchronization boundary (timestampsig , timestampupdate ), and local key material Ku , salt, and iterations. The user signing private key sku and the gossip communication key Kgossip may be derived on demand or stored securely. Accordingly, during a conversation update, a user device does not recompute MTRacc from a complete local account state, nor does it rely on a full account view pushed by the server. Instead, it treats the locally stored MTRacc and its dual signatures as the account anchor, and verifies the legitimacy of the state transition against the update payload and MerkleProofs returned by the server.

13

Table 4: Storage Parties and Their Stored Content Storage Party

Stored Content

Persistence

Server

Q&A nodes, branch structures, and conversation-level Merkle root MTRcon del Deletion-state records (MTRold con , MTRcon , timestampdel ) Current account-level Merkle root MTRacc and dual signatures (STRsacc , STRuacc ) User public key pku and server signing private key sks Complete MTRacc state-transition chain or incremental log Last confirmed account root and synchronization boundary (timestampsig , timestampupdate ) for each device Merkle intermediate nodes Most recently verified MTRacc and dual signatures (STRsacc , STRuacc ) on the device Device synchronization boundary (timestampsig , timestampupdate ) Server public key pks Local key material Ku , salt, iterations User signing private key sku and gossip communication key Kgossip

Persistent

Server Server Server Server Server

Server User device User device User device User device User device

3.3

Persistent Persistent Persistent Persistent Persistent

Ephemeral Cache Persistent Persistent Persistent Persistent Derivable on demand or stored securely

Cryptographic Preliminaries and Assumptions

VCT is constructed from standard cryptographic primitives. Public keys used for verification are assumed to be authentically bound to their claimed identities. Unless stated otherwise, adversaries are modeled as probabilistic polynomial-time (PPT) algorithms. Hash Function. Let Hash(·) denote a cryptographic hash function. It is assumed that Hash(·) satisfies collision resistance and second-preimage resistance. VCT uses hash values to bind protocol objects and their dependencies for integrity. Under these assumptions, any modification to authenticated content results in a change to the corresponding hash value, except with negligible probability. To prevent semantic ambiguity across distinct protocol objects, explicit domain-separation tags are incorporated into the relevant hash inputs. Merkle Authentication Structure. VCT employs Merkle trees as an authenticated set structure. Assuming the underlying hash function satisfies collision resistance, a Merkle root serves as a compact authenticated commitment to a set state, and a Merkle inclusion proof reliably establishes that a given object is committed under the corresponding root. Merkle trees provide only set authentication and membership proofs; the legitimacy of state transitions is governed by the specific protocol definitions given in subsequent sections. Digital Signature. Let σ ← Sign(skx , m) denote the digital signature produced by principal x over message m using private key skx , and let Verify(pkx , m, σ) denote the corresponding verification algorithm. The signature scheme is assumed to satisfy existential unforgeability under chosen-message attacks (EUF-CMA)[33]. VCT uses signatures to confirm protocol outputs such as account states and sharing snapshots. Under this assumption, an adversary cannot forge a valid signature on any message that has not been signed by the corresponding party, and any modification to the content of a signed message causes verification to fail.

14

Key Derivation. VCT assumes the availability of a secure key derivation function KDF(·). Authenticated Inter-Device Channel. Devices belonging to the same user are assumed to be able to establish authenticated and encrypted channels. Such channels provide confidentiality, integrity, and communicating-party authentication for account states and associated metadata exchanged across devices. The primitives and security assumptions above constitute the cryptographic foundation of VCT. Subsequent sections present the protocol construction on this basis and formally analyze its security properties, including account-state integrity, multi-device consistency detection, share verifiability, and non-repudiation.

3.4

Threat Model and Security Goals

LLM conversation records differ fundamentally from conventional streaming session logs. Interactions between a user and an LLM exhibit a strict Q&A pairing structure: each prompt Q corresponds to exactly one response A. A (Q, A) pair is treated as a complete node and committed to the data structure only after the server successfully returns the corresponding response A; if the server fails to return a valid response, the prompt Q does not enter the persistent record and no verifiable state transition is formed. 3.4.1

Threat Model

Both the user and the server are assumed to be capable of deviating from the protocol, while the underlying cryptographic primitives are assumed to satisfy standard security assumptions. The threat sources considered in this work fall into the following four categories. 1. User Framing the Server. A malicious user may selectively disclose conversation content or fabricate contextual dependencies in order to attribute erroneous outputs to the server, or may attempt to repudiate previously confirmed conversation states and sharing snapshots. 2. Server Tampering with Conversation Records. A malicious server may forge, delete, or modify user inputs, model outputs, associated metadata, or historical account states. 3. Inconsistent Multi-Device Views. In a multi-device setting under the same account, a malicious server may present incompatible account states to different devices belonging to the same user, or may return a stale but previously valid MTRacc when a device initiates a synchronization update, and subsequently deliver omitted increments to evade consistency detection. 4. Tampering with Sharing Links or Exported Content. Since sharing links, PDFs, and other export packages may be generated by the server, a malicious server may substitute, reorder, delete, or omit Q&A content that the user originally intended to share during the generation process, leaving the recipient R unable to determine the completeness and authenticity of the disclosed content solely from the exported artifact. This work does not address model-parameter-level unlearning, training-data deletion, hardwarebacked key storage, key revocation and rotation, or cross-device key-compromise recovery. These concerns are orthogonal and may be addressed in conjunction with the mechanisms proposed here, but fall outside the scope of the security goals of this work. 3.4.2

Security Goals

In response to the threat model above, the following four categories of security goals are defined and targeted. 15

1. Integrity. • Node-level integrity: The content of an individual Q&A node cannot be tampered with without detection. Any modification breaks the parenthash hash-chain invariant or alters the branch hashtail , propagating the change to MTRacc . • Conversation-level integrity: The set of all branches within a conversation cannot be added to, deleted from, or modified without detection. Any change to a branch alters MTRcon , which propagates to MTRacc . • Account-level integrity: The set of conversations within an account cannot be added to, deleted from, or modified without detection. Any change to a conversation alters MTRacc , which is anchored by both STRsacc and STRuacc through dual signatures. 2. Consistency. • Update authenticity: Account-state updates resulting from user interactions on any device can be verified through the update payload and MerkleProofs returned by the server, confirming that the post-update account state MTRt+1 acc claimed by the server was derived from the local anchor MTRtacc via a legitimate state transition. • Deletion serialization and deletion-epoch consistency: DeleteSession is modeled as an account-level serialized state transition that must be submitted against the server’s current latest account root; non-deletion updates must be submitted against an account state that has already witnessed the latest deletion. This prevents undecidable merge semantics between deletion states and concurrent non-deletion updates. • Merge determinism: The merge mechanism for non-deletion updates across multiple devices satisfies inclusiveness, determinism, and conflict-free preservation; concurrent modifications within the same conversation are retained as branches. Merge results are confirmed by dual signatures from both parties. • Incremental-replay rejection and gossip accountability: Before accepting and signing the server-returned concurrent merge result, each device performs an incrementalfreshness check to prevent the server from first returning a stale account state during an update and subsequently delivering omitted increments during synchronization to evade view-consistency detection. After all devices complete synchronization and gossip, they should converge to the same account state; if the server provides inconsistent account views, VCT enables the user side to produce verifiable fork evidence for accountability. 3. Share Verifiability. • Sharing package authenticity: Shared Q&A nodes must first be proven, via MerkleProofs, to be anchored to a signed MTRacc . • Sharing snapshot integrity: Shared content is reorganized into an independent hash chain and confirmed by dual signatures from both the sharer and the server. The recipient R can detect any substitution, reordering, deletion, or omission of shared content by recomputing the hash chain and verifying the dual signatures. Subsequent updates or deletions to the original conversation do not affect the verifiability of an already-generated sharing package. 4. Non-repudiation. • Server non-repudiation: The server’s signature STRsacc over MTRacc and its signature sharessig over the independent share-chain tail sharetail are non-repudiable. 16

• User non-repudiation: The user’s signature STRuacc over MTRacc and shareusig over the independent share-chain tail sharetail are non-repudiable. • Operation-content non-repudiation: All signatures are directly bound to operation outcomes (MTRacc or sharetail ); any malicious modification causes signature verification to fail.

4

Proposed Verifiable Conversation Transcript System

4.1

Verifiable Three-Layer Data Structure

LLM conversations exhibit a strict Q&A pairing structure; accordingly, a single user request together with its corresponding model response is treated as an atomic node for storage purposes. Each node contains the following fields. Table 5: Node Fields and Description Node Field

Description

hashparent

Hash value of the parent node in a hash chain, used to form the hash chain. The prompt submitted by the user. The response returned by the LLM. Model determinism parameters, including modelid , nonce, temperature, and related fields. A composite data object comprising uploaded files and their associated auxiliary information. Node creation timestamp.

Q A modelconfig file aux info timestamp

Figure 1: Hash chain structure of Q&A nodes in the interaction layer The node hash is defined as: nodehash = Hash(hashparent ∥Q∥A∥modelconfig ∥file aux info∥timestamp). Each node explicitly stores only its parent hash hashparent and does not additionally store its own nodehash ; the hash of a node is carried by the hashparent field of its child. The hashparent of the initial node in a conversation is set to the all-zero value, and the tail hash hashtail of a branch node is recomputed on demand as needed. This design trades a single hash computation 17

for a reduction in global storage overhead without affecting the trustworthiness of hashtail , since hashtail participates as a leaf in the next-layer Merkle tree assertion at every state update. Intermediate hash nodes in the Merkle tree store only intermediate values of the form Hash(hi ∥hj ). The conversation-level root MTRcon is constructed from the hashtail values of all branches within the same conversation, and the account-level root MTRacc is constructed from the MTRcon values of all conversations under the same account. Because users may regenerate a response A or re-edit a prompt Q, conversation records naturally give rise to branching. A linear hash chain cannot fully represent this structure; the system therefore adopts a three-layer verifiable storage structure. Layer 1: Hash-Chain Layer. Each Q&A pair constitutes a node, and nodes are linked via hashparent pointers. When a Regenerate or EditQ operation is performed, the original hash chain forks into multiple independent branches at the point of divergence. All branches share the assertion established before the fork and extend independently thereafter. The branch-tail assertion is defined as:

hashtail = nodehashn = Hash(hashparentn−1 ∥Q∥A∥modelconfig ∥file aux info∥timestamp). Layer 2: Conversation Layer. The hashtail values of all branches within the same conversation are used as leaves to construct a conversation-level Merkle tree whose root is MTRcon . Layer 3: Account Layer. The MTRcon values of all conversations under the same account are used as leaves to construct an account-level Merkle tree whose root is MTRacc . The account root is signed separately by the user and the server: STRsacc ← SIGNsks ("ACCOUNT STATE"∥MTRacc ∥timestamp), STRuacc ← SIGNsku ("ACCOUNT STATE"∥MTRacc ∥timestamp). Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Each branch-level node is hashed sequentially to form a chain.

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

hashtail

H12=Hash h1||h2

（

H12=Hash h1||h2

）

（

MTRcon

H12=Hash h1||h2

）

（

MTRcon

H34=Hash h3||h4

）

（

）

Each branch-level serves as a leaf node in the construction of the session-level Merkle tree

MTRcon

Each session-level Merkle tree root serves as a leaf node in the construction of the account-level Merkle tree

H12=Hash (h1||h2)

MTRcon

MTRacc

Figure 2: Three-Layer Authenticated Data Structure of VCT The account-level Merkle root MTRacc and the corresponding user and server signatures STRuacc and STRsacc are publicly anchored.

18

4.2 4.2.1

VCT System Modules Key Generation and Device Registration

To support authenticatable multi-device interaction and conversation-record signing, the system adopts a deterministic key derivation scheme. 1. User Key and Multi-Device Consistency. Each user is associated with a highentropy root key Ku , which is generated by the user from a random source at account initialization and stored securely on a trusted user device. The user additionally holds a login password pwdu . The user key seed is derived jointly from Ku and pwdu via a key derivation function [34]: seedu ← KDF(Ku , pwdu , salt, iterations, "user signing", key len), where Ku is the root key generated and securely retained by the user; pwdu is the login password known only to the user; salt is stored on the user side together with Ku ; iterations denotes the number of slow-stretching iterations; "user signing" serves as a domain-separation tag; and key len specifies the byte length of the KDF output seed. The signing key pair is subsequently derived from this seed: (sku , pku ) ← DeriveKeyPair(seedu ). This stateless derivation mechanism allows all devices holding the same Ku and pwdu to derive identical sku and pku , thereby eliminating the need for device-specific key registration and explicit key synchronization. Signatures produced by any device can be verified under the same user public key, and a verifier need only maintain a single public key per user. The user employs sku to produce account-level and share-level signed assertions: STRuacc ← SIGNsku ("ACCOUNT STATE"∥MTRacc ∥timestamp), shareusig ← SIGNsku ("SHARE SNAPSHOT"∥sharetail ∥timestamp). 2. Server Key Generation. A long-term key pair (sks , pks ) is generated at system initialization. The server uses sks to sign the account states and sharing data it publishes: STRsacc ← SIGNsks ("ACCOUNT STATE"∥MTRacc ∥timestamp), sharessig ← SIGNsks ("SHARE SNAPSHOT"∥sharetail ∥timestamp). These signatures provide publicly verifiable and non-repudiable assertions over the data published by the server. 3. New Device Registration. When a new device joins, it obtains the user root key Ku and the key derivation parameters from an existing trusted device via a secure out-of-band channel such as a QR code, while the login password pwdu is entered locally on the new device by the user. The new device then computes: seedu ← KDF(Ku , pwdu , salt, iterations, "user signing", key len), (sku , pku ) ← DeriveKeyPair(seedu ). In this process, pwdu is never transmitted between devices; consequently, intercepting Ku alone or compromising pwdu alone is insufficient to derive sku .

19

4.2.2

Conversation State Update

Conversation updates are modeled as deterministic state transitions. Each time a user initiates an update, the server computes the next state statet+1 from the current account state statet and recomputes the account-level Merkle root MTRacc . The system supports four classes of operations: • NewSession: A new independent hash chain is initialized, and the new conversation root is inserted into the account-level Merkle tree. • Append: A new Q&A node is appended to the tail of an existing branch within a conversation, and the corresponding hashtail is updated. • Branch: A new branch is created from an already-authenticated historical node, for instance when regenerating response A or re-editing prompt Q. • DeleteSession: The target conversation is replaced by a deletion-state conversation root; its plaintext content is hidden or removed in accordance with applicable legal requirements, a behavior that constitutes a storage-layer policy and does not alter the definition of the authenticated state transition. All of the above operations are completed through a unified confirmation protocol. Algorithm 1 integrates server-side state transition, proof generation, user-side proof verification, dual-party signing, and final storage into a single procedure. The server first checks whether the baseline account root submitted by the device constitutes a legitimate starting point for the current state transition; upon a successful check, it executes the corresponding state transition. The server then generates update payload and MerkleProofs from the pre- and post-transition account states and signs the new account root. The user device, using the local account anchor as its baseline, verifies the state-transition proof against the update payload and MerkleProofs, and performs a receive-side freshness check where required. Upon successful verification, the user produces a signature over the same account root, and the server finally verifies the user signature and commits the new account state. The specific conditions checked are determined by the operation type and synchronization scenario. The following presents the four basic state transitions: NewSession, Append, Branch, and DeleteSession. Case 1: New Session Creation. Upon creating a new session, the system generates an initial Q&A node whose parent hash is set to the all-zero value; the node hash serves as the hashtail of the new branch. This hashtail is used to construct a new conversation-level root MTRcon , which is then inserted as a new leaf into the account-level Merkle tree. This process corresponds to a leaf-append operation on the account-level Merkle tree. Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

（

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

H12=Hash h1||h2

）

（

MTRcon

Account state updated

（

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

（

MTRcon

H12=Hash h1||h2

）

（

MTRcon

H12=Hash (h1||h2)

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

Q&A node hashtail

Q&A node

Q&A node hashtail

H34=Hash h3||h4

）

Q&A node

H12=Hash h1||h2

）

（

MTRcon

H34=Hash h3||h4

）

（

）

MTRcon

H12=Hash (h1||h2)

MTR_con

H34=Hash (h3||h4)

MTRacc MTRacc

Figure 3: Account-State Transition for New Session Creation 20

Q&A node hashtail

Algorithm 1 VerifiedConversationUpdate 1: Input: op ∈ {NewSession, Append, Branch, DeleteSession, Merge}; anchort = (MTRacct , STRsacct , STRuacct ); sync boundary = (timestampsig , timestampupdate ); 2: Output: statet+1 , MTRacct+1 , STRsacct+1 , STRu acct+1 =====Phase 1: State Transition and Proof Generation (Server-side)===== 3: server checks CheckUpdateAdmissibility(op, MTRbase acc , statet ) 4: server checks CheckUpdateAdmissibility(op, MTRbase acc , statet ) 5: if check fails then reject and return required info 6: end if 7: switch op 8: case NewSession: statet+1 ← NewSession(statet , input) 9: case Append: statet+1 ← AppendMessage(statet , input) 10: case Branch: statet+1 ← BranchMessage(statet , input) 11: case DeleteSession: statet+1 ← DeleteSession(statet , input) 12: case Merge: statet+1 ← MergeStates(statet , input.U) 13: MTRacct+1 ← ComputeAccountRoot(statet+1 ) 14: update payload ← ExtractUpdatePayload(op, statet , statet+1 , input) 15: MerkleProofs ← GenerateTransitionProofs(op, MTRbase acc , MTRacct+1 , update payload) 16: STRsacct+1 ← Signsks ("ACCOUNT STATE"∥MTRacct+1 ∥timestamp) s 17: server sends (update payload, MTRbase acc , MTRacct+1 , timestamp, MerkleProofs, STRacct+1 ) =====Phase 2: Proof Verification and Freshness Check (User-side)===== 18: user checks MTRbase acc = locally stored MTRacct 19: if check fails then reject and abort 20: end if 21: τnodes ← ExtractRemoteNodeTimestamps(update payload) 22: user performs IncrementalReplayFreshnessCheck(τnodes , timestampsig , timestampupdate ) 23: if check fails then reject and abort 24: end if 25: user performs VerifyTransitionProof(op, MTRbase acc , MTRacct+1 , update payload, MerkleProofs) 26: if verification fails then reject and abort 27: end if 28: verify STRsacct+1 using pks 29: if fails then reject and abort 30: end if ===============Phase 3: User Commitment============== 31: STRu acct+1 ← Signsku ("ACCOUNT STATE"∥MTRacct+1 ∥timestamp) 32: user sends (MTRacct+1 , timestamp, STRu acct+1 ) to server ==============Phase 4: Server Confirmation============== 33: STRu acct+1 using pku 34: if fails then reject and abort 35: end if 36: server stores (MTRacct+1 , STRsacct+1 , STRu acct+1 ); send success =================Phase 5: Finalization================= 37: (MTRacct+1 , STRsacct+1 , STRu acct+1 ) 38: return statet+1 , MTRacct+1 , STRsacct+1 , STRu acct+1

21

Algorithm 2 NewSession(state, Q&A)) 1: Input: current account state and initial Q&A data 2: Output: updated state 3: create node N with parent hash ← 0 4: compute node hash ← Hash(parent hash∥Q∥A∥model config∥file aux info∥timestamp) 5: create a new session containing a single branch whose tail is node hash 6: update the session root and account state 7: return updated state

User-side proof verification. Let MTRacct and MTRacct+1 denote the account roots before and after the update, respectively. The server returns the newly created Q&A node, the updated account root MTRacct+1 , and the corresponding MerkleProofs. The initial node hash is recomputed from parent hash = 0, Q, A, model config, file aux info, and timestamp, and the result is taken as the hashtail of the sole branch in the new conversation: hashtail = Hash(parent hash∥Q∥A∥model config∥file aux info∥timestamp). Since the conversation contains exactly one branch at this point, the new conversation root MTRcon new is derived directly from hashtail . The MerkleProofs are then used to verify the append-style account-state transition from MTRacct to MTRacct+1 : all pre-existing conversation roots must remain consistent with the locally anchored account state, and MTRcon new must be correctly incorporated as a new leaf in the account-level Merkle tree. If the account root recomputed along the proof path matches the server-returned MTRacct+1 , the NewSession operation passes user-side verification. The proof size is O(log n), where n is the number of conversations in the account prior to the update. Case 2: Message Append. A message append modifies only the chain tail of the target branch. The current hashtail is used as the parent hash of the new node; the new node hash is computed, and the corresponding leaf in the conversation-level Merkle tree is replaced with the updated hashtail . The conversation root MTRcon is then updated, and the change is propagated to the account-level root MTRacc . Algorithm 3 AppendMessage(state, (session id, branch id, Q&A)) 1: Input: current account state, target branch, and new Q&A data 2: Output: updated state 3: locate the target branch and retrieve its current tail 4: create node N with parent hash equal to the current branch tail 5: compute node hash ← Hash(parent hash∥Q∥A∥model config∥file aux info∥timestamp) 6: append N to the branch and replace the branch tail with node hash 7: update the session root and account state 8: return updated state User-side proof verification. Let MTRcont and MTRcont+1 denote the conversation roots before and after the update, and let MTRacct and MTRacct+1 denote the corresponding account roots. A message append modifies only the tail of the target branch; no new conversation or branch is created. The server returns the new Q&A node, the previous branch tail hashold tail , the updated account root MTRacct+1 , and the corresponding MerkleProofs. Two checks are performed first: hashold tail must be a valid branch leaf under MTRcont , and MTRcont must be anchored to the locally stored account root MTRacct . With parent hash set to hashold tail , the new branch tail is then recomputed as:

22

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

（

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

Account state updated

（

Q&A node

Q&A node hashtail

Q&A node

（

MTRcon

H12=Hash h1||h2

）

（

MTRcon

H12=Hash (h1||h2)

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

Q&A node hashtail

Q&A node

Q&A node hash_tail

Q&A node hashtail

H34=Hash h3||h4

）

Q&A node hashtail

Q&A node

H12=Hash h1||h2

）

（

H34=Hash h3||h4

）

MTRcon

（

）

MTRcon

H12=Hash (h1||h2)

MTRacc

MTRacc

Figure 4: Account-State Transition for Message Appending

hashnew tail = Hash(parent hash∥Q∥A∥model config∥file aux info∥timestamp). new hashold tail is replaced by hashtail , and MTRcont+1 is recomputed along the conversation-level proof path. MTRcont is then replaced by MTRcont+1 in the account-level tree, and MTRacct+1 is recomputed along the account-level proof path. If the recomputed account root matches the server-returned value, the append operation passes user-side verification. The proof size is O(log m + log n), where m is the number of branches in the target conversation and n is the number of conversations in the account.

Case 3: Branch Creation. Adding a new branch to an existing conversation is equivalent to introducing a new hash chain. The hash of the branching-point node is used as the parent hash of the new node; the hashtail of the new branch is computed and inserted as a new leaf into the conversation-level Merkle tree. This operation modifies MTRcon and propagates the change to the account-level root MTRacc . Algorithm 4 BranchMessage(state, (session id, parent node, Q, A, params)) 1: Input: current account state, branching point, and new Q&A data 2: Output: updated state 3: locate and verify parent node in the target session 4: create node N with parent hash ← Hash(parent node) 5: compute node hash ← Hash(parent hash∥Q∥A∥model config∥file aux info∥timestamp) 6: create a new branch ending at node hash 7: update the session root and account state 8: return updated state User-side proof verification. Branch creation does not overwrite the existing history; instead, a new branch chain is created beyond an already-authenticated historical node. The server returns the branching-point node, the new Q&A node, the updated account root MTRacct+1 , and the corresponding MerkleProofs. Since the user device retains only the account-level anchor and neither the full intra-conversation hash chain nor intermediate authentication paths, the server must supply a successor-chain proof from the branching-point node to some prior branch old tail hashold tail , together with the authentication paths from hashtail to MTRcont and from MTRcont to MTRacct . These proofs are used to verify that the branching-point node is anchored to the pre-update conversation root MTRcont , which is in turn anchored to the locally stored account root MTRacct . Upon successful verification, the hash of the branching-point node is set as the parent hash of the new node, and the new branch tail is recomputed from Q, A, model config, file aux info, and timestamp: 23

Q&A node

Q&A node Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

H12=Hash h1||h2

）

（

MTRcon

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

（

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

Account state updated

（

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

（

MTRcon

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

（

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

（

Q&A node hashtail

H34=Hash h3||h4

（

H12=Hash h1||h2

）

）

H1234= Hash(H12||H34)

H12=Hash h1||h2

）

MTRcon

H12=Hash (h1||h2)

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

Q&A node hashtail

Q&A node

Q&A node hashtail

H34=Hash h3||h4

）

Q&A node

）

MTRcon

MTRcon

H12=Hash (h1||h2)

MTRacc

MTRacc

Figure 5: Account-State Transition for Branch Creation

hashnew tail = Hash(parent hash∥Q∥A∥model config∥file aux info∥timestamp). hashnew tail is then incorporated as a new branch leaf into the conversation-level Merkle tree, and MTRcont+1 is recomputed. MTRcont is subsequently replaced by MTRcont+1 in the accountlevel tree, and MTRacct+1 is recomputed. If the recomputed account root matches the serverreturned value, the branch operation passes user-side verification. If the successor chain from the branching point to the prior branch tail has length l, the total verification material is O(l + log m + log n), where m denotes the number of branches in the target conversation and n denotes the number of conversations in the account. Case 4: Session Deletion. Session deletion does not remove a leaf from the account-level Merkle tree; instead, the original conversation root is replaced by a deletion-state conversation root. All other nodes in the target conversation are deleted or hidden in accordance with applicable legal requirements. Let MTRold con denote the root of the target conversation prior to deletion. The deletion-state conversation root is defined as: old MTRdel con = Hash("DEL SESSION"∥MTRcon ∥timestampdel ),

where MTRold con preserves the historical commitment of the deleted conversation, timestampdel records the deletion time, and "DEL SESSION" serves as a domain-separation tag. The leaf corresponding to the target conversation in the account-level Merkle tree is replaced from MTRold con to MTRdel con , after which MTRacc is recomputed. Algorithm 5 DeleteSession(state, input) 1: Input: current account state and target session information 2: Output: updated state or rejection 3: if MTRbase acc ̸= current account root then 4: reject 5: end if 6: locate target session; if already deleted, reject old 7: compute MTRdel con ← Hash("DEL SESSION"∥MTRcon ∥timestampdel ) 8: mark the target session as deleted and record the deletion witness del 9: replace MTRold con with MTRcon in the account state 10: return updated state User-side proof verification. Session deletion is modeled in the authentication structure as an account-level leaf replacement rather than a direct removal of a leaf from the accountlevel Merkle tree. The server returns the pre-deletion conversation root MTRold con , the deletion 24

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

（

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

（

（

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H34=Hash h3||h4

）

MTRcon

Account state updated

Q&A node

H12=Hash h1||h2

）

（

H12=Hash h1||h2

）

MTRcon

（

MTRcon

H12=Hash (h1||h2)

MTRcon

H34=Hash h3||h4

）

del

（

）

MTRcon

H12=hash (h1||h2)

MTRacc

MTRacc

Figure 6: Account-State Transition for Session Deletion timestamp timestampdel , the deletion-state conversation root MTRdel con , the updated account root MTRacct+1 , and the corresponding MerkleProofs. Two checks are performed. First, MerkleProofs are used to verify that MTRold con is the current leaf for the target conversation under the locally anchored account root MTRacct . Second, the deletion-state root is recomputed and verified against its definition: old MTRdel con = Hash("DEL SESSION"∥MTRcon ∥timestampdel ). del The account-level leaf MTRold con is then replaced by MTRcon , and MTRacct+1 is recomputed along the account-level authentication path. If the recomputed account root matches the serverreturned value, the deletion operation passes user-side verification. This process ensures that a session deletion does not erase the cryptographic commitment to the pre-deletion conversation state; rather, it converts that state into a verifiable deletion record. The proof size is O(log n) hash values, where n denotes the number of conversations in the account. Serialization constraints between deletion and concurrent updates are handled by the multi-device consistency protocol described in the following section.

Complexity Analysis. The cryptographic update complexity for server-side account-state reconstruction and user-side account-state transition verification across the four operation types is summarized as follows. Table 6: Cryptographic complexity of core operations Operation

Server (Update)

User (Verify)

NewSession AppendMessage BranchMessage DeleteSession

O(log n) O(log m + log n) O(log m + log n) O(log n)

O(log n) O(log m + log n) O(l + log m + log n) O(log n)

Here n denotes the number of conversations in the account, m denotes the number of branches in the target conversation, and l denotes the length of the successor chain from the branching point to the prior branch tail. Session deletion additionally involves hiding or removing plaintext Q&A content at the database layer, incurring a storage overhead of O(S), where S is the number of Q&A nodes in the target conversation; this overhead does not affect the cryptographic state-update complexity. 4.2.3

Multi-Device Concurrent Merge and Accountable Synchronization

This section presents the view-merging and eventual-consistency accountability mechanism for multi-device settings. The system permits multiple devices belonging to the same user to 25

interact with the LLM concurrently; however, during concurrent operation each device uses only its own locally anchored account state as the model context, and does not automatically incorporate state updates produced by other devices that have not yet been merged locally. A device triggers account-state merging through an UpdateConversationRecord(denoted UCR for brevity) operation to obtain concurrent updates from other devices during that period; upon completion of the merge, the new account-level Merkle root MTRacc is jointly confirmed by dual signatures from the server and the user. To prevent undecidable semantic conflicts between deletion states and concurrently modified states, DeleteSession is defined in VCT as an account-level serialized state transition rather than an ordinary commutative update. Specifically, a deletion operation must be submitted against the server’s current account root and, once committed, advances the account into a new deletion epoch. The multi-device merge algorithm processes only non-deletion updates—namely NewSession, Append, and Branch—within the same deletion epoch. Although a committed deletion state does not participate in ordinary concurrent merges, it must be witnessed as a synchronization barrier by all subsequent device states. If a device’s local account anchor does not yet reflect the latest deletion state, the server must, before accepting any further updates from that device, return a state-transition proof demonstrating that the deletion transition has occurred. The device uses this proof to verify that the target conversation del root has been replaced from MTRold con to MTRcon , and advances its local account anchor to the account root that incorporates the deletion state. Only after crossing this deletion barrier are non-deletion updates produced by the device considered to belong to the current deletion epoch and eligible for the subsequent deterministic merge procedure. 4.2.3.1 Concurrent Interaction Model When multiple devices interact with the LLM simultaneously, each device maintains an independent local conversation view. Concurrent increments across devices remain mutually invisible and are not incorporated into each other’s LLM context until the user explicitly invokes an UCR operation. This concurrent interaction model is captured in Algorithm 6. Algorithm 6 ConcurrentChat 1: // Each device independently interacts with the LLM 2: devicei .local ← devicei .local ∪ LLM(devicei .local∥inputi ) 3: // The device invokes UCR to trigger merging 4: procedure SYNC(devicek ) 5: (state new, MTR acc new, STR acc s, STR acc u) 6: ← MergeStates(devicek , global, devicek .id, version) 7: global ← state new 8: devicek .local ← Sessions(MTR acc new) 9: return devicek .local 10: end procedure The notion of ”independent interaction” in Algorithm 6 refers solely to the independence of model context; it does not imply that the system is unaware of the operation target. Each state update submitted to the server still carries protocol metadata—including the operation type, the target conversation, and the corresponding baseline state—which the server uses to execute the merge, verification, and signing procedures. 4.2.3.2 Account-Level Serialization of Session Deletion Session deletion is modeled as an account-level serialized state transition. Before issuing a deletion request, the device must first invoke UCR to obtain the current global account state as declared by the server. The deletion request carries the account root MTRbase acc observed by the device, as well as the conversation-level root MTRold of the target conversation under that con 26

account state. The server accepts the deletion request only when MTRbase acc exactly matches the current current global account root MTRacc . Since the account-level Merkle root already authenticates the target conversation root MTRold con , the account-root consistency check guarantees that the deletion operation targets the latest conversation state observed by the device. These rules endow the deletion operation with strict account-level serial semantics. Because a DeleteSession operation must be submitted against the server’s current latest account root, it cannot be submitted concurrently with other operations. If the account root on which a deletion request is based lags behind MTRcurrent , committed updates exist in the account acc state that the device has not yet witnessed; the server rejects the deletion request and requires the device to synchronize first. Once a deletion is committed serially, the resulting MTRdel con is incorporated into the new account state and advances the deletion epoch. In addition to the strict freshness check on deletion operations, the server enforces a deletionepoch check on subsequent non-deletion updates. If a device submits a NewSession, Append, or Branch request based on an account root that does not yet reflect the latest deletion state, the server does not accept the update directly; instead, it returns the missing state transition, the deletion-state witness, and the corresponding MerkleProofs, enabling the device to advance its local account anchor to the account root that incorporates the deletion state and thereby enter the current deletion epoch. Once the account state has been updated, if the target conversation remains active, the non-deletion update may be resubmitted against the current deletion epoch; if the target conversation is already in a deleted state, the server rejects any subsequent Append or Branch directed at that conversation. These two checks together constitute the deletion serialization principle: a DeleteSession operation must be submitted against the current latest account root, and non-deletion updates must be submitted against an account state that has already witnessed the latest deletion. Consequently, DeleteSession does not enter the concurrent merge procedure but instead forms an account-level synchronization barrier. This mechanism ensures that all devices have observed the latest session deletion result before producing further updates, thereby preventing undecidable merge semantics between deletion states and concurrent append or branch operations. Table 7: Operation types and their handling in concurrent settings Operation

Concurrent Merge

Additional Acceptance Condition

Outcome

NewSession

Yes

—

Append

Yes

Target conversation must not be in a deleted state.

Branch

Yes

Target conversation must not be in a deleted state.

DeleteSession

No

current MTRbase acc = MTRacc

Incorporated as a new conversation leaf at the account level. The branch hashtail is updated; changes propagate to MTRcon and MTRacc . A new branch leaf is inserted; changes propagate to MTRcon and MTRacc . Committed serially; MTRdel con generated and MTRacc updated; deletion state serves as a synchronization barrier.

4.2.3.3 Merge Protocol A device obtains the current global account state declared by the server by invoking the UCR operation. This operation calls the view-merge algorithm, which consolidates non-deletion increments concurrently produced by multiple devices into a unified account state. The deterministic merge function is defined as follows. Definition 1 (Merge Function). The merge function 27

Merge(M1 , M2 , . . . , Mn ) → Mmerge satisfies the following three properties: • Inclusion: M1 ⪯ Mmerge , M2 ⪯ Mmerge , . . . , Mn ⪯ Mmerge . A valid state-transition path exists from every input state Mi to Mmerge . • Determinism: Identical input sets always yield a unique output. • Conflict-free preservation: Conflicting non-deletion updates are materialized as distinct branches; no valid update produced by any device is discarded [35, 36]. Based on this definition, the state-merge procedure in VCT partitions merge scenarios into two cases depending on whether concurrent updates target the same conversation. Merging of Concurrent Updates on Distinct Conversations If two devices each create a new conversation, the resulting conversations are ordered by the timestamp of their respective initial nodes and inserted into the account-level conversation set; this is equivalent to appending leaves to the account-level Merkle tree. If one device creates a new conversation while another modifies an existing one, a leaf insertion and a leaf update are applied simultaneously to the account-level Merkle tree, after which MTRacc is recomputed. If two devices modify different existing conversations, two distinct leaves are updated; the account-level authentication structure update alone costs O(log n), where n is the number of conversations in the account. When intra-conversation state updates are also considered, the total cost equals the sum of the respective per-conversation update costs and the account-level path update cost.

Case 1 — New sessions are created by distinct devices.

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

（

Q&A node hashtail

Q&A node

（

Q&A node hashtail

Q&A node

（

MTRcon

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

MTRcon

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

Q&A node hashtail

H12=Hash h1||h2

）

（

H12=Hash h1||h2

）

MTRcon

（

Q&A node

Q&A node

Q&A node hashtail

Q&A node

（

Q&A node hashtail

（

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

（

Case 2 — A new session is created by one device, while an existing session is modified by another device.

Q&A node hashtail

（

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

（

Q&A node

（

H12=Hash h1||h2

）

MTRcon

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

MTRcon

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

Q&A node hashtail

（

H12=Hash h1||h2

）

MTRcon

（

Q&A node

Q&A node

Q&A node hashtail

Q&A node

（

Q&A node hashtail

（

Case 3 — Existing sessions are modified by distinct devices.

Q&A node

Q&A node hashtail

Q&A node

H12=Hash h1||h2

）

（

Q&A nodel

Q&A node

Q&A node

Q&A node hashtail

（

MTRcon

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

（

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

Q&A node hashtail

Q&A node hashtail

（

MTRcon

MTRacc

The original state of the account-level Merkle tree

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

Q&A node

H12=Hash h1||h2

）

（

MTRcon

Q&A node hashtail

Q&A nodel

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

（

MTRcon

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

H34=Hash h3||h4

）

Q&A node

Q&A node

（

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

（

H34=Hash h3||h4

）

（

MTRcon

（

Q&A node

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

（

MTRcon

Q&A nodel

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

MTRcon

H34=Hash h3||h4

）

（

）

MTRcon

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

（

H34=Hash h3||h4

）

（

MTRcon

MTR_acc_B

（

After the session record is updated, the account state is merged between Device A and Device B.

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

H34=Hash h3||h4

）

（

）

MTRcon

MTRacc_B

A different existing session is updated by Device B.

Q&A node

Q&A node

Q&A nodel

Q&A node hashtail

H12=Hash h1||h2

）

MTRcon

MTRacc_A

An existing session is updated by Device A.

（

Q&A node

MTRcon

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

H34=Hash h3||h4

）

Q&A node

Q&A node

MTRacc

Q&A node

Q&A node

Q&A node hashtail

（

An existing session is updated by Device B.

A new session is initiated by Device A.

Q&A node

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

MTRacc_B

Q&A node

Q&A node

Q&A node

Q&A node hashtail

H34=Hash (h3||h4)

Q&A node hashtail

H12=Hash h1||h2

）

MTRcon

Q&A node

Q&A node

Q&A node hashtail

）

MTRacc_A

The original state of the account-level Merkle tree

Q&A node

MTRcon

Q&A node

Q&A node hashtail

H12=Hash (h1||h2)

MTRacc

Q&A node

Q&A node hashtail

H34=Hash h3||h4

）

MTRcon

Q&A node

After the session record is updated, the account state is merged between Device A and Device B.

Q&A node

Q&A node

Q&A node

H12=Hash h1||h2

）

A new session is created by Device B.

Q&A node

Q&A node hashtail

Q&A node hashtail

MTRacc

Q&A node

Q&A node

Q&A node

H12=Hash (h1||h2)

Q&A node

Q&A node

（

MTRacc_B

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

H12=Hash (h1||h2)

A new session is created by Device A.

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

）

Q&A node hashtail

Q&A node

MTRcon

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

H34=Hash h3||h4

）

Q&A node

Q&A node hashtail

（

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node

MTRcon

MTRacc_A

The original state of the account-level Merkle tree

Q&A node

Q&A node

H12=Hash h1||h2

）

Q&A node

Q&A node

MTRcon

H12=Hash (h1||h2)

MTRacc

Q&A node

Q&A node

H12=Hash h1||h2

）

MTRcon

Q&A node hashtail

Q&A node

Q&A node hashtail

H34=Hash h3||h4

）

MTRcon

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A nodel

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node hashtail

H12=Hash h1||h2

（

（

Q&A node hashtail

H34=Hash h3||h4

）

MTRcon

Q&A node

Q&A node

Q&A node hashtail

H12=Hash h1||h2

）

（

）

MTRcon

MTRacc

After the session record is updated, the account state is merged between Device A and Device B.

Figure 7: Merge scenarios on the same conversation.

28

Q&A node

Q&A nodel

）

）

Merging of Concurrent Updates on the Same Conversation. If multiple devices concurrently modify the same existing conversation, concurrent updates are materialized as distinct branches. Regardless of whether a device appends a message to the tail of an existing branch or creates a new branch from a historical node, each such update is treated at the merge layer as the insertion of one or more branches into the conversation tree. When multiple devices create branches from the same parent node, branches are ordered by their initial-node timestamps with respect to existing sibling timestamps; when devices target different parent nodes, ordering is applied independently under each respective parent. This results in an update to the conversation-level Merkle root MTRcon , which P is then propagated to the account-level root MTRacc . The complexity is O(log m + log n + i log Li ), where m is the number of branches in the target conversation after the merge, n is the number of conversations in the account, and Li is the number of children of the i-th affected parent node after the merge. These three terms correspond, respectively, to the conversation-level Merkle path update, the account-level Merkle path update, and the cost of inserting new branches into an ordered child set supporting O(log Li )-time insertion by timestamp. Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

H12=Hash h1||h2

）

（

MTRcon

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

H12=Hash h1||h2

（

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

（

MTRcon

MTRacc

Original State of the Account-Level Merkle Tree

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node

H12=Hash h1||h2

）

Q&A node

H12=Hash h1||h2

）

（

MTRcon

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

Q&A node

（

）

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

MTRcon

H12=Hash h1||h2

）

（

MTRcon

H34=Hash h3||h4

）

Q&A node

Q&A node hashtail

Q&A node

Q&A node

Q&A node hashtail

Q&A node

Q&A node hashtail

（

）

（

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

Q&A node hashtail

H12=hash

H56=hash

Q&A node

Q&A node hashtail

H78=hash

（h5||h6）

（h7||h8）

H1234=Hash H12||H34)

（

MTRcon

Q&A node

Q&A node hashtail

Q&A node hashtail

H34=hash

（h3||h4）

H1234=Hash H12||H34)

）

MTRacc

The same existing session is modified by Device B.

Q&A node

（h1||h2）

H12=Hash h1||h2

Q&A nodel

Q&A node

Q&A node

Q&A node

Q&A node hashtail

MTRcon

MTRacc

An existing session is modified by Device A.

Q&A node

Q&A node hashtail

H12=Hash h1||h2

（

Q&A nodel

Q&A node

Q&A node hashtail

H34=Hash h3||h4

）

Q&A node

Q&A node

Q&A node

（

MTRcon

MTRacc

After the session record is updated, the account state is merged between Device A and Device B.

Figure 8: Merge scenarios on the same conversation.

Merge Protocol Unlike single-device basic update operations, the increments being merged have already been witnessed by the devices that produced them and are anchored to user-signed account states. The correctness of the merge can therefore be further verified by the user side by leveraging these pre-existing signatures. As described in Section 3.2, a complete account-state history with associated state-transition records, or an equivalent delta log, is maintained on the server. Upon invoking UCR, a device base submits only its locally held account root MTRbase acc . The account state anchored by MTRacc is taken as the synchronization baseline; non-deletion updates belonging to the same deletion epoch that have been committed by other devices but not yet witnessed by the synchronizing device are extracted from the signed account-state history and deterministically merged into the device’s local view via Algorithm 7.

29

Algorithm 7 MergeStates(MTRbase acc , Hacc ) 1: Input: 2: MTRbase acc : account root submitted by the synchronizing device 3: Hacc : signed account-state history with associated transition records, or an equivalent delta log 4: Output: 5: Smer : merged account state 6: // Precondition: 7: MTRbase acc has passed the deletion-epoch check. 8: DeleteSession is serialized at the account level and does not enter MergeStates. 9: The server can recover the account state Sbase anchored by MTRbase acc , or an equivalent delta representation. 10: Sbase ← ResolveAccountState(MTRbase acc , Hacc ) 11: U ← CollectUnseenMergeableUpdates(Hacc , MTRbase acc ) 12: Smer ← Copy(Sbase ) 13: for each u ∈ NewSessionUpdates(U ) in deterministic order do 14: Smer ← InsertNewSession(Smer , u) 15: end for 16: for each session id ∈ ExistingSessionsAffectedBy(U ) in deterministic order do 17: G ← UpdatesForSession(U, session id) 18: merge Append updates in G by extending the corresponding branch tails 19: merge Branch updates in G by inserting new branch tails at their authenticated branching points 20: update the session root of session id in Smer 21: end for 22: SortSessions(Smer ) by (created at, session id) 23: return Smer Here Hacc denotes the dual-signed account-state history maintained by the server for each device, together with associated state-transition records, or an equivalent delta log. The account state Sbase anchored by MTRbase acc is recovered via ResolveAccountState, and the set U of same-epoch non-deletion updates that have been committed and confirmed by other devices but are not yet reflected in MTRbase acc is extracted via CollectUnseenMergeableUpdates. Starting from Sbase , Algorithm 7 deterministically incorporates the non-deletion increments in U into the synchronizing device’s account view. Algorithm 7 produces only the merged account state Smer ; this result is then submitted as an op = Merge state transition to Algorithm 1 for account-root computation and dual-signature confirmation. Specifically, the new account root MTRacct+1 is computed from Smer ; the associated update payload and MerkleProofs are generated and STRsacct+1 is issued by the server. On the user side, the account root is recomputed from update payload and MerkleProofs, and each incorporated update is verified to have been anchored to an account state previously signed by the same user private key on another device. Upon successful state-transition proof and signature verification, STRuacct+1 is issued over the confirmed MTRacct+1 , and the account state is finalized upon server-side verification of the user signature. The merge operation thus shares the same proof-verification and dual-signature confirmation procedure as all other account updates. Devices are not required to invoke UCR simultaneously; verification and signature confirmation of the merge result are performed by the device that triggers synchronization. The set U of unseen non-deletion updates may vary across devices depending on each device’s local account root and the timing of synchronization, but the merge rules remain invariant. 4.2.3.4 Incremental-Replay Rejection and Gossip Pre-check

30

To prevent the server from returning a stale but previously valid account state during synchronization and subsequently delivering deliberately omitted increments in follow-up updates, an incremental-replay freshness check is enforced on the device side when accepting merged increments. Let timestampsig denote the maximum timestamp bound to the user signatures STRuacc over the confirmed account states returned in the transition proofs of the last UCR invocation, and let timestampupdate denote the time at which that invocation was initiated. Since STRuacc is produced under the user private key and bound to the account-level Merkle root MTRacc , increments already reflected in that signed state prior to timestampsig cannot be omitted without invalidating signature verification. The check therefore focuses on whether increments that existed between timestampsig and timestampupdate were selectively withheld by the server. Specifically, if an incremental node received during a subsequent synchronization or merge carries a timestamp timestampnode satisfying timestampsig < timestampnode ≤ timestampupdate , the node is determined to have existed at the time of the device’s last UCR invocation but was not incorporated into the latest account state claimed by the server. The increment is accordingly rejected and treated as evidence that the server failed to return the current latest account state at that time. Conversely, if timestampnode > timestampupdate , the node may be a legitimate new update produced after the device’s last update request and is not rejected under this rule. This check is complementary to the gossip accountability mechanism described below: incrementalreplay rejection prevents the server from patching a single device’s view through a strategy of first returning a stale state and subsequently delivering omitted increments. 4.2.3.5 Gossip-Based Fork Detection and Accountability The gossip protocol is employed to detect whether inconsistent account views have been served to different devices [37, 30, 31]. Gossip is executed opportunistically whenever communication is available; when view inconsistency is suspected, all devices may be required to come online simultaneously and execute a full gossip round. Prior to gossip execution, all participating devices must complete UCR, and LLM interactions are suspended during the gossip round to prevent account-state changes from occurring mid-comparison. Inter-device gossip communication is protected by an end-to-end encrypted channel. The communication key is derived jointly from the user root key Ku and the login password pwdu , following the same derivation structure as the user signing key but under a distinct domainseparation tag: Kgossip ← KDF(Ku , pwdu , salt, iterations, "gossip encryption", key len), where Ku is the high-entropy user root key shared across all devices; pwdu is the user login password; salt and iterations are shared with the signing-key derivation; "gossip encryption" serves as a domain-separation tag ensuring that Kgossip is cryptographically independent of the signing key sku ; and key len specifies the output length in bytes. The key is derived and securely stored upon device initialization and reused in subsequent gossip rounds. The core gossip procedure is as follows. A secure channel is established under Kgossip , and each device exchanges its latest signed state EncKgossip (MTRacc ∥STRuacc ∥STRsacc ). Upon decryption, the user and server signatures are verified and the account-level Merkle roots are compared. Matching roots indicate a consistent view; diverging roots indicate a fork. Fork evidence consists of two distinct valid signed states; since the server cannot forge user signatures and cannot repudiate its own, the evidence is cryptographically non-repudiable. Algorithm 8 performs online consistency detection between devices.

31

Algorithm 8 GossipProtocol(DA , DB ) 1: Input: 2: DA : (MTRaccA , timestampA , STRuaccA , STRsaccA ) 3: DB : (MTRaccB , timestampB , STRuaccB , STRsaccB ) 4: Output: 5: Consistent or ForkDetected with evidence 6: Precondition: 7: Both DA and DB have completed UCR; no new LLM interaction occurs during gossip. 8: if Kgossip is not initialized then 9: Kgossip ← PBKDF2(Ku , pwdu , salt, iterations, "gossip encryption", key len = 32) 10: SecureStore(Kgossip ) 11: end if 12: channel ← EncChannel(Kgossip ) s 13: msgA ← EncKgossip (MTRaccA ∥timestampA ∥STRu accA ∥STRaccA ) 14: send msgA to DB ; receive msgB from DB s 15: (MTRaccB , timestampB , STRu accB , STRaccB ) ← DecKgossip (msgB ) 16: if Verify(pku , "ACCOUNT STATE"∥MTRaccA ∥timestampA , STRu accA ) = ⊥ then return ⊥ 17: end if 18: if Verify(pks , "ACCOUNT STATE"∥MTRaccA ∥timestampA , STRsaccA ) = ⊥ then return ⊥ 19: end if 20: if Verify(pku , "ACCOUNT STATE"∥MTRaccB ∥timestampB , STRu accB ) = ⊥ then return ⊥ 21: end if 22: if Verify(pks , "ACCOUNT STATE"∥MTRaccB ∥timestampB , STRsaccB ) = ⊥ then return ⊥ 23: end if 24: if MTRaccA = MTRaccB then 25: return Consistent 26: else 27: return ForkDetected with evidence: 28: (MTRaccA , timestampA , STRuaccA , STRsaccA ), 29: (MTRaccB , timestampB , STRuaccB , STRsaccB ) 30: end if Algorithm 9 is not a gossip participant; it is an offline verification procedure for use by a third party T P or auditor to validate fork evidence produced by Algorithm 8. If both evidence records carry valid user and server signatures and bind distinct values of MTRacc , the evidence constitutes a verifiable proof that inconsistent account views were served to different devices. Algorithm 9 VerifyForkEvidence(evidence) 1: Input: 2: evidence = (EA , EB ), where Ei = (MTRacci , STRuacci , STRsacci ) 3: Output: 4: ValidFork or Invalid 5: if VerifySignedState(EA ) = ⊥ then return Invalid 6: end if 7: if VerifySignedState(EB ) = ⊥ then return Invalid 8: end if 9: if MTRaccA = MTRaccB then return Invalid 10: end if 11: return ValidFork Once a full gossip round is eventually executed across all devices, any attempt by the server 32

to serve incompatible states to different devices is detected. If a stale but valid account root was returned to a device during synchronization and the server subsequently attempts to deliver omitted increments, those increments are rejected by the device based on the synchronization boundary and the signed timestamps. Should the server continue to withhold the omitted state, the divergence between the STRuacc and STRsacc values held by different devices is exposed during gossip. 4.2.3.6 Device Online Synchronization Protocol Upon coming online, a device initiates an UCR request to the server to synchronize to the current latest account state. Let MTRaccD denote the device’s locally held account-level Merkle root. A state-transition proof package is returned by the server, comprising the relevant update payload, MerkleProofs, any applicable deletion-state witnesses, and the target account root MTRcurrent . acc Using the locally verified MTRaccD as the anchor, the returned update payload, MerkleProofs, and deletion-state witnesses are verified in deterministic order, and the target account root MTR′acc is reconstructed. If MTR′acc = MTRcurrent and all state-transition verifications pass, acc the device issues a signature to confirm and updates its local account anchor. This synchronization procedure does not rely on server honesty: a stale but previously valid state may be returned by the server, but any attempt to serve inconsistent views to different devices is ultimately detected and attributed through subsequent synchronization and gossip rounds. 4.2.3.7 New Device Enrollment Protocol New device enrollment begins with the key-provisioning procedure described in Section 4.2.1: Ku is securely obtained from an existing trusted device, and pwdu is entered locally by the user on the new device, from which sku , pku , and Kgossip are derived. This phase does not rely on the server to synchronize the user private key. Upon completion of key provisioning, the device online synchronization protocol of Section 4.2.3.6 is reused to obtain and verify the current account anchor (MTRacc , timestampacc , STRsacc , STRuacc ) as declared by the server. If participation in subsequent updates, signature confirmation, and gossip is sufficient, only this account anchor need be retained on the new device. If recovery of historical conversation content is required, the corresponding Q&A payload, update payload, and MerkleProofs are returned by the server on demand, enabling the new device to verify the binding between the recovered content and the account anchor. 4.2.4

Verifiable Conversation Sharing

The goal of verifiable conversation sharing is to enable a recipient R to independently verify the integrity and provenance of a shared Q&A fragment without trusting the server’s process of generating sharing links or export files. The selected Q&A pairs are first verified to be anchored to the account-level state MTRacc ; they are then reorganized into an independent hash chain, over whose tail separate signatures are issued by the server and the user. The protocol proceeds in three phases. Phase 1: User Selection and Proof Package Verification. pairs to be shared. A proof package is generated by the server:

The user designates the Q&A

proof = {selected nodes, MerkleProofs, MTRacc , STRsacc , STRuacc }, where selected nodes is the set of Q&A nodes designated by the user, MerkleProofs establishes that these nodes are anchored to the account-level Merkle root MTRacc , and STRsacc and STRuacc are the server and user signatures over MTRacc , respectively. Upon receipt of the proof package, the Merkle proof for each selected node is verified, along with STRsacc and STRuacc . If any verification fails, the sharing procedure is aborted. 33

Phase 2: Independent Share Chain Construction and Dual Signing. Upon confirmation that the selected Q&A nodes are anchored to a signed account state, the nodes are reorganized by the server into an independent hash chain. This chain carries no dependency on unshared nodes in the original conversation record and contains no external pointers into the original conversation tree. Let the tail of this independent chain be: sharetail = BuildIndependentChain(selected nodes). A signature over sharetail and the timestamp is first issued by the server: sharessig ← Signsks ("SHARE SNAPSHOT"∥sharetail ∥timestampshare ). The tuple (sharetail , timestampshare , sharessig ) is transmitted to the user. The independent chain tail is recomputed from selected nodes and verified to match the server-declared sharetail ; the server signature is verified under pks . Upon successful verification, a signature over the same chain tail is issued by the user: shareusig ← Signsku ("SHARE SNAPSHOT"∥sharetail ∥timestampshare ). Upon receipt of shareusig , the user signature is verified by the server under pku . A successful verification confirms that both parties have reached cryptographic agreement over the same sharing snapshot. Phase 3: Share Package Generation.

The final share package is defined as:

{selected nodes, sharetail , sharessig , shareusig , timestampshare }. This package may be further rendered as a sharing link, PDF, or other export format. To confirm that the shared content is unmodified and has been jointly confirmed by both parties, the recipient recomputes the sharetail of the independent chain and verifies the dual signatures. Since the share chain is independent of the original conversation tree, subsequent appends, edits, branches, or deletions to the original conversation do not affect the verifiability of an already-generated sharing snapshot. Algorithm 10 ShareTranscript 1: Input: selected nodes, MTRacc , STRsacc , STRu acc , MerkleProofs 2: Output: share package = {selected nodes, sharetail , timestampshare , sharessig , shareu sig } =========Phase 1: User verification of the proof package========= 3: proof ← {selected nodes, MerkleProofs, MTRacc , timestampacc , STRsacc , STRu acc } 4: send proof to user 5: For each node ∈ selected nodes do VerifyMerkleProof(node, MerkleProofs, MTRacc ) 6: Verify(pks , "ACCOUNT STATE"∥MTRacc ∥timestampacc , STRsacc ) 7: Verify(pku , "ACCOUNT STATE"∥MTRacc ∥timestampacc , STRu acc ) == Phase 2: Construction and dual signing of the independent share chain== 8: sharetail ← BuildIndependentChain(selected nodes) 9: sharessig ← Signsks ("SHARE SNAPSHOT"∥sharetail ∥timestampshare ) 10: send (sharetail , timestampshare , sharessig ) to user 11: ComputeChainTail(selected nodes) = sharetail 12: Verify(pks , "SHARE SNAPSHOT"∥sharetail ∥timestampshare , sharessig ) 13: shareu sig ← Signsku ("SHARE SNAPSHOT"∥sharetail ∥timestampshare ) 14: send shareu sig to server 15: Verify(pku , "SHARE SNAPSHOT"∥sharetail ∥timestampshare , shareu sig ) =============Phase 3: Output share package============= 16: return {selected nodes, sharetail , timestampshare , sharessig , shareu sig } 34

The protocol enforces a separation between original-conversation-state verification and sharingsnapshot confirmation. The former establishes that the shared nodes originate from a signed account state; the latter fixes the shared content via an independent hash chain and dual signatures. Any substitution, deletion, or reordering of shared nodes during share-link generation or file export is detectable; equally, repudiation of the sharing snapshot by the user is precluded.

4.3

Protocol Communication Overhead

This section analyzes the protocol communication overhead introduced by VCT beyond a typical LLM request–response exchange. Application-layer payloads—including the original user prompt, model response, and uploaded file content—are excluded from the analysis. Only the root hashes, signatures, authentication paths, incremental metadata, and protocol control fields required to achieve verifiable state confirmation, multi-device synchronization, consistency detection, and verifiable sharing are accounted for. Let |h| denote the hash output length and |σ| the signature length. Let n denote the number of conversations in the account, m the number of branches in the target conversation, k the number of increments involved in a synchronization or merge, s the number of shared nodes, and d the number of devices belonging to the same user that participate in gossip. For the Branch operation, l denotes the length of the successor chain from the branching point to a previously authenticated branch tail. Concrete instantiation parameters—including hash output length, signature length, and cryptographic parameters—are provided in Section 5.2. 4.3.1

Per-Update Confirmation Overhead

The communication overhead of an account-state update arises from the bidirectional confirmation procedure of Algorithm 1. The server transmits to the user the operation-specific update payload, the updated account root MTRacc , MerkleProofs, and the server signature STRsacc ; upon successful verification, STRuacc over the same account root is returned by the user. Prompt, response, and uploaded file content in update payload constitute applicationlayer data and are excluded from VCT-specific overhead; operation type, session identifier, branch identifier, timestamp, and necessary hash values contribute only constant-size control fields. Therefore, the additional communication overhead of a single account-state update consists primarily of the baseline account root, MerkleProofs, the updated account root, and two signatures. The per-confirmation overhead for each of the four basic update operations is summarized below. NewSession: Upon new session creation, MTRcon new is inserted as a new leaf into the accountlevel Merkle tree. An account-level append proof and the authentication path for the new conversation root must be supplied; the incremental overhead is therefore O(log n · |h| + 2|h| + 2|σ|). Append: A message append replaces only the hashtail of the target branch and propagates the change to the conversation root and account root. The conversation-level authentication path from the old hashtail to MTRcon , and the account-level path from MTRcon to MTRacc , must be supplied; the incremental overhead is therefore O((log m + log n) · |h| + 2|h| + 2|σ|). Branch: Branch creation requires proof that the branching point belongs to an authenticated history. Since the user device retains neither the full conversation chain nor intermediate authentication paths, a successor-chain witness from the branching point to a prior authenticated

35

branch tail must be supplied, together with authentication paths from that branch tail to MTRcon and from MTRcon to MTRacc ; the incremental overhead is therefore O((l + log m + log n) · |h| + 2|h| + 2|σ|). DeleteSession: Session deletion is modeled as an account-level leaf replacement, substituting old old MTRdel con for MTRcon . The authentication path of MTRcon in the account-level Merkle tree old must be supplied; MTRdel con can be recomputed and verified locally by the user from MTRcon and timestampdel . The incremental overhead is therefore O(log n · |h| + 2|h| + 2|σ|). 4.3.2

State Synchronization and Merge Overhead

The communication overhead of account-state synchronization and merging depends on the number and type of increments to be synchronized. Let MTRbase acc denote the account root locally anchored by the lagging device. The synchronization target returned by the server varies by scenario: a full synchronization targets the server’s current account root MTRcurrent ; acc submission of a non-deletion update requires synchronization only to the account root reflecting the latest deletion state; submission of DeleteSession requires synchronization to MTRcurrent , acc since a deletion must be submitted against the server’s current latest account state. Let the interval from MTRbase acc to the target account root contain k non-deletion increments and r deletion-state transitions that have been serially committed but not yet witnessed by the device. The server returns the relevant update payload, MerkleProofs, the target account root, and dual signatures attesting to the state transitions. Using MTRbase acc as the anchor, these state changes are verified in deterministic order and the target account root is reconstructed. For non-deletion increments, let Πi denote the proof material size for the i-th increment. When only non-deletion increments are present, the synchronization and merge overhead is: ! k X O Πi + |h| + 2|σ| , i=1

where Πi is determined by the operation type: O(log ni · |h|) for NewSession; O((log mi + log ni ) · |h|) for Append; and O((li + log mi + log ni ) · |h|) for Branch. Here ni denotes the number of conversations in the account at the time of the i-th update, mi the number of branches in the target conversation, and li the length of the successor chain from the branching point to the previously authenticated branch tail. The latest local account roots MTRacc and STRuacc carried in the proof material for concurrent increments constitute a constant number of hash values whose count depends only on the number of devices and does not affect the asymptotic overhead. Deletion operations do not enter MergeStates as ordinary concurrent increments; instead, each forms an account-level serialization boundary. When the synchronization interval contains deletion-state transitions, a deletion-state witness must also be returned by the server. This witness establishes that MTRold con is the target conversation leaf under the pre-deletion account root, and is used to verify: old MTRdel con = Hash("DEL SESSION"∥MTRcon ∥timestampdel ).

The device then verifies along the account-level authentication path that MTRdel con is incorporated into the post-deletion account root. Let ∆j denote the proof material size of the j-th deletion-state witness; in general: ∆j = O(log nj · |h|). 36

When dual signatures are attached to each deletion-state account root, the synchronization overhead for an interval containing r deletion-state transitions is:   k r X X O Πi + (∆j + |h| + 2|σ|) + |h| + 2|σ| , i=1

j=1

Pr

where j=1 (∆j + |h| + 2|σ|) corresponds to the deletion-state witnesses together with the dual signatures over their respective deletion-state account roots, and the final term |h| + 2|σ| corresponds to the target account root and its dual signatures. When no deletion-state transitions are present in the synchronization interval, r = 0 and the expression reduces to the overhead of ordinary non-deletion increment synchronization. 4.3.3

Gossip Overhead

The communication overhead of the gossip protocol is digest-level. Rather than exchanging Q&A content, conversation trees, or MerkleProofs, devices exchange only their respective latest signed account anchors (MTRacc , STRuacc , STRsacc ). The per-pair gossip communication cost is O(|h| + 2|σ|), independent of the number of conversations, Q&A nodes, or conversation content in the account. When d devices execute a full pairwise gossip round, the total communication cost is O(d2 (|h| + 2|σ|)). Since the number of devices per user is typically small and each gossip message contains only an account root hash and two signatures, gossip overhead remains low in practical deployments. 4.3.4

New Device Onboarding Overhead

New device onboarding comprises two phases: inter-device key transfer and account-state synchronization. The user root key Ku and key derivation parameters (salt, iterations) are first obtained by the new device from an existing trusted device via a secure out-of-band channel such as a QR code, incurring a transfer cost of O(|Ku | + |salt| + |iterations|). Under fixed security parameters, this phase incurs constant communication overhead. After Ku is obtained and sku is derived, the current account anchor—MTRacc and its dual signatures (STRsacc , STRuacc )—must be acquired. If the new device is only required to participate in subsequent signature confirmation, synchronization, and gossip without immediately recovering the full conversation history, the VCT-specific overhead of account onboarding is O(|h| + 2|σ|). If full historical conversation recovery is required, the historical Q&A payload constitutes application-state synchronization and is excluded from VCT-specific overhead; the additional verification cost follows the same structure as that of a lagging-device synchronization, consisting primarily of MerkleProofs for the increments to be recovered, the final account root, and dual signatures: ! k X O |Πi | + |h| + 2|σ| . i=1

37

The minimum onboarding overhead is therefore constant; bandwidth for full history recovery is dominated by the volume of historical content the user chooses to restore, while the VCTspecific overhead remains governed by proof paths and the account anchor. 4.3.5

Verifiable Sharing Overhead

The communication overhead of the verifiable sharing protocol is computed following the threephase procedure of Section 4.2.4. During share generation, the server returns to the user a provenance proof package comprising selected nodes, the corresponding MerkleProofs, the account root MTRacc , and the dual signatures (STRsacc , STRuacc ) over the account root. The Q&A content of selected nodes constitutes user-initiated disclosure and is excluded from VCT-specific overhead; MerkleProofs, MTRacc , and the dual signatures constitute the additional verification cost of the provenance proof. When s nodes are shared and an independent authentication path is provided per node, the incremental provenance-proof overhead is O(s(log m + log n) · |h| + |h| + 2|σ|). When multiple shared nodes reside in the same conversation or share Merkle path segments, the server may employ batch proofs or multi-proofs to reduce constant factors and redundant path overhead; the expression above gives an upper bound for the case of independent paths. Upon user confirmation of the provenance proof, sharetail and sharessig are transmitted by the server, and shareusig is returned by the user. This dual-signing phase introduces an additional overhead of O(|h| + 2|σ|). The total VCT-specific overhead for share generation is therefore O(s(log m + log n) · |h| + 2|h| + 4|σ|), which, omitting constant factors, simplifies to O(s(log m + log n) · |h| + |σ|). The final public share package contains selected nodes, sharetail , sharessig , shareusig , and timestamp. Verification by the recipient requires only reconstruction of the independent share chain and verification of the dual signatures over the chain tail, with no access to the full account state and no further server interaction required. Excluding the shared content itself, the VCT-specific overhead of the public share package is O(|h| + 2|σ|).

4.4

Security Analysis

The security properties of VCT are analyzed in this section based on the threat model, security goals, and cryptographic assumptions established in Section 3. Unless stated otherwise, the following global assumptions are taken to hold throughout: Hash(·) satisfies collision resistance and second-preimage resistance; the digital signature scheme satisfies existential unforgeability under chosen-message attacks; the KDF and the underlying authenticated encryption mechanism are secure; user signatures are generated by user devices only after protocol-specified verification is completed; and the gossip channel between devices belonging to the same user provides authenticity and integrity. For properties that depend on protocol liveness—such as multi-device eventual consistency—it is additionally assumed that honest devices eventually complete synchronization and execute gossip.

38

4.4.1

Integrity Verification

Theorem 1 (Node Integrity). If any field Q, A, modelconfig , file aux info, or timestamp of a Q&A node is modified by an adversary, the modification is detected during branch hash-chain verification or account-state verification. Proof. Consider a branch hash chain consisting of nodes N1 , N2 , . . . , Nm , with branch tail hashtail . For any i < m, the hash-chain invariant requires Ni+1 .parent hash = Hash(Ni ), where Hash(Ni ) = Hash(parent hashi ∥Qi ∥Ai ∥modelconfigi ∥file aux infoi ∥timestampi ). If an intermediate node Nk with k < m is modified by the adversary, the recomputed Hash(Nk ) differs from its original value, while Nk+1 .parent hash retains the original value; the hash-chain invariant is thereby violated. If the tail node Nm is modified, the recomputed hashtail changes, which propagates to the conversation-level root MTRcon and subsequently to the account-level root MTRacc . Since any accepted MTRacc must be jointly anchored by the server signature STRsacc and the user signature STRuacc , the modified account root cannot pass verification without a valid forgery. Any tampering with node content is therefore detected. □ Theorem 2 (Conversation Integrity). If any branch within a conversation is added, deleted, or modified by an adversary, the modification is detected during conversation-level or accountlevel verification. Proof. Let the branch set of conversation C be {B1 , B2 , . . . , Bb } with corresponding branch tails {hashtail1 , hashtail2 , . . . , hashtailb }. The conversation-level Merkle root is defined as MTRcon = MerkleRoot({hashtail1 , hashtail2 , . . . , hashtailb }). Any modification to branch content alters the corresponding hashtail ; any addition or deletion of a branch alters the leaf set of the conversation-level Merkle tree. Unless a hash collision can be found, the recomputed MTRcon must therefore differ from its original value. Since MTRcon participates as a leaf in the computation of MTRacc , the change propagates to the account-level root. A valid account state must pass dual-signature verification under STRsacc and STRuacc , and no valid signature can be forged by the adversary over the modified account root. Any tampering with the branch set or branch content of a conversation is therefore detected. Theorem 3 (Account Integrity). If any conversation in a user account is added, deleted, or modified by an adversary, the modification is detected during account-level verification. Proof. Let the conversation set of the account be {C1 , C2 , . . . , Cc } with corresponding conversation roots {r1 , r2 , . . . , rc }, where each rj is either an ordinary conversation root MTRcon or a deletion-state conversation root MTRdel con . The account-level Merkle root is defined as MTRacc = MerkleRoot({r1 , r2 , . . . , rc }). Any addition, deletion, or substitution of conversation leaves by the adversary alters the leaf set or leaf order of the account-level Merkle tree, thereby changing MTRacc , unless a hash collision can be constructed. Since a valid account state must simultaneously pass verification under the server signature STRsacc and the user signature STRuacc , the modified account state cannot be forged without access to the corresponding private keys. Any unauthorized modification to the account-level conversation state is therefore detected. 4.4.2

Multi-Device View Consistency Verification

Theorem 4 (State-Transition Authenticity). Whether a device performs an independent single-interaction update or merges increments from other devices via UpdateConversationRecord in a concurrent multi-device setting, a verified account-state root MTRacc and its associated signatures guarantee the authenticity of the corresponding state transition. 39

Proof. During an update or synchronization, the server returns update payload, MerkleProofs, MTRacct+1 , and the server signature STRsacct+1 . Using the locally anchored MTRacct as the baseline, proof-path verification is performed according to the operation type: for NewSession, it is verified that the new MTRcon is incorporated into the account-level Merkle tree; for Append, the old hashtail is verified to be anchored to MTRcont , and the new hashtail , MTRcont+1 , and MTRacct+1 are recomputed; for Branch, the branching point is verified to be anchored to MTRcont via the prior branch tail, and the conversation root and account root after branch insertion are recomputed; for DeleteSession, MTRold con is verified to be the current conversation leaf under MTRacct , and MTRdel and MTR acct+1 are recomputed. In the merge scenario, con concurrent increments being merged have typically already been verified by the corresponding devices and anchored to their then-confirmed account states via user signatures; the server therefore cannot introduce fabricated increments that were never confirmed by any user device. If the server omits, substitutes, or forges any operation-related object, the recomputed MTR′acc will differ from the server-returned MTRacct+1 , or STRsacct+1 will fail verification. Under the assumptions of collision-resistant hashing and unforgeable signatures, no incorrectly anchored update state can be accepted by a device. Theorem 5 (Deletion Serialization and Deletion-Epoch Admission). In a concurrent multi-device setting, VCT prevents deletion operations from producing undecidable merge conflicts with concurrent non-deletion updates. Proof. DeleteSession is modeled in VCT as an account-level serialized operation. A deletion current request must satisfy MTRbase , meaning a deletion may only be submitted against acc = MTRacc the server’s current latest account root. If a deletion request is submitted against a stale account root, the server rejects it per protocol and requires the device to synchronize first. Upon commitment of a deletion, the target conversation root is replaced from MTRold con to the deletiondel state root MTRcon , and a new deletion epoch is established. Subsequently, before accepting any non-deletion update—NewSession, Append, or Branch—the server checks whether the MTRbase acc submitted by the device already reflects the latest deletion state. If the device remains in a prior deletion epoch, the server rejects the update and returns the deletion-state witness. Deletion operations are thereby handled as account-level serialized transitions, and non-deletion updates are admitted to the subsequent merge procedure only after the latest deletion state has been witnessed, preventing undecidable merge semantics between deletion states and concurrent nondeletion updates. Theorem 6 (Merge Determinism). For any set of concurrent non-deletion updates within the same deletion epoch, MergeStates produces a uniquely determined output that is independent of merge ordering. Proof. Per Definition 1 in Section 4.2.3.3, Merge satisfies inclusion, determinism, and conflictfree preservation. Concurrent updates targeting distinct conversations act on different leaves of the account-level Merkle tree; concurrent updates targeting the same conversation are preserved as distinct branches and ordered by deterministic rules—specifically, the initial-node timestamps of branches and the sibling timestamps under each parent node. The merge result depends solely on the input increment set, parent–child relationships, and timestamp ordering rules, and is independent of the order in which the server processes those increments. For any fixed input set, MergeStates therefore produces a uniquely determined merged state. Theorem 7 (Incremental-Replay Rejection). The server cannot cause a device to accept omitted increments without detection by first returning a stale signed state and subsequently delivering those increments in a follow-up synchronization. Proof. Before accepting a synchronization or merge result and issuing a user signature, the device inspects the timestamp set of remote incremental nodes to be accepted in the current response. If any timestampnode satisfies timestampsig < timestampnode ≤ timestampupdate , the node is determined to have been produced before the last synchronization request was initiated but was not incorporated into the latest merged account state previously returned by the server

40

and confirmed by the user; the merge result is accordingly rejected. Since the server cannot forge the user-signature-bound timestampsig or timestampnode , omitted increments cannot be accepted without detection via a strategy of returning a stale state followed by post-hoc delivery. Theorem 8 (View Eventual Consistency and Gossip Accountability). Upon execution of the gossip protocol, VCT satisfies the following dichotomy: either all devices belonging to the same user eventually converge to the same account state, or two devices exist that hold distinct account roots each bearing valid dual signatures, thereby constituting publicly verifiable fork evidence. Proof. All conversation states under the same account are aggregated into the account-level Merkle root MTRacc , which is confirmed by dual signatures from the server and the user. During synchronization, the server merges non-deletion updates from the same deletion epoch that the device has not yet witnessed into the device’s account view via MergeStates, and completes state-transition proof verification and dual-signature confirmation via Algorithm 1. If the server returns state transitions honestly, all devices eventually converge to the same MTRacc . If incompatible account states are served to different devices, those devices exchange and verify their respective (MTRacc , STRuacc , STRsacc ) tuples during gossip. Whenever two devices hold distinct values of MTRacc , the two valid but differing dual-signed account roots constitute fork evidence. Since the server cannot forge user signatures and cannot repudiate its own, the evidence is non-repudiable and suitable for accountability. 4.4.3

Shared Transcript Integrity Verification

Theorem 9 (Share Package Authenticity). Every shared Q&A node contained in a share package is verifiable as originating from an account state jointly confirmed by the user and the server; no unauthenticated content can be inserted into a share package by the server without detection. Proof. Per Section 4.2.4, the provenance proof package is defined as proof = {selected nodes, MerkleProofs, MTRacc , STRsacc , STRuacc }. Prior to generating the sharing snapshot, the server signature STRsacc and the user signature STRuacc are verified by the user device, confirming that the account root MTRacc has been mutually confirmed by both parties. The MerkleProofs are then used to verify that each node to be shared belongs to the conversation structure authenticated by that account state and is ultimately anchored to MTRacc . If the server attempts to insert a fabricated node N ′ that does not appear in the account history, a valid Merkle inclusion proof for N ′ must be produced. Since N ′ did not participate in the computation of MTRacc , verification fails unless the server can construct a forged Merkle proof or find a hash collision. Furthermore, if the server attempts to fabricate a new account root that incorporates N ′ , a valid user signature STRuacc over that root must also be forged, which contradicts the existential unforgeability of the signature scheme. Under the assumptions of collision-resistant hashing and unforgeable signatures, every shared node in a share package is therefore verifiable as originating from an account state jointly confirmed by the user and the server, and no unauthenticated content can be inserted by the server. Theorem 10 (Sharing Snapshot Integrity). Once a sharing snapshot is generated, its verification is independent of the subsequent state of the original conversation tree; any modification, deletion, reordering, or omission of content in the share package is detected by the recipient R upon verification. Proof. The sharing protocol reorganizes selected nodes into an independent share chain and produces the chain tail sharetail . Subsequent appends, branches, or deletions in the original conversation tree affect only later values of MTRcon or MTRacc and do not participate in the

41

recomputation of an already-generated sharetail . Once a sharing snapshot is generated, its verification object is therefore decoupled from the original conversation tree. During verification, the recipient R recomputes the share chain tail share′tail according to the share-chain construction rules, checks that share′tail = sharetail , and verifies sharessig and shareusig . Any content modification, node deletion, reordering, or omission from the signed share set alters share′tail . If the adversary simultaneously replaces sharetail , valid signatures from both the server and the user over the new sharetail must be forged, which contradicts the unforgeability of the signature scheme. Any tampering, reordering, deletion, or omission within a signed sharing snapshot is therefore detected. 4.4.4

Non-repudiation of Commitments

Theorem 11 (Operation Non-repudiation). Any conversation update, state merge, session deletion, or share generation that has been confirmed by both parties is cryptographically nonrepudiable. Proof. Account state-transition confirmation is accomplished through dual signatures: the server produces STRsacc over the account root MTRacc , and the user device, upon successful state-transition verification, produces STRuacc over the same MTRacc . State merges reuse the same account state-transition confirmation procedure. Session deletion produces the deletionstate conversation root MTRdel con , which is jointly confirmed by both parties via signatures over the new account root MTRacc . For sharing snapshots, sharessig and shareusig are produced by the server and the user, respectively, over the independent share chain tail sharetail . Since the signature scheme satisfies existential unforgeability [33, 38, 39], STRsacc and sharessig can only be produced under the server private key, and STRuacc and shareusig can only be produced under the user private key. Each signature is bound directly to the account root MTRacc or the share chain tail sharetail ; any modification to an operation outcome or shared content causes signature verification to fail. Neither the user nor the server can therefore repudiate any operation or its bound content that has been confirmed. 4.4.5

Summary of Security Guarantees Table 8: Summary of Security Properties

Security Property

Mechanism and Final Anchor

Cryptographic Assumptions

Node Integrity

parent hash hash chain; recomputation of tail hashtail → anchors to STRacc (hashtail → MTRcon → MTRacc ) Conversation-level Merkle tree over hashtail → anchors to STRacc (MTRcon → MTRacc )

Collision-resistant hash + Unforgeable signatures Collision-resistant hash + Unforgeable signatures Collision-resistant hash + Unforgeable signatures Collision-resistant hash + Unforgeable signatures

Conversation tegrity

In-

Account Integrity

Account-level Merkle tree + STRsacc /STRuacc → anchors to MTRacc

State-Transition Authenticity

MerkleProofs + local recomputation + root reconstruction + dual-signature verification → ans u chors to MTRnew acc /STRacc /STRacc

Continued on next page

42

Table 8: Summary of Security Properties (continued) Security Property

Mechanism and Final Anchor

Cryptographic Assumptions

Deletion tion

Serializa-

DeleteSession requires MTRbase = MTRcur acc acc ; post-deletion new epoch formed with MTRdel con → anchors to MTRdel /MTR /dual signatures acc con

Merge Determinism

MergeStates + deterministic ordering + branch preservation → anchors to merged MTRacc + dual signatures

Incremental-Replay Rejection

Rejection of remote increments satisfying timestampsig < timestampnode ≤ timestampupdate → anchors to synchronization boundary and set of accepted increments Device synchronization + gossip exchange and verification of (MTRacc , STRuacc , STRsacc ); divergent roots produce fork evidence → anchors to consistent MTRacc or two distinct dual-signed roots

Protocol check + Collision-resistant hash + Unforgeable signatures Deterministic ordering + Collisionresistant hash + Unforgeable signatures Unforgeable signatures

View Consistency and Gossip Accountability

Share Authenticity

Share Integrity

Dual-signed MTRacc ; MerkleProofs prove nodes belong to that state → anchors to MTRacc + dual signatures Reorganize selected nodes into independent hash chain; recompute sharetail and verify dual signatures → anchors to sharetail /sharessig /shareusig

5

Experimental Evaluation

5.1

Prototype System and Evaluation Scope

Unforgeable signatures + Collisionresistant hash + Gossip channel security + eventual synchronization Collision-resistant hash + Unforgeable signatures Collision-resistant hash + Unforgeable signatures

A prototype system is implemented in Python to evaluate the protocol overhead and securitygoal achievability of VCT. The prototype employs standard cryptographic libraries—SHA-256, Ed25519, and PBKDF2-HMAC-SHA256—and realizes the core protocol paths defined in Section 4, including Q&A node hash chains, conversation-level and account-level Merkle trees, the four state-update operations, multi-device synchronization, gossip-based fork detection, and the verifiable sharing protocol. Account-state objects in the prototype are kept consistent with the formal model. Q&A nodes form branch hash chains via parent hash; each conversation constructs MTRcon from the hashtail values of its internal branches; the account layer constructs MTRacc from the conversation roots or deletion-state conversation roots, with dual signatures issued separately by the server and the user. Multi-device synchronization employs deterministic merging of non-deletion updates; deletion operations follow the account-level serialization rules; the sharing procedure reorganizes selected nodes into an independent share chain with appended dual signatures. It should be noted that the account state-update protocol is designed such that the server recomputes only the Merkle path from the affected leaf to the root when updating MTRacc . For implementation simplicity, the current prototype adopts linear recomputation or cache-flush

43

updates on the server side. The experimental results therefore reflect end-to-end overhead under a conservative server-side implementation rather than the theoretical optimum achievable with incremental Merkle maintenance.

5.2

Experimental Setup

Platform. All experiments are conducted on an Intel Core i7-13700H (2.40 GHz, 14 cores / 20 threads) with 32 GB RAM, a 256 GB NVMe SSD, and Windows 11 (10.0.26200). Measurements cover only the cryptographic computation and in-memory processing of VCT, excluding LLM inference, network I/O, persistent storage I/O, and client-side rendering. Cryptographic and Merkle Configuration. The prototype instantiates SHA-256 [40] (32byte digest, represented as 64 hexadecimal characters) and the Ed25519 digital signature algorithm [41, 42] (32-byte public and private keys, 64-byte signatures). The KDF is instantiated as PBKDF2-HMAC-SHA256 [34, 43]. The Merkle tree follows the recursive binary tree structure of RFC 6962, with leaves as pre-hashed commitments and internal nodes aggregated as Hash(left∥right). Only the tree structure of RFC 6962 is adopted; the leaf and internal-node domain-separation prefixes (0x00 and 0x01) are not used, so the results do not guarantee interoperability with RFC 6962 implementations. The empty-tree root is defined as the fixed constant ZERO HASH = "0" × 64, serving solely as an implementation placeholder. Measurement Methodology and Latency Definition. Timing measurements are based on a monotonic clock with microsecond precision. Unless stated otherwise, each experimental configuration is repeated independently 50 times, and results are reported as the sample mean with sample standard deviation. State-Update Operation Latency (End-to-End). For account state-update operations—NewSession, Append, Branch, DeleteSession, and Merge—latency is defined as the end-to-end time required to complete one logical operation, denoted Te2e and computed as: Te2e = tlocal + tP 1 + tP 2 + tP 3 , where tlocal is the time to execute the account state transition in memory (or the merge computation along the merge path); tP 1 is the server-side time to compute MTRacc over the updated account state, generate the state-transition proof (update payload and MerkleProofs), and issue STRsacc ; tP 2 is the user-side time to verify the state-transition proof and STRsacc and to issue STRuacc ; and tP 3 is the server-side time to verify STRuacc and for both parties to commit the current account state. Nested sub-timings within Te2e are reported separately for Merkle- and signature-related overhead: • Merkle: nested sub-timing covering server-side account root recomputation and deviceside Merkle proof verification. • Verify: nested sub-timing covering Ed25519 signature verification of STRsacc and user signing of STRuacc . Other Protocol Operation Overhead. • Gossip: the latency of a single fork-detection round is measured, comprising four Ed25519 signature verifications over the account anchor digests of both devices (STRsaccA , STRuaccA , STRsaccB , STRuaccB ) and one MTRacc comparison. • Verifiable sharing: share generate covers independent share chain construction and dual signing of the sharing snapshot; verify share covers recipient-side recomputation of sharetail and verification of sharessig and shareusig . 44

• Merkle proof: inclusion proof sizes (in bytes) are reported at fixed sampling points on the terminal accumulated account state; proof sample at scale additionally measures proof generation latency at the same positions. Reproducibility. Experiment timestamps are simulated using monotonically increasing integers. The modelconfig of each Q&A node is fixed as {"model id" : "eval", "temperature" : 0.0}, and file aux info is set to an empty dictionary in all synthetic workloads. The conversation creation time created at is taken from the timestamp of the first node; account-level conversation ordering follows (created at, session id), where session id serves as a stable tiebreaker to ensure deterministic Merkle tree construction at all levels during merging.

5.3

Experimental Workloads and Security Test Coverage

Three progressively scaled workloads—Basic, Medium, and Large—are defined to evaluate the functional correctness, security-goal coverage, and scalability of VCT across different account sizes. All three workloads employ a consistent protocol feature set and security test matrix, but differ in the number of Q&A pairs, conversations, and operation executions, serving respectively to assess the intrinsic overhead of individual protocol components and the scalability under accumulated account states. Isolated-operation baseline. This baseline measures the end-to-end intrinsic overhead of individual protocol operations under a minimal account state. NewSession is measured against an empty account state; all other update and verification operations are executed against an account state containing a single existing conversation. The baseline is designed to isolate the fundamental costs of cryptographic confirmation, Merkle root computation, and signature verification. Scaled baseline. The same set of protocol operations is measured against the accumulated account state formed by each workload, yielding trends in latency, storage overhead, and Merkle proof size as a function of account scale. Table 9: Experimental workload configurations Workload

Sessions

Total Q&A

Avg Q&A / session

Core operations and counts

Basic

5

25

5

Medium

20

100

5

Branch commit ×2; session deletion ×1; remote append merge ×2; parallel branch merge ×1; deletion-epoch rejection detection ×1; session sharing ×1; gossip consistency ×1; gossip fork ×1; gossip invalid signature ×1; lagging-device detection ×1; fork evidence size check ×1 Branch commit ×5; session deletion ×4; remote append merge ×5; parallel branch merge ×1; deletion-epoch rejection detection ×1; session sharing ×5; gossip consistency ×10; gossip fork ×5; gossip invalid signature ×5; lagging-device detection ×1; fork evidence size check ×1 Continued on next page 45

Table 9: Experimental workload configurations (continued) Workload

Sessions

Total Q&A

Avg Q&A / session

Core operations and counts

Large

100

500

5

Branch commit ×10; session deletion ×20; remote append merge ×10; parallel branch merge ×1; deletion-epoch rejection detection ×1; session sharing ×5; gossip consistency ×25; gossip fork ×10; gossip invalid signature ×10; lagging-device detection ×1; fork evidence size check ×1

Table 5.2 summarizes the correspondence between VCT security goals and specific test cases. Table 10: Security goals and test coverage Security goal

Test operations

Integrity

Message append, branch creation, session deletion, content removal of deleted sessions, Merkle path verification from Q&A nodes to account root Remote append merge, parallel branch merge, deletion strict-freshness check, deletion-epoch check, omitted-interval incremental replay, final view consistency check, fork evidence size verification Provenance proof verification, independent share chain verification, share chain node tampering and omission, chain-tail signature substitution Account root dual-signature verification, share chain tail dual-signature verification, signed payload tampering

Multi-device consistency and fork detection

Share verifiability

Non-repudiation

Experimental results demonstrate that across all three workloads, all security functional tests satisfy the expected protocol outcomes. VCT correctly maintains the complete authentication chain from Q&A nodes through branch tails, conversation roots, and account roots. In concurrent multi-device settings, all valid concurrent increments are deterministically merged, deletion operations are serialized, increments falling within the signed timestamp boundary are rejected, and account-view consistency is detected via gossip. The independent share chain supports independent verification of selectively disclosed nodes and detects modifications, omissions, reorderings, and chain-tail signature substitutions in shared content. These results demonstrate that the hash binding, Merkle authentication structure, dual signatures, deterministic merging, freshness checks, gossip detection, and independent share chain mechanisms of VCT collectively support the core security goals defined in this work across varying account scales.

5.4

Minimal-State Operation Overhead

To characterize the intrinsic overhead of individual VCT protocol operations, latency is measured in this section under a minimal-state context. Specifically, NewSession is executed against an empty account state, and all other operations are executed against a minimal account state containing a single existing conversation. The results in this section therefore reflect 46

per-operation protocol costs under a minimal account state and are intended to characterize intrinsic overhead; scalability under accumulated account states is analyzed further in Section 5.5.

Figure 9: Minimal-state operation latency (N = 50, synthetic payload). Account updates (including merge) report end-to-end latency Te2e . Gossip and sharing are measured as standalone primitives. Share operations use 2 nodes per trial without owner proofs. As shown in Figure 5.1, all protocol operations under the minimal account state fall within the sub-millisecond to low-millisecond range. The mean latency of NewSession, Append, Branch, DeleteSession, Merge, and Gossip is concentrated in approximately 0.26–0.31 ms; share generate (0.068 ms) and verify share (0.17 ms) exhibit lower absolute latency. These results indicate that the basic operations of the VCT protocol do not introduce significant interaction latency. To identify the dominant sources of per-operation overhead, Figure 5.2 compares the perphase latency of the four core update operations, together with the nested Merkle and Verify sub-timings within each phase.

Figure 10: Protocol latency breakdown of core update operations. This figure exclusively decomposes protocol-layer cryptographic and synchronization overhead and does not include tlocal —the latency of in-memory state modifications. Error bars represent standard deviation across 50 repeated trials. Component-level results indicate that Ed25519 signing and verification constitute a stable and relatively dominant source of cryptographic overhead; Merkle-related costs are comparatively low, as the device side executes only logarithmic-depth proof-path verification. Under the 47

minimal account state, the baseline latency of VCT is therefore dominated by dual-signature confirmation rather than by hierarchical state-structure transitions.

5.5

Cross-Scale Performance Evaluation

This section evaluates the scalability of the current prototype under accumulated account states. Unlike the isolated-operation baseline of Section 5.4, all operations in this section are executed across the Basic, Medium, and Large account scales to analyze the impact of account-state growth on protocol latency. 5.5.1

Scalability Trends for Account-State-Transition Operations

To assess the impact of account-state scale on state-transition operations, Figure 11 compares the latency of NewSession, Append, Branch, DeleteSession, Merge, and proof sample across account states of 5, 20, and 100 conversations. All of these operations directly or indirectly depend on account-level Merkle root updates or account-level proof generation, and therefore capture the primary performance bottlenecks of the current prototype as account state scales.

Figure 11: Scalability trends for account-root-modifying operations (N = 50, synthetic payload). Account sizes range from 5 to 100 conversations. As shown in Figure 11, the end-to-end latency of NewSession, Append, Branch, and DeleteSession increases with account scale, reaching approximately 6.8–7.4 ms at the Large scale. The growth is most pronounced for Merge: approximately 4.4 ms at Medium scale and approximately 18.5 ms at Large scale, representing roughly 2.6× and 2.7× the latency of Append at the corresponding scales. This disparity stems from the account-level batch semantics of Merge: concurrent modifications from multiple devices are first aligned and consolidated into a unified account state; the account-level and conversation-level Merkle roots are then recomputed, and separate Merkle inclusion proofs are generated for each conversation whose content has changed; the device side must further verify multiple transition proofs and complete dual-signature confirmation. By contrast, proof sample measures only the cost of generating Merkle inclusion proofs at fixed sampling points—the terminal conversation root and the first active branch tail—on the accumulated account end state, remaining at approximately 2.5 ms at the Large scale. This result indicates that proof-path overhead scales primarily with Merkle tree depth rather than linearly with the full account state; the latency of a single conversation update is dominated by the update to the affected branch or conversation root, account-root reconstruction, transition proof generation, and dual-signature confirmation. Merge additionally incurs the cost of 48

multi-conversation consolidation and multi-path account-level proof generation, making it the primary latency contributor in large-scale settings. 5.5.2

Lightweight Security Operation Overhead

To distinguish the performance characteristics of account-state-modifying operations from those of digest-oriented verification operations, Figure 5.4 compares the latency of gossip, share generate, and verify share across three account scales. These operations depend primarily on accountroot digests, signed states, or independent share chains, and do not require traversal of the full account state.

Figure 12: Scale experiment for verification-oriented operations (N = 50, synthetic payload). The account scale varies from 5 to 100 sessions. gossip at scale verifies only account roots and their dual signatures; sharing operations use public share packages containing 20 selected nodes and omit owner proofs. As shown in Figure 12, gossip, share generate, and verify share remain stable across account scales of 5, 20, and 100 conversations. Gossip latency ranges from 0.31 to 0.34 ms, while share generate and verify share remain approximately 0.15 ms and 0.23–0.24 ms, respectively. These results indicate that digest-oriented security operations exhibit weak dependence on account scale: gossip exchanges and verifies only account roots and dual signatures, whereas share generation and verification construct an independent hash chain from the shared nodes without traversing the full account tree. Taken together, Figures 11 and 12 show that scale-sensitive overhead in the current prototype is concentrated in account-state merging, server-side account-state transitions, and transitionproof generation. In contrast, gossip and public share-package verification maintain low latency with negligible growth as account scale increases. Future engineering optimizations should therefore focus primarily on the Merge path—specifically, conversation-root indexing, hashtail caching for unmodified branches, and incremental Merkle-tree maintenance based on intermediate-node caching—so that account-root recomputation is confined to the authentication path from the affected leaf to the root, rather than on gossip or share-verification procedures.

5.6

Storage Overhead and Merkle Proof Size

To evaluate the storage overhead introduced by security metadata and Merkle proofs under synthetic workloads, Figure 13 reports the total volume of security metadata together with the sizes of account-level and conversation-level inclusion proofs measured at fixed sampling 49

positions in the final account states of the Basic, Medium, and Large workloads. Security metadata encompasses Q&A node hashes, conversation roots, account roots, dual signatures, and historical account-root metadata. Proof sizes are sampled at fixed positions, namely the last conversation root in the account tree and the first active branch leaf of the first active conversation, after each workload reaches its final state.

Figure 13: Storage overhead and Merkle proof size: (a) security metadata volume; (b) accountlevel and conversation-level proof sizes. As shown in Figure 13(a), security metadata grows steadily with the number of nodes and conversations under the synthetic short-text workload. Since the synthetic Q&A content is extremely short, the ratio of metadata to plaintext is substantially amplified (approximately 3:1 across all three workloads). This ratio should not be extrapolated directly to real-world long-text deployments. The experiment is more appropriately interpreted as characterizing the growth trend of metadata as a function of state scale rather than as an estimate of its absolute storage proportion. As shown in Figure 13(b), account-level proof size grows sub-linearly with the number of conversations, increasing from 64 B to 192 B and 256 B. Conversation-level proof size remains at 64 B across all three scales, since the fixed sampling position targets the first active conversation whose branch structure is identical across all workloads. This result reflects a key design property of the hierarchical Merkle structure adopted by VCT: account-level proof size scales primarily with the depth of the account tree, while conversation-level proof size is determined by the branch structure within a single conversation and is largely decoupled from the total number of conversations in the account. A verifier therefore requires only the proof path relevant to the target position rather than the complete account state. Verification can be completed using local authentication information without reconstructing the entire account-level Merkle structure.

5.7

Real-Payload Evaluation

To evaluate the impact of conversation content length on performance and storage proportion, two payload configurations are compared under the Medium workload (20-session accumulated account state). The synthetic payload uses minimal placeholder Q&A content and omits the file aux info attachment field, resulting in approximately 41 B of plaintext per node. This configuration is intended to highlight the fixed protocol overhead introduced by hashing, signing, and authenticated-state maintenance. In contrast, the real payload populates Q and A with approximately 4 KB and 16 KB of content, respectively, and attaches approximately 512 B of file metadata per node (including filename, MIME type, SHA-256 digest, and related fields), yielding approximately 21 KB of plaintext per node. This configuration more closely reflects the content volume of practical LLM conversations. 50

Figure 14: Real-payload evaluation: latency comparison between synthetic and real workloads. Storage measurements show that security metadata occupies 20,896 B under both payload configurations. This metadata is determined primarily by fixed structures such as node hashes, conversation roots, account roots, dual signatures, and associated state metadata, and is therefore largely independent of Q&A content length. In contrast, total plaintext volume increases from approximately 7 KB to approximately 2.30 MB, causing the metadata-to-plaintext ratio to decrease from approximately 299% to approximately 0.9%. These results indicate that the elevated metadata ratio observed under the synthetic workload arises from the extremely short placeholder content rather than from any intrinsic inflation of the security metadata itself. In realistic long-text deployments, VCT security metadata grows approximately linearly with conversation scale while remaining a small fraction of the overall conversation content. Figure 14 further characterizes the impact of payload size on protocol latency. Compared with the synthetic workload, real Q&A content increases Merge latency from approximately 4.4 ms to approximately 58.3 ms, and increases the latency of NewSession, Append, Branch, and DeleteSession from approximately 1.7–1.8 ms to approximately 8.5–9.1 ms. This increase is attributable primarily to content-dependent node hashing and branch-tail recomputation. Larger Q&A payloads increase the size of hash inputs and therefore raise the computational cost of updating chain tails along affected branches. In contrast, conversation-level and account-level Merkle trees, together with their authentication paths, operate on fixed-length hash values. Their overhead is determined primarily by the number of branches, the number of conversations, and the scope of state changes, rather than by content length. The amplification is most pronounced for Merge, which additionally requires multi-branch tail recomputation, multiconversation consolidation, account-root reconstruction, and corresponding proof generation. By comparison, gossip latency remains approximately 0.31 ms under both payload configurations because only account roots and dual signatures are exchanged and verified, with no dependence on conversation content. Among the sharing-related operations, share generate and verify share rely on an independent share chain and snapshot dual signatures and likewise do not require traversal of the full account tree. Under the real payload, their latencies are approximately 1.53 ms and 1.52 ms, respectively, compared with approximately 0.15 ms and 0.24 ms under the synthetic workload. The increase arises primarily from recomputation of share-chain hashes over larger shared nodes. Even so, their absolute latencies remain substantially lower than those of account-state update operations under the real workload. Overall, the primary performance bottleneck of VCT in practical deployments is associated with processing conversation content rather than maintaining authenticated state structures. Gossip and share-verification operations exhibit negligible or only mild sensitivity to payload size and therefore retain favorable deployment characteristics even under realistic workloads.

51

5.8

Experimental Discussion

This chapter presents a systematic evaluation of the functional correctness, security-goal coverage, and performance characteristics of the VCT prototype across three progressively scaled workloads—Basic, Medium, and Large—and two payload configurations—synthetic and real. The experimental results support the following observations. Functionality and Security. The prototype successfully implements the core mechanisms of three-layer state assertions, multi-device state merging, gossip-based fork detection, and verifiable sharing. Across all experimental configurations, the designed test cases covering integrity, consistency, non-repudiation, and share verifiability are satisfied. These results provide implementation-level evidence that the protocol achieves its intended security objectives and is practically deployable. Intrinsic Protocol Overhead. Under minimal account-state and short-text workloads, the latency of the core protocol primitives remains predominantly in the sub-millisecond range. This indicates that fixed cryptographic operations—including signature verification, proof validation, digest-oriented gossip, and independent share-chain verification—do not constitute a major source of end-to-end protocol latency. Subsequent performance variation is attributable primarily to account scale, conversation content volume, and merge-path complexity. Scalability Characteristics. As the number of conversations increases, the latency of singleconversation state updates and Merge grows most noticeably, with Merge emerging as the dominant bottleneck under large-scale workloads. In contrast, gossip and sharing-related operations exhibit only limited sensitivity to account scale and maintain relatively stable latency across all tested configurations. Storage and Proof Overhead. Security metadata grows approximately linearly with the number of conversations. Account-level and conversation-level proof sizes are bounded primarily by account-tree depth and single-conversation branch structure, respectively, and therefore do not scale with the size of the complete account state. Under realistic payloads, the ratio of metadata to conversation content is substantially lower than under synthetic short-text workloads, indicating that the cryptographic assertions introduced by VCT impose only modest storage overhead in practice. Real-Payload Behavior and Optimization Directions. Conversation content volume is the primary performance-sensitive factor in realistic deployments. State-update paths are affected most significantly, with Merge exhibiting the largest amplification effect. By contrast, anchor verification and gossip are essentially unaffected by payload size, while sharing operations exhibit only mild sensitivity. Future optimizations should therefore focus on branch-tail caching, incremental merge processing, and server-side incremental Merkle-tree maintenance rather than on the dual-signature mechanism or digest-exchange procedures themselves. Overall, the experimental results provide evidence that VCT achieves its functional and security objectives while maintaining manageable overhead under both scaled workloads and realistic payload conditions. Further reductions in latency and storage overhead remain achievable through engineering optimizations such as branch-tail caching, incremental merge processing, and incremental Merkle maintenance.

6

Discussion and Future Work

6.1

Scope and Limitations

The primary objective of VCT is to provide verifiable authenticity, integrity, and accountability for large language model conversation records. The protocol enables users to verify whether a given conversation state has been correctly generated, stored, synchronized, and shared, and to detect unauthorized tampering with conversation history.

52

VCT does not, however, attempt to verify the factual correctness, reasoning validity, or semantic quality of model-generated responses. The protocol guarantees that a response has been faithfully recorded and cryptographically anchored to a signed account state, but provides no evidence regarding the correctness of the response content itself. VCT should therefore be understood as a conversation-record verification framework rather than a verifiable reasoning framework. In multi-device settings, VCT adopts eventual-consistency semantics: account consistency is established primarily through verifiable synchronization between devices and the server and through Merge commits, while gossip is employed for fork detection and reconciliation across multi-device views. Prior to synchronization completion, transient inconsistencies may exist between the local views of different devices; under the assumption that honest devices eventually complete synchronization with the server and participate in gossip, the system achieves eventual convergence while preserving an accountable operation chain. Security metadata accumulates over prolonged use. Account state assertions, dual signatures, and deletion-related records must be retained to support auditability and verifiability; the total volume grows near-linearly with the number of conversations and the frequency of state commits. The evaluation in Section 5 demonstrates that, under real long-text workloads, the ratio of security metadata to conversation content is low; however, this result is based on the Medium workload end state and does not cover long-retention or high-commit-frequency scenarios representative of extended operation. Long-term deployments may require checkpointing, archiving, or pruning mechanisms, which must be designed without compromising the verifiability of historical states. Several limitations exist at the experimental and prototype levels. The current implementation does not incorporate branch-tail caching, incremental merge indexing, or server-side incremental Merkle maintenance; the latency results in Section 5 should therefore be interpreted as a characterization of prototype-level performance rather than as a lower bound on what optimized implementations can achieve. Performance evaluation is conducted primarily through local prototype execution, excluding network round-trip latency, model inference delay, and productionlevel concurrency pressure; synthetic short-text workloads are used to highlight fixed protocol overhead, and the real-payload comparison is conducted only under the 20-session accumulated account state. Security analysis is carried out under standard assumptions—collision-resistant hashing, unforgeable signatures, and honest-but-curious participants—and does not cover malicious collusion, side-channel attacks, or availability threats that fall outside the scope of the formal proof.

6.2

Design Trade-offs

Several design choices in VCT deliberately prioritize auditability and verifiability over stronger consistency semantics or higher concurrent throughput. First, DeleteSession is modeled as an account-level serialized state transition rather than an operation eligible for concurrent merging alongside non-deletion updates. Before initiating a deletion, a device must synchronize to the latest account root; non-deletion updates must be submitted against an account anchor within the current deletion epoch to prevent ambiguous merge semantics between deletions and concurrent updates. This design reduces concurrency in deletion-intensive scenarios but eliminates semantic conflicts between deletions and concurrent updates, and guarantees determinism in account-state evolution. Second, account state transitions in VCT are confirmed by dual signatures from the user and the server. Compared with a server-only logging approach, this introduces additional communication and storage overhead; the resulting account states are, however, non-repudiable from both parties’ perspectives and provide stronger evidentiary value for subsequent verification, synchronization, and sharing. Under real payloads, the ratio of fixed-structure security metadata to conversation content is substantially lower than under the synthetic short-text 53

workload, indicating that the relative storage burden introduced by dual signing is acceptable under deployment conditions. Third, the protocol adopts a hierarchical Merkle tree structure at the conversation and account levels. This structure incurs additional metadata and proof-generation costs, but enables a verifier to perform local verification without access to the full account state. Evaluation results indicate that proof size scales primarily with Merkle tree depth rather than linearly with conversation content volume; under a fixed sampling strategy, conversation-level proof length is determined by the branch structure within a single conversation and grows logarithmically with the number of branches, largely decoupled from the total number of conversations in the account. Overall, VCT trades moderate metadata and synchronization overhead for auditability, verifiable synchronization, and evidentiary integrity. The experiments in Section 5 support the deployability of this trade-off under scaled and real-payload conditions.

6.3

Future Directions

The following directions are identified as avenues for further improving the practicality and scalability of VCT. Verifiable History Compression and Checkpointing. Cryptographic checkpointing and metadata pruning of distant historical states warrant investigation, subject to the constraint that deletion barriers and checkpoint root verifiability are preserved. Such mechanisms would bound storage growth for long-lived accounts without compromising auditability or accountability. Incremental Maintenance of State Updates. As demonstrated in Section 5, repeated recomputation during account state transitions constitutes the primary scalability bottleneck, most notably for Merge commits. Under the existing merge semantics and deletion-epoch constraints, branch-tail caching, changed-conversation indexing, and incremental Merkle tree maintenance are promising directions, with the goal of limiting state updates to recomputation along affected paths only. Integration with Verifiable Reasoning. VCT guarantees the provenance and state evolution of conversation records but does not cover the correctness of model reasoning. Combining VCT with verifiable reasoning, model execution environment attestation, and verifiable proofs of inference processes could yield end-to-end assurance spanning both whether a conversation has been faithfully recorded and whether the model generation process is auditable, thereby extending verifiability from conversation history to model behavior itself. Production-Scale Evaluation and Deployment Validation. Future work should reproduce the benchmarks of this chapter under larger account sizes, real network conditions, and full long-text workloads, and assess the impact of operational requirements—including archiving strategies, key rotation, and compliance-driven retention—on protocol overhead and security boundaries.

7

Conclusion

This paper addresses the verifiability of large language model interaction records and proposes the Verifiable Conversation Transcript system, VCT. Unlike conventional logging systems, transparency logs, or secure messaging protocols, VCT does not aim to record a linear event sequence; instead, an independently verifiable account-level authenticated state is established over dynamically evolving LLM conversation states. The design targets the distinctive characteristics of LLM conversations—including Q&A atomic structure, history-node-based editing, response regeneration, legitimate branching, session deletion, multi-device concurrency, and selective sharing—and provides unified mechanisms for integrity, consistency, share verifiability,

54

and non-repudiation. VCT adopts a three-layer verifiable structure. At the interaction layer, each Q&A pair is modeled as a hash-chain node. At the conversation layer, branch tails are used to construct a conversation-level Merkle root. At the account layer, all conversation roots under an account are further aggregated into an account-level Merkle root, jointly confirmed by dual signatures from the user and the server. This structure preserves legitimate intra-conversation branches without collapsing all interactions into a single linear log. Building on this foundation, VCT defines a state-update protocol, deletion serialization rules, a multi-device state-merge protocol, a gossip-based fork detection mechanism, and a verifiable sharing protocol. Deletion serialization prevents semantic conflicts between deletion states and ordinary concurrent increments. The gossip protocol detects inconsistent views served by the server through cross-device exchange of dual-signed account roots. The sharing protocol reorganizes the user-confirmed set of shared nodes into an independent hash chain, over whose tail dual signatures are produced, enabling recipients to verify that nodes in the public share package have not been tampered with, omitted, reordered, or substituted. Security analysis demonstrates that, under standard assumptions of collision-resistant hashing, unforgeable digital signatures, and secure key derivation, VCT achieves integrity, consistency, share verifiability, and operation non-repudiation. Experimental evaluation further validates the practical achievability of the design: core operations on the prototype under minimal account states remain in the sub-millisecond to low-millisecond range; all cross-scale security tests pass; gossip and share verification exhibit negligible growth with account scale; and storage and proof overhead remain manageable. Under real long-text workloads, the ratio of security metadata to conversation content decreases substantially; however, state-update and Merge latency increase noticeably as conversation content volume and account scale grow. This increase is attributable primarily to branch-tail recomputation, Merkle root updates, and multi-conversation consolidation in Merge, rather than to fixed cryptographic primitives such as signature verification and proof checking. Overall, VCT provides a verifiable infrastructure for LLM interaction records oriented toward forensic, audit, and accountability-tracing scenarios, enabling third parties to verify the authenticity and integrity of conversation records without placing full trust in the platform server.

References [1] Jiawei Li, Yu Gao, Yifan Yang, Zhongyi Zhang, Xiaojie Yuan, Jie Tang, and Juanzi Li. Fundamental capabilities and applications of large language models: A survey. ACM Computing Surveys, 58(2):38:1–38:45, 2025. [2] Yifan Ye, Zhen Zhang, Tianyi Ma, Fangrui Liu, Haotian Zhang, Shiyu Zhao, and Yang Liu. LLMs4All: A systematic review of large language models across academic disciplines. arXiv preprint, arXiv:2509.19580, 2025. [3] Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, and Ting Liu. A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions. ACM Transactions on Information Systems, 2025. [4] Stephen Embry. Proposed evidentiary rule 707: Addressing a nonexistent problem instead of real ones. Above the Law, January 2026. [5] United Nations Office on Drugs and Crime. Cybercrime module 6: Key issues — digital evidence admissibility, 2017. Education for Justice Initiative.

55

[6] Mark Scanlon, Frank Breitinger, Christopher Hargreaves, Jan-Niclas Hilgert, and John Sheppard. ChatGPT for digital forensic investigation: The good, the bad, and the unknown. Forensic Science International: Digital Investigation, 46:301609, 2023. [7] United states v. rinderknecht, criminal complaint and affidavit in support of criminal complaint. Case No. 2:25-mj-01161, C.D. California, January 2025. [8] Garcia v. character technologies, inc. No. 6:24-cv-01903-ACC-DJK, M.D. Florida, May 2025. [9] Raine v. openai, complaint. No. 3:25-cv-04827, N.D. California, August 2025. [10] Stuart Haber and W. Scott Stornetta. How to time-stamp a digital document. Journal of Cryptology, 3(2):99–111, 1991. [11] Anvar p.v. v. p.k. basheer & ors. (2014) 10 SCC 473, Supreme Court of India, 2014. [12] International Organization for Standardization. ISO/IEC 27037:2012 — information technology — security techniques — guidelines for identification, collection, acquisition and preservation of digital evidence, 2012. [13] Bruce Schneier and John Kelsey. Secure audit logs to support computer forensics. ACM Transactions on Information and System Security, 2(2):159–176, 1999. [14] Mihir Bellare and Bennet S. Yee. Forward integrity for secure audit logs. Technical Report CS98-580, University of California at San Diego, November 1997. [15] Jason E. Holt. Logcrypt: Forward security and public verification for secure audit logs. In Proceedings of the 15th USENIX Security Symposium, pages 53–62, 2006. [16] Di Ma and Gene Tsudik. A new approach to secure logging. In Proceedings of the 24th IFIP International Information Security Conference (SEC 2009), pages 48–62, 2009. [17] Ralph C. Merkle. A digital signature based on a conventional encryption function. In Advances in Cryptology — CRYPTO ’87, volume 293 of Lecture Notes in Computer Science, pages 369–378. Springer, 1987. [18] Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos. Authenticated data structures for outsourced databases. Information Systems, 36(2):195–214, 2011. [19] Andrew Miller, Michael Hicks, Jonathan Katz, and Elaine Shi. Authenticated data structures, generically. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 411–424, 2014. [20] Ben Laurie, Adam Langley, and Emilia Kasper. Certificate transparency. RFC 6962, 2013. [21] Marcela S. Melara, Aaron Blankstein, Joseph Bonneau, Edward W. Felten, and Michael J. Freedman. CONIKS: Bringing key transparency to end users. In Proceedings of the 24th USENIX Security Symposium, pages 383–398, 2015. [22] Katriel Cohn-Gordon, Cas Cremers, Benjamin Dowling, Luke Garratt, and Douglas Stebila. A formal security analysis of the signal messaging protocol. In Proceedings of the 2017 IEEE Symposium on Security and Privacy (S&P), pages 840–858, 2017. [23] Richard Barnes, Benjamin Beurdouche, Jon Millican, Emad Omara, Konrad Kohbrok, and Raphael Robert. The messaging layer security (mls) protocol. RFC 9420, 2023.

56

[24] Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. arXiv preprint, arXiv:2305.20050, 2023. [25] Ziyi Ling, Yunfang Wu, Yuxiang Wang, Xinyu Zhang, and Wei Li. Deductive verification of chain-of-thought reasoning. In Advances in Neural Information Processing Systems (NeurIPS), 2023. [26] Alon Jacovi, Yonatan Bitton, Bernd Bohnet, Jonathan Herzig, Orith Toledo-Ronen, Alon Halfon, Matan Vaxman, Ilya Shnayderman, Yonatan Katz, Yoav Levine, Noam Slonim, Chulaka Gunasekara, and Benjamin Sznajder. A chain of thought is as strong as its weakest link. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (ACL), 2024. [27] Scott A. Crosby and Dan S. Wallach. Efficient data structures for tamper-evident logging. In Proceedings of the 18th USENIX Security Symposium, pages 317–334, 2009. [28] Alin Tomescu, Vivek Bhupatiraju, Dimitrios Papadopoulos, Charalampos Papamanthou, Nikos Triandopoulos, and Srinivas Devadas. Transparency logs via append-only authenticated dictionaries. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1299–1316, 2019. [29] David Mazières and Dennis Shasha. Building secure file systems out of byzantine storage. In Proceedings of the 21st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 108–117, 2002. [30] Jinyuan Li, Maxwell N. Krohn, David Mazières, and Dennis Shasha. Secure untrusted data repository (SUNDR). In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 121–136, 2004. [31] Prince Mahajan, Srinath Setty, Sangmin Lee, Allen Clement, Lorenzo Alvisi, Mike Dahlin, and Michael Walfish. Depot: Cloud storage with minimal trust. ACM Transactions on Computer Systems, 29(4):12:1–12:38, 2011. [32] Michael Walfish and Andrew J. Blumberg. Verifying computations without reexecuting them. Communications of the ACM, 58(2):74–84, 2015. [33] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, 1988. [34] Burt Kaliski. PKCS #5: Password-based cryptography specification version 2.0. RFC 2898, RSA Laboratories, September 2000. [35] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 6976 of Lecture Notes in Computer Science, pages 386–400, 2011. [36] Martin Kleppmann and Alastair R. Beresford. A conflict-free replicated JSON datatype. IEEE Transactions on Parallel and Distributed Systems, 28(10):2733–2746, 2017. [37] Mark D. Ryan. Enhanced certificate transparency and end-to-end encrypted mail. In Proceedings of the Network and Distributed System Security Symposium (NDSS), 2014.

57

[38] Steve Kremer and Olivier Markowitch. Optimistic non-repudiable information exchange. In Proceedings of the 21st IFIP WG 6.1 International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), volume 2529 of Lecture Notes in Computer Science, pages 258–271, 2002. [39] Jianying Zhou and Dieter Gollmann. A fair non-repudiation protocol. In Proceedings of the 1996 IEEE Symposium on Security and Privacy, pages 55–61, 1996. [40] National Institute of Standards and Technology. Secure hash standard (SHS). FIPS Publication 180-4, National Institute of Standards and Technology, 2015. [41] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures. Journal of Cryptographic Engineering, 2(2):77–89, 2012. [42] Simon Josefsson and Ilari Liusvaara. Edwards-curve digital signature algorithm (EdDSA). RFC 8032, Internet Research Task Force, 2017. [43] Meltem Sönmez Turan, Elaine Barker, William Burr, and Lily Chen. Recommendation for password-based key derivation: Part 1: Storage applications. NIST Special Publication 800-132, National Institute of Standards and Technology, 2010.

58