Comments (9)
One of the papers that come to mind when this came up: https://link.springer.com/content/pdf/10.1007/978-3-642-32009-5_21.pdf
from research-lab.
Instead of selecting a common HMAC key in a concensus step, I'd advise to use VRFs. They are basically HMACS with assymetric keys, and they behave well as a RO. This way every miner has their own extra trapdoor information that is publicly verifiable to be bound on the original hash, this eliminates adversarial control.
from research-lab.
from research-lab.
Actually, my idea as stated is dumb, whether with HMAC or VRF... and here is why... but it's fixable...
Say you have two random oracles H and G and proof of work is played by finding an input x such that H(block || G(x))*diff < targ. Then a miner merely stores G(x) into a table for many inputs x, orders the values of x linearly by their value G(x), and proceeds through the nonces G(x) by proceeding through their inputs according to the linear order. Nothing is saved, gained, or prevented, and in fact the miner is incentivized to collate a big table for G over time.
On the other hand, if H is a random oracle and G(-,key) is a family of keyed random oracles, then playing the game by computing H(block || G(x, block))*diff < targ prevents the miner from generating the table ahead of seeing the block. Of course, the miner selects the block, so it's possibly they can maliciously select stuff to mess with G(x, block). However, they still won't really be able to pre-compute a big table for any old block they want to publish, and it'd be more fruitful for them to merely play the POW game faithfully, I think.
from research-lab.
Note this is not a way around parallel computing: if G and H are both highly parallelizable, then someone with a block could compute many choices of G(x, block) and then compute H(block || G(x,block))*diff for all those choices.
from research-lab.
Here is a short version of an elliptic curve VRF, I can present a jupyter notebook PoC to one of the usual research meetings:
We want to prove that a||privkey
hashes to b
without disclosing b. We output b
, and a proof.
Public information:
-g
generator,
-a
the public part of the input
-H1
hashes bitstrings to the curve,
-H2
hashes points to its abscissa,
-H3
any safe hash like SHA3
- g^x the prover's public key
Private information:
x
the private part of the input i.e the asymmetric HMAC key
Prover:
h = H1(a)
- select uniform random scalar
k
c = H3(g||h||g*x||h*x||g*k||h*k)
s = k - c*x
- output
(h*x, H2(h*x) c, s)
Verifier:
h = H1(a)
u = g*x*c + g*s = g^k
v = h*x*c + h*s = h^x
- check that the proof has
c = H3(g||h||g*x||h*x||g*k||h*k)
andH2(h*x)
This construction also prevents adversaries to go ahead of the block with precomputed proofs as you modelled above. I don't know how parallelizable EC operations are now :/
from research-lab.
I've implemented the above scheme in Rust hope it can help evaluating the idea: https://github.com/Silur/ECVRF
from research-lab.
from research-lab.
Previous studies on nonce distribution for our POW algorithm suggest that our algorithm is behaving badly as a random oracle.
ASICs may be designed with greater energy efficiency when seeking nonces that solve H(block || nonce)*diff < targ within a certain range. This hmac removes the adversarial control over the nonce.
Do we really know for sure if such an efficiency gain exists? The particular non-uniform nonce distribution may be simply because of the way some miners were implemented. Your proposal may end up introducing another complexity to the protocol by "solving" a nonexistent problem.
Also, if the PoW algorithm was behaving badly as a random oracle, the correct fix IMO should be to fix the PoW algorithm itself instead of tweaking the handling of nonces.
from research-lab.
Related Issues (20)
- Exploring Trustless zk-SNARKs for Monero's payment protocol HOT 107
- Bulletproofs++ HOT 2
- Investigate possibility of reducing 10-blocks lock HOT 19
- Remove the burning bug as a class of attack with a modified shared key definition HOT 2
- Remove Extra Coinbase Locktime HOT 5
- Consider Switch commitments for future supply security HOT 29
- Radical idea for forward secrecy and instant wallet sync HOT 13
- Flashproofs
- Coinbase Consolidation Tx Type HOT 8
- Avoid selecting coinbase outputs as decoys HOT 2
- Scale the blockchain with recursive ZK proofs HOT 2
- Archiving historic nullifiers with mutator sets HOT 1
- Porting Utreexo to Monero HOT 7
- increasing uniformity of number of inputs/outputs
- Class Group-based ZK SNARKs
- Add scripting to Monero via the specification of R1CS circuits HOT 14
- based monero address decentralized IP address, Abolish ipv4 and ipv6 HOT 8
- potential measures against a black marble attack HOT 29
- Mining protocol changes to combat pool centralization HOT 16
- Catalogue of Monero decoy selection algorithms HOT 7
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from research-lab.