# 0-ART: verifiable group key agreement

One of the most challenging problems in applied cryptography is building encryption protocols for large groups(so-called *continuous group key agreement(CGKA)* or *e2g* encryption) that are applicable for decentralized settings. Usually it faces a lot of issues such as scalability, eventual consistency, group members' anonymity, various trust assumptions, etc. Of course, it's also worth mentioning classic e2e messengers' characteristics such as [forward secrecy(FS)](https://en.wikipedia.org/wiki/Forward_secrecy) and *post-compromise secrecy(PCS)*. *Forward secrecy* prevents an adversary which controls current session key from decrypting past messages. *Post-compromise secrecy* is also called in some-sources as *self-healing property*: a valid user could prevent an adversary with the compromised session key access future messages if the valid user manages to update group state first.

## Signal: the pioneer of modern e2e messenging

[Signal](https://signal.org/#signal) is a wonderful messenger built for those who care about their privacy and confidentiality. Built upon its own [Double-Ratchet](https://signal.org/docs/specifications/doubleratchet/) algorithm along with [X3DH](https://signal.org/docs/specifications/x3dh/) and other fancy cryptographic protocols, it became the de-facto standard protocol for e2e communication in the whole industry: WhatsApp, Google Messenger, Skype and many others have taken Signal's protocol or been heavily inspired by it. But, of course, it has a few flies in the ointment. Firstly, Signal is very centralized by its design and requires users to have persistent identifiers, such as a telephone number. Secondly, [group system](https://signal.org/blog/signal-private-group-system/) in Signal is built over [sender keys protocol](https://blog.trailofbits.com/2019/08/06/better-encrypted-group-chat/). It means that each user in a group encrypts each message's encryption key separately for any other user. Obviously, this approach preserves all benefits of DoubleRatchet, such as FS and PCS, but also causes huge scalability problems as encryption complexity grows linearly from the number of users in the group. Moreover, the overall number of encrypted keys in group grows quadratically, thus creating a potential bottleneck on the server side. Hence, Signal limits a number of users in a group to 1000.

## New hope: tree-based group key agreement

To address the issue of scalability of linearly-growing systems, Computer Science invented binary trees. There are a lot of them, notable examples include:

- *Binary Search Trees*, which make search in various data structures and databases blazingly fast
- *Merkle Trees*, which make the verification of transaction's inclusion in the blockchain's block efficient
- *Abstract Syntax Trees*, which help compilers do their work best

One could then ask whether there exists a tree-based approach for *continuous group key agreement* as well. In fact, it does! The first practical scheme of CGKA was [Asynchronous Ratchet Tree](https://eprint.iacr.org/2017/666.pdf) that encapsulates classic Diffie-Hellman key exchange on every node of the tree thus most of the ART operations run with sub-linear complexity $O(\log(n))$.

If the member A decides to perform key rotation he must generate new leaf keypair, compute each internal node secret and send to the group all updated public keys along his path to the root (blue path on the picture above). Other group members use the updated path's public keys to recompute the new group secret. It's easy to see that the complexity of key update depends on the depth of the tree, which in turn is the logarithm from the number of members.

ART inspired the other tree-based CGKA protocol TreeKEM, that was recently adopted in [MLS RFC9420](https://datatracker.ietf.org/doc/rfc9420/). The main difference from the classic ART is the usage of the Key Encapsulation Mechanism instead of the Diffie-Hellman key exchange. MLS is currently being adopted in various modern messaging software such as [Wire](https://wire.com/en/), [GermDM](https://www.germnetwork.com), [WhiteNoise](https://www.whitenoise.chat)


Despite being efficient ART and MLS suffer some practical **problems**:

- the usage of identity keys for explicit signature of protocol messages leads to unwanted identity disclosure and lack of deniability
- reliance on the *Service Provider*(**SP**) with a quite high level of trust assumption could have a negative impact on decentralized applications
- the concurrent group updates support is quite difficult to implement, e.g., *Propose&Commit* scheme in MLS partially solves this at the price of some form of consensus, which usually is costly, hence, hardly scalable
- removing group members despite surface simplicity is not easy: MLS conception of blanked nodes comes with a collateral price of additional encryption complexity which increases with the number of blanked nodes and could even approach $O(n)$ in the worst case.
- groups built with ART/MLS are vulnerable to [Sybil](https://en.wikipedia.org/wiki/Sybil_attack)(malicious insider) attacks which even tighter limits adoption of decentralized settings.

## 0-ART: asynchronous & verifiable CGKA

Here comes the most interesting part: we designed a novel protocol **0-ART** which adds to the classic ART a crucial component of trustless decentralized applications: **verifiability** that mitigates the aforementioned problems. The key characteristics of our protocol:

- almost every group operation (`KeyUpdate, AddMember, RemoveMember`) is publicly verifiable without trusted setup with *bulletproofs*, thus **SP** could merely assert proof validity and deliver the frame to a group where every member could validate it. So basically all group history is verifiable with zero-knowledge proofs which makes the probability of group state disruption negligible.
- users fully control their identities: identity keys are not revealed to **SP**, only a minimal amount of metadata is disclosed
- we proposed an *anonymous verifiable credential mechanism* based on *bulletproofs* for proving group operation eligibility: each user could prove the right to perform some operation without disclosing their identity
- group operations could be efficiently aggregated if performed by one user
- concurrent group operations performed by different users at the same *epoch* could be merged with our *CausalART* protocol
- using *CausalART* we implemented `RemoveMember` operation without *blank nodes*


### Implementation

We use [Dalek's implementation](https://github.com/dalek-cryptography/bulletproofs) of [bulletproofs](https://eprint.iacr.org/2017/1066.pdf) as our main zk-NARK(*zero-knowledge non-interactive argument of knowledge*) which is built upon the *commit-and-prove* paradigm. Each level of the tree requires proving two scalar multiplications, for that reason we built a custom optimized scalar multiplication circuit which takes ~1.5K quadratic constraints.
This allowed us to prove and verify each level of the tree in parallel accelerating operations for multi-core CPUs while preserving a still reasonable proof size.
For example proving one level of the tree takes nearly 400ms and 1.1Kb of proof size, while verification takes nearly 40ms on moderate CPUs. Utilizing multi-threading proving for the tree of depth 20 (group with ~1M users) we get proving ~1.5s, verification ~170ms and proof size ~24Kb.

## Applications

The main straightforward application of our verifiable CGKA is decentralized messengers with support of large groups. But, we've built something more interesting: end-to-end encrypted collaborative tool [Veil](https://github.com/zero-art-rs/veil-app/) that uses **0-ART** under the hood with [CRDT](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type) protocol provided by [automerge](https://automerge.org), the app idea was heavily inspired by Ink&Switch's [KeyHive](https://www.inkandswitch.com/keyhive/notebook/) project. It's like an amazing Hack.md app but with privacy enabled by default: each document is encrypted only for a list of its members and every group state update is verifiable by design. Our demo application uses the service provider which acts as merely a trustless delivery service and does not have the access to documents content nor users' identities, furthermore it can not modify any group frame acting as an active adversary trying to impersonate or disrupt a group's state. The next obvious step is building a fully decentralized application which eliminates the need for the centralized service provider entirely.

## Conclusions & further research vectors

Our main goal now is to implement a fully decentralized system on top of **0-ART**. We believe that zero-knowledge proofs could open lots of new opportunities for decentralized applications and make the world more private and secure.
You could check out our [0-ART open source toolkit](https://github.com/zero-art-rs/), which contains a full **0-ART** implementation in Rust, service provider implementation, high-level client-SDK and a demo of the secure collaboration tool [Veil](https://github.com/zero-art-rs/veil-app/). For detailed technical description of the protocol we refer the reader to our [paper](https://eprint.iacr.org/2025/1874.pdf).
In the subsequent posts we will discuss technical detail of verifiable group operations, anonymous verifiable credentials and circuit design.