And I forgot to say, nice one Bill!
Topic: Lightweight Cryptos without Block Chain Bloat (Coq Development and Paper) (Read 1443 times)
February 10, 2015, 06:13:14 PM
Bump.
And I forgot to say, nice one Bill!
And I forgot to say, nice one Bill!
February 09, 2015, 05:01:42 PM
@gmaxwell RE: POS
Have you reviewed the research and modelling by Consensus Research relating to multibranch forging? They cite that paper as one of the basis of their research..
https://bitcointalksearch.org/topic/nothing-at-stake-long-range-attack-on-proof-of-stake-consensus-research-897488
They will soon be launching a testcoin with a modified forging algo, based on their research.
Have you reviewed the research and modelling by Consensus Research relating to multibranch forging? They cite that paper as one of the basis of their research..
https://bitcointalksearch.org/topic/nothing-at-stake-long-range-attack-on-proof-of-stake-consensus-research-897488
To summarize the discussion, known claimed attacks on proof-of-stake distributed consensus algorithm(and concrete implementations) at the moment:
1. Short-range attack - attacker can offer better chain started few blocks behind current canonical chain. The attack is possible at the moment, the only likely outcome though is just gathered fees increase for an attacker. In our simulations this kind of attack is possible mostly when a long delay occurs due to low target. By the way, the attack has positive aspect for network, as it shorten delays average between blocks. So attacker gets extra fees for a good job done
2. Long-range attack - attacker can start fork hundreds or thousands blocks behind current chain. From our investigations the attack isn't possible.
3. Nothing-at-stake attack - not possible at the moment! Will be possible when a lot of forgers will use multiple-branch forging to increase profits. Then attacker can contribute to all the chains(some of them e.g. containing a transaction) then start to contribute to one chain only behind the best(containing no transaction) making it winner. Previous statements on N@S attack made with assumption it costs nothing to contribute to an each fork possible and that makes N@S attack a disaster. In fact, it's not possible at all to contribute to each fork possible, as number of forks growing exponentially with time. So the only strategy for a multibranch forger is to contribute to N best forks. In such scenario attack is possible only within short-range e.g. with 25 confirmations needed 10% attacker can't make an attack. And attack is pretty random in nature, it's impossible to predict whether 2 forks will be within N best forks(from exponentially growing set) for k confirmations. So from our point of view the importance of the attack is pretty overblown.
4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.
If you know any other kind of attack, please add. Please note IPO properties of a concrete coins etc isn't related to proof-of-stake distributed consensus problems.
And Consensus Research is going to work on better proof-of-stake prototyping & implementation !
1. Short-range attack - attacker can offer better chain started few blocks behind current canonical chain. The attack is possible at the moment, the only likely outcome though is just gathered fees increase for an attacker. In our simulations this kind of attack is possible mostly when a long delay occurs due to low target. By the way, the attack has positive aspect for network, as it shorten delays average between blocks. So attacker gets extra fees for a good job done
2. Long-range attack - attacker can start fork hundreds or thousands blocks behind current chain. From our investigations the attack isn't possible.
3. Nothing-at-stake attack - not possible at the moment! Will be possible when a lot of forgers will use multiple-branch forging to increase profits. Then attacker can contribute to all the chains(some of them e.g. containing a transaction) then start to contribute to one chain only behind the best(containing no transaction) making it winner. Previous statements on N@S attack made with assumption it costs nothing to contribute to an each fork possible and that makes N@S attack a disaster. In fact, it's not possible at all to contribute to each fork possible, as number of forks growing exponentially with time. So the only strategy for a multibranch forger is to contribute to N best forks. In such scenario attack is possible only within short-range e.g. with 25 confirmations needed 10% attacker can't make an attack. And attack is pretty random in nature, it's impossible to predict whether 2 forks will be within N best forks(from exponentially growing set) for k confirmations. So from our point of view the importance of the attack is pretty overblown.
4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.
If you know any other kind of attack, please add. Please note IPO properties of a concrete coins etc isn't related to proof-of-stake distributed consensus problems.
And Consensus Research is going to work on better proof-of-stake prototyping & implementation !
They will soon be launching a testcoin with a modified forging algo, based on their research.
February 09, 2015, 03:18:32 PM
Thank you very much for your feedback and the links. I am still reading the linked material, but the second link forum thread from 2012 sounds a lot like what I formalized. It also looks like there are well-known data structures that are more efficient than what I used.
The main reason I emphasized proof of stake is that the technique gives a way to check the stake only using the header, something that I think is new. (Though now that I know about your links and the altcoin Cryptonite, I think it's fair to say that it was already known it could be done this way.) In the white paper I remained agnostic on the consensus mechanism until the end when I needed to describe a block header. By the way, the people behind Consensus Research are doing some work regarding the security of proof of stake (also making use of Coq). I'm watching their work with interest.
I didn't extract the code and try to run it, so I don't make claims about the efficiency. It's just theory at the moment.
My intention is to extend the theory to include some different kinds of "assets" and then try to implement it. What I want is a block chain for use with distributed theorem proving. The block chain would record what definitions have been made, what theorems have been proven, and in what order. I can also imagine people putting bounties on conjectures, and similar ideas. My current guess is that the security and efficiency for this application needs to be "good enough." I'll be surprised if it comes under serious attack. One never knows. If it does come under attack and fail, then at least it would give information that might help people who try again later.
Finally, thank you for pointing me to Peter R's "spin-offs" thread. I think this is a better way to do an initial distribution than anything else I've seen.
The main reason I emphasized proof of stake is that the technique gives a way to check the stake only using the header, something that I think is new. (Though now that I know about your links and the altcoin Cryptonite, I think it's fair to say that it was already known it could be done this way.) In the white paper I remained agnostic on the consensus mechanism until the end when I needed to describe a block header. By the way, the people behind Consensus Research are doing some work regarding the security of proof of stake (also making use of Coq). I'm watching their work with interest.
I didn't extract the code and try to run it, so I don't make claims about the efficiency. It's just theory at the moment.
My intention is to extend the theory to include some different kinds of "assets" and then try to implement it. What I want is a block chain for use with distributed theorem proving. The block chain would record what definitions have been made, what theorems have been proven, and in what order. I can also imagine people putting bounties on conjectures, and similar ideas. My current guess is that the security and efficiency for this application needs to be "good enough." I'll be surprised if it comes under serious attack. One never knows. If it does come under attack and fail, then at least it would give information that might help people who try again later.
Finally, thank you for pointing me to Peter R's "spin-offs" thread. I think this is a better way to do an initial distribution than anything else I've seen.
February 08, 2015, 07:34:45 PM
Greetings, interesting work.
I'm not sure if you're aware of it, but Bitcoin core hasn't used the blockchain for verification for years; instead it uses a compact state summary and differences which we call the UTXO set (unspent transaction outputs). Among other things, this allows you to run a Bitcoin full node with under 1GB storage.
The UTXO set is not authenticated in Bitcoin core today, it's just locally generated-- though the utility of a committed utxo set has been known for years (also, somewhat later https://bitcointalksearch.org/topic/ultimate-blockchain-compression-w-trust-free-lite-nodes-88208) it's a rather expensive commitment (e.g. a single spend/create update is factor log(utxo) more IO required) and perhaps not as useful as it seems-- if nodes do not construct their own but jump in mid-stream they only have SPV security of the history. SPV security is a substantial step down from the Bitcoin security model (in particular people expect the full node rules to limit the damage of dishonest miners) but it might still be reasonable-- but if you're willing to accept SPV security why not go all the way and use a SPV node at a massive cost savings?
With respect to proof of stake, I'm disappointed to see it just applied here with no analysis to the actual security model being used. It appears to be impossible to achieve the same security model as Bitcoin with POS; existing systems compromise with centralized block signers or other external sybil-proof beacon assumptions (which seemingly could just replace the blockchain entirely if you really trusted them). For some applications these might be reasonable trade-offs, but if they're ignored or pretended to be the same trafeoffs as Bitcoin, thats just sloppy cryptography. I'd encourage you to not take these things for granted.
I haven't reviewed your COQ yet, but have you benchmarked the performance of your extractions? Having some formal statements of the system is interesting indeed, but perhaps of low utility if there isn't a way to get extractions with acceptable computational/memory performance.
What you're calling a 'snapshot' has been described before (by PeterR) as 'spinoffs'.
I'm not sure if you're aware of it, but Bitcoin core hasn't used the blockchain for verification for years; instead it uses a compact state summary and differences which we call the UTXO set (unspent transaction outputs). Among other things, this allows you to run a Bitcoin full node with under 1GB storage.
The UTXO set is not authenticated in Bitcoin core today, it's just locally generated-- though the utility of a committed utxo set has been known for years (also, somewhat later https://bitcointalksearch.org/topic/ultimate-blockchain-compression-w-trust-free-lite-nodes-88208) it's a rather expensive commitment (e.g. a single spend/create update is factor log(utxo) more IO required) and perhaps not as useful as it seems-- if nodes do not construct their own but jump in mid-stream they only have SPV security of the history. SPV security is a substantial step down from the Bitcoin security model (in particular people expect the full node rules to limit the damage of dishonest miners) but it might still be reasonable-- but if you're willing to accept SPV security why not go all the way and use a SPV node at a massive cost savings?
With respect to proof of stake, I'm disappointed to see it just applied here with no analysis to the actual security model being used. It appears to be impossible to achieve the same security model as Bitcoin with POS; existing systems compromise with centralized block signers or other external sybil-proof beacon assumptions (which seemingly could just replace the blockchain entirely if you really trusted them). For some applications these might be reasonable trade-offs, but if they're ignored or pretended to be the same trafeoffs as Bitcoin, thats just sloppy cryptography. I'd encourage you to not take these things for granted.
I haven't reviewed your COQ yet, but have you benchmarked the performance of your extractions? Having some formal statements of the system is interesting indeed, but perhaps of low utility if there isn't a way to get extractions with acceptable computational/memory performance.
Quote
Create an initial "genesis" ledger in which each address holds assets corresponding to the unspent transaction outputs that can be spent by that address. (I don't know a general way to handle P2SH, so I will ignore these.)
The parenthetical at the end suggests that you could use some improvement in how you're thinking about the signature system in Bitcoin. You shouldn't think in terms of addresses, addresses are just human friendly (compact) ways to encode a scriptPubKey. A scriptPubKey is a public key for the script cryptosystem, and like in other signature systems a public key is an identifier for the criteria required to sign to authenticate a signature. A UTXO oriented system should track scriptPubKeys, not addresses. (And P2SH itself shows how to make those entries constant size, with computational security). What Bitcoin does is much more general than basic multisignature-- in particular atomic swaps are not possible in a model which is constrained to simple thresholds. (Also, thresholds can be done much more efficiently than multisignature in any case, if supporting only thresholds was really the goal).What you're calling a 'snapshot' has been described before (by PeterR) as 'spinoffs'.
February 08, 2015, 04:59:57 PM
I didn't know about Cryptonite. Thank you very much for pointing it. Cryptonite's account tree/mini-blockchain approach looks very similar to what I'm describing. From a big picture point of view, I'd say it's the same. There are some differences in the details.
For example, I used an "asset based" approach instead of an "account based" approach. At the leaves of my trees would be a list of (unspent) assets rather than an account balance. (The reason was to prevent the same transaction from spending from an account twice. Cryptonite solves this problem by having a "lockheight" field after which transactions become invalid.)
Also, in my approach nodes do not need to store the full account tree. (In fact, a node might only store the root.) In practice I would expect people to store enough of the account tree to "watch" their own addresses. Miners/forgers might store the whole tree. If there were parts of the account tree that no one on the network watched, then that part of the tree would be essentially pruned.
I'll look further into Cryptonite. Thanks again.
For example, I used an "asset based" approach instead of an "account based" approach. At the leaves of my trees would be a list of (unspent) assets rather than an account balance. (The reason was to prevent the same transaction from spending from an account twice. Cryptonite solves this problem by having a "lockheight" field after which transactions become invalid.)
Also, in my approach nodes do not need to store the full account tree. (In fact, a node might only store the root.) In practice I would expect people to store enough of the account tree to "watch" their own addresses. Miners/forgers might store the whole tree. If there were parts of the account tree that no one on the network watched, then that part of the tree would be essentially pruned.
I'll look further into Cryptonite. Thanks again.
February 08, 2015, 03:48:15 PM
Interesting concept, specially when people are discussing about the size limit of the blocks in Bitcoin... But how this implementation differs from Cryptonite's implementation?
http://cryptonite.info/
http://cryptonite.info/
February 08, 2015, 03:25:00 PM
Recently I had an idea how to represent cryptocurrency ledgers as Merkle trees in a way that prevents needing to store complete transaction histories. It stores different information than the block chains of traditional cryptocurrencies, so it's not clear if it could be applied to Bitcoin or existing Altcoins. (The ideas might, however, inspire modifications of some current cryptocurrencies.)
To make sure the idea would work in theory, I wrote a Coq development. Coq is a popular proof assistant: coq.inria.fr
In it I made a number of precise definitions and proved certain results. For example, I proved that the total value of the assets in the ledger at a certain height of a valid block chain is necessarily equal to the intended number. (Even Bitcoin doesn't quite have this property, since Satoshis can be 'lost', e.g., via a mistake by a miner.)
The Coq development is now public (and open source) along with a white paper giving a high level description of the idea and an overview of some of the definitions and theorems. There is more in the Coq code than there is in the white paper. I hope to eventually write more papers going into more detail, but it will take time.
Here is the github repository with everything:
git clone git://qeditas.org/ledgertheory.git
Here is a link specifically to the white paper:
http://qeditas.org/lightcrypto.pdf
Feedback and/or questions are welcome.
Whether or not the idea would work in practice will require an implementation. I do not plan to do such an implementation at the moment. These particular ideas were something of an aside from my main interests. If someone were to implement it, it would be of great interest to me and I'm willing to answer questions to a developer who'd like to do it.
Here's how I can imagine someone could make an altcoin using the ideas.
In the Coq development and white paper, I was mainly thinking of the coin as being proof of stake. One of the advantages of the approach is that the block header has enough information to verify the claimed stake of the stakeholder. With current proof of stake coins, this isn't possible by looking at the block headers alone.
To make sure the idea would work in theory, I wrote a Coq development. Coq is a popular proof assistant: coq.inria.fr
In it I made a number of precise definitions and proved certain results. For example, I proved that the total value of the assets in the ledger at a certain height of a valid block chain is necessarily equal to the intended number. (Even Bitcoin doesn't quite have this property, since Satoshis can be 'lost', e.g., via a mistake by a miner.)
The Coq development is now public (and open source) along with a white paper giving a high level description of the idea and an overview of some of the definitions and theorems. There is more in the Coq code than there is in the white paper. I hope to eventually write more papers going into more detail, but it will take time.
Here is the git
git clone git://qeditas.org/ledgertheory.git
Here is a link specifically to the white paper:
http://qeditas.org/lightcrypto.pdf
Feedback and/or questions are welcome.
Whether or not the idea would work in practice will require an implementation. I do not plan to do such an implementation at the moment. These particular ideas were something of an aside from my main interests. If someone were to implement it, it would be of great interest to me and I'm willing to answer questions to a developer who'd like to do it.
Here's how I can imagine someone could make an altcoin using the ideas.
- Take a snapshot of the current Bitcoin block chain.
- Create an initial "genesis" ledger in which each address holds assets corresponding to the unspent transaction outputs that can be spent by that address. (I don't know a general way to handle P2SH, so I will ignore these.)
- Start the new block chain (using the ideas from the paper) from there.
In the Coq development and white paper, I was mainly thinking of the coin as being proof of stake. One of the advantages of the approach is that the block header has enough information to verify the claimed stake of the stakeholder. With current proof of stake coins, this isn't possible by looking at the block headers alone.
Jump to: