8 ms·

Asynchronous Consensus Without Trusted Setup or Public-Key Cryptography

157 points by simonpure 2y ago

monocultured 2y ago
This sounds interesting but the description goes way over my head. Anyone care to explain in layman's terms the concept and the non-obvious benefits?
- eterm 2y ago
  It's hard to answer that without you saying what you think the obvious benefits are. Consensus algorithms are important for all kinds of distributed computing problems. A simple example would be failover. If you have a leader database that replicates to 4 others, and you want another node to take over if the leader DB fails, then you need a consensus algorithm to prevent a situation where 2 different machines both think they're the new leader in a netsplit. There are many other equivalent problems in distributed computing, from atomic transactions to "exactly once" messaging systems. Asynchronous consensus is a model where you cannot make assumptions about the bounded nature of call timings, whereas in a synchronous model, you can assume everything is bounded. Byzantine fault tolerance is important for security under byzantine faults, that is to say malicious actors acting deliberately against what the protocol specifies they should do.
steelframe 2y ago
Their protocol only uses cryptographic hash functions, which means that it's post-quantum secure. One reason why this is significant is because existing post-quantum public key algorithms such as SPHINCS+ use much larger keys than classic public key algorithms such as RSA or ECDH. *Edit: As other have pointed out, for SPHINCS+ it's the signature size and not the key size that's significantly larger.
- EGreg 2y ago
  For those here who don’t know SPHINCS is essentially Lamport Signatures and SPHINCS+ is essentially removing the need to store “state” by using chains of hashes and a random oracle https://crypto.stackexchange.com/questions/54304/difference-between-gravity-sphincs-and-sphincs https://crypto.stackexchange.com/questions/54304/difference-... I prefer tham to lattice-based methods because it seems to me that cryptographic hashes (and other trapdoor functions) are more likely to be quantum-resistant than lattices (for which an algorithm like Shor’s algorithm merely hasn’t been found yet).
  - chc4 2y ago
    In case you haven't seen, there was actually a quantum algorithm on preprint recently for solving some class of learning with errors problems in polynomial time. https://eprint.iacr.org/2024/555 https://eprint.iacr.org/2024/555
    - fdupress 2y ago
      And since you apparently haven't seen, the abstract now includes the following note. > Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.
      - chc4 2y ago
        Oops, I did not, thank you!
    - westurner 2y ago
      [flagged]
- westurner 2y ago
  Only PQ hash functions are PQ FWIU. Other cryptographic hash functions are not NIST PQ standardization finalists; I don't think any were even submitted with "just double the key/hash size for the foreseeable future" as a parameter as is suggested here. https://news.ycombinator.com/item?id=25009925 https://news.ycombinator.com/item?id=25009925 NIST Post-Quantum Cryptography Standardization > Round 3 > Selected Algorithms 2022 > Hash based > SPHINCS+: https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization#Finalists https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography... SPHINCS+ is a hash based PQ Post Quantum (quantum resistant) cryptographic signature algorithm. SPHINCS+: https://github.com/sphincs/sphincsplus https://github.com/sphincs/sphincsplus
- jythonscript 2y ago
  Minor note, I'm not an expert in this field but I believe SPHINCS+ uses smaller key sizes than RSA, but is notable for producing much larger signatures than RSA or ECDSA.
- lagniappe 2y ago
  > Their protocol only uses cryptographic hash functions, which means that it's post-quantum secure Can you elaborate on this?
  - woodruffw 2y ago
    Inverting a general-purpose cryptographic hash function in the quantum setting is (roughly) as hard as it is in the classical setting. (Roughly because of Grover’s algorithm, but there are algorithms that perform similarly or better on classical machines. Which is why modern hash functions have relatively large margins anyways.)
api 2y ago
Haven’t had a chance to go through this but my instant #1 question is security against malicious nodes. All such protocols, even Bitcoin and friends, break under a sufficiently costly Sybil attack. The trick with cryptocurrency is to make the attack so expensive that it requires a highly economically irrational actor. What are the thresholds here?
- deleted 2y ago
  [deleted]
- chc4 2y ago
  This is a Byzantine agreement protocol. By definition it is a construction taking into account malicious nodes: that is what Byzantine agreement means. Table 1 says that this algorithm, like all the rest except one in the table, has fault tolerance 1/3 which is optimal. The second page also says "We consider the presence of a static adversary A that can corrupt up to t out of the n ≥ 3t + 1 parties. "
  - repelsteeltje 2y ago
    > ... static adversary A that can corrupt ... Doesn't that mean that an adversary using multiple identities would be able to do so? And therefore, some means of limiting the number of identities (through public key or prior trust) would still be desirable? What am I missing? Is this mitigated through staking?
    - mike_hearn 2y ago
      You're not missing anything. Systems like this assume there is a pre-created set of honest and independent nodes, which might later get hacked. They don't apply in the more realistic setting the PoW blockchain algorithm solves, where nodes can enter and leave the consensus at will and may be malicious or non-independent from the start.
      - chc4 2y ago
        You just do rounds of fixed sets of parties, like Ethereum proof of stake does. The set of nodes in each round are then needed to be 2/3rds honest. They then have Sybil resistance in each round as identities aren't free, since you need a stake in order to be selected for a round.
Rhapso 2y ago
So the protocol seems to boil down to: 1) Already have a leader "Dealer" 2) The leader builds a K-of-N set of shared secret keys. 3) They publish a mapping of each participant (participant_i->hash(secret_i)) 4) The leader transmits each key to each participant 5) Participants exchange secrets pairwise, armed with the upfront mapping of participants->secrets 6) Select K and a k-of-N secret scheme such that a majority of participants now have a shared key lots of the claims aren't meaningful: - "post quantum" for example isn't a special value in this situation. - "minimal use of cryptography" isn't relevant to practicality - The "experimental" component doesn't meaningful contribute to the conclusion. - No public-key-encryption really means "outsource sender identification to the network layer" - They pretend using a system of equations to solve for a shared key isn't"cryptography". In general the contribution of the paper reads as "offusicated". The lack of "public key cryptography" sets them up for a novel problem to solve, but it is an arbitrary handicap that doesn't provide utility. This is academic "make up a novel and nontrivial problem and then solve it", its of utility to the process of producing grad students and publication count but not something we need to get excited about. Read it like a survey paper of the space, which it does well as.
- xhkkffbf 2y ago
  I'm not as cynical. I think quests like this are important to understanding what's important and not-so-important in protocols. Quests like post-quantum algorithms are important for me not because I believe in the chance of any quantum machine coming along. It's because we learn so much. The foundation of many public key systems is pretty sketchy. We trust them because no one has publicly described how to break them. But that doesn't mean that the truth isn't out there.
  - Rhapso 2y ago
    Right but "Avoiding PKI" and "Secure Against Quantum Computers" barely even correlate. We have methods we consider post-quantum in heavy use. "PKI is generally sketchy and we would like to explore alternatives" is actually a much better rationalization than "post-quantum buzzword dropping"
bloopernova 2y ago
I kind of wish Git had a feature where multiple people could sign a PR or commit. Is there a multiple signature method that isn't "just" signing other people's signatures?
- deleted 2y ago
  [deleted]
- jazzyjackson 2y ago
  if you have a trusted central party you could reconstruct shards of a signing key, known as threshold cryptography eg Shamirs Secret Sharing
  - treyd 2y ago
    You don't need a trusted central party. You can sign using just shamir shares with a multi-round MPC protocol without ever reconstructing the real key. There's round-optimized schemes like MuSig2 and FROST for specifically schnorr-based signatures, which GPG doesn't support but are used in other places. I don't know what the effort to integrate that into git would look like.
    - kreetx 2y ago
      If you're just signing, is there any role for MPC in in there?
      - treyd 2y ago
        To do the signing without having to reconstruct the privkey in any single location.
- leni536 2y ago
  I guess you could sign a git note[1] on an existing commit. As a bonus you could add metadata about what you are actually signing off, like "approved" or even "rejected". Just adding an additional signature on top of an existing commit wouldn't carry too much info. What are you actually signing off on? Is it approval? Is it acknowledgement? And then it can be hard to sign off on something negative, like a code review that rejects. [1] https://git-scm.com/docs/git-notes https://git-scm.com/docs/git-notes
I___am___ejajul 2y ago
[flagged]
ngneer 2y ago
I was expecting multivariate polynomials, as those used to be all the rage. Just an example: https://ieeexplore.ieee.org/document/9066840 https://ieeexplore.ieee.org/document/9066840
glitchc 2y ago
Please note the Cryptology ePrint Archive is not a peer-reviewed source. The description of the paper may indicate another (peer-reviewed) publication, but this is entirely optional and not required for a submission. Edit: Adding this as a PSA in case folks start debating the veracity assuming this has undergone review by experts.
- ilya_m 2y ago
  To be fair, peer-reviewed publications are not what they used to be. For example, the conference reviewing process is not designed to validate correctness of the submissions. (Obviously wrong papers are filtered out most of the time, but this is a welcome side effect, not - apparently - their main objective.) See, for instance, recent Carlini's experience of reporting a demonstrably flawed paper to the chairs of a major conference: https://nicholas.carlini.com/writing/2024/yet-another-broken-defense.html https://nicholas.carlini.com/writing/2024/yet-another-broken...
  - Rhapso 2y ago
    Yeah, sadly this paper is a reasonable example of the status quo. There is a contribution in there under all the cruft (if we assume a trusted leader, and we can authenticate message origin, we don't have to use Public/private key encryption to build a shared secret key, hash functions and k-of-n secret sharing are enough) it is just very narrow and they feel like they have to "dress it up" a lot. If they actually wrote their contribution in clear terms they couldn't get it published because it sounds too simple. I think they should be able able to get it published without inflating it's complexity like this. They are just reacting to a broken system.
    - c0742e9366 2y ago
      It’s unfair to equate this paper to obviously flawed ones since all their claims seem to be properly substantiated. Also, the protocol does not assume a trusted leader (otherwise agreement would be trivially solved). In general, I am also not fond of this writing style. However, if one reads more papers published in this community/area, then one notices that many of them are written similarly. Since the primary audience of these papers are other researchers in the same area, they are presumably able to read past the cruft efficiently. I also agree that academia incentivizes overselling results. In this case, however, this is a nice result and not oversold by the authors (being somewhat knowledgeable in this field).
simonpure 2y ago
One of the original authors also published a follow up with some additional details and analysis that may be of interest (still reading through it myself) [0] [0] https://eprint.iacr.org/2024/696 https://eprint.iacr.org/2024/696
bumbledraven 2y ago
I noticed that Victor Shoup is an author. I recognize the name from citations in papers by cryptographer D. J. Bernstein (known for creating ChaCha20, Ed25519, qmail, and more). Shoup is referenced in over 100 pages on Bernstein's cr.yp.to domain (https://www.google.com/search?q=shoup+site%3Acr.yp.to https://www.google.com/search?q=shoup+site%3Acr.yp.to), so my first impression is to regard this paper as potentially legit and important. That said, my very uneducated guess is that the problem being solved here is not important for many users of distributed consensus algorithms. If you have a bunch of nodes that need to agree on something, you generally don't mind sharing a cryptographic secret among them as part of the set-up.

157 points by simonpure 2y ago

This sounds interesting but the description goes way over my head. Anyone care to explain in layman's terms the concept and the non-obvious benefits?

eterm 2y ago
It's hard to answer that without you saying what you think the obvious benefits are. Consensus algorithms are important for all kinds of distributed computing problems. A simple example would be failover. If you have a leader database that replicates to 4 others, and you want another node to take over if the leader DB fails, then you need a consensus algorithm to prevent a situation where 2 different machines both think they're the new leader in a netsplit. There are many other equivalent problems in distributed computing, from atomic transactions to "exactly once" messaging systems. Asynchronous consensus is a model where you cannot make assumptions about the bounded nature of call timings, whereas in a synchronous model, you can assume everything is bounded. Byzantine fault tolerance is important for security under byzantine faults, that is to say malicious actors acting deliberately against what the protocol specifies they should do.

steelframe 2y ago

Their protocol only uses cryptographic hash functions, which means that it's post-quantum secure. One reason why this is significant is because existing post-quantum public key algorithms such as SPHINCS+ use much larger keys than classic public key algorithms such as RSA or ECDH. *Edit: As other have pointed out, for SPHINCS+ it's the signature size and not the key size that's significantly larger.

EGreg 2y ago
For those here who don’t know SPHINCS is essentially Lamport Signatures and SPHINCS+ is essentially removing the need to store “state” by using chains of hashes and a random oracle https://crypto.stackexchange.com/questions/54304/difference-between-gravity-sphincs-and-sphincs https://crypto.stackexchange.com/questions/54304/difference-... I prefer tham to lattice-based methods because it seems to me that cryptographic hashes (and other trapdoor functions) are more likely to be quantum-resistant than lattices (for which an algorithm like Shor’s algorithm merely hasn’t been found yet).
- chc4 2y ago
  In case you haven't seen, there was actually a quantum algorithm on preprint recently for solving some class of learning with errors problems in polynomial time. https://eprint.iacr.org/2024/555 https://eprint.iacr.org/2024/555
  - fdupress 2y ago
    And since you apparently haven't seen, the abstract now includes the following note. > Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.
    - chc4 2y ago
      Oops, I did not, thank you!
  - westurner 2y ago
    [flagged]
westurner 2y ago
Only PQ hash functions are PQ FWIU. Other cryptographic hash functions are not NIST PQ standardization finalists; I don't think any were even submitted with "just double the key/hash size for the foreseeable future" as a parameter as is suggested here. https://news.ycombinator.com/item?id=25009925 https://news.ycombinator.com/item?id=25009925 NIST Post-Quantum Cryptography Standardization > Round 3 > Selected Algorithms 2022 > Hash based > SPHINCS+: https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization#Finalists https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography... SPHINCS+ is a hash based PQ Post Quantum (quantum resistant) cryptographic signature algorithm. SPHINCS+: https://github.com/sphincs/sphincsplus https://github.com/sphincs/sphincsplus
jythonscript 2y ago
Minor note, I'm not an expert in this field but I believe SPHINCS+ uses smaller key sizes than RSA, but is notable for producing much larger signatures than RSA or ECDSA.
lagniappe 2y ago
> Their protocol only uses cryptographic hash functions, which means that it's post-quantum secure Can you elaborate on this?
- woodruffw 2y ago
  Inverting a general-purpose cryptographic hash function in the quantum setting is (roughly) as hard as it is in the classical setting. (Roughly because of Grover’s algorithm, but there are algorithms that perform similarly or better on classical machines. Which is why modern hash functions have relatively large margins anyways.)

api 2y ago

Haven’t had a chance to go through this but my instant #1 question is security against malicious nodes. All such protocols, even Bitcoin and friends, break under a sufficiently costly Sybil attack. The trick with cryptocurrency is to make the attack so expensive that it requires a highly economically irrational actor. What are the thresholds here?

deleted 2y ago
[deleted]
chc4 2y ago
This is a Byzantine agreement protocol. By definition it is a construction taking into account malicious nodes: that is what Byzantine agreement means. Table 1 says that this algorithm, like all the rest except one in the table, has fault tolerance 1/3 which is optimal. The second page also says "We consider the presence of a static adversary A that can corrupt up to t out of the n ≥ 3t + 1 parties. "
- repelsteeltje 2y ago
  > ... static adversary A that can corrupt ... Doesn't that mean that an adversary using multiple identities would be able to do so? And therefore, some means of limiting the number of identities (through public key or prior trust) would still be desirable? What am I missing? Is this mitigated through staking?
  - mike_hearn 2y ago
    You're not missing anything. Systems like this assume there is a pre-created set of honest and independent nodes, which might later get hacked. They don't apply in the more realistic setting the PoW blockchain algorithm solves, where nodes can enter and leave the consensus at will and may be malicious or non-independent from the start.
    - chc4 2y ago
      You just do rounds of fixed sets of parties, like Ethereum proof of stake does. The set of nodes in each round are then needed to be 2/3rds honest. They then have Sybil resistance in each round as identities aren't free, since you need a stake in order to be selected for a round.

Rhapso 2y ago

So the protocol seems to boil down to: 1) Already have a leader "Dealer" 2) The leader builds a K-of-N set of shared secret keys. 3) They publish a mapping of each participant (participant_i->hash(secret_i)) 4) The leader transmits each key to each participant 5) Participants exchange secrets pairwise, armed with the upfront mapping of participants->secrets 6) Select K and a k-of-N secret scheme such that a majority of participants now have a shared key lots of the claims aren't meaningful: - "post quantum" for example isn't a special value in this situation. - "minimal use of cryptography" isn't relevant to practicality - The "experimental" component doesn't meaningful contribute to the conclusion. - No public-key-encryption really means "outsource sender identification to the network layer" - They pretend using a system of equations to solve for a shared key isn't"cryptography". In general the contribution of the paper reads as "offusicated". The lack of "public key cryptography" sets them up for a novel problem to solve, but it is an arbitrary handicap that doesn't provide utility. This is academic "make up a novel and nontrivial problem and then solve it", its of utility to the process of producing grad students and publication count but not something we need to get excited about. Read it like a survey paper of the space, which it does well as.

xhkkffbf 2y ago
I'm not as cynical. I think quests like this are important to understanding what's important and not-so-important in protocols. Quests like post-quantum algorithms are important for me not because I believe in the chance of any quantum machine coming along. It's because we learn so much. The foundation of many public key systems is pretty sketchy. We trust them because no one has publicly described how to break them. But that doesn't mean that the truth isn't out there.
- Rhapso 2y ago
  Right but "Avoiding PKI" and "Secure Against Quantum Computers" barely even correlate. We have methods we consider post-quantum in heavy use. "PKI is generally sketchy and we would like to explore alternatives" is actually a much better rationalization than "post-quantum buzzword dropping"

bloopernova 2y ago

I kind of wish Git had a feature where multiple people could sign a PR or commit. Is there a multiple signature method that isn't "just" signing other people's signatures?

deleted 2y ago
[deleted]
jazzyjackson 2y ago
if you have a trusted central party you could reconstruct shards of a signing key, known as threshold cryptography eg Shamirs Secret Sharing
- treyd 2y ago
  You don't need a trusted central party. You can sign using just shamir shares with a multi-round MPC protocol without ever reconstructing the real key. There's round-optimized schemes like MuSig2 and FROST for specifically schnorr-based signatures, which GPG doesn't support but are used in other places. I don't know what the effort to integrate that into git would look like.
  - kreetx 2y ago
    If you're just signing, is there any role for MPC in in there?
    - treyd 2y ago
      To do the signing without having to reconstruct the privkey in any single location.
leni536 2y ago
I guess you could sign a git note[1] on an existing commit. As a bonus you could add metadata about what you are actually signing off, like "approved" or even "rejected". Just adding an additional signature on top of an existing commit wouldn't carry too much info. What are you actually signing off on? Is it approval? Is it acknowledgement? And then it can be hard to sign off on something negative, like a code review that rejects. [1] https://git-scm.com/docs/git-notes https://git-scm.com/docs/git-notes

I___am___ejajul 2y ago

[flagged]

ngneer 2y ago

I was expecting multivariate polynomials, as those used to be all the rage. Just an example: https://ieeexplore.ieee.org/document/9066840 https://ieeexplore.ieee.org/document/9066840

glitchc 2y ago

Please note the Cryptology ePrint Archive is not a peer-reviewed source. The description of the paper may indicate another (peer-reviewed) publication, but this is entirely optional and not required for a submission. Edit: Adding this as a PSA in case folks start debating the veracity assuming this has undergone review by experts.

ilya_m 2y ago
To be fair, peer-reviewed publications are not what they used to be. For example, the conference reviewing process is not designed to validate correctness of the submissions. (Obviously wrong papers are filtered out most of the time, but this is a welcome side effect, not - apparently - their main objective.) See, for instance, recent Carlini's experience of reporting a demonstrably flawed paper to the chairs of a major conference: https://nicholas.carlini.com/writing/2024/yet-another-broken-defense.html https://nicholas.carlini.com/writing/2024/yet-another-broken...
- Rhapso 2y ago
  Yeah, sadly this paper is a reasonable example of the status quo. There is a contribution in there under all the cruft (if we assume a trusted leader, and we can authenticate message origin, we don't have to use Public/private key encryption to build a shared secret key, hash functions and k-of-n secret sharing are enough) it is just very narrow and they feel like they have to "dress it up" a lot. If they actually wrote their contribution in clear terms they couldn't get it published because it sounds too simple. I think they should be able able to get it published without inflating it's complexity like this. They are just reacting to a broken system.
  - c0742e9366 2y ago
    It’s unfair to equate this paper to obviously flawed ones since all their claims seem to be properly substantiated. Also, the protocol does not assume a trusted leader (otherwise agreement would be trivially solved). In general, I am also not fond of this writing style. However, if one reads more papers published in this community/area, then one notices that many of them are written similarly. Since the primary audience of these papers are other researchers in the same area, they are presumably able to read past the cruft efficiently. I also agree that academia incentivizes overselling results. In this case, however, this is a nice result and not oversold by the authors (being somewhat knowledgeable in this field).

simonpure 2y ago

One of the original authors also published a follow up with some additional details and analysis that may be of interest (still reading through it myself) [0] [0] https://eprint.iacr.org/2024/696 https://eprint.iacr.org/2024/696

bumbledraven 2y ago

I noticed that Victor Shoup is an author. I recognize the name from citations in papers by cryptographer D. J. Bernstein (known for creating ChaCha20, Ed25519, qmail, and more). Shoup is referenced in over 100 pages on Bernstein's cr.yp.to domain (https://www.google.com/search?q=shoup+site%3Acr.yp.to https://www.google.com/search?q=shoup+site%3Acr.yp.to), so my first impression is to regard this paper as potentially legit and important. That said, my very uneducated guess is that the problem being solved here is not important for many users of distributed consensus algorithms. If you have a bunch of nodes that need to agree on something, you generally don't mind sharing a cryptographic secret among them as part of the set-up.