Surae 2018 August updates:

Greetings all,

In the month of August, I met a lot of you in person in Las Vegas at DefCon. This was fun, but I was sick most of the time, so I didn't get to spend as much time with you guys as I wanted.

I also posted the multisig paper on IACR, available here. I have posted it on my github here, and I have a meta-thread going to collect all review and copy-editing changes as they come up, see here. After we select a journal and send it out for peer review, I'll post any information from that process that I can in that issue, or in a similar issue.

I also continued my churn analysis; under a certain null hypothesis, it looks like ring sizes around 19 or 20 are unnecessarily large for transction histories to be concretely indistinguishable with only 3 churns. The write-up for this is in-progress (not quite ready for sharing). Under this hypothesis, using Chebyshev's inequality, we obtain a rough bound: for d churns and ring size r, with a probability of q of "de-fungible-izing" a transaction spending a tagged or poison output, with the attacker being the true spender or knowing the identity of the true spender of proportion p of the blockchain, transactions are (approximately) concretely indistinguishable up to this probability q if pqr^d > 1. The Chebyshev inequality is notoriously a very weak bound. For example, if the attacker controls half the blockchain and we want the probability of q to be smaller than 10^-6 (i.e.\ one in a million tagged transactions are identified) then Chebyshev's says we need r^d > 2*10^6. For a ring size of 20, this means d = 5 churns. However, as I mentioned above, the practical number for d is closer to 3 for a ring size of 20.

My churn analysis ended up extending to a game-theoretic formalization of the fungibility of a digital currency, which informally goes like this. Alice and Bob are two PPT algorithms with access to some non-empty wallets. Alice sends Bob a single transaction, whose outputs are "tagged." Bob selects a random bit b and is granted full access to the digital currency network for up to q blocks. Bob then sends Alice m new transactions, whose outputs are "deposits." Alice then outputs a bit b'. The bit b indicates whether Bob shall try to include at least one tagged output in at least one deposit, and the bit b' indicates Alice's guess at the value of b. Alice wins if b = b'. If for any ppt Alice, for any ppt Bob, Alice has a probability of success at most negligibly greater than 1/2, we say the protocol is (q, m)-fungible.

I also got horribly sick in the middle of the month, and I've been sort of inactive as a consequence. I hope that getting the IACR paper out the door and developing some concrete approaches to churn and fungibility is satisfactory for the community. I have been reviewing the DLSAG paper by Sarang and I have started writing up a paper whose title is already known: "Spender-ambiguous cross-chain atomic swaps of confidential assets." This involves formalizing threshold ring confidential transactions (thring confidential transactions?) using dual output ring signatures being described by Sarang.

I want to once again express my gratitude to the Monero community. My work so far at MRL has been extremely rewarding to me, both personally and professionally; I hope my work on multisignature can bring confidence to the community about the security of their funds, and I hope I can continue to contribute valuably to the Monero community.

Surae

I have watched the activity at MRL these last months with a smile on my face as much fundamental work for Monero was being done. Foundational work has always been a strong point of Monero and I fell that it is important to continue that focus. I will support this funding.

<3 your work Surae. Will donate

Donated.

Surae 2018 Q3 updates:

Greetings all,

I am joining my June and July progress reports for convenience.

June

The following is a description of my work for June 2018. I have been working on: 1. Ongoing work on the security of multi-signature schemes, the Knowledge-of-secret-key (KOSK) setting, rewind/replay attacks, and tree-based signing. This has included communication with community members and members of the cryptography community. The multi-signature MRL bulletin is still in prep (see below). . Ongoing work on consensus systems, selfish mining, cryptocurreny network dynamics, and population ecology-inspired network simulations. . Ongoing work on a formal proposal on selecting a fixed consensus ring size and how to go about selecting that ring size. 4. Developed a statistical test for Moneromooo. The test is based on hashrate to warn a node that the hashrate may have experienced a sharp discontinuity. I have a blog post (in preparation) planned working through the creation of such a test from a formal hypothesis testing perspective from mathematical statistics. . Volunteered on the ZCash Foundation Grant-Making Committee, helping guide the foundation in distributing $250,000 for projects related to "internet payment privacy infrastructure." 5. Assisted serhack and UkoeHB with their writing projects: Mastering Monero and Zero to Monero. 6. Held research meetings (see here, here, here, and here).

Here are some progress notes.

My time on multisignatures has been productive, but frustrating. I brought the multisignature paper mostly to it's current state (you can see it here), which is still "under construction." The knowledge of secret key (KOSK) setting has some problems with it unless it satisfies from strict formal requirements (which I'm looking into); abandoning the KOSK setting seems to expose us to a commit-and-reveal stage which might allow a certain sort of replay attack (an especially egregious problem in the case that a sloppy implementation leads to users exposing their private keys). I am communicating with some authors in the space to see if I can gain some clarity on proof details and attack routes. So, more research needs to be done, but we are rounding the corner here. The primary "works cited" include: 1. Bellare, Mihir, and Gregory Neven. "Multi-signatures in the plain public-key model and a general forking lemma." Proceedings of the 13th ACM conference on Computer and communications security. ACM, 2006. PDF link here 2. Maxwell, Gregory, et al. "Simple Schnorr Multi-Signatures with Applications to Bitcoin." (2018). PDF link here 3. Drijvers, Manu, et al. Okamoto Beats Schnorr: On the Provable Security of Multi-Signatures. IACR Cryptology ePrint Archive, Report 2018/417, 2018. Available at http://eprint. iacr. org/2018/417, 2018. PDF link here 4. Bellare, Mihir, and Oded Goldreich. "On defining proofs of knowledge." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992. PDF link here

Consensus systems. I have been working on network simulations (see here) and I have started looking into some other interesting approaches (see here). Additionally, I've been reading up on the following papers. I have no particular thoughts yet. This sort of reading is an ongoing sort of task that will always take time at MRL, so we can stay on top of new research in the area. . Team Rocket. "Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies", 2018. . Fruit chains (Pass, Rafael, and Elaine Shi. "Fruitchains: A fair blockchain." Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 2017.

Blockchains as an abstract object, selfish mining, and Ethereum as an economic predator: Call this a flight of fancy. I've made several updates to my PoissonGraphs project here, which simulates a network live for testing the dynamic properties of things like difficulty algorithms and consensus algorithms. Any change to our protocols would require looking at questions like "how stable is the algorithm?" and "how rapidly does the algorithm return to an operational equilibrium after a perturbation?" Some of these are difficult to analyse without just straight-up Monte Carlo simulations, which is what PoissonGraphs is meant to do. It's almost ready. It spits out a human-readable transcript that could be animated by an ambitious person. I am interested in eventually coupling two such networks together (like Bitcoin coexisting next to Ethereum) with an econonomic model of trade between the two simulating some central exchange authority.

In addition to that, I have a colleague (formerly at University of New Mexico, and soon to be at the University of Exeter) who is interested in writing a paper using population ecology inspired model of a smart contract system like Ethereum and a more usual system like Bitcoin, to model how a clever smart contract system like Ethereum could "prey" upon the hashrate of an innocent unsuspecting Bitcoin. Papers I'm reading that are loosely falling into this pile include the following. 7. Ritz, Fabian and Zugenmaier, Alf. "The Impact of Uncle Rewards on Selfish Mining in Ethereum." Arxiv. 2018. 8. Pass, Rafael, Lior Seeman, and Abhi Shelat. "Analysis of the blockchain protocol in asynchronous networks." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2017.

July was mostly taken up by multisignatures, which are freaking done! Well, ready for submission anyway.

My time on multisignatures came to an end: no more writing before submitting to a journal and receiving comments from reviewers. You can see the current incarnation here. We are currently considering different journal options.

A new sublinear ring signature scheme was submitted to MRL by Lai, Ronge, Schröder, Thyagarajan (all at FAU), Ruffing (at Blockstream) and Wang (at CUHK). Sarang started coding it in Python, and I've been working through his code with him looking for various indexing stuff, and generally learning about polynomial commitment schemes.

DLSAG: I started to review dual-output LSAG signatures for use as return addresses, written by Sarang, formalizing an idea by Pedro Moreno-Sanchez.

I want to once again express my gratitude to the Monero community. I am excited to meet all y'all at DefCon in 120 degree heat. I hope that my work so far at MRL has been pleasing to you guys, and I hope my work on multisignature can bring confidence to the community about the security of their funds.

If anyone is curious, here is the current multisig paper: https://v2.overleaf.com/read/bfjfkdgnhgvh

Donated

3 XMR donated from XMR.TO

donated