{"id":"f0d74e31-1317-4c99-9403-6bcc73c83c8d","arxiv_id":"1908.06068","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors construct tile-assembly systems that conceal inputs and computational history, and use these to prove coNP-completeness of unique assembly verification in the growth-only negative-glue aTAM.","lead":"This paper introduces covert computation in tile self-assembly, where the input and history of a computation are hidden inside the final assembled structure. It builds a functionally complete set of covert logic gates and uses them to prove that unique assembly verification in a growth-only negative-glue model is coNP-complete.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Correctness rests on informally verified gadget properties; the NAND gadget's growth-only claim (Sec. 3.5, property 8) is the load-bearing point and needs a formal or exhaustive check.","rationale":"The reader's weakest-assumption analysis already targets the informal correctness of the covert gadgets, and my stress-test converges on the same point. I see no demonstrated internal contradiction in the paper, but the central theorems are only as secure as the NAND/FANOUT gadget properties, and those properties are not formally verified. Section 3.5, property 8 is the sharpest instance because the paper explicitly concedes a possible stability violation and then relies on an 'intentional' build path without proving that all producible assembly orders are safe. This is a verification gap rather than a known counterexample, so the appropriate verdict remains conditional: accept the conceptual framework and complexity route, but require an exhaustive or machine-checked verification of the gadget properties before treating the theorems as fully established. Since the reader already reached this conditional verdict, no adjustment is needed.","tokens_in":15164,"tokens_out":7564,"duration_ms":84538,"concrete_test":"Implement an exhaustive verifier for the Section 3 tile sets (or use an existing aTAM simulator with full enumeration) that, for each input seed, explores every reachable assembly under the aTAM attachment rule and checks (1) every reachable assembly is tau-stable, and (2) every terminal assembly has the correct dual-rail output and complete backfill. Run it on the NAND gadget's four input cases and on the FANOUT gadget. If any reachable unstable assembly or wrong terminal is found, the gadget needs repair; if the exhaustive search succeeds, the main remaining risk is resolved for these gadgets.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claims (Theorems 1 and 2) inherit all of Section 3's gadget properties. These properties are supported by informal case analysis, not by formal proofs or machine checks, and the paper's own history (Section 1: a NAND backfill issue 'has been corrected') is evidence that hand-verified gadgets in this model are fragile. The most load-bearing unsecured step is Section 3.5, property 8, which asserts the growth-only constraint is not violated by the additional negative glue nH in the H-NOT. The accompanying reason is that the tile with nH 'would be the last tile that could attach' if fout_ij is placed and tout_ij backfilled, so the assembly would never be unstable. But growth-only is a universal condition: every producible assembly must be tau-stable, not just the intended build order. The text does not prove that no alternative attachment order can put the green tile before the blue tile, or otherwise form an unstable assembly; it only asserts a build path is 'intentional.' A single violation of property 8 would invalidate the NAND gadget, and with it Theorem 1's covert universal computation and Theorem 2's coNP-completeness reduction, since both use this gadget.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the notion of covert computation in tile self-assembly, formalized through Tile Assembly Computers (TACs), and presents a library of dual-rail logic gadgets -- variables, wires, backfill stops, logic diodes, NOT, NAND, and FANOUT -- built in the abstract Tile Assembly Model with positive and negative glues under a growth-only restriction. The authors claim that any function computed by a boolean circuit can be covertly computed by a TAC (Theorem 1), and they use the covert circuitry to show that Unique Assembly Verification in the growth-only negative-glue aTAM is coNP-complete (Theorem 2). The appendix-like sections give additional AND and OR gadgets, a half-adder, and discussions of cryptographic motivation. The central technical content is the correctness of the gadget constructions, on which both theorems rest.","tokens_in":15459,"tokens_out":4609,"duration_ms":47760,"significance":"If the construction is fully correct, the paper makes a noteworthy contribution to algorithmic self-assembly: it provides the first general framework for concealing input and computational history in aTAM computations, and it resolves the complexity of Unique Assembly Verification under negative glues with the growth-only restriction. The definitions of TACs and covert computation are useful formalizations, and the reduction from Planar Circuit SAT is conceptually clean. The paper is also honest about a previously corrected NAND bug, which signals the fragility of hand-verified gadget constructions. However, the correctness of the main theorems depends on a list of asserted gadget properties that are not formally proved, and at least one of those assertions (property 8 of Section 3.5) is not justified by the text. For this reason the result is plausible but not yet fully established.","major_comments":[{"comment":"The growth-only constraint is a universal condition: every producible assembly must be τ-stable, not merely the intended build order. The text justifies the additional negative glue nH by saying that \"the build path is intentional\" so that the tile with nH would be the last tile that could attach. This is not a proof: one must rule out all alternative attachment orders and all partial assemblies that could become unstable. Since property 8 is used in the NAND gadget, and Theorem 1 and Theorem 2 both rely on the NAND gadget, this gap is load-bearing. I request a formal proof, an inductive invariant, or an exhaustive computer-assisted verification of the growth-only property.","section":"Section 3.5, property 8"},{"comment":"The correctness of the NOT, NAND, and FANOUT gadgets is presented as lists of properties with informal explanations (e.g., Section 3.4 properties 1-6, Section 3.5 properties 1-9, Section 3.6 properties 1-4) rather than formal proofs. The paper's own statement that the NAND gadget had a backfill issue that \"has been corrected\" (Section 1) shows that these constructions are delicate. I recommend that the authors supply a rigorous proof of each gadget property, or at least a machine-checkable exhaustive verification, before the main theorems can be considered fully supported.","section":"Section 3, gadget properties generally"},{"comment":"The proof text says that NAND gates are functionally complete and \"these are easily transformed into Circuit SAT instances to compute any function that is in the class NP.\" This is inaccurate: functions computed by boolean circuits are non-uniform and are not restricted to NP. However, the construction in Section 3 already gives a direct simulation of arbitrary circuits by NAND and FANOUT gadgets, so the theorem can be proved without invoking NP or Circuit SAT. The proof should be rewritten to state the direct simulation.","section":"Theorem 1 proof"},{"comment":"The claim that any failure of unique assembly yields \"a polynomially sized assembly that is inconsistent with A\" needs a supporting argument. A valid certificate can be obtained by taking a growth path from the seed and stopping at the first assembly that is not a subassembly of the target A; a short argument bounding the size of that assembly is needed to make the coNP membership rigorous.","section":"Theorem 2 proof, coNP membership"}],"minor_comments":[{"comment":"There are several typographical errors, including \"implementaiton\" (Section 1), \"assemby\" (Section 2.3), \"receieved\" (Section 3.4), and \"ouput\" (Definition 2). The paper would benefit from a careful proofreading pass.","section":"Throughout"},{"comment":"The NOT gadget properties are explained with reference to Figure 6, but the figure does not show the logic diode that is part of the actual gadget in Figure 5b. It would improve clarity to either include the diode in the walkthrough or state explicitly that the properties are claimed for the version with the diode.","section":"Section 3.4"},{"comment":"In the reduction for Theorem 2, the sentence \"If the circuit is not-satisfiable, then the final computation will be false regardless of the guessed input\" should be phrased more carefully: the TAC computes the circuit for the nondeterministically chosen input, so for unsatisfiable circuits every possible evaluated input yields the unique false output assembly, which is the target assembly in the UAV instance.","section":"Section 4"},{"comment":"The variable gadget is described as having a negative glue between the true and false tiles, but the accompanying text could explain more explicitly why this prevents both tiles from attaching in the seed phase; the current phrasing \"only the ti or fi tile may attach\" is clear enough, but a bit more detail would help the reader verify the blocking mechanism.","section":"Section 3.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be of interest to the self-assembly theory community, and the central idea is attractive. My main concern is that the correctness of the gadget library is asserted rather than proved, especially the growth-only property of the NAND gadget. Given the authors' own report of a corrected NAND bug, I would strongly encourage the editor to require either detailed formal proofs or a computer-assisted exhaustive check of all gadget properties before publication. The other issues in the proofs of Theorems 1 and 2 are local and should be straightforward to fix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead this if you work on tile self-assembly complexity. The new idea is covert computation in the growth-only negative aTAM: the final assembly hides the input and the computational history, and only the output is readable. The authors build dual-rail logic gadgets (NOT, NAND, FANOUT, plus AND/OR) that backfill unused wires, so all terminal assemblies for the same output look alike even when the inputs differ. They then use those gadgets to show that Unique Assembly Verification in growth-only negative aTAM is coNP-complete, which closes the gap between the polynomial case without negative glues and the undecidable case with detachment. That is a genuine contribution to the theory.\n\nThe paper does several things well. The backfilling mechanism is clearly explained, and the figures carry a lot of weight. The authors are honest about provenance: this arXiv text is an extended version of their ICALP 2019 paper [3], and they list the changes, including a corrected NAND backfill issue and the new backfill stop gadget. The citation pattern is fine; self-citation here is appropriate and not masking circularity. The coNP membership part is fine: a non-unique system has a polynomially sized assembly differing from the target, which serves as a certificate.\n\nThe soft spot is the informal correctness proof, and it is not minor. Sections 3.4 and 3.5 state long lists of gadget properties (e.g., NAND properties 1-9) but do not prove them. Given how tightly the negative glues and cooperative attachments are tuned, this is exactly the kind of construction that needs exhaustive case analysis or a machine-checked simulation. The paper's own admission that the NAND gadget previously had a backfill bug supports that worry. The most load-bearing unproven claim is property 8: the assertion that the growth-only constraint is never violated. The text says the build path is \"intentional\" to prevent the problematic tile from attaching before the stabilizing tile, but growth-only is a universal condition about all producible assemblies, not just the intended order. Without a proof that no alternative attachment order creates an unstable assembly, property 8 is an assumption, and both Theorems 1 and 2 depend on it. The stress-test note is right to flag this.\n\nWho should read it: researchers in algorithmic self-assembly, particularly those working on negative interactions, verification problems, or molecular data privacy. It deserves a serious referee. My recommendation: send it to review, but ask the referee to focus on Section 3.5 property 8 and the gadget correctness argument. If the authors can supply an exhaustive case split or a mechanically verified model, the paper will be solid. If not, it should be accepted only as a conference-level statement with the caveat made explicit.","headline":"Clear, useful paper with a real new complexity result, but correctness rests on hand-verified gadget properties that should be checked formally or exhaustively.","tokens_in":15923,"tokens_out":4569,"would_cite":true,"duration_ms":45294,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A tile-assembly system can compute any boolean function while concealing its input and history.","keywords":["covert computation","tile self-assembly","abstract Tile Assembly Model","negative glues","coNP-complete","unique assembly verification","dual-rail logic","molecular cryptography"],"falsifier":"Run an exhaustive enumeration or a tile-assembly simulator on the Section 3 NAND gadget for each of the four input settings and check the nine listed properties: only the claimed output rail grows, the unused input rails are backfilled, and every producible assembly is stable at temperature τ. A single input setting that yields the wrong output, leaves a rail unfilled, or produces an unstable intermediate assembly would refute Theorem 1; for Theorem 2, the same test on the nondeterministic-seed system would expose a second terminal assembly for a satisfiable circuit.","tokens_in":15018,"feed_emoji":"🧬","tokens_out":7050,"duration_ms":66686,"temperature":0.7,"pith_summary":"Tile self-assembly, the paper argues, can be made covert: the final crystal reports the output of a boolean function but leaves no visible trace of the input bits or of the order in which tiles attached. The paper builds a functionally complete set of covert logic gates—variables, wires, NOT, NAND, and FANOUT—inside the growth-only variant of the abstract Tile Assembly Model, where negative-strength glues act purely as blockers. It then proves that any function computable by a boolean circuit admits a tile assembly computer that covertly computes it, and uses the same circuitry to prove that Unique Assembly Verification in this model is coNP-complete, filling a known gap between the polynomial-time positive-glue case and the undecidable case with detachment. The stakes are practical as well as theoretical: covert molecular computation is a candidate mechanism for privacy-preserving biomedical diagnostics and molecular cryptography.","feed_headline":"Covert computation works in self-assembled tile circuits","feed_subtitle":"A complete set of hidden logic gates makes any boolean function conceal its input; verification becomes coNP-complete.","key_machinery":"The load-bearing machinery is a kit of covert gadgets: dual-rail wires, backfill stops, logic diodes, and NOT, NAND, and FANOUT tile sets. Each gadget uses negative-strength glues as one-way blockers and cooperative attachments—two strength-1 glues binding together—to make backfilling wait until the relevant input value is known. The central invariant is the backfill rule: after a gadget passes a value onward, the entire unused rail is filled in from the downstream side, so the finished assembly contains both possible paths of every wire and the build order is erased. This erasure is what makes the computation covert and is also what lets the gadgets be composed into arbitrary planar circuits without leaving traces of the inputs.","core_discovery":"The paper's central claim is that covert computation is possible in general: for every function f computable by a boolean circuit, there is a tile assembly computer (TAC) whose terminal assembly depends only on the output f(b), not on the input b or on the assembly history. The proof works by implementing dual-rail logic with tiles: each bit travels on one of two adjacent wires, and once a gadget has read a value, the unused wire is backfilled retroactively so both wires are present in the final assembly. Because the final shape contains both rails of every wire, an observer cannot tell from the finished crystal which bits entered the computation. The same gadget set is then used to prove Theorem 2: deciding whether a growth-only negative-glue tile system uniquely produces a given assembly is coNP-complete, via a reduction from Planar Circuit SAT in which a nondeterministic seed guesses all inputs and the covertly computed output is the unique 'no' assembly iff the circuit is unsatisfiable.","pith_inferences":["The backfill-and-block design principle likely transfers beyond the specific aTAM gadgets: any self-assembly model that supports two-valued cooperative binding and repulsive glues could implement the same dual-rail erasure strategy, so the result is a template rather than a one-off construction.","The coNP-completeness of Unique Assembly Verification suggests that negative glues add computational power not by enabling detachment but by letting a system delay commitment to a wire; a testable prediction is that weakening the growth-only promise even slightly changes the complexity boundary.","A concrete follow-up experiment would be to implement the NAND gadget in a DNA tile system or kinetic simulation and watch whether backfilling completes before off-path growth; the logic diodes predict that partial wires should stop cleanly at gadget boundaries, a signature that could be checked experimentally."],"forward_implications":["Any boolean-circuit-computable function can be implemented as a covert tile system whose final assembly reveals only the function value, enabling privacy-preserving molecular diagnostics where the patient's biological input is not readable from the product.","The Unique Assembly Verification dichotomy in the aTAM becomes complete: polynomial time with only positive glues, coNP-complete with negative glues under growth-only, and undecidable when detachment is allowed.","Covert computation can be composed from functionally complete NAND and FANOUT gadgets, so circuit designers do not need a crossover gadget; planarity is handled by XOR-from-NAND constructions.","The construction provides a concrete template for any future covert tile assembly computer, including the half-adder and multiplier examples used as stepping stones toward molecular cryptography."],"supporting_citations":[{"why":"establishes that Unique Assembly Verification is polynomial-time in the aTAM without negative glues, the baseline the new coNP-completeness result sharpens.","marker":"[1]"},{"why":"defines the negative-interaction self-assembly model and shows UAV becomes undecidable once detachment is allowed, setting the boundary that the growth-only result fills in.","marker":"[11]"},{"why":"supplies Circuit SAT and the NP-hardness framework used both for the function-computing formulation and for the Planar Circuit SAT reduction of Theorem 2.","marker":"[15]"},{"why":"establishes that NAND plus FANOUT is functionally complete, which is what lets the covert gadget set simulate every boolean circuit.","marker":"[27]"},{"why":"is the earlier version of this work containing the original covert gadget construction, including the NAND backfill bug corrected here.","marker":"[3]"},{"why":"supplies the formal notion of a tile assembly computer that the paper adapts to bit templates and covert output.","marker":"[18]"}],"fun_headline_variants":["Covert computation achieved in self-assembled tile circuits","Self-assembled tile logic computes without revealing inputs","Hidden-input tile self-assembly computes any boolean function","Tile circuits conceal their computational history","Self-assembly enables covert computation via dual-rail tiles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Both theorems rest on the unproven property lists of Section 3: each gadget's negative glues must block exactly as drawn, backfilling must fill every unused wire, and no intermediate assembly may be able to fall apart, so if any single gadget fails one of those behaviors, the covert-circuit simulation and the coNP-hardness reduction both collapse.","fun_headline_variants_meta":{"raw":{"variants":["Covert computation achieved in self-assembled tile circuits","Self-assembled tile logic computes without revealing inputs","Hidden-input tile self-assembly computes any boolean function","Tile circuits conceal their computational history","Self-assembly enables covert computation via dual-rail tiles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000247,"raw_usage":{"total_tokens":1540,"prompt_tokens":942,"completion_tokens":598,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":524}},"tokens_in":558,"tokens_out":598,"duration_ms":6471,"temperature":1.0,"reasoning_tokens":524,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:56:44.800193+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive enumeration or a tile-assembly simulator on the Section 3 NAND gadget for each of the four input settings and check the nine listed properties: only the claimed output rail grows, the unused input rails are backfilled, and every producible assembly is stable at temperature τ. A single input setting that yields the wrong output, leaves a rail unfilled, or produces an unstable intermediate assembly would refute Theorem 1; for Theorem 2, the same test on the nondeterministic-seed system would expose a second terminal assembly for a satisfiable circuit.","supporting_citations":[{"cited_title":"Adleman, Qi Cheng, Ashish Goel, Ming-Deh A","cited_arxiv_id":null,"evidence_quote":"establishes that Unique Assembly Verification is polynomial-time in the aTAM without negative glues, the baseline the new coNP-completeness result sharpens."},{"cited_title":"Negative interactions in irreversible self-assembly","cited_arxiv_id":null,"evidence_quote":"defines the negative-interaction self-assembly model and shows UAV becomes undecidable once detachment is allowed, setting the boundary that the growth-only result fills in."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies Circuit SAT and the NP-hardness framework used both for the function-computing formulation and for the Planar Circuit SAT reduction of Theorem 2."},{"cited_title":"A set of five independent postulates for boolean algebras, with applica- tion to logical constants","cited_arxiv_id":null,"evidence_quote":"establishes that NAND plus FANOUT is functionally complete, which is what lets the covert gadget set simulate every boolean circuit."},{"cited_title":"Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie","cited_arxiv_id":null,"evidence_quote":"is the earlier version of this work containing the original covert gadget construction, including the NAND backfill bug corrected here."},{"cited_title":"Fast arithmetic in algorithmic self-assembly","cited_arxiv_id":null,"evidence_quote":"supplies the formal notion of a tile assembly computer that the paper adapts to bit templates and covert output."}],"review_version":1}