MAVE: Digital Signature Protocol for Massive bulk verifications

[Sergio_Demian_Lerner]

As I promised in the thread about Poker, here is the preliminary version of my paper on new digital signature protocols suitable for Bitcoin-like networks.

I've posted the MAVE paper on my blog:
http://bitslog.wordpress.com/2012/04/09/mave-digital-signature-protocol-for-massive-bulk-verifications/

Another paper (HBOW) with notes of how to properly implement MAVE for a p2p cryptocurrency is coming soon.

Please read it, comment it and give feedback.

Thanks.
 Sergio.

[Etlase2]

I am reading it now and will give feedback when I am finished. I am very interested because the cryptocurrency I am designing encoin is planning to use signature aggregates and a system of reputation and consensus. This might have a very useful application.

[cunicula]

I'll bump this because I am eager to hear about it. Can you provide a short summary in the OP of 1) what the issue with the current bitcoin protocol is 2) how your protocol might help resolve this issue.

I think this might help attract more interest.

[Sergio_Demian_Lerner]

1) Bitcoin does not scale well (this has been discussed, refuted and debated, so this is just my opinion)

2) With an alternate digital signature system, it can scale upto 1000 tps (transactions per second) with an average computer, and some idle CPU time. Periodic balance sheets are required though.

A cryptocurrency based only on MAVE has the drawback that confirmation times are higher. So I would propose a hybrid system, using MAVE for low valued transactions and ECDSA for high value payments.


In a couple of days I'm posting a second paper with implementation details...

Best regards,
 Sergio.

[cunicula]

Can you use a proof-of-stake element as a source of txn verification security? Many people, not just me, view stake as a more secure and lower cost method of achieving consensus on txn validity than proof-of-work.

[Sergio_Demian_Lerner]

Yes, MAVE adapts well to the proof-of-stake model (but implementation really matters).

Note: MAVE REQUIRES checkpoints (or user defined limits in transaction amounts) in order to reduce the incentive to revert payments accumulated from the last checkpoint.

 
Bye!

[cunicula]

Yes, MAVE adapts well to the proof-of-stake model (but implementation really matters).

Note: MAVE REQUIRES checkpoints (or user defined limits in transaction amounts) in order to reduce the incentive to revert payments accumulated from the last checkpoint.

 
Bye!

In that case I will read your paper carefully and try to comment on economic aspects (the technical details are largely beyond me, but security involves economics as well).

[Sergio_Demian_Lerner]

If your interest is purely economical, I recommend you to skip MAVE-3 paper and wait a few days more until I publish MAVEPAY paper, where I apply MAVE to define a p2p currency.

Also I calculate the cost of handling 1000 tps for 5 million users at aprox. 10 USD per user/month. (this figure includes electricity, hardware amortization, bandwidth usage, etc.)

Bye!

[finway]

Interesting.

So MAVE costs less GPU/CPU power to verify, while staying at  the same level of security than ECDSA?

Or MAVE use a ledger_based_system rather than transactions_based_system to save storage ?


EDIT: First glance, too complicated. Insurance? Really ?

EDIT: The real problem is, MAVE, as a new cryptographic algorithm, is it safe? Are you a Cryptographer ? I think we should stop reinventing wheels.

[Mike Hearn]

Thanks for this. Don't be discouraged by the minimal feedback so far. Your paper is large and complex, so it will take some time to work through it and fully digest. Also some people have previously posted papers here that appeared at first to be useful but were actually of fairly minimal contribution.

However so far (I'm on page 6) it seems credible and worth spending the time to understand.

One minor thing - I'd suggest asking somebody to proofread it and run it through a spelling checker, eg:

7.1. Public key Creation. A MAVE key public is built by applying multiple times a hash function to a seed message, creating a hash chain. The first message
is a random or psoudorandom seed

[Sergio_Demian_Lerner]

Thanks Mike for the feedback related the typos and for the patience to reach page 6. Have you finished it?

I want to point out that the concept of MAVE is very simple. If the paper is complicated, then is my fault in explaining it (my native language is not English).

Regarding finway questions:

1) MAVE, as a new cryptographic algorithm, is it safe?

In the paper I sketch of a proof of resistance for three types of attackers I can identify. As my humble opinion, is it secure. Please review the paper and try to break it! The underlining security of the scheme is the impossibility of inverting a one-way hash function, which is the same assumption Bitcoin relies on for mining.

2) Are you a Cryptographer ?

I´d like to think myself as one. But probably I´m not, since I don´t like writing proofs. Though my graduate thesis was about new developments in cryptography, and I was a teacher assistance on cryptography in university,  and I have spent many years doing computer security, and I have a few of patents on crypto.
Make your own mind.

3) I think we should stop reinventing wheels.
Tell that to Satoshi 

We should start reinventing, re-engineering,  and re-thinking, all time. The moment you think a problem is "solved", the moment you cannot innovate.

Best regards,
 Sergio.

P.S: Today or tomorrow I´m publishing the MAVEPAY paper.

[cunicula]

Looking forward to it.

On a side note, it would be interesting to have an initial currency distribution system arranged around.poker free rolls and subsidized pay to enter poker tournaments. It would.be.novel to.do poker p2p, but not essential.  Txn Verification could be done using another system. Distributing the currency via proof-of-poker could go viral and build up a user base interested in its functionality for non-subsidized gambling.

How to build a user base is a big challenge, regardless of the technological sophistication of the currency design.

[Mike Hearn]

No, I didn't finish it yet, I was busy last night and will be busy for the next few days too. I'll post here when I've finished reading it.

I'm sure the underlying concept seems simple to you, but the paper is quite long and lays out several variants of the same algorithms with different sets of tradeoffs and constraints. I need to not only fully understand what you're proposing but think about ways it could go wrong.

Probably, it'll be easier to see how it all fits together once the MAVEPAY paper is out.

[Sergio_Demian_Lerner]

I´l like the term "proof-of-poker", whatever that mean!  

Note: MAVEPAY is not about poker, but It could be used for paying bets, since payments are really lightweight. (comment: though confirmation time is an issue)

There are two fast-tracks for bootstrapping a p2p coin:

1. Black market.
2. unregulated but secure poker gambling.

The remaining uses can also bootstrap a cryptocoin, but much slowly.

Doing (2) is quite challenging, but it can be done. I spent a year (before Bitcoin was created) to research on a new method to solve the mental poker problem. I´ll post the paper afterwards, so you can check it (it´s almost 70 pages long though)

But I would prefer MAVEPAY to some time in the future be included in Bitcoin and to form an hybrid, and in the paper I describe how to do it. It could be done in such a way that it don´t break older clients, but older clients won´t see the money going back and forth between Bitcoin and MAVEPAY (only money going out of Bitcoin).

Anyway, instead of talking and talking about it, I should go to TeXnicCenter and finish the damn paper!

Bye!

[Sergio_Demian_Lerner]

As I promised, I’m publishing the preliminary paper on how to apply MAVE-3 to P2P cryptocurrency. I spent some time re-thinking everything and meanwhile (at 2 a.m.) I designed a new one-time digital signature algorithm with 320 bits signatures, and 80 bit public keys, that is faster than RSA.  Better than Lamport’s but probably not better than Merkle-Winternitz. Every time I think I’ve finished something, I start a new thing…

Apart from the description of the new protocol, you’ll find interesting proposals for Bitcoin evolution such as:

•     Combining Multiple Digital Signature Algorithms into a single P2P currency
•     Protection from Miners selfishness
•     Adding a Proof-of-work for every Bitcoin transaction, and how the network can deal with this.
•     Free market and the principle of Least Required Security (LRS) to optimize network resource usage.
•     How to achieve more advanced transaction fee rates.
•     Hybrid systems
•     The hidden costs of maintaining a Bitcoin client.

Download the paper from: http://bitslog.wordpress.com/2012/04/16/mavepay-a-new-lightweight-payment-scheme-for-peer-to-peer-currency-networks/

 

Enjoy it!

[gmaxwell]

As I promised, I’m publishing the preliminary paper on how to apply MAVE-3 to P2P cryptocurrency.

The paper would be a lot more readable if it didn't constantly make factually incorrect statements about Bitcoin, it makes it somewhat irritating to read.

Some examples,  (though there are a great many— I think, in fact, the majority of the comments about the bitcoin system are arguably incorrect or misleading— including things as simple and factual as transaction sizes)

One of the key differences between Bitcoin and MAVEPAY is that Bitcoin has no "free rides". Every transaction can (and ussualy must) pay a fee.

This is incorrect, and you could have verified in just a couple minutes that an overwhelming super-majority of transactions pay _no fee at all_ right now.

Though fees are one mechanism bitcoin uses for anti-dos— resulting in a _reusable proof of work_ system which is arguably superior to any one-shot POW system, at least so long as mining is creating substantial amounts of coin,  Bitcoin also uses coin-immobility-time as an anti-dos mechanism— and the effectiveness of this is why most txn don't carry fees.

One of the problems with Bitcoin is that, in order to prevent transactions of being broadcast ad-infinitum, each client maintains a hash table of cryptographic hashes of each transaction ever seen and avoids reprocessing a transaction previously processed by checking every transaction against this table. This protocol requires the eternal storage of transaction hashes.

I'm not even sure how you're making this error.  It simply isn't true.  Transactions must spend a previously existing transaction, and they exhaust it in the process thus making duplicates of that transaction invalid. Nodes do remember transactions they've already forwarded to peers to avoid excessive rapid retransmission, but there is no protocol requirement of this and the storage is purely in memory not eternal.

Perhaps it would be better in the future to describe your system without constant incorrect references to the Bitcoin system.

[I don't mean to be entirely negative—  the PoW-Chain-staggered-commitments as signatures is quite clever.  I'm not convinced as to it's use in currency systems, especially since ecdsa signatures (esp with the proper curve selected and bulk validation) are not that much slower, nor are lamport signatures that much bigger... but it's still a neat idea]

[Sergio_Demian_Lerner]

Dear gmaxwell,
 Some comments on Bitcoin were favor to it, and not against. The fact that Bitcoin has no free-rides is a pro and not a con!
MAVEPAY, on the contrary, has the DRAWBACK that it cannot allow fees to be paid in all types of messages. Bitcoin is better in this respect: you can (if you want) pay fees in every message, so that the network has a incentive to include them in a mining block.

The sentence  "Every transaction can (and usually must) pay a fee" is somehow misleading, and you're right I should have said  "Every transaction can (and generally do) pay a fee".

Regarding the issue of eternal storage of transactions you're completely right: it's not a problem of the protocol but a problem of the implementation. I know there are now strong efforts to formally describe the protocol (as in the thread "Satoshi Client Operation: Overview"). Nevertheless still Satoshi Bitcoin client source code is the main reference for the description of the protocol.

Last but not least, I want to thank gmaxwell of reading the paper and make these useful comments. Since the published paper is preliminary, I will correct them in the final one.

Regards,
 Sergio.

[marcus_of_augustus]

Interesting.

Do you cover the specifics of any total anonymity possibility for MAVE? (I didn't see it briefing through the papers).

[Sergio_Demian_Lerner]

Interesting.

Do you cover the specifics of any total anonymity possibility for MAVE? (I didn't see it briefing through the papers).

No. I specifically left Total anonymization out of the MAVEPAY paper, since anonymization gos against performance in every protocol I´ve seen. MAVEPAY aim is to have the best performance, and so pseudo-anonymous transactions are more expensive in MAVEPAY and total anonymization is not granted by the protocol.

I´m working on the paper of a system with total anonymization as the design rule. I´ve already designed it. Nevertheless, it uses a lot of PK crypto (signatures, trapdoor mixes, universal re-encryption, zero knowledge proofs). I think its performance would be 10 tps (and the bottleneck would be hard disk block chain storage).

Sergio.

[marcus_of_augustus]

Interesting.

Do you cover the specifics of any total anonymity possibility for MAVE? (I didn't see it briefing through the papers).

No. I specifically left Total anonymization out of the MAVEPAY paper, since anonymization gos against performance in every protocol I´ve seen. MAVEPAY aim is to have the best performance, and so pseudo-anonymous transactions are more expensive in MAVEPAY and total anonymization is not granted by the protocol.

I´m working on the paper of a system with total anonymization as the design rule. I´ve already designed it. Nevertheless, it uses a lot of PK crypto (signatures, trapdoor mixes, universal re-encryption, zero knowledge proofs). I think its performance would be 10 tps (and the bottleneck would be hard disk block chain storage).

Sergio.

Ok, thanks for clearing that up. I had read your earlier blog posts and assumed that MAVEPAY was "the one". I'm more interested in the total anonymous system is why I just briefed through MAVEPAY papers. Seems to be obvious, in hindsight, that there will be a trade off between anonymity and system performance, yet interesting never-the-less, once the details are fleshed out.