[avalanche] Sort the stakes inside a proof
ClosedPublic
Actions

Authored by Fabien on Sep 8 2021, 15:56.

Details

Reviewers

PiRK

Group Reviewers

Restricted Project

Maniphest Tasks

Restricted Maniphest Task

Commits

rABC278b300a0620: [avalanche] Sort the stakes inside a proof

Summary

This diff computes a stake id and use it to sort the stakes in the proof, so the proof id is deterministic for a set or stakes.

This prevents proofs from conflicting when the same set of UTXO is shuffled inside the proof.

I deliberately did not update the stake hash used for computing the signature so single stake utxos remain valid and I don't have to update all the tests.

Ref T1676.

Test Plan

ninja all check-all

Diff Detail

Repository

rABC Bitcoin ABC

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

Fabien created this revision.Sep 8 2021, 15:56

Herald added a reviewer: Restricted Project. · View Herald TranscriptSep 8 2021, 15:56

Fabien requested review of this revision.Sep 8 2021, 15:56

Harbormaster completed remote builds in B16591: Diff 29857.Sep 8 2021, 16:08

PiRK added a subscriber: PiRK.Sep 9 2021, 06:48

PiRK added inline comments.

src/avalanche/proofbuilder.cpp
57 ↗	(On Diff #29857)	This is not blocking, but wouldn't it be easier to understand the process of building the proof if this `sort` was at the beginning of `ProofBuilder::build`, just before `getProofId` is called? Right now, this sorting which affect a class member and the order of the stakes in the serialized proof, is an undocumented side effect of what you would expect to be a simple getter.

Fabien added inline comments.Sep 9 2021, 07:38

src/avalanche/proofbuilder.cpp
57 ↗	(On Diff #29857)	This was in fact how I did it initially, but this make it possible to return a wrong value when calling `getProofId()` which is brittle. Another solution is do a sorted insert (ensure the stake container is sorted after each call to `addUTXO()`). This either means I need another type of container and convert it when doing the serialization (to keep the format compatible) or I sort after each UTXO addition. I wanted to avoid that last solution for performance reason but it's maybe not that bad, proof creation is not on a critical path.

Going to use a std::set of stakes to keep them sorted all the time. This is more complicated to implement (and test) but more robust in the end since it enforces consistency.

Using a set in the proof builder is a better solution but it breaks tests for duplicated inputs, since it's no longer possible to build them with the proof builder and so it requires a bit more test tooling. This is going to happen in a follow-up diff, for now I moved the TestProofBuilder structure to avalanche/test/util.h (will be expanded for duplicate inputs) and added a comment regarding the sorting function that needs to be removed from getProofId().

Harbormaster completed remote builds in B16596: Diff 29867.Sep 9 2021, 11:20

Fabien added a child revision: D10077: [avalanche] Use an ordered container for stakes in the proof builder.Sep 9 2021, 11:21

Sounds like a good plan. With a sorted container the state of the proof builder will be guaranteed to always be consistent.

This revision is now accepted and ready to land.Sep 9 2021, 11:40

Closed by commit rABC278b300a0620: [avalanche] Sort the stakes inside a proof (authored by Fabien). · Explain WhySep 13 2021, 19:04

This revision was automatically updated to reflect the committed changes.

Fabien added a commit: rABC278b300a0620: [avalanche] Sort the stakes inside a proof.