Venue: JSYS 2022 May_Papers

Reviews:

final_score: rating: Strong reject: this paper has serious problems, fixing it would definitely take more than three months
review_content: ## Review feedback

My feedback on this paper is mostly negative. I think it would require major revision(s) before it can be accepted for publication.

- The most major element that should be improved is the accuracy and subjectiveness. The paper mentions "absolute minimum amount of coordination" repeatedly but does not offer any method or model to quantify whether this is indeed the case.
  - Even in the CChimera protocol (the simplest), the step #2 _cross-shard exchange_ entails an all-to-all communication across all shards in a given transaction.
  - It is not clear if this is truly the "absolute" minimum, as I can imagine other approaches with various tradeoffs that would still work in the given model (ex: the client handling the cross-shard coordination step).
  - The paper should either (a) rephrase their contribution to make it more accurate and less subjective, or (b) discuss why their proposed approach offers the minimum amount of coordination.

- I enjoyed seeing how the paper builds on the insight of "limiting the types of workload supported". Generally, this kind of leveraging of application-specific semantics is indeed very powerful. Since this paper applies itself specifically to the UTXO model, and praises "minimum" coordination, it would be helpful to explain why is consensus even necessary within a cluster, since that part was not clear. In the _local inputs_ step, in particular, it seems like a Byzantine reliable broadcast primitive might have sufficed. I would be curious to see an explanation on why is consensus necessary.


### More specific comments:
- §4: The cluster-sending protocol is important, and should be at least described, not delegated to a reference [33].
- It is not clear how can a consensus protocol (such as the ones referenced in this paper) can be used so that "whenever a good replica learns that a decision D needs to be made, then it can force consensus on D"; this assumption should be detailed more, with the explanation in section 4 (local inputs) being insufficient.
- The solution in §4 seems to rely on a key property that the "set of currently-available inputs at S" (a shard) is known, which is a set in constant change, but it was not clear to me how this set was determined. This is likely related to the UTXO model from what I can tell.
- Given that the paper assumes the UTXO model, it was not clear how is integrity guaranteed. By integrity I mean that the values of the objects being destructed should be equal to the values of objects produced (if Alice has 10 tokens, she cannot send 10 to Bob and 2 to Carol).
- It's good that the paper tries to tackle the theoretical correctness of their protocol in §7. The proof was a bit high level and skipped over some parts, but found it of some use in helping my understanding.
- The authors should avoid vague statements such as "If malicious primaries behave sufficiently malicious to affect the normal-case operations, their behavior is detected, and the primary is replaced". Both malicious-fault detection and consensus reconfiguration are very difficult and subtle problems (impossible under various conditions), but this paper deals with both via "view-change", which skips a lot of relevant algorithmic parts.
- On §8.3, I have two remarks:
  1. I'm confused by the fact that the workload includes 50% multi-shard transactions, yet the baseline (AHL) seems to degrade or at best retain the same performance. This is not what I would expect, since  50% of transaction are single-shard, if I understood correctly, and then at least these 50% should turn up partitioned across different shards, manifesting into increased throughput, or I'm misunderstanding something here.
  2. The evaluation in both Fig. 9 and Fig. 10 deals with common-case, i.e., clients and nodes are all "good". In order to assess scalability and resiliency differences across the 3 Chimera versions, it would be important to model & evaluate what happens under non-graceful conditions. I'm suggesting this because the paper centers on resiliency, so it would make sense to address that property.


### Nits
- The paragraph "The choice of protocol.." (§1) would benefit a lot if it cited certain concrete examples (of prior work) that it is making reference to.
- The "problem" paragrah in §1 is actually an insight paragraph. A problem statement would be "Can one reduce the cost of coordination in the design of sharded consensus-based systems?"
- You mention a couple of times that clients "approve" transaction and not sure if I understand what that means.
- In the Abstract an Intro the paper makes it sound like it applies beyond UTXO ("..can be of use in non-UTXO environments") but this was never shown. That statement is confusing and should be clarified.
review_title: Requires major revisions

final_score: rating: Weak accept: good paper with flaws that can be fixed in three months
review_content: Decision
--------

Weak Accept


Summary
-------

This paper proposes a novel sharding mechanism with three variants. It achieves improved efficiency by only implicating relevant shards to transaction confirmation, leveraging the transaction DAG implied by the UTXO model. It defines and proves the desirable properties of the mechanism and provides some efficiency simulations.


Advantages
----------

Quite detailed model, protocol, security requirements, results and proofs. Very efficient and scalable protocol under favorable conditions.


Drawbacks
---------

The differences between the variants are not very well explained. The comparison with related work and the simulations could be improved. Some parts of the paper are hard to parse.


Detailed review
---------------

Abstract, "absolute minimum": This is a bit vague and strong, consider making a more concrete claim or removing this phrase.

Sec. 1, par. 1: "health care" -> "healthcare"

Sec. 1, par. 1: Missing references for supply chain tracking and advertising. You may also refer to non-academic projects.

Sec. 1, par. 1 & 2: "federated" -> "decentralized or federated"

Sec. 1, par. 3, "but are severely limited in their transaction processing throughput": almost verbatim repetition of a previous phrase

Sec. 1, par. 3, "permissioned solutions [...]  lack scalability as their performance is bound by the speed of individual participants.": Unclear, please clarify and ideally give a reference

Sec. 1, under "Problem": "In specific" -> "Specifically" (also elsewhere)

Sec. 1, left col of p. 2, bot: "deal with" -> "relax/avoid/do away with"

Sec. 1, last par.: According to the Abstract, O/RChimera relax the UTXO assumption. If that is correct, in the non-UTXO setting, what guarantees do these two variations provide? If that is incorrect, please rephrase the Abstract.

Sec. 1, last par.: missing period (.) at the end

Sec. 1: Some more intuition on how your scheme works should be given in the introduction. E.g. add a brief description of the steps 1-3 of Sec. 4, p. 4.

Sec. 2, par. 3: "can act Byzantine" -> "can act in a Byzantine manner"

Sec. 2, par. 3 & 4: I don't particularly like the bold font used in the notation, because bold is commonly used for vectors. I would prefer it if you change n_S, g_S, f_S and z.

Sec. 2, p. 3, par. 2: The network assumption is confusing. Since you need the reliable bounded-delay communication assumption (ak.a. Delta-synchronous network assumption) for crucial parts of the protocol, the asynchronous communication assumption does not apply. E.g. you need synchrony for the correctness of the argument of the proof of Theorem 4.1 towards cross-shard consistency.

Sec. 2, p. 3, par. 2: Mention that the authenticated communication assumption is why this work is in the permissioned setting.

Assumption 2.1: Better consider a single adversary that controls all corrupted parties, as is the usual terminology (instead of coordinating adversaries)

Assumption 2.1: the adversaries control exactly f_S' replicas, by definition. You may instead state that you assume n_S' > 3f_S'.

After Assumption 2.1: It should be mentioned that having only 1 owner per object makes your application-level expressivity weaker than Bitcoin, which supports multisigs, timelocks, hashlocks etc. Can shared ownership be emulated via MuSig-like (https://popeller.io/schnorr-musig2) key aggregation?

Assumption 2.2: The first part of the assumption is unclear. What does a-priori mean in this context?

Assumption 2.3: There are Bitcoin protocols (e.g. Lightning Network) in which an honest owner has to sign multiple conflicting txs. Possibly this is a non-issue, since such protocols typically also require shared ownership, which is precluded in your model.

Def. 3.1: "coordinate" -> "coordinates"

Def. 3.1, bullet 3: "decision D needs to be made" not well defined. Rephrase and/or add discussion/example of how this guarantee differs from the other two.

Sec. 3, p. 3, last par.: "inputs that no longer exists" -> "inputs that no longer exist"

Sec. 3, R1: "must only processes" -> "must only process"/"only processes"

Sec. 3, R5: Notation <tau>_c undefined. How is it different from tau? I suspect <tau>_c is tau + signatures from each input owner.

(#2) Sec. 4, "cross-shard exchange": since it doesn't completely trust other shards (it verifieas that I(S',tau) = D(S',tau) after all) and in order to ensure that no inputs are unmatched, shard S should also verify that each input of tau appears in exactly one m(S",tau) message.

Sec. 4: Parties process only one transaction per round instead of aggregating them in atomic blocks. This design choice should be justified.

Sec. 4, p. 4, col. 2, par. 1: "at each shards" -> "at each shard"

Sec. 4, p. 4, col. 2, par. 1: Mention that tau is valid only when accompanied by signatures on itself by all its inputs' owners.

Sec. 4, p. 4, col. 2, par. 1: "primary" undefined. If all of PBFT, PoE, HotStuff have a leader (primary), then define it in the first paragraph of the section. Otherwise elaborate.

Sec. 4, p. 4, col. 2, par. 1: P(S) currently proposes a message even if I(S,t) != D(S,t), which seems redundant.

Sec. 4, p. 4, col. 2, par. 1: The definition of D(S, tau) should mention explicitly that it refers to the inputs of tau.

Sec. 4, p. 4, col. 2, par. 3: It is unclear whether I(S', tau) and D(S', tau) are known to a party in shard S != S' only via the m(S', tau) message, or if the party needs to have extra visibility into S' to deduce I(S', tau) and D(S', tau).

Sec. 4, p. 4, col. 2, par. 3: What happens if a transaction looks valid to shard S but invalid to shard S'? It seems that S will wait forever for a m(S', tau) message that will never come, as S' sends nothing in that case. There should be some form of timeout, after which a "processed"(#1) transaction is dropped.

Sec. 4, p. 5, bullet 2: "that content for" -> "that contend for"

Sec. 4, p. 5, bullet 2: The first-pledge rule does not specify how to resolve disagreements between parties on which tx is the first.

Sec. 4, p. 5, bullet 2: The two rules are not discussed in the rest of the paper. How are they guaranteed to hold?

(#1) Secs. 3 & 4: The terminology "process" vs "execute" is very unclear. Normally these two terms are interchangeable. I think that one can see a tx but decide not to process it, or process it but then not execute it, or execute it but then not commit it. In detail, my understanding on the lifecycle of a transaction is: a party learns about it, validates it and ensures it belongs to its shard. It then _processes_ it, i.e. it tries to achieve consensus with its other shard members on the message m(S,tau). Once this is achieved, the party waits for the cross-shard exchange to complete and then it _executes_ tau, i.e. it updates its local state by destructing Inputs(tau) and constructing Outputs(tau) of its shard. Lastly it _commits_ to these changes by achieving consensus on the execution of tau with its other shard members. Only the last step, commitment, respects round ordering. Whether I'm right or not, this workflow should be clearly described with all relevant terms introduced and explicitly defined (not necessarily in delineated definitions, but clearly enough). Figure 2 should also be expanded to show all these phases with the respective names. Lastly, if my understanding of the flow is correct, I propose renaming "processing" to "intra-shard processing" and "executing" to "inter-shard processing" or equivalent.

Proof of Theorem 4.1, par. 1: If I understand correctly, without the verification of (#2), shard-applicability does not hold.

Proof of Theorem 4.1, par. 3: "as it is send" -> "as it is sent"

Sec. 4, last par.: This optimisation severely limits the usability of the blockchain. As mentioned earlier, it precludes protocols in which honest parties sign various alternative transactions that spend the same output. It additionally precludes techniques like Bitcoin's Replace-by-fee. Also, since agreement with other shards is anyway needed to securely construct the output objects, the bottleneck of communication still exists. Therefore the benefit of the optimization is unclear. Given the drawbacks, it must be argued that this approach is supported by the strong experimental efficiency improvements.

Sec. 4, last par.: Mention explicitly that, following the optimization, inputs are destructed at the end of the local input step (right?) and outputs are constructed at the end of the decide outcome step.

Sec. 4: Communication complexity is entirely missing. Is it quadradic in the number of parties of the biggest shard? Do other factors (number of shards, total number of parties, number of inputs/outputs, size of blockchain) influence it? This possibly needs its own subsection.

Sec. 5, p. 6, Modified PBFT: How does this protocol differ from PBFT between all parties of shards(tau)?

Sec. 5, p. 6, global prepare & commit: What exactly is a prepare/commit message from a replica?

Sec. 5, p. 6, global commit: "P(S'')" -> "C(S'')"

Sec. 5. Fig. 4, line 1: How much time does R wait before concluding this event happened?

Sec. 5. Fig. 4 & 5: This code seems to assume that the preprepare phase has completed successfully, because in the case of need for local recovery in Fig. 4, Fig. 5 assumes that there is some M for round \ro. Discuss what happens when no such M exists.

Sec. 5, p. 7, second-last par.: "this either by themselves" -> "either by themselves"

Sec. 5, p. 7, second-last par.: "at-least" -> "at least" (also elsewhere)

Sec. 5, p. 7, second-last par. & Fig. 5, line 10: What if an honest party receives f_S+1 or more VCRecoveryRQ messages but it can respond with a valid VCLocalSCR message? It seems that this case would be problematic, as it would trigger an unneeded local state recovery. Is there something preventing this?

Sec. 5, Fig. 6, line 7: Fix font of VCGlobalStateRQ

Sec. 5, Lemma 5.1: "exists shards" -> "exist shards"

Sec. 5, Lemma 5.1: "and there exist shards S_i \in shards(t_i), i \in {1, 2}" -> "and for all i \in {1, 2} there exist shards S_i \in shards(t_i)"

Sec. 5, Prop. 5.1: "every successful future view of S will recover M" undefined

Sec. 5, Prop. 5.1: M refers only to a single tx (c.f. def. in "Global preprepare"). How can a replica "recover" M in every future view, even in views that refer to future transactions? I think you need to specify that you refer to future views of the _same_ round.

Sec. 5, Prop. 5.1 proof, par. 3: "global preprepare certificate M†" -> "global preprepare certificate M‡" (If I understand correctly)

Sec. 5, Prop. 5.1 proof, par. 3: "the premise of this proposition hold" -> "the premise of this proposition holds"

Sec. 5, Prop. 5.1 proof, par. 3, "conclude that w = v*": in both bullets 1 and 2 it is said v* < w, therefore the conclusion is wrong. Also the base of the induction is v*+1.

Sec. 5, Prop. 5.1 proof, par. 3, "we assume that the conditions of Line 15 of Figure 6 do not hold, in which case M ∗ can only be recovered via global state recovery": There is also a 3rd case, Fig. 6, line 19.

Sec. 5, Prop. 5.1 proof, par. 3: "Q is good and send" -> "Q is good and sent"

Sec. 5, Prop. 5.1 proof, par. 4: "meet the conditions of Line 23 of Figure 6" -> "meet the conditions of Line 10 of Figure 6"

Sec. 5, Prop. 5.1 proof, par. 4, "Due to Line 22 of Figure 6, the global preprepare certificate for the newest view of S will be recovered.": It's nowhere explained that the VCGlobalStateR message is the global preprepare certificate.

Sec. 5, Prop. 5.1 proof, par. 4, "v* is the newest view of S": I thought v*+1 is the newest view, please clarify.

Sec. 5, Prop. 5.1 proof, par. 5, "M‡ is recovered via either Line 16 of Figure 6 or Line 23 of Figure 6.": Since it's recovered due to a NewView proposal (not a NewViewGlobal one), how can M‡ be recovered via line 23?

Sec. 5, Prop. 5.1 proof, par. 5, "Analogous to the proof [...] also conclude M‡ = M*": I don't get this, please clarify/expand.

Sec. 5, Prop. 5.2 proof, bullet 1: "R has a local commit certificate C(S''), S'' ∈ shards(τ)." -> "R has a local commit certificate C(S''), for some S'' ∈ shards(τ)."

Sec. 5, Thm. 5.2 proof: The proof is persuasive in the accept & commit case, but the argument is not clear in the abort case.

Sec. 5, Prop. 5.3: "optimistic case" is not formally defined.

p. 10, last par.: "at-most" -> "at most"

Sec. 6, par. 3: Mention that the second consensus step is intra-shard.

Thm. 6.1 proof: "shard-applicability follow directly" -> "shard-applicability follows directly"

Thm. 7.1 proof: "there exists transactions" -> "there exist transactions"

After proof of Thm. 7.1: "transactions that content for" -> "transactions that contend for"

After proof of Thm. 7.1: "shards; while" -> "shards, while"

p. 12, last par.: "not behave malicious" -> "not behave maliciously"

p. 12, last par.: "behave sufficiently malicious" -> "behave sufficiently maliciously"

Subsec. 8.1: It would be better to add clearly distinct use-cases for each of the three protocol variations. Especially the difference of Core and Resilient Chimera elude me.

p. 13, Fig. 8: "Principle Technique" -> "Principal Technique"

p. 13: Please introduce (non-)blocking locks.

Subsec. 8.2: "CHAINSPACE takes one more round as in RCHIMERA." -> "CHAINSPACE takes one more round than RCHIMERA."

p. 14: "can only processing" -> "can only process"

p. 14: " transactions that content" -> " transactions that contend"

Sec. 8: There is extensive discussion on the number of phases and steps of each protocol, but the efficiency of each such step is not extensively discussed. If each Chimera step is very expensive, the total latency could be worse than other protocols with more steps.

Subsec. 8.3, par. 2: Why did you choose only AHL for comparison? Justify.

Subsec. 8.3, par. 3: In Fig. 9 the number of objects is not that interesting by itself. It would be better to know _how many_ shards are involved in each (i.e. in the average) tx.

Subsec. 8.3, par. 3: The simulation of Fig. 10 is poorly explained. How many txs have been handled? What exactly does the simulation involve? Which of the three protocols was run?

Subsec. 8.3: The simulations assume a very large number of very small shards. Under such circumstances, the per-shard honest supermajority assumption is unreasonable. Please add simulations with a much larger number of parties per shard -- a smaller total number of shards is OK.

Subsec. 8.3, "A closer look at the data does reveal excellent scalability of AHL": Are you referring to the experiments of [17]?

Sec. 9, "A few fully-replicated [...] multi-shard design": I don't understand this sentence, please rephrase.

Sec. 9: "orders of magnitudes" -> "orders of magnitude"

Sec. 10 title: "Conclusion" -> "Further work & Conclusion"

Sec. 10: "more-general" -> "more general"
review_title: Problem: Sharded Resilient Transaction Processing with Minimal Costs

final_score: rating: Weak accept: good paper with flaws that can be fixed in three months
review_content: Paper summary: Sharding is a common approach to make distributed systems scale. We partition the network into groups of smaller nodes, referred as shards, and each of those process incoming transactions in parallel. One unique challenge in this setting is due to cross-shard transactions. For example, the inputs of a transaction can be in different shards. In such cases, the involved shards need to communicate, and ensure that the transaction is processed correctly, i.e., either both inputs are destroyed, and the output is created, or none of that happens. This paper introduces cross-chain transaction processing algorithms particular to the UTXO model. By tailoring their algorithm to this particular setting, they come up with more efficient approaches than algorithms that are more generic.


Questions&Comments:
1-In the paper, it says that, "Due to this, CCHIMERA will not undo any pledges of objects to the execution of any transactions." 
So let's say I submit a transaction with inputs I1, I2 where I1 resides in S1, and where I2 is an invalid input, doesn't exist in any shard.=S1 will locally run consensus, and broadcast m(I1, S1). However, it is not going to receive m(I2, S2), and will abort. What does this abort do exactly? If I later submit tx <I1, O1> to send only I1, am I not able to do so? If so, what exactly is the benefit of this? Or am I understanding this incorrectly?

2- There are some cross-shard transactions that are not considered in paper, but introduced in sharded blockchain papers such as: https://eprint.iacr.org/2017/406.pdf, https://eprint.iacr.org/2018/460.pdf, https://eprint.iacr.org/2022/413.pdf. A brief compare/contrast with these methods would be helpful. Especially the third papers cross-shard method also seem to be particularly suited to UTXO model.

3- Is there a particular reason to only include AHL in the experimental analysis as the baseline? Could it be expanded to some other cross-shard methods mentioned in the paper?

Overall,  I believe this is a good paper that considers a practical and timely problem, and concretely demonstrates its benefits over at least some baselines concretely. 

review_title: Faster x-shard transaction by making use of UTXO assumptions

Meta-review: metareview: Dear Authors,

We regret to inform you that your submission has not been accepted for publication at this round of JSYS. As you will see at the reviews the paper's topic is indeed of interest in the community however the current manuscript lacked in rigor of the definitions and security arguments. We hope that the reviews will prove to be helpful towards your work.

Best regards, JSYS Commitee
confidence: 5: The area chair is absolutely certain
Decision: Weak accept: good paper with flaws that can be fixed in three months