[关闭]
@zhongdao 2017-12-22T03:14:07.000000Z 字数 13327 阅读 2520

Part3 计算机基础与密码学v2


Part1: 比特币与区块链v2 https://www.zybuluo.com/zhongdao/note/994815
Part2: 区块链设计与实现笔记v2 https://www.zybuluo.com/zhongdao/note/992471
Part3: 计算机基础与密码学v2 https://www.zybuluo.com/zhongdao/note/992687

拟定目录大纲:
Part1: 比特币与区块链
1. 比特币技术原理
2. 比特币协议
3. 硬分叉
4. 侧链设计原理
5. 侧链开发
6. 智能合约设计原理
7. 智能合约开发
8. 区块链生态介绍
9. 区块链应用

Part2: 设计与实现笔记
1. 区块链原理机制与背景
2. 区块链基本结构
3. 加解密算法实现
4. 区块数据结构从定义到初步实现
5. 区块节点读取验证与挖矿
6. 节点和应用程序之间协议
7. 节点之间沟通

Part3: 计算机基础与密码学
1. 计算机基础知识
1. Linux相关说明
3. 密码学相关说明
4. 程序开发语言相关说明
5. 虚拟机语言

第三期课程:
区块链设计与实现笔记v1: https://www.zybuluo.com/zhongdao/note/933849

若有更正请联系: 李君
邮件: junlicn@foxmail.com
2017.12.20

实际自动导航目录:

目录不可见时访问: https://www.zybuluo.com/zhongdao/note/933849

Part3: 区块链相关基础知识
1. 计算机基础知识
1. Linux相关说明
3. 密码学相关说明
4. 程序开发语言相关说明
5. 虚拟机语言

12. 计算机基础

图灵完备

图灵完备是什么意思呢?
在可计算理论中,当一组数据操作的规则(一组指令集,编程语言,或者元胞自动机)满足任意数据按照一定的顺序可以计算出结果,被称为图灵完备(turing complete)。一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的,它(计算机设备)有能力执行条件跳转(“if” 和 “goto”语句)以及改变内存数据。 如果某个东西展现出了图灵完备,它就有能力表现出可以模拟原始计算机,而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的(C++ template就是图灵完备的),都能解决内存有限的问题。图灵完备的机器都被定义有无限内存,但是机器指令集却通常定义为只工作在特定的,有限数量的RAM上。

图灵不完备的语言常见原因有循环或递归受限(无法写不终止的程序,如 while(true){}; ), 无法实现类似数组或列表这样的数据结构(不能模拟纸带). 这会使能写的程序有限图灵完备可能带来坏处, 如C++的模板语言, 模板语言是在类型检查时执行, 如果编译器不加以检查,我们完全可以写出使得C++编译器陷入死循环的程序.图灵不完备也不是没有意义, 有些场景我们需要限制语言本身. 如限制循环和递归, 可以保证该语言能写的程序一定是终止的.

操作系统中字节表示

32位系统中, 标准数字用4个字节表示. 整数的范围是2的32次方.
64位系统中, 定义证书int 也是4个字节. long int 时是8字节

字符串通过ASCII码来表示0-255范围内与字母等的对应.
中文字有其他的规则来对应. 例如utf8.

image_1btoa8s9oog1chl4ct1c3t24e9.png-152.3kB

Windows研发思想的来龙去脉

多进程的管理来自于UNIX

从系统的角度, 和从进程自己的角度来看内存.
程序自己的地址是连续的, 实际系统中不是连续的, 是多个程序公用内存段落.

  1. graph LR
  2. unix-->OpenVMS
  3. OpenVMS-->WindowsNT
  4. WindowsNT -->Windows2000
  5. Windows2000-->WindowsXP

UNIX --> BSD
--> SysV
---> Linux

执行程序对比

系统文件对比 执行 动态链接库 静态链接库 编译结果 源文件
windows: .exe .dll .lib .obj .c
linux: 无后缀 .so .a .o .c
  • 编译器是把非执行文件转换成执行文件。
  • .exe:直接运行程序,
  • .dll:一套函数不能运行,但可以在另一个程序运行的,更高级也可一共享,程序运行中可以引用的。
  • .lib:造一个程序可以运行,但必须重新编译才成实现,程序可以互相共享
  • .obj:链接以前的编译结果,一个程序有若干个源程序,一个源程序一个Obj文件。半成品文件编译还未处理
  • .a 是若干个 .o 组成的,.a 到 .so 需要加若干个源数据。.so是 .a加工后的。

BASE64

Base64说明:
https://baike.baidu.com/item/base64/8545775?fr=aladdin

Base64是网络上最常见的用于传输8Bit字节码的编码方式之一,Base64就是一种基于64个可打印字符来表示二进制数据的方法。可查看RFC2045~RFC2049,上面有MIME的详细规范。
Base64编码是从二进制到字符的过程,可用于在HTTP环境下传递较长的标识信息。例如,在Java Persistence系统Hibernate中,就采用了Base64来将一个较长的唯一标识符(一般为128-bit的UUID)编码为一个字符串,用作HTTP表单和HTTP GET URL中的参数。在其他应用程序中,也常常需要把二进制数据编码为适合放在URL(包括隐藏表单域)中的形式。此时,采用Base64编码具有不可读性,需要解码后才能阅读。在MIME格式的电子邮件中,base64可以用来将binary的字节序列数据编码成ASCII字符序列构成的文本。

执行速度

TCP 接收 HTTP

以 GET, POST, PUT, DELETE, HEAD 开头.

内存中栈与堆的区别

堆和栈的第一个区别就是申请方式不同:栈(英文名称是stack)是系统自动分配空间的,例如我们定义一个 char a;系统会自动在栈上为其开辟空间。
而堆(英文名称是heap)则是程序员根据需要自己申请的空间,例如malloc(10);开辟十个字节的空间。

由于栈上的空间是自动分配自动回收的,所以栈上的数据的生存周期只是在函数的运行过程中,运行后就释放掉,不可以再访问。
而堆上的数据只要程序员不释放空间,就一直可以访问到,不过缺点是一旦忘记释放会造成内存泄露。
从下面代码可以看出:

  1. int a = 0; //全局初始化区
  2. char *p1; //全局未初始化区
  3. main()
  4. {
  5. int b; //栈
  6. char s[] = "abc"; //栈
  7. char *p2; //栈
  8. char *p3 = "123456"; //123456\0在常量区,p3在栈上。
  9. static int c =0 //全局(静态)初始化区
  10. p1 = (char *)malloc(10); //堆
  11. p2 = (char *)malloc(20); //堆

image_1bu134etlerc8641f4g1dagglep.png-74.9kB

状态机

..

形式语言

..

stack based machine

Compilers for stack machines are simpler and quicker to build than compilers for other machines. Code generation is trivial and independent of prior or subsequent code. For example, given an expression x+y*z+u, the corresponding syntax tree would be:

image_1bv3kbvvj4uf12u31ata1avc1n8f1g.png-33.9kB

The compiled code for a simple stack machine would take the form:

  1. push x
  2. push y
  3. push z
  4. multiply
  5. add
  6. push u
  7. add

逆波兰表达式

Reverse Polish Notation
逆波兰表达式,它的语法规定,表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。
可以将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)(c+d)转换为ab+cd+
它的优势在于只用两种简单操作,入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下:
如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
在数据结构和编译原理这两门课程中都有介绍,下面是一些例子:

4 * ( A + B) 的堆栈变化过程示意:
image_1bv3bj49g17661el1ql71heauap9.png-10.1kB
(6*(4+5) - 25 )/(2+3) 的例子的二叉树表示:
image_1bv3cqt0g1n611dr21l6ms6k1t0j1g.png-59.3kB
3*4+5*6 = 42 的整个计算过程图示:
image_1bv3bpor7s2rlma19dl1id5dn913.png-382.2kB
12 * ( 3 + 4 ) - 6 + ( 8 / 2 ) = 82 的运算过程图示:
image_1bv3d1c4s1aij1s71uvn437m2t9.png-17.2kB

正常的表达式 ---> 逆波兰表达式
a+b ---> a,b,+
a+(b-c) ---> a,b,c,-,+
a+(b-c)*d ---> a,b,c,-,d,*,+
a+d*(b-c)--->a,d,b,c,-,*,+
a=1+3 ---> a=1,3 +
http=(smtp+http+telnet)/1024 写成什么呢?
http,smtp,http,+,telnet,+,1024,/,=

Postfix evaluation algorithm

  1. for each token in the postfix expression:
  2. if token is an operator:
  3. operand_2 pop from the stack
  4. operand_1 pop from the stack
  5. result evaluate token with operand_1 and operand_2
  6. push result back onto the stack
  7. else if token is an operand:
  8. push token onto the stack
  9. result pop from the stack

13. Linux相关说明

13.1 基础操作

设置文本编译器

  1. alias nano = "nano -w -x -E -T 3 -I -S"

16进制展示与xxd

xxd 可用来查看生字节的16进制展示.

以下是个示例.
每行16个字节. 每4个字母数字为2个字节.

  1. $ xxd 1.block
  2. 0000000: 196f d33e b38e 61d5 4579 d98e 16d1 ac4e .o.>..a.Ey.....N
  3. 0000010: 279e 065c 07d7 5461 42b7 fe60 d226 72bc '..\..TaB..`.&r.
  4. 0000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
  5. 0000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
  6. 0000040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
  7. 0000050: 0000 0000 0000 0000 0000 0000 0000 0000 ................

字节的计算过程:
e8 : 232
e803 = 232 + 256 *3 = 1000
图中所示, 前2个字节表示整数1000

  1. 00000e0: e803 0000 0000 0000 0000 0000 0000 0000 ................

linux终端共享使用说明

作共享屏幕:

  1. tmux -S $SOCKET new -t $SESSION

接入共享屏幕

  1. tmux -S $SOCKET attach -t $SESSION -r

-r 参数表示只读, 去掉可以一起写.

示例:

  1. tmux -S /tmp/330 attach -t 0 -r
  2. or
  3. sh /tmp/a

linux 传统安装

linux来源于unix的传统, 安装时会将不同的文件如设置,执行,变量会放在不同的路径

13.2 编译执行相关

程序运行过程

head |... |... |... |... |... |
section

_start()
initialize libc.so
run main()
libc.so and system call are heavily dependedt up global variables(全局变量)
argc argv envp

对于复杂的命令行参数,需要parser,analyzer来分析. 简单起见,也可以把顺序等写死.

./bitcoind --help
conciseCoin
./ccn -k yuanxun.private -s /tmp/blocks
argv1 argv2 argv3

image_1buksdg4vk6r1ddd1eo266n1aek9.png-96.5kB
命令行参数argc 与argv 在内存中的图示:
image_1bukrl5tp1gbi108018po15cc1vbs9.png-104.2kB

编译执行源代码:

  1. tcc -c program.c -o program.o
  2. tcc -o program.elf program.o libtfm.a libtomcrypt.a
  3. ./program.elf

注意: 编译时文件名的顺序不要变, 否则无法编译通过.

查看库

  1. 查看库的函数名
  2. $ readelf -S libtomcrypt.a | grep File
  3. File: libtomcrypt.a(aes.o)
  4. File: libtomcrypt.a(aes_enc.o)
  5. File: libtomcrypt.a(anubis.o)
  6. File: libtomcrypt.a(blowfish.o)
  7. File: libtomcrypt.a(camellia.o)
  8. File: libtomcrypt.a(cast5.o)
  9. File: libtomcrypt.a(des.o)

nc

多进程多线程

  1. multiprocess 多进程
  2. multithread 多线程
  3. poll/select

symmetric asymmetric

如果一个应用程序去处理多个设备,例如应用程序读取网路数据,按键,串口,一般能想到的有三种方法:
方法1:
串行+阻塞的方式读取:
while(1) {
read(标准输入);
read(网络);
}
缺点:每当阻塞读取标准输入时,如果用户不进行标准输入的操作,而此时客户端给服务器发送数据,导致服务器无法读取客户端发送来的数据!

方法2:
采用多线程或者多进程机制来实现读取:
开辟多个线程,每一个线程处理一个设备,不会导致的数据的无法读取,但是系统的开销相比方法1要大!

方案3:采用linux系统提供的高级IO的处理机制
select/poll:两者一样,主进程能够利用select或者poll能够对多个设备进行监听!

14. 程序开发语言相关说明

14.1 C语言

14.1.1 C语言基础

  1. #include "stdio.h" 包含输入和输出相关的函数 printf() fopne() fread() fwrite() fclose()
  2. #include "stdlib.h" 包含内存管理的函数 malloc() free()
  3. #include "string.h" 包含字符串处理的函数 strlen() strtok() strcpy()
  4. #include "sys/socket.h" 包含套接字的函数
  5. #include "arpa/inet.h" 互联网套接字函数

14.1.2 注意点

构造8字节, 64位的数字处理

32位的机器, 要想创造64位的整数,
C语言里long long int 会分配一个64位的整数.
用特定的函数来支持. 编译器支持. 虽然机器本身不支持.

  1. unsigned char *y;
  2. unsiged int z;
  3. y = malloc(8); // 分配8个字节
  4. z = 1000; // 4个字节的变量z
  5. memcpy(y, &z, 4); // 把 4个字节的z 复制到 y上.
  6. memset(y + 4, 0, 4); // 后4个字节补充0.

memset与填充0

buffer 在创造时( malloc() ), 不会自动地填充成0. 所以可以用memset.

  1. buffer = malloc(1000);
  2. memset(buffer,0,1000);

void 指针

课上bug已解,原因是C语言不能从void类型的指针中取值,需要进行两次强转,形式如下:

  1. while ((int)list != 0 ) {
  2. data = (unsigned char *) *((int *) list);
  3. printf("value: %d%c", (int)data, 10);
  4. list = (void *)*((int *) (list + 4));
  5. printf("list: %d%c", (int)list, 10);
  6. }

文件结束符

当公钥存在一个文件里.
文件里可能会增加一个跳行. 引起base64的函数转变的崩溃. 因为base64没有跳行字符.
最好是拿之前的函数来读文件, 判断最后一个字符是不是10, 若是10要去掉. 倒数第二个是10也要删掉.
或者把 钥匙 放在代码变量里.

signed char 与 unsigned char区别

signed char取值范围是 -128 到 127(有符号位)
unsigned char 取值范围是 0 到 255
char 到底是signed char还是unsigned char?这得看编译器.

  1. #include <stdio.h>
  2. int main(void)
  3. {
  4. signed char a = -1;
  5. unsigned char b = -1;
  6. printf("%%d:\n");
  7. printf("signed: %d\n", a);
  8. printf("unsiged:%d\n", b);
  9. printf("%%u:\n");
  10. printf("signed: %u\n", a);
  11. printf("unsigned: %u\n", b);
  12. }
  1. %d:
  2. signed: -1
  3. unsiged:255
  4. %u:
  5. signed: 4294967295
  6. unsigned: 255

uint8_t\uint_16_t\uint32_t\uint64_t

一般来说整形对应的*_t类型为:
uint8_t为1字节
uint16_t为2字节
uint32_t为4字节
uint64_t为8字节
1. 这些类型的来源:这些数据类型中都带有_t, _t 表示这些数据类型是通过typedef定义的,而不是新的数据类型。
2. 在涉及到跨平台时,不同的平台会有不同的字长,所以利用预编译和typedef可以方便的维护代码。
3. 在C99标准中定义了这些数据类型,具体定义在:/usr/include/stdint.h ISO C99: 7.18 Integer types

14.2 php语言

函数说明

ord()

把字母转成字节

hash

string hash ( string data [, bool $raw_output = false ] )

  1. 参数
  2. algo
  3. 要使用的哈希算法,例如:"md5""sha256""haval160,4" 等。
  4. data
  5. 要进行哈希运算的消息。
  6. raw_output
  7. 设置为 TRUE 输出原始二进制数据, 设置为 FALSE 输出小写 16 进制字符串。
  8. 返回值
  9. 如果 raw_output 设置为 TRUE 则返回原始二进制数据表示的信息摘要, 否则返回 16 进制小写字符串格式表示的信息摘要。

http://php.net/manual/zh/function.hash.php

array_push()

将一个或多个单元压入数组的末尾(入栈)

  1. $a=array("Dog","Cat");
  2. array_push($a,"Horse","Bird");//内容加到数组中
  3. print_r($a);

输出:

  1. Array
  2. (
  3. [0] => Dog
  4. [1] => Cat
  5. [2] => Horse
  6. [3] => Bird
  7. )

array_shift()

将数组开头的单元移出数组
另外, array_unshift()在数组开头插入一个或多个单元

  1. $stack = array("Java", "Php", "C++", "C#", "Ruby");
  2. array_shift($stack);
  3. print_r($stack);
  1. Array
  2. (
  3. [0] => Php
  4. [1] => C++
  5. [2] => C#
  6. [3] => Ruby
  7. )

15. 密码学相关说明

密码学在区块链的应用:hash函数 椭圆曲线数字签名

image_1btobo6mh1cpr16ui1lvo3erlvj1g.png-39kB

hash的应用

1.Tx的hash和Merkle root
2.地址生成 —>节约空间
3.挖矿 hash(x||N)难于解决易于验证
4.连接

image_1btobljiu1bq0i1t1q3c1g5l12tn13.png-155.3kB

椭圆曲线

Elliptal Cirue Digital Signature Algorthim
ECC: Elliptal Curve Crypeogaphy. 加解密
ECDSA: 签名和验证的.

超级计算机速度: 4万亿/s
找到碰撞 需要计算 4万亿年.

16. 资料链接

课程相关链接

课程直播地址:
http://www.itdks.com/dakashuo/playback/1428

第13次课程屏幕录屏:
http://pan.baidu.com/s/1nviNO1b

老师开发的wiki,记录一些知识:
http://d111.learningchain.cn

比特币与区块链介绍

对未来产生影响最大的科技
http://open.163.com/movie/2016/9/P/1/MC0Q7LQR3_MC0Q97OP1.html

比特币原理图示与解释
https://visual.ly/community/infographic/technology/bitcoin-infographic

区块链技术文档

Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto
https://bitcoin.org/bitcoin.pdf

比特币白皮书:一种点对点的电子现金系统 中文翻译版, 中本聪
http://www.8btc.com/wiki/bitcoin-a-peer-to-peer-electronic-cash-system

GitHub - bitcoinbook/bitcoinbook: Mastering Bitcoin 2nd Edition - Programming the Open Blockchain https://github.com/bitcoinbook/bitcoinbook
精通比特币中文第1版
http://book.8btc.com/master_bitcoin
精通比特币第二版中文版
http://book.8btc.com/masterbitcoin2cn

Merkle Tree(默克尔树)算法解析
http://blog.csdn.net/wo541075754/article/details/54632929

介绍几本关于比特币和区块链的书
https://www.zhihu.com/question/35541188

比特币背后的密码学原理
http://www.jianshu.com/p/225ff9439132

侧链

解释与白皮书:
A SIMPLE EXPLANATION OF BITCOIN “SIDECHAINS”
https://gendal.me/2014/10/26/a-simple-explanation-of-bitcoin-sidechains/

sidechains
https://www.slideshare.net/crainbf/sidechains-presentation

blockstream公司的开源侧链模板项目elements:
https://elementsproject.org/

区块链架构与开发

区块链技术可视化演示

演示视频:
http://www.iqiyi.com/w_19ruazv201.html
演示学习网站:
http://blockchaindemo.io/
https://anders.com/blockchain/
可视化演示代码:
https://github.com/anders94/blockchain-demo

bitcoin script

bitcoin Script wiki说明
https://en.bitcoin.it/wiki/Script

在线script演示

https://webbtc.com/script
http://www.crmarsh.com/script-playground/

比特币开发

官方网站开发
https://bitcoin.org/en/development
https://bitcoin.org/en/developer-guide

bitcoin wiki(非官方,确是最完整的比特币文档wiki)
https://en.bitcoin.it/wiki/Main_Page

bitcoin 协议规格
https://en.bitcoin.it/wiki/Protocol_documentation

比特币难度公式:
https://en.bitcoin.it/Difficulty
https://en.bitcoin.it/wiki/Target

其实并没有什么比特币,只有 UTXO
http://8btc.com/article-4381-1.html
比特币UTXO的原理?
https://www.zhihu.com/question/59913301

区块链应用

区块链技术是什么?未来可能用于哪些方面?
https://www.zhihu.com/question/27687960

https://blockchain.info/

以太坊

wiki
https://github.com/ethereum/wiki/wiki
以太坊白皮书
https://github.com/ethereum/wiki/wiki/White-Paper
以太坊白皮书中文版
https://github.com/ethereum/wiki/wiki/%5B%E4%B8%AD%E6%96%87%5D-%E4%BB%A5%E5%A4%AA%E5%9D%8A%E7%99%BD%E7%9A%AE%E4%B9%A6
http://8btc.com/thread-2918-1-1.html

以太坊黄皮书英文版
https://ethereum.github.io/yellowpaper/paper.pdf
以太坊黄皮书中文版(关于以太坊技术的实现规范)
https://github.com/yuange1024/ethereum_yellowpaper/blob/master/Paper_Chinese.pdf
http://download.cxyym.com/blockchain/ethereum_yellowpaper_cn.pdf

网上比特币相关公开课程

在线演示区块链原理:
http://blockchaindemo.io/
http://anders.com/blockchain/

比特币和数字货币技术-Princeton University课程
https://www.coursera.org/learn/cryptocurrency

斯坦福大学公开课MOOC:比特币工程学
https://bitcoin.stanford.edu/

计算机基础

什么是图灵完备?
https://www.zhihu.com/question/20115374

内存堆和栈的区别
http://www.cnblogs.com/lln7777/archive/2012/03/14/2396164.html
数据结构之用栈实现逆波兰表达式
http://www.codes51.com/article/detail_1076640.html

parrot 虚拟机
http://www.oschina.net/p/parrot
php的数组的实现介绍
http://nikic.github.io/2012/03/28/Understanding-PHPs-internal-array-implementation.html

编程语言

php file 函数教程:
http://www.w3school.com.cn/php/php_ref_filesystem.asp

虚拟机原理与实现

How to implement a simple dalvik virtual machine
https://www.slideshare.net/ssusere3af56/how-to-implement-a-simple-dalvik-virtual-machine
register简单虚拟机
http://www.cnblogs.com/unixfy/p/3280264.html
基于栈的虚拟机的实现
http://www.cppblog.com/kevinlynx/archive/2010/04/15/112704.html
栈虚拟机源码剖析
http://www.cnblogs.com/unixfy/p/3335874.html
实现一个堆栈虚拟机
http://www.cnblogs.com/unixfy/p/3337917.html

网络编程

beej's Guide to Network Programming(2016)

UNIX Network Programming(1990) by W Richard Stevens

https://www.kernel.org/doc/man-pages Michael kerrish维护,网站分为8个部分

利用select/poll监听多个设备详解
http://blog.csdn.net/qq_28090573/article/details/51094321

密码学基础:

密码学算法应用机制
https://www.zybuluo.com/zhongdao/note/950527

一个图文并茂的比特币与其中应用的密码学算法的入门简介文章:
https://www.myblockchainblog.com/blog/blockchain-cryptography

What is a Digital Signature?
http://www.youdzone.com/signature.html

markdown 编辑器

markdown editor:
https://github.com/cloose/CuteMarkEd
cmd markdown editor:
https://www.zybuluo.com/

区块链技术公开课的公众号报道

http://mp.weixin.qq.com/s/GKXUHEHd44mGqH05SgRkBA
http://mp.weixin.qq.com/s/d0hBmFFqxWl995ZbEKqkHw
http://mp.weixin.qq.com/s/qoVkB_xzaoRNAPkaPJWddw
http://mp.weixin.qq.com/s/kF_G9bkefJdbx24wcoJ0IA
http://mp.weixin.qq.com/s/hZi0RFrjMEYCdVsiE95E6w

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注