1. bookVolume 2019 (2019): Issue 3 (July 2019)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Snapdoc: Authenticated snapshots with history privacy in peer-to-peer collaborative editing

Published Online: 12 Jul 2019
Page range: 210 - 232
Received: 30 Nov 2018
Accepted: 16 Mar 2019
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

Document collaboration applications, such as Google Docs or Microsoft Office Online, need to ensure that all collaborators have a consistent view of the shared document, and usually achieve this by relying on a trusted server. Other existing approaches that do not rely on a trusted third party assume that all collaborating devices are trusted. In particular, when inviting a new collaborator to a group, one needs to choose between a) keeping past edits private and sending only the latest state (a snapshot) of the document; or b) allowing the new collaborator to verify her view of the document is consistent with other honest devices by sending the full history of (signed) edits. We present a new protocol which allows an authenticated snapshot to be sent to new collaborators while both hiding the past editing history, and allowing them to verify consistency. We evaluate the costs of the protocol by emulating the editing history of 270 Wikipedia pages; 99% of insert operations were processed within 11.0 ms; 64.9 ms for delete operations. An additional benefit of authenticated snapshots is a median 84% reduction in the amount of data sent to a new collaborator compared to a basic protocol that transfers a full edit history.


[1] Niko Barić and Birgit Pfitzmann. Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees. In Advances in Cryptology – EUROCRYPT ’97, pages 480–494. Springer, 1997.Search in Google Scholar

[2] Josh Benaloh and Michael De Mare. One-way accumulators: A decentralized alternative to digital signatures. In Advances in Cryptology – EUROCRYPT ’93, pages 274–285. Springer, 1993.Search in Google Scholar

[3] Eric A. Brewer. Towards Robust Distributed Systems. In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, PODC 2000, page 7. ACM, 2000.Search in Google Scholar

[4] Philippe Camacho, Alejandro Hevia, Marcos Kiwi, and Roberto Opazo. Strong accumulators from collision-resistant hashing. International Journal of Information Security, 11(5):349–363, 2012.Search in Google Scholar

[5] Jan Camenisch, Markulf Kohlweiss, and Claudio Soriente. An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. In Public Key Cryptography – PKC 2009, pages 481–500. Springer, 2009.Search in Google Scholar

[6] Dario Catalano and Dario Fiore. Vector commitments and their applications. In Public-Key Cryptography – PKC 2013, pages 55–72. Springer, 2013.Search in Google Scholar

[7] 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. USENIX Association, 2009.Search in Google Scholar

[8] John Day-Richter. What’s different about the new Google Docs: Making collaboration fast, 2010.Search in Google Scholar

[9] David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In Topics in Cryptology – CT-RSA 2015, pages 127–144. Springer, 2015.Search in Google Scholar

[10] Benjamin Dowling, Felix Günther, Udyani Herath, and Douglas Stebila. Secure Logging Schemes and Certificate Transparency. In Computer Security – ESORICS 2016, pages 140–158. Springer, 2016.Search in Google Scholar

[11] Clarence A. Ellis and Simon J. Gibbs. Concurrency Control in Groupware Systems. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, volume 18, pages 399–407. ACM, 1989.Search in Google Scholar

[12] Ariel J. Feldman, William P. Zeller, Michael J. Freedman, and Edward W. Felten. SPORC: Group Collaboration Using Untrusted Cloud Resources. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation, OSDI 2010, pages 337–350. USENIX Association, 2010.Search in Google Scholar

[13] Dennis Felsch, Christian Mainka, Vladislav Mladenov, and Jörg Schwenk. SECRET: On the Feasibility of a Secure, Efficient, and Collaborative Real-Time Web Editor. In Proceedings of the 2017 ACM Asia Conference on Computer and Communications Security, AsiaCCS 2017, pages 835–848. ACM, 2017.Search in Google Scholar

[14] Seth Gilbert and Nancy Lynch. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News, 33(2):51–59, 2002.Search in Google Scholar

[15] Abdessamad Imine, Pascal Molli, Gérald Oster, and Michaël Rusinowitch. Proving Correctness of Transformation Functions in Real-Time Groupware. In ECSCW 2003, pages 277–293. Springer, 2003.Search in Google Scholar

[16] Abdessamad Imine, Michaël Rusinowitch, Gérald Oster, and Pascal Molli. Formal design and verification of operational transformation algorithms for copies convergence. Theoretical Computer Science, 351(2):167–183, 2006.Search in Google Scholar

[17] Robert Johnson, David Molnar, Dawn Song, and David Wagner. Homomorphic signature schemes. In Topics in Cryptology – CT-RSA 2002, pages 244–262. Springer, 2002.Search in Google Scholar

[18] Martin Kleppmann and Alastair R. Beresford. A Conflict-Free Replicated JSON Datatype. IEEE Transactions on Parallel and Distributed Systems, 28(10):2733–2746, 2017.Search in Google Scholar

[19] Nadim Kobeissi. Capsule: A protocol for secure collaborative document editing. IACR Cryptology ePrint 2018/253, 2018.Search in Google Scholar

[20] Ben Laurie, Adam Langley, and Emilia Kasper. RFC 6962: Certificate Transparency. IETF, 2013.Search in Google Scholar

[21] Prince Mahajan, Lorenzo Alvisi, and Mike Dahlin. Consistency, Availability, and Convergence. Technical Report UTCS TR-11-22, Department of Computer Science, The University of Texas at Austin, 2011.Search in Google Scholar

[22] 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.Search in Google Scholar

[23] Ralph C. Merkle. A Digital Signature Based on a Conventional Encryption Function. In Advances in Cryptology – CRYPTO ’87, pages 369–378. Springer, 1988.Search in Google Scholar

[24] Brice Nédelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils. LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing. In Proceedings of the 2013 ACM Symposium on Document Engineering, DocEng 2013, pages 37–46. ACM, 2013.Search in Google Scholar

[25] Lan Nguyen. Accumulators from Bilinear Pairings and Applications. In Topics in Cryptology – CT-RSA 2005, pages 275–292. Springer, 2005.Search in Google Scholar

[26] David A. Nichols, Pavel Curtis, Michael Dixon, and John Lamping. High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System. In Proceedings of the 8th Annual ACM Symposium on User Interface Software and Technology, UIST 1995, pages 111–120. ACM, 1995.Search in Google Scholar

[27] Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine. Proving correctness of transformation functions in collaborative editing systems. Technical Report RR-5795, INRIA, 2005.Search in Google Scholar

[28] Nuno Preguiça, Joan Manuel Marques, Marc Shapiro, and Mihai Letia. A Commutative Replicated Data Type for Cooperative Editing. In 29th International Conference on Distributed Computing Systems, ICDCS 2009, pages 395–403. IEEE, 2009.Search in Google Scholar

[29] Michael O. Rabin. Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12(1):128–138, 1980.Search in Google Scholar

[30] Paulo Ribenboim. The Little Book of Bigger Primes. Springer, 2004.Search in Google Scholar

[31] Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee. Replicated abstract data types: Building blocks for collaborative applications. Journal of Parallel and Distributed Computing, 71(3):354–368, 2011.Search in Google Scholar

[32] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. A comprehensive study of convergent and commutative replicated data types. Technical Report RR-7506, INRIA, 2011.Search in Google Scholar

[33] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free Replicated Data Types. In Stabilization, Safety, and Security of Distributed Systems, SSS 2011, pages 386–400. Springer, 2011.Search in Google Scholar

[34] Ron Steinfeld, Laurence Bull, and Yuliang Zheng. Content Extraction Signatures. In Information Security and Cryptology – ICISC 2001, pages 285–304. Springer, 2001.Search in Google Scholar

[35] Roberto Tamassia. Authenticated data structures. In Algorithms – ESA 2003, pages 2–5. Springer, 2003.Search in Google Scholar

[36] Stéphane Weiss, Pascal Urso, and Pascal Molli. Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In 29th IEEE International Conference on Distributed Computing Systems, ICDCS 2009, pages 404–412. IEEE, 2009.Search in Google Scholar

[37] Stéphane Weiss, Pascal Urso, and Pascal Molli. Logoot-Undo: Distributed Collaborative Editing System on P2P Networks. IEEE Transactions on Parallel and Distributed Systems, 21(8):1162–1174, 2010.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo