1 Introduction↩︎

Making robust digital currencies that are practical requires decentralized solutions that are efficient. A recent breakthrough states consensus is not required to validate transactions [1], [2]: establishing a total order — through protocols based on Nakamoto consensus like Bitcoin or Byzantine Fault Tolerant consensus — can be avoided in the cryptocurrency problem and a Byzantine quorum suffices to guarantee only valid transactions are accepted. Many solutions following this approach in asynchronous networks were proposed [3]–[9], but still process transactions sequentially: even two non-conflicting transactions must be validated one after the other by sufficiently intersecting quorums.

Bazzi and Tucci [10] were the first to parallelize non-conflicting transactions. The key idea is simple: given an account with balance \(X\) and transactions spending only a fraction of it, say \(X/100\), then the first hundred transactions do not conflict and can be validated in parallel — without any quorum intersection. This approach is captured by the Fractional Spending Problem. Their protocol rely on a new family of quorum systems, called \((k_1,k_2)\)-quorums, where up to \(k_1\) transactions are guaranteed to be processed in parallel, but no more than \(k_2\) concurrent transactions are ever allowed. Once all spendable fractions of an account are consumed, a settlement phase contacts the previously involved quorums to recover the residual balance, or to allow a seller to redeem received funds.

Beyond parallelization, the central novelty of fractional spending is validation of transactions not requiring \(2f+1\) votes, but fewer than \(f\). This introduces a critical challenge: a quorum smaller than \(f\) can be entirely corrupted by an adaptive adversary that chooses which validators to corrupt during the execution. Bazzi and Tucci further considered a rushing-adaptive adversary, i.e., one that can observe the messages sent by honest validators before deciding which messages the corrupted ones should send. To protect against such a powerful adversary, their protocol relies on cryptographic primitives to hide the composition of the validating quorum until settlement, preventing the adversary from predicting and corrupting it in advance. If the adversary could identify and corrupt a quorum, it can erase a payment from the collective memory of validators and thus enable fraud.

In this work we introduce a novel abstraction, Secret Quorums, that extends the concept of secret leader election [11], [12]. A secret quorum allows the selection of a quorum of expected size \(k\) out of \(n\) validators such that the selection is unpredictable (the adversary can do no better than guessing), random (all validators are equally likely to be selected), and anonymous (proofs of membership do not reveal the validator’s identity but only its legitimacy for the given transaction). We instantiate this abstraction using ring verifiable random function [13] together with \((k_1,k_2)\)-quorums, and we build StealthDust, a protocol for fractional spending that reduces payment latency from five to three communication steps and settlement complexity from \(O(n^3)\) to \(O(n^2)\), while tolerating rushing-adaptive adversaries.

Contributions.  Our contributions are threefold:

• Secret Quorums. We introduce the abstraction of secret quorums, which extends secret leader election to the selection of a quorum of expected size \(k\) to anonymity. A validator of a quorum can prove to be a legitimated validator showing a proof that does not reveal its identity.

• Instantiation via Verifiable Ring Signatures. We construct secret quorums using ring verifiable random functions, providing the first practical mechanism to realize them in a decentralized setting.

• StealthDust Protocol. We design StealthDust, a protocol for fractional spending based on \((k_1,k_2)\)-quorums and secret quorums. StealthDust reduces payment latency from five to three communication steps and improves settlement complexity from \(O(n^3)\) to \(O(n^2)\), while tolerating a rushing-adaptive adversary.

Organization.  The rest of the paper is organized as follows. We discuss related work in Section 2. The system model and the fractional spending problem are presented in Section 3 and 4. Section 5 presents the \((k_1, k_2)-\)quorum systems and the protocol from [10] we build upon in Section 6, where we present Secret Quorums and our new protocol StealthDust. We conclude this paper in Section 7.

2 Related Work↩︎

A common approach to achieve efficient distributed digital currencies is to resort to a blockchain — and thus to Consensus — as little as possible.

Batching.  A first direction is batching. Payment channels and channel factories [14]–[17] allow two parties to transact quickly and cheaply in a private channel, but they require a close cooperation and a constant monitoring of the blockchain to ensure that no outdated state is submitted. Some approaches attempt to settle transactions in bulk [18], acting as a second layer on top of a blockchain and reducing the validation cost per transaction; but they require all transactions to be processed simultaneously, which can be restrictive in dynamic environments.

Parallel validation.  Another direction is relaxing the strict total ordering of transactions, such as many recent works [1]–[9]. This relaxation was made possible thanks to the discovery in [1], [2] that Consensus can be avoided in the validation of transactions: there is no need to order spendings from different accounts. These protocols, such as Stingray, Astro or Fastpay, only order transactions from a same account and typically assume a Byzantine fault tolerance model, where at most \(f\) out of \(n >3f\) servers are malicious and transactions are validated by at least a super-majority of \(2f+1\) validators. This limits scalability due to transactions being validated by the same \(f+1\) validators in the intersection, which locally need to process some transactions sequentially — even if these transactions should be parallel. CryptoConcurrency [9] goes further and proposes an overspending detection mechanism for accounts shared by independent clients. This mechanism is strictly weaker than consensus and allows for parallel processing of non conflicting transactions — even from a same account. When an overspending is detected, consensus is solved only between the owners of a shared account and allows owners to choose the consensus mechanism they trust. All these protocols implements cryptocurrencies where any amount can be spent in each transactions — which is not our case — but are limited by the use of the same validators for non conflicting transactions. We never resort to consensus and are fully asynchronous.

Using Cryptography.  Our work is in the same line of inquiry as of [10] which also considers fractional spending transactions with an adaptive adversary, and we introduce Secret Quorums to tolerate this powerful adversary. Our implementation of Secret Quorums is based on VRF and Ring Signatures and is more efficient than the protections used in [10]. Using VRFs to randomly select validators in a private and non-interactive way is already presented in Algorand [12], [19] for block proposers and committees selection. Proposers and committee members in Algorand, however, need to reveal themselves to prove the correctness of the selection and thus become vulnerable from this moment — contrarily to Secret Quorums. Algorand also solves Consensus and uses the current blockchain as a common coin for the VRF selection. Our implementation of Secret Quorums avoids using a consensus based common coin for the VRF.

Ring Signatures [20] are used in CryptoNote [21] — empowering for instance the digital currency Monero — where the sender of a payment is hidden between multiple possible signers. We use ring signatures in StealthDust to protect validators and not clients sending anonymous transactions. The cryptographic primitive \(\textit{rVRF}\) [13] was also used to build a secret single leader election (SSLE) in Sassafras [22]; but Sassafras has no secret sets, elected leaders are revealed and its network is synchronous.

3 Model↩︎

We use the same model used in [10].

Byzantine Asynchronous Message Passing.  Let \(\ifmmode \mathcal{P} \else\) \(\fi\) be an unbounded set of participating clients and \(\Pi\) a finite set of \(n\) validators responsible for validating transactions. We use the term node when it does not matter if the participant is a client or a validator. Nodes are prone to byzantine faults, i.e. can arbitrarily deviate from their protocol. Such node is called corrupted and otherwise it is correct. An unbounded number of clients can be corrupted but no more than \(f\) validators are corrupted during an execution. Nodes communicate via message passing through an asynchronous network, i.e., there is no bound on the time to deliver messages.

Cryptographic Primitives.  Each node \(i\) in the system is equipped a pair of public/private key and can be identified by its public key \(pk_i\). Nodes are also equipped with a collision resistant hash function. We denote by \(\textit{Hash}(x||y)\) the hash of the concatenation of arbitrary values \(x\) and \(y\).

Fault Tolerance of Parallel Quorums [10].  Parallel quorums, as defined in [10] can independently validate transactions from a same account and are of size \(m<f\). Following the probabilistic quorum construction in [10], we also have that \(n>8f\). Indeed, quorums are selected at random over \(\Pi\) which implies: \(n\) is large enough to ensure each selected quorums has sufficient intersection with other quorums to stop validation when the bound is reached; but also sufficient non-intersection to guarantee parallel execution when the bound is not reached. This construction may appear less resilient than other constructions with traditional quorum systems, which have \(n > 3f\). This resilience, however, is global for \(k\) parallel transactions. Achieving \(k\) parallel transactions using traditional quorum systems would require to split the nodes in \(k\) partitions of size \(m = n/k\). The resilience of such solution would then be reduced to the one of a unique partition: corrupting \(m/3\) nodes from one quorum would allow double spending. Thus, the probabilistic quorum systems construction from [10] provides better resilience against corruptions than traditional quorums for \(k\) greater or equal to \(3\).

A Strong Adaptive and Rushing Adversary.  We assume a strong adaptive and rushing adversary that can corrupt Byzantine nodes. The adversary has read and write access to memory of corrupted nodes. Corrupted nodes can collude. The adversary can control message delays, but it cannot drop systematically messages between correct nodes. Being rushing, the adversary can observe any message sent before any correct node. In particular, it controls message delays so it can define the delivery order at all nodes and deliver any message to a corrupted node before any correct node.

Being strong and adaptive, the adversary can corrupt instantly any node of its choice — still up to \(f\) nodes — based on messages gathered during the execution. The adversary can, for instance, observe a particular set of messages intended for a given node, instantly corrupt the intended recipient and impede a reaction to this message.

We also assume private channels, i.e. the adversary cannot see the internal state of correct nodes and cannot see the internal content of messages between correct nodes; but still the adversary can learn the source, target, and size of each message.

We assume that the adversary is computationally bounded and cannot break cryptographic schemes, find a private key given the matching public key of a non corrupted node nor forge a signature.

4 Problem Definition↩︎

The Fractional Spending Problem.  We now recall the Fractional Spending Problem. The interested reader can find the original formulation of the problem in [10] and a formulation generalising the Asset Transfer problem [1] to fractional spending in Appendix 8.

The problem introduces the notion of funds¹. Akin to accounts, funds carry a balance of the currency and have some clients called owners that can apply operations on them. Depending on the context, a client can act as a buyer or as a seller: a buyer is the one spending from a fund, and a seller is the one getting a payment. Any fund is denoted as \(F=\{F.owner, F.balance\}\). Some funds are created at system setup, and new funds are created via a successful settlement. We make no assumption on ownership of funds, and thus funds can be shared between multiple clients. We do not need Consensus since owners make independent payments of the same amount. This can be deduced from [1] and is discussed in Section [sec:noconsensus].

The fractional spending problem is parameterized by parameters \(s_1\) and \(s_2\).

\(s_1\) denotes the number of concurrent payments that can be validated in parallel, while \(s_2\) denotes the fraction such that, when doing a fractional payment, \(\frac{1}{s_2}\) of the balance of the fund is spent, so in total \(\frac{s_1}{s_2}\) of the balance can be spent. Thus, our problem is well defined only if we consider \(s_1 \leq s_2\). We should note here that the balance which is part of the fund definition does not change due to spending from the fund but the payment protocols guarantee that no overdraft occurs. The new balance is calculated as part of settlement when a new fund with a new balance reflecting the payments is created.

We consider three operations: Pay(F,\(pk_s\)), Settlement(F), Reedem(F):

• Pay(F,\(pk_s\)) is used by any buyer to execute a fractional spending from its own fund F to the seller identified by \(pk_s\). Any spending transfers \(\frac{F.balance}{s_2}\).

• Settlement(F) is used by any buyer to create a new fund with unspent balance.

• Redeem(F)² is used by any seller \(pk_s\) to create a new fund that collects all the fractional spending received through a Pay(F,\(pk_s\)).

Properties.  The fractional spending problem can be specified through the following properties

1. No double spending: (Safety) The sum of the value of all payments from a fund cannot exceed its balance.

2. Non-interference: (Liveness) A buyer should be able to make at least \(s_1\) payment in parallel successfully.

3. Eventual Retrieving (Liveness) Any correct buyer or seller invoking, respectively, Settlement(F) and Redeem(F) will eventually own a new fund.

4. Retrieving Consistency (Safety) the balance of new funds created through Settlement(F) and Redeem(F), respectively, do not exceed the unspent balance and do not exceed the sum of the fractional spending received.

5 \((k_1, k_2)\)-quorum systems and Initial Protocol↩︎

This section resumes what is proposed in [10]: \((k_1, k_2)\)-quorum systems and the protocol relying on them for fractional spending. We will build upon these later.

\((k_1, k_2)-\) quorums: combining intersection and non-intersection.  \((k_1, k_2)-\)quorum systems from [10] have both a lower bound on the size of the intersections to check operations can be safely applied; and an upper bound to control concurrency: \(k_1\) transactions can be concurrently validated but no more than \(k_2\) can. The intersections \(I_{k_1}\) and \(I_{k_2}\) of any \((k_1, k_2)-\)quorum \(Q\) satisfy with high probability (shortened to w.h.p.) for \(C\) any set of corrupted nodes, \(P_{k_1}\) any union of at most \(k_1 - 1\) quorums, \(P_{k_2}\) any union of at least \(k_2\) quorums, and some construction-dependent fractions \(\alpha\) and \(\beta\):

• Upper Bound: \(I_{k_1} = Q \cap (P_{k_1} \cup C)\) and \(|I_{k_1}| \leq \alpha |Q|\) w.h.p.

• Lower Bound: \(I_{k_2} = (Q \cap P_{k_2}) \setminus C\) and \(|I_{k_2}| > \beta |Q|\) w.h.p.

\((k_1, k_2)-\)quorum systems guarantee w.h.p., for a set of transactions \(T\):

• \((k_1, k_2)-\)liveness: \(T\) can be entirely validated in parallel if \(|T| \leq k_1\)

• \((k_1, k_2)-\)safety: some transactions of \(T\) will be rejected if \(|T| \geq k_2\)

Previous Protocol.  The protocol in [10] uses classic digital signatures from validators: a fractional payment is valid if signed by a \((k_1, k_2)-\)quorum. Recall that we name here settlement for a buyer settlement in [10] and redeem for a seller settlement. Settlement and redeem rely on secret sharing [23]. Without it, the adversary can learn the composition of the quorum \(Q\) used in a payment when its proofs are shared. Armed with this knowledge, the adversary can instantly erase the proofs from all validators in \(Q\)—because the size of \(Q\) is less than \(f\)—and correct validators would invalidate this redeem, preventing a correct seller from redeeming a payment that was successful.

A high-level presentation of a payment in [10] is as follows.

Such protocol has a message complexity of \(O(|Q|)\), where \(Q\) is the validating quorum, and its latency adds up to \(5\) message delays.

An high-level description of a settlement is as follows.

Because of secret sharing, message complexity of settlement is \(O(n^3)\).

A seller executes the following steps to redeem received payments.

The message complexity of this redeem is \(O(n^2)\) because of secret sharing.

Limitations.  Producing blind signatures during a payment (step [code:blindsignatures]) require an interactive phase between the buyer and the seller, resulting in a high latency. Each instance of secret sharing costs \(O(n^2)\) messages and \(5\) message delays, resulting in a high message complexity for settlement (step [code:secretsharing1]) and redeem (step [code:secretsharing2]). These mechanisms protect from an adaptive adversary and we replace them in StealthDust with a more efficient one: secret quorums.

6 StealthDust↩︎

We propose StealthDust, a fractional spending protocol using a new abstraction called secret quorums — of independent interest — hiding validators part of \((k_1, k_2)\)-quorums. The implementation of secret quorums is based on ring verifiable random functions and is more efficient than the protections of [10] described in Section 5 (see limitations [sec:limitations]). We present its properties, the cryptographic primitive rVRF and then the implementation based on rVRF.

6.1 Secret Quorums↩︎

Abstraction.  We extend secret leader election [11], [12] to a secret set, where sharing the proof generated by the set still preserves secrecy of the set’s composition. We model secret quorums as an abstraction \(\textit{sq}(k)\) with \(k\) as expected number of validators in a secret set, which can validate data such as a transaction and verify proofs of validation. Its interface is the following:

• \(\textit{validate}(d) \mapsto \mathcal{P} \cup \{ \bot \}\) can be called by a client to validate data \(d\) by a set of validators \(S\). It returns a validation proof \(P\) or \(\bot\) if \(d\) is invalid.

• \(\textit{verify}(P,d) \mapsto \{ true, false \}\) can be called by any node (client or validator) and returns true if and only if \(P\) is a correct validation proof for data \(d\).

It has the following properties:

• Unpredictability: for any correct validator \(v\in\Pi\), the adversary cannot guess if \(v\in S\) with probability greater than \(|S|/(n-f)\).

• Anonymity: validators stay anonymous among \(\Pi\), even after \(P\) is verified through \(\textit{verify}(P,d)\).

• Fairness: The probability for any validator to be in \(S\) is \(1/n\). In particular, the adversary cannot force a specific subset to be in \(S\).

• k-Cardinality: \(|S|=k\) in expectation.

• Verifiability: \(\textit{verify}(P,d)\) outputs \(\textit{true}\) if and only if \(P\) was correctly generated by \(S\) for \(d\).

Secret quorums can be adapted to work with any quorum system — classical or \((k_1, k_2)\). To do so, we denote \(w\) as the number of responses to wait for and \(q\) as the number of validation constituting a quorum. \(\textit{valid}(d)\) should be designed to return true if and only if \(d\) can be validated based on the state of a validator; and \(\textit{mutate}(d)\) is a callback to change a validator’ state when it validates \(d\).

rVRF.  Ring verifiable random function (rVRF) is a cryptographic primitive combining ring signatures and VRF. Usual VRF schemes can prove random numbers were produced using the private key matching a public key but this leaks the producer’s identity. rVRF is introduced in [13] to prove numbers are indeed random without revealing the producer: it proves each number was produced by one member of a set—the ring.

A construction of such \(\textit{rVRF}\) scheme is presented in [13]. It produces a signature in \(O(\log n)\) time the first execution, for a ring \(R\) of public keys of size \(n\), and the signature is of constant size. If a same signer uses \(R\) again, then the construction allows to a signature in \(O(1)\) time for a different message and seed. The verification time is always in \(O(1)\).

Implementation.  We assume every node can use a rVRF scheme to implement secret quorums. Our implementation is parameterized by \(V\), ranging from \(n\) to \(m\) and tuning complexity versus security: if \(V\) is close to be \(n\), then security is optimal but message complexity of payments is high; if \(V\) is close to be \(m\) then security is low but complexity is also low. We set \(\textit{MAX}\), the upper bound on the output of the VRF part of \(\textit{rVRF}\), to be orders of magnitude greater than \(V\): \(\textit{MAX} \gg V\). We denote by \(\eta\) any constant such that \(0 < \eta < 1\), used for probabilistic computations.

A correct client follows Algorithm 1 to validate \(d\). He computes a set of \(V\) validators called candidates using a deterministic function of \(d\), depicted in Appendix 9, Algorithm 6. All candidates test if they are in the quorum validating d using Algorithm 3. They produce a number out using \(\textit{rVRF}.\textit{Eval}\) that is uniformly random and unique given a \(\textit{seed}\) and their private key \(S_k\). They are selected if out is lower than the expected value below which a proportion \(k'/V\) of the uniform samples lie. Because the VRF selection is probabilistic, the number of validators selected is not exactly \(k\) validators but rather follows a binomial distribution centered on \(k\). To overcome this limitation, we try to select \(k' = k / (1 - \eta)\) validators in order to have \(k\) validators selected with high probability.

Messages with ring signatures can leak validators’ identities because the secret signer is the first one sending such message. To avoid this, validators send confirmation to the seller using gossiping. Moreover, we assume similarly to [10] that the seller batched multiple messages for multiple transactions together, so that validators for different transactions are contacted at the same time and the adversary cannot tell, just by observing the communication, which of the contacted validators validate which transactions.

The client waits for \(w\) correct ring signatures from selected validators; and the validation proof is the ring signatures collected with the random number \(N\) used as seed. Because a client contacts all candidates, the message complexity of \(\textit{validate}\) is \(O(V)\).

We use ring signatures as proofs of validation, which—unlike classical digital signatures—hide the specific signer. A ring signature only proves the signer was indeed part of the quorum thanks to the VRF. Algorithm 4 shows that such signature uses the whole set candidates as a ring. This ensures that a valid signature can only be produced by a validator which is in the set candidates, without requiring any additional validation beside the signature itself. Such signature also allows to retrieve the result of \(\textit{rVRF}.\textit{Eval}\) by the secret signer.

Nodes can verify if a validation proof for \(d\) is correct using Algorithm 5. It recomputes the seed, the ring and the threshold from d at lines [code:verifseed] to [code:verifthreshold]. They are used to verify that each ring signature r in signatures is valid line [code:verifcheck], i.e., \(v=\textit{true}\) if and only if was produced by \(\textit{rVRF}.\textit{Sign}\) using \(\textit{seed}\), \(\textit{d}\) and \(\textit{ring}\); and \(o\) is the result of \(\textit{rVRF}.\textit{Eval}\) by the secret signer using the same parameters. It also checks if a single validator did not produce many ring signatures by keeping track of the random output from the VRF. Indeed, a validator has only one output from the VRF and selected validators will have different random number with high probability. Ring signatures passing this check are collected in valids. The set valids is a proof if and only if it is greater than \(q\).

Proofs.  Fairness is proved in Lemmas 1 and 2; Lemma 1 also shows k-Cardinality. Unpredictability is proved in Lemmas 3 and Anonymity by 4 if \(V=n\). Verifiability is shown in Lemma 5.

6.2 Protocol for Fractional Spending↩︎

Because we follow roughly the same steps, we only detail StealthDust’ specific features and highlight the differences with [10]. An interested reader is redirected to Appendix 9 for our full protocol.

Parameters.  We rely on a secret quorum scheme \(\textit{sq}\), where data are fractional spending transactions, and parameterized for the quorum system to be a \((k_1, k_2)\) [10], described in Section [sec:k1k2], \(\textit{sq}\) is implemented by a \(rVRF\) signature scheme [13] and described in Section 6.1. Parameters are:

• \(m\) is the size of any \((k_1, k_2)-\)quorum and \(k\) is set to \(m\).

• \(\beta\) is from the bounds of the \((k_1, k_2)-\)quorum system such that the size of the intersection of a quorum with the union of at least \(k_2\) other quorums is greater than \(\beta * m\) w.h.p (see Section [sec:k1k2]). Thus, \(q = (1-\beta)*m\).

• \(w = m - (1 + \gamma)(f / n) m\) because \(m = (1 - \eta)m'\) validators will be selected by the VRF with high probability. Among them \((1 + \gamma)(f / n) m\) can be corrupted and never reply (see [10]).

• \(s_1 = k_1\) and \(s_2 = k_2\), where \(s_1\) and \(s_2\) are parameters of the fractional spending problem such as defined in Section 4.

Using secret quorums.  We replace the validation by a quorum, and specifically the quorum selection (steps [code:randomnoncebasedqselection] and [code:blindsignatures]), in a payment by a \(\textit{sq}.\textit{validate}(\textit{tx})\). Thus, buyers avoid producing blind signatures and even sellers are unaware of the composition of the quorum. On validators side, \(\textit{valid}(\textit{tx})\) expresses no other transaction from the same fund was seen by the validator nor it was settled; and \(\textit{mutate}(\textit{tx})\) marks \(\textit{tx}.\textit{fund}\) as seen and stores the produced signature for later settlement.

Validation proofs of a payment now hide identities so we can bypass secret sharing: we use the same settlements and redeems algorithms as [10] but with simple broadcasts instead of secret sharing (step [code:secretsharing1] settlement and step [code:secretsharing2] of redeem). We leave details for Appendix 9 but nodes can check if a payment is valid using \(\textit{sq}.\textit{verify}(P,\textit{tx})\), where \(P\) was produced by \(\textit{sq}.\textit{validate}(\textit{tx})\).

The correctness of StealthDust is straightforward from the one of secret quorums. We summarize complexities in Table 1. Recall that a settlement required each validator to use secret sharing, leading to an \(O(n^3)\) message complexity and a redeem required the seller to use secret sharing, leading to an \(O(n^2)\) message complexity. Because we bypass secret sharing with ring signatures, we shave a factor \(n\) compared [10]: message complexities are only \(O(n^2)\) for a settlement and \(O(n)\) for a redeem in StealthDust.

Multi-owner without Consensus.  Guerraoui et al., prove in [1] that a payment system — formalized as the asset transfer problem — where accounts are shared by \(k\) owners has consensus number \(k\). We argue here that StealthDust handles unbounded shared accounts without Consensus. The proof from [1] relies on different owners of a same account trying to send payments with different amounts such that only one of them is valid. This allows each owner to compute who won this hidden leader election by reading the remaining balance of the shared account.

StealthDust is a protocol of fractional payment. In this case, the amount of each payment is the same fraction \(\frac{1}{s_2}\) of the balance of the account. It is thus impossible for independent owners to compute the payment of which one was successful when there is 3 or more owners. This circumvents the result of [1].

7 Concluding Remarks and Future Work↩︎

We introduced secret quorums and implement a new protocol for the fractional spending protocol improving complexity. We have shown the relevance of this abstraction to tolerate an adaptive adversary because it protects the identities of nodes playing key roles in our protocol. It was particularly suited to introduce secret quorums on the fractional spending problem because the size of \((k_1, k_2)\)-quorums is smaller than the corruption bound \(f\) of the adversary. Our construction for its implementation is based on [13], but other constructions can be explored.

Moreover, secret quorums can be generalized to other problems. For instance, they could allow Byzantine Reliable Broadcast to tolerate adaptive adversaries when sampled quorums are considered, such as in [25]. Studying how \((k_1, k_2)\)-quorum systems can be used to leverage commutativity in other settings, is left for future work.

APPENDIX↩︎

8 Formalization of the Fractional Spending Problem↩︎

We generalize the formalization of [1] to the fractional case. Let \(\mathcal{F}\) be a set of funds, akin to accounts. and \(\mu: \ifmmode \mathcal{F} \else\) \(\fi \mapsto 2^{\ifmmode \mathcal{P} \else \mathcal{P} \fi }\) an ownership map that associate each fund with a set of clients allowed to pay from the fund. We make no assumption on \(\mu\) and thus handle funds shared between multiple clients. Depending on the context, a client can act as a buyer or as a seller: a buyer is the one spending from a fund, and a seller is the one getting a payment. The fractional spending problem is parameterized by \(s_1\) and \(s_2\): \(s_1\) denotes the number of fractional payment a buyer can do in parallel; \(s_2\) denotes the fraction such that, when doing a fractional payment, \(\frac{1}{s_2}\) of the balance of the fund is spent. Contrarily to [10], we batch settlements and redeems of multiple funds by using a set as parameter of these operations. We define the fractional-spending object type associated with \(\ifmmode \mathcal{F} \else\) \(\fi\) and \(\mu\) as a tuple \((Q, q_0, O, R, \Delta)\), where:

• The set of possible states is \(Q\) the set of all possible maps \(q: \ifmmode \mathcal{F} \else\) \(\fi \mapsto {\mathbb{N}}\times (\ifmmode \mathcal{P} \else\) \(\fi \mapsto {\mathbb{N}})\). Intuitively, each state of the object assigns each fund with the amount of currency it is holding along with a map registering the number of payments made to each client.

• The initialization map \(q_0: \ifmmode \mathcal{F} \else\) \(\fi \mapsto {\mathbb{N}}\times(\ifmmode \mathcal{P} \else\) \(\fi \mapsto 0)\) assigns the initial balance to each fund but without any payment yet.

• Operations and responses of the type are defined as \[\begin{align} O & = \{pay(F, s) : F\in\ifmmode \mathcal{F} \else \mathcal{F} \fi , s \in \ifmmode \mathcal{P} \else \mathcal{P} \fi \} \\ & \cup \{settle(S_F): S_F\subseteq\ifmmode \mathcal{F} \else \mathcal{F} \fi \} \\ & \cup \{redeem(S_F): S_F\subseteq\ifmmode \mathcal{F} \else \mathcal{F} \fi \} \\ & \cup \{read(F) : F \in \ifmmode \mathcal{F} \else \mathcal{F} \fi \} \end{align}\] and \(R = \{true, false\} \cup \ifmmode \mathcal{F} \else\) \(\fi \cup ({\mathbb{N}}\times(\ifmmode \mathcal{P} \else\) \(\fi \mapsto {\mathbb{N}}))\).

• \(\Delta\) is the set of valid state transitions. For a state \(q \in Q\), a client \(p \in\ifmmode \mathcal{P} \else\) \(\fi\) an operation \(o \in O\), a response \(r \in R\) and a new state \(q' \in Q\), the tuple \((q, p, o, q',r) \in \Delta\) if and only if one of the following conditions is satisfied:

  • \[\begin{align} o & = pay(F, s) \\ & \land ((r = true \land p \in \mu(F) \land q(F) = (balance, payments) \\ & \land \sum_{p'\in \ifmmode \mathcal{P} \else \mathcal{P} \fi }(payments[p']) \leq s_2 \text{ (no double spending)} \\ & \land q'(F) = (balance', payments') \land balance' = balance \\ & \land payments'[s] = payment[s] + 1 \\ & \land \forall s' \in \ifmmode \mathcal{P} \else \mathcal{P} \fi \setminus \{ s \}: payments'[s'] = payments[s'] \text{ (no other client received a payment)} \\ & \land \forall F' \in \ifmmode \mathcal{F} \else \mathcal{F} \fi \setminus \{F\} : q'(F') = q(F') \text{ (all other funds unchanged)}) \\ & \lor (r = false \land q' = q)) \end{align}\]

  • \[\begin{align} o & = settle(S_F) \\ & \land \forall F \in S_F: p \in \mu(F) \\ & \land r = F' \land q(F') = (0, no\_payments) \land \forall p'\in \ifmmode \mathcal{P} \else \mathcal{P} \fi : no\_payments[p'] = 0 \land p \in \mu(F') \\ & \land q'(F') = (balance', payments') \\ & \land balance' = \sum_{F\in S_F: q(F) = (balance, payments)} (balance - \frac{balance}{s_2}\sum_{p'\in \ifmmode \mathcal{P} \else \mathcal{P} \fi }payments[p']) \\ & \text{ (subtract amount spent)}\\ & \land \forall p'\in \ifmmode \mathcal{P} \else \mathcal{P} \fi : payments'[p'] = 0 \text{ (no payment made yet)} \\ & \land \forall F'\in\ifmmode \mathcal{F} \else \mathcal{F} \fi \setminus S_F: q'(F') = q(F') \text{ (all other funds unchanged)}) \end{align}\]

  • \[\begin{align} o & = redeem(S_F) \\ & \land \forall F \in S_F: (q(F) = (balance, payments) \land payments[p] > 0) \\ & \land r = F' \land q(F') = (0, no\_payments) \land \forall p'\in \ifmmode \mathcal{P} \else \mathcal{P} \fi : no\_payments[p'] = 0 \land p \in \mu(F') \\ & \land q'(F') = (balance', payments') \\ & \land balance' = \sum_{F\in S_F: q(F) = (balance, payments)} (payments[p] \frac{balance}{s_2}) \\ & \text{ (merge amount of payments received)}\\ & \land \forall p'\in \ifmmode \mathcal{P} \else \mathcal{P} \fi : payments'[p'] = 0 \text{ (no payment made yet)} \\ & \land \forall F'\in\ifmmode \mathcal{F} \else \mathcal{F} \fi \setminus S_F: q'(F') = q(F') \text{ (all other funds unchanged)}) \end{align}\]

  • \[\begin{align} o & = read(F) \\ & \land q = q' \text{ (all funds unchanged)} \\ & \land r = (balance\_r, payments\_r) \land q(F) = (balance\_q, payments\_q) \\ & \land balance\_r = balance\_q \text{ (returns the balance)} \\ & \land p \in \mu(F) \implies payments\_r = payments\_q \text{ (an owner knows all payments)}\\ & \land p \not\in \mu(F) \implies \forall p'\in\ifmmode \mathcal{P} \else \mathcal{P} \fi \setminus\{p\}: payments\_r[p']=0 \text{ (unknown payments to others)} \\ & \land payments\_r[p] = payments\_q[p] \text{ (seller knows payments received)} \end{align}\]

In other words, the operation of fractional payment is denoted \(pay(F,s)\) where \(F\) is a fund to spend from and \(s\) the seller. Its effect is to increment the payments counter of \(F\) such that when the buyer settles a set of funds \(S_F\) (in which \(F\) is) via \(settle(S_F)\), its total value is subtracted from \(\frac{1}{s_2}\) times the old balance for every payments recorded. Similarly, when the seller settles a set of funds \(S_F\) via \(redeem(S_F)\), his balance is incremented for each payment by \(\frac{1}{s_2}\) times the value of the fund the payment was made from. Both settle and redeem take effect into a new fresh fund that was not used before. Clients can use the \(read(F)\) operation to read the state of a fund \(F\) but due to the fractional nature of payments, they can only see the payments they received or the one they sent. Because the balance is updated only via settle or redeem, they can read the balance of any fund.

This specification is equivalent to the one proposed in [10] but there is few differences. For simplicity, and because their implementations are not the same, we distinguish between operations of settlement as a buyer and as a seller: we call settle settlements from a buyer and redeem settlements from the seller. Moreover, we only consider one type of funds and are tracked using the counter of payments made to each seller.

9 Full protocol↩︎

We present in details our new protocol StealthDust using a secret quorum abstraction \(\textit{sq}\), implemented with a Ring VRF scheme \(\textit{rVRF}\), and where the quorum system is a \((k_1, k_2)\). It solves the fractional spending problem with \(s_1=k_1\) and \(s_2=k_2\). Contrarily to [10], we batch settlements and redeems of multiple funds by using a set as parameter of these operations.

We start by Algorithm 6 to complete the implementation of secret quorum. It determines \(V\) unique validators based on a data \(d\), used to select which validators will test with the VRF if they are selected or not for a quorum. This algorithm is similar to quorum selection in [10].

States.  To be able to execute payments, clients are storing a set \(\textit{assets}\) of funds they own. For later redeem, clients are storing a list of their transactions denoted \(\textit{transactions}\) and \(\textit{proofs}\) a map from each transaction to its secret quorum validation proof justifying its validity.

For their validations duty, validators are storing a set \(\textit{funds}\) of all funds in the system, initially set to some common arbitrary value, a set \(\textit{seen}\) storing fund identifiers which they already validated a transaction from, a set \(\textit{settled}\) storing fund identifiers that were already settled, a set \(\textit{redeemed}\) storing transaction identifiers that were already redeemed and a map \(\textit{signatures}\) from fund identifiers to the ring signatures they produced. Every node also store a list of all validators public keys \(\textit{validators}\) used to generate ring signatures and select candidates.

Payments.  We present the protocol to achieve a payment between clients buyer and seller in Algorithms 7 and 8. We denote \(\langle m \rangle_{\textit{pk}}\) a message \(m\) that is signed using the private key matching the public key \(\textit{pk}\). We suppose that signatures are always verified and omit verification steps from algorithms. The buyer signs a transaction \(\textit{tx}\) with a fund and the public key of the seller, and sends \(\textit{tx}\) to the seller.

The seller uses \(\textit{sq}.\textit{validate}\) to check the validity of \(\textit{tx}\) with a secret \((k_1, k_2)-\)quorum. Secretely selected validators check the validity of the transaction using \[\textit{valid}(\textit{tx}) := \textit{tx}.\textit{fund} \not \in (\textit{seen}\cup \textit{settled}) \land \textit{pkb}\in\textit{funds}[\textit{tx}.\textit{fund}].\textit{owner}\] If the transaction is valid, they mutate their state to take it into account with mutate(tx) : \[\textit{seen} := \textit{seen} \cup \{ \textit{tx}.\textit{fund} \} \land \textit{signatures}[\textit{tx}.\textit{fund}] := (\textit{tx}, r, N)\]

A corrupted seller may never send a confirmation to the buyer. After waiting for a timeout, the buyer can assume that the payment was successful and if not he will learn about the amount not spent when executing a settlement. Moreover, the buyer has no way to check if a seller claiming that a payment failed is saying the truth. This can be fixed by making validators send ring signatures to both the seller and the buyer. For simplicity and because this issue is not considered in [10], we omit this detail in the pseudo code.

Settlements.  Algorithm 9 and 10 describe the protocol to achieve settlements. After receiving a request to settle a set of funds³ from a buyer, each validator sends to others validators the ring signatures generated when validating a transaction from a fund in \(S_F\), if they did. After receiving \(n-f\) such data from others, each validator locally reconstructs the transactions and the corresponding signatures attesting their validity. For each valid transaction, he will subtract the transaction from the sum of the balance of each fund in \(S_F\). The unspent balance is credited on a new fund \(F'\) and its data is sent to the buyer in a confirmation message. After receiving \(n-f\) same \(F'\), the buyer can add \(F'\) to its assets and remove settled ones.

Redeem.  The protocol to redeem is presented in Algorithms 11 and 12. It is a simple broadcast from the seller of the validation proof from a secret quorum collected during the validation of each transactions from a fund to redeem. Validators check the proofs and merge the value of each valid transaction into a single new fund. After receiving \(n-f\) same confirmations for the same fund \(F'\), \(F'\) is a valid new fund that can be added to the list of assets owned by the Seller. The transactions that were redeemed can be erased from the memory of the seller.

References↩︎