From: praxeology_guy <praxeology_guy@protonmail•com>
To: Natanael <natanael.l@gmail•com>
Cc: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>,
Erik Aronesty <earonesty@gmail•com>
Subject: Re: [bitcoin-dev] Properties of an ideal PoW algorithm & implementation
Date: Tue, 18 Apr 2017 15:14:05 -0400 [thread overview]
Message-ID: <d34BBx6aArm944Gm26SU3KIEqVMVbt1rx5Bnd3Cfs8Jc_uquIB5-RoMVoDoXRYXEaO_FudCUGe4y3ylqoz1JyEM7NUgS7kZMjE04dpxwkdw=@protonmail.com> (raw)
In-Reply-To: <CAAt2M1-LsEgBXhMpAn+JkBwA+Q7AwikiVFY6z0jEfj8dCCBUTw@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2561 bytes --]
Natanael,
=== Metal Layers ===
One factor in chip cost other than transistor count is the number of layers required to route all the interconnects in the desired die area constraint. The need for fewer layers can result in less patent-able costs of layering technology. Fewer layers are quicker and easier to manufacture.
I'm not an expert in the field, and I can't vouch for the validity of the entirety of the paper, but this paper discusses various factors that impact chip cost design.
http://www.cse.psu.edu/~juz138/files/3d-cost-tcad10.pdf
=== Early nonce mixing, Variable Length Input with Near Constant Work ===
To minimize asicboost like optimizations... the entirety of the input should be mixed with the nonce data ASAP. For example with Bitcoin as it is now, the 80 byte block header doesn't fully fit in one 64 byte SHA256 input block. This results in a 2nd SHA256 block input that only has 4 bytes of nonce and the rest constant that are mixed much later than the rest of the input... which allows for unexpected optimizations.
Solution: A hash algorithm that could have more linear computation time vs input size would be a 2 stage algorithm:
1. 1st stage Merkle tree hash to pre-lossy-mix-compress the variable length input stream to the size of the 2nd stage state vector. Each bit of input should have about equal influence on each of the output bits. (Minimize information loss, maximize mixed-ness).
2. Multi-round mixing of the 2nd stage, where this stage is significantly more work than the 1st stage.
This is somewhat done already in Bitcoin by the PoW doing SHA256 twice in serial. The first time is pretty much the merkle tree hash (a node with two children), and then the second time is the mult-round mixing. If the Bitcoin PoW did SHA256 three or four times or more, then asicboost like optimizations would have less of an effect.
In actual hardware, assuming a particular input length for the design can result in a significantly more optimized design than creating hardware that can handle a variable length input. So your design goal of "not linear in performance relative to input size" to me seems to be a hard one to attain... in practical, to support very large input sizes in a constant work fashion requires a trade off between memory/parallelization and die space. I think it would be better to make an assumption about the block header size, such as that it is exactly 80 bytes, or, at least something reasonable like the hardware should be able to support a block header size <= 128 bytes.
Cheers,
Praxeology Guy
[-- Attachment #2: Type: text/html, Size: 3023 bytes --]
next prev parent reply other threads:[~2017-04-18 19:14 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CAAt2M19QK9cZShOf16UmRz6me9+h_FvjaSCcq_T6aaabX_qpKg@mail.gmail.com>
[not found] ` <CAAt2M1_Eo9F+mH851GQLhCR+nAsBNrfYJeYkuHmW=Jz335Z0ZA@mail.gmail.com>
[not found] ` <CAAt2M19VuJ9iEZCvdC3OtpJkMVM8kAB2NRSFqmt2zNREOYAMaA@mail.gmail.com>
[not found] ` <CAAt2M19bmxR0hUp0rsnNZ8MoUayz82sNnOOXVzg0WXFwma4xzQ@mail.gmail.com>
[not found] ` <CAAt2M199BKp_k=cia_1APaAZwZ+EV8z=9ebWKHp3+VY68G1jYw@mail.gmail.com>
[not found] ` <CAAt2M18O3hEcGU7md7Ojsx5716QCYfP0GG9UyNudGCjRszPrFA@mail.gmail.com>
[not found] ` <CAAt2M1-18yfw+J2S+CDkRO6DT_Rj3FRQQcBhpiuujSYnnC-w7w@mail.gmail.com>
[not found] ` <CAAt2M19bgyyXsjOXEzSK2h6jTCRZDn9nw+B51yPOYhD4qUjDcw@mail.gmail.com>
[not found] ` <CAAt2M1_Yikty=W_GvRMSNdkC7xVmFyECP1cM-HBJ0vOs9jiiGg@mail.gmail.com>
[not found] ` <CAAt2M18Mdp2xJzt-ovbqF2_VSKK4-6RMtSySqso2PDcse5TuMQ@mail.gmail.com>
[not found] ` <CAAt2M188dzogU4hxardZPNyFeW0=Nu6-h5VRHaiOZ9vyoaktcw@mail.gmail.com>
[not found] ` <CAAt2M182UqUDt4jg7yY33uycaHJHWw+jfY6Qu0kEf=FsyUzMYQ@mail.gmail.com>
[not found] ` <CAAt2M18+Moq-+twzqpuZiJM7+q_-wuu=rskvp+srKH2PEH5Ziw@mail.gmail.com>
[not found] ` <CAAt2M1-Vr+k5kwqbJqbo-UgSXA7v0YesN6WrtFMjdaniMAmJ+A@mail.gmail.com>
[not found] ` <CAAt2M1_2ADtYjSbE-0RDZ8DSvfx+O82AkeNeBXo0bzy-KTfD_w@mail.gmail.com>
[not found] ` <CAAt2M19WRsM3XGhL_ghnkywAuuvcosx0aMCjYxpvWdnAqV_0Yw@mail.gmail.com>
[not found] ` <CAAt2M1-aqTmj2FQcYRrv5oe0Ly3j8ywQYE-DhCrvF7jp2ghs2w@mail.gmail.com>
[not found] ` <CAAt2M1_KJqcKWcckvYG3Yy0mMqHUfPfD5vfkxtZWcJ_KexkCzA@mail.gmail.com>
[not found] ` <CAAt2M18-RCFqxqDptsjrHAWcExQibfgxJH+duh_zN1_-1XHTEw@mail.gmail.com>
[not found] ` <CAAt2M1-0i=6wcL2+On5G=v-nMpw6pO9fa3FoxF30JO8vtZL8hA@mail.gmail.com>
[not found] ` <CAAt2M19nyUy4U7cURD7TVbvEzN=v+Roq=W4qrjYQ4=1jP_ojdQ@mail.gmail.com>
[not found] ` <CAAt2M1907HBkXcMMTUybSUT1uSibJ9dTKSiRmrqsSzm_qM58gg@mail.gmail.com>
[not found] ` <CAAt2M19ezOG1=Bpps54Sk=n+KhvgAVNaMa-=vfr6FNSMFhKyHg@mail.gmail.com>
[not found] ` <CAAt2M1_KiJfhjo8Qk4cLQXZ+4=8nZeeHS0gVrNDV75kcfkJaFQ@mail.gmail.com>
[not found] ` <CAAt2M1-WSjfxxX60DBgkkhaRZUTy4cn=zgHZUThiU1p2VdxGnQ@mail.gmail.com>
[not found] ` <CAAt2M18-9WVs7OgeEREMSFQXMg6p865U2mczivU3jZF7SKmD=g@mail.gmail.com>
[not found] ` <CAAt2M1_siUEfXsWB5Hj3V5tcm6xboVjjYNZhS4Pn4YBw6YQv7A@mail.gmail.com>
[not found] ` <CAAt2M1_AdwAoc981zs0ObwBuefQwyi6XqWF8VXLe+ojz0802eA@mail.gmail.com>
[not found] ` <CAAt2M1_A6m=s6hwURNF7WUbQKvshEOROPySuDwvjSMisdwLbXA@mail.gmail.com>
[not found] ` <CAAt2M1_d2ycOW3TPF0_nRyzK_v-kzko3Zw8KCzMhCp2KNOg0DA@mail.gmail.com>
[not found] ` <CAAt2M18MeqTXLd1KpyzRoKb9C2fzj1rr4E89kvkGU_Yjda0goQ@mail.gmail.com>
[not found] ` <CAAt2M1_pDJrSghsd5eSA3p_6FZkix1HdcjKeUrGDN8Hkwrcm2w@mail.gmail.com>
[not found] ` <CAAt2M1_2buzQgcybVv8qQLRgcnD0uzj43cOyS53HJdzicJ6_PA@mail.gmail.com>
[not found] ` <CAAt2M1-t8w1Tw2sgG2RPmpqcCuwdc3piB_6pj2cj-CnXqFwDsw@mail.gmail.com>
[not found] ` <CAAt2M1_O2GHpYTMqf6Sr0se+6XMKaKeVXFfqGYkPD537sqFfAw@mail.gmail.com>
[not found] ` <CAAt2M18P_=Nd+Q7=0CKGfpf47+0MDWNgPV3+BRVthGFz8ref-Q@mail.gmail.com>
[not found] ` <CAAt2M19igqAzme9_G+0sKDaaDPsFOUcp9m15XmnNXTYjtSVYjA@mail.gmail.com>
[not found] ` <CAAt2M1-FLeQAAKWcM-xEpsDD0P=yJLhMYwzQ72xzFLqovo9SsQ@mail.gmail.com>
[not found] ` <CAAt2M18Pe6GJUxoiZSO-kiexj+mv+nAP4vvFiWvaafEBRCy08w@mail.gmail.com>
[not found] ` <CAAt2M1822oiWBO+QxiUUO+3qnLxSFYz4Uh-77=omo-N6RCsc1g@mail.gmail.com>
[not found] ` <CAAt2M1_rzKX27=naLKdyWh8Cfb3iCY+TUCmi8etJKUmNpGpW=g@mail.gmail.com>
[not found] ` <CAAt2M1_UZobHAjbEYV0=fPOSJzM+sm_GnLmvtqdFCQqyU0EmrA@mail.gmail.com>
[not found] ` <CAAt2M1896xctLXp0ae+eGK9jsAM2w4XTk1XVpzZm0CbGLAt7Lw@mail.gmail.com>
[not found] ` <CAAt2M1-5Lw497BHn=n2+maTnAdGzzosLacN7+hvcj2EQ9wyWyA@mail.gmail.com>
[not found] ` <CAAt2M18qXJNwWoVDrAOfxaqkSyqwQeEWmHCNRpkbigjE__T44w@mail.gmail.com>
[not found] ` <CAAt2M1_5tqKwLuGBTY9GjhEK-Mn-9Pr=_hoGD0=p85oFuzTLzw@mail.gmail.com>
[not found] ` <CAAt2M1-MArg6HUT5D-VnQVAS+1nmPGKp-LTOPnzSueWxKz8imQ@mail.gmail.com>
[not found] ` <CAAt2M18F+RhOuVSrimpmBp8h7BqBhU6wYJYR+b0Rx_dHAdyXGw@mail.gmail.com>
[not found] ` <CAAt2M1_D8STg96jqscU1Z=uTntwFvSZ5MTuJLmNJ05jLZ9p8rg@mail.gmail.com>
[not found] ` <CAAt2M1_+BKObb27LR87JjbpTnZbg0AGCA8uh7Ks03bf459x7jg@mail.gmail.com>
[not found] ` <CAAt2M18VCjufEU3H4ENRuMcAfTbj5A73S8t2zXsvL8y2UyZhew@mail.gmail.com>
[not found] ` <CAAt2M19NScrLv3ax_=PCPW4-L466js=H29ogVCOgAVbk6Xma_g@mail.gmail.com>
[not found] ` <CAAt2M1_n-p20OK_ibzx5qrh_BVtat3=rs5vL+6TF5rAPi1iExg@mail.gmail.com>
[not found] ` <CAAt2M1-bk9B7B45AKYOKyB7s_LF8ckBw51OdyTqG2JguRxR-9Q@mail.gmail.com>
[not found] ` <CAAt2M1_hwHE-tm2OppnnogQruB8bhyR6Cc+bNVP5ZrTNv92-Rg@mail.gmail.com>
[not found] ` <CAAt2M1-YVEAGBy9cQ1q0siOPpC5C8wh-mdz=m8W33boN1dc5CQ@mail.gmail.com>
[not found] ` <CAAt2M197Mj5sWGY1gewoKHYwsOiSf=38c5DVv7CH+gfJ1Khe-w@mail.gmail.com>
[not found] ` <CAAt2M1_RdOOq11uzNLShvVNaDYMRw_3S1JhbKfy_cv_3F7z-cA@mail.gmail.com>
[not found] ` <CAAt2M1-wv1tWKpo+sEMAuKD79vVX6JhtOFOgbxPtOD6LckdW8g@mail.gmail.com>
[not found] ` <CAAt2M194fKBctfgQmXv2a8OSrYEa_X=cpzQT45OvnpH+B_BA2A@mail.gmail.com>
[not found] ` <CAAt2M1-Y7+dQc7aLvES-y0rz9YXOsdp-Ou+CERs-EmpRp3N=Ng@mail.gmail.com>
[not found] ` <CAAt2M18HF2-+dpSF=bR8rw3jR1-i-_FdK9DnvHHEwMq_b7rs6w@mail.gmail.com>
[not found] ` <CAAt2M19x0vcHG2-Vs9aq-OjgxKg1pHSw8oS=gxAQv8VaugSgGA@mail.gmail.com>
[not found] ` <CAAt2M19w81CiLQStMaH+5LXukvYmxvZqWdR5R6Cf37bJS2Ci0A@mail.gmail.com>
[not found] ` <CAAt2M1-PWBdBqc4w0kbTvzaSq7O+39Hj1v1uZD0uM1-AvgLk1w@mail.gmail.com>
[not found] ` <CAAt2M1_-KM3y-wOnAc-3bFJzJVz3GooSG0h_rixofd61R3h6gA@mail.gmail.com>
[not found] ` <CAAt2M1_YdK6n4B_tsJsCeKRNnG_p+e4mH=D_Jz1FkeYL1y54TA@mail.gmail.com>
[not found] ` <CAAt2M187-81ED8ZLf6F7m324RLBwB6u62=iPMbr9FD9qnu1XJw@mail.gmail.com>
[not found] ` <CAAt2M1_C_3wv9g7auCSg_ECZ=gbxAPumcfZZZO=o5Ly4VV+GvA@mail.gmail.com>
[not found] ` <CAAt2M1-a66K=uqOkGiHuuzU1qEPan6RHoRfwC+YVFeU94JBxNw@mail.gmail.com>
[not found] ` <CAAt2M1-RXYxVuNBDdKrnyWow6PCNDeGawv0gQx+jn4f-3xuumg@mail.gmail.com>
[not found] ` <CAAt2M1-kpQyK2bQyHM=vy2oor75m30frHLGk_phPs10gLsH14A@mail.gmail.com>
2017-04-18 10:34 ` Natanael
2017-04-18 19:14 ` praxeology_guy [this message]
2017-04-19 11:08 ` Tim Ruffing
2017-04-19 17:43 ` Bram Cohen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='d34BBx6aArm944Gm26SU3KIEqVMVbt1rx5Bnd3Cfs8Jc_uquIB5-RoMVoDoXRYXEaO_FudCUGe4y3ylqoz1JyEM7NUgS7kZMjE04dpxwkdw=@protonmail.com' \
--to=praxeology_guy@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=earonesty@gmail$(echo .)com \
--cc=natanael.l@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox